Richardson-extrapoláció

Ez a szócikk vagy szakasz lektorálásra, tartalmi javításokra szorul. A felmerült kifogásokat a szócikk vitalapja részletezi (vagy extrém esetben a szócikk szövegében elhelyezett, kikommentelt szövegrészek). Ha nincs indoklás a vitalapon (vagy szerkesztési módban a szövegközben), bátran távolítsd el a sablont! Csak akkor tedd a lap tetejére ezt a sablont, ha az egész cikk megszövegezése hibás. Ha nem, az adott szakaszba tedd, így segítve a lektorok munkáját!

A numerikus analízisben a Richardson extrapoláció egy sorozatgyorsító módszer, amivel felgyorsíthatjuk egy sorozat konvergenciáját. Az eljárás Lewis Fry Richardson angol matematikusról kapta a nevét, aki a technikát a 20. század elején vezette be.^[1][2] Birkhoff és Rota szerint „…a gyakorlati számításokban a hasznosságát nem igazán lehet túlbecsülni.”^[3]

Gyakorlati alkalmazásai között szerepel a Romberg integrálás, amely Richardson-extrapolációt alkalmaz a trapéz-szabályra, és a Bulirsch–Stoer-algoritmus, amely differenciál egyenletek megoldására használható.

Tegyük fel, hogy ${\displaystyle A(h)\;}$ egy ${\displaystyle h^{n}\;}$ rendű közelítése egy ${\displaystyle A=\lim _{h\to 0}A(h)}$ alakú függvénynek, tehát ${\displaystyle A-A(h)=a_{n}h^{n}+O(h^{m}),~a_{n}\neq 0,~m>n}$. Ekkor

${\displaystyle R(h)=A(h/2)+{\frac {A(h/2)-A(h)}{2^{n}-1}}={\frac {2^{n}\,A(h/2)-A(h)}{2^{n}-1}}}$

a Richardson extrapoláltja A(h)-nak; azaz a h^m rendű megközelítése A-nak, ha m>n.

Általános esetben, a „2” tényező helyettesíthető más tényezővel, a lent bemutatott módon.

Gyakran könnyebb elérni egy adott pontosságot R(h)-t használva A(h') helyett, egy sokkal kisebb h' -val, ami problémákat okozhat a korlátozott pontosság (kerekítési hiba) és/vagy a szükséges számítások többlete miatt (ld. lenti példák).

Legyen A(h) egy megközelítése A-nak, ami a pozitív h lépésszámtól függ, egy ${\displaystyle A-A(h)=a_{0}h^{k_{0}}+a_{1}h^{k_{1}}+a_{2}h^{k_{2}}+\cdots }$ alakú hibaképlettel, ahol a_i ismeretlen és k_i ismert állandók úgy, hogy h^k_i > h^k_i+1.

A keresett érték megadható a

${\displaystyle A=A(h)+a_{0}h^{k_{0}}+a_{1}h^{k_{1}}+a_{2}h^{k_{2}}+\cdots }$

összefüggéssel, ami leegyszerűsíthető a nagy O jelöléssel

${\displaystyle A=A(h)+a_{0}h^{k_{0}}+O(h^{k_{1}}).\,\!}$

h lépésközt használva és h / t-t egy adott t-re, a két képlet A-ra:

${\displaystyle A=A(h)+a_{0}h^{k_{0}}+O(h^{k_{1}})\,\!}$

${\displaystyle A=A\!\left({\frac {h}{t}}\right)+a_{0}\left({\frac {h}{t}}\right)^{k_{0}}+O(h^{k_{1}}).}$

A második egyenletet beszorozva t^k₀-val és kivonva az elsőt kapjuk a

${\displaystyle (t^{k_{0}}-1)A=t^{k_{0}}A\left({\frac {h}{t}}\right)-A(h)+O(h^{k_{1}})}$

egyenletet, amely A-ra megoldva a következőt adja:

${\displaystyle A={\frac {t^{k_{0}}A\left({\frac {h}{t}}\right)-A(h)}{t^{k_{0}}-1}}+O(h^{k_{1}}).}$

Az eljárás által egy jobb közelítést értünk el A-ra, kiküszöbölve a legnagyobb hibatényezőt, O-t (h^k₀). Az eljárás megismételhető még több hibatényező eltávolításáért és ezáltal még jobb közelítés eléréséért.

Egy általános rekurzív összefüggés állapítható meg a közelítésekre:

${\displaystyle A_{i+1}(h)={\frac {t^{k_{i}}A_{i}\left({\frac {h}{t}}\right)-A_{i}(h)}{t^{k_{i}}-1}}}$

úgy, hogy

${\displaystyle A=A_{i+1}(h)+O(h^{k_{i+1}})}$, ${\displaystyle A_{0}=A(h)}$.

Megjegyzendő, hogy a Richardson-extrapoláció lineáris sorozat-transzformációnak fogható fel.

Taylor-sorbafejtéssel,

${\displaystyle f(x+h)=f(x)+f'(x)h+{\frac {f''(x)}{2}}h^{2}+\cdots }$

f(x) deriváltja megadható

${\displaystyle f'(x)={\frac {f(x+h)-f(x)}{h}}-{\frac {f''(x)}{2}}h+\cdots .}$

formában.

Ha a derivált eredeti közelítéseit

${\displaystyle A_{0}(h)={\frac {f(x+h)-f(x)}{h}}}$

formában választjuk meg, akkor k_i = i+1.

t = 2 esetben az első extrapoláció A-ra

${\displaystyle A=2A_{0}\!\left({\frac {h}{2}}\right)-A_{0}(h)+O(h^{2}).}$ lesz.

Az új közelítéshez

${\displaystyle A_{1}(h)=2A_{0}\!\left({\frac {h}{2}}\right)-A_{0}(h)}$

újraextrapolálhatunk,

${\displaystyle A={\frac {4A_{1}\!\left({\frac {h}{2}}\right)-A_{1}(h)}{3}}+O(h^{3}).}$ kapva

.

• Extrapolation Methods. Theory and Practice by C. Brezinski and M. Redivo Zaglia, North-Holland, 1991

• Module for Richardson's Extrapolation, fullerton.edu
• Fundamental Methods of Numerical Extrapolation With Applications Archiválva 2011. június 29-i dátummal a Wayback Machine-ben, mit.edu
• Richardson-Extrapolation
• Richardson extrapolation on a website of Robert Israel (University of British Columbia)