Abstract
For interpolation of scattered multivariate data by radial basis functions, an “uncertainty relation” between the attainable error and the condition of the interpolation matrices is proven. It states that the error and the condition number cannot both be kept small. Bounds on the Lebesgue constants are obtained as a byproduct. A variation of the Narcowich-Ward theory of upper bounds on the norm of the inverse of the interpolation matrix is presented in order to handle the whole set of radial basis functions that are currently in use.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
W.R. Madych and S.A. Nelson, Multivariate interpolation: a variational theory, Manuscript (1983).
W.R. Madych and S.A. Nelson, Bounds on multivariate polynomials and exponential error estimates for multiquadric interpolation. J. Approx. Theory 70 (1992) 94–114.
F.J. Narcowich and J.D. Ward, Norm of inverses and condition numbers for matrices associated with scattered data. J. Approx. Theory 64 (1991) 69–94.
F.J. Narcowich and J.D. Ward, Norms of inverses for matrices associated with scattered data, in:Curves and Surfaces, eds. P.J. Laurent, A. Le Méhauté and L.L. Schumaker (Academic Press, Boston, 1991) pp. 341–348.
F.J. Narcowich and J.D. Ward, Norm estimates for the inverses of a general class of scattered-data radial-function interpolation matrices, J. Approx. Theory 69 (1992) 84–109.
M.J.D. Powell, Univariate multiquadric interpolation: Some recent results, in:Curves and Surfaces, eds. P.J. Laurent, A. Le Méhauté and L.L. Schumaker (Academic Press, 1991) pp. 371–382.
R. Schaback, Comparison of radial basis function interpolants, in:Multivariate Approximation: From CAGD to Wavelets, eds. K. Jetter and F. Utreras, (World Scientific, London, 1993) pp. 293–305.
R. Schaback, Lower bounds for norms of inverses of interpolation matrices for radial basis functions, J. Approx. Theory 79 (1994) 287–306.
X. Sun, Norm estimates for inverses of Euclidean distance matrices, J. Approx. Theory 70 (1992) 339–347.
Z. Wu and R. Schaback, Local error estimtes for radial basis function interpolation of scattered data, IMA J. Numer. Anal. 13 (1993) 13–27.
H.P. Seidel, Symmetric recursive algorthms for curves, Comp. Aided Geom. Design 7 (1990) 57–67.
H.P. Seidel, Polar forms for geometrically continuous spline curves of arbitrary degree, ACM Trans. Graphics 12 (1993) 1–34.
K. Strøm, Splines, polynomials and polar forms. Ph.D. dissertation, University of Oslo, Norway (1992).
K. Strøm, Products of B-patches, Numer. Algor. 4 (1993) 323–337.
References
A.S. Cavaretta, W. Dahmen and C.A. Micchelli,Stationary Subdivision, Memoirs of Amer. Math. Soc., Vol. 93 (1991).
D. Colella and C. Heil, Characterizations of scaling functions: continuous solutions, SIAM J. Matrix Anal. Appl. 15 (1994) 496–518.
W. Dahmen and C.A. Micchelli, Translates of multivariate splines, Lin. Alg. Appl. 52 (1983) 217–234.
G. Deslauriers and S. Dubuc, Symmetric iterative interpolation process, Constr. Approx. 5 (1989) 49–68.
I. Daubechies and J.C. Lagarias, Two-scale difference equations: I. Existence and global regularity of solutions, SIAM J. Math. Anal. 22 (1991) 1388–1410.
I. Daubechies and J.C. Lagarias, Two-scale difference equations: II. Local regularity, infinite products of matrices and fractals, SIAM J. Math. Anal. 23 (1992) 1031–1079.
R.A. DeVore and G.G. Lorentz,Constructive Approximation (Springer, Berlin, 1993).
S. Dubuc, Interpolation through an iterative scheme, J. Math. Anal. Appl. 114 (1986) 185–205.
N. Dyn, Subdivision schemes in computer aided geometric design, in:Advances in Numerical Analysis II — Wavelets, Subdivision Algorithms and Radius Functions, ed. W.A. Light (Clarendon Press, Oxford, 1991) pp. 36–104.
N. Dyn, J.A. Gregory and D. Levin, Analysis of uniform binary subdivision schemes for curve design. Constr. Approx. 7 (1991) 127–147.
T. Eirola, Sobolev characterization of solutions of dilation equations, SIAM J. Math. Anal. 23 (1992) 1015–1030.
References
J.R. Dormand and P.J. Prince, A family of embedded Runge-Kutta formulae, J. Comput. Appl. Math. 6 (1980) 19–26.
K. Gustafsson, Control theoretic techniques for stepsize selection in explicit Runge-Kutta methods, ACM Trans. Math. Software 17 (1991) 533–544.
K. Gustafsson, M. Lundh and G. Söderlind, A PI stepsize control for the numerical solution of ordinary differential equations, BIT 28 (1988) 270–287.
E. Hairer and G. Wanner,Solving Ordinary Differential Equations II (Springer, Berlin, 1991).
G. Hall, Equilibrium states of Runge-Kutta formulae, ACM Trans. Math. Software 11 (1985) 289–301.
G. Hall and D.J. Higham, Analysis of stepsize selection schemes for Runge-Kutta codes, IMA J. Numer. Anal. 8 (1988) 305–310.
D.J. Higham and G. Hall, Embedded Runge-Kutta formulae with stable equilibrium states, J. Comput. Appl. Math. 29 (1990) 25–33.
F.T. Krogh, On testing a subroutine for the numerical integration of ordinary differential equations, J. ACM 4 (1973) 545–562.
P.J. Prince and J.R. Dormand, High order embedded Runge-Kutta formulae, J. Comput. Appl. Math. 7 (1981) 67–75.
B.C. Robertson, Detecting stiffness with explicit runge-Kutta formulas, Report 193/87, Dept. Comp. Sci., University of Toronto (1987).
L.F. Shampine, Lipschitz constants and robust ODE codes, Technical Report SAND79-0458, Sandia National Laboratories, Albuquerque, New Mexico (March 1979).
References
M. Abramowitz and I.A. Stegun,Pocketbook of Mathematical Functions (Harri Deutsch, Thun, 1984).
K. Ball, N. Sivakumar and J.D. Ward, On the sensitivity of radial basis interpolation to minimal data separation distance, Constr. Approx. 8 (1992) 401–426.
C. de Boor, The quasi-interpolant as a tool in elementary polynomial spline theory in:Approximation Theory, ed. G.G. Lorentz (Academic Press, New York, 1973) pp. 269–276.
C. de Boor,A Practical Guide to Splines (Springer, New York, 1978).
C. de Boor and G.J. Fix, Spline approximation by quasiinterpolants, J. Approx. Theory 8 (1973) 19–45.
M.D. Buhmann, Discrete least squares approximation and prewavelets from radial function spaces, Math. Proc. Cambridge Phil. Soc. 114 (1993) 533–558.
M.D. Buhmann and C.A. Micchelli, Spline prewavelets for non-uniform knots, Numer. Math. 61 (1992) 455–474.
C.K. Chui, K. Jetter, J. Stöckler and J.D. Ward, Wavelets for analyzing scattered data: An unbounded operator approach, ms. (November 1994).
C.K. Chui, K. Jetter and J.D. Ward, Cardinal interpolation with differences of tempered functions, Comp. Math. Appl. 24 (1992) 35–48.
I. Daubechies,Ten Lectures on Wavelets, CBMS-NSF Reg. Conf. Series in Appl. Math., vol. 61 (SIAM, Philadelphia, 1992).
R.A. DeVore and G.G. Lorentz,Constructive Approximation (Springer, New York, 1994).
I.M. Gel’fand and G.E. Shilov,Generalized Functions, vol. 1 (Academic Press, New York, 1964).
I.M. Gelfand and N.Ya. Vilenkin,Generalized Functions, vol. 4 (Academic Press, New York, 1964).
M.J.D. Powell, Univariate multiquadric approximation: Reproduction of linear polynomials, in:Multivariate Approximation and Interpolation, eds. W. Hau\mann and K. Jetter, ISNM 94 (Birkhäuser, Basel, 1990) pp. 227–240.
Author information
Authors and Affiliations
Additional information
Communicated by L.L. Schumaker
Rights and permissions
About this article
Cite this article
Schaback, R. Error estimates and condition numbers for radial basis function interpolation. Adv Comput Math 3, 251–264 (1995). https://doi.org/10.1007/BF02432002
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/BF02432002