Runge's phenomenon

The red curve is the Runge function.
The blue curve is a 5th-order interpolating polynomial (using six equally spaced interpolating points).
The green curve is a 9th-order interpolating polynomial (using ten equally spaced interpolating points).
At the interpolating points, the error between the function and the interpolating polynomial is (by definition) zero. Between the interpolating points (especially in the region close to the endpoints 1 and −1), the error between the function and the interpolating polynomial gets worse for higher-order polynomials.

In the mathematical field of numerical analysis, Runge's phenomenon is a problem of oscillation at the edges of an interval that occurs when using polynomial interpolation with polynomials of high degree over a set of equispaced interpolation points. It was discovered by Carl David Tolmé Runge (1901) when exploring the behavior of errors when using polynomial interpolation to approximate certain functions.^[1] The discovery was important because it shows that going to higher degrees does not always improve accuracy. The phenomenon is similar to the Gibbs phenomenon in Fourier series approximations.

Introduction

The Weierstrass approximation theorem states that for every continuous function f(x) defined on an interval [a,b], there exists a set of polynomial functions P_n(x) for n=0, 1, 2, …, each of degree n, that approximates f(x) with uniform convergence over [a,b] as n tends to infinity, that is,

\lim _{{n\rightarrow \infty }}\left(\max _{{a\leq x\leq b}}\left|f(x)-P_{n}(x)\right|\right)=0.

Consider the case where one desires to interpolate through n+1 equispaced points of a function f(x) using the n-degree polynomial P_n(x) that passes through those points. Naturally, one might expect from Weierstrass' theorem that using more points would lead to a more accurate reconstruction of f(x). However, this particular set of polynomial functions P_n(x) is not guaranteed to have the property of uniform convergence; the theorem only states that a set of polynomial functions exists, without providing a general method of finding one.

The P_n(x) produced in this manner may in fact diverge away from f(x) as n increases; this typically occurs in an oscillating pattern that magnifies near the ends of the interpolation points. This phenomenon is attributed to Runge.^[2]

Problem

Consider the Runge function

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

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(\max _{{-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 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=1}}^{{n+1}}(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 $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 $w_{n}$ function :

W_{n}=\max _{{-1\leq x\leq 1}}w_{n}(x).

Then it can be proved that, if equidistant nodes are used,^[3] then :

W_{n}\leq h^{n}{\frac {(n-1)!}{4}}

where $h=2/(n-1)$ is the step size.

Moreover, assume that the n-th derivative of $f$ is bounded, i.e.

\max _{{-1\leq x\leq 1}}f^{{(n)}}(x)\leq M_{n}

Therefore,

\max _{{-1\leq x\leq 1}}|f(x)-P_{n}(x)|\leq M_{n}{\frac {h^{n}}{4n}}

But the magnitude of the n-th derivative of Runge's function increases when n increases, and very fast. The result is that the product in the previous equation 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 to the problem

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^[4] $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. The phenomenon demonstrates that high degree polynomials are generally unsuitable for interpolation with equidistant 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^{\mathrm {th} }$ derivative and the mean value of it's $m^{\mathrm {th} }$ derivative. Explicitly, to minimize

V_{p}=\int _{a}^{b}\left|{\frac {\operatorname {d} ^{m}P_{N}(x)}{\operatorname {d} x^{m}}}-{\frac {1}{b-a}}\int _{a}^{b}{\frac {\operatorname {d} ^{m}P_{N}(z)}{\operatorname {d} z^{m}}}\operatorname {d} z\right|^{p}\operatorname {d} x-\sum _{i=1}^{n}\lambda _{i}\,\left(P_{N}(x_{i})-f(x_{i})\right),

where $N\geq n-1$ and $m<N$ , 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\rightarrow \infty }P_{N}(x)$ will approach a form very similar to a piecewise polynomials approximation. When $m=1$ , in particular, $\lim _{N\rightarrow \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

Another method is fitting a polynomial of lower degree using the method of least squares. Generally, when using $m$ equidistant points, if $N<2{\sqrt {n}}$ then least squares approximation $P_{N}(x)$ is well-conditioned.^[5]

Bernstein polynomial

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

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.^[6] 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

↑ Runge, Carl (1901), "Über empirische Funktionen und die Interpolation zwischen äquidistanten Ordinaten", Zeitschrift für Mathematik und Physik, 46: 224–243. available at www.archive.org
↑ Epperson, James (1987). "On the Runge example". Amer. Math. Monthly. 94: 329–341. doi:10.2307/2323093.
↑ Heath, Michael (2000). Scientific Computing. McGraw-Hill. p. 324. ISBN 0072399104.
↑ Berrut, Jean-Paul; Trefethen, Lloyd N. (2004), "Barycentric Lagrange interpolation", SIAM Review, 46 (3): 501–517, doi:10.1137/S0036144502417715, ISSN 1095-7200
↑ Dahlquist, Germund; Björk, Åke (1974), "4.3.4. Equidistant Interpolation and the Runge Phenomenon", Numerical Methods, pp. 101–103, ISBN 0-13-627315-7
↑ Cheney, Ward; Light, Will (2000), A Course in Approximation Theory, Brooks/Cole, p. 19, ISBN 0-534-36224-9

This article is issued from Wikipedia - version of the 12/4/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.