3.2/

Neville’s Method

1. What?
2. Why?
3. The lagrange Polynomial of the point \(x_{m_i}\):
   
4. Method to recursively generate Lagrange polynomial:
   
   • Method:
     The Kth Lagrange Poly that interpolates f at the (k+1) points \(x_0,x_1,..,x_k\):
   • Examples:

     \(P_{0,1} = \\ P_{1,2} = \\ P_{0,1,2} =\) __________________ \(P_{j,..,i} = \\ Q_{i,j} = \\ P_{i-j,..,i} = \\\)

   • Generated according to the following Table:
5. Notation and subscripts:
   

   • Proceeding down the table corresponds to

   • Proceeding to the right corresponds to

   • To avoid the multiple subscripts, we let \(Q_{i,j}\), for \(0 \leq j \leq i\) be:

   : \(Q_{i,j} =\)

6. Algorithm:
   
7. Stopping Criterion:
   
   • Criterion:
   • If the inequality is true, \(Q_{i,i}\) is
   • If the inequality is false,

3.3/

Divided Differences

1. What?
2. Form of the Polynomial:
   
   • \(P_n(x) =\)
     
     

   • Evaluated at \(x_0\):
     

   • Evaluated at \(x_1\):
     

   • \(\implies a_1 = \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \\).

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

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

   • The remaining divided differences are defined:

   • The first divided difference of \(f\) with respect to \(x_i\) and \(x_{i+1}\):
     • Denoted:
     • Defined:
   • The second divided difference of \(f\) with respect to \(x_i\), \(x_{i+1}\) and \(x_{i+2}\):
     • Denoted:
     • Defined:
   • The Kth divided difference of \(f\) with respect to \(x_i\), \(x_{i+1},...,x_{i+k-1},x_{i+k}\):
     • Denoted:
     • Defined:

   • The process ends with

   • The nth divided difference of \(f\) with respect to \(x_i\), \(x_{i+1},...,x_{i+k-1},x_{i+k}\):
     • Denoted:
     • Defined:

4. The Interpolating Polynomial:
   \(P_n(x) =\)

5. Newton’s Divided Difference:
   \(P_n(x) =\)
   
   

   The value of \(f[x_0,x_1,...,x_k]\) is

6. Generation of Divided Differences:
   
7. Algorithm:
   

Forward Differences

1. Forward Difference:
   
2. The divided differences (with del notation):
   

   \(f[x_0,x_{1}] = \\ f[x_0,x_{1},x_2] = \\\) and in general,
   \(\\ f[x_0,x_{1},...,x_{k-1},x_{k}] \\\)

3. Newton Forward-Difference Formula:
   

Backward Differences

1. Backward Difference:
   
2. The divided differences:
   

   and in general,

   Consequently, the Interpolating Polynomial \

   If we extend the binomial coefficient notation to

   then \

3. Newton Backward–Difference Formula:
   

Centered Differences

1. What?
2. Why?
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]
4. Table of Entries: