# 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}-3x$ at $2$ using $x_{0}=0,x_{1}=1,x_{2}=2,x_{3}=3,x_{4}=4$, and $x_{3}=6$.
Solution:
Step 1:
We begin by evaluating the function at four given points and obtain
    $f(x_{0})=f(0)=3(0^{3})-2(0^{2})-{\sqrt {0}}+2=2$
    $f(x_{1})=f(1)=3(1^{3})-2(1^{2})-{\sqrt {1}}+2=2$
    $f(x_{2})=f(4)=3(4^{3})-2(4^{2})-{\sqrt {4}}+2=160$ and
    $f(x_{3})=f(9)=3(9^{3})-2(9^{2})-{\sqrt {9}}+2=2024$.
Thus, $P_{0,0}(5)=2,P_{1,1}(5)=2,P_{2,2}(5)=160$ and $P_{3,3}(5)=2024$.
Step 2:
We can calculate $P_{0,1}(5),P_{1,2}(5)$ and $P_{2,3}(5)$ to be
    ${\begin{aligned}P_{0,1}(5)&={\frac {(x_{1}-x)P_{0,0}(x)+(x-x_{0})P_{1,1}(x)}{x_{1}-x_{0}}}\\&={\frac {(1-5)(2)+(5-0)(2)}{1-0}}\\&={\frac {-8+10}{1}}=2\,,\end{aligned}}$
    ${\begin{aligned}P_{1,2}(5)&={\frac {(x_{2}-x)P_{1,1}(x)+(x-x_{1})P_{2,2}(x)}{x_{2}-x_{1}}}\\&={\frac {(4-5)(2)+(5-1)(160)}{4-1}}\\&={\frac {-2+640}{3}}={\frac {638}{3}}\,,\quad {\text{and}}\end{aligned}}$
    ${\begin{aligned}P_{2,3}(5)&={\frac {(x_{3}-x)P_{2,2}(x)+(x-x_{2})P_{3,3}(x)}{x_{3}-x_{2}}}\\&={\frac {(9-5)(160)+(5-4)(2024)}{9-4}}\\&={\frac {640+2024}{5}}={\frac {2664}{5}}\,.\end{aligned}}$
Step 3:
From these values we now find $P_{0,2}(5)$, and $P_{1,3}(5)$ and get
    ${\begin{aligned}P_{0,2}(5)&={\frac {(x_{2}-x)P_{0,1}(x)+(x-x_{0})P_{1,2}(x)}{x_{2}-x_{0}}}\\&={\frac {(4-5)(2)+(5-0)({\frac {638}{3}})}{4-0}}\\&={\frac {-2+{\frac {3190}{3}}}{4}}={\frac {796}{3}}\quad {\text{and}}\end{aligned}}$
    ${\begin{aligned}P_{1,3}(5)&={\frac {(x_{3}-x)P_{1,2}(x)+(x-x_{1})P_{2,3}(x)}{x_{3}-x_{1}}}\\&={\frac {(9-5)({\frac {638}{3}})+(5-1)({\frac {2664}{5}})}{9-1}}\\&={\frac {{\frac {2552}{3}}+{\frac {10656}{5}}}{8}}={\frac {5591}{15}}\,.\end{aligned}}$.
Step 4:
Finally, we can find $P_{0,3}(5)$ to be
    ${\begin{aligned}P_{0,3}(5)&={\frac {(x_{3}-x)P_{0,2}(x)+(x-x_{0})P_{1,3}(x)}{x_{3}-x_{0}}}\\&={\frac {(9-5)({\frac {796}{3}})+(5-0)({\frac {5591}{15}})}{9-0}}\\&={\frac {{\frac {3184}{3}}+{\frac {5591}{3}}}{9}}=325\,.\end{aligned}}$