Kapitola 6
Numerická integrace
Kvadraturní vzorce
Chceme-li spočítat určitý integrál, případně integrál s váhovou funkcí
\begin{equation}\label{eq:05:integral} I[f(x)] = \int_a^b f(x)\,\mathrm{d}x , \qquad \text{příp.} \qquad I[f(x)] = \int_a^b w(x) f(x)\,\mathrm{d}x , \end{equation}numericky, aproximujeme jej určitým kvadraturním vzorcem
\begin{equation}\label{eq:05:kvadraturni_vzorec} I_n[f] = \sum_{j=0(1)}^{n} w_j\, f(x_j) , \end{equation}kde \(w_j\) jsou tzv. váhy a \(x_j\) uzly kvadraturního vzorce.
Zápis \(j = 0(1)\) znamená, že u některých typů kvadratur je vhodné číslovat od \(0\) (Newtonovy–Cotesovy vzorce) a jindy od \(1\) (Gaussovy vzorce).
Existují i zobecnění, která uvažují též derivace \(f'(x_j)\) a příslušné váhy \(w_j'\). Přímo se jimi zabývat nebudeme, ale využití je například pro určení chyby Gaussova vzorce.
Obvykle požadujeme, aby \(I_n[f]\) dával přesné výsledky pro polynomy do určitého stupně \(s\), který pak nazýváme řádem kvadraturního vzorce. Podle toho, které parametry ponecháme volné, dostáváme tři základní typy kvadratur.
- A) Pokud zafixujeme \(x_j\), obvykle \(x_j = x_0 + jh\), \(j = 0, \dots, n\), pak máme \(n+1\) volných parametrů \(w_j\), které můžeme určit položením \[ I_n[x^k] = I[x^k] = \mu_k , \qquad k = 0, \dots, n . \] To vede na \(V w = \mu\), kde \(V\) je opět Vandermondeova matice, a pro \(x_i \neq x_j\) pro \(\forall i \neq j\) máme jednoznačné řešení. Takovéto kvadratury nazýváme Newtonovy–Cotesovy vzorce.
- B) Pokud bereme též \(x_j\) jako volné parametry, pak budeme mít \(x_j\) a \(w_j\), \(j = 1, \dots, n\), tj. \(2n\) parametrů, které by mělo jít v principu určit z podmínek \[ I_n[x^k] = \mu_k , \qquad k = 0, \dots, 2n-1 . \] Jde však o soustavu nelineárních rovnic, a proto se obvykle postupuje jinak, viz níže. Tyto kvadratury se nazývají Gaussovy.
- C) Jsou též kvadratury, které fixují pouze některé uzly. Například Lobattova kvadratura fixuje krajní body \(a\), \(b\), a tedy integruje přesně polynomy stupně \(2n-1\), máme-li \(x_0 = a\), \(x_1, \dots, x_n = b\).
Newtonovy–Cotesovy vzorce
Newtonovy–Cotesovy vzorce jsou numerické kvadratury, které integrují přesně polynomy do řádu \(n\), máme-li zadány uzly \(x_j = x_0 + jh\), \(j = 0, \dots, n\).
Máme-li funkci \(f\) zadánu v bodech \(x_j\), pak Lagrangeův interpolační polynom \(L_n(x)\) těmito body je stupně \(n\), a tedy
\begin{equation}\label{eq:05:nc_definice} I[f(x)] \simeq \int_a^b L_n(x)\,\mathrm{d}x = I_n[f(x)] , \end{equation}a tedy
\begin{equation}\label{eq:05:vahy_nc} \sum_{j=0}^{n} w_j f(x_j) = \sum_{j=0}^{n} f(x_j) \underbrace{\int_a^b \ell_j(x)\,\mathrm{d}x}_{w_j} , \qquad \text{kde } \ell_j(x) = \prod_{i \neq j} \frac{x-x_i}{x_j-x_i} . \end{equation}Chybu této aproximace lze určit integrací chybového členu Lagrangeova interpolačního polynomu. Ukazuje se (viz např. Segethová, Ralston a podobně), že pro \(n\) sudé integrují Newtonovy–Cotesovy vzorce přesně i polynomy stupně \((n+1)\), a chyba je následující.
- 1) Pro \(n\) sudé, nechť \(f \in C^{n+2}\langle a,b \rangle\); pak existuje \(\xi \in \langle a,b \rangle\) takové, že \begin{equation}\label{eq:05:chyba_nc_sude} \int_a^b f(x)\,\mathrm{d}x - \int_a^b L_n(x)\,\mathrm{d}x = \frac{-f^{(n+2)}(\xi)}{(n+2)!} \int_a^b x\,\omega_{n+1}(x)\,\mathrm{d}x , \end{equation} kde \(\omega_{n+1}(x) = \prod_{j=0}^{n} (x-x_j)\).
- 2) Pro \(n\) liché, nechť \(f \in C^{n+1}\langle a,b \rangle\); pak existuje \(\xi \in \langle a,b \rangle\) takové, že \begin{equation}\label{eq:05:chyba_nc_liche} I[f(x)] - I[L_n(x)] = \frac{f^{(n+1)}(\xi)}{(n+1)!} \int_a^b \omega_{n+1}(x)\,\mathrm{d}x . \end{equation}
Odvození vzorců pomocí operátorů na polynomech
Definujme operátor integrace
\begin{equation}\label{eq:05:operator_j} J p(x) = \int_x^{x+h} p(t)\,\mathrm{d}t . \end{equation}Provedeme substituci \(t = x+sh\), \(\mathrm{d}t = h\,\mathrm{d}s\), a využijeme, že \(E^s p(x) = p(x+sh)\). Formální integrací přes \(s\) dostaneme
\begin{align*} J p(x) &= h \int_0^1 E^s p(x)\,\mathrm{d}s = h \int_0^1 e^{s \ln E}\,\mathrm{d}s \; p(x) = h\,\frac{E-I}{\ln E}\,p(x) = \frac{h\Delta}{\ln(I+\Delta)}\,p(x) \\ &= \frac{h\Delta}{hD}\,p(x) = \frac{\Delta}{D}\,p(x) . \end{align*}Dostáváme mimo jiné vztah \(JD = DJ = \Delta\).
Vzorce pro numerickou kvadraturu dostaneme Taylorovým rozvojem v \(\Delta\) do určitého stupně:
\begin{equation}\label{eq:05:rozvoj_j} J = \frac{h\Delta}{\ln(I+\Delta)} = h\left( I + \frac{1}{2}\Delta - \frac{1}{12}\Delta^2 + \frac{1}{24}\Delta^3 - \frac{19}{720}\Delta^4 + \dots \right) , \end{equation}například trikem \(\ln(I+\Delta) = \Delta(I-R)\), kde
\[ R = \frac{1}{2}\Delta - \frac{1}{3}\Delta^2 + \frac{1}{4}\Delta^3 - \dots \qquad \text{a} \qquad J = \frac{h}{I-R} = h\left( I + R + R^2 + \dots \right) . \]Lichoběžníkové a Simpsonovo pravidlo
Z rozvoje \eqref{eq:05:rozvoj_j} dostáváme kvadraturní vzorce. Například ponecháním členů do \(\Delta\) dostaneme
\begin{equation}\label{eq:05:lichobeznikove} \int_{x_0}^{x_1} f(x)\,\mathrm{d}x = Jf(x)\Big|_{x_0} \simeq h f_0 + \frac{h}{2}\left(f_1 - f_0\right) = \frac{h\left(f_1+f_0\right)}{2} - \frac{f''(\xi)h^3}{12} , \end{equation}což je lichoběžníkové pravidlo.
Přidáním dalšího členu máme
\begin{equation}\label{eq:05:tri_body_prvni} \int_{x_0}^{x_1} f(x)\,\mathrm{d}x \simeq h\left(\frac{5}{12}f_0 + \frac{2}{3}f_1 - \frac{1}{12}f_2\right) . \end{equation}Tento vzorec není úplně ideální: parabola \(L_2(x)\) je proložena třemi body, ale integruje se jen přes první podinterval.
Parabola \(L_2(x)\) proložená hodnotami \(f_0, f_1, f_2\) v uzlech \(x_0, x_1, x_2\); vyšrafovaná je plocha nad prvním podintervalem. Body lze tahat svisle a parabola i hodnota kvadratury se přepočítávají. Vyzkoušejte si, že šrafovaná plocha nad \(\langle x_0, x_1 \rangle\) odpovídá vzorci \eqref{eq:05:tri_body_prvni}, že plocha nad \(\langle x_1, x_2 \rangle\) odpovídá jeho zrcadlovému protějšku níže a že jejich součet je vždy přesně Simpsonovo pravidlo. Zapnutím tětiv uvidíte, o kolik se od paraboly liší lichoběžníkové pravidlo — a proč je nesymetrický tříbodový vzorec „ne úplně ideální“.
Sečteme-li \eqref{eq:05:tri_body_prvni} se vzorcem pro sousední podinterval
\begin{equation}\label{eq:05:tri_body_druhy} \int_{x_1}^{x_2} f(x)\,\mathrm{d}x \simeq h\left(-\frac{1}{12}f_0 + \frac{2}{3}f_1 + \frac{5}{12}f_2\right) , \end{equation}dostaneme
\begin{equation}\label{eq:05:simpson} \int_{x_0}^{x_2} f(x)\,\mathrm{d}x \simeq \frac{h}{3}\left(f_0 + 4f_1 + f_2\right) - \frac{f^{(4)}(\xi)}{90}h^5 , \end{equation}tedy Simpsonovo pravidlo.
Obdobně bychom mohli získat vyšší kvadraturní vzorce, například Booleovo pravidlo
\begin{equation}\label{eq:05:boole} \int_{x_0}^{x_4} f(x)\,\mathrm{d}x = \frac{2h}{45}\left(7f_0 + 32f_1 + 12f_2 + 32f_3 + 7f_4\right) + \mathcal{O}\left(h^7\right) . \end{equation}Obecně se ovšem nevyplatí zvyšovat \(n\) kvůli numerickým nestabilitám: například pro \(n > 7\) jsou některé váhy záporné, což vede k odečítání blízkých čísel a podobně. Navíc tyto vzorce konvergují pro \(n \to \infty\) jen pro omezenou třídu funkcí.
Složené kvadraturní vzorce
V praxi se užívají tzv. složené kvadraturní vzorce (též rozšířené), kdy použijeme určité kvadraturní pravidlo na podintervalech, do kterých rozdělíme interval \(\langle a,b \rangle\).
Například složené lichoběžníkové pravidlo je
\begin{equation}\label{eq:05:slozene_lichobeznikove} \int_a^b f(x)\,\mathrm{d}x \simeq h\left(\frac{f_0}{2} + \sum_{i=1}^{n-1} f_i + \frac{f_n}{2}\right) + \mathcal{O}\left(h^2\right) \end{equation}a složené Simpsonovo pravidlo (pro \(n\) sudé)
\begin{equation}\label{eq:05:slozene_simpson} \int_a^b f(x)\,\mathrm{d}x \simeq \frac{h}{3}\left(f_0 + 4f_1 + 2f_2 + 4f_3 + \dots + 4f_{n-1} + f_n\right) + \mathcal{O}\left(h^4\right) . \end{equation}Řád chyby je zde o řád nižší než pro samotný integrál přes \(\langle x_0, x_1 \rangle\), a to kvůli sčítání chyb z jednotlivých podintervalů.
Existují i tzv. otevřené Newtonovy–Cotesovy vzorce, kdy \(x_0 > a\), \(x_n < b\) a vyčíslujeme integrál na \(\langle a,b \rangle\). To je třeba udělat, pokud \(f(a)\) či \(f(b)\) divergují, ale přesto je integrál konečný. Vzhledem k malé přesnosti oproti Gaussovým kvadraturám, které jsou též v tomto smyslu „otevřené“, se však často nepoužívají.
Eulerův–Maclaurinův sumační vzorec
Pro chybu složeného lichoběžníkového pravidla si dokážeme následující vztah, který je důležitý pro extrapolaci pro \(h \to 0\), a tedy pro Rombergův algoritmus.
Nechť \(f(x) \in C^{2k+2} \langle x_0, x_n \rangle\). Potom platí
\begin{equation}\label{eq:05:euler_maclaurin} \begin{split} h\left( \frac{f_0}{2} + \sum_{i=1}^{n-1} f_i + \frac{f_n}{2} \right) &= \int_{x_0}^{x_0+nh} f(x)\,\mathrm{d}x + a_1 \left[ f'(x_n) - f'(x_0) \right] h^2 \\ &\quad + a_2 \left[ f'''(x_n) - f'''(x_0) \right] h^4 + \dots \\ &\quad + a_k \left[ f^{(2k-1)}(x_n) - f^{(2k-1)}(x_0) \right] h^{2k} + \dots , \end{split} \end{equation}kde konstanty \(a_1, a_2, \dots\) jsou koeficienty Taylorova rozvoje funkce \(\dfrac{x}{2\tanh\frac{x}{2}}\).
Konstanty \(a_k\) lze vyjádřit též jako \(a_k = \dfrac{B_{2k}}{(2k)!}\), kde \(B_n\) jsou Bernoulliova čísla
\[ B_0 = 1,\; B_1 = \frac{1}{2},\; B_2 = \frac{1}{6},\; B_3 = 0,\; B_4 = -\frac{1}{30},\; B_6 = \frac{1}{42} . \]Upravujme rozdíl
\begin{align*} &h\left[ \sum_{i=0}^{n-1} f_i + \frac{1}{2}\left( f_n - f_0 \right) \right] - \int_{x_0}^{x_0+h} f(x)\,\mathrm{d}x - \int_{x_0+h}^{x_0+2h} f(x)\,\mathrm{d}x - \dots - \int_{x_0+(n-1)h}^{x_0+nh} f(x)\,\mathrm{d}x = \\ &\qquad = h\left[ \underbrace{\left( E^0 + E^1 + \dots + E^{n-1} \right)}_{(E^n - I)/(E-I)} f_0 + \frac{1}{2}\left( E^n - I \right) f_0 \right] \\ &\qquad\qquad - \left[ Jf(x_0) + E^1 Jf(x_0) + \dots + E^{n-1} Jf(x_0) \right] = \\ &\qquad = h\left( E^n - I \right)\left( \frac{1}{\Delta} + \frac{I}{2} \right) f_0 - \left( E^n - I \right) \left( \frac{J}{\Delta} \right) f(x_0) = \\ &\qquad = h\left( E^n - I \right)\left( \frac{1}{2\tanh\frac{hD}{2}} - \frac{1}{hD} \right) f_0 = \\ &\qquad = \frac{1}{12} h^2 \left( f'(x_n) - f'(x_0) \right) - \frac{1}{720} h^4 \left( f'''(x_n) - f'''(x_0) \right) + \dots \end{align*}Přitom jsme využili, že \(\dfrac{J}{\Delta} = \dfrac{1}{D}\), a dále vedlejšího výpočtu (s \(E = e^{hD}\))
\begin{align*} \frac{I}{2} + \frac{1}{\Delta} &= \frac{I}{2} + \frac{1}{e^{hD} - I} = \frac{e^{hD} + I}{2\left( e^{hD} - I \right)} = \frac{1}{2\tanh\frac{hD}{2}} \\ &= \frac{1}{hD} + \frac{1}{12} hD - \frac{1}{720} (hD)^3 + \frac{1}{30240} (hD)^5 - \dots \end{align*} □Operace \(\frac{1}{D}\) a \(\frac{1}{\Delta}\) nejsou jednoznačně definovány, jde o třídu funkcí lišících se konstantou: \(\frac{1}{D}p(x)\) jsou polynomy \(P(x)\) takové, že \(DP(x) = p(x)\), a totéž tedy platí pro \(P(x) + c\). Vždy jsou ale v kombinaci s \((E^n - E^0)\), takže výsledek už je jednoznačný.
Využití Eulerova–Maclaurinova vzorce
Odvození složených Newtonových–Cotesových vzorců vyššího řádu
Složené Newtonovy–Cotesovy vzorce vyššího řádu lze odvodit pomocí Richardsonovy extrapolace. Označme \(I_n^0[f]\) lichoběžníkové pravidlo pro \(n+1\) bodů. Platí tedy
\begin{align*} I_n^0[f] &= I[f] + a_1\left[f_n' - f_0'\right] h_n^2 + \mathcal{O}(h^4) \\ &= I[f] + c\,h_n^2 + \mathcal{O}(h_n^4) \end{align*}a zároveň máme
\[ I_{2n}^0[f] = I[f] + c\left(\frac{h_n}{2}\right)^2 + \mathcal{O}(h_n^4) . \]Číselná osa s dělením na body \(x_0, x_1, \dots, x_{2n}\); svorky vyznačují krok \(\frac{h_n}{2}\) nad úsekem \(x_0\)–\(x_1\) a \(h_n\) nad úsekem \(x_2\)–\(x_4\). Nad osou je zvolená funkce a obě lomené čáry složeného lichoběžníkového pravidla — hrubá s krokem \(h_n\) (sudé uzly) a jemná s krokem \(\frac{h_n}{2}\). Hodnoty \(I_n^0\), \(I_{2n}^0\) i jejich Richardsonova kombinace \(I_{2n}^1\) se počítají a porovnávají s přesnou hodnotou integrálu. Sledujte, jak chyba \(I_n^0\) klesá jako \(h^2\), zatímco chyba \(I_{2n}^1\) jako \(h^4\) — a jak u funkce \(1/(1+25x^2)\) extrapolace pro malá \(n\) ještě nepomáhá, protože \(h_n\) není srovnatelné s charakteristickou škálou funkce.
Vhodnou kombinací obou vztahů dostaneme
\begin{equation}\label{eq:05:richardson_prvni} I_{2n}^1[f] = \frac{4\,I_{2n}^n - I_n^0}{3} = I[f] + \mathcal{O}(h_n^4) , \end{equation}a tedy
\begin{align*} I_{2n}^1[f] &= \frac{4}{3}\left[\frac{h_n}{2}\left(\frac{f_0}{2} + \sum_{i=1}^{2n-1} f_i + \frac{f_{2n}}{2}\right)\right] - \frac{1}{3}h_n\left(\frac{f_0}{2} + \sum_{k=1}^{n-1} f_{2k} + \frac{f_{2n}}{2}\right) = \\ &= \frac{\left(\frac{h_n}{2}\right)}{3}\left[f_0 + 4f_1 + 2f_2 + \dots + 4f_{2n-1} + f_{2n}\right] , \end{align*}což je Simpsonovo pravidlo.
Obecně platí
\[ \left. \begin{aligned} I_n^{k-1} &= I + c\,h^{2k} + \mathcal{O}(h^{2k+2}) \\ I_{2n}^{k-1} &= I + c\left(\frac{h}{2}\right)^{2k} + \mathcal{O}(h^{2k+2}) \end{aligned} \right\} \quad \Rightarrow \quad I_{2n}^k = \frac{4^k I_{2n}^{k-1} - I_n^{k-1}}{4^k - 1} = I + \mathcal{O}(h^{2k+2}) . \]Pro Booleovo pravidlo tak dostáváme
\begin{align*} I_{2n}^2 = \frac{16\,I_{2n}^1 - I_n^1}{15} &= \frac{16}{15}\frac{\left(\frac{h}{2}\right)}{3}\left(f_0 + 4f_1 + 2f_2 + \dots + 2f_{2n-2} + 4f_{2n-1} + f_{2n}\right) \\ &\quad - \frac{1}{15}\frac{h}{3}\left(f_0 + \quad 4f_2 + 2f_4 + \dots + 4f_{2n-2} \quad + \quad f_{2n}\right) = \\ &= \left(\frac{h}{2}\right)\frac{2}{45}\left(7f_0 + 32f_1 + 12f_2 + \underbrace{\dots}_{+\,32f_3 + 14f_4 + 32f_5 + \dots} + 32f_{2n-1} + 7f_{2n}\right) . \end{align*}Rombergův algoritmus
Richardsonovu extrapolaci lze použít přímo k výpočtu integrálu. Začneme s \(h_1 = b-a\) a počítáme
\[ I_1^0[f] = (b-a)\frac{f_1 + f_0}{2} , \]a dále
\begin{equation}\label{eq:05:romberg_rekurence} I_{2n}^0[f] = \frac{1}{2}I_n^0[f] + h_{2n}\sum_{k=1}^{n} f(x_{2k-1}) , \end{equation}kde faktor \(\frac{1}{2}\) plyne z toho, že \(h_{2n} = \frac{h_n}{2}\). Hodnoty \(I_{2n}^k\) pro \(k > 0\) pak dopočítáme pomocí Richardsonovy extrapolace.
Dostáváme tabulku
\[ \begin{array}{lccccccc} \text{počet bodů} & h \diagdown \text{chyba} & \mathcal{O}(h^2) & & \mathcal{O}(h^4) & & \mathcal{O}(h^6) & \cdots \qquad \mathcal{O}(h^{2k+2}) \\[4pt] 2 & b-a & I_1^0 \\[4pt] 2^1+1 = 3 & \dfrac{b-a}{2} & I_2^0 & \to & I_2^1 \\[4pt] 2^2+1 = 5 & \dfrac{b-a}{2^2} & I_4^0 & \to & I_4^1 & \to & I_4^2 & \cdots \\[4pt] & \vdots & \vdots \\[4pt] 2^k+1 & \dfrac{b-a}{2^k} & I_{2^k}^0 & \to & I_{2^k}^1 & \to & I_{2^k}^2 & \to \ \cdot \to \ I_{2^k}^k \end{array} \]V tabulce navíc vedou šikmé šipky \(\searrow\) vždy z posledního prvku jednoho řádku do dalšího sloupce na řádku pod ním, tj. \(I_1^0 \searrow I_2^1\), \(I_2^1 \searrow I_4^2\) a tak dále. Poslední šipka vedoucí do \(I_{2^k}^k\) odpovídá odstranění chyby \(\mathcal{O}(h^{2k})\).
- a) Má-li \(f(x)\) charakteristickou škálu, na které se mění, je vhodné začínat rovnou s \(I_n^0\), kde \(n\) je zvoleno tak, aby \(h_n = \frac{b-a}{n}\) bylo srovnatelné s touto škálou.
- b) Schéma funguje až do \(k\)-tého sloupce, má-li funkce \(f(x)\) \(2k-1\) spojitých derivací; jinak je nutné zvyšovat počet bodů.
- e) Pokud jsou derivace na kraji nulové či stejné, pak Richardsonova extrapolace selhává, protože se chyba chová jinak; je tedy nutné to hlídat. Například u hladké periodické funkce je integrál přes periodu vhodné aproximovat přímo pomocí \(I_n^0\) a zvětšovat \(n\), neboť chyba klesá rychleji než jakákoli mocnina \(h^m\).
- d) Rombergův algoritmus může být vhodnější než Gaussova kvadratura (viz níže), pokud chceme dosáhnout určité přesnosti a dopředu nevíme, kolik bodů \(n\) za tím účelem u Gaussovy kvadratury zvolit, neboť přepočítávání Gaussových \(x_n\), \(w_n\) je časově náročné.
Gaussova kvadratura
Uvažujme nyní integrál s vahou
\begin{equation}\label{eq:05:gauss_integral} I[f(x)] = \int_a^b f(x)\, v(x)\, \mathrm{d}x , \end{equation}kde váha \(v(x)\) je skoro všude kladná na \(\langle a, b \rangle\), a předpokládejme, že \(I[x^k]\) je konečný pro \(\forall k\).
Tento integrál chceme aproximovat kvadraturním vzorcem
\begin{equation}\label{eq:05:gauss_kvadratura} I[f(x)] \simeq \sum_{j=1}^{n} w_j\, f(x_j) \equiv I_n[f(x)] \end{equation}tak, aby \(I_n[x^k] = I[x^k] = \mu_k\) pro \(k = 0, \dots, 2n-1\), tj. aby integrál z polynomu do stupně \(2n-1\) byl přesný. Máme \(2n\) podmínek \(I_n[x^k] = \mu_k\) pro \(2n\) neznámých \(x_1, \dots, x_n\); \(w_1, \dots, w_n\), avšak tyto podmínky jsou nelineární.
Ukážeme si však obecně, že pro zvolenou váhu \(v(x)\) musí být \(x_j\) kořeny ortogonálního polynomu \(P_n(x)\) pro tuto váhu \(v(x)\), a pak už stačí jen určit váhy \(w_j\), což je lineární problém. Podle váhy pak například dostáváme Gaussovu–Legendreovu kvadraturu pro \(v(x) = 1\) a podobně pro další váhy.
Odvození
Předpokládejme, že už známe \(x_j\), a zvolme \(w_j\) tak, aby šlo o Newtonův–Cotesův vzorec, tj. aby \(I_n[x^k] = \mu_k\) pro \(k = 0, \dots, n-1\).
Nyní každý polynom \(p(x)\) stupně nejvýše \(2n-1\) lze psát ve tvaru
\begin{equation}\label{eq:05:deleni_polynomu} p(x) = q(x)\, P_n(x) + r(x) , \end{equation}kde \(P_n(x)\) je ortogonální polynom dané váhy a \(q(x)\) a \(r(x)\) jsou nejvýše stupně \(n-1\).
Pro integrál \(p(x)\) dostaneme
\[ I[p(x)] = \underbrace{I[q(x)\, P_n(x)]}_{= 0} + I[r(x)] = I_n[r(x)] , \]neboť \(P_n(x)\) je ortogonální na \(\forall\) polynomy stupně \(< n\) a \(I_n\) integruje přesně polynomy stupně \(n-1\). Ale zároveň má být přesné
\[ I[p(x)] = \underbrace{\sum_{k=1}^{n} w_k\, q(x_k)\, P_n(x_k)}_{\text{musí být } 0} + I_n[r(x)] . \]Označená suma tedy musí být nula pro \(\forall p(x)\), a tedy pro libovolné \(q(x)\), což může být jedině tehdy, pokud \(P_n(x_k) = 0\) pro \(\forall k\). Odtud plyne, že \(x_k\) musí být kořeny \(P_n(x)\).
Váhy lze vyjádřit jako
\[ w_k = \int_a^b \ell_k(x)\, v(x)\, \mathrm{d}x \]podobně jako u Newtonových–Cotesových vzorců.
Lze ukázat, že váhy \(w_k\) jsou vždy kladné pro \(v(x)\) kladné skoro všude a že integrál konverguje pro dostatečně hladké funkce. Neboť pro \(p(x) = \ell_i(x)^2\) stupně \(2n-2\), kde
\[ \ell_i(x) = \frac{\prod\limits_{i \neq j}(x - x_j)}{\prod\limits_{i \neq j}(x_i - x_j)} , \]máme
\[ 0 < I[\ell_i(x)^2] = \sum_{k=1}^{n} \ell_i(x_k)^2\, w_k = \sum_{k=1}^{n} \delta_{ik}\, w_k = w_i . \]Výpočet kořenů \(x_j\) a vah \(w_j\)
Nejčastěji se postupuje pomocí diagonalizace tridiagonální matice
\begin{equation}\label{eq:05:jacobiho_matice} J_n = \begin{pmatrix} \delta_1 & \gamma_2 & & & \\ \gamma_2 & \delta_2 & \ddots & & 0 \\ & & \ddots & \ddots & \\ 0 & & & & \gamma_n \\ & & & \gamma_n & \delta_n \end{pmatrix} , \end{equation}neboť \(\det(\lambda - J_n)\) splňuje stejné rekurentní vztahy jako \(p_n(x)\):
\[ \det(\lambda - J_n) = \det(\lambda - J_{n-1})(\lambda - \delta_n) - \gamma_n^2 \det(\lambda - J_{n-2}) . \]Kořeny \(x_j\) jsou tedy též vlastní čísla \(J_n\).
Lze ukázat, že
\[ w_j^{(n)} = \left(v_1^{(j)}\right)^2 , \qquad j = 1, \dots, n , \]kde \(v_1^{(j)}\) je první prvek \(j\)-tého vlastního vektoru odpovídajícího vlastní hodnotě \(x_j^{(n)}\), pokud je normovaný tak, že
\[ v^{(j)T} v^{(j)} = (p_0, p_0) = \int_a^b v(x)\, \mathrm{d}x = \mu_0 . \]Chyba Gaussovy kvadratury
Pokud \(f \in C^{2n}\langle a,b \rangle\), pak
\begin{equation}\label{eq:05:chyba_gauss} I[f(x)] - I_n[f(x)] = \frac{f^{(2n)}(\xi)}{(2n)!}\,(p_n, p_n) \end{equation}pro určité \(\xi \in \langle a,b )\).
Existují i kvadratury, které fixují krajní body (\(a = x_1\), \(b = x_n\)); to jsou Gaussovy–Lobattovy kvadratury.
Základní Gaussovy kvadratury
| \(\langle a,b \rangle\) | \(w(x)\) | |
|---|---|---|
| Gaussova–Legendreova kv. | \(\langle -1,1 \rangle\) | \(1\) |
| Gaussova–Čebyševova kv. | \(\langle -1,1 \rangle\) | \(1/\sqrt{1-x^2}\) nebo \(\sqrt{1-x^2}\) |
| Gaussova–Jacobiho kv. | \(\langle -1,1 \rangle\) | \((1-x)^\alpha (1+x)^\beta\) |
| Gaussova–Laguerreova kv. | \(\langle 0,\infty \rangle\) | \(x^\alpha e^{-x}\) |
| Gaussova–Hermiteova kv. | \(\langle -\infty,\infty \rangle\) | \(e^{-x^2}\) |
Integrály se singularitami
Postupovat lze buď (pokud víme, kde a jaká singularita je) rozdělením na dva intervaly a použitím vhodné Gaussovy kvadratury se singulární vahou, nebo (je-li například singularita v proměnném bodě) lze občas singularitu odečíst.
Chceme-li například spočítat
\[ Hf(y) = \mathrm{v.p.} \int_{-\infty}^{\infty} \frac{f(x)}{y-x}\, \mathrm{d}x \](tzv. Hilbertova transformace) a známe-li \(Hg(y)\) pro vhodnou funkci \(g(x)\), pak pro \(\tilde f(x) = f(x)/g(x)\) platí
\begin{equation}\label{eq:05:hilbert} Hf(y) = \mathrm{v.p.} \int_{-\infty}^{\infty} \frac{\tilde f(x)\, g(x)}{y-x}\, \mathrm{d}x = \int_{-\infty}^{\infty} \frac{\tilde f(x) - \tilde f(y)}{y-x}\, g(x)\, \mathrm{d}x + \tilde f(y)\, Hg(y) , \end{equation}přičemž podíl \(\dfrac{\tilde f(x) - \tilde f(y)}{y-x}\) už může být hladká funkce.
Poznámky k vícerozměrným integrálům
Vícerozměrné integrály jsou mnohem obtížnější než 1D integrály:
- a) hranice může být velmi komplikovaná (nekonvexní apod.);
- b) počet vyčíslení funkce může velice rychle narůstat, chceme-li vysokou přesnost (pokud v 1D potřebujeme 10 bodů, tak ve 3D \(10^3\) a obecně \(10^N\)).
Proto je důležité se nejprve zamyslet:
- a) Je možné část integrálu spočítat analyticky? Pokud ano, určitě to udělat.
- b) Je potřeba vysoká přesnost? Pokud ne, pak je asi nejvhodnější metoda Monte Carlo (viz letní semestr), která je vhodná i pro komplikovanou hranici. Bohužel chyba je řádu \(\dfrac{1}{\sqrt{n}}\), kde \(n\) je počet bodů, ovšem nezávisle na dimenzi.
Pokud je třeba vysoká přesnost, pak buď
- a) integruj opakovaně v 1D, nebo
- b) použij vícerozměrné Gaussovy kvadratury, je-li to možné.
Integrál přes obsah kruhu lze zapsat jako
\begin{equation}\label{eq:05:kruh} I = \int_{-1}^{1} \mathrm{d}x \int_{-\sqrt{1-x^2}}^{\sqrt{1-x^2}} \mathrm{d}y\, f(x,y) , \end{equation}tj. nejprve integrace přes \(y\) ve „vhodných“ bodech \(x\) s ohledem na vnější integrál.
Kruh se svislými tětivami, které naznačují integraci přes \(y\) při pevném \(x\): tětivy leží v uzlech vnější kvadratury a body na nich jsou uzly vnitřní kvadratury. Integrál \eqref{eq:05:kruh} se pro zvolenou funkci počítá (Gaussovy–Legendreovy uzly a váhy se dopočítávají Newtonovou metodou z rekurence pro \(P_n\)). Porovnejte Gaussovu kvadraturu s ekvidistantním lichoběžníkovým pravidlem při stejném počtu \(n^2\) vyčíslení a všimněte si, že ani Gauss nekonverguje rychle: vnitřní integrál je úměrný \(\sqrt{1-x^2}\), takže na hranici není hladký. Přesně to je ta „komplikovaná hranice“ z bodu a) výše.
Poznámky k singulárním integrálům
Užitečné bývá použití vhodné substituce, například
\begin{equation}\label{eq:05:substituce} \int_{a}^{b} f(x)\, \mathrm{d}x = \int_{1/b}^{1/a} \frac{1}{t^2}\, f\!\left(\frac{1}{t}\right) \mathrm{d}t , \qquad \text{pro } ab > 0 , \end{equation}a podobně; viz Numerical Recipes.