Back to the on-screen lesson ·
Building the interpolant one node at a time in a triangular table, so that a new data point appends a term instead of rebuilding everything.
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 fill a divided-difference table, read the Newton coefficients off its top diagonal, evaluate the result by nesting, and explain what a constant column and a zero column tell you about the data.
You know that $n$ points with distinct $x$ values determine one polynomial of degree at most $n-1$, and you have built it by substituting the nodes into a monomial form. That method rebuilds everything when a point is added; this lesson builds the same polynomial so that nothing is rebuilt.
The divided difference $f[x_i, \ldots, x_j]$ is defined by $f[x_i] = y_i$ and $f[x_i,\ldots,x_j] = \dfrac{f[x_{i+1},\ldots,x_j] - f[x_i,\ldots,x_{j-1}]}{x_j - x_i}$. The Newton form writes the interpolant as a sum of terms each carrying the factors of all earlier nodes. Nesting, or Horner's scheme, evaluates such a sum from the innermost bracket outwards.
Write the interpolant as $p(x) = c_0 + c_1(x - x_0) + c_2(x - x_0)(x - x_1) + \cdots$. Each term after the first vanishes at every node before it, so substituting the nodes in order determines the coefficients one at a time and never disturbs the ones already found. Those coefficients are the divided differences $c_k = f[x_0, \ldots, x_k]$, and they are computed in a triangular table: the data is the first column, and each later column is the difference of the entries above and below to its left, divided by the distance between the outermost nodes involved. Three things follow. First, adding a node costs one new diagonal, and the existing polynomial is unchanged — the property the Lagrange form lacks. Second, a divided difference over $k+1$ nodes equals $\dfrac{f^{(k)}(\xi)}{k!}$ for some $\xi$ in their span, so the table estimates derivatives from samples and is the bridge to the error term. Third, a column that comes out constant means the data lies on a polynomial of that degree, and the next column is zero — the table measures the data as well as fitting it.
Another way: steps
Another way: example
Data $(0,1)$, $(1,3)$, $(2,9)$: first differences $2$ and $6$; second difference $\dfrac{6-2}{2} = 2$. So $p(x) = 1 + 2x + 2x(x-1) = 1 + 2x^{2}$ — the same polynomial the monomial method gave, obtained without solving a system.
The divisor is not always one. With equally spaced nodes one apart the first differences look like plain subtractions, and it is easy to carry that habit into the second column — which spans two gaps and divides by two. Write the nodes at the side of the table and read the divisor off them: it is always the last node of the group minus the first.
To $(0,1)$, $(1,3)$, $(2,9)$ add $(3,19)$: the new first difference is $10$.
Extend the table by a row.
The new second difference is $\dfrac{10 - 6}{2} = 2$, and the third is $\dfrac{2 - 2}{3} = 0$.
The new coefficient is zero.
So the cubic term vanishes and the interpolant is still $1 + 2x^{2}$: the new point was already on it.
Nothing earlier was recomputed.
Sampling $f(x) = x^{3}$ at $0, 1, 2$ gives first differences $1$ and $7$.
Estimates of $f'$ in each gap.
The second difference is $3$, and $\tfrac12 f''(\xi) = 3\xi$ gives $\xi = 1$ — inside the span, as promised.
The theorem locates it.
The third difference over four nodes would be $\tfrac{f'''}{6} = 1$, the leading coefficient itself.
The table finds the cubic.
The first differences are $\dfrac{1-0}{1-0} = 1$ and $\dfrac{9-1}{3-1} = 4$.
Watch the second divisor.
The second difference spans from $0$ to $3$, so it divides by $3$: $\dfrac{4 - 1}{3} = 1$.
The interpolant is $x + x(x-1) = x^{2}$, which is right: all three points lie on it.
The data is $(0, 1)$, $(1, 4)$, $(2, 15)$. Fill in the divided-difference table.
| Data | First difference | Second difference | |
|---|---|---|---|
| Node at 0 | 1 | ||
| Node at 1 | 4 | — | |
| Node at 2 | 15 | — | — |
An interpolant through $4$ nodes has been written in Newton form. A further data point arrives. What has to be recomputed?
Put the five steps of interpolating $4$ points by divided differences into order.
Number the steps in order (write the number in the box):
The data comes from a smooth function $f$ sampled at $6$ nodes. Match each divided difference to what it estimates.
| The value of the function at that node | The first derivative, somewhere between the two nodes | Half the second derivative, somewhere in the span | The $5$-th derivative divided by $5$ factorial, somewhere in the span | |
|---|---|---|---|---|
| A divided difference over one node | ||||
| A divided difference over two nodes | ||||
| A divided difference over three nodes | ||||
| A divided difference over $6$ nodes |
A fourth reading arrives, and the data is now $(0, 2)$, $(1, 6)$, $(2, 12)$, $(3, 20)$. Complete the divided-difference table, including its third column.
| Data | First difference | Second difference | Third difference | |
|---|---|---|---|---|
| Node at 0 | 2 | |||
| Node at 1 | 6 | — | ||
| Node at 2 | 12 | — | — | |
| Node at 3 | 20 | — | — | — |
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
The Newton form of an interpolant on the nodes $0$, $1$, $2$ is $p(x) = 5 + x + x(x - 1)$. Evaluate it at $x = 3$ by nesting.
Answer:
You can build and read a divided-difference table and evaluate a Newton form by nesting. Say in your own words why adding a data point leaves the earlier coefficients untouched.
8. Your turn: the second divided difference of $(0,0)$, $(1,1)$, $(3,9)$, step 3