Ромбергова интеграција

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

Ромбергова интеграција (понекад се наводи такође као Ромбергова метода) је поступак из нумеричке анализе. Користи се када желимо нумерички да израчунамо неки интеграл, а добила је име по Вернеру Ромбергу.

Идеја[уреди]

Основа Ромбергове интеграције је комбинација две лоше апроксимације којом ћемо доћи до једне боље. У суштини, она представља само један вид Ричардсонове екстраполације примењене на интеграцију и трапезоидно правило.

Присетимо се грешке трапезоидног правила са n\, датих тачака:


T_r(h) = \frac{h}{2} \left(f(x_0) + 2f(x_1) + 2f(x_2)+\dots+2f(x_{n-1}) + f(x_n) \right)
h = \frac{b-a}{n}\,

I_{precizan} = \int_a^b f(x) dx = T_r (h) + { (b-a) \over 12 } h^2 f''(\xi) + \dots
\xi \in [a,b]\,

Напишимо то све мало другачије:


T(h) = I_{precizan} + c_2 \cdot h^2 + c_4 \cdot h^4 + \dots

c_2 = { (b-a) \over 12 } \cdot f''(\xi), c_4 = \ldots

А шта се дешава када преполовимо размак између тачака?


T(h/2) = I_{precizan} + c_2 \cdot (h/2)^2 + c_4 \cdot (h/4)^2 + \dots = I_{precizan} + \frac{1}{4} c_2 \cdot h^2 + \frac{1}{16} c_4 \cdot h^4 + \dots

Очигледно је да се коефицијенти за квадратни део грешке (c_2 h^2 \,) донекле преклапа; зато га можемо простом комбинацијом ове две апроксимације елиминисати:


T_1(h/2) = \frac{4 \cdot T(h/2) - T(h)}{3} = I_{precizan} - \frac{1}{4} c_4 + \dots

Сада грешка зависи само од h^4\,! Постпупак можемо наставити и врло брзо ћемо доћи до веома прецизних резултата. Даљим рачуном елиминишемо остале степене из грешке:


T_n (\frac{h}{2^k}) = \frac{ 4^n \cdot T_{n-1} (\frac{h}{2^k} ) - T_{n-1} (\frac{h}{2^{k-1}} ) } {2^k - 1}

На шеми се види мало јасније:


\begin{matrix}

T_0(h)   &              &          &             &          &        \\
         & \searrow     &          &             &          &        \\
T_0(h/2) & \rightarrow  & T_1(h/2) &             &          &        \\ 
         & \searrow     &          & \searrow    &          &        \\
T_0(h/4) & \rightarrow  & T_1(h/4) & \rightarrow & T_2(h/4) &        \\
 \vdots  & \ddots       & \vdots   & \ddots      & \vdots   & \ddots \\
\end{matrix}


Као резултат се узима увек последњи елемент на дијагонали.

Грешка[уреди]

Грешка Ромбергове интеграције, написана нотацијом са великим О: \mathcal{O} (h^{2n+1} ).

За њену приближну вредност (за критеријум обуставе алгоритма) може се узети разлика дијагонале: T_{n} (h/2^k ) - T_{n-1}(h/2^{k-1})\,

Треба међутим имати у виду да у одређеним случајевима грешка не мора да се смањује - добар пример за то су таласне функције (косинус, синус итд.). На конкретном примеру:

 \int_{0}^{2 \pi} f(x) * cos(2^n x) dx

број тачака мора да будем барем n+1 иначе ће нам интеграл увек бити једнак нули.

Ромбергова интеграција има и ту предност што грешку можемо у сваком следећем кораку да израчунамо и тако сваки пут изнова одлучимо да ли хоћемо да идемо даље или смо задовољни досадашњим резултатом.

Пример[уреди]

Узмимо да желимо да израчунамо:


\int_{10}^{20} \frac{1}{ \sqrt{ \pi } } \ \mathrm e ^{ \left (\frac{x}{3} \right ) } dx

Трапезоидно правило са две тачке нам даје:


T_0(h = 10) = 10 \cdot (\frac{1}{2} f(10) + \frac{1}{2} f(20) ) = 2295.70

Са три:


T_0(h/2 = 5) = 5 \cdot (\frac{1}{2} f(10) + f(15) + \frac{1}{2} f(20) ) = 1566.51

И са пет:


T_0(h/4 = 2.5) = 2.5 \cdot (\frac{1}{2} f(10) + f(12.5) + f(15) + f(17.5) + \frac{1}{2} f(20) ) = 1355.90

Када упоредимо чак и задњи резултат, грешка је још увек велика:


\int_{10}^{20} \frac{1}{ \sqrt{ \pi } } \ \mathrm e ^{ \left (\frac{x}{3} \right ) } dx - T_0(h/4) = -73.38

У неким ситуацијама би таква грешка могла да буде кобна! Применимо са овим резултатима Ромбергову методу:


T_1(h/2) = \frac{ 4 \cdot T_0(h/2) - T_0(h) }{3} = \frac{ 4 \cdot 1566.51 - 2295.70 }{3} = 1323.45

Грешка је \int_{10}^{20} f(x) dx - 1323.45 = -40.93, још увек недовољно прецизно за наше потребе. Идемо још један корак даље:


T_1(h/4) = \frac{ 4 \cdot T_0(h/4) - T_0(h/2) }{3} = \frac{ 4 \cdot 1355.90 - 1566.51 }{3} = 1285.70

T_2(h/4) = \frac{ 4^2 \cdot T_1(h/4) - T_1(h/2) }{4^2-1} = 1283.18

Грешка на крају: -0.65 ! Са само пет тачака смо добили изузетно прецизан резултат. Када бисмо желели да постигнемо исти резултат простим трапезоидним правилом, требало би нам око 50 тачака.