= Runge's phenomenon
{c}
{wiki}
= Runge phenomenon
{c}
{synonym}
The <Runge phenomenon> is the failure of increasing-degree <polynomial interpolation> at equally spaced <interpolation nodes> to converge to some smooth target <functions>, with large oscillations near the ends of the interval. It is a property of the approximation problem, and can occur even with exact arithmetic. A numerically stable evaluation method cannot remove it. Endpoint clustering, as in <Chebyshev-Lobatto nodes>, changes the approximation problem and can greatly improve it.https://fncbook.com/python/stability-1/[Driscoll and Braun, Fundamentals of Numerical Computation, §9.3.1–9.3.2]{ref}
Take $f(x)=1/(1+25x^2)$ on $[-1,1]$ and <polynomial degree> at most $10$. Use either $x_k=-1+k/5$ or $x_k=\cos(k\pi/10)$ for $k=0,\ldots,10$. Each <interpolation polynomial> passes through all eleven of its own samples, yet the first has severe endpoint oscillations and the second stays much closer to the target <function>. Evaluating both by the <barycentric interpolation formula> on $20{,}001$ equally spaced points, including the endpoints, gives sampled maximum absolute errors of approximately $1.915659$ and $0.132197$, respectively: about a $14.49$-fold reduction. These are maxima over the stated grid, not certified maxima over the continuous interval. The generator separately checks exact reproduction of all stored nodal values.
\Image[/interpolation-node-placement.png]
{title=Degree-10 interpolation of the Runge function at equally spaced and Chebyshev-Lobatto nodes, with absolute errors}
The <polynomial interpolation error> formula explains why <interpolation nodes> enter the analysis. If $f$ has $n+1$ continuous <derivatives> on an interval containing $x$ and all the <interpolation nodes>, then for a suitable $\xi_x$ in that interval,
$$
f(x)-p_n(x)=\frac{f^{(n+1)}(\xi_x)}{(n+1)!}\prod_{i=0}^n(x-x_i).
$$
At an <interpolation node> the error is zero directly. Away from the <interpolation nodes>, both the product and the high-order <derivative> matter. A short proof applies <Rolle's theorem> repeatedly to $f(t)-p_n(t)-[f(x)-p_n(x)]\prod_i(t-x_i)/\prod_i(x-x_i)$, which vanishes at $n+2$ distinct points.https://fncbook.com/polynomial/[Driscoll and Braun, Fundamentals of Numerical Computation, §9.1.2, Theorem 9.1.3]{ref}
The successful comparison here does not assert that <Chebyshev-Lobatto nodes> solve every approximation problem for every <function>. The <derivatives>, the <polynomial degree>, and measurement errors still matter. The <Lebesgue constant of interpolation> measures worst-case amplification of nodal errors, while the <polynomial reproduction error bound> relates interpolation to the <best uniform approximation> available at that <polynomial degree>.
Back to article page
