Richardson-extrapolatie

In de numerieke analyse is Richardson-extrapolatie een techniek voor het versnellen van de convergentie van reeks benaderingen. De methode is genoemd naar Lewis Fry Richardson, die de techniek introduceerde in het begin van de 20e eeuw. In de woorden van Birkhoff en Rota, kan het nut ervan voor praktische berekeningen nauwelijk overschat worden ("its usefulness for practical computations can hardly be overestimated").

Praktische toepassingen van Richardson-extrapolatie zijn Romberg-integratie, waarbij de extrapolatie toegepast wordt op de trapeziumregel, en het Bulirsch-Stoer-algoritme voor het oplossen van gewone differentiaalvergelijkingen.

Methode

De basisgedachte achter de methode kan toegelicht worden aan een benaderingsmethode die afhankelijk is van een te kiezen stapgrootte. Door de stapgrootte te variëren kunnen door een combinatie van de resultaten termen in de fout geëlimineerd worden.

Veronderstel dat de methode $A(h)$, die afhangt van de stapgrootte $h$, gebruikt wordt als benadering van de grootheid $A_{0}$. De fout (afwijking) wordt ontwikkeld in machten van de stapgrootte.

$A_{0}=A(h)+Ch^{k}+C'h^{k+1}+\ldots$

De benadering zou verbeterd kunnen worden als de term $Ch^{k}$ zou verdwijnen. Dit kan bereikt worden door ook de benadering bij een andere stapgrootte $g$ te bepalen:

$A_{0}=A(g)+Cg^{k}+C'h^{k+1}+\ldots$

In het verschil van

$g^{k}A_{0}=g^{k}A(h)+Cg^{k}h^{k}+C'g^{k}h^{k+1}+\ldots$

en

$h^{k}A_{0}=h^{k}A(g)+Cg^{k}h^{k}+C'h^{k}g^{k+1}+\ldots$

is deze term inderdaad verdwenen:

$(h^{k}-g^{k})A_{0}=h^{k}A(g)-g^{k}A(h)+C'g^{k}h^{k}(g-h)+\ldots$

De benadering die hieruit volgt

$A_{0}={\frac {h^{k}A(g)-g^{k}A(h)}{h^{k}-g^{k}}}+C'{\frac {g^{k}h^{k}(g-h)}{h^{k}-g^{k}}}+\ldots$

is een orde van de stapgrootte verbeterd, aangezien de term

$C'{\frac {g^{k}h^{k}(g-h)}{h^{k}-g^{k}}}$

van de orde $h^{k+1}$ is.

De methode wordt ter besparing op het rekenwerk vaak toegepast door het halveren van de stapgrootte. Als bijvoorbeeld

$A_{0}\approx A(h)+Ch^{k}+O(h^{k+1})$

en $g={\tfrac {1}{2}}h$, wordt door een benadering met de halve stapgrootte te berekenen en deze met de eerste te combineren, een verbeterde benadering verkregen:

$A_{0}\approx {\frac {2^{k}A({\tfrac {1}{2}}h)-A(h)}{2^{k}-1}}+O(h^{k+1})$

waarin de term met $h^{k}$ niet meer voorkomt.