Namespaces
Variants
Actions

Difference between revisions of "Everett interpolation formula"

From Encyclopedia of Mathematics
Jump to: navigation, search
m (→‎References: better)
m (tex encoded by computer)
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
 +
 
 +
$$ \tag{2 }
 +
S _ {q} ( t) =
 +
$$
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036650/e0366507.png" /> and
+
$$
 +
= \
 +
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/e0366508.png" /></td> <td valign="top" style="width:5%;text-align:right;">(2)</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
  
<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>
+
$$
 +
f ( x _ {0} - t h )  = S _ {0} ( u ) + S _ {-} 1 ( t) ;
 +
$$
  
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
+
and  $  S _ {0} ( u ) $
 +
is used to find both values $  f ( x _ {0} \pm  t 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/e/e036/e036650/e03665016.png" /></td> </tr></table>
+
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
  
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" />.
+
$$
 +
- k
 +
\frac{t ( t  ^ {2} - 1 ) }{3!}
  
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
+
$$
  
<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  $  S _ {q} ( t) $
 +
to compute
  
and instead of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036650/e03665022.png" /> to compute
+
$$
 +
\overline{S}\; _ {q} ( t)  = f _ {q} t + \left (
 +
f _ {q} ^ { 2 } -
 +
\frac{k}{20}
 +
f _ {q} ^ { 4 } \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/e/e036/e036650/e03665023.png" /></td> </tr></table>
+
\frac{t ( t  ^ {2} - 1 ) }{3!}
 +
.
 +
$$
  
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
+
The parameter $  k $
 +
can be chosen, for example, from the condition that the principal part of
  
<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>
+
$$
 +
\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 48: Line 117:
 
<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>
 
</table>
 
 
  
 
====Comments====
 
====Comments====
 
  
 
====References====
 
====References====

Revision as of 19:38, 5 June 2020


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)

Comments

References

[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=46862
This article was adapted from an original article by M.K. Samarin (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article