Why a table?
Suppose values arrive one at a time. Reconstructing every Lagrange basis polynomial after adding a node obscures what can be reused. Newton form instead keeps the old polynomial and adds one term that vanishes at every old node. The coefficient of that term is a divided difference. A triangular table computes all these coefficients using only differences and divisions.
Definition 7.6.1
(Divided-difference table)
Let be distinct, with data . Define and, for and ,
Thus , using the divided-difference notation for the given data. The entries on the diagonal give
No function between the nodes is required to construct this polynomial. The notation records data values; it does not imply extra evaluations of .
Why the coefficients interpolate
Theorem 7.6.2
(Newton interpolation formula)
For distinct nodes the polynomial with is the unique polynomial of degree at most with for all .
Proof
(Differences of consecutive interpolants)
For a consecutive block , let be its unique interpolant of degree at most . Its coefficient of is the divided difference of that block. Indeed, for this is the data value. At the next level the Neville relation expresses using the two overlapping degree-at-most- interpolants; comparing coefficients of gives the recurrence above.
Now has degree at most and vanishes at . It is therefore a constant multiple of . Its coefficient of is , since has lower degree. Summing these differences proves the displayed Newton formula. This argument also covers the case in which the highest coefficient happens to be zero.
Proof X-ray
What changes when a node arrives?
If a new distinct node and value arrive, the previous coefficients remain unchanged. Compute only the new last entries, ending with , and append . The extra term vanishes at the old nodes, while the recurrence makes the result correct at the new node. This is an exact-arithmetic statement: rounded data or repeated computation can change computed coefficients.
The hypothesis that the nodes are distinct enters every denominator , and it cannot simply be dropped.
Counterexample mode
Repeated nodes break the table
A tempting claim is that any data pairs have a polynomial interpolant of degree at most that the table computes. Take with , , . No function at all, polynomial or not, takes the values and at the same point . The table's first entry would be , a division by zero, so the failure is not an artifact of the formula. Distinct nodes make every denominator nonzero. Repeated nodes need consistent data and a different construction, which is not treated here.
A table and nested evaluation
Worked example 7.6.3
(Four data points)
Take . The table is
| 0 | 0 | 1 | |||
| 1 | 1 | 2 | 1 | ||
| 2 | 2 | 5 | 3 | 1 | |
| 3 | 3 | 10 | 5 | 1 | 0 |
For instance, and . Hence . The zero last coefficient says the four data points already lie on a quadratic; it does not say that an unknown underlying function is quadratic between the nodes.
At , evaluate in nested form:
Starting with , replace by for . This takes multiplications and additions after the differences are available.
Worked example 7.6.4
(Unequally spaced nodes)
Take nodes with values . The first divided differences are and ; the second is . So and . Check: , , . Nested evaluation at gives , in agreement with .
Worked example 7.6.5
(Appending a node whose new coefficient is zero)
Append to the data of the previous example, keeping the old coefficients. The new first difference is , the next is , and the new third difference is . The appended term is , so still, and indeed . This conclusion concerns these four data values, not every function agreeing with them.
In-place construction and its ordering
Initialize an array . For each , update downward for :
Theorem 7.6.6
(Correctness and cost of the in-place update)
With the descending update, after pass one has for and for . Hence for every at the end. The construction uses divisions and array storage.
Proof
(Invariant of the descending update)
Before pass we have for all . Suppose that before pass the array holds for and for . In pass the index runs from down to . When is updated, the cell has not yet been changed in this pass, because is visited later or, when , never. So the operands are and , and the new value is . The cells with index below are untouched, and is now finished, so the invariant holds after pass . Pass performs divisions, giving in total, and only the array is stored besides the nodes.
Nested evaluation uses work per target.
Common mistake
(An ascending update mixes two columns)
With the first three values above, the first pass must give . If is overwritten first with , an ascending update instead computes . The error is not a harmless change of node order: it is a different computation using an already overwritten operand.
The mathematical interpolant is independent of node order by uniqueness, though Newton coefficients and the intermediate calculations depend on it. In floating-point arithmetic different orders can produce different rounding errors, and close nodes make the divisions sensitive to data perturbations. A small table residual at the nodes does not by itself guarantee accuracy between them or bound numerical error; stability and conditioning require separate analysis.
Practice with solutions
Quick check
(Use nodes with values . Find the divided-difference coefficients and the value of the interpolant at .)
Compute two first differences, then one second difference.
Solution · Answer
The first differences are and , and the second is . So and . Then , which agrees with .
Quick check
(For arbitrary distinct , explain why changing their order can change but not the interpolating polynomial.)
What is in terms of the first two nodes?
Solution · Answer
The first coefficient after the constant is the slope between the first two nodes; a different first pair may have a different slope. Both final polynomials interpolate the same three values and have degree at most two, so uniqueness makes them equal in exact arithmetic.
Quick check
(How many divisions does the table need for five nodes?)
Use the count in the cost statement with .
Solution · Answer
Five nodes means , so the table needs divisions: over the four passes.
Quick check
(Which denominator in the table would vanish if two nodes coincided, and what does that signal?)
Look at .
Solution · Answer
The denominator vanishes when . It signals that the data cannot be treated as distinct-node interpolation: two different values at one point would be inconsistent, and equal values would still need a different construction.