An extended continuous Newton method

This paper describes a numerical realization of an extended continuous Newton method defined by Diener. It traces a connected set of locally one-dimensional trajectories which contains all critical points of a smooth functionf: ⁿ . The results show that the method is effectively applicable.The authors would like to thank L. C. W. Dixon for pointing out some errors in the original version of this paper and for several suggestions of improvements.     

Convergence analysis of the general Gauss-Newton algorithm

Summary The convergence of the Gauss-Newton algorithm for solving discrete nonlinear approximation problems is analyzed for general norms and families of functions. Aquantitative global convergence theorem and several theorems on the rate of local convergence are derived. A general stepsize control procedure and two regularization principles are incorporated. Examples indicate the limits of the convergence theorems.     

Error estimates and condition numbers for radial basis function interpolation

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.     

A meshfree method for solving the Monge–Ampère equation

Numerical Algorithms - This paper solves the two-dimensional Dirichlet problem for the Monge-Ampère equation by a strong meshless collocation technique that uses a polynomial trial space and...     

Adaptive greedy techniques for approximate solution of large RBF systems

For the solution of large sparse linear systems arising from interpolation problems using compactly supported radial basis functions, a class of efficient numerical algorithms is presented. They iteratively select small subsets of the interpolation points and refine the current approximative solution there. Convergence turns out to be linear, and the technique can be generalized to positive definite linear systems in general. A major feature is that the approximations tend to have only a small number of nonzero coefficients, and in this sense the technique is related to greedy algorithms and best n-term approximation. This revised version was published online in June 2006 with corrections to the Cover Date.     

Improved error bounds for scattered data interpolation by radial basis functions

If additional smoothness requirements and boundary conditions are met, the well-known approximation orders of scattered data interpolants by radial functions can roughly be doubled.

     

Greedy sparse linear approximations of functionals from nodal data

In many numerical algorithms, integrals or derivatives of functions have to be approximated by linear combinations of function values at nodes. This ranges from numerical integration to meshless methods for solving partial differential equations. The approximations should use as few nodal values as possible and at the same time have a smallest possible error. For each fixed set of nodes and each fixed Hilbert space of functions with continuous point evaluation, e.g. a fixed Sobolev space, there is an error–optimal method available using the reproducing kernel of the space. But the choice of the nodes is usually left open. This paper shows how to select good nodes adaptively by a computationally cheap greedy method, keeping the error optimal in the above sense for each incremental step of the node selection. This is applied to interpolation, numerical integration, and numerical differentiation. The latter case is particularly important for the design of meshless methods with sparse generalized stiffness matrices. The greedy algorithm is described in detail, and numerical examples are provided. In contrast to the usual practice, the greedy method does not always use nearest neighbors for local approximations of function values and derivatives. Furthermore, it avoids multiple points from clusters and it is better conditioned than choosing nearest neighbors.     

Generalized Whittle–Matérn and polyharmonic kernels

This paper simultaneously generalizes two standard classes of radial kernels, the polyharmonic kernels related to the differential operator (???Δ) ^m and the Whittle–Matérn kernels related to the differential operator (???Δ?+?I) ^m . This is done by allowing general differential operators of the form $\prod_{j=1}^m(-\Delta+\kappa_j^2I)$ with nonzero κ _j and calculating their associated kernels. It turns out that they can be explicity given by starting from scaled Whittle–Matérn kernels and taking divided differences with respect to their scale. They are positive definite radial kernels which are reproducing kernels in Hilbert spaces norm-equivalent to $W_2^m(\ensuremath{\mathbb{R}}^d)$ . On the side, we prove that generalized inverse multiquadric kernels of the form $\prod_{j=1}^m(r^2+\kappa_j^2)^{-1}$ are positive definite, and we provide their Fourier transforms. Surprisingly, these Fourier transforms lead to kernels of Whittle–Matérn form with a variable scale κ(r) between κ ₁,...,κ _m . We also consider the case where some of the κ _j vanish. This leads to conditionally positive definite kernels that are linear combinations of the above variable-scale Whittle–Matérn kernels and polyharmonic kernels. Some numerical examples are added for illustration.