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

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

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

Идеја

Симпсонова формула (или правило) је у ствари део Њутн-Коутс формула. Функцију прво апроксимирамо уз помоћ Лагранжових полинома другог степена, а после уместо да израчунамо интеграл фунцкије $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]$.

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

$\left | E_S \right | \leq \frac{(b-a)^5}{90} \left | \max_{a \leq \xi \leq b} 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]$

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

$\left | 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))$

Адаптивно Симпсоново правило

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

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

1. Израчунај средишну тачку датог интервала $[a,b]$: $m = \frac{b-a}{2}$
2. Израчунај апроксимацију интеграла за $[a,b]$ користећи се Симпсоновим правилом (назовимо је $S_{[a,b]}$
3. Израчунај апроксимације за подељен интервал (означимо је $S_{[a,m]}$ и $S_{[m,b]}$) уз помоћ обичног Симпсоновог правила.
4. Уколико смо задовољни разликом $S_{[a,b]} - (S_{[a,m]} + S_{[m,b]})$, резултат је $S_{[a,m]} + S_{[m,b]}$.
5. Уколико нисмо, наставимо даље рекурзивно примењујући адаптивно Симпсоново правило на интервале $[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 )$

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

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

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