Interpolation and numerical integration with error terms

In one sentence

There is exactly one polynomial of degree $\le n$ through $n+1$ points, adding equispaced points can make the approximation worse, and Simpson's rule is exact for cubics rather than for quadratics.

Why the exam asks it

Because two results run against expectation — Runge's phenomenon and Simpson's extra degree — and both have short, checkable statements. Degree of precision is also a definition that can be tested directly.

The idea

Interpolation

Through $n+1$ distinct nodes there is a unique polynomial of degree $\le n$. Lagrange form:

$$p(x) = \sum_{i=0}^{n} f(x_i)\,\ell_i(x), \qquad \ell_i(x)=\prod_{j\ne i}\frac{x-x_j}{x_i-x_j}.$$

Newton's divided-difference form gives the same polynomial and is cheaper to extend by one node. Uniqueness means they agree — a question asking whether two forms give different polynomials is asking whether you know that.

Error: for $f$ sufficiently smooth,

$$f(x)-p(x) = \frac{f^{(n+1)}(\xi)}{(n+1)!}\prod_{i=0}^{n}(x-x_i).$$

Both factors matter. The product is small in the middle and large near the ends, and $f^{(n+1)}$ can grow with $n$ faster than $(n+1)!$ shrinks.

Runge's phenomenon

$f(x)=\dfrac{1}{1+25x^2}$ on $[-1,1]$, interpolated at equispaced nodes, oscillates violently near the endpoints, and the oscillation grows as nodes are added. More data makes it worse.

The fix is the node spacing, not the degree: Chebyshev nodes $x_k = \cos\frac{(2k+1)\pi}{2n}$ cluster at the ends and minimise the maximum of $\prod|x-x_i|$. The same degree through Chebyshev nodes tracks the function closely.

The moral is that "more points is better" is false, and that the error formula predicted it — the product term is exactly what Chebyshev nodes optimise.

Quadrature and degree of precision

The degree of precision is the largest $d$ such that the rule is exact for all polynomials of degree $\le d$.

• Trapezoid: $\frac{h}{2}(f_0+f_1)$, error $-\frac{h^3}{12}f''(\xi)$, precision 1.
• Simpson: $\frac{h}{3}(f_0+4f_1+f_2)$, error $-\frac{h^5}{90}f^{(4)}(\xi)$, precision 3.
• Gauss with $n$ nodes: precision $2n-1$.

Simpson is built to be exact for quadratics and comes out exact for cubics as well — the cubic error term vanishes by symmetry, which is why the error involves $f^{(4)}$ rather than $f'''$.

Checked directly on $[0,1]$: for $x^3$, Simpson gives $\frac16(0+4\cdot\frac18+1) = \frac14$, which is exact. For $x^4$ it gives $\frac{5}{24}$ against $\frac15$ — an error of $\frac1{120}$, and the first failure.

Gauss quadrature achieves precision $2n-1$ with only $n$ nodes by choosing the nodes as well as the weights — they are the roots of the Legendre polynomial. Two points give precision $3$, the same as Simpson's three points.

Composite rules: over $n$ subintervals the total error is $O(h^2)$ for trapezoid and $O(h^4)$ for Simpson, one power lower than the single-interval error because there are $O(1/h)$ of them.

Where intuition breaks

"More interpolation nodes give a better approximation." Runge. With equispaced nodes the error can grow without bound as $n\to\infty$.

"Simpson's rule is exact for quadratics." For cubics. Its precision is $3$, not $2$, which is why it is so much better than trapezoid.

"Lagrange and Newton forms give different polynomials." The interpolating polynomial is unique. Different formulas, same polynomial.

"Gauss quadrature with $n$ points has precision $n$." $2n-1$. Choosing the nodes doubles what fixed nodes achieve.

"The composite error is the same order as the single-interval error." One order lower: $h^3$ becomes $h^2$ for trapezoid, $h^5$ becomes $h^4$ for Simpson.

"Runge's phenomenon is about the function being badly behaved." $1/(1+25x^2)$ is smooth on $\mathbb{R}$ — its trouble is the poles at $\pm i/5$ in the complex plane, near the interval. The radius-of-convergence chapter is the explanation.

"Chebyshev nodes fix it by using more points." Same number of points, different placement.

The exam's angle

1. For "degree of precision", test monomials in order — $1, x, x^2, \dots$ — until the rule fails. That is the definition applied directly.
2. Remember Simpson is exact through cubics and Gauss-$n$ through degree $2n-1$.
3. Match the error term to the derivative order: $f''$ for trapezoid, $f^{(4)}$ for Simpson, and the composite version one power of $h$ lower.
4. If a question adds nodes and asks whether the error falls, check the spacing. Equispaced is the trap.
5. Use uniqueness. Any question comparing two interpolation methods on the same nodes has the same answer for both.

The night before

• Unique polynomial of degree $\le n$ through $n+1$ nodes; Lagrange and Newton give the same one.
• Error $\dfrac{f^{(n+1)}(\xi)}{(n+1)!}\prod(x-x_i)$.
• Runge: equispaced nodes on $1/(1+25x^2)$ diverge as $n$ grows. Chebyshev nodes, same degree, do not.
• Trapezoid: precision $1$, error $-h^3f''/12$. Simpson: precision 3, error $-h^5f^{(4)}/90$.
• Composite: $O(h^2)$ and $O(h^4)$ respectively.
• Gauss with $n$ nodes: precision $2n-1$, nodes at Legendre roots.
• Simpson on $[0,1]$: exact for $x^3$, gives $5/24$ against $1/5$ for $x^4$.