Całkowanie numeryczne - Polski Serwis Naukowy

Całkowanie numeryczne – metoda numeryczna polegająca na przybliżonym obliczaniu całek oznaczonych. Termin kwadratura numeryczna, często po prostu kwadratura, jest synonimem całkowania numerycznego, w szczególności w odniesieniu do całek jednowymiarowych. Dwu- i wyżejwymiarowe całkowania nazywane są czasami kubaturami, choć wyraz kwadratura również niesie to znaczenie dla całkowania w wyższych wymiarach.

Metody numeryczne – metody rozwiązywania problemów matematycznych za pomocą operacji na liczbach. Otrzymywane tą drogą wyniki są na ogół przybliżone, jednak dokładność obliczeń może być z góry określona i dobiera się ją zależnie od potrzeb.

Algorytm probabilistyczny albo randomizowany to algorytm który do swojego działania używa losowości. W praktyce oznacza to że implementacja takiego algorytmu korzysta przy obliczeniach z generatora liczb losowych. Główną zaletą algorytmów probabilistycznych w porównaniu z deterministycznymi jest działanie zawsze w "średnim przypadku", dzięki czemu złośliwe dane wejściowe nie wydłużają jego działania. Formalnie efektywność takiego algorytmu jest zmienną losową określoną na przestrzeni możliwych losowych ciągów. Wartość oczekiwana takiej zmiennej nazywana jest oczekiwanym czasem działania. Przypadek pesymistyczny jest zwykle na tyle mało prawdopodobny, że można go pominąć w analizie.

Proste metody całkowania numerycznego polegają na przybliżeniu całki za pomocą odpowiedniej sumy ważonej wartości całkowanej funkcji w kilku punktach. Aby uzyskać dokładniejsze przybliżenie dzieli się przedział całkowania na niewielkie fragmenty. Ostateczny wynik jest sumą oszacowań całek w poszczególnych podprzedziałach. Najczęściej przedział dzieli się na równe podprzedziały, ale bardziej wyszukane algorytmy potrafią dostosowywać krok do szybkości zmienności funkcji.

Metoda prostokątów

Prawdopodobnie najprostszym wzorem jest metoda punktu środkowego (midpoint rule): $\int\limits_{x_*}^{x_*+h} f(x) dx \approx h f\left( x_* + \frac h 2 \right)$

Jeśli funkcja $f(x)$ zmienia się w niewielkim stopniu na przedziale $(x_*, x_*+h)$ , reguła taka da dobre przybliżenie całki.

Metoda trapezów

Calkowanie numeryczne-metoda trapezow.png

Metoda trapezów polega na tym, że figurę ABCD zastępujemy figurą złożoną z trapezów wpisanych, tzn. krzywą aproksymujemy linią łamaną w nią wpisaną. Przedział całkowania $(a,b)$ dzielimy przy tym na $n$ równych części o długościach: $h:=\frac{b-a}{n}$ .

Punktami podziału (końcami części) są wówczas: $x_i = a+(i-1)h, \quad i=1\dots n+1.$

Wówczas pole figury złożonej z trapezów wynosi $S_{n}=\frac{y_{1}+y_{2}}{2}h+\frac{y_{2}+y_{3}}{2}h+...+\frac{y_{n}+y_{n+1}}{2}h=h\left(\frac{y_{1}}{2}+y_{2}+y_{3}+...+y_{n}+\frac{y_{n+1}}{2}\right)$

gdzie $y_{i}:=f(x_{i})$ – wartości funkcji w punktach podziału.

Stąd otrzymujemy wzór przybliżony w metodzie trapezów: $\int\limits_{a}^{b}f(x)dx \approx h\left(\frac{y_{1}}{2}+y_{2}+y_{3}+...+y_{n}+\frac{y_{n+1}}{2}\right) = \frac{h}{2}\sum_{i=1}^{n}\left(f(x_{i})+f(x_{i+1})\right)$

Oszacowanie błędu tej metody wynosi $R_{n}:=\left|\int\limits_{a}^{b}f(x)dx-S_{n}\right|\leq{\frac{(b-a)^{3}M^\prime{'}}{12n^{2}}}$

gdzie $M^\prime{'}:=\max_{\langle a,b\rangle}|f^\prime{'}|$

Metoda parabol (Simpsona)

Osobny artykuł: Metoda Simpsona.

Wymaga podzielenia przedziału całkowania na parzystą liczbę podprzedziałów, tzn. $h = \frac {b-a} {2n}$

dla uproszczenia oznaczamy: $x_i = a + i h$ oraz $f_i = f (x_i)$

wykonując całkowanie wielomianu interpolacyjnego Lagrange'a z 3 kolejnych punktów otrzymujemy wzór Simpsona: $\int\limits_{x_i}^{x_{i+2}} f(x) dx \approx \frac h 3 [f_i+4f_{i+1}+f_{i+2}]$

dla całego przedziału (a,b) otrzymujemy: $\int\limits_a^b f(x) dx \approx \frac h 3 [f_0 + 4(f_1+f_3+...+f_{2n-1}) + 2(f_2+f_4+...+f_{2n-2}) + f_{2n}]$

Metody losowe

Do przybliżonego obliczania całki oznaczonej można również wykorzystać metody probabilistyczne. Należy pamiętać jednak, że wynik takiego całkowania jest też zmienną losową.

Monte Carlo

Idea opiera się na policzeniu pola pod wykresem funkcji dla $f(x)>0$ i odjęciu pola nad wykresem dla $f(x)<0$

probabilistyczna

$\int\limits_a^b f(x) dx \approx \frac {b-a} n \sum_{i=1}^n f(x_i)$

$x_i$ jest losowo wybierane z przedziału $<a,b>$
$n$ określa liczność próbki.

Przykłady

Przykład – metoda prostokątów

Spróbujmy scałkować funkcję $\cos(x)$ na przedziale od 0 do 1. Ponieważ da się ją scałkować analitycznie, znamy dokładny wynik i możemy łatwo obliczać błąd przybliżenia różnych metod całkowania. Z dokładnością do 10 miejsc dziesiętnych prawidłowy wynik wynosi: $\int\limits_0^1 \cos(x) dx = \sin(1)-\sin(0) = 0,8414709848$

Całkowanie numeryczne za pomocą zasady punktu środkowego da nam wynik: $\int\limits_0^1 \cos(x) dx \approx (1-0) \cos\left(\frac 1 2\right) = 0,8775825619$

co daje błąd 0,0361115771 (błąd względny 4,3%) – niewielki jak na tak prostą metodę, jednak oczywiście niezadowalający do wielu zastosowań.

Żeby uzyskać lepsze przybliżenia możemy podzielić przedział całkowania: $\int\limits_0^1 \cos(x) dx = \int\limits_0^{1/2} \cos(x) dx + \int\limits_{1/2}^1 \cos(x) dx \approx \left(\frac 1 2-0\right) \cos\left(\frac 1 4\right) + \left(1-\frac 1 2\right) \cos\left(\frac 3 4\right) = 0,8503006452$

Z błędem bezwzględnym 0,0088296604 lub względnym 1%.

Dzieląc przedział całkowania na więcej fragmentów możemy uzyskać lepsze przybliżenie:

Przykład 2

Całkowanie numeryczne przebiegów czasowych. Spróbujmy scałkować spróbkowany przebieg $\sin(t)$ na przedziale od 0 do $4\cdot\pi$ [s]. Oznaczmy częstotliwość próbkowania przebiegu przez $f_p$ [Hz].

Do obliczeń wykorzystamy metodę prostokątów. Średnica podziału $t_p=\frac{1}{f_p}=t_{i+1}-t_i$ wynosi 1. Niech $X_i(t)$ oznacza próbkę po całkowaniu. Każdy wyraz $X_i$ można obliczyć jako sumę częściową: $X_i=\sum_{n=0}^{i} x_i(t)t_p$

Zobacz też

Metody Newtona-Cotesa

Kwadratury Gaussa