Ричардсонова екстраполација

Ричардсонова екстраполација је поступак из нумеричке анализе којим од две „лошије“ апроксимације добијамо једну „бољу“ (у зависности од размака изме[у тачака); названа је тако по њеном творцу Луису Фрај Ричардсону.

Претпоставимо да је $g\,$ тачна функција, скуп или шта већ желимо да апроксимирамо (односно да екстраполирамо, када нисмо у могућности да уопште израчунамо резултат). Такође

, обележимо апроксимацију зависну од параметра $h\,$:

$g\approx g(h)$

На пример, када је реч о интеграцији, онда је $h\,$ најчешће размак изме[у двеју тачака (интервал).

Претпоставимо још да апроксимација има грешку у зависности од $h\,$, а $c_{1},c_{2},\dots$ су неке (познате или непознате) константе :

$g(h)-g=c_{1}\cdot h+c_{2}\cdot h^{2}+...\quad \ \Rightarrow \ \ \ \quad g(h)=g+c_{1}\cdot h+c_{2}\cdot h^{2}+\dots$

Узмимо да можемо да добијемо и $g(h/2)\,$; што ће рећи да смо преполовили интервал (када се ради о интеграцији) и тако удвостручили број рачунских операција са циљем да добијемо бољи резултат. Грешка апроксимације $g(h/2)\,$ је:

$g(h/2)-g=c_{1}\cdot (h/2)+c_{2}\cdot (h/2)^{2}+\dots \quad \ \Rightarrow \ \ \ \quad g(h/2)=g+c_{1}\cdot (h/2)+c_{2}\cdot (h/2)^{2}+\dots$

Шта нам може дати комбинација те две апроксимације? Летимичан поглед ће нам већ рећи да део грешке $c_{1}\cdot h$ можемо једноставно да елиминешемо множењем и одузимањем:

$g_{1}(h)=2\cdot g(h/2)-g(h)=2\cdot (g(h/2)=g+c_{1}\cdot (h/2)+c_{2}\cdot (h/2)^{2}+\dots )-(g+c_{1}\cdot h+c_{2}\cdot h^{2}+\dots )=$

$=g+c'_{2}\cdot h^{2}+c'_{3}\cdot h^{3}+\dots$

$c'_{2},c'_{3},\dots$ су неке нове константе добијене комбинацијом претходних.

Као што видимо, грешка апроксимације $g_{1}(h)$ зависи тек од квадрата дужине интервала (што је, наравно, врло позитивно, када се има у виду да је најчешће $h<1\,$).

Добивши $g_{1}(h)$ можемо да наставимо и добијемо $g_{2}(h)={\frac {1}{3}}\left[4g_{1}(h/2)-g_{1}(h)\right]=g+c''_{3}h^{3}$, и тако докле год не будемо били задовољни резултатом.

Рекурзивна формула Ричардсонове екстраполације је:

$g_{n}(h)={\frac {2^{n}\cdot g_{n-1}(h/2)-g_{n-1}(h)}{2^{n}-1}}=g+{\mathcal {O}}(h^{n+1})$

Општа Ричардсонова екстраполација

Ричардсонову екстраполацију можемо да напишемо и у нешто општијем смислу:

$g=g(h)+c_{1}h^{k_{1}}+{\mathcal {O}}(h^{k_{2}})$ (1)

Уместо да сада преполовимо $h\,$, поделимо га са $t\,$:

$g=g(h/t)+c_{1}\cdot (h/t)^{k_{1}}+{\mathcal {O}}\left((h/t)^{k_{2}}\right)$ (2)

Помножимо (2) са $t^{k_{1}}$ и одузмимо од (1):

$(t^{k_{1}}-1)\cdot g=t^{k_{1}}\cdot g(h/t)-g(h)+{\mathcal {O}}(h^{k_{2}})$

Исти израз, за $g\,$:

$g={\frac {t^{k_{1}}\cdot g(h/t)-g(h)}{t^{k_{1}}-1}}+{\mathcal {O}}(h^{k_{2}}$

Одатле можемо да израчунамо рекурзивну формулу:

$g_{n}(h)={\frac {t^{k_{n-1}}g_{n-1}(h/t)-g_{n-1}(h/t)}{t^{k_{n-1}}-1}}$,

где је:

$g=g_{n}(h)+{\mathcal {O}}(h^{k_{n}})$