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)$, so the successive values are in order of the closeness of the $x_i$ to $x$.
• Suppose we are given these data
  $$\begin{array}{rr} x & f(x) \hline 10.1 & 0.17537 \\ 22.2... ...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} i & \vert x-x_i\vert & x_i & f_i=P_{i0} ... ...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} i & x & P_{i0} & P_{i1} & P_{i2} & P_... ...7379 & & & \\ 4 & 50.5 & 0.63608 & & & & \hline \end{array}$$
  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}$$
  Thus, the value of $P_{01}$ is computed by '
  $$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 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$.
• The preceding data are for sines of angles in degrees and the correct value for $x=27.5$ is $0.46175$.