GuideInterpolationintermediate

Newton interpolation and divided differences

The Newton polynomial built in layers with divided differences: linear, quadratic and general form, the difference table, the error and a worked example with real data.

The idea: a polynomial in layers

Newton writes the polynomial so that each new node adds one term without forcing a rebuild of the previous work. Instead of the power basis, it uses a basis of accumulated products:

pn(x)=b0+b1(x−x0)+b2(x−x0)(x−x1)+⋯+bn(x−x0)⋯(x−xn−1)p_n(x)=b_0+b_1(x-x_0)+b_2(x-x_0)(x-x_1)+\cdots+b_n(x-x_0)\cdots(x-x_{n-1})

The coefficients bib_i are the divided differences of order ii. The linear form (two points) fixes the idea:

p1(x)=f(x0)+f(x1)−f(x0)x1−x0⏟f[x1,x0](x−x0)p_1(x)=f(x_0)+\underbrace{\frac{f(x_1)-f(x_0)}{x_1-x_0}}_{f[x_1,x_0]}(x-x_0)

Divided differences

In practice you fill a triangular table: the first column is the f(xi)f(x_i), the second the first-order differences, and so on. The polynomial coefficients are the upper diagonal.

Error of the Newton polynomial

Worked example

ExamplePopulation census (degree 4)

With Spain's population data (millions) in 1971, 1981, 1991, 2001 and 2011 (33.956, 37.743, 39.434, 40.847 and 46.816), estimate the 2005 population with the highest-degree Newton polynomial.

  1. With 5 data points the degree is 4. Compute the divided differences (the upper diagonal of the table):

    f[x0]=33.956f[x1,x0]=0.3787f[x2,x1,x0]=−0.01048f[x3,…,x0]=0.000303f[x4,…,x0]=0.0000127\begin{aligned} f[x_0]&=33.956\\ f[x_1,x_0]&=0.3787\\ f[x_2,x_1,x_0]&=-0.01048\\ f[x_3,\dots,x_0]&=0.000303\\ f[x_4,\dots,x_0]&=0.0000127 \end{aligned}

  2. Assemble the Newton polynomial with those coefficients:

    p4(x)= 33.956+0.3787 (x−1971)−0.01048 (x−1971)(x−1981)+0.000303 (x−1971)(x−1981)(x−1991)+0.0000127 (x−1971)(x−1981)(x−1991)(x−2001)\begin{aligned} p_4(x)=\ &33.956+0.3787\,(x-1971)\\ &-0.01048\,(x-1971)(x-1981)\\ &+0.000303\,(x-1971)(x-1981)(x-1991)\\ &+0.0000127\,(x-1971)(x-1981)(x-1991)(x-2001) \end{aligned}

Evaluating at 2005 gives the estimate:

p4(2005)≈42.315 millonesp_4(2005)\approx 42.315\ \text{millones}

Derivation of divided differences

DerivationDerivation: Newton coefficients via divided differencesView as its own page →

  1. Start from the linear form p1(x)=b0+b1(x−x0)p_1(x)=b_0+b_1(x-x_0) and require it to pass through (x0,f(x0))(x_0,f(x_0)) and (x1,f(x1))(x_1,f(x_1)):

    {p1(x0)=f(x0)=b0p1(x1)=f(x1)=b0+b1(x1−x0)\begin{cases} p_1(x_0)=f(x_0)=b_0\\ p_1(x_1)=f(x_1)=b_0+b_1(x_1-x_0) \end{cases}

  2. From the first equation b0=f(x0)b_0=f(x_0). Substituting into the second and solving for b1b_1:

    b1=f(x1)−f(x0)x1−x0=f[x1,x0]b_1=\frac{f(x_1)-f(x_0)}{x_1-x_0}=f[x_1,x_0]

b1b_1 is called the first-order divided difference. Repeating the same argument with three points gives the second-order difference, and so we reach the general recursion.

f[xn,…,x0]=f[xn,…,x1]−f[xn−1,…,x0]xn−x0f[x_n,\dots,x_0]=\frac{f[x_n,\dots,x_1]-f[x_{n-1},\dots,x_0]}{x_n-x_0}