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.”126. o.

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 egy rendű közelítése egy alakú függvénynek, tehát . Ekkor

a Richardson extrapoláltja A(h)-nak; azaz a hm 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 alakú hibaképlettel, ahol ai ismeretlen és ki ismert állandók úgy, hogy hki > hki+1.

A keresett érték megadható a

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

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

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

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

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 (hk0). 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:

úgy, hogy

, .

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

Példa

Taylor-sorbafejtéssel,

f(x) deriváltja megadható

formában.

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

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

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

lesz.

Az új közelítéshez

újraextrapolálhatunk,

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 , mit.edu Richardson-Extrapolation Richardson extrapolation on a website of Robert Israel (University of British Columbia)

Kategória:Numerikus analízis