Namespaces
Variants
Actions

Difference between revisions of "Newton interpolation formula"

From Encyclopedia of Mathematics
Jump to: navigation, search
m (link)
m (tex encoded by computer)
Line 1: Line 1:
 +
<!--
 +
n0665301.png
 +
$#A+1 = 31 n = 0
 +
$#C+1 = 31 : ~/encyclopedia/old_files/data/N066/N.0606530 Newton interpolation formula
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
 +
 +
{{TEX|auto}}
 +
{{TEX|done}}
 +
 
A form of writing the [[Lagrange interpolation formula|Lagrange interpolation formula]] by using [[divided difference]]s:
 
A form of writing the [[Lagrange interpolation formula|Lagrange interpolation formula]] by using [[divided difference]]s:
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066530/n0665301.png" /></td> <td valign="top" style="width:5%;text-align:right;">(1)</td></tr></table>
+
$$ \tag{1 }
 +
L _ {n} ( x)  = \
 +
f ( x _ {0} ) +
 +
( x - x _ {0} ) f ( x _ {0} ; x _ {1} ) + \dots +
 +
$$
 +
 
 +
$$
 +
+
 +
( x - x _ {0} ) \dots ( x - x _ {n - 1 }  ) f ( x _ {0} ; \dots ; x _ {n} ),
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066530/n0665302.png" /></td> </tr></table>
+
where  $  f ( x _ {0} ; \dots ; x _ {k} ) $
 +
are the divided differences of order  $  k $;  
 +
it was treated by I. Newton in 1687. Formula (1) is called Newton's interpolation formula for unequal differences. When the  $  x _ {i} $
 +
are equidistant, that is, if
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066530/n0665303.png" /> are the divided differences of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066530/n0665304.png" />; it was treated by I. Newton in 1687. Formula (1) is called Newton's interpolation formula for unequal differences. When the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066530/n0665305.png" /> are equidistant, that is, if
+
$$
 +
x _ {1} - x _ {0}  = \dots = x _ {n} - x _ {n - 1 = h,
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066530/n0665306.png" /></td> </tr></table>
+
then by introducing the notation  $  ( x - x _ {0} )/h = t $
 +
and expressing the divided differences  $  f ( x _ {0} ; \dots ; x _ {k} ) $
 +
in terms of the finite differences  $  f _ {k/2} ^ { k } $
 +
according to the formula
  
then by introducing the notation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066530/n0665307.png" /> and expressing the divided differences <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066530/n0665308.png" /> in terms of the finite differences <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066530/n0665309.png" /> according to the formula
+
$$
 +
f ( x _ {0} ; \dots ; x _ {k} )  = \
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066530/n06653010.png" /></td> </tr></table>
+
\frac{f _ {k/2} ^ { k } }{h  ^ {k} k! }
 +
,\ \
 +
k = 0 \dots n,
 +
$$
  
one obtains a way of writing the polynomial <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066530/n06653011.png" /> in the form
+
one obtains a way of writing the polynomial $  L _ {n} ( x) $
 +
in the form
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066530/n06653012.png" /></td> <td valign="top" style="width:5%;text-align:right;">(2)</td></tr></table>
+
$$ \tag{2 }
 +
L _ {n} ( x)  = \
 +
L _ {n} ( x _ {0} + th) =
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066530/n06653013.png" /></td> </tr></table>
+
$$
 +
= \
 +
f _ {0} + tf _ {1/2} ^ { 1 } +
 +
\frac{t ( t - 1) }{2! }
 +
f _ {1} ^ { 2 } + \dots +
 +
\frac{t ( t - 1) \dots ( t - n + 1) }{n! }
 +
f _ {n/2} ^ { n } ,
 +
$$
  
which is called Newton's interpolation formula for forward interpolation. If the same change of variables is made in the interpolation polynomial <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066530/n06653014.png" /> with nodes <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066530/n06653015.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066530/n06653016.png" />,
+
which is called Newton's interpolation formula for forward interpolation. If the same change of variables is made in the interpolation polynomial $  L _ {n} $
 +
with nodes $  x _ {0} , x _ {-} 1 \dots x _ {-} n $,  
 +
where $  x _ {-} k = x _ {0} - kh $,
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066530/n06653017.png" /></td> </tr></table>
+
$$
 +
L _ {n} ( x)  = \
 +
f ( x _ {0} ) +
 +
( x - x _ {0} ) f ( x _ {0} ; x _ {-} 1 ) + \dots +
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066530/n06653018.png" /></td> </tr></table>
+
$$
 +
+
 +
( x - x _ {0} ) \dots ( x - x _ {- n + 1 }  ) f ( x _ {0} ; \dots ; x _ {-} n ),
 +
$$
  
 
then one obtains Newton's interpolation formula for backward interpolation:
 
then one obtains Newton's interpolation formula for backward interpolation:
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066530/n06653019.png" /></td> <td valign="top" style="width:5%;text-align:right;">(3)</td></tr></table>
+
$$ \tag{3 }
 +
L _ {n} ( x)  = L _ {n} ( x _ {0} + th) =
 +
$$
 +
 
 +
$$
 +
= \
 +
f _ {0} + tf _ {-} 1/2 ^ { 1 } +
 +
\frac{t ( t + 1) }{2! }
 +
f _ {-} 1 ^ { 2 } + \dots +
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066530/n06653020.png" /></td> </tr></table>
+
$$
 +
+
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066530/n06653021.png" /></td> </tr></table>
+
\frac{t ( t + 1) \dots ( t + n - 1) }{n! }
 +
f _ {-} n/2 ^ { n } .
 +
$$
  
Formulas (2) and (3) are convenient for computing tables of a given function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066530/n06653022.png" /> if the point <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066530/n06653023.png" /> is at the beginning or the end of the table, since in this case the addition of one or several nodes caused by the wish to increase the accuracy of the approximation does not lead to a repetition of the whole work done as in computations with Lagrange's formula.
+
Formulas (2) and (3) are convenient for computing tables of a given function $  f ( x) $
 +
if the point $  x $
 +
is at the beginning or the end of the table, since in this case the addition of one or several nodes caused by the wish to increase the accuracy of the approximation does not lead to a repetition of the whole work done as in computations with Lagrange's formula.
  
 
====References====
 
====References====
 
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  I.S. Berezin,  N.P. Zhidkov,  "Computing methods" , '''1''' , Pergamon  (1973)  (Translated from Russian)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  N.S. Bakhvalov,  "Numerical methods: analysis, algebra, ordinary differential equations" , MIR  (1977)  (Translated from Russian)</TD></TR></table>
 
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  I.S. Berezin,  N.P. Zhidkov,  "Computing methods" , '''1''' , Pergamon  (1973)  (Translated from Russian)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  N.S. Bakhvalov,  "Numerical methods: analysis, algebra, ordinary differential equations" , MIR  (1977)  (Translated from Russian)</TD></TR></table>
  
 +
====Comments====
 +
The divided differences  $  f ( x _ {0} ;  x _ {1} ) \dots f ( x _ {0} ; \dots ; x _ {n} ) $
 +
are defined by:
  
 +
$$
 +
f ( x _ {0} ;  x _ {1} )  = \
  
====Comments====
+
\frac{f ( x _ {1} ) - f ( x _ {0} ) }{x _ {1} - x _ {0} }
The divided differences <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066530/n06653024.png" /> are defined by:
+
,
 
+
$$
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066530/n06653025.png" /></td> </tr></table>
 
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066530/n06653026.png" /></td> </tr></table>
+
$$
 +
f ( x _ {0} ;  x _ {1} ; x _ {2} )  =
 +
\frac{1}{x _ {2} -
 +
x _ {1} }
 +
\left (
 +
\frac{f ( x _ {2} ) - f ( x _ {0} )
 +
}{x _ {2} - x _ {0} }
 +
-
 +
\frac{f ( x _ {1} ) -
 +
f ( x _ {0} ) }{x _ {1} - x _ {0} }
 +
\right ) ,
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066530/n06653027.png" /></td> </tr></table>
+
$$
 +
{\dots \dots \dots \dots }
 +
$$
  
 
or
 
or
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066530/n06653028.png" /></td> </tr></table>
+
$$
 +
f ( x _ {0} ; \dots ; x _ {n} )  = \
 +
\sum _ { i= } 0 ^ { n }  \prod _ { j= } 0 ^ { n }  {}  ^  \prime
 +
 
 +
\frac{f ( x _ {i} ) }{x _ {i} - x _ {j} }
 +
,
 +
$$
  
where the prime in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066530/n06653029.png" /> means that the factor <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066530/n06653030.png" /> is to be omitted. Formula (1) is also known as the finite Newton series for a function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066530/n06653031.png" />.
+
where the prime in $  \prod  ^  \prime  $
 +
means that the factor $  1/ ( x _ {i} - x _ {i} ) $
 +
is to be omitted. Formula (1) is also known as the finite Newton series for a function $  f $.
  
 
====References====
 
====References====
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  K.E. Atkinson,  "An introduction to numerical analysis" , Wiley  (1978)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  P.J. Davis,  "Interpolation and approximation" , Dover, reprint  (1975)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  F.B. Hildebrand,  "Introduction to numerical analysis" , McGraw-Hill  (1974)</TD></TR></table>
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  K.E. Atkinson,  "An introduction to numerical analysis" , Wiley  (1978)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  P.J. Davis,  "Interpolation and approximation" , Dover, reprint  (1975)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  F.B. Hildebrand,  "Introduction to numerical analysis" , McGraw-Hill  (1974)</TD></TR></table>

Revision as of 08:02, 6 June 2020


A form of writing the Lagrange interpolation formula by using divided differences:

$$ \tag{1 } L _ {n} ( x) = \ f ( x _ {0} ) + ( x - x _ {0} ) f ( x _ {0} ; x _ {1} ) + \dots + $$

$$ + ( x - x _ {0} ) \dots ( x - x _ {n - 1 } ) f ( x _ {0} ; \dots ; x _ {n} ), $$

where $ f ( x _ {0} ; \dots ; x _ {k} ) $ are the divided differences of order $ k $; it was treated by I. Newton in 1687. Formula (1) is called Newton's interpolation formula for unequal differences. When the $ x _ {i} $ are equidistant, that is, if

$$ x _ {1} - x _ {0} = \dots = x _ {n} - x _ {n - 1 } = h, $$

then by introducing the notation $ ( x - x _ {0} )/h = t $ and expressing the divided differences $ f ( x _ {0} ; \dots ; x _ {k} ) $ in terms of the finite differences $ f _ {k/2} ^ { k } $ according to the formula

$$ f ( x _ {0} ; \dots ; x _ {k} ) = \ \frac{f _ {k/2} ^ { k } }{h ^ {k} k! } ,\ \ k = 0 \dots n, $$

one obtains a way of writing the polynomial $ L _ {n} ( x) $ in the form

$$ \tag{2 } L _ {n} ( x) = \ L _ {n} ( x _ {0} + th) = $$

$$ = \ f _ {0} + tf _ {1/2} ^ { 1 } + \frac{t ( t - 1) }{2! } f _ {1} ^ { 2 } + \dots + \frac{t ( t - 1) \dots ( t - n + 1) }{n! } f _ {n/2} ^ { n } , $$

which is called Newton's interpolation formula for forward interpolation. If the same change of variables is made in the interpolation polynomial $ L _ {n} $ with nodes $ x _ {0} , x _ {-} 1 \dots x _ {-} n $, where $ x _ {-} k = x _ {0} - kh $,

$$ L _ {n} ( x) = \ f ( x _ {0} ) + ( x - x _ {0} ) f ( x _ {0} ; x _ {-} 1 ) + \dots + $$

$$ + ( x - x _ {0} ) \dots ( x - x _ {- n + 1 } ) f ( x _ {0} ; \dots ; x _ {-} n ), $$

then one obtains Newton's interpolation formula for backward interpolation:

$$ \tag{3 } L _ {n} ( x) = L _ {n} ( x _ {0} + th) = $$

$$ = \ f _ {0} + tf _ {-} 1/2 ^ { 1 } + \frac{t ( t + 1) }{2! } f _ {-} 1 ^ { 2 } + \dots + $$

$$ + \frac{t ( t + 1) \dots ( t + n - 1) }{n! } f _ {-} n/2 ^ { n } . $$

Formulas (2) and (3) are convenient for computing tables of a given function $ f ( x) $ if the point $ x $ is at the beginning or the end of the table, since in this case the addition of one or several nodes caused by the wish to increase the accuracy of the approximation does not lead to a repetition of the whole work done as in computations with Lagrange's formula.

References

[1] I.S. Berezin, N.P. Zhidkov, "Computing methods" , 1 , Pergamon (1973) (Translated from Russian)
[2] N.S. Bakhvalov, "Numerical methods: analysis, algebra, ordinary differential equations" , MIR (1977) (Translated from Russian)

Comments

The divided differences $ f ( x _ {0} ; x _ {1} ) \dots f ( x _ {0} ; \dots ; x _ {n} ) $ are defined by:

$$ f ( x _ {0} ; x _ {1} ) = \ \frac{f ( x _ {1} ) - f ( x _ {0} ) }{x _ {1} - x _ {0} } , $$

$$ f ( x _ {0} ; x _ {1} ; x _ {2} ) = \frac{1}{x _ {2} - x _ {1} } \left ( \frac{f ( x _ {2} ) - f ( x _ {0} ) }{x _ {2} - x _ {0} } - \frac{f ( x _ {1} ) - f ( x _ {0} ) }{x _ {1} - x _ {0} } \right ) , $$

$$ {\dots \dots \dots \dots } $$

or

$$ f ( x _ {0} ; \dots ; x _ {n} ) = \ \sum _ { i= } 0 ^ { n } \prod _ { j= } 0 ^ { n } {} ^ \prime \frac{f ( x _ {i} ) }{x _ {i} - x _ {j} } , $$

where the prime in $ \prod ^ \prime $ means that the factor $ 1/ ( x _ {i} - x _ {i} ) $ is to be omitted. Formula (1) is also known as the finite Newton series for a function $ f $.

References

[a1] K.E. Atkinson, "An introduction to numerical analysis" , Wiley (1978)
[a2] P.J. Davis, "Interpolation and approximation" , Dover, reprint (1975)
[a3] F.B. Hildebrand, "Introduction to numerical analysis" , McGraw-Hill (1974)
How to Cite This Entry:
Newton interpolation formula. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Newton_interpolation_formula&oldid=47967
This article was adapted from an original article by M.K. Samarin (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article