Neville's Method

• The trouble with the standard Lagrangian polynomial technique is that we do not know which degree of polynomial to use.
  • If the degree is too low, the interpolating polynomial does not give good estimates of $f(x)$.
  • If the degree is too high, undesirable oscillations in polynomial values can occur.
• Neville's method can overcome this difficulty.
  • It computes the interpolated value with polynomials of successively higher degree,
  • stopping when the successive values are close together.
• The successive approximations are actually computed by linear interpolation from the previous values.
• The Lagrange formula for linear interpolation to get $f(x)$ from two data pairs, $(x_1,f_1)$ and $(x_2,f_2)$, is
  $$f(x)=\frac{(x-x_2)}{(x_1-x_2)}f_1+\frac{(x-x_1)}{(x_2-x_1)}f_2$$

• Neville's method begins by arranging the given data pairs, $(x_i,f_i)$.
• Such that the successive values are in order of the closeness of the $x_i$ to $x$.
• Suppose we are given
  these data
  

  x	f(x)
  10.1	0.17537
  22.2	0.37784
  32.0	0.52992
  41.6	0.66393
  50.5	0.63608

  and we want to interpolate for $x=27.5$.

  We first rearrange the data pairs in order of closeness to $x=27.5$:

  i	|x-x$_i$|	x$_i$	f$_i$=P$_{i0}$
  0	4.5	32.0	0.52992
  1	5.3	22.2	0.37784
  2	14.1	41.6	0.66393
  3	17.4	10.1	0.17537
  4	23.0	50.5	0.63608

  
  

• Neville's method begins by renaming the $f_i$ as $P_{i0}$.
• We build a table
  

  i	x	P$_{i0}$	P$_{i1}$	P$_{i2}$	P$_{i3}$	P$_{i4}$
  0	32.0	0.52992	0.46009	0.46200	0.46174	0.45754
  1	22.2	0.37784	0.45600	0.46071	0.47901
  2	41.6	0.66393	0.44524	0.55843
  3	10.1	0.17537	0.37379
  4	50.5	0.63608

  
  
• Thus, the value of $P_{01}$ is computed by
  $$f(x)=\frac{(27.5-x_1)}{(x_0-x_1)}*0.52992+\frac{(27.5-x_0)}{(x_1-x_0)}*0.37784$$
  substituting all;
  $$P_{01}=\frac{(27.5-22.2)}{(32.0-22.2)}*0.52992+\frac{(27.5-32.0)}{(22.2-32.0)}*0.37784=0.46009$$

• Once we have the column of $P_{i1}$'s, we compute the next column.
  $$P_{22}=\frac{(27.5-41.6)*0.37379+(50.5-27.5)*0.44524}{50.5-41.6}=0.55843$$

• The remaining columns are computed similarly.
• The general formula for computing entries into the table is
  $$\boxed{p_{i,j}=\frac{(x-x_i)*P_{i+1,j-1}+(x_{i+j}-x)*P_{i,j-1}}{x_{i+j}-x_i}}$$

• The top line of the table represents Lagrangian interpolates at $x=27.5$ using polynomials of degree equal to the second subscript of the $P's$.
  

  i	x	P$_{i0}$	P$_{i1}$	P$_{i2}$	P$_{i3}$	P$_{i4}$
  		0.52992	0.46009	0.46200	0.46174	0.45754

  
  
• The preceding data are for sines of angles in degrees and the correct value for $x=27.5$ is $0.46175$.