Polynomial interpolation and Runge's phenomenon

You fit a curve through your data. It passes through every point perfectly. Then you plot it and the curve swings way above and below your data between the points, especially near the ends.

You add more data points to fix it. It gets worse. This is Runge's phenomenon, and it is the reason nobody fits one big polynomial through a long dataset.

The quick answer

A single polynomial through many evenly spaced points oscillates wildly between them, and adding more points makes the swings bigger rather than smaller.

Two fixes. Either choose where you sample, bunching points toward the ends of your range (Chebyshev nodes), or stop using one big curve and switch to a cubic spline. With data you did not choose, use the spline.

The function that showed it up

Carl Runge worked this out in 1901 using a function that looks completely harmless:

f(x) = 1 ÷ (1 + 25x²) on the range from −1 to 1

It is smooth everywhere, has no breaks or spikes, and has a single hump of height 1 at the middle that falls to about 0.0385 at each end. Nothing about it looks like trouble.

Sample it at evenly spaced points and fit a polynomial through them. With a few points the fit is mediocre. Add more and the middle gets better while the ends develop growing waves. Keep adding and the largest error does not shrink toward zero. It grows without limit.

Watch it happen with five points

Sample the function at five evenly spaced x values:

The data is symmetric around zero, so the polynomial through it only needs even powers. That means it looks like P(x) = a + bx² + cx⁴, and three of your points determine the three unknowns.

At x = 0 everything with an x in it disappears, so a = 1 straight away.

At x = 1, all the powers equal 1, so 1 + b + c = 0.038462, giving b + c = −0.961538.

At x = 0.5, you get x² = 0.25 and x⁴ = 0.0625, so 0.25b + 0.0625c = −0.862069.

Multiply that last one by 16 so the c terms match, then subtract the other equation:

4b + c = −13.793104
−( b + c = −0.961538 )
3b = −12.831566, so b = −4.277189

And c = −0.961538 + 4.277189 = 3.315651. So your fitted curve is:

P(x) = 1 − 4.277189x² + 3.315651x⁴

Now test it somewhere between two of your data points, at x = 0.75. There x² = 0.5625 and x⁴ = 0.316406:

P(0.75) = 1 − 2.405919 + 1.049093 = −0.356826

The real value there:

f(0.75) = 1 ÷ (1 + 25 × 0.5625) = 1 ÷ 15.0625 = 0.066390

Your polynomial says negative 0.36 for a function that is positive everywhere it is defined. With only five points, the error at that spot is 0.42, which is bigger than almost all of the function's own values outside the central hump. The fit hits all five data points exactly and is useless between them.

Take it to eleven evenly spaced points and it deteriorates further: the curve swings to roughly 1.9 near x = 0.9, where the true value is about 0.05.

Why it happens

The error at any point x has this shape:

f(x) − P(x) = [ f⁽ⁿ⁺¹⁾(ξ) ÷ (n+1)! ] × (x − x₀)(x − x₁)…(x − x_n)

Two things are fighting each other as you add points.

The factorial on the bottom grows extremely fast, which drives the error down. That is the part everyone expects to win, and it is why more points feels like it should help.

The derivative on top can grow faster still. For this particular function the high derivatives explode, because the function has trouble spots just off the real number line at plus and minus one fifth of i. They are not on your interval, but they are close enough to dominate.

The bracket product is the third piece and it explains the location. With evenly spaced points, that product is much larger near the ends of the range than in the middle, because out near the edge every single factor is close to its largest value at the same time. In the middle, the factors are small and some are positive while others are negative, so they partly cancel. That is why the waves appear at the edges and not the centre.

Fix one: pick better sample locations

Evenly spaced is a habit, not a requirement. Chebyshev nodes bunch the samples toward the ends:

x_k = cos(kπ ÷ n), for k = 0, 1, …, n

Picture equally spaced points around a semicircle, then drop each one straight down to the x axis. They come out dense at the edges and sparse in the middle, which is exactly where the trouble was. These positions are chosen to keep that bracket product as small as possible, and the improvement is dramatic: on Chebyshev nodes the fit to the Runge function converges as you add points instead of falling apart.

The catch is that this requires you to control where the measurements happen. If someone hands you a table sampled every 10 units, this fix is not available.

Fix two: use lots of small curves

This is what you do with data you did not choose, which is most data. Rather than one polynomial of high degree through everything, fit a separate cubic to each gap and join them smoothly. That is a cubic spline.

It cannot suffer from Runge's phenomenon, because the degree never goes above 3 no matter how many points you add. More points just means more, smaller pieces, so a spline gets strictly better as your data improves.

What to take away

Treat any polynomial degree above about 5 as a warning. Fitting a degree 12 curve to 13 points is almost never what you want, however good it looks at the points themselves.

Judge a fit by how it behaves between your data, not at it. Every interpolating polynomial has zero error at every data point by construction, so that number tells you nothing whatsoever.

Never push a high degree polynomial past the end of your data. Inside the range it oscillates. Outside it diverges, which is covered in interpolation vs extrapolation.

To see this on your own numbers, run the same points through polynomial mode and spline mode in the interpolation calculator and compare the two curves between the points. The difference is usually obvious at a glance. For how the polynomial is actually built, see Lagrange interpolation.