Lagrangen interpolaatiopolynomi

Numeerisessa analyysissä Lagrangen interpolaatiopolynomi on polynomimuotoinen funktio, joka kulkee annettujen pisteiden kautta. Polynomi on nimetty Joseph-Louis Lagrangen mukaan, vaikka sen keksi ensimmäisenä Edward Waring vuonna 1779 ja myöhemmin Leonhard Euler vuonna 1783.

Kuva osoittaa neljälle pisteelle ((−9, 5), (−4, 2), (−1, −2), (7, 9)) kolmannen asteen interpolaatiopolynomin L(x), joka on summa skaalattuja kantapolynomeja y0l0(x), y1l1(x), y2l2(x) ja y3l3(x). Interpolaatiopolynomi kulkee kaikkien neljän pisteen kautta ja jokainen kantapolynomi kulkee kiinnitetyn pisteen kautta ja saa arvon nolla kun x saa jonkin muun kiinnitetyn pisteen arvon.

Määritelmä

Olkoon annettu joukko k + 1 havaintoja

( x 0 , y 0 ) , … , ( x k , y k ) , {\displaystyle (x_{0},y_{0}),\ldots ,(x_{k},y_{k}),}

missä kaikki xj:t ovat keskenään erisuuria. Tällöin Lagrangen interpolaatiopolynomi on lineaarikombinaatio

L ( x ) = ∑ j = 0 k y j ℓ j ( x ) {\displaystyle L(x)=\sum _{j=0}^{k}y_{j}\ell _{j}(x)}

Lagrangen kantapolynomeja

ℓ j ( x ) = ∏ i = 0 j ≠ i k x − x i x j − x i = x − x 0 x j − x 0 ⋯ x − x j − 1 x j − x j − 1 x − x j + 1 x j − x j + 1 ⋯ x − x k x j − x k . {\displaystyle \ell _{j}(x)=\prod _{{i=0} \atop {j\neq i}}^{k}{\frac {x-x_{i}}{x_{j}-x_{i}}}={\frac {x-x_{0}}{x_{j}-x_{0}}}\cdots {\frac {x-x_{j-1}}{x_{j}-x_{j-1}}}{\frac {x-x_{j+1}}{x_{j}-x_{j+1}}}\cdots {\frac {x-x_{k}}{x_{j}-x_{k}}}.}

Todistus

Hakemamme funktio on astetta k oleva polynomifunktio L(x), jolle

L ( x j ) = y j j = 0 , … , k {\displaystyle L(x_{j})=y_{j}\qquad j=0,\ldots ,k}

Stonen–Weierstrassin lauseen mukaan tällainen funktio on olemassa ja yksikäsitteinen. Lagrangen polynomi on ratkaisu kyseiseen interpolaatio-ongelmaan.

Kuten helposti nähdään,

  1. ℓ j ( x ) {\displaystyle \ell _{j}(x)} on astetta k oleva polynomi.
  2. ℓ i ( x j ) = δ i j , 0 ≤ i , j ≤ k . {\displaystyle \ell _{i}(x_{j})=\delta _{ij},\quad 0\leq i,j\leq k.\,}

Siten funktio L(x) on astetta k oleva polynomi ja

L ( x i ) = ∑ j = 0 k y j ℓ j ( x i ) = y i . {\displaystyle L(x_{i})=\sum _{j=0}^{k}y_{j}\ell _{j}(x_{i})=y_{i}.}

Siten L(x) on hakemamme yksikäsitteinen interpolaatiopolynomi.

Polynomin idea

Interpolaatio-ongelman ratkaisu johtaa lineaariseen matriisimuotoiseen yhtälöön. Valitsemalla interpolaatiopolynomin kannaksi monomit saadaan usein hyvin monimutkainen Vandermonden matriisi. Sen sijaan valitsemalla kannaksi Lagrangen kannan päädymme paljon yksinkertaisempaan yksikkömatriisiin, jonka ratkaisu voidaan lukea välittömästi suoraan matriisista.

Käyttö

Esimerkki

Tangenttifunktio ja sen interpolaatio.

Haluamme interpoloida funktiota f ( x ) = tan ⁡ x {\displaystyle f(x)=\tan {x}} pisteissä

x 0 = − 1.5 {\displaystyle x_{0}=-1.5} f ( x 0 ) = − 14.1014 {\displaystyle f(x_{0})=-14.1014}
x 1 = − 0.75 {\displaystyle x_{1}=-0.75} f ( x 1 ) = − 0.931596 {\displaystyle f(x_{1})=-0.931596}
x 2 = 0 {\displaystyle x_{2}=0} f ( x 2 ) = 0 {\displaystyle f(x_{2})=0}
x 3 = 0.75 {\displaystyle x_{3}=0.75} f ( x 3 ) = 0.931596 {\displaystyle f(x_{3})=0.931596}
x 4 = 1.5 {\displaystyle x_{4}=1.5} f ( x 4 ) = 14.1014 {\displaystyle f(x_{4})=14.1014}

Nyt kantapolynomeiksi saadaan:

ℓ 0 ( x ) = x − x 1 x 0 − x 1 ⋅ x − x 2 x 0 − x 2 ⋅ x − x 3 x 0 − x 3 ⋅ x − x 4 x 0 − x 4 = 1 243 x ( 2 x − 3 ) ( 4 x − 3 ) ( 4 x + 3 ) {\displaystyle \ell _{0}(x)={x-x_{1} \over x_{0}-x_{1}}\cdot {x-x_{2} \over x_{0}-x_{2}}\cdot {x-x_{3} \over x_{0}-x_{3}}\cdot {x-x_{4} \over x_{0}-x_{4}}={1 \over 243}x(2x-3)(4x-3)(4x+3)}
ℓ 1 ( x ) = x − x 0 x 1 − x 0 ⋅ x − x 2 x 1 − x 2 ⋅ x − x 3 x 1 − x 3 ⋅ x − x 4 x 1 − x 4 = − 8 243 x ( 2 x − 3 ) ( 2 x + 3 ) ( 4 x − 3 ) {\displaystyle \ell _{1}(x)={x-x_{0} \over x_{1}-x_{0}}\cdot {x-x_{2} \over x_{1}-x_{2}}\cdot {x-x_{3} \over x_{1}-x_{3}}\cdot {x-x_{4} \over x_{1}-x_{4}}=-{8 \over 243}x(2x-3)(2x+3)(4x-3)}
ℓ 2 ( x ) = x − x 0 x 2 − x 0 ⋅ x − x 1 x 2 − x 1 ⋅ x − x 3 x 2 − x 3 ⋅ x − x 4 x 2 − x 4 = 1 243 ( 243 − 540 x 2 + 192 x 4 ) {\displaystyle \ell _{2}(x)={x-x_{0} \over x_{2}-x_{0}}\cdot {x-x_{1} \over x_{2}-x_{1}}\cdot {x-x_{3} \over x_{2}-x_{3}}\cdot {x-x_{4} \over x_{2}-x_{4}}={1 \over 243}(243-540x^{2}+192x^{4})}
ℓ 3 ( x ) = x − x 0 x 3 − x 0 ⋅ x − x 1 x 3 − x 1 ⋅ x − x 2 x 3 − x 2 ⋅ x − x 4 x 3 − x 4 = − 8 243 x ( 2 x − 3 ) ( 2 x + 3 ) ( 4 x + 3 ) {\displaystyle \ell _{3}(x)={x-x_{0} \over x_{3}-x_{0}}\cdot {x-x_{1} \over x_{3}-x_{1}}\cdot {x-x_{2} \over x_{3}-x_{2}}\cdot {x-x_{4} \over x_{3}-x_{4}}=-{8 \over 243}x(2x-3)(2x+3)(4x+3)}
ℓ 4 ( x ) = x − x 0 x 4 − x 0 ⋅ x − x 1 x 4 − x 1 ⋅ x − x 2 x 4 − x 2 ⋅ x − x 3 x 4 − x 3 = 1 243 x ( 2 x + 3 ) ( 4 x − 3 ) ( 4 x + 3 ) {\displaystyle \ell _{4}(x)={x-x_{0} \over x_{4}-x_{0}}\cdot {x-x_{1} \over x_{4}-x_{1}}\cdot {x-x_{2} \over x_{4}-x_{2}}\cdot {x-x_{3} \over x_{4}-x_{3}}={1 \over 243}x(2x+3)(4x-3)(4x+3)}

Siten interpolaatiopolynomi on

1 243 ( f ( x 0 ) x ( 2 x − 3 ) ( 4 x − 3 ) ( 4 x + 3 ) − 8 f ( x 1 ) x ( 2 x − 3 ) ( 2 x + 3 ) ( 4 x − 3 ) {\displaystyle {1 \over 243}{\Big (}f(x_{0})x(2x-3)(4x-3)(4x+3)-8f(x_{1})x(2x-3)(2x+3)(4x-3)}
+ f ( x 2 ) ( 243 − 540 x 2 + 192 x 4 ) − 8 f ( x 3 ) x ( 2 x − 3 ) ( 2 x + 3 ) ( 4 x + 3 ) {\displaystyle +f(x_{2})(243-540x^{2}+192x^{4})-8f(x_{3})x(2x-3)(2x+3)(4x+3)\,}
+ f ( x 4 ) x ( 2 x + 3 ) ( 4 x − 3 ) ( 4 x + 3 ) ) {\displaystyle +f(x_{4})x(2x+3)(4x-3)(4x+3){\Big )}\,}
= − 1.47748 x + 4.83456 x 3 . {\displaystyle =-1.47748x+4.83456x^{3}.\,}

Huomaa

Lagrangen polynomi osoittaa sen, että polynomi saadaan aina kulkemaan annettujen pisteiden kautta, ja että tämä polynomi on yksikäsitteinen pienintä mahdollista astetta oleva kiinnitettyjen pisteiden kautta kulkeva polynomi. Kuitenkin jos solmut xk vaihtuvat, joudutaan kaikki Lagrangen kantapolynomit laskemaan uudelleen. Käytännön laskuissa on parempi käyttää Newtonin polynomeja.

Lagrangen- ja muut interpolaatiopolynomit oskilloivat kiinnitettyjen arvojen välillä. Oskillointia voidaan pienentää kun interpolointipisteiksi valitaan Tšebyševin solmut.

Lagrangen kantapolynomeja käytetään numeerisessa integroinnissa johtamaan Newtonin–Cotesin kaavat.

Lagrangen interpolaatiota käytetään paljon äänen digitaalisessa signaalinkäsittelyssä määrittämään FIR-filtterit.