Newtonin interpolaatiokaavat

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 25. syyskuuta 2019 tarkistetusta versiosta . tarkastukset vaativat 7 muokkausta .

Newtonin interpolaatiokaavat ovat laskennallisia matematiikan kaavoja , joita käytetään polynomiinterpoloinnissa .

Kaavat

Annetaan joitain pareittain erillisiä pisteitä , joita kutsutaan myös interpolaatiosolmuiksi, ja joidenkin funktioiden arvot näissä kohdissa ovat tiedossa. ${\displaystyle x_{0},\,x_{1},\,\ldots ,\,x_{n))$ $f(x_{0}),\,f(x_{1}),\,\ldots ,\,f(x_{n})$ $f$

Epätasaisten solmujen tapaus

Jos kaikki vierekkäisten solmujen väliset etäisyydet ovat erilaisia, niin Newtonin polynomi muodostetaan kaavan [1] mukaisesti.

P_{n}(x)=f(x_{0})+(x-x_{0})f(x_{0};x_{1})+(x-x_{0})(x) -x_{1})f(x_{0};x_{1};x_{2})+\ldots +(x-x_{0})\ldots (x-x_{n-1})f(x_ {0};\ldots ;x_{n}),

missä on jaetun järjestyksen ero . $f(x_{0};\ldots ;x_{n})$ $n$

Jaetun eron ominaisuuksia käyttämällä voidaan osoittaa, että yllä oleva polynomi todella ratkaisee interpolointiongelman : [2]

Antaa olla Lagrangen interpolaatiopolynomi pisteille . Sitten . $L_{k}(x)$ ${\displaystyle x_{0},\,x_{1},\,\ldots ,\,x_{k))$ $L_{n}(x)=L_{0}(x)+(L_{1}(x)-L_{0}(x))+\ldots +(L_{n}(x)-L_ {n-1}(x))$

Harkitse : $L_{k}(x)-L_{k-1}(x)$

$L_{k}(x)-L_{k-1}(x)=\sum _{i=0}^{k}f(x_{i})*\prod _{j=0,j \neq i}^{k}{\frac {(x-x_{j})}{(x_{i}-x_{j))}}-\sum _{i=0}^{k-1} f(x_{i})*\prod _{j=0,j\neq i}^{k-1}{\frac {(x-x_{j})}{(x_{i}-x_{j })}}=$

$=\sum _{i=0}^{k-1}f(x_{i})*{\frac {(x-x_{0})*\ldots (x-x_{i-1} )*(x-x_{i+1})\ldots *(x-x_{k-1})}{(x_{i}-x_{0})*\ldots *(x_{i}-x_{ i-1})*(x_{i}-x_{i+1})*\ldots *(x_{i}-x_{k-1})}}*({\frac {x-x_{k} }{x_{i}-x_{k}}}-1)+$

$+f(x_{k})*{\frac {(x-x_{0})*\ldots *(x-x_{k-1})}{(x_{k}-x_{0} )*\ldots *(x_{k}-x_{k-1})}}$ .

Toisaalta kahden Lagrangen interpolaatiopolynomin ero on astepolynomi ja sen juuret tunnetaan - . $k-1$ ${\displaystyle x_{0},x_{1},x_{2},...,x_{k-1))$

Bezoutin lauseen mukaan saamme: . $L_{k}(x)-L_{k-1}(x)=a*(x-x_{0})*...*(x-x_{k-1})$

Löydämme : anna $a$ ${\näyttötyyli x=x_{k))$

$a=\sum _{i=0}^{k}{\frac {f(x_{i})}{(x_{i}-x_{0})*...*(x_{i }-x_{i-1})*(x_{i}-x_{i+1})*...*(x_{i}-x_{k})}}=f(x_{0};x_ {1};...;x_{k})$

Kun tulos on korvattu arvolla , saamme . $L_n(x)$ $P_n(x)$

Siten on osoitettu, että Newton-polynomi epätasaisesti etäisyydellä olevien solmujen tapauksessa osuu yhteen Lagrangen interpolaatiopolynomin kanssa ja ratkaisee siten interpolointiongelman.

Tasavälisten solmujen tapaus

Jos naapurisolmut ovat jollain kiinteällä etäisyydellä toisistaan , eli , niin Newtonin polynomi voidaan rakentaa joko alkaen (tässä tapauksessa ne puhuvat "eteenpäin interpoloinnista") tai alkaen ("taaksepäin interpolointi"). $h$ $x_{i}=x_{0}+ih$ $i=0,\ldots ,n$ $x_{0}$ $x_{n}$

Ensimmäisessä tapauksessa Newtonin polynomin kaava saa muotoa [3]

P_{n}(x)=y_{0}+q\Delta y_{0}+{\frac {q(q-1)}{2!}}\Delta ^{2}y_{0} +\lpisteet +{\frac {q(q-1)\lpisteet (q-n+1)}{n!}}\Delta ^{n}y_{0},

missä , ja muodon lausekkeet ovat äärellisiä eroja . $q=(x-x_{0})/h,\;y_{i}=f(x_{i})$ $\Delta ^{k}y_{0}$

Toisessa tapauksessa kaava saa muotoa [4]

P_{n}(x)=y_{n}+q\Delta y_{n-1}+{\frac {q(q+1)}{2!}}\Delta ^{2}y_{ n-2}+\lpisteet +{\frac {q(q+1)\lpisteet (q+n-1)}{n!}}\Delta ^{n}y_{0},

missä . $q=(x-x_{n})/h$

Sille , kaava $h = 1$

P_{n}(x)=\summa _{{m=0}}^{{n}}C_{x}^{m}\sum _{{k=0}}^{m}(-1) ^{{mk}}\,C_{m}^{k}\,f(k)

missä ovat binomikertoimet yleistettynä reaalilukujen alueeseen . $C_{x}^{m}$

Loput

Newton-polynomi on yksi Lagrangen polynomin muodoista , joten näiden kaavojen loput termit ovat samat [5] . Newtonin kaavan loppuosa voidaan kuitenkin kirjoittaa eri muodossa: $R_{n}(x)=f(x)-P_{n}(x)$