Shanks transformation

I numerisk analys är Shanks -transformationen en icke-linjär serieaccelerationsmetod för att öka konvergenshastigheten för en sekvens . Denna metod är uppkallad efter Daniel Shanks , som återupptäckte denna sekvenstransformation 1955. Den härleddes och publicerades först av R. Schmidt 1941.

Man kan bara beräkna ett fåtal termer av en störningsexpansion , vanligtvis inte mer än två eller tre, och nästan aldrig mer än sju. Den resulterande serien är ofta långsamt konvergent, eller till och med divergerande. Ändå innehåller dessa få termer en anmärkningsvärd mängd information, som utredaren bör göra sitt bästa för att få fram. Denna synpunkt har på ett övertygande sätt framställts i en förtjusande tidning av Shanks (1955), som visar ett antal fantastiska exempel, inklusive flera från flödesmekanik .

Milton D. Van Dyke (1975) Perturbation methods in fluid mechanics , sid. 202.

Formulering

För en sekvens $\left\{a_{m}\right\}_{m\in \mathbb {N} }$ serien

A=\sum _{m=0}^{\infty }a_{m}\,

ska fastställas. Först definieras delsumman ${\displaystyle A_{n}} som:$

A_{n}=\summa _{m=0}^{n}a_{m}\,

och bildar en ny sekvens $\left\{A_{n}\right\}_{n\in \mathbb {N} }$ . Förutsatt att serien konvergerar $A_{n}$ också att närma sig gränsen $A$ som $n\to \infty .$ Shanks-transformationen $S(A_{n})$ för sekvensen $A_{n}$ är den nya sekvensen som definieras av

\displaystyle S(A_{n})={\frac {A_{n+1}\,A_{n-1}\,-\, A_{n}^{2}}{A_{n+1}-2A_{n}+A_{n-1}}}=A_{n+1}-{\frac {(A_{n+1}- A_{n})^{2}}{(A_{n+1}-A_{n})-(A_{n}-A_{n-1})}}}

där denna sekvens $S(A_{n})$ ofta konvergerar snabbare än sekvensen $A_{n}.$ Ytterligare snabbhet kan erhållas genom upprepad användning av Shanks-transformationen, genom att beräkna $S^{2} (A_{n})=S(S(A_{n})),$ $S^{3}(A_{n })=S(S(S(A_{n}))),$ osv.

Observera att den icke-linjära transformationen som används i Shanks-transformationen i huvudsak är densamma som används i Aitkens delta-kvadratprocess så att precis som med Aitkens metod, uttrycket längst till höger i ${\displaystyle S(A_{ n})$ $\displaystyle S(A_{n})=A_{n+1}-{\frac {(A_{n+1}-A_{n})^{2}}{(A_{n+1}-A_{ n})-(A_{n}-A_{n-1})}}} )$ $s$ definition är mer numeriskt stabilt än uttrycket till vänster (dvs. ${\displaystyle S(A_{n})={\frac {A_{n+1}\,A_{n-1}\,-\,A_{ n}^{2}}{A_{n+1}-2A_{n}+A_{n-1}}}})$ . Både Aitkens metod och Shanks-transformationen fungerar på en sekvens, men sekvensen Shanks-transformationen fungerar på anses vanligtvis vara en sekvens av delsummor, även om vilken sekvens som helst kan ses som en sekvens av delsummor.

Exempel

Absolut fel som funktion av

n

i delsummorna

A_{n}

och efter applicering av Shanks-transformationen en eller flera gånger:

S(A_{ n}),

S^{2}(A_{n})

och

S^{3}(A_{n}).

Serien som används är

\scriptstyle 4\left(1- {\frac {1}{3}}+{\frac {1}{5}}-{\frac {1}{7}}+{\frac {1}{9}}-\cdots \right),

som har den exakta summan

\pi .

Som ett exempel, betrakta den långsamt konvergerande serien

4\sum _{k=0}^{\infty }(- 1)^{k}{\frac {1}{2k+1}}=4\left(1-{\frac {1}{3}}+{\frac {1}{5}}-{\frac {1}{7}}+\cdots \right)

som har den exakta summan π ≈ 3,14159265. Delsumman $A_{6}$ har bara ensiffrig noggrannhet, medan sexsiffrig noggrannhet kräver summering av cirka 400 000 termer.

I tabellen nedan, delsummorna $A_{n}$ , Shanks-transformationen $S(A_{n})$ på dem, såväl som de upprepade Shanks-transformationerna $S^{2}(A_{n})$ och $S^{3}(A_{n})$ ges för $n$ upp till 12. Figuren till höger visar det absoluta felet för delsummorna och Shanks-transformationsresultaten, vilket tydligt visar den förbättrade noggrannheten och konvergenshastigheten.

$n$	$A_{n}$	$S(A_{n})$	$S^{2}(A_{n})$	$S^{3}(A_{n})$
0	4,00000000	—	—	—
1	2,66666667	3,16666667	—	—
2	3,46666667	3,13333333	3,14210526	—
3	2,89523810	3,14523810	3,14145022	3,14159936
4	3,33968254	3,13968254	3,14164332	3,14159086
5	2,97604618	3,14271284	3,14157129	3,14159323
6	3,28373848	3,14088134	3,14160284	3,14159244
7	3,01707182	3,14207182	3,14158732	3,14159274
8	3,25236593	3,14125482	3,14159566	3,14159261
9	3,04183962	3,14183962	3,14159086	3,14159267
10	3,23231581	3,14140672	3,14159377	3,14159264
11	3,05840277	3,14173610	3,14159192	3,14159266
12	3,21840277	3,14147969	3,14159314	3,14159265

Shanks-transformationen $S(A_{1})$ har redan tvåsiffrig noggrannhet, medan de ursprungliga delsummorna bara etablerar samma noggrannhet vid $A_{24}.$ Anmärkningsvärt nog har $S^{3}(A_{3})$ sexsiffrig noggrannhet, erhållen från upprepade Shank-transformationer som tillämpas på de första sju termerna $A_{0},\ldots ,A_{6}.$ Som nämnts tidigare, $A_{n}$ erhåller endast 6-siffrig noggrannhet efter att ha summerat 400 000 termer.

Motivering

Shanks-transformationen motiveras av observationen att — för större $n$ — delsumman $A_{n}$ ganska ofta beter sig ungefär som

A_{n}=A+\alpha q^{n},\,

med $|q|<1$ så att sekvensen konvergerar transient till serieresultatet $A$ för $n\to \infty .$ Så för $n-1,$ $n$ och $n+1$ är respektive delsummor:

A_{n-1}=A+\alpha q^{n-1}\quad ,\qquad A_{n}=A+\alpha q^{n}\qquad {\text{and}}\qquad A_ {n+1}=A+\alpha q^{n+1}.

Dessa tre ekvationer innehåller tre okända: $A,$ $\alpha$ och $q.$ Att lösa för $A$ ger

A={\frac {A_{n+1}\,A_{n-1}\,-\,A_{n}^{2}}{A_{n+1}-2A_{n}+ A_{n-1}}}.

I det (exceptionella) fallet att nämnaren är lika med noll: då $A_{n}=A$ för alla $n.$

Generaliserad Shanks-transformation

Den generaliserade k :te ordningens Shanks-transformation ges som förhållandet mellan determinanterna :

S_{k}(A_{n})={\frac {\begin{vmatrix}A_{nk}&\cdots &A_{n-1}&A_{n}\\\Delta A_{nk}& \cdots &\Delta A_{n-1}&\Delta A_{n}\\\Delta A_{n-k+1}&\cdots &\Delta A_{n}&\Delta A_{n+1}\ \\vdots &&\vdots &\vdots \\\Delta A_{n-1}&\cdots &\Delta A_{n+k-2}&\Delta A_{n+k-1}\\\end{vmatrix }}{\begin{vmatrix}1&\cdots &1&1\\\Delta A_{nk}&\cdots &\Delta A_{n-1}&\Delta A_{n}\\\Delta A_{n-k+1 }&\cdots &\Delta A_{n}&\Delta A_{n+1}\\\vdots &&\vdots &\vdots \\\Delta A_{n-1}&\cdots &\Delta A_{n+ k-2}&\Delta A_{n+k-1}\\\end{vmatrix}}},

med ${\displaystyle \Delta A_{p}=A_{p+1}-A_{p}.} Det$ är lösningen av en modell för konvergensbeteendet för partialsummorna $A_{n}$ med $k$ distinkta transienter:

A_{n}=A+\sum _{p=1}^{k}\alpha _{p}q_{p}^{n}.

Denna modell för konvergensbeteendet innehåller $2k+1$ okända. Genom att utvärdera ovanstående ekvation vid elementen $A_{nk},A_{n-k+1},\ldots ,A_{n+ k}$ och löser $A,$ ovanstående uttryck för k: te ordningens Shanks-transformation erhålls. Den första ordningens generaliserade Shanks-transformationen är lika med den vanliga Shanks-transformationen: $S_{1}(A_{n})=S(A_{n}).$

Den generaliserade Shanks-transformationen är nära besläktad med Padé-approximanter och Padé-tabeller .

Obs: Beräkningen av determinanter kräver många aritmetiska operationer att göra, men Peter Wynn upptäckte en rekursiv utvärderingsprocedur som kallas epsilon-algoritm som undviker att beräkna determinanterna.

Se även

Anteckningar

Shanks, D. (1955), "Non-linear transformation of divergent and slowly convergent sequences", Journal of Mathematics and Physics , 34 : 1–42, doi : 10.1002/sapm19553411
Schmidt, R. (1941), "Om den numeriska lösningen av linjära simultane ekvationer med en iterativ metod", Philosophical Magazine , 32 : 369–383
Van Dyke, MD (1975), Perturbation methods in fluid mechanics (kommenterad utg.), Parabolic Press, ISBN 0-915760-01-0
Bender, CM ; Orszag, SA (1999), Avancerade matematiska metoder för forskare och ingenjörer , Springer, ISBN 0-387-98931-5
Weniger, EJ (1989). "Icke-linjära sekvenstransformationer för acceleration av konvergens och summering av divergerande serier". Datorfysikrapporter . 10 (5–6): 189–371. arXiv : math.NA/0306302 . Bibcode : 1989CoPhR..10..189W . doi : 10.1016/0167-7977(89)90011-7 .
Brezinski, C.; Redivo-Zaglia, M .; Saad, Y. (2018), "Shanks sequence transformations and Anderson acceleration", SIAM Review , 60 (3): 646–669, doi : 10.1137/17M1120725 , hdl : 11577/3270110
Senhadji, MN (2001), "On condition numbers of the Shanks transformation", J. Comput. Appl. Matematik. , 135 : 41–61
Wynn, P. (1962), "Accelerationstekniker för itererade vektor- och matrisproblem", Math. Comp. , 16 : 301-322