# Numerical Analysis/Neville's algorithm examples

The main idea of Neville's Algorithm is to approximate the value of a polynomial at a particular point without having to first find all of the coefficients of the polynomial. The following examples and exercise illustrate how to use this method.

## Example 1

Approximate the function ${\displaystyle f(x)={\frac {1}{\sqrt {x}}}}$ at ${\displaystyle 81}$ using ${\displaystyle x_{0}=16}$, ${\displaystyle x_{1}=64}$, and ${\displaystyle x_{2}=100}$.

We begin by finding the value of the function at the given points, ${\displaystyle x_{0}=16,x_{1}=64}$, and ${\displaystyle x_{2}=100}$. We obtain

${\displaystyle f(x_{0})=f(16)={\frac {1}{4}}=.25}$
${\displaystyle f(x_{1})=f(64)={\frac {1}{8}}=.125}$ and
${\displaystyle f(x_{2})=f(100)={\frac {1}{10}}=.1}$.

Since, we know from the Wikipedia page on Neville's Algorithm that ${\displaystyle P_{i,i}(x)=y_{i}}$, the approximations for ${\displaystyle P_{0,0}(81)}$, ${\displaystyle P_{1,1}(81)}$ and ${\displaystyle P_{2,2}(81)}$ are

${\displaystyle P_{0,0}(81)=f(x_{0})=.25}$
${\displaystyle P_{1,1}(81)=f(x_{1})=.125}$ and
${\displaystyle P_{2,2}(81)=f(x_{2})=.1}$.

Using Neville's Algorithm we can now calculate ${\displaystyle P_{0,1}(81)}$ and ${\displaystyle P_{1,2}(81)}$. We find ${\displaystyle P_{0,1}(81)}$ and ${\displaystyle P_{1,2}(81)}$ to be

{\displaystyle {\begin{aligned}P_{0,1}(81)&={\frac {(x_{1}-x)P_{0,0}(x)+(x-x_{0})P_{1,1}(x)}{x_{1}-x_{0}}}\\&={\frac {(64-81)(.25)+(81-16)(.125)}{64-16}}\\&={\frac {-4.25+.8.125}{48}}\\&\approx .080729\end{aligned}}}

and

{\displaystyle {\begin{aligned}P_{1,2}(81)&={\frac {(x_{2}-x)P_{1,1}(x)+(x-x_{1})P_{2,2}(x)}{x_{2}-x_{1}}}\\&={\frac {(100-81)(.125)+(81-64)(.1)}{100-64}}\\&={\frac {2.375+1.7}{36}}\\&\approx .113194\,.\end{aligned}}}

From these two values we now find ${\displaystyle P_{0,2}(81)}$ to be

{\displaystyle {\begin{aligned}P_{0,2}(81)&={\frac {(x_{2}-x)P_{0,1}(x)+(x-x_{0})P_{1,2}(x)}{x_{2}-x_{0}}}\\&={\frac {(100-81)(.080729)+(81-16)(.113194)}{100-16}}\\&={\frac {1.533851+7.35761}{84}}\\&\approx .105851\,.\end{aligned}}}

Thus, our approximation for the function ${\displaystyle f(x)={\frac {1}{\sqrt {x}}}}$ at ${\displaystyle 81}$ using ${\displaystyle x_{0}=16,x_{1}=64}$, and ${\displaystyle x_{2}=100}$ is ${\displaystyle .105851}$. We know the actual value of the function evaluated at ${\displaystyle 81}$ is ${\displaystyle {\frac {1}{\sqrt {81}}}}$ or ${\displaystyle .11111...}$. Therefore, our approximation within ${\displaystyle .00526}$ of the actual value.

## Example 2

For this example, we will use the points given in the example of Newton form to approximate the function ${\displaystyle f(x)}$ at ${\displaystyle 3}$. The given points are

${\displaystyle f(x_{0})=f(1)=-6}$
${\displaystyle f(x_{1})=f(2)=2}$ and
${\displaystyle f(x_{2})=f(4)=12}$.

Using ${\displaystyle P_{i,i}(x)}$, the approximations for ${\displaystyle P_{0,0}(3)}$, ${\displaystyle P_{1,1}(3)}$ and ${\displaystyle P_{2,2}(3)}$ are

${\displaystyle P_{0,0}(3)=f(x_{0})=-6}$
${\displaystyle P_{1,1}(3)=f(x_{1})=2}$ and
${\displaystyle P_{2,2}(3)=f(x_{2})=12}$.

Using Neville's Algorithm we now calculate ${\displaystyle P_{0,1}(3)}$ and ${\displaystyle P_{1,2}(3)}$ to be equal to

{\displaystyle {\begin{aligned}P_{0,1}(3)&={\frac {(x_{1}-x)P_{0,0}(x)+(x-x_{0})P_{1,1}(x)}{x_{1}-x_{0}}}\\&={\frac {(2-3)(-6)+(3-1)(2)}{2-1}}\\&={\frac {6+4}{1}}\\&=10\quad {\text{and}}\end{aligned}}}
{\displaystyle {\begin{aligned}P_{1,2}(3)&={\frac {(x_{2}-x)P_{1,1}(x)+(x-x_{1})P_{2,2}(x)}{x_{2}-x_{1}}}\\&={\frac {(4-3)(2)+(3-2)(12)}{4-2}}\\&={\frac {2+12}{2}}\\&=7\quad \end{aligned}}}

From these two values we find ${\displaystyle P_{0,2}(3)}$ to be

{\displaystyle {\begin{aligned}P_{0,2}(3)&={\frac {(x_{2}-x)P_{0,1}(x)+(x-x_{0})P_{1,2}(x)}{x_{2}-x_{0}}}\\&={\frac {(4-3)(10)+(3-1)(7)}{4-1}}\\&={\frac {10+14}{3}}\\&={\frac {24}{3}}\,.\end{aligned}}}

## Exercise

Try this one on your own before revealing the answer. You can reveal one step at a time.

Approximate the function ${\displaystyle f(x)=3x^{3}-2x^{2}-{\sqrt {x}}+2}$ at ${\displaystyle 5}$ using ${\displaystyle x_{0}=0,x_{1}=1,x_{2}=4}$, and ${\displaystyle x_{3}=9}$.