Aitkens plan

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 28. december 2020; verifikation kræver 1 redigering .

Aitkens skema er en iterativ metode til beregning af Lagrange-interpolationspolynomiet , som gør det muligt at introducere information om nye punkter i polynomiet i kvadratisk tid med hensyn til antallet af interpolationsknuder.

Definition

Betegn ved Lagrange-polynomiet opnået ved interpolation af basispunkter . Så er følgende forhold sandt $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}$ (degenereret kasus, polynomium af grad nul er en konstant)

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

Bevis

Beviset er let at udføre ved induktion. Uden tab af almenhed accepterer vi for nemheds skyld , . $i=0$ $j=n$

Lad og vær Lagrange-polynomier for de tilsvarende sæt af punkter. Det betyder, at og $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}}}}$

Hvis vi udpeger ; og så er det indlysende ${\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}}$ ,

som er det samme som Lagrange-polynomiet.

Ydeevne

Beregningstid

Med kendte koefficienter af polynomier er beregningen af et polynomium også mulig i lineær tid direkte ved formlen. $P_{0,\dots ,n-1}(x)$ $P_{1,\dots ,n}(x)$ $P_{0,\dots ,n}(x)$

Men hvis vi overvejer anvendelsen af Aitkin-skemaet, når vi tilføjer et nyt punkt til sættet af basispunkter, vil det i dette tilfælde også være ukendt, og det skal beregnes i lineær tid baseret på og . For at gøre dette vil det være nødvendigt at forudberegne , og så videre. $(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)$

Tilføjelse af et punkt er således kun muligt i kvadratisk tid ved sekventielt at opnå polynomier . Hvis programmet på samme tid allerede vil lagre , så er beregningen af hvert af de nødvendige polynomier mulig i lineær tid med hensyn til antallet af parameterpunkter. Dette opsummerer asymptotisk tiden til at tilføje et nyt punkt og følgelig beregne Lagrange-polynomiet over et forudbestemt sæt af punkter. $P_{n-1,n}(x),P_{n-2,n-1,n}(x),\dots ,P_{2,\dots,n}(x),P_{1 ,\dots ,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$

Hukommelsesomkostninger

Hvis vi bruger den tidsoptimale beregningsmetode, er det nødvendigt at gemme polynomier af formen . th af disse polynomier kræver hukommelse til at gemme koefficienterne, hvilket kræver en total hukommelse. $P_{i,\dots ,n}(x)(i=0,\dots ,n)$ $jeg$ $O(ni)$ $O(n^{2})$