Divided Differences

1. What?

   A recursive method definition used to successively generate the approximating
   polynomials.

2. Form of the Polynomial:
   
   • \[P_n(x) = a_0 + a_1(x − x_0) + a_2(x − x_0)(x − x_1) +···+ a_n(x − x_0)···(x − x_{n−1}),\ \ \ (3.5)\]

   • Evaluated at \(x_0\): \(\ P_n(x_0) = a_0 = f(x_0)\)

   • Evaluated at \(x_1\): \(\ P_n(x_1) = f(x_0) + a_1(x_1 − x_0) = f(x_1)\)

   • \(\implies \ \ \ \ \ \ \ \ a_1 = \dfrac{f(x_1) − f(x_0)}{x_1 − x_0}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (3.6)\).

3. The divided differences:
   
   • The zeroth divided difference of the function f with respect to \(x_i\):
     • Denoted: \(f[x_i]\)
     • Defined: as the value of \(f\) at \(x_i\)

     • \(f[x_i] = f(x_i) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (3.7)\).

   • The remaining divided differences are defined recursively.

   Recursive Divdided Differences

4. The Interpolating Polynomial:
   \(P_n(x) = f[x_0] + f[x_0, x_1](x − x_0) + a_2(x − x_0)(x − x_1)+···+ a_n(x − x_0)(x − x_1)···(x − x_{n−1})\)

5. Newton’s Divided Difference:
   \(P_n(x) = f[x_0]+ \sum^n_{k=1}f[x_0, x_1, ... , x_k](x-x_0)···(x − x_{k−1}) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (3.10)\)

   The value of \(f[x_0,x_1,...,x_k]\) is independent of the order of the numbers \(x_0, x_1, ... ,x_k\)

6. Generation of Divided Differences:
   Table
7. Algorithm:
   

Forward Differences

1. Forward Difference:
   
   • Check here
     
2. The divided differences (with del notation):
   
   and in general,
   

3. Newton Forward-Difference Formula:
   

   derivation

Backward Differences

1. Backward Difference:
   

2. The divided differences:
   

   
   and in general,
   

   Consequently, the Interpolating Polynomial
   

   If we extend the binomial coefficient notation to include all real values of s by letting
   
   then
   

3. Newton Backward–Difference Formula:
   

Centered Differences

1. What?

2. Why?

   The Newton forward- and backward-difference formulas are not appropriate for
   approximating \(f(x)\) when x lies near the center of the table because neither will permit the highest-order difference to have \(x_0\) close to x.

3. Stirling’s Formula:
   
   • If \(n = 2m + 1\) is odd:
   • If \(n = 2m\) is even: [we use the same formula but delete the last line] Formula

4. Table of Entries:
   Table

5. OMG:
   \(F_{i,j} = \dfrac{1}{x_{i} − x_{i-j}}[(F_{i,j-1} − F_{i-1,j-1})] \\ Q_{i,j} = \dfrac{1}{x_{i} − x_{i-j}}[Q_{i,j-1} − Q_{i-1,j-1}], \\\)