Back to the on-screen lesson ·
Why the node product is the only factor of the interpolation error a node choice can touch, how the Chebyshev roots minimise it, and what that leaves untouched.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to isolate the node product in the interpolation error, explain why choosing nodes is choosing a monic polynomial, compute the Chebyshev error bound, say what Runge's phenomenon is and what it is not, and scale the construction to another interval.
You have built interpolating polynomials, seen the error formula with its node product, and watched equally spaced interpolation of a smooth function go wild near the ends of an interval. You also know that the monic Chebyshev polynomial has the smallest largest size of any monic polynomial of its degree. This lesson is those two facts meeting.
The node product is $\prod_i (x - x_i)$, the factor of the interpolation error that depends on where the nodes are. Chebyshev nodes are the roots of $T_n$, at $\cos\dfrac{(2i+1)\pi}{2n}$. Runge's phenomenon is the wild oscillation of an equally spaced interpolant near the ends of the interval. A half-width is half the length of the interval a construction has been rescaled to.
The interpolation error at $n$ nodes is
$$f(x) - p(x) = \frac{f^{(n)}(\xi)}{n!}\prod_{i}(x - x_i),$$
and the nodes appear in exactly one factor of it. That factor is a polynomial in $x$ of degree $n$ with leading coefficient one — it is monic, whatever the nodes are — so choosing the nodes is choosing which monic polynomial of degree $n$ it is. Minimising its largest size is therefore a problem whose answer is already known: the monic Chebyshev polynomial, with largest size $2^{1-n}$ on $[-1, 1]$. Taking the nodes to be its roots gives the Chebyshev nodes, which crowd towards the ends of the interval, and that crowding is the cure for Runge's phenomenon: with equal spacing the node product is tiny in the middle and enormous near the ends, and the interpolant oscillates exactly where the product is large. Two limits are worth stating with the result. The other factor, $\dfrac{\max|f^{(n)}|}{n!}$, belongs to the function and no node choice touches it — a corner or a nearby pole defeats Chebyshev nodes as thoroughly as any others. And on an interval of half-width $c$ every distance scales, so the node product gains a factor $c^{n}$: on a long interval the gain from good nodes is overrun, and splitting the interval is the answer instead.
Another way: steps
Another way: picture
Draw the node product for eleven equally spaced nodes: a wave whose humps in the middle barely leave the axis and whose outermost humps are hundreds of times taller. Now draw it for eleven Chebyshev nodes: every hump the same height. The second picture is the equal ripple, and the first is Runge's phenomenon before the interpolant has even been mentioned.
Chebyshev nodes are treated as a general cure for bad interpolation. They are a complete answer to one factor of the error bound and no answer at all to the other. A function with a corner, or with a pole just off the interval, still interpolates badly at Chebyshev nodes, and adding nodes still makes it worse, because the derivative factor grows faster than anything the node product can save. The right response there is a different approximating space — a spline, or a fit on each side of the trouble — rather than a different sampling of the same one.
Three nodes on $[-1, 1]$: $\cos\dfrac{\pi}{6}$, $\cos\dfrac{\pi}{2}$, $\cos\dfrac{5\pi}{6}$.
Roots of $T_3$.
That is $\pm\dfrac{\sqrt3}{2}$ and $0$ — squares $\tfrac34$, $0$, $\tfrac34$, so the outer pair sits at about $\pm 0.87$ rather than $\pm 0.67$.
Pushed outward from equal spacing.
$f(x) = \dfrac{1}{1 + 25x^{2}}$ on $[-1, 1]$, equally spaced: the error at the ends grows without bound as nodes are added.
A pole at $\pm i/5$, just off the interval.
At Chebyshev nodes the same function interpolates to full precision with a few dozen nodes.
The node product was the whole of the trouble.
Five nodes make the product monic of degree five.
The best largest size is $2^{1-5} = \tfrac{1}{16}$.
So the interpolation error is at most $\dfrac{\max|f^{(5)}|}{5!} \times \dfrac{1}{16}$, and only the first factor is still open to argument.
A function on $[-1, 1]$ has $|f^{(3 + 1)}| \le 6$ everywhere, and is interpolated at the $3 + 1$ Chebyshev nodes. What does the error bound $\dfrac{\max|f^{(n+1)}|}{2^{n}(n+1)!}$ give? Give a fraction.
Answer:
On $[-1, 1]$, the node product $\prod_{i}(x - x_i)$ for $n$ Chebyshev nodes has largest size $2^{1-n}$. Give that size for $4$, $5$ and $6$ nodes, as fractions.
| Nodes | Largest size of the node product | |
|---|---|---|
| $4$ nodes | 4 | |
| $5$ nodes | 5 | |
| $6$ nodes | 6 |
Put the five steps of choosing interpolation nodes into the order they depend on each other.
Number the steps in order (write the number in the box):
Match each choice of interpolation nodes to what the node product does.
| Small in the middle, exponentially large near the ends | The same size at every hump: the worst case is as small as possible | Worse near the ends than equal spacing, which was already the problem | The Taylor case: excellent at that point, hopeless away from it | |
|---|---|---|---|---|
| Equally spaced nodes | ||||
| Chebyshev nodes | ||||
| Nodes clustered in the middle | ||||
| All the nodes at a single point |
The Chebyshev construction is moved from $[-1, 1]$ to an interval of length $8$, keeping $4$ nodes. By what factor does the largest size of the node product change?
Answer:
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
A function with a corner in the middle of $[-1, 1]$ is interpolated at $12$ Chebyshev nodes. What should be expected?
You can derive the Chebyshev node choice from the interpolation error and state its limits. Say in your own words why good nodes cannot rescue a function with a corner.
8. Your turn: the best possible node product size for five nodes on $[-1, 1]$, step 3