This monograph is designed as a comprehensive and self-contained introduction to the field of multivariate scattered data approximation. The problem of function reconstruction from unstructured scattered data occurs with increasing frequency in contemporary applications. Unlike other treatments of this problem based on methods that require a mesh (e.g.multivariate polynomial splines), the original approach of this book concentrates on genuinely meshless methods: radial basis functions, moving least squares, and partition of unity. The author captures the flavour of the subject by emphasizing throughout the book the interactions of the approximation methods with topics from pure and applied mathematics, numerical analysis and computer science.
The book offers an interesting reading for both the beginner and the specialist. An inspired selection of topics is organized into seventeen chapters which can easily be converted into either a one-semester or a two-semester graduate course. The material draws in good measure on the well-known research contributions of the author, who has also endeavoured to present the best available proofs, many of which are new or simplified. The ‘Notes and comments’ section at the end of each chapter provides informative and useful details on the relevant literature.
In the first chapter, the importance of the subject is shown via three types of multivariate applications: the reconstruction of explicit and implicit surfaces, fluid-structure interaction in aeroelasticity, and grid-free semi-Lagrangian advection. The classical properties of univariate cubic splines are then analysed in view of their generalization to the multivariate case. Chapters 2 and 3 introduce the basic tools of multivariate polynomials and local polynomial reproduction, respectively.
Approximation by the moving least squares method is studied in Chapter 4. It is demonstrated that this method provides local polynomial reproduction, from which error estimates are deduced. The computational complexity and generalizations of the moving least squares method are also investigated.
Chapter 5 reviews Bessel functions, Fourier transforms, approximation by convolution, and Borel measures, as required in the subsequent investigation of radial basis functions (RBF). This forms the core of the book and begins with the discussion of positive definite functions in Chapter 6. Such functions lead to an elegant multivariate interpolation method using only linear combinations of their translates. After presenting Bochner’s characterization of positive semi-definite functions, the author analyses examples and properties of radial positive definite functions. Chapter 7 studies completely monotone functions and their use in Schoenberg’s characterization of positive definiteness. The more general concept of a conditionally positive definite function is taken up in Chapter 8. The author provides characterizations, examples, as well as the construction of the standard multivariate interpolation scheme using conditionally positive definite functions. Chapter 9 is based on the author’s results regarding positive definite radial functions with compact support, which are obtained as integral transforms of truncated power functions.
Having described all the main classes of radial basis functions, in Chapter 10 the author turns to the theory of native spaces as the natural framework for the analysis of RBF interpolation methods. Thus native spaces associated with (conditionally) positive definite kernels are constructed, along with a thorough investigation of examples, characterizations, and important properties of native spaces (embeddings, restrictions and extensions). Chapter 11 presents a variety of error estimates for RBF interpolation to data functions from native spaces. The main techniques use the so-called power function approach and Sobolev bounds for functions with scattered zeros.
Chapter 12 concerns the numerical stability of the radial basis function interpolation process. Estimates on the condition number of the interpolation matrix are obtained via suitable bounds on the minimum and maximum eigenvalues of the matrix. It is also studied how the condition number depends on the basis in which the interpolant is represented. Using the properties of native spaces, in Chapter 13 it is shown that RBF interpolants satisfy variational principles that are analogous to the classical minimization properties of univariate splines.
Chapter 14 analyses several computational geometry methods for the storage of scattered data sets in order that the underlying data structure can efficiently answer basic queries, such as nearest neighbor or range searches. This analysis is a prerequisite for the discussion of numerical implementations of RBFmethods. Thus Chapter 15 provides a state-of-the-art collection of RBF numerical recipes, including fast multipole methods, approximate Lagrange functions, alternating projections, partitions of unity, multilevel and greedy algorithms.
Chapter 16 demonstrates the capabilities of more general recovery problems by applying Hermite-Birkhoff interpolation to the solution of partial differential equations through symmetric collocation. A different extension of the theoretical setup, namely to scattered data interpolation on spheres and compact manifolds, is contained in the last chapter. Using the specific machinery of spherical harmonics and differentiable manifolds, error estimates are obtained for interpolation by positive definite functions on spheres and on manifolds.
Through its variety of topics and its careful exposition, this book will appeal to everyone interested in the theory and numerical applications of meshless methods for scattered data approximation.