DerivationInterpolationintermediate

Derivation: Newton coefficients via divided differences

Where b0b_0 and b1b_1 come from when forcing the polynomial through the points, and how the recursion generates every higher-order coefficient.

Forcing it through two points

  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}