Schema lui Aitken

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 28 decembrie 2020; verificarea necesită 1 editare .

Schema lui Aitken este o metodă iterativă de calculare a polinomului de interpolare Lagrange , care permite introducerea de informații despre noi puncte în polinom în timp patratic în raport cu numărul de noduri de interpolare.

Definiție

Se notează prin polinomul Lagrange obţinut prin interpolarea punctelor de bază . Atunci următoarea relație este adevărată $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}$ (caz degenerat, polinomul de grad zero este o constantă)

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

Dovada

Dovada este ușor de făcut prin inducție. Fără a pierde generalitatea, pentru comoditate acceptăm , . $i=0$ $j=n$

Fie și polinoamele Lagrange pentru seturile corespunzătoare de puncte. Aceasta înseamnă că și $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}}}}$

Dacă desemnăm ; și , atunci este evident că ${\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})}}}\right)}=$

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

care este același cu polinomul Lagrange.

Performanță

Timp de calcul

Cu coeficienți cunoscuți ai polinoamelor , calculul unui polinom este posibil și în timp liniar direct prin formulă. $P_{0,\dots ,n-1}(x)$ $P_{1,\dots ,n}(x)$ $P_{0,\dots ,n}(x)$

Totuși, dacă luăm în considerare aplicarea schemei Aitkin la adăugarea unui nou punct la setul de puncte de bază, atunci și în acest caz va fi de asemenea necunoscut și va trebui calculat în timp liniar pe baza și . Pentru a face acest lucru, va fi necesar să se precalculeze și așa mai departe. $(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)$

Astfel, adăugarea unui punct este posibilă numai în timp patratic prin obținerea secvențială de polinoame . Dacă, în același timp, programul va stoca deja , atunci calculul fiecăruia dintre polinoamele necesare este fezabil în timp liniar în raport cu numărul de puncte ale parametrilor. Aceasta însumează asimptotic timpul necesar pentru a adăuga un nou punct și, în consecință, pentru a calcula polinomul Lagrange pe un set predeterminat de puncte. $P_{n-1,n}(x),P_{n-2,n-1,n}(x),\dots,P_{2,\dots,n}(x),P_{1 ,\puncte ,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$

Costurile memoriei

Dacă folosim metoda de calcul optimă în timp, atunci este necesar să stocăm polinoame de forma . Al-lea dintre aceste polinoame necesită memorie pentru a stoca coeficienții, ceea ce necesită o memorie totală. $P_{i,\dots,n}(x)(i=0,\dots,n)$ $i$ $O(ni)$ $O(n^{2})$