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.
Approximate the function
at
using
,
, and
.
We begin by finding the value of the function at the given points,
, and
. We obtain
![{\displaystyle f(x_{0})=f(16)={\frac {1}{4}}=.25}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fefa6b29534aab4d36aacf70ed6fefaf232ca8b9)
and
.
Since, we know from the Wikipedia page on Neville's Algorithm that
, the approximations for
,
and
are
![{\displaystyle P_{0,0}(81)=f(x_{0})=.25}](https://wikimedia.org/api/rest_v1/media/math/render/svg/82d9d772df106bc0eb807eb6fb7892899207cfe8)
and
.
Using Neville's Algorithm we can now calculate
and
. We find
and
to be
![{\displaystyle {\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d5eac0484e086a4b7ac1edae61c0f58031334897)
and
![{\displaystyle {\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/388b47ff85d648586fb61dcee814c8d11dc625b1)
From these two values we now find
to be
![{\displaystyle {\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0bb170d40383b4dd900285fadacede6d110643a1)
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.
For this example, we will use the points given in the example of Newton form to approximate the function
at
. The given points are
![{\displaystyle f(x_{0})=f(1)=-6}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8487eff177721214e5e930dc40960e8fe0c1c7f3)
and
.
Using
, the approximations for
,
and
are
![{\displaystyle P_{0,0}(3)=f(x_{0})=-6}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b0b09463b95a118b3f242706d3978bfda8d253f7)
and
.
Using Neville's Algorithm we now calculate
and
to be equal to
![{\displaystyle {\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d428f022f895dd5fa22fd8115c25d34066742e4f)
![{\displaystyle {\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/330642015e25fa4d91a4baa0d873aa8a87174e7c)
From these two values we find
to be
![{\displaystyle {\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0841a9ec7490d5c1624cc9b64d0e84749d6492a4)
Try this one on your own before revealing the answer. You can reveal one step at a time.
Approximate the function
at
using
, and
.
We begin by evaluating the function at four given points and obtain
![{\displaystyle f(x_{0})=f(0)=3(0^{3})-2(0^{2})-{\sqrt {0}}+2=2}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c97d27f7f85c1aa2ee2780f8db43e471796ee546)
![{\displaystyle f(x_{1})=f(1)=3(1^{3})-2(1^{2})-{\sqrt {1}}+2=2}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e6f6ad6e4045668313737ad3d1c5b615d9432dbe)
and
.
Thus,
and
.
We can calculate
and
to be
![{\displaystyle {\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/23481e14b294c26bc40fe0fdbbacc99c35deab6d)
![{\displaystyle {\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/dcdb47457444e750f74dc3913f03d9457b2b3d1c)
![{\displaystyle {\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6a7888780e1994fc68485596d7f5e1e695773a4c)
From these values we now find
, and
and get
![{\displaystyle {\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ccb9660065373921a29a6f78c62fc3a84e9cf9c9)
.
Finally, we can find
to be
![{\displaystyle {\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9f867e15aaaaab5aa2b0a6812d14452e2f6b44cf)
http://people.math.sfu.ca/~kevmitch/teaching/316-10.09/neville.pdf