Back to the on-screen lesson ·
The error term of an interpolant, the node polynomial that shapes it, and why adding equally spaced nodes to a perfectly smooth function can make the answer worse.
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 state and apply the interpolation error formula, compute the node polynomial and see where it is large, bound the error at a point, and explain why more equally spaced nodes is not a reliable way to improve an interpolant.
You know that a divided difference over $k+1$ nodes equals $f^{(k)}(\xi)/k!$ for some $\xi$ in their span. Adding one hypothetical extra node at the point you are evaluating turns that fact into this lesson's error formula.
The node polynomial $\omega(x) = \prod_i(x - x_i)$ is the product of the distances from $x$ to every node. Runge's phenomenon is the divergence of equally spaced interpolants of some smooth functions as nodes are added. The Chebyshev points are nodes clustered towards the ends of the interval, chosen to make $\max|\omega|$ as small as possible.
For $f$ with $n+1$ continuous derivatives interpolated at $n+1$ nodes, $f(x) - p(x) = \dfrac{f^{(n+1)}(\xi)}{(n+1)!}\,\omega(x)$ with $\xi$ somewhere in the span of the nodes and $x$. Three factors, three separate stories. The derivative belongs to the function and nothing you do changes it. The factorial shrinks fast as nodes are added, which is the reason interpolation usually improves. The node polynomial is the part you control, and with equally spaced nodes it is badly behaved: $|\omega|$ near the ends of the interval is far larger than in the middle, and the ratio worsens with the degree. Put the second and third together with a function whose high derivatives grow quickly and you get Runge's phenomenon: $\dfrac{1}{1+25x^{2}}$ on $[-1,1]$ is infinitely differentiable, and its equally spaced interpolants diverge, with oscillations near $\pm 1$ growing without bound. The repair is to move the nodes, not to add them: clustering towards the ends flattens $|\omega|$ and restores convergence. Notice what the formula also says: the error is exactly zero at every node, so a check against the data can never detect any of this.
Another way: steps
Another way: example
Interpolating at $0, 1, 2$ with $|f'''| \le 6$: at $x = \tfrac12$, $\omega = 0.375$ and the bound is $\dfrac{6 \times 0.375}{6} = 0.375$. At $x = \tfrac52$, half a gap outside, $\omega = 1.875$ and the bound is $1.875$ — five times as large, for the same function and the same nodes.
The instinct that more nodes must be better is the same instinct that a smaller step must be better, and this subject punishes both. The formula shows why: adding a node divides by one more factor of the factorial and multiplies by one more factor in $\omega$ and moves to a higher derivative of $f$. Two of those three can grow, and for equally spaced nodes they often do. Whether interpolation improves is a question about the function and the node placement together, and it is not answered by counting.
At $x = x_j$ the node polynomial has a factor $(x_j - x_j) = 0$.
So $\omega(x_j) = 0$.
Hence $f(x_j) - p(x_j) = 0$ whatever the derivative does.
The formula reproduces the interpolation property.
Which means checking an interpolant against its own data measures nothing at all: the answer is zero by construction.
Test between the nodes, or not at all.
$f(x) = \dfrac{1}{1 + 25x^{2}}$ on $[-1,1]$ is smooth and bounded by $1$.
Nothing looks dangerous.
Its equally spaced interpolants of degree $10$ overshoot near $\pm1$ by about $2$, and degree $20$ by far more.
The error grows with the degree.
At Chebyshev nodes the same degrees converge steadily. The function did not change; the node placement did.
The node polynomial was the problem.
At any node $x_j$ the node polynomial contains the factor $x_j - x_j$.
So $\omega(x_j) = 0$ and the whole product is zero.
The bound is zero, and so is the error — which is why a fit to its own data is not evidence of anything.
For an interpolant through $3$ nodes the error is $f(x) - p(x) = \dfrac{f^{(3)}(\xi)}{3!}\,\omega(x)$, where $\omega(x) = \prod_i (x - x_i)$. Match each part to what controls it.
| The function being interpolated, and nothing you choose | How many nodes there are, and nothing else | Where the nodes are and where you are evaluating | Unknown, somewhere inside the span, and bounded rather than found | |
|---|---|---|---|---|
| The derivative $f^{(3)}$ | ||||
| The factorial $3!$ | ||||
| The node polynomial $\omega(x)$ | ||||
| The point $\xi$ |
An interpolant on a fixed interval uses $15$ equally spaced nodes, and more are added. What happens to the largest error on the interval?
The nodes are $0$, $3$ and $6$, so $\omega(x) = x(x - 3)(x - 6)$. Evaluate $\omega$ at the three points shown, signs included.
| Value of x | Value of the node polynomial | |
|---|---|---|
| Inside, first gap | 1.5 | |
| Inside, second gap | 4.5 | |
| Just outside | 7.5 |
Put the five steps of bounding the error of an interpolant through $6$ nodes into order.
Number the steps in order (write the number in the box):
The same function, with $|f'''| \le 2$ on the interval from $0$ to $\tfrac52$, and the same nodes $0$, $1$, $2$. Bound the error at $x = \tfrac52$, half a gap beyond the last node.
Answer:
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
A function with $|f'''| \le 3$ on the interval from $0$ to $2$ is interpolated at the nodes $0$, $1$ and $2$. Bound the error at $x = \tfrac12$.
Answer:
You can bound an interpolation error at a point and say which factor of the formula each choice controls. Say in your own words why testing an interpolant against its own data measures nothing.
8. Your turn: the error bound at a node, step 3