Lagrange interpolation formula

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)

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)