Numerical Analysis/Neville's algorithm examples

< Numerical Analysis

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{align}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{align}

and

\begin{align}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{align}

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

\begin{align}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{align}

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{align}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{align}

\begin{align}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-1}\\ &= \frac{2+12}{3}\\ &= \frac{14}{3}\,.\end{align}

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

\begin{align}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)(\frac{14}{3})}{4-1}\\ &= \frac{10+\frac{28}{3}}{3}\\ &= \frac{58}{9}\,.\end{align}

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$ .

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{align}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{align}

\begin{align}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{align}

\begin{align}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{align}

Step 3:

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

\begin{align}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{align}

\begin{align}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{align}

Step 4:

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

\begin{align}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{align}

References

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

This article is issued from Wikiversity - version of the Saturday, April 02, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.