The approximation power of moving least-squares. (English) Zbl 0911.41016

Levin, David

Math. Comput. 67, No. 224, 1517-1531 (1998).

The author investigates a general method to approximate linear functionals on spaces of multivariate functions, namely the so-called moving least-squares method. Given a data set \(\{L_i(f) \}_{i=1}^l\) (for example, \(f(x_i)\) for sample points \(x_i\in \mathbb{R}^d\)), an unknown functional \(L(f)\) (for example, \(f(x)\) for another point \(x\)) is approximated by \(\sum_{i=1}^l a_iL_i(f)\), where the coefficients are obtained by minimizing the quadratic form \(\sum_{i=1}^l w(L,L_i)a_i^2\) under the linear constraints \(\sum_{i=1}^l a_iL_i(p_j)\), \(j=1,\dots,J\). This means that the elements \(p_j\) (typically polynomials of low degree) are reproduced, while the nonnegative weight \(w(L,L_i)\) is a separation measure between the functionals \(L_i\) and \(L\) (such as a radial function of the distance of the sample point \(x_i\) from \(x\)). It is shown how this constrained minimization can be solved in a matrix formulation. For the multivariate interpolation problem and for specific choices of the weights, \(C^\infty\)-smoothness in \(x\) and the approximation order on suitable data sets are established. The paper concludes with several numerical examples, including some in a bi- and trivariate setting as well as with data-dependent separation measures.

Reviewer: E.Quak (Oslo)

MSC:

41A45	Approximation by arbitrary linear expressions
41A25	Rate of convergence, degree of approximation
65D15	Algorithms for approximation of functions

References:

[1]	F. Abramovici, 1984 The Shepard interpolation as the best average of a set of data, Technical Report, Tel-Aviv University.
[2]	M. D. Buhmann, N. Dyn, and D. Levin, On quasi-interpolation by radial basis functions with scattered centres, Constr. Approx. 11 (1995), no. 2, 239 – 254. · Zbl 0824.41010
[3]	G. Backus and F. Gilbert, 1967 Numerical applications of a formalism for geophysical inverse problems, Geophys. J.R. Astr. Soc. 13 247-276.
[4]	G. Backus and F. Gilbert, 1968 The resolving power of gross Earth data, Geophys. J.R. Astr. Soc. 16 169-205. · Zbl 0177.54102
[5]	G. Backus and F. Gilbert, Uniqueness in the inversion of inaccurate gross Earth data, Philos. Trans. Roy. Soc. London Ser. A 266 (1970), no. 1173, 123 – 192.
[6]	L. P. Bos and K. Šalkauskas, Moving least-squares are Backus-Gilbert optimal, J. Approx. Theory 59 (1989), no. 3, 267 – 275. · Zbl 0729.41008
[7]	Nira Dyn, David Levin, and Samuel Rippa, Data dependent triangulations for piecewise linear interpolation, IMA J. Numer. Anal. 10 (1990), no. 1, 137 – 154. · Zbl 0699.65004
[8]	Reinhard Farwig, Rate of convergence of Shepard’s global interpolation formula, Math. Comp. 46 (1986), no. 174, 577 – 590. · Zbl 0607.41005
[9]	Reinhard Farwig, Multivariate interpolation of arbitrarily spaced data by moving least squares methods, J. Comput. Appl. Math. 16 (1986), no. 1, 79 – 93. · Zbl 0636.65007
[10]	Richard Franke, Scattered data interpolation: tests of some methods, Math. Comp. 38 (1982), no. 157, 181 – 200. · Zbl 0476.65005
[11]	Richard Franke and Greg Nielson, Smooth interpolation of large sets of scattered data, Internat. J. Numer. Methods Engrg. 15 (1980), no. 11, 1691 – 1704. · Zbl 0444.65011
[12]	P. Lancaster and K. Salkauskas, Surfaces generated by moving least squares methods, Math. Comp. 37 (1981), no. 155, 141 – 158. · Zbl 0469.41005
[13]	D. H. McLain, 1974 Drawing contours from arbitrary data points, Comput. J. 17 318-324.
[14]	D. H. McLain, Two dimensional interpolation from random data, Comput. J. 19 (1976), no. 2, 178 – 181. · Zbl 0321.65009
[15]	D. Shepard, 1968 A two dimensional interpolation function for irregularly spaced data, Proc. 23th Nat. Conf. ACM, 517-523.