Aitkensův trojúhelníkový proces - Aitkens delta-squared process - Wikipedia

v numerická analýza, Aitkenův delta-kvadratický proces nebo Aitkenova extrapolace je sériové zrychlení metoda používaná pro zrychlení rychlost konvergence sekvence. Je pojmenován po Alexander Aitken, který tuto metodu zavedl v roce 1926.^[1] Jeho raná podoba byla známa Seki Kōwa (konec 17. století) a byl nalezen pro opravu kruhu, tj. výpočet π. Je to nejužitečnější pro urychlení konvergence posloupnosti, která se sbíhá lineárně.

Definice

Vzhledem k posloupnosti ${ displaystyle X = {(x_ {n})} _ {n in mathbb {N}}}$, jeden spojuje s touto sekvencí novou sekvenci

${ displaystyle AX = { left ({ frac {x_ {n} , x_ {n + 2} -x_ {n + 1} ^ {2}} {x_ {n} + x_ {n + 2} - 2 , x_ {n + 1}}} right)} _ {n in mathbb {Z} ^ {*}},}$

které mohou, s vylepšenými numerická stabilita, psát také jako

${ displaystyle (AX) _ {n} = x_ {n} - { frac {( Delta x_ {n}) ^ {2}} { Delta ^ {2} x_ {n}}},}$

nebo ekvivalentně jako

${ displaystyle (AX) _ {n} = x_ {n + 2} - { frac {( Delta x_ {n + 1}) ^ {2}} { Delta ^ {2} x_ {n}}} = x_ {n + 2} - { frac {(x_ {n + 2} -x_ {n + 1}) ^ {2}} {(x_ {n + 2} -x_ {n + 1}) - ( x_ {n + 1} -x_ {n})}}}$

kde

${ displaystyle Delta x_ {n} = {(x_ {n + 1} -x_ {n})}, Delta x_ {n + 1} = {(x_ {n + 2} -x_ {n + 1 })},}$

a

${ displaystyle Delta ^ {2} x_ {n} = x_ {n} -2x_ {n + 1} + x_ {n + 2} = Delta x_ {n + 1} - Delta x_ {n}, }$

pro ${ displaystyle n = 0,1,2,3, tečky ,}$

Očividně, ${ displaystyle AX}$ je špatně definováno, pokud ${ displaystyle Delta ^ {2} x}$ obsahuje nulový prvek nebo ekvivalentně, pokud posloupnost první rozdíly má opakující se termín.

Z teoretického hlediska, pokud k tomu dojde pouze pro konečný počet indexů, dalo by se snadno souhlasit s uvažováním posloupnosti ${ displaystyle AX}$ omezeno na indexy ${ displaystyle n> n_ {0}}$ s dostatečně velkým ${ displaystyle n_ {0}}$. Z praktického hlediska se obecně spíše zvažuje pouze prvních pár výrazů posloupnosti, které obvykle poskytují potřebnou přesnost. Navíc při numerickém výpočtu sekvence je třeba se postarat o zastavení výpočtu, když chyby zaokrouhlování ve jmenovateli se stanou příliš velkými, kde operace Δ² může zrušit příliš mnoho významné číslice. (Bylo by lepší použít numerický výpočet ${ displaystyle Delta x_ {n + 1} - Delta x_ {n} = (x_ {n + 2} -x_ {n + 1}) - (x_ {n + 1} -x_ {n}) }$ spíše než ${ displaystyle x_ {n} -2x_ {n + 1} + x_ {n + 2} }$ .)

Vlastnosti

Aitkenův delta-kvadratický proces je metoda zrychlení konvergence a konkrétní případ nelineárního sekvenční transformace.

${ displaystyle x}$ vůle konvergovat lineárně na ${ displaystyle ell}$ pokud existuje takové číslo μ ∈ (0, 1)

${ displaystyle lim _ {n to infty} { frac {| x_ {n + 1} - ell |} {| x_ {n} - ell |}} = mu.}$

Aitkenova metoda urychlí sekvenci ${ displaystyle x_ {n}}$ -li ${ displaystyle lim _ {n to infty} { frac {(sekera) _ {n} - ell} {x_ {n} - ell}} = 0.}$

${ displaystyle A}$ není lineární operátor, ale konstantní člen vypadne, viz: ${ displaystyle A [x- ell] = Ax- ell}$, pokud ${ displaystyle ell}$ je konstanta. To je zřejmé z výrazu ${ displaystyle Axe}$ z hlediska konečný rozdíl operátor ${ displaystyle Delta}$.

Ačkoli se nový proces obecně nesbližuje kvadraticky, lze ukázat, že pro a pevný bod proces, tedy pro iterovaná funkce sekvence ${ displaystyle x_ {n + 1} = f (x_ {n})}$ pro nějakou funkci ${ displaystyle f}$konvergující do pevného bodu je konvergence kvadratická. V tomto případě je technika známá jako Steffensenova metoda.

Empiricky A-operace eliminuje "nejdůležitější chybový termín". Lze to zkontrolovat zvážením sekvence formuláře ${ displaystyle x_ {n} = ell + a ^ {n} + b ^ {n}}$, kde ${ displaystyle 0$:Sekvence ${ displaystyle Axe}$ poté přejde na limit jako ${ displaystyle b ^ {n}}$ jde na nulu.

Geometricky, graf exponenciální funkce ${ displaystyle f (t)}$ to uspokojuje ${ displaystyle f (n) = x_ {n}}$, ${ displaystyle f (n + 1) = x_ {n + 1}}$ a ${ displaystyle f (n + 2) = x_ {n + 2}}$ má vodorovnou asymptotu v ${ displaystyle { frac {x_ {n} x_ {n + 2} -x_ {n + 1} ^ {2}} {x_ {n} -2x_ {n + 1} + x_ {n + 2}}} }$ (li ${ displaystyle x_ {n} -2x_ {n + 1} + x_ {n + 2} neq 0}$).

Lze také ukázat, že pokud ${ displaystyle x}$ jde na hranici svých možností ${ displaystyle ell}$ rychlostí přísně vyšší než 1, ${ displaystyle Axe}$ nemá lepší míru konvergence. (V praxi má člověk zřídka např. Kvadratickou konvergenci, což by znamenalo přes 30 resp. 100 správných desetinných míst po 5 resp. 7 iteracích (počínaje 1 správnou číslicí); v takovém případě obvykle není nutná akcelerace.)

V praxi, ${ displaystyle Axe}$ konverguje mnohem rychleji k limitu než ${ displaystyle x}$ dělá, jak ukazují níže uvedené příkladové výpočty. Výpočet je obvykle mnohem levnější ${ displaystyle Axe}$ (zahrnující pouze výpočet rozdílů, jedno násobení a jedno dělení), než vypočítat mnohem více členů posloupnosti ${ displaystyle x}$. Je však třeba dbát na to, aby se zabránilo zavádění chyb z důvodu nedostatečné přesnosti při výpočtu rozdíly v čitateli a jmenovateli výrazu.

Ukázkové výpočty

Příklad 1: Hodnota ${ displaystyle { sqrt {2}} přibližně 1,4142136}$ lze aproximovat předpokládáním počáteční hodnoty pro ${ displaystyle a_ {0}}$ a iterace následujícího:

${ displaystyle a_ {n + 1} = { frac {a_ {n} + { frac {2} {a_ {n}}}} {2}}.}$

Začínání s ${ displaystyle a_ {0} = 1:}$

Zde stojí za zmínku, že Aitkenova metoda neukládá dva iterační kroky; výpočet prvních tří Sekera požadovaných hodnot prvních pět X hodnoty. Také druhá hodnota Ax je rozhodně horší než hodnota 4. x, většinou kvůli skutečnosti, že Aitkenův proces předpokládá spíše lineární než kvadratickou konvergenci^{[Citace je zapotřebí ]}.

Příklad 2: Hodnota ${ displaystyle { frac { pi} {4}}}$ lze vypočítat jako nekonečný součet:

${ displaystyle { frac { pi} {4}} = součet _ {n = 0} ^ { infty} { frac {(-1) ^ {n}} {2n + 1}} přibližně 0,785398 }$

V tomto příkladu je Aitkenova metoda aplikována na sublearně konvergující řadu, což značně urychluje konvergenci. Je to stále sublimační, ale mnohem rychlejší než původní konvergence: první hodnota Ax, jejíž výpočet vyžadoval první tři hodnoty x, je blíže limitu než hodnota osmého x.

Příklad pseudokódu pro Aitkenovu extrapolaci

Následuje příklad použití Aitkenovy extrapolace k nalezení limitu sekvence ${ displaystyle x_ {n + 1} = f (x_ {n})}$ když je dán ${ displaystyle x_ {0}}$, což předpokládáme jako pevný bod ${ displaystyle alpha = f ( alpha)}$. Mohli bychom například mít ${ displaystyle x_ {n + 1} = { frac {1} {2}} (x_ {n} + { frac {2} {x_ {n}}})}$ s ${ displaystyle x_ {0} = 1}$ který má pevný bod ${ displaystyle { sqrt {2}}}$ aby ${ displaystyle f (x) = { frac {1} {2}} (x + { frac {2} {x}})}$ (vidět Metody výpočtu druhé odmocniny ).

Tento pseudokód také počítá Aitkenovu aproximaci ${ displaystyle f '( alpha)}$. Extrapoláty Aitken budou označeny aitkenX. Musíme zkontrolovat, zda během výpočtu extrapolátu je jmenovatel příliš malý, což by se mohlo stát, pokud již máme velkou míru přesnosti, protože jinak by mohlo dojít k velké chybě. Toto malé číslo označíme epsilon.

% Tyto volby závisí na řešeném problémux0 = 1                      % Počáteční hodnotaF(X) = (1/2)*(X + 2/X)      % Funkce, která najde další prvek v pořadítolerance = 10^-10          Je požadována% 10místná přesnostepsilon = 10^-16            % Nechci dělit o číslo menší než totomaxIterace = 20          % Nedovolte, aby iterace pokračovaly neomezeně dlouhohaveWeFoundSolution = Nepravdivé % Byli jsme schopni najít řešení v rámci požadované tolerance? ještě ne.pro i = 1 : maxIterace     x1 = F(x0)    x2 = F(x1)    -li (x1 ~= x0)        lambda = absolutní hodnota((x2 - x1)/(x1 - x0))  % VOLITELNÉ: vypočítá aproximaci | f '(fixedPoint) |, která je označena lambda    konec    jmenovatel = (x2 - x1) - (x1 - x0);    -li (absolutní hodnota(jmenovatel) < epsilon)          % Nechci dělit příliš malým počtem        tisk(„UPOZORNĚNÍ: jmenovatel je příliš malý“)        přestávka;                                        % Opusťte smyčku    konec    aitkenX = x2 - ( (x2 - x1)^2 )/jmenovatel        -li (absolutní hodnota(aitkenX - x2) < tolerance)       % Pokud je výsledek v toleranci        tisk(„Pevný bod je“, aitkenX))        % Zobrazte výsledek extrapolace Aitken        haveWeFoundSolution = skutečný        přestávka;                                        % Hotovo, tak opusťte smyčku    konec    x0 = aitkenX                                      % Aktualizujte x0 a začněte znovu     konec-li (haveWeFoundSolution == Nepravdivé)   % Pokud bychom nebyli schopni najít řešení v rámci požadované tolerance    tisk(„Varování: Nelze najít řešení v rámci požadované tolerance“, tolerance)    tisk(„Poslední vypočítaný extrapolát byl“, aitkenX)konec

Viz také

• Míra konvergence
• Limit posloupnosti
• Iterace s pevným bodem
• Richardsonova extrapolace
• Sekvenční transformace
• Shanksova transformace
• Steffensenova metoda

Poznámky

Reference

• William H. Press, et al., Numerické recepty v jazyce C.(1987) Cambridge University Press, ISBN  0-521-43108-5 (Vidět oddíl 5.1 )
• Abramowitz a Stegun, Příručka matematických funkcí, oddíl 3.9.7
• Kendall E. Atkinson, Úvod do numerické analýzy(1989) John Wiley & Sons, Inc, ISBN  0-471-62489-6