Richardson-extrapoláció

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. Birkhoff és Rota szerint „…a gyakorlati számításokban a hasznosságát nem igazán lehet túlbecsülni.” 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ó.

Példa

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

$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).

Általános képlet

Legyen A(h) egy megközelítése A-nak, ami a pozitív h lépésszámtól függ, egy $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

$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

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

$A=A(h)+a_0{h}^{k_0}+O(h^{k_1})$

$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

$(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:

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

$A_{i+1}(h)=\frac{t^{k_i}{A}_i\left(\frac{h}{t}\right)-A_i(h)}{t^{k_i}-1}$

úgy, hogy

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

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

Példa

Taylor-sorbafejtéssel,

$f(x+h)=f(x)+f^{\prime }(x)h+\frac{f^{″}(x)}{2}{h}^2+\cdots$

f(x) deriváltja megadható

$f^{\prime }(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

$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

$A=2A_0\left(\frac{h}{2}\right)-A_0(h)+O(h^2).$ lesz.

Az új közelítéshez

$A_1(h)=2A_0\left(\frac{h}{2}\right)-A_0(h)$

újraextrapolálhatunk,

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

.

Hivatkozások

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

Külső linkek

• 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)