Aitken séma

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2020. december 28-án felülvizsgált verziótól ; az ellenőrzéshez 1 szerkesztés szükséges .

Az Aitken-séma egy iteratív módszer a Lagrange-interpolációs polinom kiszámítására , amely lehetővé teszi új pontokról való információ bejuttatását a polinomba másodfokú időben az interpolációs csomópontok számának függvényében.

Definíció

Jelölje az alappontok interpolációjával kapott Lagrange-polinommal . Ekkor igaz a következő összefüggés $P_{i,\dots ,j}(x)$ $(x_{i},y_{i}),(x_{i+1},y_{i+1}),\dots ,(x_{j},y_{j})$

$P_{i}(x)=y_{i}$ (degenerált eset, a nulla fokú polinom állandó)

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

Bizonyítás

A bizonyítás indukcióval könnyen elvégezhető. Az általánosság elvesztése nélkül, az egyszerűség kedvéért elfogadjuk a , . $i=0$ $j=n$

Legyen és a megfelelő ponthalmazok Lagrange-polinomjai. Ez azt jelenti, hogy és $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}}}}$

Ha kijelöljük ; és akkor nyilvánvaló, hogy ${\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})}}}\jobbra)}=$

$=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}}$ ,

amely megegyezik a Lagrange-polinommal.

Teljesítmény

Számítási idő

A polinomok ismert együtthatóival a polinomok lineáris időben történő kiszámítása is lehetséges közvetlenül a képlet segítségével. $P_{0,\dots ,n-1}(x)$ $P_{1,\dots ,n}(x)$ $P_{0,\dots ,n}(x)$

Ha azonban az Aitkin-séma alkalmazását vesszük figyelembe, amikor új pontot adunk a bázispontok halmazához, akkor ebben az esetben is ismeretlen lesz, és lineáris időben kell számolni a és alapján . Ehhez előre ki kell számítani és így tovább. $(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)$

Így egy pont összeadása csak másodfokú időben lehetséges polinomok szekvenciális beszerzésével . Ha egyidejűleg a program már tárolja a -t, akkor az egyes szükséges polinomok kiszámítása a paraméterpontok számának függvényében lineáris időben megvalósítható. Ez aszimptotikusan összegzi az új pont hozzáadásához és ennek megfelelően a Lagrange-polinom kiszámításához szükséges időt egy előre meghatározott ponthalmazra. $P_{n-1,n}(x),P_{n-2,n-1,n}(x),\dots ,P_{2,\dots ,n}(x),P_{1 ,\pontok ,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$

Memória költségek

Ha az időoptimális számítási módszert használjuk, akkor szükséges a formájú polinomok tárolása . Ezen polinomok th-e memóriát igényel az együtthatók tárolásához, amihez összesen memória szükséges. $P_{i,\dots ,n}(x)(i=0,\dots ,n)$ $én$ $O(ni)$ $O(n^{2})$