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

Из Википедије, слободне енциклопедије

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

Претпоставимо да је 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 [ 4 g_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} )