Rombergova integracija

Rombergova integracija (ponekad se navodi takođe kao Rombergova metoda) je postupak iz numeričke analize. Koristi se kada želimo numerički da izračunamo neki integral, a dobila je ime po Verneru Rombergu.

Ideja

Osnova Rombergove integracije je kombinacija dve loše aproksimacije kojom ćemo doći do jedne bolje. U suštini, ona predstavlja samo jedan vid Ričardsonove ekstrapolacije primenjene na integraciju i trapezoidno pravilo.

Prisetimo se greške trapezoidnog pravila sa $n\,$ datih tačaka:

$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]\,$

Napišimo to sve malo drugačije:

$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$

A šta se dešava kada prepolovimo razmak između tačaka?

$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$

Očigledno je da se koeficijenti za kvadratni deo greške ($c_{2}h^{2}\,$) donekle preklapa; zato ga možemo prostom kombinacijom ove dve aproksimacije eliminisati:

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

Sada greška zavisi samo od $h^{4}\,$! Postpupak možemo nastaviti i vrlo brzo ćemo doći do veoma preciznih rezultata. Daljim računom eliminišemo ostale stepene iz greške:

$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}}$

Na šemi se vidi malo jasnije:

${\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}}$

Kao rezultat se uzima uvek poslednji element na dijagonali.

Greška

Greška Rombergove integracije, napisana notacijom sa velikim O: ${\mathcal {O}}(h^{2n+1})$.

Za njenu približnu vrednost (za kriterijum obustave algoritma) može se uzeti razlika dijagonale: $T_{n}(h/2^{k})-T_{n-1}(h/2^{k-1})\,$

Treba međutim imati u vidu da u određenim slučajevima greška ne mora da se smanjuje - dobar primer za to su talasne funkcije (kosinus, sinus itd.). Na konkretnom primeru:

$\int _{0}^{2\pi }f(x)*cos(2^{n}x)dx$

broj tačaka mora da budem barem $n+1$ inače će nam integral uvek biti jednak nuli.

Rombergova integracija ima i tu prednost što grešku možemo u svakom sledećem koraku da izračunamo i tako svaki put iznova odlučimo da li hoćemo da idemo dalje ili smo zadovoljni dosadašnjim rezultatom.

Primer

Uzmimo da želimo da izračunamo:

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

Trapezoidno pravilo sa dve tačke nam daje:

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

Sa tri:

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

I sa pet:

$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$

Kada uporedimo čak i zadnji rezultat, greška je još uvek velika:

$\int _{10}^{20}{\frac {1}{\sqrt {\pi }}}\ \mathrm {e} ^{\left({\frac {x}{3}}\right)}dx-T_{0}(h/4)=-73.38$

U nekim situacijama bi takva greška mogla da bude kobna! Primenimo sa ovim rezultatima Rombergovu metodu:

$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$

Greška je $\int _{10}^{20}f(x)dx-1323.45=-40.93$, još uvek nedovoljno precizno za naše potrebe. Idemo još jedan korak dalje:

$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$

Greška na kraju: -0.65 ! Sa samo pet tačaka smo dobili izuzetno precizan rezultat. Kada bismo želeli da postignemo isti rezultat prostim trapezoidnim pravilom, trebalo bi nam oko 50 tačaka.