Namespaces
Variants
Actions

Difference between revisions of "Lagrange interpolation formula"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (tex encoded by computer)
 
Line 1: Line 1:
A formula for obtaining a polynomial of degree <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057170/l0571701.png" /> (the Lagrange interpolation polynomial) that interpolates a given function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057170/l0571702.png" /> at nodes <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057170/l0571703.png" />:
+
<!--
 +
l0571701.png
 +
$#A+1 = 38 n = 0
 +
$#C+1 = 38 : ~/encyclopedia/old_files/data/L057/L.0507170 Lagrange 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/l/l057/l057170/l0571704.png" /></td> <td valign="top" style="width:5%;text-align:right;">(1)</td></tr></table>
+
{{TEX|auto}}
 +
{{TEX|done}}
  
When the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057170/l0571705.png" /> are equidistant, that is, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057170/l0571706.png" />, using the notation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057170/l0571707.png" /> one can reduce (1) to the form
+
A formula for obtaining a polynomial of degree  $  n $(
 +
the Lagrange interpolation polynomial) that interpolates a given function  $  f ( x) $
 +
at nodes  $  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/l/l057/l057170/l0571708.png" /></td> <td valign="top" style="width:5%;text-align:right;">(2)</td></tr></table>
+
$$ \tag{1 }
 +
L _ {n} ( x)  = \sum _ { i= } 0 ^ { n }  f ( x _ {i} ) \prod _ {j \neq i }
  
<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/l/l057/l057170/l0571709.png" /></td> </tr></table>
+
\frac{x - x _ {j} }{x _ {i} - x _ {j} }
 +
.
 +
$$
 +
 
 +
When the  $  x _ {i} $
 +
are equidistant, that is,  $  x _ {1} - x _ {0} = \dots = x _ {n} - x _ {n-} 1 = h $,
 +
using the notation  $  ( x - x _ {0} ) / h = t $
 +
one can reduce (1) to the form
 +
 
 +
$$ \tag{2 }
 +
L _ {n} ( x)  = L _ {n} ( x _ {0} + th )  = ( - 1 )  ^ {n}
 +
\frac{t ( t- 1 )
 +
{} \dots ( t- n ) }{n!}
 +
\times
 +
$$
 +
 
 +
$$
 +
\times
 +
\sum _ { i= } 0 ^ { n }  ( - 1 )  ^ {i} \left ( \begin{array}{c}
 +
n
 +
\\
 +
i
 +
\end{array}
 +
\right )
 +
\frac{f ( x _ {i} ) }{t-}
 +
i .
 +
$$
  
 
In the expression (2), called the Lagrange interpolation formula for equidistant nodes, the coefficients
 
In the expression (2), called the Lagrange interpolation formula for equidistant nodes, the coefficients
  
<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/l/l057/l057170/l05717010.png" /></td> </tr></table>
+
$$
 +
( - 1 )  ^ {n-} i \left ( \begin{array}{c}
 +
n \\
 +
i
 +
\end{array}
 +
\right )
  
of the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057170/l05717011.png" /> are called the Lagrange coefficients.
+
\frac{t ( t- 1 ) \dots ( t- n ) }{( t- i) n! }
  
If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057170/l05717012.png" /> has a derivative of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057170/l05717013.png" /> on the interval <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057170/l05717014.png" />, if all interpolation nodes lie in this interval and if for any point <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057170/l05717015.png" /> one defines
+
$$
  
<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/l/l057/l057170/l05717016.png" /></td> </tr></table>
+
of the  $  f ( x _ {i} ) $
 +
are called the Lagrange coefficients.
  
then a point <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057170/l05717017.png" /> exists such that
+
If  $  f $
 +
has a derivative of order  $  n+ 1 $
 +
on the interval  $  [ a , b ] $,
 +
if all interpolation nodes lie in this interval and if for any point $  x \in [ a , b ] $
 +
one defines
  
<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/l/l057/l057170/l05717018.png" /></td> </tr></table>
+
$$
 +
\alpha _ {x}  = \min \{ x _ {0} \dots x _ {n} , x
 +
\} ,\  \beta _ {x}  = \max \{ x _ {0} \dots x _ {n} , x \} ,
 +
$$
 +
 
 +
then a point  $  \xi \in [ \alpha _ {x} , \beta _ {x} ] $
 +
exists such that
 +
 
 +
$$
 +
f ( x) - L _ {n} ( x)  =
 +
\frac{f ^ { ( n+ 1 ) } ( \xi ) \omega _ {n} ( x) }{( n+ 1) ! }
 +
,
 +
$$
  
 
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/l/l057/l057170/l05717019.png" /></td> </tr></table>
+
$$
 +
\omega _ {n} ( x)  = \prod _ { j= } 0 ^ { n }  ( x - x _ {j} ) .
 +
$$
  
If the absolute value of the derivative <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057170/l05717020.png" /> is bounded on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057170/l05717021.png" /> by a constant <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057170/l05717022.png" /> and if the interpolation nodes are chosen such that the roots of the Chebyshev polynomial of degree <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057170/l05717023.png" /> are mapped into these points under a linear mapping from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057170/l05717024.png" /> onto <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057170/l05717025.png" />, then for any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057170/l05717026.png" /> one has
+
If the absolute value of the derivative $  f ^ { ( n+ 1 ) } $
 +
is bounded on $  [ a , b ] $
 +
by a constant $  M $
 +
and if the interpolation nodes are chosen such that the roots of the Chebyshev polynomial of degree $  n+ 1 $
 +
are mapped into these points under a linear mapping from $  [ - 1 , 1] $
 +
onto $  [ a , b ] $,
 +
then for any $  x \in [ a , b ] $
 +
one has
  
<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/l/l057/l057170/l05717027.png" /></td> </tr></table>
+
$$
 +
| f ( x) - L _ {n} ( x) |  \leq  M
 +
\frac{( b- a )  ^ {n+} 1 }{( n+ 1 )!
 +
2  ^ {2n+} 1 }
 +
.
 +
$$
  
If the interpolation nodes are complex numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057170/l05717028.png" /> and lie in some domain <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057170/l05717029.png" /> bounded by a piecewise-smooth contour <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057170/l05717030.png" />, and if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057170/l05717031.png" /> is a single-valued analytic function defined on the closure of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057170/l05717032.png" />, then the Lagrange interpolation formula has the form
+
If the interpolation nodes are complex numbers $  z _ {0} \dots z _ {n} $
 +
and lie in some domain $  G $
 +
bounded by a piecewise-smooth contour $  \gamma $,  
 +
and if $  f $
 +
is a single-valued analytic function defined on the closure of $  G $,  
 +
then the Lagrange interpolation formula has 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/l/l057/l057170/l05717033.png" /></td> </tr></table>
+
$$
 +
L _ {n} ( z)  =
 +
\frac{1}{2 \pi i }
 +
\int\limits _  \gamma 
 +
\frac{\omega ( \zeta ) -
 +
\omega ( z) }{\omega ( \zeta ) ( \zeta - z ) }
 +
f ( \zeta )  d \zeta ,
 +
$$
  
 
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/l/l057/l057170/l05717034.png" /></td> </tr></table>
+
$$
 +
f ( z) - L _ {n} ( z)  =
 +
\frac{\omega ( z) }{2 \pi i }
 +
\int\limits _  \gamma
 +
 
 +
\frac{f ( \zeta ) }{\omega ( \zeta ) ( z - \zeta ) }
 +
  d \zeta .
 +
$$
  
 
The Lagrange interpolation formula for interpolation by means of trigonometric polynomials is:
 
The Lagrange interpolation formula for interpolation by means of trigonometric polynomials is:
  
<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/l/l057/l057170/l05717035.png" /></td> </tr></table>
+
$$
 +
T _ {n} ( x)  = \sum _ { k= } 0 ^ { n }  y _ {k} \prod _ {j \neq k }
 +
\frac{\sin
 +
( x - x _ {j} ) / 2 }{\sin  ( x _ {k} - x _ {j} ) / 2 }
 +
,
 +
$$
  
which is a trigonometric polynomial of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057170/l05717036.png" /> having prescribed values <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057170/l05717037.png" /> at the given nodes <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057170/l05717038.png" />.
+
which is a trigonometric polynomial of order $  n $
 +
having prescribed values $  y _ {0} \dots y _ {n} $
 +
at the given nodes $  x _ {0} \dots x _ {n} $.
  
 
The formula was proposed by J.L. Lagrange in 1795.
 
The formula was proposed by J.L. Lagrange in 1795.
Line 49: Line 148:
 
====References====
 
====References====
 
<table><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></table>
 
<table><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></table>
 
 
  
 
====Comments====
 
====Comments====
 
  
 
====References====
 
====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">[a2]</TD> <TD valign="top">  L.W. Johnson,  R.D. Riess,  "Numerical analysis" , Addison-Wesley  (1977)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  G.M. Phillips,  P.J. Taylor,  "Theory and applications of numerical analysis" , Acad. Press  (1973)</TD></TR></table>
 
<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">[a2]</TD> <TD valign="top">  L.W. Johnson,  R.D. Riess,  "Numerical analysis" , Addison-Wesley  (1977)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  G.M. Phillips,  P.J. Taylor,  "Theory and applications of numerical analysis" , Acad. Press  (1973)</TD></TR></table>

Latest revision as of 22:15, 5 June 2020


A formula for obtaining a polynomial of degree $ n $( the Lagrange interpolation polynomial) that interpolates a given function $ f ( x) $ at nodes $ x _ {0} \dots x _ {n} $:

$$ \tag{1 } L _ {n} ( x) = \sum _ { i= } 0 ^ { n } f ( x _ {i} ) \prod _ {j \neq i } \frac{x - x _ {j} }{x _ {i} - x _ {j} } . $$

When the $ x _ {i} $ are equidistant, that is, $ x _ {1} - x _ {0} = \dots = x _ {n} - x _ {n-} 1 = h $, using the notation $ ( x - x _ {0} ) / h = t $ one can reduce (1) to the form

$$ \tag{2 } L _ {n} ( x) = L _ {n} ( x _ {0} + th ) = ( - 1 ) ^ {n} \frac{t ( t- 1 ) {} \dots ( t- n ) }{n!} \times $$

$$ \times \sum _ { i= } 0 ^ { n } ( - 1 ) ^ {i} \left ( \begin{array}{c} n \\ i \end{array} \right ) \frac{f ( x _ {i} ) }{t-} i . $$

In the expression (2), called the Lagrange interpolation formula for equidistant nodes, the coefficients

$$ ( - 1 ) ^ {n-} i \left ( \begin{array}{c} n \\ i \end{array} \right ) \frac{t ( t- 1 ) \dots ( t- n ) }{( t- i) n! } $$

of the $ f ( x _ {i} ) $ are called the Lagrange coefficients.

If $ f $ has a derivative of order $ n+ 1 $ on the interval $ [ a , b ] $, if all interpolation nodes lie in this interval and if for any point $ x \in [ a , b ] $ one defines

$$ \alpha _ {x} = \min \{ x _ {0} \dots x _ {n} , x \} ,\ \beta _ {x} = \max \{ x _ {0} \dots x _ {n} , x \} , $$

then a point $ \xi \in [ \alpha _ {x} , \beta _ {x} ] $ exists such that

$$ f ( x) - L _ {n} ( x) = \frac{f ^ { ( n+ 1 ) } ( \xi ) \omega _ {n} ( x) }{( n+ 1) ! } , $$

where

$$ \omega _ {n} ( x) = \prod _ { j= } 0 ^ { n } ( x - x _ {j} ) . $$

If the absolute value of the derivative $ f ^ { ( n+ 1 ) } $ is bounded on $ [ a , b ] $ by a constant $ M $ and if the interpolation nodes are chosen such that the roots of the Chebyshev polynomial of degree $ n+ 1 $ are mapped into these points under a linear mapping from $ [ - 1 , 1] $ onto $ [ a , b ] $, then for any $ x \in [ a , b ] $ one has

$$ | f ( x) - L _ {n} ( x) | \leq M \frac{( b- a ) ^ {n+} 1 }{( n+ 1 )! 2 ^ {2n+} 1 } . $$

If the interpolation nodes are complex numbers $ z _ {0} \dots z _ {n} $ and lie in some domain $ G $ bounded by a piecewise-smooth contour $ \gamma $, and if $ f $ is a single-valued analytic function defined on the closure of $ G $, then the Lagrange interpolation formula has the form

$$ L _ {n} ( z) = \frac{1}{2 \pi i } \int\limits _ \gamma \frac{\omega ( \zeta ) - \omega ( z) }{\omega ( \zeta ) ( \zeta - z ) } f ( \zeta ) d \zeta , $$

where

$$ f ( z) - L _ {n} ( z) = \frac{\omega ( z) }{2 \pi i } \int\limits _ \gamma \frac{f ( \zeta ) }{\omega ( \zeta ) ( z - \zeta ) } d \zeta . $$

The Lagrange interpolation formula for interpolation by means of trigonometric polynomials is:

$$ T _ {n} ( x) = \sum _ { k= } 0 ^ { n } y _ {k} \prod _ {j \neq k } \frac{\sin ( x - x _ {j} ) / 2 }{\sin ( x _ {k} - x _ {j} ) / 2 } , $$

which is a trigonometric polynomial of order $ n $ having prescribed values $ y _ {0} \dots y _ {n} $ at the given nodes $ x _ {0} \dots x _ {n} $.

The formula was proposed by J.L. Lagrange in 1795.

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] L.W. Johnson, R.D. Riess, "Numerical analysis" , Addison-Wesley (1977)
[a3] G.M. Phillips, P.J. Taylor, "Theory and applications of numerical analysis" , Acad. Press (1973)
How to Cite This Entry:
Lagrange interpolation formula. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Lagrange_interpolation_formula&oldid=17497
This article was adapted from an original article by L.D. KudryavtsevM.K. Samarin (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article