Aitkenin suunnitelma

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 28. joulukuuta 2020 tarkistetusta versiosta . vahvistus vaatii 1 muokkauksen .

Aitkenin kaavio on iteratiivinen menetelmä Lagrangen interpolaatiopolynomin laskemiseen , mikä mahdollistaa uusien pisteiden tuomisen polynomiin neliössä suhteessa interpolointisolmujen määrään.

Määritelmä

Merkitään peruspisteiden interpoloimalla saadulla Lagrangen polynomilla . Sitten seuraava suhde on totta $P_{i,\dots ,j}(x)$ ${\näyttötyyli (x_{i},y_{i}),(x_{i+1},y_{i+1}),\dots ,(x_{j},y_{j})}$

$P_{i}(x)=y_{i}$ (degeneroitunut tapaus, nollaasteen polynomi on vakio)

$P_{i,\dots ,j}(x)={\frac {1}{x_{j}-x_{i))}{\begin{vmatrix}x-x_{i}&P_{i, \pisteet ,j-1}(x)\\x-x_{j}&P_{i+1,\pisteet ,j}(x)\end{vmatrix}}$

Todiste

Todistus on helppo tehdä induktiolla. Yleisyyttä menettämättä hyväksymme mukavuuden vuoksi , . $i = 0$ $j = n$

Olkoon ja Lagrangen polynomit vastaaville pistejoukoille. Tämä tarkoittaa, että ja $P_{0,\dots ,n-1}(x)$ $P_{1,\dots ,n}(x)$ $P_{0,\dots ,n-1}(x)=\sum \limits _{i=0}^{n-1}{y_{i}\prod \limits _{j=0;j \not =i}^{n-1}{\frac {x-x_{j}}{x_{i}-x_{j}}}}$ $P_{1,\dots ,n}(x)=\sum \limits _{i=1}^{n}{y_{i}\prod \limits _{j=1;j\not =i }^{n}{\frac {x-x_{j}}{x_{i}-x_{j}}}}$

Jos nimeämme ; ja sitten se on selvää ${\displaystyle A_{i}=\prod \limits _{j=0;j\not =i}^{n}{(x-x_{j)))))$ $T_{i}=y_{i}\prod \limits _{j=0;j\not =i}^{n}{\frac {x-x_{j}}{x_{i}-x_ {j}}}$ ${\displaystyle X_{i}=\prod \limits _{j=1;j\not =i}^{n-1}{(x_{i}-x_{j)))))$

${\frac {1}{x_{n}-x_{0}}}{\begin{vmatrix}x-x_{0}&P_{0,\dots ,n-1}(x)\\x -x_{n}&P_{1,\dots ,n}(x)\end{vmatrix}}=T_{0}+T_{n}+\sum \limits _{i=1}^{n-1} {y_{i}\left({{\frac {A_{i}}{X_{i}(x_{i}-x_{n})(x_{n}-x_{0))}}-{\ frac {A_{i}}{X_{i}(x_{i}-x_{0})(x_{n}-x_{0})}}}\oikea)}=$

$=T_{0}+T_{n}+\sum \limits _{i=1}^{n-1}{y_{i}{\frac {A_{i}x_{n}-A_{ i}x_{0}}{X_{i}(x_{i}-x_{n})(x_{i}-x_{0})(x_{n}-x_{0})}}}=T_ {0}+T_{n}+\sum \limits _{i=1}^{n-1}{y_{i}{\frac {A_{i}}{X_{i}(x_{i}- x_{n})(x_{i}-x_{0})}}}=\sum \limits _{i=0}^{n}{T_{i}}$ ,

joka on sama kuin Lagrangen polynomi.

Suorituskyky

Laskuaika

Tunnetuilla polynomikertoimilla polynomin laskenta on mahdollista myös lineaarisessa ajassa suoraan kaavan avulla. $P_{0,\dots ,n-1}(x)$ $P_{1,\dots ,n}(x)$ $P_{0,\dots ,n}(x)$

Jos kuitenkin otetaan huomioon Aitkin-kaavion soveltaminen lisättäessä uusi piste peruspisteiden joukkoon, niin se on tässäkin tapauksessa tuntematon ja se on laskettava lineaarisessa ajassa ja perusteella . Tätä varten on tarpeen laskea etukäteen ja niin edelleen. ${\näyttötyyli (x_{n},y_{n})}$ $P_{1,\dots ,n}(x)$ $P_{1,\dots ,n-1}(x)$ $P_{2,\dots ,n}(x)$ $P_{2,\dots ,n}(x)$

Näin ollen pisteen lisääminen on mahdollista vain neliössä saamalla peräkkäin polynomeja . Jos samaan aikaan ohjelma jo tallentaa , niin jokaisen vaaditun polynomin laskenta on mahdollista lineaarisessa ajassa suhteessa parametripisteiden määrään. Tämä summaa asymptoottisesti ajan uuden pisteen lisäämiseen ja vastaavasti Lagrangen polynomin laskemiseen ennalta määrätylle pistejoukolle . $P_{n-1,n}(x),P_{n-2,n-1,n}(x),\pisteet ,P_{2,\pisteet ,n}(x),P_{1 ,\pisteet ,n}(x)$ $P_{1,\dots ,n-1}(x),P_{2,\dots ,n-1}(x),\dots ,P_{n-2,n-1}(x), P_{n-1}(x)$ $O(n^{2})$ $O(n^{3})$ $n$

Muisti maksaa

Jos käytämme aikaoptimaalista laskentamenetelmää, on tarpeen tallentaa muotoa olevat polynomit . Näiden polynomien th vaatii muistia kertoimien tallentamiseen, mikä vaatii yhteensä muistia. $P_{i,\dots ,n}(x)(i=0,\dots ,n)$ $i$ $O(ni)$ $O(n^{2})$