Namespaces
Variants
Actions

Difference between revisions of "Everett interpolation formula"

From Encyclopedia of Mathematics
Jump to: navigation, search
m (→‎References: better)
(gather refs)
 
(2 intermediate revisions by 2 users not shown)
Line 1: Line 1:
A method of writing the interpolation polynomial obtained from the [[Gauss interpolation formula|Gauss interpolation formula]] for forward interpolation at <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036650/e0366501.png" /> with respect to the nodes <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036650/e0366502.png" />, that is,
+
<!--
 +
e0366501.png
 +
$#A+1 = 27 n = 0
 +
$#C+1 = 27 : ~/encyclopedia/old_files/data/E036/E.0306650 Everett 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.
 +
-->
  
<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/e/e036/e036650/e0366503.png" /></td> </tr></table>
+
{{TEX|auto}}
 +
{{TEX|done}}
  
<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/e/e036/e036650/e0366504.png" /></td> </tr></table>
+
A method of writing the interpolation polynomial obtained from the [[Gauss interpolation formula|Gauss interpolation formula]] for forward interpolation at  $  x = x _ {0} + th $
 +
with respect to the nodes  $  x _ {0} , x _ {0} + h , x _ {0} - h \dots x _ {0} + n h , x _ {0} - n h , x _ {0} + ( n + 1 ) h $,
 +
that is,
 +
 
 +
$$
 +
G _ {2n+} 1 ( x)  = G _ {2n+} 1 ( x _ {0} + t h )  = f _ {0} + t f _ {1/2} ^ { 1 } +
 +
\frac{t ( t - 1 ) }{2!}
 +
f _  \theta  ^ { 2 } + \dots +
 +
$$
 +
 
 +
$$
 +
+
 +
 
 +
\frac{t ( t  ^ {2} - 1 ) \dots [ t  ^ {2} - ( n - 1 )  ^ {2} ] (
 +
t  ^ {2} - n  ^ {2} ) }{( 2 n + 1 ) }
 +
f _ {1/2} ^ { 2n+ 1 } ,
 +
$$
  
 
without finite differences of odd order, which are eliminated by means of the relation
 
without finite differences of odd order, which are eliminated by means of the relation
  
<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/e/e036/e036650/e0366505.png" /></td> </tr></table>
+
$$
 +
f _ {1/2} ^ { 2k+ 1 }  = f _ {1} ^ { 2k } - f _ {0} ^ { 2k } .
 +
$$
  
 
Adding like terms yields Everett's interpolation formula
 
Adding like terms yields Everett's interpolation formula
  
<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/e/e036/e036650/e0366506.png" /></td> <td valign="top" style="width:5%;text-align:right;">(1)</td></tr></table>
+
$$ \tag{1 }
 +
E _ {2n+} 1 ( x _ {0} + t h )  = S _ {0} ( u ) + S _ {1} ( t) ,
 +
$$
 +
 
 +
where  $  u = 1 - t $
 +
and
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036650/e0366507.png" /> and
+
$$ \tag{2 }
 +
S _ {q} ( t) =
 +
$$
  
<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/e/e036/e036650/e0366508.png" /></td> <td valign="top" style="width:5%;text-align:right;">(2)</td></tr></table>
+
$$
 +
= \
 +
f _ {q} t + f _ {q} ^ { 2 }
 +
\frac{t ( t  ^ {2} - 1 ) }{3!}
 +
+ \dots +
 +
f _ {q} ^ { 2n }
 +
\frac{t ( t  ^ {2} - 1 ) \dots ( t  ^ {2} - n  ^ {2} ) }{( 2 n + 1 ) ! }
 +
.
 +
$$
  
<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/e/e036/e036650/e0366509.png" /></td> </tr></table>
+
Compared with other versions of the interpolation polynomial, formula (1) reduces approximately by half the amount of work required to solve the problem of table condensation; for example, when a given table of the values of a function at  $  x _ {0} + k h $
 +
is to be used to draw up a table of the values of the same function at  $  x _ {0} + k h  ^  \prime  $,
 +
$  h  ^  \prime  = h / l $,
 +
where  $  l $
 +
is an integer, the values  $  f ( x _ {0} - t h ) $
 +
for  $  0 < t < 1 $
 +
are computed be means of the formula
  
Compared with other versions of the interpolation polynomial, formula (1) reduces approximately by half the amount of work required to solve the problem of table condensation; for example, when a given table of the values of a function at <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036650/e03665010.png" /> is to be used to draw up a table of the values of the same function at <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036650/e03665011.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036650/e03665012.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036650/e03665013.png" /> is an integer, the values <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036650/e03665014.png" /> for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036650/e03665015.png" /> are computed be means of the formula
+
$$
 +
f ( x _ {0} - t h )  =  S _ {0} ( u ) + S _ {-} 1 ( t) ;
 +
$$
  
<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/e/e036/e036650/e03665016.png" /></td> </tr></table>
+
and  $  S _ {0} ( u ) $
 +
is used to find both values  $  f ( x _ {0} \pm  t h ) $.
  
and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036650/e03665017.png" /> is used to find both values <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036650/e03665018.png" />.
+
For manual calculation in the case  $  n = 2 $,
 +
L. J. Comrie introduced '''throwback'''. It is advisable to approximate the coefficient of  $  f _ {q} ^ { 4 } $
 +
in (2) by
  
For manual calculation in the case <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036650/e03665019.png" />, L. J. Comrie introduced '''throwback'''. It is advisable to approximate the coefficient of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036650/e03665020.png" /> in (2) by
+
$$
 +
- k
 +
\frac{t ( t ^ {2} - 1 ) }{3!}
  
<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/e/e036/e036650/e03665021.png" /></td> </tr></table>
+
$$
  
and instead of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036650/e03665022.png" /> to compute
+
and instead of $  S _ {q} ( t) $
 +
to compute
  
<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/e/e036/e036650/e03665023.png" /></td> </tr></table>
+
$$
 +
\overline{S}\; _ {q} ( t)  = f _ {q} t + \left (
 +
f _ {q} ^ { 2 } -  
 +
\frac{k}{20}
 +
f _ {q} ^ { 4 } \right )
  
The parameter <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036650/e03665024.png" /> can be chosen, for example, from the condition that the principal part of
+
\frac{t ( t  ^ {2} - 1 ) }{3!}
 +
.
 +
$$
  
<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/e/e036/e036650/e03665025.png" /></td> </tr></table>
+
The parameter  $  k $
 +
can be chosen, for example, from the condition that the principal part of
 +
 
 +
$$
 +
\sup  | E _ {5} ( x _ {0} + t h ) - \overline{E}\; _ {5} ( x _ {0} + t h ) | ,
 +
$$
  
 
where
 
where
  
<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/e/e036/e036650/e03665026.png" /></td> </tr></table>
+
$$
 +
\overline{E}\; _ {5} ( x _ {0} + t h )  = \overline{S}\; _ {0} ( u ) + \overline{S}\; _ {1} ( t) ,\ \
 +
u = 1 - t ,
 +
$$
  
has a minimum value. In this case <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036650/e03665027.png" />.
+
has a minimum value. In this case $  k = 3 . 6785 $.
  
 
====References====
 
====References====
Line 47: Line 116:
 
<TR><TD valign="top">[1]</TD> <TD valign="top">  I.S. Berezin,  N.P. Zhidkov,  "Computing methods" , Pergamon  (1973)  (Translated from Russian)</TD></TR>
 
<TR><TD valign="top">[1]</TD> <TD valign="top">  I.S. Berezin,  N.P. Zhidkov,  "Computing methods" , 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>
 
<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====
 
 
 
====References====
 
<table>
 
 
<TR><TD valign="top">[a1]</TD> <TD valign="top">  P.J. Davis,  "Interpolation and approximation" , Dover, reprint  (1975)  pp. 108–126</TD></TR>
 
<TR><TD valign="top">[a1]</TD> <TD valign="top">  P.J. Davis,  "Interpolation and approximation" , Dover, reprint  (1975)  pp. 108–126</TD></TR>
 
<TR><TD valign="top">[a2]</TD> <TD valign="top">  A.J. Thomson,  "Table of the coefficients of Everett's central difference interpolation formula" , Cambridge Univ. Press  (1965)</TD></TR>
 
<TR><TD valign="top">[a2]</TD> <TD valign="top">  A.J. Thomson,  "Table of the coefficients of Everett's central difference interpolation formula" , Cambridge Univ. Press  (1965)</TD></TR>
 
<TR><TD valign="top">[b1]</TD> <TD valign="top">  L. J. Comrie, "Inverse interpolation and scientific applications of the national accounting machine", Suppl. JR statist. Soc. London '''3''' (1936) 87-114 {{ZBL|63.1136.02}}</TD></TR>
 
<TR><TD valign="top">[b1]</TD> <TD valign="top">  L. J. Comrie, "Inverse interpolation and scientific applications of the national accounting machine", Suppl. JR statist. Soc. London '''3''' (1936) 87-114 {{ZBL|63.1136.02}}</TD></TR>
 
<TR><TD valign="top">[b2]</TD> <TD valign="top">  J. D. Everett, "On interpolation formulae", ''Quarterly J.'' '''32''' (1900) 306-313 {{ZBL|32.0271.01}}</TD></TR>
 
<TR><TD valign="top">[b2]</TD> <TD valign="top">  J. D. Everett, "On interpolation formulae", ''Quarterly J.'' '''32''' (1900) 306-313 {{ZBL|32.0271.01}}</TD></TR>
<TR><TD valign="top">[b3]</TD> <TD valign="top">  Maurice V. Wilkes, "A short introduction to numerical analysis", Cambridge University Press (1966) ISBN 0-521-09412-7 {{ZBL|0149.10902}}</TD></TR>
+
<TR><TD valign="top">[b3]</TD> <TD valign="top">  Maurice V. Wilkes, "A short introduction to numerical analysis", Cambridge University Press (1966) {{ISBN|0-521-09412-7}} {{ZBL|0149.10902}}</TD></TR>
 
</table>
 
</table>

Latest revision as of 08:09, 26 November 2023


A method of writing the interpolation polynomial obtained from the Gauss interpolation formula for forward interpolation at $ x = x _ {0} + th $ with respect to the nodes $ x _ {0} , x _ {0} + h , x _ {0} - h \dots x _ {0} + n h , x _ {0} - n h , x _ {0} + ( n + 1 ) h $, that is,

$$ G _ {2n+} 1 ( x) = G _ {2n+} 1 ( x _ {0} + t h ) = f _ {0} + t f _ {1/2} ^ { 1 } + \frac{t ( t - 1 ) }{2!} f _ \theta ^ { 2 } + \dots + $$

$$ + \frac{t ( t ^ {2} - 1 ) \dots [ t ^ {2} - ( n - 1 ) ^ {2} ] ( t ^ {2} - n ^ {2} ) }{( 2 n + 1 ) } f _ {1/2} ^ { 2n+ 1 } , $$

without finite differences of odd order, which are eliminated by means of the relation

$$ f _ {1/2} ^ { 2k+ 1 } = f _ {1} ^ { 2k } - f _ {0} ^ { 2k } . $$

Adding like terms yields Everett's interpolation formula

$$ \tag{1 } E _ {2n+} 1 ( x _ {0} + t h ) = S _ {0} ( u ) + S _ {1} ( t) , $$

where $ u = 1 - t $ and

$$ \tag{2 } S _ {q} ( t) = $$

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

Compared with other versions of the interpolation polynomial, formula (1) reduces approximately by half the amount of work required to solve the problem of table condensation; for example, when a given table of the values of a function at $ x _ {0} + k h $ is to be used to draw up a table of the values of the same function at $ x _ {0} + k h ^ \prime $, $ h ^ \prime = h / l $, where $ l $ is an integer, the values $ f ( x _ {0} - t h ) $ for $ 0 < t < 1 $ are computed be means of the formula

$$ f ( x _ {0} - t h ) = S _ {0} ( u ) + S _ {-} 1 ( t) ; $$

and $ S _ {0} ( u ) $ is used to find both values $ f ( x _ {0} \pm t h ) $.

For manual calculation in the case $ n = 2 $, L. J. Comrie introduced throwback. It is advisable to approximate the coefficient of $ f _ {q} ^ { 4 } $ in (2) by

$$ - k \frac{t ( t ^ {2} - 1 ) }{3!} $$

and instead of $ S _ {q} ( t) $ to compute

$$ \overline{S}\; _ {q} ( t) = f _ {q} t + \left ( f _ {q} ^ { 2 } - \frac{k}{20} f _ {q} ^ { 4 } \right ) \frac{t ( t ^ {2} - 1 ) }{3!} . $$

The parameter $ k $ can be chosen, for example, from the condition that the principal part of

$$ \sup | E _ {5} ( x _ {0} + t h ) - \overline{E}\; _ {5} ( x _ {0} + t h ) | , $$

where

$$ \overline{E}\; _ {5} ( x _ {0} + t h ) = \overline{S}\; _ {0} ( u ) + \overline{S}\; _ {1} ( t) ,\ \ u = 1 - t , $$

has a minimum value. In this case $ k = 3 . 6785 $.

References

[1] I.S. Berezin, N.P. Zhidkov, "Computing methods" , Pergamon (1973) (Translated from Russian)
[2] N.S. Bakhvalov, "Numerical methods: analysis, algebra, ordinary differential equations" , MIR (1977) (Translated from Russian)
[a1] P.J. Davis, "Interpolation and approximation" , Dover, reprint (1975) pp. 108–126
[a2] A.J. Thomson, "Table of the coefficients of Everett's central difference interpolation formula" , Cambridge Univ. Press (1965)
[b1] L. J. Comrie, "Inverse interpolation and scientific applications of the national accounting machine", Suppl. JR statist. Soc. London 3 (1936) 87-114 Zbl 63.1136.02
[b2] J. D. Everett, "On interpolation formulae", Quarterly J. 32 (1900) 306-313 Zbl 32.0271.01
[b3] Maurice V. Wilkes, "A short introduction to numerical analysis", Cambridge University Press (1966) ISBN 0-521-09412-7 Zbl 0149.10902
How to Cite This Entry:
Everett interpolation formula. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Everett_interpolation_formula&oldid=36056
This article was adapted from an original article by M.K. Samarin (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article