It seems obvious that more data points give a better fit. For polynomial interpolation at equally spaced points it is false, and the classic example is Runge's function $f(x) = \frac{1}{1 + 25x^{2}}$ on $[-1, 1]$. The error formula explains why, and a choice of nodes based on the unit circle fixes it.
| nodes | max error, equally spaced | max error, Chebyshev |
|---|---|---|
| $5$ | $0.44$ | $0.40$ |
| $11$ | $1.9$ | $0.11$ |
| $21$ | $60$ | $0.015$ |
Two things go wrong at the same time. The derivatives $f^{(n+1)}$ of Runge's function grow very fast with $n$ (it has poles at $x = \pm\frac{i}{5}$ in the complex plane, close to the interval). And for equally spaced nodes the node product $\omega(x)$ is far larger in the outer gaps than in the middle. Together they win over the $(n + 1)!$ in the denominator.
The cure is to choose nodes that keep $|\omega(x)|$ small everywhere. The Chebyshev nodes on $[-1, 1]$ are $$x_k = \cos\frac{(2k + 1)\pi}{2(n + 1)},\quad k = 0, 1, \ldots, n:$$ the $x$-coordinates of points equally spaced in angle around the upper half of the unit circle. They crowd toward the ends of the interval.
Key idea
Why it works
Worked example: Three Chebyshev nodes
- Angles $\frac{\pi}{6}, \frac{\pi}{2}, \frac{5\pi}{6}$, so the nodes are $\frac{\sqrt{3}}{2}$, $0$, $-\frac{\sqrt{3}}{2}$.
- Chebyshev: $\max|\omega| = 2^{-2} = \frac{1}{4}$.
- Equally spaced: $\omega = x^{3} - x$, largest at $x = \pm\frac{1}{\sqrt{3}}$, where $|\omega| = \frac{2\sqrt{3}}{9} \approx 0.385$.
- With 11 nodes the gap is wider: about $0.0085$ for equal spacing against $2^{-10} \approx 0.00098$ for Chebyshev.
Answer: $\pm\frac{\sqrt{3}}{2}$ and $0$; $0.25$ versus $0.385$
Worked example: Another interval
- Use $x = \frac{a + b}{2} + \frac{b - a}{2}t = 2 + 2t$ for each node $t$.
- $t = \pm\frac{\sqrt{3}}{2}, 0$ give $x = 2 \pm \sqrt{3}$ and $x = 2$, about $0.27$, $2$ and $3.73$.
Answer: $2 - \sqrt{3}$, $2$, $2 + \sqrt{3}$
Common mistake