Abstract :
Radial basis function (RBF) interpolation is a ‘‘meshless’’ strategy with great promise for
adaptive approximation. Because it is meshless, there is no canonical grid to act as a starting
point for function-adaptive grid modification. Uniform grids are therefore common with
RBFs. Like polynomial interpolation, which is the limit of RBF interpolation when the RBF
functions are very wide (the ‘‘flat limit’’), RBF interpolants are vulnerable to the Runge
Phenomenon, whether the grid is uniform or irregular: the N-point interpolant may diverge
as N → ∞on the interval spanned by the interpolation points even for a function f (x) that
is analytic everywhere on and near this interval.
In this work, we discuss six strategies for defeating the Runge Phenomenon, specializing
to a uniform grid on a finite interval and one particular species of RBFs in one space
dimension: φ(x) = exp(−[α2/h2]x2) where h is the grid spacing. Three strategies fail,
but three are successful. One good strategy is to vary α with the number of interpolation
points N as N−1/4. Unfortunately this gives both a subgeometric rate of convergence
for the approximation (error falling as exp(−q
√
N) for some constant q) and a matrix
condition number that grows as exp(p
√
N) for some p > 0. (In order to explain why
fixed α, independent of N, is not a convergent strategy, we digress to discuss error
saturation, and show experimentally that the saturation error on the finite interval is
about 0.6 exp(−0.47/α2)‖f ‖∞; if a user-chosen error tolerance δ is acceptable, then
the optimum choice is αoptimum(δ) = 1/
√
−2 log(δ/0.06).) The second good strategy is
RBF Extension, which uses RBF functions with centers on a interval slightly larger than
the target interval to approximate f (x). A third strategy is to split the interval into two
‘‘boundary layers’’ and a large middle interval and apply separate RBF approximations
on each. The slow-decrease-of-α strategy is much cheaper, but RBF Extension is much
more resistant to ill-conditioning and therefore can achieve much lower errors. The threeinterval
method is the least accurate, but is robust and inexpensive.
