Richardson-extrapoláció

A Wikipédiából, a szabad enciklopédiából

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ó.

Példa[szerkesztés | forrásszöveg szerkesztése]

Tegyük fel, hogy A(h)\; egy h^n\; rendű közelítése egy A=\lim_{h\to 0}A(h) alakú függvénynek, tehát A-A(h) = a_n h^n+O(h^m),~a_n\ne0,~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 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[szerkesztés | forrásszöveg szerkesztése]

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_0h^{k_0} + a_1h^{k_1} + a_2h^{k_2} + \cdots alakú hibaképlettel, ahol ai ismeretlen és ki ismert állandók úgy, hogy hki > hki+1.

A keresett érték megadható a

 A = A(h) + a_0h^{k_0} + a_1h^{k_1} + a_2h^{k_2} + \cdots

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

 A = A(h)+ a_0h^{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_0h^{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 tk0-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 ö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 rekurrenciás ö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).

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

Példa[szerkesztés | forrásszöveg szerkesztése]

Taylor-sorbafejtéssel,

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

f(x) deriváltja megadható

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

A_0(h) = \frac{f(x+h) - f(x)}{h}

formában választjuk meg, akkor ki = 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[szerkesztés | forrásszöveg szerkesztése]

  1. Richardson, L. F. (1911.). „The approximate arithmetical solution by finite differences of physical problems including differential equations, with an application to the stresses in a masonry dam”. Philosophical Transactions of the Royal Society of London, Series A 210, 307–357. o. DOI:10.1098/rsta.1911.0009.  
  2. Richardson, L. F. (1927.). „The deferred approach to the limit”. Philosophical Transactions of the Royal Society of London, Series A 226, 299–349. o. DOI:10.1098/rsta.1927.0008.  
  3. 126. o. Birkhoff, Garrett, Gian-Carlo Rota. Ordinary differential equations, 3rd edition, John Wiley and sons (1978). ISBN 047107411X. OCLC 4379402 
  • Extrapolation Methods. Theory and Practice by C. Brezinski and M. Redivo Zaglia, North-Holland, 1991.

Külső (angol!) linkek[szerkesztés | forrásszöveg szerkesztése]