Recipe

Construct Newton's divided-difference interpolating polynomial

Use when: you have a table of (x, y) data points (or values of a known function at chosen nodes) and want a polynomial passing through all of them, especially if you might add more points later

Goal: the divided-difference table's top diagonal, assembled into Newton's nested form for P(x)

Taught in Newton's divided-difference form

1. 1

   Arrange the nodes x_0 < x_1 < \cdots < x_n in a column, with their known values f(x_i) beside them. This is divided-difference order zero: f[x_i]=f(x_i).

   Example

   For (1,3), (2,1), (4,3), (5,10):

   x_i	f[x_i]
   1	3
   2	1
   4	3
   5	10

   • nodes already listed in increasing x order — proceed directly to Step 2.
   • nodes given out of order — relabel them x_0<x_1<\cdots<x_n first, carrying each value along with its node. The table only builds correctly left-to-right along increasing x.

   Why: every higher-order divided difference is defined recursively from this column. So it has to be right, and correctly ordered, before anything else is computed.

2. 2

   For each adjacent pair, compute f[x_i,x_{i+1}]=\dfrac{f[x_{i+1}]-f[x_i]}{x_{i+1}-x_i}. This is the ordinary slope between those two points.

   Example

   f[1,2]=\dfrac{1-3}{2-1}=-2, \quad f[2,4]=\dfrac{3-1}{4-2}=1, \quad f[4,5]=\dfrac{10-3}{5-4}=7.

   Why: this is the same slope formula from introductory algebra. It's just written with bracket notation so it generalizes cleanly to the next step.

3. 3

   Repeat the same pattern one order up: f[x_i,\ldots,x_{i+k}]=\dfrac{f[x_{i+1},\ldots,x_{i+k}]-f[x_i,\ldots,x_{i+k-1}]}{x_{i+k}-x_i}. Use the two nearest entries in the column just built. Keep going until the table narrows to a single final entry.

   Example

   f[1,2,4]=\dfrac{1-(-2)}{4-1}=1, \quad f[2,4,5]=\dfrac{7-1}{5-2}=2, then f[1,2,4,5]=\dfrac{2-1}{5-1}=\dfrac14.

   Why: each new order measures how much the previous order's own "slope" changes across one more node. It's the same recursive idea as Step 2, just one level higher every time.

4. 4

   Read the top diagonal — f[x_0], f[x_0,x_1], f[x_0,x_1,x_2], \ldots — as the coefficients of Newton's nested form: P(x)=f[x_0]+f[x_0,x_1](x-x_0)+f[x_0,x_1,x_2](x-x_0)(x-x_1)+\cdots

   Example

   P(x)=3-2(x-1)+1(x-1)(x-2)+\frac14(x-1)(x-2)(x-4)

   which expands to P(x)=\dfrac{x^3}{4}-\dfrac{3x^2}{4}-\dfrac{3x}{2}+5.

   ⚡ Shortcut

   If the goal is a single value P(x^*) rather than the expanded formula, never expand at all. Evaluate the nested form directly (Horner-style), innermost parentheses first, straight from the divided-difference coefficients: P(x)=f[x_0]+(x-x_0)\Big(f[x_0,x_1]+(x-x_1)\big(f[x_0,x_1,x_2]+(x-x_2)f[x_0,x_1,x_2,x_3]\big)\Big). At x^*=3, working from the innermost parenthesis outward: 1+(3-4)\cdot\tfrac14 = 0.75, \quad -2+(3-2)\cdot0.75=-1.25, \quad 3+(3-1)\cdot(-1.25)=0.5, matching P(3)=0.5 from the expanded formula exactly. This costs only 3 multiplications and 3 subtractions total. Compare that to expanding an nth-degree Newton form into standard form by hand first. That costs O(n^2) work, and only after it's done can you evaluate the result. (This cubic's own expansion above already took several lines of algebra by itself.) Evaluating straight from the table costs O(n) arithmetic operations for any degree n. Expanding first costs O(n^2) before a single value is even produced. The divided-difference-table widget above performs exactly this nested evaluation every time its "Evaluate at" box updates.

   Why: each step folds in one more node's information without disturbing what came before. That's exactly the property that lets you extend the table with a brand-new point. It costs one new diagonal, not a full restart.