# 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 $f(x)={\frac {1}{\sqrt {x}}}$ at $81$ using $x_{0}=16$ , $x_{1}=64$ , and $x_{2}=100$ .

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

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

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

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

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

{\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

{\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 $P_{0,2}(81)$ to be

{\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 $f(x)={\frac {1}{\sqrt {x}}}$ at $81$ using $x_{0}=16,x_{1}=64$ , and $x_{2}=100$ is $.105851$ . We know the actual value of the function evaluated at $81$ is ${\frac {1}{\sqrt {81}}}$ or $.11111...$ . Therefore, our approximation within $.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 $f(x)$ at $3$ . The given points are

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

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

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

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

{\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}} {\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 $P_{0,2}(3)$ to be

{\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 $f(x)=3x^{3}-2x^{2}-{\sqrt {x}}+2$ at $5$ using $x_{0}=0,x_{1}=1,x_{2}=4$ , and $x_{3}=9$ .