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 at using , , and .
We begin by finding the value of the function at the given points, , and . We obtain
- and
- .
Since, we know from the Wikipedia page on Neville's Algorithm that , the approximations for , and are
- and
- .
Using Neville's Algorithm we can now calculate and . We find and to be
and
From these two values we now find to be
Thus, our approximation for the function at using , and is . We know the actual value of the function evaluated at is or . Therefore, our approximation within 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 at . The given points are
- and
- .
Using , the approximations for , and are
- and
- .
Using Neville's Algorithm we now calculate and to be equal to
From these two values we find to be
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 at using , and .
Solution:
Step 1:
We begin by evaluating the function at four given points and obtain
- and
- .
Thus, and .
Step 2:
We can calculate and to be
Step 3:
From these values we now find , and and get
- .
Step 4:
Finally, we can find to be
References
[edit | edit source]http://people.math.sfu.ca/~kevmitch/teaching/316-10.09/neville.pdf