Convergence order estimates of meshless collocation methods using radial basis functions

We study meshless collocation methods using radial basis functions to approximate regular solutions of systems of equations with linear differential or integral operators. Our method can be interpreted as one of the emerging meshless methods, cf. T. Belytschko et al. (1996). Its range of application is not confined to elliptic problems. However, the application to the boundary value problem for an elliptic operator, connected with an integral equation, is given as an example. Although the method has been used for special cases for about ten years, cf. E.J. Kansa (1990), there are no error bounds known. We put the main emphasis on detailed proofs of such error bounds, following the general outline described in C. Franke and R. Schaback (preprint). This revised version was published online in June 2006 with corrections to the Cover Date.     

Unsymmetric meshless methods for operator equations

A general framework for proving error bounds and convergence of a large class of unsymmetric meshless numerical methods for solving well-posed linear operator equations is presented. The results provide optimal convergence rates, if the test and trial spaces satisfy a stability condition. Operators need not be elliptic, and the problems can be posed in weak or strong form without changing the theory. Non-stationary kernel-based trial and test spaces are shown to fit into the framework, disregarding the operator equation. As a special case, unsymmetric meshless kernel-based methods solving weakly posed problems with distributional data are treated in some detail. This provides a foundation of certain variations of the “Meshless Local Petrov-Galerkin” technique of S.N. Atluri and collaborators.     

A Newton basis for Kernel spaces

It is well known that representations of kernel-based approximants in terms of the standard basis of translated kernels are notoriously unstable. To come up with a more useful basis, we adopt the strategy known from Newton’s interpolation formula, using generalized divided differences and a recursively computable set of basis functions vanishing at increasingly many data points. The resulting basis turns out to be orthogonal in the Hilbert space in which the kernel is reproducing, and under certain assumptions it is complete and allows convergent expansions of functions into series of interpolants. Some numerical examples show that the Newton basis is much more stable than the standard basis of kernel translates.     

Multivariate Interpolation by Polynomials and Radial Basis Functions

In many cases, multivariate interpolation by smooth radial basis functions converges toward polynomial interpolants, when the basis functions are scaled to become flat. In particular, examples show and this paper proves that interpolation by scaled Gaussians converges toward the de Boor/Ron least polynomial interpolant. To arrive at this result, a few new tools are necessary. The link between radial basis functions and multivariate polynomials is provided by radial polynomials ||x-y||₂^2l\|x-y\|_2^{2\ell} that already occur in the seminal paper by C.A. Micchelli of 1986. We study the polynomial spaces spanned by linear combinations of shifts of radial polynomials and introduce the notion of a discrete moment basis to define a new well-posed multivariate polynomial interpolation process which is of minimal degree and also least and degree-reducing in the sense of de Boor and Ron. With these tools at hand, we generalize the de Boor/Ron interpolation process and show that it occurs as the limit of interpolation by Gaussian radial basis functions. As a byproduct, we get a stable method for preconditioning the matrices arising with interpolation by smooth radial basis functions.     

Multilevel Interpolation and Approximation

Interpolation by translates of a given radial basis function (RBF) has become a well-recognized means of fitting functions sampled at scattered sites in ^d. A major drawback of these methods is their inability to interpolate very large data sets in a numerically stable way while maintaining a good fit. To circumvent this problem, a multilevel interpolation (ML) method for scattered data was presented by Floater and Iske. Their approach involves m levels of interpolation where at the jth level, the residual of the previous level is interpolated. On each level, the RBF is scaled to match the data density. In this paper, we provide some theoretical underpinnings to the ML method by establishing rates of approximation for a technique that deviates somewhat from the Floater–Iske setting. The final goal of the ML method will be to provide a numerically stable method for interpolating several thousand points rapidly.     

Approximation by radial basis functions with finitely many centers

Interpolation by translates of “radial” basis functions Φ is optimal in the sense that it minimizes the pointwise error functional among all comparable quasiinterpolants on a certain “native” space of functions $\mathcal{F}_\Phi $ . Since these spaces are rather small for cases where Φ is smooth, we study the behavior of interpolants on larger spaces of the form $\mathcal{F}_{\Phi _0 } $ for less smooth functions Φ₀. It turns out that interpolation by translates of Φ to mollifications of functionsf from $\mathcal{F}_{\Phi _0 } $ yields approximations tof that attain the same asymptotic error bounds as (optimal) interpolation off by translates of Φ₀ on $\mathcal{F}_{\Phi _0 } $ .     

Inverse and saturation theorems for radial basis function interpolation

While direct theorems for interpolation with radial basis functions are intensively investigated, little is known about inverse theorems so far. This paper deals with both inverse and saturation theorems. For an inverse theorem we especially show that a function that can be approximated sufficiently fast must belong to the native space of the basis function in use. In case of thin plate spline interpolation we also give certain saturation theorems.