# 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}-3x}$  at ${\displaystyle 2}$  using ${\displaystyle x_{0}=0,x_{1}=1,x_{2}=2,x_{3}=3,x_{4}=4}$ , and ${\displaystyle x_{3}=6}$ .