Jump to content

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

[edit | edit source]

Approximate the function f(x)=1x at 81 using x0=16, x1=64, and x2=100.

We begin by finding the value of the function at the given points, x0=16,x1=64, and x2=100. We obtain

f(x0)=f(16)=14=.25
f(x1)=f(64)=18=.125 and
f(x2)=f(100)=110=.1.

Since, we know from the Wikipedia page on Neville's Algorithm that Pi,i(x)=yi, the approximations for P0,0(81), P1,1(81) and P2,2(81) are

P0,0(81)=f(x0)=.25
P1,1(81)=f(x1)=.125 and
P2,2(81)=f(x2)=.1.

Using Neville's Algorithm we can now calculate P0,1(81) and P1,2(81). We find P0,1(81) and P1,2(81) to be

P0,1(81)=(x1−x)P0,0(x)+(x−x0)P1,1(x)x1−x0=(64−81)(.25)+(81−16)(.125)64−16=−4.25+.8.12548≈.080729

and

P1,2(81)=(x2−x)P1,1(x)+(x−x1)P2,2(x)x2−x1=(100−81)(.125)+(81−64)(.1)100−64=2.375+1.736≈.113194.

From these two values we now find P0,2(81) to be

P0,2(81)=(x2−x)P0,1(x)+(x−x0)P1,2(x)x2−x0=(100−81)(.080729)+(81−16)(.113194)100−16=1.533851+7.3576184≈.105851.

Thus, our approximation for the function f(x)=1x at 81 using x0=16,x1=64, and x2=100 is .105851. We know the actual value of the function evaluated at 81 is 181 or .11111.... Therefore, our approximation within .00526 of the actual value.

Example 2

[edit | edit source]

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(x0)=f(1)=−6
f(x1)=f(2)=2 and
f(x2)=f(4)=12.

Using Pi,i(x), the approximations for P0,0(3), P1,1(3) and P2,2(3) are

P0,0(3)=f(x0)=−6
P1,1(3)=f(x1)=2 and
P2,2(3)=f(x2)=12.

Using Neville's Algorithm we now calculate P0,1(3) and P1,2(3) to be equal to

P0,1(3)=(x1−x)P0,0(x)+(x−x0)P1,1(x)x1−x0=(2−3)(−6)+(3−1)(2)2−1=6+41=10and
P1,2(3)=(x2−x)P1,1(x)+(x−x1)P2,2(x)x2−x1=(4−3)(2)+(3−2)(12)4−2=2+122=7

From these two values we find P0,2(3) to be

P0,2(3)=(x2−x)P0,1(x)+(x−x0)P1,2(x)x2−x0=(4−3)(10)+(3−1)(7)4−1=10+143=243.

Exercise

[edit | edit source]

Try this one on your own before revealing the answer. You can reveal one step at a time.

Approximate the function f(x)=3x3−2x2−3x at 2 using x0=0,x1=1,x2=2,x3=3,x4=4, and x3=6.

References

[edit | edit source]

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