Lagrange interpolation formula

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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)