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
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.
Example 2
edit
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}}} Exercise
edit
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}}}
References
edit