Numerical experiments on optimal shape parameters for radial basis functions

A numerical investigation on a technique for choosing an optimal shape parameter is proposed. Radial basis functions (RBFs) and their derivatives are used as interpolants in the asymmetric collocation radial basis method, for solving systems of partial differential equations. The shape parameter c in RBFs plays a major role in obtaining high quality solutions for boundary value problems. As c is a user defined value, inexperienced users may compromise the quality of the solution, often a problem of this meshless method. Here we propose a statistical technique to choose the shape parameter in radial basis functions. We use a cross‐validation technique suggested by Rippa 6 for interpolation problems to find a cost function Cost(c) that ideally has the same behavior as an error function. If that is the case, the parameter c that minimizes the cost function will be an optimal shape parameter, in the sense that it minimizes the error function. The form of the cost and error functions are analized for several examples, and for most cases the two functions have a similar behavior. The technique produced very accurate results, even with a small number of points and irregular grids. © 2009 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2010     

Multivariate interpolation with increasingly flat radial basis functions of finite smoothness

In this paper, we consider multivariate interpolation with radial basis functions of finite smoothness. In particular, we show that interpolants by radial basis functions in ℝ ^d with finite smoothness of even order converge to a polyharmonic spline interpolant as the scale parameter of the radial basis functions goes to zero, i.e., the radial basis functions become increasingly flat.     

Admissible slopes for monotone and convex interpolation

Summary In many applications, interpolation of experimental data exhibiting some geometric property such as nonnegativity, monotonicity or convexity is unacceptable unless the interpolant reflects these characteristics. This paper identifies admissible slopes at data points of variousC ¹ interpolants which ensure a desirable shape. We discuss this question, in turn for the following function classes commonly used for shape preserving interpolations: monotone polynomials,C ¹ monotone piecewise polynomials, convex polynomials, parametric cubic curves and rational functions.     

Trigonometric variable shape parameter and exponent strategy for generalized multiquadric radial basis function approximation

The generalized multiquadric radial basis function (φ_j=[(x-x_j)²+c²]^β) has the exponent β and shape parameter c that play an important role in the accuracy of the approximation. In this study, we present a trigonometric variable shape parameter and exponent strategy and apply it to function interpolations and linear boundary value problems. Several numerical experiments with the uniformly spaced nodes show that the inverse multiquadric radial basis function (β = −0.5) with the trigonometric variable shape parameter c strategy results in the best accuracy for the one-dimensional interpolations; the trigonometric variable shape parameters and exponent strategy produces the best accuracy for the two-dimensional interpolations and linear boundary value problems. For the non-uniformly spaced nodes, the random variable shape parameter c and exponent β strategy produces the best accuracy for the two-dimensional boundary value problem.     

On estimates for the uniform norm of the Laplace operator of the best interpolants on a class of bounded interpolation data

We consider an interpolation problem with minimum value of the uniform norm of the Laplace operator of interpolants for a class of bounded interpolated sequences. The data are interpolated at nodes of the grid formed by points from ?² with integer coordinates. Two-sided estimates for the uniform norm of the best interpolant are found, which improve known estimates.     

Exponential convergence and H‐c multiquadric collocation method for partial differential equations

The radial basis function (RBF) collocation method uses global shape functions to interpolate and collocate the approximate solution of PDEs. It is a truly meshless method as compared to some of the so‐called meshless or element‐free finite element methods. For the multiquadric and Gaussian RBFs, there are two ways to make the solution converge—either by refining the mesh size h, or by increasing the shape parameter c. While the h‐scheme requires the increase of computational cost, the c‐scheme is performed without extra effort. In this paper we establish by numerical experiment the exponential error estimate ? ～ O(λ^√c?h) where 0 < λ < 1. We also propose the use of residual error as an error indicator to optimize the selection of c. © 2003 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 19: 571–594, 2003     

Monotone and Convex C 1 Hermite Interpolants Generated by a Subdivision Scheme

   Abstract. We propose C ¹ Hermite interpolants generated by the general subdivision scheme introduced by Merrien [17] and satisfying monotonicity or convexity constraints. For arbitrary values and slopes of a given function f at the end-points of a bounded interval, which are compatible with the contraints, the given algorithms construct shape-preserving interpolants. Moreover, these algorithms are quite simple and fast as well as adapted to CAGD. We also give error estimates in the case of interpolation of smooth functions.     

Convergence rates of derivatives of a family of barycentric rational interpolants

In polynomial and spline interpolation the k-th derivative of the interpolant, as a function of the mesh size h, typically converges at the rate of O(hd+1−k) as h→0, where d is the degree of the polynomial or spline. In this paper we establish, in the important cases k=1,2, the same convergence rate for a recently proposed family of barycentric rational interpolants based on blending polynomial interpolants of degree d.     

Where does smoothness count the most for Fredholm equations of the second kind with noisy information?

We study the complexity of Fredholm problems (I−T_k)u=f of the second kind on I^d=[0,1]^d, where T_k is an integral operator with kernel k. Previous work on the complexity of this problem has assumed either that we had complete information about k or that k and f had the same smoothness. In addition, most of this work has assumed that the information about k and f was exact. In this paper, we assume that k and f have different smoothness; more precisely, we assume that fW^r,p(I^d) with r>d/p and that kW^s,∞(I^2d) with s>0. In addition, we assume that our information about k and f is contaminated by noise. We find that the nth minimal error is Θ(n^−μ+δ), where μ=min{r/d,s/(2d)} and δ is a bound on the noise. We prove that a noisy modified finite element method has nearly minimal error. This algorithm can be efficiently implemented using multigrid techniques. We thus find tight bounds on the -complexity for this problem. These bounds depend on the cost c(δ) of calculating a δ-noisy information value. As an example, if the cost of a δ-noisy evaluation is proportional to δ^−t, then the -complexity is roughly (1/)^t+1/μ.     

Uniqueness of minimal coverings of maximal partial clones

A partial function f on a k-element set E _k is a partial Sheffer function if every partial function on E _k is definable in terms of f. Since this holds if and only if f belongs to no maximal partial clone on E _k , a characterization of partial Sheffer functions reduces to finding families of minimal coverings of maximal partial clones on E _k . We show that for each k ≥ 2, there exists a unique minimal covering.     

The barycentric weights of rational interpolation with prescribed poles

We introduce a method for calculating rational interpolants when some (but not necessarily all) of their poles are prescribed. The algorithm determines the weights in the barycentric representation of the rationals; it simply consists in multiplying each interpolated value by a certain number, computing the weights of a rational interpolant without poles, and finally multiplying the weights by those same numbers. The supplementary cost in comparison with interpolation without poles is about (v + 2)N, where v is the number of poles and N the number of interpolation points. We also give a condition under which the computed rational interpolation really shows the desired poles.     

Reliable determination of interpolating polynomials

This paper addresses a fundamental problem in mathematics and numerical analysis, that of determining a polynomial interpolant to specified data. The data is taken as consisting of a set of points (abscissae), at each of which is specified a function value. Additionally, at each point, any number of leading derivative values of the function may be given. Mathematically, this problem is solved. The classical Lagrangian interpolation formula applies in the derivative-free case, and the Newton form of the interpolating polynomial in general.Numerically, few reliable algorithms are available; most published algorithms concentrate on speed of computation. This paper describes an algorithm that delivers the required polynomial in Chebyshev form. It is based on the repeated use of the Newton representation, with a data ordering strategy and iterative refinement to improve accuracy, using a carefully devised merit function to measure success. The algorithm attempts to provide a polynomial that is stable in the sense of backward error analysis, i.e. that is exact for slightly perturbed data.Implementations of the algorithm have been in use since the early 1980s in the NAG Library and NPL's Data Approximation Subroutine Library (DASL). In addition to providing polynomial interpolants in their own right, these implementations are used as computational modules in the NAG and DASL routines for constrained least-squares polynomial data fitting.This paper constitutes the first detailed presentation of the algorithm.     

Cardinal interpolation with general multiquadrics: convergence rates

This article pertains to interpolation of Sobolev functions at shrinking lattices \(h\mathbb {Z}^{d}\) from L _p shift-invariant spaces associated with cardinal functions related to general multiquadrics, ? _{α, c} (x) := (|x|² + c ²) ^α . The relation between the shift-invariant spaces generated by the cardinal functions and those generated by the multiquadrics themselves is considered. Additionally, L _p error estimates in terms of the dilation h are considered for the associated cardinal interpolation scheme. This analysis expands the range of α values which were previously known to give such convergence rates (i.e. O(h ^k ) for functions with derivatives of order up to k in L _p , \(1<p<\infty \)). Additionally, the analysis here demonstrates that some known best approximation rates for multiquadric approximation are obtained by their cardinal interpolants.     

Algorithms for cardinal interpolation using box splines and radial basis functions

Summary We describe an algorithm for (bivariate) cardinal interpolation which can be applied to translates of basis functions which include box splines or radial basis functions. The algorithm is based on a representation of the Fourier transform of the fundamental interpolant, hence Fast Fourier Transform methods are available. In numerical tests the 4-directional box spline (transformed to the characteristical submodule of ²), the thin plate spline, and the multiquadric case give comparably equal and good results.     

The Neville-like form of the Fitzpatrick algorithm for rational interpolation

The Fitzpatrick algorithm, which seeks a Gr?bner basis for the solution of a system of polynomial congruences, can be applied to compute a rational interpolant. Based on the Fitzpatrick algorithm and the properties of an Hermite interpolation basis, we present a Neville-like algorithm for multivariate osculatory rational interpolation. It may be used to compute the values of osculatory rational interpolants at some points directly without computing the rational interpolation function explicitly.     

Fast fitting of radial basis functions: Methods based on preconditioned GMRES iteration

Solving large radial basis function (RBF) interpolation problems with non‐customised methods is computationally expensive and the matrices that occur are typically badly conditioned. For example, using the usual direct methods to fit an RBF with N centres requires O(N ²) storage and O(N ³) flops. Thus such an approach is not viable for large problems with N ≥10,000. In this paper we present preconditioning strategies which, in combination with fast matrix–vector multiplication and GMRES iteration, make the solution of large RBF interpolation problems orders of magnitude less expensive in storage and operations. In numerical experiments with thin‐plate spline and multiquadric RBFs the preconditioning typically results in dramatic clustering of eigenvalues and improves the condition numbers of the interpolation problem by several orders of magnitude. As a result of the eigenvalue clustering the number of GMRES iterations required to solve the preconditioned problem is of the order of 10-20. Taken together, the combination of a suitable approximate cardinal function preconditioner, the GMRES iterative method, and existing fast matrix–vector algorithms for RBFs [4,5] reduce the computational cost of solving an RBF interpolation problem to O(N) storage, and O(N \log N) operations. This revised version was published online in June 2006 with corrections to the Cover Date.     

Spherical Maximal Operators on Radial Functions

Let A_tf(x) denote the mean of f over a sphere of radius t and center x. We prove sharp estimates for the maximal function M_E f(X) = sup_t∈_E |Atf(x)| where E is a fixed set in IR⁺ and f is a radial function ∈ L^p(IR^d). Let P_d = d/(d?1) (the critical exponent for Stein's maximal function). For the cases (i) p < p_d, d ? 2, and (ii) p = p_d, d ? 3, and for p ? q ? ∞ we prove necessary and sufficient conditions on E for M_E to map radial functions in L^p to the Lorentz space L^P,q.     

Continued fractions associated with the Newton-Padé table

Summary We discuss first the block structure of the Newton-Padé table (or, rational interpolation table) corresponding to the double sequence of rational interpolants for the data{(z _k, h(z_k)} _k =0. (The (m, n)-entry of this table is the rational function of type (m,n) solving the linearized rational interpolation problem on the firstm+n+1 data.) We then construct continued fractions that are associated with either a diagonal or two adjacent diagonals of this Newton-Padé table in such a way that the convergents of the continued fractions are equal to the distinct entries on this diagonal or this pair of diagonals, respectively. The resulting continued fractions are generalizations of Thiele fractions and of Magnus'sP-fractions. A discussion of an some new results on related algorithms of Werner and Graves-Morris and Hopkins are also given.Dedicated to the memory of Helmut Werner (1931–1985)     

On an interpolatory product rule for evaluating Cauchy principal value integrals

Convergence results for interpolatory product rules for evaluating Cauchy principal value integrals of the form f _?1 ¹ v(x)f(x)/x ? λ dx wherev is an admissible weight function have been extended to integrals of the form f _?1 ¹ k(x)f(x)/x ? λ dx wherek is an arbitrary integrable function subject to certain conditions. Further, whereas the above convergence results were shown when the interpolation points were the Gauss points with respect to some admissible weight functionw, they are now shown to hold when the interpolation points are Radau or Lobatto points with respect tow.     

Some new perspectives in best approximation and interpolation of random data

A new notion of universally optimal experimental design is introduced, relevant from the perspective of adaptive nonparametric estimation. It is demonstrated that both discrete and continuous Chebyshev designs are universally optimal in the problem of fitting properly weighted algebraic polynomials to random data. The result is a direct consequence of the well-known relation between Chebyshev’s polynomials and the trigonometric functions. Optimal interpolating designs in rational regression proved particularly elusive in the past. The question can be effectively handled using its connection to elliptic interpolation, in which the ordinary circular sinus, appearing in the classical trigonometric interpolation, is replaced by the Abel-Jacobi elliptic sinus sn(x, k) of a modulus k. First, it is demonstrated that — in a natural setting of equidistant design — the elliptic interpolant is never optimal in the so-called normal case k ∈ (?1, 1), except for the trigonometric case k = 0. However, the equidistant elliptic interpolation is always optimal in the imaginary case k ∈ i?. Through a relation between elliptic and rational functions, the result leads to a long sought optimal design, for properly weighted rational interpolants. Both the poles and nodes of the interpolants can be conveniently expressed in terms of classical Jacobi’s theta functions.