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
f
(
x
)
=
1
x
{\displaystyle f(x)={\frac {1}{\sqrt {x}}}}
at
81
{\displaystyle 81}
using
x
0
=
16
{\displaystyle x_{0}=16}
,
x
1
=
64
{\displaystyle x_{1}=64}
, and
x
2
=
100
{\displaystyle x_{2}=100}
.
We begin by finding the value of the function at the given points,
x
0
=
16
,
x
1
=
64
{\displaystyle x_{0}=16,x_{1}=64}
, and
x
2
=
100
{\displaystyle x_{2}=100}
. We obtain
f
(
x
0
)
=
f
(
16
)
=
1
4
=
.25
{\displaystyle f(x_{0})=f(16)={\frac {1}{4}}=.25}
f
(
x
1
)
=
f
(
64
)
=
1
8
=
.125
{\displaystyle f(x_{1})=f(64)={\frac {1}{8}}=.125}
and
f
(
x
2
)
=
f
(
100
)
=
1
10
=
.1
{\displaystyle 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
{\displaystyle P_{i,i}(x)=y_{i}}
, the approximations for
P
0
,
0
(
81
)
{\displaystyle P_{0,0}(81)}
,
P
1
,
1
(
81
)
{\displaystyle P_{1,1}(81)}
and
P
2
,
2
(
81
)
{\displaystyle P_{2,2}(81)}
are
P
0
,
0
(
81
)
=
f
(
x
0
)
=
.25
{\displaystyle P_{0,0}(81)=f(x_{0})=.25}
P
1
,
1
(
81
)
=
f
(
x
1
)
=
.125
{\displaystyle P_{1,1}(81)=f(x_{1})=.125}
and
P
2
,
2
(
81
)
=
f
(
x
2
)
=
.1
{\displaystyle P_{2,2}(81)=f(x_{2})=.1}
.
Using Neville's Algorithm we can now calculate
P
0
,
1
(
81
)
{\displaystyle P_{0,1}(81)}
and
P
1
,
2
(
81
)
{\displaystyle P_{1,2}(81)}
. We find
P
0
,
1
(
81
)
{\displaystyle P_{0,1}(81)}
and
P
1
,
2
(
81
)
{\displaystyle P_{1,2}(81)}
to be
P
0
,
1
(
81
)
=
(
x
1
−
x
)
P
0
,
0
(
x
)
+
(
x
−
x
0
)
P
1
,
1
(
x
)
x
1
−
x
0
=
(
64
−
81
)
(
.25
)
+
(
81
−
16
)
(
.125
)
64
−
16
=
−
4.25
+
.8
.125
48
≈
.080729
{\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}}}
and
P
1
,
2
(
81
)
=
(
x
2
−
x
)
P
1
,
1
(
x
)
+
(
x
−
x
1
)
P
2
,
2
(
x
)
x
2
−
x
1
=
(
100
−
81
)
(
.125
)
+
(
81
−
64
)
(
.1
)
100
−
64
=
2.375
+
1.7
36
≈
.113194
.
{\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}}}
From these two values we now find
P
0
,
2
(
81
)
{\displaystyle P_{0,2}(81)}
to be
P
0
,
2
(
81
)
=
(
x
2
−
x
)
P
0
,
1
(
x
)
+
(
x
−
x
0
)
P
1
,
2
(
x
)
x
2
−
x
0
=
(
100
−
81
)
(
.080729
)
+
(
81
−
16
)
(
.113194
)
100
−
16
=
1.533851
+
7.35761
84
≈
.105851
.
{\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}}}
Thus, our approximation for the function
f
(
x
)
=
1
x
{\displaystyle f(x)={\frac {1}{\sqrt {x}}}}
at
81
{\displaystyle 81}
using
x
0
=
16
,
x
1
=
64
{\displaystyle x_{0}=16,x_{1}=64}
, and
x
2
=
100
{\displaystyle x_{2}=100}
is
.105851
{\displaystyle .105851}
. We know the actual value of the function evaluated at
81
{\displaystyle 81}
is
1
81
{\displaystyle {\frac {1}{\sqrt {81}}}}
or
.11111
.
.
.
{\displaystyle .11111...}
. Therefore, our approximation within
.00526
{\displaystyle .00526}
of the actual value.
For this example, we will use the points given in the example of Newton form to approximate the function
f
(
x
)
{\displaystyle f(x)}
at
3
{\displaystyle 3}
. The given points are
f
(
x
0
)
=
f
(
1
)
=
−
6
{\displaystyle f(x_{0})=f(1)=-6}
f
(
x
1
)
=
f
(
2
)
=
2
{\displaystyle f(x_{1})=f(2)=2}
and
f
(
x
2
)
=
f
(
4
)
=
12
{\displaystyle f(x_{2})=f(4)=12}
.
Using
P
i
,
i
(
x
)
{\displaystyle P_{i,i}(x)}
, the approximations for
P
0
,
0
(
3
)
{\displaystyle P_{0,0}(3)}
,
P
1
,
1
(
3
)
{\displaystyle P_{1,1}(3)}
and
P
2
,
2
(
3
)
{\displaystyle P_{2,2}(3)}
are
P
0
,
0
(
3
)
=
f
(
x
0
)
=
−
6
{\displaystyle P_{0,0}(3)=f(x_{0})=-6}
P
1
,
1
(
3
)
=
f
(
x
1
)
=
2
{\displaystyle P_{1,1}(3)=f(x_{1})=2}
and
P
2
,
2
(
3
)
=
f
(
x
2
)
=
12
{\displaystyle P_{2,2}(3)=f(x_{2})=12}
.
Using Neville's Algorithm we now calculate
P
0
,
1
(
3
)
{\displaystyle P_{0,1}(3)}
and
P
1
,
2
(
3
)
{\displaystyle P_{1,2}(3)}
to be equal to
P
0
,
1
(
3
)
=
(
x
1
−
x
)
P
0
,
0
(
x
)
+
(
x
−
x
0
)
P
1
,
1
(
x
)
x
1
−
x
0
=
(
2
−
3
)
(
−
6
)
+
(
3
−
1
)
(
2
)
2
−
1
=
6
+
4
1
=
10
and
{\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}}}
P
1
,
2
(
3
)
=
(
x
2
−
x
)
P
1
,
1
(
x
)
+
(
x
−
x
1
)
P
2
,
2
(
x
)
x
2
−
x
1
=
(
4
−
3
)
(
2
)
+
(
3
−
2
)
(
12
)
4
−
2
=
2
+
12
2
=
7
{\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}}}
From these two values we find
P
0
,
2
(
3
)
{\displaystyle P_{0,2}(3)}
to be
P
0
,
2
(
3
)
=
(
x
2
−
x
)
P
0
,
1
(
x
)
+
(
x
−
x
0
)
P
1
,
2
(
x
)
x
2
−
x
0
=
(
4
−
3
)
(
10
)
+
(
3
−
1
)
(
7
)
4
−
1
=
10
+
14
3
=
24
3
.
{\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}}}
Try this one on your own before revealing the answer. You can reveal one step at a time.
Approximate the function
f
(
x
)
=
3
x
3
−
2
x
2
−
3
x
{\displaystyle f(x)=3x^{3}-2x^{2}-3x}
at
2
{\displaystyle 2}
using
x
0
=
0
,
x
1
=
1
,
x
2
=
2
,
x
3
=
3
,
x
4
=
4
{\displaystyle x_{0}=0,x_{1}=1,x_{2}=2,x_{3}=3,x_{4}=4}
, and
x
3
=
6
{\displaystyle x_{3}=6}
.
We begin by evaluating the function at four given points and obtain
f
(
x
0
)
=
f
(
0
)
=
3
(
0
3
)
−
2
(
0
2
)
−
0
+
2
=
2
{\displaystyle 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
)
−
1
+
2
=
2
{\displaystyle 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
)
−
4
+
2
=
160
{\displaystyle 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
)
−
9
+
2
=
2024
{\displaystyle 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
{\displaystyle P_{0,0}(5)=2,P_{1,1}(5)=2,P_{2,2}(5)=160}
and
P
3
,
3
(
5
)
=
2024
{\displaystyle P_{3,3}(5)=2024}
.
We can calculate
P
0
,
1
(
5
)
,
P
1
,
2
(
5
)
{\displaystyle P_{0,1}(5),P_{1,2}(5)}
and
P
2
,
3
(
5
)
{\displaystyle P_{2,3}(5)}
to be
P
0
,
1
(
5
)
=
(
x
1
−
x
)
P
0
,
0
(
x
)
+
(
x
−
x
0
)
P
1
,
1
(
x
)
x
1
−
x
0
=
(
1
−
5
)
(
2
)
+
(
5
−
0
)
(
2
)
1
−
0
=
−
8
+
10
1
=
2
,
{\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}}}
P
1
,
2
(
5
)
=
(
x
2
−
x
)
P
1
,
1
(
x
)
+
(
x
−
x
1
)
P
2
,
2
(
x
)
x
2
−
x
1
=
(
4
−
5
)
(
2
)
+
(
5
−
1
)
(
160
)
4
−
1
=
−
2
+
640
3
=
638
3
,
and
{\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}}}
P
2
,
3
(
5
)
=
(
x
3
−
x
)
P
2
,
2
(
x
)
+
(
x
−
x
2
)
P
3
,
3
(
x
)
x
3
−
x
2
=
(
9
−
5
)
(
160
)
+
(
5
−
4
)
(
2024
)
9
−
4
=
640
+
2024
5
=
2664
5
.
{\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}}}
From these values we now find
P
0
,
2
(
5
)
{\displaystyle P_{0,2}(5)}
, and
P
1
,
3
(
5
)
{\displaystyle P_{1,3}(5)}
and get
P
0
,
2
(
5
)
=
(
x
2
−
x
)
P
0
,
1
(
x
)
+
(
x
−
x
0
)
P
1
,
2
(
x
)
x
2
−
x
0
=
(
4
−
5
)
(
2
)
+
(
5
−
0
)
(
638
3
)
4
−
0
=
−
2
+
3190
3
4
=
796
3
and
{\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}}}
P
1
,
3
(
5
)
=
(
x
3
−
x
)
P
1
,
2
(
x
)
+
(
x
−
x
1
)
P
2
,
3
(
x
)
x
3
−
x
1
=
(
9
−
5
)
(
638
3
)
+
(
5
−
1
)
(
2664
5
)
9
−
1
=
2552
3
+
10656
5
8
=
5591
15
.
{\displaystyle {\begin{aligned}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{aligned}}}
.
Finally, we can find
P
0
,
3
(
5
)
{\displaystyle P_{0,3}(5)}
to be
P
0
,
3
(
5
)
=
(
x
3
−
x
)
P
0
,
2
(
x
)
+
(
x
−
x
0
)
P
1
,
3
(
x
)
x
3
−
x
0
=
(
9
−
5
)
(
796
3
)
+
(
5
−
0
)
(
5591
15
)
9
−
0
=
3184
3
+
5591
3
9
=
325
.
{\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}}}