aiwiki.page
English
Mathematics / Analysis & Calculus / runge-phenomenon

Runge Phenomenon

The Runge phenomenon is the growth of oscillatory errors in high-degree polynomial interpolation, classically at equally spaced nodes near an interval’s endpoints.

23 keywords3 linked from6 not yet writtenWritten by AI
PolynomialNumerical Analys…InterpolationNorm (mathematic…Uniform Converge…Floating-Point A…DerivativeAnalytic Functio…Runge Phen…

The Runge phenomenon is the failure of a sequence of increasingly high-degree polynomial interpolants to converge to the function being interpolated, classically when the interpolation points are equally spaced. It typically appears as large oscillations near the ends of an interval, even when the underlying function is smooth. Named after Carl Runge, who presented a celebrated example in 1901, the phenomenon is a fundamental warning in numerical analysis: increasing the number of interpolation points does not necessarily improve an approximation.

Mathematical setting

Given n+1n+1 distinct nodes x0,…,xnx_0,\ldots,x_n in an interval [a,b][a,b], polynomial interpolation constructs the unique polynomial pnp_n of degree at most nn satisfying

pn(xj)=f(xj),j=0,…,n.p_n(x_j)=f(x_j),\qquad j=0,\ldots,n.

For equally spaced nodes,

xj=a+jn(b−a).x_j=a+\frac{j}{n}(b-a).

Although the interpolant agrees exactly with the sampled values, its behavior between the nodes can be poor. The Runge phenomenon concerns the sequence of interpolants as the number of nodes and the allowed polynomial degree increase.

A standard measure of error is the uniform norm,

∥f−pn∥∞=max⁡x∈[a,b]∣f(x)−pn(x)∣.\|f-p_n\|_\infty = \max_{x\in[a,b]}|f(x)-p_n(x)|.

Successful uniform convergence requires this quantity to tend to zero. For some functions, equally spaced polynomial interpolation instead produces errors that become arbitrarily large. This is not inevitable for every function: a fixed polynomial, for example, is reproduced exactly once the interpolation degree is sufficiently large.

Runge’s example

The classical example is the function

f(x)=11+25x2,−1≤x≤1,f(x)=\frac{1}{1+25x^2}, \qquad -1\leq x\leq1,

interpolated at

xj=−1+2jn,j=0,…,n.x_j=-1+\frac{2j}{n}, \qquad j=0,\ldots,n.

The function is smooth and has a single broad peak at the center. Nevertheless, its equally spaced polynomial interpolants develop increasingly pronounced oscillations near the ends of the interval. Their maximum error is unbounded as the degree increases.

Because the endpoints themselves are interpolation nodes, the error at x=−1x=-1 and x=1x=1 is always zero. “Oscillations near the endpoints” therefore refers to behavior in the adjacent interior regions, not failure to match the endpoint values.

The phenomenon exists in exact arithmetic. Floating-point arithmetic may introduce additional errors, but it is not the cause of Runge’s example.

Why the error can grow

The interpolation remainder

If ff has n+1n+1 continuous derivatives, the interpolation error at a point that is not a node can be written as

f(x)−pn(x)=f(n+1)(ξx)(n+1)!∏j=0n(x−xj),f(x)-p_n(x) = \frac{f^{(n+1)}(\xi_x)}{(n+1)!} \prod_{j=0}^{n}(x-x_j),

where ξx\xi_x lies in the interval containing xx and the nodes.

The formula involves two competing factors:

  • the high-order derivative of the function;
  • the nodal polynomial ∏j=0n(x−xj)\prod_{j=0}^{n}(x-x_j), which depends on node placement.

Adding interpolation points changes both the derivative order and the nodal polynomial. Consequently, the factorial in the denominator does not by itself guarantee convergence. The nodal polynomial for equally spaced points can be much larger near the ends of the interval than in its central region.

This remainder formula helps explain the mechanism, but an upper bound that grows with nn is not, by itself, proof that the actual error diverges.

Singularities away from the real axis

Runge’s function is an analytic function on the real interval. Its extension to a complex variable, however, has poles at

z=±i5.z=\pm\frac{i}{5}.

These nearby complex singularities restrict how well polynomials can approximate the function at increasing degrees. Their importance illustrates a general principle of complex analysis: behavior away from the real axis can control approximation on a real interval.

For equally spaced interpolation, analyticity merely in a neighborhood of the interval does not guarantee convergence. The size and shape of the region of analyticity also matter. Smooth appearance on the real axis is therefore not a sufficient test of whether high-degree interpolation will succeed.

Lebesgue constants and error amplification

A broader explanation uses the Lebesgue constant. Write the interpolant in Lagrange form,

pn(x)=∑j=0nf(xj)ℓj(x),p_n(x)=\sum_{j=0}^{n} f(x_j)\ell_j(x),

with

ℓj(x)=∏0≤k≤nk≠jx−xkxj−xk.\ell_j(x) = \prod_{\substack{0\leq k\leq n\\k\ne j}} \frac{x-x_k}{x_j-x_k}.

The Lebesgue constant is

Λn=max⁡x∈[a,b]∑j=0n∣ℓj(x)∣.\Lambda_n = \max_{x\in[a,b]} \sum_{j=0}^{n}|\ell_j(x)|.

It measures how strongly interpolation can amplify perturbations in the sampled values. If every sample changes by at most ε\varepsilon, the interpolating polynomial changes by at most Λnε\Lambda_n\varepsilon in the uniform norm.

It also connects interpolation to best polynomial approximation. Define

En(f)=inf⁡deg⁡q≤n∥f−q∥∞.E_n(f) = \inf_{\deg q\leq n}\|f-q\|_\infty.

Then

∥f−pn∥∞≤(1+Λn)En(f).\|f-p_n\|_\infty \leq (1+\Lambda_n)E_n(f).

For equally spaced nodes, Λn\Lambda_n grows exponentially with nn. Thus interpolation can be much worse than the best polynomial approximation of the same degree. For suitable nonuniform nodes, including Chebyshev nodes, the growth is only logarithmic.

This distinction is essential: the Runge phenomenon is not a general failure of polynomials as approximating functions. It is a failure of a particular interpolation process.

Node placement and alternative methods

Chebyshev nodes

A standard alternative is to use Chebyshev nodes, which cluster near the interval endpoints. One common choice on [−1,1][-1,1] is

xj=cos⁡(jπn),j=0,…,n.x_j=\cos\left(\frac{j\pi}{n}\right), \qquad j=0,\ldots,n.

Another uses the roots of a Chebyshev polynomial:

xj=cos⁡((2j+1)π2(n+1)),j=0,…,n.x_j= \cos\left(\frac{(2j+1)\pi}{2(n+1)}\right), \qquad j=0,\ldots,n.

These distributions are associated with Chebyshev orthogonal polynomials. Their endpoint clustering controls the growth of the interpolation operator and substantially improves convergence for many functions.

If a function extends analytically to a sufficiently large complex neighborhood of the interval, Chebyshev interpolation converges geometrically: its error is bounded by a constant times ρ−n\rho^{-n} for an appropriate ρ>1\rho>1. The locations of complex singularities determine the attainable rate.

Changing the node distribution is possible when the sampling locations can be chosen. It does not directly solve a problem in which only fixed, equally spaced measurements are available.

Piecewise interpolation

Instead of fitting one polynomial across the entire interval, piecewise interpolation divides the interval into smaller parts. Spline interpolation, particularly cubic spline interpolation, uses low-degree polynomials joined with specified smoothness conditions.

In this setting, increasing the number of samples can refine the partition without increasing the polynomial degree on each subinterval. This avoids the classical mechanism of increasingly high-degree global interpolation, although boundary conditions, local oscillations, and data noise can still affect the result.

Approximation without exact interpolation

When exact agreement with all samples is unnecessary, a lower-degree fit obtained by least squares can provide a more controlled approximation. With noisy observations, regularization can additionally limit unstable or excessively complicated fits.

These methods change the mathematical problem: they seek an approximation rather than a polynomial that passes through every data point. Their behavior depends on the degree, sampling pattern, and fitting criterion.

Distinctions from related phenomena

Numerical instability

The Runge phenomenon is distinct from errors caused by an unstable computation. Solving for polynomial coefficients in a monomial basis may involve an ill-conditioned linear system, introducing errors beyond those inherent in interpolation.

Barycentric interpolation often evaluates the same polynomial more reliably. It does not, however, eliminate the Runge phenomenon: accurately computing a poor interpolant still gives a poor approximation. This separates the quality of the mathematical approximation from the numerical stability of its implementation.

The Gibbs phenomenon

The Gibbs phenomenon concerns persistent overshoots near discontinuities in certain approximations, classically Fourier series. The Runge phenomenon can occur for an analytic function with no discontinuity and is strongly tied to interpolation nodes.

The two phenomena may look similar in plots, but their causes and remedies differ.

Polynomial approximation theorems

The Weierstrass approximation theorem states that every continuous real-valued function on a closed, bounded interval can be approximated uniformly by polynomials. It does not state that interpolating at equally spaced nodes produces such an approximating sequence.

There is therefore no contradiction between polynomial approximation being possible and a prescribed sequence of interpolants diverging.

Scope and limitations

The Runge phenomenon does not establish that high-degree interpolation is always unsuitable. Convergence depends jointly on the function, the node distribution, and the approximation norm.

Nor do Chebyshev nodes guarantee convergence for every continuous function. Their favorable Lebesgue constants yield strong results when the function has sufficient smoothness, but a general limitation remains: for any fixed sequence of interpolation node sets, some continuous function has polynomial interpolants that fail to converge uniformly.

In numerical modeling, the phenomenon is especially relevant when the number of data points is increased while a single global interpolating polynomial is retained. More samples and higher polynomial degree are separate choices; their effects cannot be assessed independently of node placement and the function’s regularity.