Why node placement affects an error bound
For distinct nodes in , the interpolation remainder for is
where lies between the smallest and largest of when is not a node; at a node the error is zero. If a bound is known, the size of the node product controls a uniform error bound.
Definition 7.8.1
(Monic polynomial and uniform norm)
A polynomial of degree is monic if its leading coefficient is . The node product is monic of degree . For a function on , .
Which monic polynomial of degree has the smallest uniform norm on ?
Chebyshev polynomials
Definition 7.8.2
(Chebyshev polynomials)
For , define the polynomials by the recurrence
Proposition 7.8.3
(Cosine form and alternating extrema)
For all , . For , has degree and leading coefficient . On we have , and at the points
it takes the alternating values .
Proof
(Induction with the cosine identity)
The cases are and . The identity shows that satisfies the same recurrence at , which gives by induction. The recurrence multiplies the leading term by , so the degree rises by one and the leading coefficient doubles from at , giving . Every equals for some , so , and .
The monic polynomial
therefore has maximum absolute value on the interval.
Common mistake
(Using itself for the node product)
has uniform norm , but its leading coefficient is , not . A node product is monic, so it equals and has norm . Using in the error bound overstates it by the factor .
The minimax product theorem
Theorem 7.8.4
(Minimax property of monic Chebyshev polynomials)
For every monic real polynomial of degree ,
The polynomial attains the bound.
Proof
(A strictly better competitor would have too many zeros)
Suppose instead that . At each , the difference has the sign , because is strictly smaller than . Consecutive points are distinct and ordered in reverse, so the intermediate value theorem gives a zero of in each of the disjoint open intervals between them. But both polynomials are monic, so their difference has degree at most . It cannot have distinct zeros unless it is zero, which contradicts the strict inequality. Therefore no monic has a smaller uniform norm; attains it.
Proof X-ray
Alternating extrema force too many zeros
The proof does not guess where an arbitrary competitor is largest. It tests the competitor at known extrema. Strict improvement would force alternating signs in the difference and hence zeros, but cancellation of the leading terms leaves degree at most . The monic hypothesis is used exactly once, in that cancellation; without it the constant multiple would be an arbitrarily small competitor.
From the minimax polynomial to nodes
Theorem 7.8.5
(Error bound at Chebyshev roots)
Let . The zeros of are
they are distinct and lie in , and interpolation at these Chebyshev roots satisfies
Among all choices of distinct nodes in , this choice minimizes the uniform norm of the node product.
Proof
(Counting roots and comparing monic polynomials)
The angles lie distinctly in and the cosine of times each is zero. Thus the displayed points are distinct roots of the degree- polynomial and lie in . Since the node product is monic with these zeros, it equals , with norm ; the remainder formula then gives the bound. Any other node set gives a monic product of degree , whose norm is at least by the minimax theorem.
This choice minimizes this particular bound when the same is used. Other commonly used Chebyshev grids include endpoints and serve different practical purposes; they are not the root grid derived here.
Worked example 7.8.6
(The linear interpolant on two nodes)
For , , the two nodes are , and the product is . Its maximum absolute value on is . For , the linear interpolant at both nodes is the constant , so the actual maximum error is also . The derivative bound gives exactly.
Worked example 7.8.7
(Three Chebyshev roots against equal spacing)
For , , the roots of are and , and the node product is with norm . For we may take , so the bound is . With equally spaced nodes the product is , whose maximum on is at . The corresponding bound is , larger by the factor .
Worked example 7.8.8
(The smallest case, one node)
For , , there is one node, the zero of . The node product is , with norm , and the interpolant is the constant . The bound reads with , and for it is attained at .
Counterexample mode
A minimax bound is not a claim about every function's actual error
Claim: Chebyshev roots give the smallest actual interpolation error for every . If is already a polynomial of degree at most , interpolation is exact at any distinct nodes. Chebyshev roots minimize the worst possible node product and the displayed derivative-based upper bound; another node set can give a smaller actual error for a particular function. For example, with and , the root nodes give the interpolant and error , whose maximum on is at . The nodes give the interpolant and error , whose maximum is .
What the bound leaves open
The derivative constant depends on when the degree changes. The formula alone does not prove convergence for every infinitely differentiable function as . It also does not bound how data errors or floating-point rounding are amplified; those are separate conditioning and stability questions. In practice, one may evaluate the interpolant with a barycentric formula, while still choosing nodes and a degree appropriate to the data.
Practice with solutions
Quick check
(Compute and verify that is monic.)
Solution · Answer
, so .
Quick check
(For , list the roots of and give the minimum possible maximum norm of a monic cubic on .)
Solution · Answer
The roots are , and the minimum norm is .
Quick check
(If , what does the Chebyshev-root bound give?)
Solution · Answer
It gives .
Quick check
(Why does the minimax proof use a strict hypothetical improvement?)
Solution · Answer
Strict improvement makes the difference's sign nonzero and alternating at every extremum; then the intermediate value theorem gives distinct zeros between adjacent extrema.