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{array}{cc}{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{array}$

and

$\begin{array}{cc}{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{array}$

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

$\begin{array}{cc}{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{array}$

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{array}{cc}{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\text{and}\end{array}$

$\begin{array}{cc}{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\end{array}$

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

$\begin{array}{cc}{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{array}$

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{array}{cc}{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{array}$

$\begin{array}{cc}{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},\text{and}\end{array}$

$\begin{array}{cc}{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{array}$

Step 3:

From these values we now find $P_{0,2}(5)$, and $P_{1,3}(5)$ and get

$\begin{array}{cc}{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}\text{and}\end{array}$

$\begin{array}{cc}{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{array}$.

Step 4:

Finally, we can find $P_{0,3}(5)$ to be

$\begin{array}{cc}{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{array}$

References

http://people.math.sfu.ca/~kevmitch/teaching/316-10.09/neville.pdf