Runge's phenomenon

Problem

Consider the Runge function

f(x) = \frac{1}{1+25x^2},

(a scaled version of the Witch of Agnesi). Runge found that if this function is interpolated at equidistant points x**i between −1 and 1 such that:

x_i = \frac{2i}{n} - 1,\quad i \in \left{ 0, 1, \dots, n \right}

with a polynomial P_n(x) of degree ≤ n, the resulting interpolation oscillates toward the end of the interval, i.e. close to −1 and 1. It can even be proven that the interpolation error increases (without bound) when the degree of the polynomial is increased:

\lim_{n \rightarrow \infty} \left( \sup_{-1 \leq x \leq 1} | f(x) -P_n(x)| \right) = \infty.

This shows that high-degree polynomial interpolation at equidistant points can be troublesome.

Reason

Runge's phenomenon is the consequence of two properties of this problem.

• The magnitude of the n-th order derivatives of this particular function grows quickly when n increases.
• The equidistance between points leads to a Lebesgue constant that increases quickly when n increases.

The phenomenon is graphically obvious because both properties combine to increase the magnitude of the oscillations.

The error between the generating function and the interpolating polynomial of order n is given by

f(x) - P_n(x) = \frac{f^{(n + 1)}(\xi)}{(n + 1)!} \prod_{i=0}^{n} (x - x_i) .

for some \xi in (−1, 1). Thus,

\max_{-1 \leq x \leq 1} |f(x) - P_n(x)| \leq \max_{-1 \leq x \leq 1} \frac{\left|f^{(n + 1)}(x)\right|}{(n + 1)!} \max_{-1 \leq x \leq 1} \prod_{i=0}^n |x - x_i|.

Denote by w_n(x) the nodal function

w_n(x) = (x - x_0)(x - x_1)\cdots(x - x_n)

and let W_n be the maximum of the magnitude of the w_n function:

W_n=\max_{-1 \leq x \leq 1} |w_n(x)|.

It is elementary to prove that with equidistant nodes

W_n \leq n!h^{n+1}

where h=2/n is the step size.

Moreover, assume that the (n+1)-th derivative of f is bounded, i.e.

\max_{-1 \leq x \leq 1} |f^{(n+1)}(x)| \leq M_{n+1}.

Therefore,

\max_{-1 \leq x \leq 1} |f(x) - P_{n}(x)| \leq M_{n+1} \frac{h^{n+1}}{(n+1)}.

But the magnitude of the (n+1)-th derivative of Runge's function increases when n increases. The consequence is that the resulting upper bound tends to infinity when n tends to infinity.

Although often used to explain the Runge phenomenon, the fact that the upper bound of the error goes to infinity does not necessarily imply, of course, that the error itself also diverges with n.

Mitigations

Change of interpolation points

The oscillation can be minimized by using nodes that are distributed more densely towards the edges of the interval, specifically, with asymptotic density (on the interval [-1,1]) given by the formula

\frac{1}{\sqrt{1-x^2}}.

A standard example of such a set of nodes is Chebyshev nodes, for which the maximum error in approximating the Runge function is guaranteed to diminish with increasing polynomial order.

S-Runge algorithm without resampling

When equidistant samples must be used because resampling on well-behaved sets of nodes is not feasible, the S-Runge algorithm can be considered. |doi-access = free In this approach, the original set of nodes is mapped on the set of Chebyshev nodes, providing a stable polynomial reconstruction. The peculiarity of this method is that there is no need of resampling at the mapped nodes, which are also called fake nodes.

Use of piecewise polynomials

The problem can be avoided by using spline curves which are piecewise polynomials. When trying to decrease the interpolation error one can increase the number of polynomial pieces which are used to construct the spline instead of increasing the degree of the polynomials used.

Constrained minimization

One can also fit a polynomial of higher degree (for instance, with n points use a polynomial of order N = n^2 instead of n + 1), and fit an interpolating polynomial whose first (or second) derivative has minimal L^2 norm.

A similar approach is to minimize a constrained version of the L^p distance between the polynomial's m-th derivative and the mean value of its m-th derivative. Explicitly, to minimize

V_p = \int_a^b \left|\frac{\mathrm{d}^m P_N(x)}{\mathrm{d} x^m} - \frac{1}{b-a} \int_a^b \frac{\mathrm{d}^m P_N(z)}{\mathrm{d} z^m} \mathrm{d}z\right|^p \mathrm{d} x - \sum_{i=1}^n \lambda_i , \left(P_N(x_i) - f(x_i)\right),

where N \ge n - 1 and m , with respect to the polynomial coefficients and the Lagrange multipliers, \lambda_i. When N = n - 1, the constraint equations generated by the Lagrange multipliers reduce P_N(x) to the minimum polynomial that passes through all n points. At the opposite end, \lim_{N \to \infty} P_N(x) will approach a form very similar to a piecewise polynomials approximation. When m=1, in particular, \lim_{N \to \infty} P_N(x) approaches the linear piecewise polynomials, i.e. connecting the interpolation points with straight lines.

The role played by p in the process of minimizing V_p is to control the importance of the size of the fluctuations away from the mean value. The larger p is, the more large fluctuations are penalized compared to small ones. The greatest advantage of the Euclidean norm, p=2, is that it allows for analytic solutions and it guarantees that V_p will only have a single minimum. When p\neq 2 there can be multiple minima in V_p, making it difficult to ensure that a particular minimum found will be the global minimum instead of a local one.

Least squares fitting

Main article: Polynomial fit

Another method is fitting a polynomial of lower degree using the method of least squares. Generally, when using m equidistant points, if N then least squares approximation P_N(x) is well-conditioned.

Bernstein polynomial

Using Bernstein polynomials, one can uniformly approximate every continuous function in a closed interval, although this method is rather computationally expensive.

External fake constraints interpolation

This method proposes to optimally stack a dense distribution of constraints of the type on nodes positioned externally near the endpoints of each side of the interpolation interval, where P"(x) is the second derivative of the interpolation polynomial. Those constraints are called External Fake Constraints as they do not belong to the interpolation interval and they do not match the behaviour of the Runge function. The method has demonstrated that it has a better interpolation performance than Piecewise polynomials (splines) to mitigate the Runge phenomenon.

Related statements from the approximation theory

For every predefined table of interpolation nodes there is a continuous function for which the sequence of interpolation polynomials on those nodes diverges. For every continuous function there is a table of nodes on which the interpolation process converges. Chebyshev interpolation (i.e., on Chebyshev nodes) converges uniformly for every absolutely continuous function.

References

de:Polynominterpolation#Runges Phänomen

References

1. Epperson, James. (1987). "On the Runge example". The American Mathematical Monthly.
2. (2004). "Barycentric Lagrange interpolation". SIAM Review.
3. (1974). "Numerical Methods".
4. (2017). "External Fake Constraints Interpolation: the end of Runge phenomenon with high degree polynomials relying on equispaced nodes – Application to aerial robotics motion planning".
5. (2000). "A Course in Approximation Theory". Brooks/Cole.