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 formula_1 ja formula_2 ja y-koordinaateilla tarkoitetaan funktion formula_3 arvoja, voidaan suoran yhtälöllä muodostaa ensimmäisen asteen polynomi 
formula_4 
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
formula_5 on nolla sijoituksella formula_6 ja formula_7 sijoituksella formula_8
ja
formula_9 on nolla sijoituksella formula_8 ja formula_11 sijoituksella formula_12
Polynomi saadaan näiden lausekkeiden summana
formula_13 
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 formula_14 formula_2 ja formula_16 voidaan suorittaa viimeksi mainitulla tavalla. Muodostetaan lausekkeet, jotka antavat arvoksi nolla muissa pisteissä paitsi "omassa" pisteessä. Seuraava termi on nolla, kun siihen sijoitetaan formula_6 tai formula_18, mutta se on formula_7, kun siihen sijoitetaan formula_8 
formula_21
Polynomi saadaan kolmella termillä
formula_22 
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.
Lagrangen interpolaatio luodaan käyttämällä yleistä Lagrangen interpolaatiopolynomia. Se voidaan kirjoittaa muodossa 
formula_23
missä ensimmäinen kantapolynomi formula_24 on
formula_25
ja formula_26 kantapolynomi on
formula_27
Polynomin aste on korkeintaan formula_28, jos pisteitä on formula_29. Mikäli osa pisteistä ovat samoja tai ne ovat kollineaarisia, laskee polynomin asteluku alle formula_28. Lagrangen interpolaatiopolynomi on vaikea laskea tietokoneella, sillä pyöristysvirheet aiheuttavat joskus yli- tai alivuotoa.
Newtonin interpolaatio.
Newtoinin interpolaatiomenetelmässä polynomille haetaan kertoimet muodossa
formula_31
Kertoimet määräytyvät ehdosta
formula_32 formula_33
joka johtaa rekursiivisesti ratkeavaan yhtälöryhmään
formula_34
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.