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
  $$\begin{array}{rr}\hline x & f(x) \hline 10.1 & 0.17537 \\... ...992 \\ 41.6 & 0.66393 \\ 50.5 & 0.63608 \hline \end{array}$$
  and we want to interpolate for $x=27.5$.

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

  $$\begin{array}{rrrr} \hline i & \vert x-x_i\vert & x_i & f_i... ...1 & 0.17537 \\ 4 & 23.0 & 50.5 & 0.63608 \hline \end{array}$$

• Neville's method begins by renaming the $f_i$ as $P_{i0}$.
• We build a table
  $$\begin{array}{rrrrrrr} \hline i & x & P_{i0} & P_{i1} & P_{i... ...7379 & & & \\ 4 & 50.5 & 0.63608 & & & & \hline \end{array}$$

• 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-32.0)*0.37784+(22.2-27.5)*0.52992}{22.2-32.0}=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
  $$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$.
  $$\begin{array}{rrrrrrr} \hline i & x & P_{i0} & P_{i1} & P_{i... ... 0.52992 & 0.46009 & 0.46200 & 0.46174 & 0.45754\\ \end{array}$$

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