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

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

Претпоставимо да је $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+...\Rightarrow 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 \Rightarrow 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{\text{'}}_2\cdot h^2+c{\text{'}}_3\cdot h^3+\dots$

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

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

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

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

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

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

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

$g=g(h)+c_1{h}^{k_1}+𝒪(h^{k_2})$ (1)

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

$g=g(h/t)+c_1\cdot (h/t{)}^{k_1}+𝒪((h/t{)}^{k_2})$ (2)

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

$(t^{k_1}-1)\cdot g=t^{k_1}\cdot g(h/t)-g(h)+𝒪(h^{k_2})$

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

$g=\frac{t^{k_1}\cdot g(h/t)-g(h)}{t^{k_1}-1}+𝒪(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)+𝒪(h^{k_n})$