Симпсоново правило

Из пројекта Википедија

Функцију f(x) (плава) апроксимирамо уз помоћ квадратне функције P(x) (црвена).

Симпсоново правило названо тако по Томасу Симпсону је метода из нумеричке анализе којом приближно израчунавамо одређен интеграл неке функције f(x), тј. интересује нас апроксимација $\int_a^b f(x) dx$ .

Садржај

1 Идеја
2 Сложено Симпсоново правило
3 Адаптивно Симпсоново правило
- 3.1 Грешка адаптивног Симпсоновог правила

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

Симпсонова формула (или правило) је у ствари део Њутн-Коутс формула. Функцију прво апроксимирамо уз помоћ Лагранжових полинома другог степена, а после уместо да израчунамо интеграл фунцкије $f (x)$ , израчунавамо интеграл добијеног полинома:

$f(x) \approx P(x) = \sum_{i=0}^{n=2} l_i (x) \cdot f(x_i)$ , притом

$l_{i}(x) = \prod_{j=0, j \neq i}^{n} \frac{x-x_{j}}{x_{i}-x_{j}}$

[[Означимо почетну тачку интеграла $a = x 0$ , крајњу $b = x 2$ , а тачку у средини $m = x 1$ (обрати пажњу на скицу са стране) и добићемо:

$P(x)=f(a)\frac{(x-m)(x-b)}{(a-m)(a-b)}+ f(m)\frac{(x-a)(x-b)}{(m-a)(m-b)}+ f(b)\frac{(x-a)(x-m)}{(b-a)(b-m)} \approx f(x)$

Овом приликом нећемо приказати како се долази до коначне формуле; рачун није тежак и састоји се од примене једноставних правила за интеграле (на пример, примена интеграла на суму):

$\int_{a}^{b} f(x) \, dx\approx \int_{a}^{b} P(x) \, dx =\frac{b-a}{6}\left[f(a) + 4f\left(\frac{a+b}{2}\right)+f(b)\right]$

Када хоћемо да апроксимирамо интеграл у интервалу од $a$ до $b$ очигледно је да ће нам за то бити неопходне три тачке дате функције.

Грешка у датом интервалу је:

$E_S = -\frac{(b-a)^5}{90}f^{(4)}(\xi)$ , где је $\xi \in [a,b]$ .

Уколико желимо да нађемо највећу могућу грешку односно њену границу, довољно је да максимирамо четврти извод функције за $ξ$ :

E_S \right | \leq \frac{(b-a)^5}{90} \left | \max_{a \leq \xi \leq } f^{(4)}(\xi) \right |" />

Обзиром да грешка зависи од размака између тачака којима вршимо апроксимацију, а ако означивши тај размак са $h = \frac{b-a}{2}$ , можемо рећи, користећи се O-нотацијом да се грешка налази $E_S = \mathcal{O} (h^5)$ .

[уреди] Сложено Симпсоново правило

Уколико смо незадовољни апроксимацијом, један од начина за побољшање је да интервал поделимо на више делова (мањих интервала) те да на сваком појединачно применимо Симпсоново правило и на крају их саберемо.

Означимо број тачака са $n$ , а размак између њих са $h = \frac{b-a}{n}$ и добићемо:

$\int_a^b f(x) \, dx\approx \frac{h}{3}\bigg[f(x_0)+2\sum_{j=1}^{n/2-1}f(x_{2j})+ 4\sum_{j=1}^{n/2}f(x_{2j-1})+f(x_n) \bigg]$ ,

што такође можемо написати као

$\int_a^b f(x) \, dx\approx \frac{h}{3}\bigg[f(x_0)+4f(x_1)+2f(x_2)+4f(x_3)+...+4f(x_{n-1})+f(x_n)\bigg]$

или као призвод вектора ( $f = (f(x_0), f(x_1), \dots, f(x_n)$ ):

$f \cdot (1, 4, 2, 4, 2, \dots , 2, 4, 1)^T$ .

Грешка за сложено Симпсоново правило је:

$E_S = -\frac{h^4}{180}(b-a)f^{(4)}(\xi)$ , $\xi \in [a,b]$

или када желимо да јој нађемо границу:

E_S \right | \leq \frac{h^4}{180}(b-a) \left | \max_{a \leq \xi \leq b} f^{(4)}(\xi) \right |" />

Такође, као што видимо, формулу за Симпсоново правило можемо извести и из комбинације трапезоидног правила и правила правоугаоника ( $Q S (f)$ означава апроксимацију интеграла функције $f$ између датих $a$ и $b$ , $Q T (f)$ то исто за трапезоидно правило, а $Q R (f)$ за правило правоугаоника):

$Q(f)={1 \over 3} (Q_S(f)+2Q_T(f))$

[уреди] Адаптивно Симпсоново правило

У пракси се понекад сусрећемо са ситуацијама када је нека функција у одређеним областима "досадна" и чије интеграле можемо да израчунамо врло лако са мало тачака (када је функција релативно "испеглана"), док је у одређеним областима врло променљива и ту нам за добру апроксимацију треба много више тачака.

Да бисмо то постигли, користићемо се тактиком "подели па владај":

Израчунај средишну тачку датог интервала $[a, b]$ : $m = \frac{b-a}{2}$
Израчунај апроксимацију интеграла за $[a, b]$ користећи се Симпсоновим правилом (назовимо је $S [a, b]$
Израчунај апроксимације за подељен интервал (означимо је $S [a, m]$ и $S [m, b]$ ) уз помоћ обичног Симпсоновог правила.
Уколико смо задовољни разликом $S [a, b] - (S [a, m] + S [m, b])$ , резултат је $S [a, m] + S [m, b]$ .
Уколико нисмо, наставимо даље рекурзивно примењујући адаптивно Симпсоново правило на интервале $[a, m]$ и $[m, b]$ , а резултат је њихова сума.

[уреди] Грешка адаптивног Симпсоновог правила

Обележимо резултат адаптивног Симпсоновог правила примењеног на интервалу $[a,b]\,$ за функцију $f\,$ са $S(a,b)\,$ , a размак између двеју тачака са $h = \frac{b-a}{2}\,$ онда важи:

За $h\,$ : $\int_a^b f(x) dx = S(a,b) - \frac{h^5}{90} \cdot f^{(4)} (\xi) - \mathcal{O} (h^7)$

За $\frac{h}{2}$ : $\int_a^b f(x) dx = S \left ( a, \frac{a+b}{2} \right ) + S \left ( \frac{a+b}{2}, b \right ) - \underbrace{2 \cdot \frac{(h/2)^5}{90}}_{-\frac{1}{16} \frac{h^5}{90} } \cdot f^{(4)} (\tilde{\xi}) - \mathcal{O} (h^7)$

Из тога даље закључујемо, под претпоставком $f^{(4)}(\xi) = f^{(4)} (\tilde{\xi} )$ :

$S \left ( a, \frac{a+b}{2} \right ) + S \left ( \frac{a+b}{2}, b \right ) - \frac{1}{16} \left ( \frac{h^5}{90} \right ) f^{(4)}(\xi) \approx S(a,b) - \frac{h^5}{90} f^{(4)} (\xi)$

$\Rightarrow \frac{h^5}{90} f^{(4)} (\xi) \approx \frac{16}{15} \left ( S(a,b) - S \left ( a, \frac{a+b}{2} \right ) - S \left ( \frac{a+b}{2}, b \right ) \right )$

Тако можемо даље доћи до (разумно) приближне вредности грешке:

\int_a^b f(x) dx - S \left ( a, \frac{a+b}{2} \right ) - S \left ( \frac{a+b}{2}, b \right ) \right | \approx \frac{1}{15} \left | S(a,b) - S \left ( a, \frac{a+b}{2} \right ) - S \left ( \frac{a+b}{2}, b \right ) \right |" />

Ова приближна грешка је врло згодна као критеријум за крај рекурзије.

Добављено из "http://sr.wikipedia.org../../../%D1%81/%D0%B8/%D0%BC/%D0%A1%D0%B8%D0%BC%D0%BF%D1%81%D0%BE%D0%BD%D0%BE%D0%B2%D0%BE_%D0%BF%D1%80%D0%B0%D0%B2%D0%B8%D0%BB%D0%BE.html"

Категорија страница: Нумеричка интеграција