Radial basis functions for simulating PDEs
Overview
Finite differences remain useful because they are simple, direct,
flexible, easy done at high order, and effective.
Main limitation is restriction to (logically) rectangular grids.
Radial basis functions offer the possibility of a difference-based
method with no need for grids or meshes.
1. Background
2. 1-D analysis
3. Practical considerations for PDEs
Interpolation (1D)
In one dimension, data can be interpolated smoothly using splines.
Doesn't matter if nodes are scattered rather than equispaced.
Interpolation (2D)
On a regular 2-D grid, data can be interpolated smoothly by splines.
On scattered nodes, smooth splines are diffcult.
Radial basis functions
A radial basis function interpolant can be smooth and accurate on
any set of nodes in any dimension.
Definition
Given nodes xi and data fi, i = 1, . . . ,N, define
Use 2-norm for
The
are chosen for interpolation.
In matrix terms,
Basis functions
Piecewise smooth
Infinitely smooth
Basic properties
•For many smooth choices of
,
the RBF matrix A is guaranteed
to be invertible (Micchelli, 1986). Other cases are easily fixed.
•No grid required, only nodes.
•Effort is independent of spatial dimension.
•ore smoothness = higher accuracy = poorer conditioning of A.
Cubic splines
Consider 1-D,
.
Since
and piecewise cubic,
RBF interpolant is a spline. The B-spline
can be used for analysis. For instance, Gibbs' phenomenon.
Overshoot is 10.78% (compared to 14.11% in trig interpolation).
Cubic RBFs from cubic splines
A cubic spline is determined by interpolation plus two boundary
conditions.
Suppose x ∈[−1, 1]. To recreate a cubic RBF interpolant, use
Conclude. Boundaries are coupled together in RBF interpolation.
Cubic splines from cubic RBFs
Natural spline. s''(−1) = s''(1) = 0.
RBF interpolant with linear asymptotic growth.
Not-a-knot spline. s''' continuous at x^2 and xN−1.
Divorce nodes and RBF centers (knots).
Improves convergence at ends.
In nitely smooth RBFs
Most important in practice is
.
(MQ).
Use
for analysis (IQ). Similar to MQ in practice.
Introduce scaling parameter
as in
Decreasing tends to flatten the basis functions.
Fourier analysis
Discretize
on in nite grid xn = nh.
Interpolate, differentiate, and evaluate on grid.
Spectral di erentiation is
FD2 gives
RBFs using IQ with scaling parameter
gives
Comparison on Fourier data
The flat-RBF society
As
, two things seem to happen.
Better accuracy for interpolant
Worse (unbounded) conditioning for matrix A in
Practical computations strike a balance|often through brute force.
But even though the
diverge, might
have a limit?
Limit result
Theorem (Driscoll and Fornberg). Expand a smooth
as
Define symmetric matrices by
If
and
are nonsingular, then on any set of N 1-D nodes,
converges to the Lagrange interpolating polynomial as
Spin
In the flat limit, RBFs give something familiar and useful.
Computing the RBF coefficients
is an unstable step in a
well-conditioned process (polynomial interpolation).
In 2-D,
still (usually) converges to an interpolating
polynomial. However, limit depends on
Work is underway on stable means of computing in the limit,
preferably by bypassing the coefficient computation.
RBF difference methods
Use RBF interpolant to compute spatial derivatives for a PDE at
grid points.
Already successful for elliptic and diffusive evolution equations.
Issues
condition of RBF matrix
size of RBF matrix
choice of
boundary conditions
variable resolution
grid generation
Strategies
preconditioners, multigrid
domain decomposition
many good options|still heuristic
symmetric Hermite method
adaptive, time-varying grids
NOT!
Nondissipative propagation
For example, Maxwell's equations with interfaces.
New challenge. Time stability at boundaries
Boundaries
From 1-D theory.
•coupling of boundaries (spline BC)
•loss of accuracy near boundaries (natural spline)
•convergence to polynomial (Runge phenomenon)
All suggest trouble at boundaries.
Suggestions
Without dissipation, instability is deadly.
Some options.
1. Change the basis, as in natural splines.
2. Change the implementation, as in not-a-knot.
3. Change the nodes, as in pseudospectral methods.
1. Change the basis
Reproduce polynomials exactly, or limit asymptotic growth.
V is Vandermonde
m = −1 gives standard RBF.
m = N − 1 gives polynomial interpolation.
Actually an old RBF idea. Easily generalizes to higher dimensions.
Effect of polynomial terms
Benefits for small m, but diminishing returns as degree increases.
2. Change the method
Not-a-knot. Separate two RBF centers from interpolation nodes.
Independent of the changed center locations. Improves cubic
spline accuracy from h2 to h3.
"Super" not-a-knot. Do it again.
Independent of altered locations. Improves accuracy to h4 even
just outside the interval.
Not-a-knot example
May be special only for 1-D cubics.
3. Change the nodes
For 1-D polynomials, Chebyshev density
is optimal for stability.
Try distributing nodes according to
for
(equispaced to Chebyshev).
Effects of node density
Most improvement for intermediate
Comparison in 2-D
Node/center distributions on the unit disk.
Observations
1. Adding polynomials to the basis
•Some improvement throughout.
•Little benefit in going past linear.
•Some theoretical justification.
2. Not-a-Knot/SNaK
•Dramatic improvement with SNaK.
•Locating centers to move may be tricky.
•Effects on RBF matrix not well known.
3. Boundary clustering
•Good improvement at boundary.
•May cause interior degradation.
•Distribution of nodes may be difficult in general.
These approaches may be combined freely.
Promise and problems
Radial basis functions offer the promise of difference
methods that
are simple, user-friendly, easy at high order, and free of grids and
meshes.
Significant problems remain to be fully resolved.
•stable boundary strategies
•choice of scaling parameter/computing in the flat limit
•conditioning/size of RBF matrix
•theoretical underpinnings in realistic situations