Polynominen interpolaatio

Polynominen interpolaatio eli polynomi-interpolaatio on matematiikassa approksimaatiomenetelmä, jossa sovituskäyrinä käytetään polynomeja. Polynomisella interpolaatiolla halutaan yleensä laskea tunnettujen pisteiden välistä puuttuvia pisteitä tai sovittamaan pisteiden väleihin sileä ja jatkuva käyrä. Toisinaan sovitetaan mutkikkaalle funktiolle helpommin laskettava polynomi, jolla funktion arvot voidaan approksimoida nopeasti.

Polynominen interpolaatio on tehokas menetelmä, jos interpoloitavia pisteitä on vähän. Suuri pistejoukko vaatii polynomin, jolla on korkea asteluku ja sellainen polynomi heilahtelee paljon. Alemmilla asteluvuilla heilahtelua on vain vähän ja sen laskeminen on helppoa. Interpoloitava pistejoukko jaetaankin ryhmiin, joihin sovitetaan erilaisia matala-asteisia polynomeja. Silloin eri polynomien yhtymiskohdissa käyrä on jatkuva, mutta sen derivoituvuus puuttuu. Tätä varten voidaan sovitusalgoritmiin lisätä derivoituvuusehtoja, jolloin käyristä tulee jokaisessa kohdassa sileä. On kehitelty monia menetelmiä, jotka sopivat eri tilanteisiin paremmin ja erilaisia polynomiluokkia, jotka täyttävät kulloinkin vaaditut ominaisuudet.

Jotta polynomin kuvaaja kulkisi kaikkien annettujen pisteiden kautta, tulisi polynomin asteluku olla yhtä pienempi kuin pisteiden lukumäärä. Silloinkin, jos pisteitä sijaitsee päällekkäin tai ne ovat esimerkiksi kollineaarisia, tullaan toimeen alemmallakin asteluvulla. Kun kertoimien laskentamenetelmä on valittu, on saatu interpolaatiopolynomi yksikäsitteinen.

Ensimmäisen asteen polynomi

Lineaarinen interpolaatio toteutetaan joko sovittamalla suoran yhtälö kahden pisteen välille tai luomalla Lagrangen polynomi kahdelle pisteelle. Kun kaksi pistettä merkitään $(x_0,y_0)$ ja $(x_1,y_1)$ ja y-koordinaateilla tarkoitetaan funktion $y=f(x)$ arvoja, voidaan suoran yhtälöllä muodostaa ensimmäisen asteen polynomi

$f(x)\approx \frac{y_1-y_0}{x_1-x_0}(x-x_0)+y_0.$

Toinen tapa muodostaa kahden pisteen kautta kulkeva polynomi on luoda lausekkeet, jotka saavat arvon nolla toisen pisteen sijoituksesta ja oman y-koordinaatin omassa kohdassa. Silloin

$y_0\frac{x-x_1}{x_0-x_1}$ on nolla sijoituksella $x_1$ ja $y_0$ sijoituksella $x_0$

ja

$y_1\frac{x_0-x}{x_0-x_1}$ on nolla sijoituksella $x_0$ ja $y_1$ sijoituksella $x_1.$

Polynomi saadaan näiden lausekkeiden summana

$f(x)\approx y_0\frac{x-x_1}{x_0-x_1}+y_1\frac{x_0-x}{x_0-x_1}.$

Se antaa tulokseksi saman ensimmäisen asteen interpolaatiopolynomin kuin edellinenkin menetelmä. Viimeistä muotoa kutsutaan myös Lagrangen polynomiksi.

Toisen asteen polynomi

Toisen asteen interpolointi voidaan toteuttaa joko sovittamalla toisen asteen polynomin käyrää eli paraabeli kolmelle pisteelle tai soveltamalla Lagrangen menetelmää. Toisen asteen interpolointi kolmelle pisteelle $(x_0,y_0),$ $(x_1,y_1)$ ja $(x_2,y_2)$ voidaan suorittaa viimeksi mainitulla tavalla. Muodostetaan lausekkeet, jotka antavat arvoksi nolla muissa pisteissä paitsi "omassa" pisteessä. Seuraava termi on nolla, kun siihen sijoitetaan $x_1$ tai $x_2$, mutta se on $y_0$, kun siihen sijoitetaan $x_0$

$y_0\frac{(x-x_1)(x-x_2)}{(x_0-x_1)(x_0-x_2)}.$

Polynomi saadaan kolmella termillä

$f(x)\approx y_0\frac{(x-x_1)(x-x_2)}{(x_0-x_1)(x_0-x_2)}+y_1\frac{(x-x_0)(x-x_2)}{(x_1-x_0)(x_1-x_2)}+y_2\frac{(x-x_0)(x-x_1)}{(x_2-x_0)(x_2-x_1)}.$

Näitä interpolaatiopolynomeja voi liittää moneen peräkkäisen kolmen pisteen sarjoihin. Jos pisteet ovat kollineaarisia, tulee polynomista ensimmäistä astetta. Jos pisteet eivät ole kollineaarisia, tulee siitä toisen asteen interpolaatiopolynomi. Esitettyä muotoa kutsutaan Lagrangen polynomiksi.

Lagrangen interpolaatio

Malline:Pääartikkeli Lagrangen interpolaatio luodaan käyttämällä yleistä Lagrangen interpolaatiopolynomia. Se voidaan kirjoittaa muodossa

$p(x)=y_0{L}_0(x)+y_1{L}_1(x)+\dots +y_n{L}_n(x),$

missä ensimmäinen kantapolynomi $L_0(x)$ on

$L_0(x)=\frac{(x-x_1)(x-x_2)\dots (x-x_n)}{(x_0-x_1)(x_0-x_2)\dots (x_0-x_n)}$

ja $i.$ kantapolynomi on

$L_i(x)=\frac{(x-x_1)(x-x_2)\dots (x-x_{i-1})(x-x_{i+1})\dots (x-x_n)}{(x_i-x_1)(x_i-x_2)\dots (x_i-x_{i-1})(x_i-x_{i+1})\dots (x_i-x_n)}.$

Polynomin aste on korkeintaan $n$, jos pisteitä on $n+1$. Mikäli osa pisteistä ovat samoja tai ne ovat kollineaarisia, laskee polynomin asteluku alle $n$. Lagrangen interpolaatiopolynomi on vaikea laskea tietokoneella, sillä pyöristysvirheet aiheuttavat joskus yli- tai alivuotoa.

Newtonin interpolaatio

Malline:Pääartikkeli Newtoinin interpolaatiomenetelmässä polynomille haetaan kertoimet muodossa

$P(x)=a_0+a_1(x-x_0)+a_2(x-x_0)(x-x_1)+\dots +a_n(x-x_0)(x-x_1)\dots (x-x_{n-1}).$

Kertoimet määräytyvät ehdosta

$P(x_i)=y_i,$ $(i\in \{0,1,\dots ,n-1\}),$

joka johtaa rekursiivisesti ratkeavaan yhtälöryhmään

$\begin{array}{cc}{y}_0& =a_0\\ y_1& =a_0+a_1(x_1-x_0)\\ y_2& =a_0+a_1(x_2-x_0)+a_2(x_2-x_0)(x_2-x_1)\\ y_3& =a_0+a_1(x_3-x_0)+a_2(x_3-x_0)(x_3-x_1)+a_3(x_3-x_0)(x_3-x_1)(x_3-x_2)\\ ⋮& =⋮\\ y_n& =a_0+a_1(x_n-x_0)+\dots +a_n(x_n-x_0)\dots (x_n-x_{n-1})\end{array}$

Yhtälöryhmän ratkaiseminen voidaan järjestää taulukossa, jota kutsutaan Newtonin erotustaulukoksi.

Newtonin menetelmä on melko suoraviivainen tapa laskea polynomin kertoimet. Kun uuden pisteen lisääminen johtaa Lagrangen menetelmässä uuteen laskutehtävään, tulee Newtonin menetelmässä lisätä vain uusi rivi ja suorittaa sille pikkulaskuja.

Lähteet

• Malline:Kirjaviite
• Ruotsalainen, Keijo: Numeeriset menetelmät Malline:Wayback (luentomoniste), Teknillinen tiedekunta, Oulun Yliopisto, 2010

Aiheesta muualla

• Lehtonen, Ari: 2. Interpolointi (pdf), kurssilla MATA145 Matematiikan laskennallisia menetelmiä, Jyväskylän yliopisto, 2012, viitattu 2.9.2015