Aitkenovo schéma

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 28. prosince 2020; ověření vyžaduje 1 úpravu .

Aitkenovo schéma je iterativní metodou pro výpočet Lagrangeova interpolačního polynomu , která umožňuje zavádět informace o nových bodech do polynomu v kvadratickém čase s ohledem na počet interpolačních uzlů.

Definice

Označme Lagrangeovým polynomem získaným interpolací základních bodů . Pak platí následující vztah $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}$ (degenerovaný případ, polynom nultého stupně je konstanta)

$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,\tečky ,j}(x)\end{vmatrix}}$

Důkaz

Důkaz lze snadno provést indukcí. Bez ztráty obecnosti, pro pohodlí přijímáme , . $i=0$ $j=n$

Nechť a být Lagrangeovy polynomy pro odpovídající množiny bodů. To znamená, že a $P_{0,\tečky ,n-1}(x)$ $P_{1,\tečky ,n}(x)$ $P_{0,\tečky ,n-1}(x)=\součet \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,\tečky ,n}(x)=\součet \limits _{i=1}^{n}{y_{i}\prod \limits _{j=1;j\not =i }^{n}{\frac {x-x_{j}}{x_{i}-x_{j}}}}$

Pokud určíme ; a pak je zřejmé, že ${\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,\tečky ,n}(x)\end{vmatrix}}=T_{0}+T_{n}+\součet \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}+\součet \limits _{i=1}^{n-1}{y_{i}{\frac {A_{i}}{X_{i}(x_{i}- x_{n})(x_{i}-x_{0})}}}=\součet \limits _{i=0}^{n}{T_{i}}$ ,

což je stejné jako Lagrangeův polynom.

Výkon

Doba výpočtu

Se známými koeficienty polynomů je výpočet polynomu možný také v lineárním čase přímo podle vzorce. $P_{0,\tečky ,n-1}(x)$ $P_{1,\tečky ,n}(x)$ $P_{0,\tečky ,n}(x)$

Pokud však vezmeme v úvahu aplikaci Aitkinova schématu při přidávání nového bodu do množiny základních bodů, pak v tomto případě bude také neznámý a bude nutné jej vypočítat v lineárním čase na základě a . K tomu bude nutné provést předběžný výpočet atd. $(x_{n},y_{n})$ $P_{1,\tečky ,n}(x)$ $P_{1,\tečky ,n-1}(x)$ $P_{2,\tečky ,n}(x)$ $P_{2,\tečky ,n}(x)$

Přidání bodu je tedy možné pouze v kvadratickém čase postupným získáváním polynomů . Pokud současně bude program již ukládat , pak je výpočet každého z požadovaných polynomů proveditelný v lineárním čase s ohledem na počet bodů parametru. To asymptoticky sčítá čas pro přidání nového bodu a podle toho pro výpočet Lagrangeova polynomu přes předem určenou množinu bodů. $P_{n-1,n}(x),P_{n-2,n-1,n}(x),\tečky ,P_{2,\tečky ,n}(x),P_{1 ,\tečky ,n}(x)$ $P_{1,\tečky ,n-1}(x),P_{2,\tečky ,n-1}(x),\tečky ,P_{n-2,n-1}(x), P_{n-1}(x)$ $O(n^{2})$ $O(n^{3})$ $n$

Náklady na paměť

Pokud použijeme metodu časově optimálního výpočtu, pak je nutné uložit polynomy tvaru . th z těchto polynomů vyžaduje paměť pro uložení koeficientů, což vyžaduje celkovou paměť. $P_{i,\tečky ,n}(x)(i=0,\tečky ,n)$ $i$ $O(ni)$ $O(n^{2})$