Kapitola 5
Numerická derivace
Reprezentace funkce a výpočet derivace
Výpočet derivace v počítači závisí na reprezentaci funkce v počítači. Často máme například funkce reprezentované jako rozvoj do určité (analytické) báze \(\phi_i(x)\),
\begin{equation}\label{eq:04:rozvoj_baze} f(x) \simeq \sum_{i=1}^{n} c_i \phi_i(x) , \end{equation}a derivace pak můžeme počítat přímo pomocí
\begin{equation}\label{eq:04:derivace_baze} \frac{\mathrm{d}^m f(x)}{\mathrm{d}x^m}\bigg|_{x=z} \approx \sum_{i=1}^{n} c_i \frac{\mathrm{d}^m \phi_i(x)}{\mathrm{d}x^m}\bigg|_{x=z} , \end{equation}pokud lze derivace báze rozumně počítat (např. pro polynomy apod.).
Pokud máme funkci zadanou body a funkčními hodnotami, pak je nutné funkci nejprve aproximovat, a to buď pomocí \eqref{eq:04:rozvoj_baze}, např. metodou nejmenších čtverců, nebo interpolací, nejčastěji polynomiální. Teprve tuto aproximaci pak derivujeme.
I tehdy, když můžeme funkci \(f(x)\) vyčíslit v libovolném bodě, ale ne už její derivaci (např. je-li \(f(x)\) řešením složitého problému), není vhodné používat nejjednodušší aproximace derivací jako např.
\begin{equation}\label{eq:04:dopredna_dvoubodova} \frac{\mathrm{d}f(x)}{\mathrm{d}x}\bigg|_{x=x_0} \approx \frac{f(x_1)-f(x_0)}{x_1-x_0} = \frac{f(x_0+h)-f(x_0)}{h} , \end{equation}kdy volíme \(x_1\) co nejblíže \(x_0\), neboli volíme \(h\) malé. Vznikají totiž problémy se zaokrouhlovací chybou při odečítání dvou blízkých čísel. Chyba se v tomto případě chová jako \(\mathcal{O}(h)\) (viz později), a potřebujeme-li vysokou přesnost, je nutné volit velmi malé \(h\); zaokrouhlovací chyba pak může výsledek hodně ovlivnit.
Je tedy vhodné použít vícebodové aproximace, u kterých se chyba chová jako \(\mathcal{O}(h^p)\) s \(p>1\), a není pak nutné volit tak malá \(h\).
Derivace interpolačního polynomu
Mějme \(f(x)\) zadanou v bodech \(x_0, \dots, x_n\) a k její aproximaci použijme polynomiální interpolaci
\[ f(x) \approx L_n(x) = \sum_{i=0}^{n} \ell_{n,i}(x)\, f(x_i) , \]kde \(\ell_{n,i}(x)\) lze vyjádřit jako
\[ \ell_{n,i}(x) = \frac{\omega_n(x)}{(x-x_i)\,\omega_n'(x_i)} , \]přičemž
\[ \omega_n(x) = \prod_{j=0}^{n}(x-x_j) \quad \text{a} \quad \omega_n'(x) = \sum_{i=0}^{n} \prod_{\substack{j=0 \\ j \neq i}}^{n} (x-x_j) , \]a tedy
\[ \omega_n'(x_k) = \prod_{\substack{j=0 \\ j \neq k}}^{n} (x_k - x_j) . \]Derivováním \(L_n(x)\) dostaneme aproximaci
\begin{equation}\label{eq:04:derivace_Ln} \frac{\mathrm{d}^m f}{\mathrm{d}x^m}\bigg|_{x=z} \approx \sum_{i=0}^{n} f(x_i)\, \frac{\mathrm{d}^m \ell_{n,i}(x)}{\mathrm{d}x^m}\bigg|_{x=z} = \sum_{i=0}^{n} f(x_i)\, C_{n,i}^{m}(z) . \end{equation}Koeficienty \(C_{n,i}^{m}(z)\) závisí jak na počtu použitých bodů \(n\), tak na bodu \(z\), ve kterém derivaci počítáme. Lze je určit různými způsoby, které rozebereme v následujících odstavcích.
Přímá derivace bázových polynomů
První možností je přímá derivace \(\ell_{n,i}(x)\). Není příliš efektivní, neboť vyžaduje konstrukci polynomů \(\ell_{n,i}(x)\).
Řešení soustavy lineárních rovnic z Taylorových rozvojů
Druhou možností je řešení soustavy lineárních rovnic, které vychází z Taylorových rozvojů \(f(x)\) v bodech \(x_i\). Ani tento postup není příliš efektivní; jeho výhodou ovšem je, že spolu s koeficienty dostáváme i chybové členy.
Rozvineme-li
\begin{align*} f(x_0) &= f(z) + \frac{f'(z)}{1!}(x_0 - z) + \frac{f''(z)}{2!}(x_0-z)^2 + \mathcal{O}\big((x_0-z)^3\big) , \\ f(x_1) &= f(z) + f'(z)(x_1 - z) + \frac{f''(z)}{2!}(x_0-z)^2 + \mathcal{O}\big((x_1-z)^3\big) \end{align*}a vyřešíme-li tuto soustavu vůči \(f(z)\) a \(f'(z)\), dostaneme pro \(f(z)\) lineární interpolaci funkce \(f(x)\),
\begin{equation}\label{eq:04:linearni_interpolace} f(z) = \frac{x_1 - z}{x_1 - x_0} f(x_0) + \frac{z - x_0}{x_1 - x_0} f(x_1) + \frac{f''(z)}{2}(x_1 - z)(z - x_0) , \end{equation}a pro derivaci
\begin{equation}\label{eq:04:derivace_dvoubodova_chyba} f'(z) = \frac{f(x_1) - f(x_0)}{x_1 - x_0} - \frac{f''(z)}{2}\underbrace{(x_1 + x_0 - 2z)}_{\substack{\pm h \text{ pro } z = x_0 \text{ nebo } z = x_1 \\ 0 \text{ pro } z = \frac{x_0+x_1}{2}}} . \end{equation}Pro \(z\) uprostřed intervalu tedy vedoucí chybový člen vymizí a chyba je \(\mathcal{O}(h^2)\).
Rostoucí křivka \(f(x)\) s čárkovanou sečnou a svislicemi v bodech \(x_0\), \(z\), \(x_1\). Body \(x_0\), \(z\) a \(x_1\) lze táhnout po vodorovné ose; počítá se diference \(D=\frac{f(x_1)-f(x_0)}{x_1-x_0}\), přesnou derivaci \(f'(z)\) i vedoucí chybový člen \(\frac{f''(z)}{2}(x_1+x_0-2z)\) z \eqref{eq:04:derivace_dvoubodova_chyba}. Vyzkoušejte si, že pro \(z\) uprostřed intervalu se sklon sečny (oranžová) kryje se sklonem tečny (zelená) a chyba spadne o řád níž — u paraboly dokonce přesně na nulu.
Více viz demonstrace v Mathematice.
Fornbergovy rekurentní vztahy
Efektivní výpočet koeficientů \(C^m_{n,i}(z)\) navrhl Fornberg v Math. Comp. 51 (1988) 699. Vychází z rekurentních vztahů pro \(\omega_n(x)\),
\begin{align*} \omega_n(x) &= (x - x_n)\,\omega_{n-1}(x) , \\ \omega'_n(x) &= (x - x_n)\,\omega'_{n-1}(x) + \omega_{n-1}(x) , \end{align*}z nichž plynou vztahy
\begin{equation}\label{eq:04:rekurence_l} \begin{aligned} \ell_{n,i}(x) &= \frac{(x - x_n)}{(x_i - x_n)}\,\ell_{n-1,i} \quad \text{pro } 0 \le i \le n-1 , \\ \text{a}\quad \ell_{n,n}(x) &= \frac{\omega_{n-2}(x_{n-1})}{\omega_{n-1}(x_n)}\,(x - x_{n-1})\,\ell_{n-1,n-1} \, . \end{aligned} \end{equation}Vyjádříme-li nyní \(\ell_{n,i}(x)\) pomocí Taylorova rozvoje v bodě \(z\) jako
\[ \ell_{n,i}(x) = \sum_{m=0}^{n} \frac{C^m_{n,i}(z)}{m!}\,(x - z)^m \]a dosadíme do \eqref{eq:04:rekurence_l}, pak porovnáním členů u \((x-z)^k\) nakonec dostaneme
\begin{equation}\label{eq:04:fornberg_C} C^m_{n,i} = \frac{1}{x_n - x_i}\Big[(x_n - z)\,C^m_{n-1,i} - m\,C^{m-1}_{n-1,i}\Big] \quad \text{pro } 0 \le i \le n-1 \text{ a } n \ge m \ge 1 \end{equation}a
\begin{equation}\label{eq:04:fornberg_Cnn} C^m_{n,n} = \frac{\omega_{n-2}(x_{n-1})}{\omega_{n-1}(x_n)}\Big[m\,C^{m-1}_{n-1,n-1} - (x_{n-1} - z)\,C^m_{n-1,n-1}\Big] , \end{equation}a speciálně
\begin{align*} C^0_{n,i} &= \frac{x_n - z}{x_n - x_i}\,C^0_{n-1,i} \qquad \text{a } C^0_{0,0}(z) = 1 , \\ C^0_{n,n} &= \frac{\omega_{n-2}(x_{n-1})}{\omega_{n-1}(x_n)}\,(z - x_{n-1})\,C^0_{n-1,n-1} , \end{align*}kde \(\omega_{-1}(x) = 1\) a \(C^m_{n,i} = 0\) pro \(m > n\).
Tyto rekurentní vztahy používá Mathematica.
Chyba takto získaných aproximací je obecně \(\mathcal{O}(h^{n+1-m})\) pro \(m\)-tou derivaci a \((n{+}1)\)-bodovou formuli, ale u symetrických vztahů je obvykle o řád lepší.
Rovnoměrné sítě
Pro rovnoměrné sítě (ekvidistantní grid), kdy
\begin{equation}\label{eq:04:ekvidistantni_grid} x_i = x_0 + ih \quad , \quad i = 1, \dots, n , \end{equation}jsou koeficienty jednodušší a zvláště pro derivace v bodech \(x_i\) jsou pouze funkcemi kroku \(h\) (viz později).
Richardsonova extrapolace
K odvození přesnějších vztahů pro derivaci lze použít i tzv. Richardsonovu extrapolaci, kdy obecně ze známého chování chyby extrapolujeme k \(h \to 0\).
Centrovaná diference v bodě \(x_i\) aproximuje první derivaci s chybou \(\mathcal{O}(h^2)\). Označíme-li \(D_h\) operátor centrované diference s krokem \(h\), můžeme psát
\begin{align*} D_h f(x_i) &= \frac{f_{i+1} - f_{i-1}}{2h} = f'(x_i) + ch^2 + \mathcal{O}(h^4) , \\ D_{2h} f(x_i) &= \frac{f_{i+2} - f_{i-2}}{4h} = f'(x_i) + c\,4h^2 + \mathcal{O}(h^4) , \end{align*}kde \(c\) je neznámá konstanta. Odtud
\begin{align} f'(x_i) + \mathcal{O}(h^4) &= \frac{4 D_h f(x_i) - D_{2h} f(x_i)}{3} \label{eq:04:richardson_ctyrbodova} \\ &= \frac{4}{6h}\,(f_{i-1} - f_{i-1}) - \frac{1}{12h}\,(f_{i+2} - f_{i-2}) \notag \\ &= \frac{1}{12h}\left(-f_{i+2} + 8 f_{i+1} - 8 f_{i-1} + f_{i-2}\right) . \notag \end{align}Výraz \eqref{eq:04:richardson_ctyrbodova} je speciálním případem obecné Richardsonovy extrapolace
\begin{equation}\label{eq:04:richardson_obecna} \left.\begin{aligned} A_h &= A + Ch^k + \mathcal{O}(h^{k+1}) \\ A_{2h} &= A + C(2h)^k + \mathcal{O}(h^{k+1}) \end{aligned}\right\} \quad \Rightarrow \quad A + \mathcal{O}(h^{k+1}) = \frac{2^k A_h - A_{2h}}{2^k - 1} . \end{equation}Optimální volba kroku \(h\)
Na přesnost výpočtu derivace mají vliv dvě chyby.
- Chyba aproximace – závisí na použitém vzorci a je typicky \(\mathcal{O}(h^k)\); např. \(f'_0 \approx \frac{f_1 - f_0}{h} + \mathcal{O}(h)\), přesněji je vedoucí člen roven \(\frac{h f''}{2}\).
- Chyba zaokrouhlovací – odhad absolutní chyby odečítání \(f(x{+}h) - f(x)\) je \(\frac{2\varepsilon|f|}{h}\), kde \(\varepsilon\) je strojové epsilon.
Optimální volba \(h\) je tedy taková, že jsou obě chyby srovnatelné:
\begin{equation}\label{eq:04:hopt} \frac{h_{\mathrm{opt}}|f''|}{2} \simeq \frac{2\varepsilon|f|}{h_{\mathrm{opt}}} \quad \Rightarrow \quad h_{\mathrm{opt}} \simeq 2\sqrt{\frac{|f|}{|f''|}}\,\sqrt{\varepsilon} , \end{equation}což pro dvojitou přesnost dává \(h_{\mathrm{opt}} \sim 10^{-8}\).
Výraz \(\sqrt{|f|/|f''|}\) představuje jistou charakteristickou škálu, na které se \(f\) mění.
Podobně dostaneme
\begin{align*} \mathcal{O}(h^2) &\to h_{\mathrm{opt}} \approx \sqrt[3]{\varepsilon} \approx 10^{-5} \quad \Rightarrow \quad h^2 \approx 10^{-10} , \\ \mathcal{O}(h^4) &\to h_{\mathrm{opt}} \approx \sqrt[5]{\varepsilon} \approx 10^{-3} \qquad\ \ \, h^4 \approx 10^{-12} . \end{align*}Závislost chyby na kroku \(h\) v log-log měřítku. Čárkovaně jsou teoretické asymptoty — klesající \(\varepsilon h^{-1}\) a rostoucí \(h^1\), \(h^2\), \(h^4\) — a svislice označují jejich průsečíky; plné čáry jsou změřené chyby: dopředná, centrovaná a Richardsonova čtyřbodová diference se počítají ve dvojité přesnosti pro dvě stě hodnot \(h\) a vykresluje se \(|D_h f - f'(x)|\). Posuvníkem měňte bod \(x\) a přepínačem funkci: charakteristická písmena „V“ mají minima kolem \(10^{-8}\), \(10^{-5}\) a \(10^{-3}\), přesně jak předpovídá \eqref{eq:04:hopt}. Nalevo od minima dominuje zaokrouhlovací šum, napravo chyba aproximace.
Vzorce pro numerickou derivaci a integraci na rovnoměrné síti pomocí operátorů na polynomech
Definujme na prostoru polynomů do určitého stupně \(n\) následující operátory:
\begin{align*} I\,p(x) &= p(x) & &\text{identita,} \\ E\,p(x) &= p(x+h) & &\text{posunutí,} \\ \Delta\,p(x) &= p(x+h) - p(x) & &\text{dopředná diference,} \\ \nabla\,p(x) &= p(x) - p(x-h) & &\text{zpětná diference,} \\ \delta\,p(x) &= p\!\left(x+\tfrac{h}{2}\right) - p\!\left(x-\tfrac{h}{2}\right) & &\text{centrovaná diference.} \end{align*}Operátory \(E\), \(\Delta\), \(\nabla\) a \(\delta\) jsou závislé na \(h\), ale tuto závislost obvykle vyznačovat nebudeme.
Jde o lineární operátory a standardně jsou k operátoru \(A\) definovány i operátory \(A^2, \dots, A^k\), dále \(A^0 = I\) a \(A^{-1}\) jakožto operátor, pro nějž \(A^{-1}(A p(x)) = p(x)\) pro libovolný polynom. Pro některé operátory, jako jsou diference, však operace \(A^{-1} p(x)\) není jednoznačná a výsledek je určen až na konstantu.
Exponenciála je dána Taylorovým rozvojem, například
\[ e^{\Delta} = I + \Delta + \frac{\Delta^2}{2} + \dots , \]a obdobně jiné funkce. Pro polynomy stupně nejvýše \(n\) ovšem platí
\begin{equation}\label{eq:04:nulovani_diferenci} \Delta^m p_n(x) = \nabla^m p_n(x) = \delta^m p_n(x) = 0 \quad \text{pro } m > n , \end{equation}neboť se vždy sníží řád polynomu minimálně o 1, a tedy Taylorova řada je konečná.
Protože \(\Delta = E - I\), platí
\[ \Delta^n = (E-I)^n = \sum_{k=0}^{n} (-1)^k \binom{n}{k} E^{n-k} , \]neboli, označíme-li \(x_i = x_0 + ih\), \(i = 1, \dots, n\), a \(p_i = p(x_i)\),
\begin{align*} \Delta p_i &= p_{i+1} - p_i , \\ \Delta^2 p_i &= p_{i+2} - 2p_{i+1} + p_i , \\ \Delta^3 p_i &= p_{i+3} - 3p_{i+2} + 3p_{i+1} - p_i \qquad \text{atd.} \end{align*}Obdobně pro \(\nabla = I - E^{-1}\) máme
\[ \nabla^n = (I - E^{-1})^n = \sum_{k=0}^{n} (-1)^k \binom{n}{k} E^{-k} \]a
\begin{align*} \nabla p_i &= p_i - p_{i-1} , \\ \nabla^2 p_i &= p_i - 2p_{i-1} + p_i \qquad \text{atd.} \end{align*}Derivace
Zavedeme operátor derivace \(D\,p(x) = p'(x)\). Pomocí Taylorova rozvoje máme
\begin{align*} (I+\Delta)p(x) = E\,p(x) = p(x+h) &= p(x) + h\,p'(x) + \frac{h^2}{2!}p''(x) + \dots \\ &= \left(I + hD + \frac{(hD)^2}{2!} + \dots\right) p(x) = e^{hD}\,p(x) , \end{align*}odkud
\begin{equation}\label{eq:04:hD_dopredna} hD = \ln(I+\Delta) = \Delta - \frac{1}{2}\Delta^2 + \frac{1}{3}\Delta^3 - \dots + (-1)^{k+1}\frac{\Delta^k}{k} + \dots \end{equation}Obdobně pro zpětnou diferenci je \(e^{-hD} = I - \nabla\), a tedy
\begin{equation}\label{eq:04:hD_zpetna} hD = \nabla + \frac{\nabla^2}{2} + \frac{\nabla^3}{3} + \dots \end{equation}Aplikujeme-li tyto vztahy na interpolační polynom funkce \(f(x)\) jdoucí body \(f_i = f(x_i)\), \(x_i = x_0 + ih\), a omezíme-li se na prvních několik členů, dostaneme vzorce pro přibližnou derivaci. Například dopředná konečná diference dává
\[ D f_i = f'(x_i) \cong \frac{\Delta f_i}{h} = \frac{f_{i+1}-f_i}{h} \qquad \text{s chybou } \mathcal{O}(h) , \]respektive
\begin{align*} D f_i &\cong \frac{1}{h}\left(\Delta - \frac{\Delta^2}{2}\right) f_i = \frac{f_{i+1}-f_i}{h} - \frac{f_{i+2}-2f_{i+1}+f_i}{2h} \\ &= \frac{-f_{i+2}+4f_{i+1}-3f_i}{2h} \qquad \text{s chybou } \mathcal{O}(h^2) . \end{align*}Pro centrovanou diferenci vezmeme
\[ \delta_{2h} = \Delta + \nabla = e^{hD} - e^{-hD} = 2\sinh(hD) , \]a tedy
\begin{equation}\label{eq:04:hD_centrovana} hD = \sinh^{-1}\frac{\Delta+\nabla}{2} = \frac{\Delta+\nabla}{2} - \frac{1}{6}\left(\frac{\Delta+\nabla}{2}\right)^3 + \dots \end{equation}Integrace
Nyní definujeme operátor integrace
\begin{align} J\,p(x) &= \int_x^{x+h} p(t)\,\mathrm{d}t = h\int_0^1 E^s p(x)\,\mathrm{d}s = h\int_0^1 e^{s\ln E}\,\mathrm{d}s\; p(x) \notag \\ &= h\,\frac{E-I}{\ln E}\,p(x) = \frac{h\Delta}{\ln(I+\Delta)}\,p(x) , \label{eq:04:operator_J} \end{align}kde jsme použili substituci \(t = x+sh\), \(\mathrm{d}t = h\,\mathrm{d}s\), formálně integrovali přes \(s\) a využili vztahu \(E^s p(x) = p(x+sh)\).
Můžeme tedy psát
\[ J\,p(x) = \frac{h\Delta}{hD}\,p(x) = \frac{\Delta}{D}\,p(x) \qquad \text{a tedy} \qquad JD = DJ = \Delta . \]Opět Taylorovým rozvojem dostaneme
\begin{equation}\label{eq:04:J_rozvoj} 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}Lze při tom využít trik \(\ln(I+\Delta) = \Delta(I-R)\), kde \(R = \frac{1}{2}\Delta - \frac{1}{3}\Delta^2 + \dots\), takže
\[ J = \frac{h}{I-R} = h\left(1 + R + R^2 + \dots\right) . \]Opět ponecháním prvních členů máme aproximaci integrálu přes interpolační polynom dané funkce, například
\begin{equation}\label{eq:04:lichobeznik} \int_{x_0}^{x_1} f(x)\,\mathrm{d}x = J f(x)\Big|_{x_0} \cong h f_0 + \frac{h}{2}(f_1 - f_0) = \frac{h(f_1+f_0)}{2} + \mathcal{O}(h^3) . \end{equation}