diff options
Diffstat (limited to 'content/numerik_dgl.tex')
| -rw-r--r-- | content/numerik_dgl.tex | 106 |
1 files changed, 64 insertions, 42 deletions
diff --git a/content/numerik_dgl.tex b/content/numerik_dgl.tex index 331ba77..1bf0c2d 100644 --- a/content/numerik_dgl.tex +++ b/content/numerik_dgl.tex @@ -9,7 +9,7 @@ Dann $\forall (\tilde x,\tilde y) \in G \exists$ Lösung $y'=f(x,y)$ im Gebiet. Sei $f : S \to \R^n$ stg. auf Steifen $S := [a,b] \times \R^n$ und $f$ erfülle die Lipschitz-Bedingung: \vspace*{-2mm} -$$\|f(x,y)-f(x,\tilde y)\| \leq L \|y-\tilde y\|, \ L > 0$$ +\[ \|f(x,y)-f(x,\tilde y)\| \leq L \|y-\tilde y\|, \ L > 0 \] Dann existiert für das AWP genau eine Lösung in $\mathcal{C}([a,b],\R^n)$ für jedes Element in $S$. @@ -20,7 +20,7 @@ Sei $f : [a,b] \times \R^n \to \R^n, \ y(x_0)=y_0 \in \R^n$ AWP. Ein \emph{Einschrittverfahren} ist Vorschrift: \vspace*{-4mm} -$$\eta_0 = y_0, \ \eta_{k+1} = \eta_k + h \cdot \Phi(x_k, \eta_k, h), \ x_{k+1} = x_k + h$$ +\[ \eta_0 = y_0, \ \eta_{k+1} = \eta_k + h \cdot \Phi(x_k, \eta_k, h), \ x_{k+1} = x_k + h \] Für \emph{Verfahrensfunktion} $\Phi : [a,b] \times \R^n \times \R \to \R^n$. @@ -29,19 +29,19 @@ Für \emph{Verfahrensfunktion} $\Phi : [a,b] \times \R^n \times \R \to \R^n$. Die \emph{Näherungslösung} $\eta_k$ ist eine \emph{Gitterfunktion}. \vspace*{-4mm} -$$\eta_k : \{x \in [x_0,b] | x = x_0 + i \cdot h, \ i \in \N_0 \} \to \R^n$$ +\[ \eta_k : \{x \in [x_0,b] | x = x_0 + i \cdot h, \ i \in \N_0 \} \to \R^n \] \subsection*{Explizites Eulerverfahren} -$$\Phi(x,y,h) := f(x,y) \text{ d.h. Butcher-Schema: } \begin{array}{c|c} +\[ \Phi(x,y,h) := f(x,y) \text{ d.h. Butcher-Schema: } \begin{array}{c|c} 0 & 0 \\ \hline & 1 -\end{array}$$ +\end{array} \] \subsection*{Implizites Eulerverfahren} -$$\Phi(x,y,h) := f(x+h, g(x,y,h)), \ g = y + h \cdot f(x+h, g)$$ +\[ \Phi(x,y,h) := f(x+h, g(x,y,h)), \ g = y + h \cdot f(x+h, g) \] Mit Butcher-Schema: $\begin{array}{c|c} 1 & 1 \\ @@ -56,7 +56,7 @@ Sei $z$ mit $z'(x) = f(x,z(x))$ die exakte AWP Lösung. Der \emph{lokale Diskretisierungsfehler} in $(x,y)$: -$$\tau(x,y,h) := \frac{z(x+h)-y}{h} - \Phi(x,y,h)$$ +\[ \tau(x,y,h) := \frac{z(x+h)-y}{h} - \Phi(x,y,h) \] Ein ESV ist brauchbar, wenn $\lim_{h \to 0} \tau(x,y,h) = 0$ bzw. $\lim_{h \to 0} \Phi(x,y,h) = f(x,y)$. @@ -65,7 +65,7 @@ Ein ESV ist brauchbar, wenn $\lim_{h \to 0} \tau(x,y,h) = 0$ bzw. $\lim_{h \to 0 ESV mit $\Phi$ ist \emph{konsistent mit Ordnung $p$}, falls: \vspace*{-2mm} -$$\tau(x,y,h) \in \mathcal{O}(h^p) \text{ für } h \to 0$$ +\[ \tau(x,y,h) \in \mathcal{O}(h^p) \text{ für } h \to 0 \] Hierzu ist eine Taylorentwicklung von $z$ hilfreich. @@ -73,7 +73,7 @@ Beide Eulerverfahren haben Ordnung $1$. \subsection*{Allgemeiner Ansatz für Ordnung $2$} -$$\Phi(x,y,h) := a_1 \cdot f(x,y) + a_2 \cdot f(x+p_1 h, y+p_2 h \cdot f(x,y))$$ +\[ \Phi(x,y,h) := a_1 \cdot f(x,y) + a_2 \cdot f(x+p_1 h, y+p_2 h \cdot f(x,y)) \] für Konstanten $a_1, a_2, p_1, p_2 \in \R$. @@ -83,11 +83,11 @@ Bedingungen: $a_1 + a_2 = 1, \ a_2 p_1 = \frac{1}{2}, \ a_2 p_2 = \frac{1}{2}$ \subsubsection*{Verfahren von Heun} -$$\Phi(x,y,h) := \frac{1}{2}(f(x,y) + f(x+h, y+h \cdot f(x,y)))$$ +\[ \Phi(x,y,h) := \frac{1}{2}(f(x,y) + f(x+h, y+h \cdot f(x,y))) \] \subsubsection*{Verfahren von Runge} -$$\Phi(x,y,h) := f(x + \frac{h}{2}, y + \frac{h}{2} f(x,y) )$$ +\[ \Phi(x,y,h) := f(x + \frac{h}{2}, y + \frac{h}{2} f(x,y) ) \] \subsubsection*{Implizite Trapezregel} @@ -102,16 +102,16 @@ g(x,y,h) &:= y + \frac{h}{2} (f(x,y) + f(x+h,g(x,y,h)) Der \emph{globale Diskretisierungsfehler} für $x \in [a,b]$: \vspace*{-4mm} -$$e(x,h_n) := \eta(x,h_n) - y(x), \ h_n=h_n(x)=\frac{x-x_0}{n}, n \in \N_0$$ +\[ e(x,h_n) := \eta(x,h_n) - y(x), \ h_n=h_n(x)=\frac{x-x_0}{n}, n \in \N_0 \] Ein ESV ist \emph{konvergent}, falls: \vspace*{-4mm} -$$\forall x \in [a,b], \text{hinr. glatte } f : \lim_{n \to \infty} e(x,h_n) = 0$$ +\[ \forall x \in [a,b], \text{hinr. glatte } f : \lim_{n \to \infty} e(x,h_n) = 0 \] \section*{Autonomisierung} -$$\eta := \begin{pmatrix}x \\ y\end{pmatrix} \in \R^{n+1}, \ \widehat{f} : \R^{n+1} \to \R^{n+1}, \eta \mapsto \begin{pmatrix}1 \\ f(x,y)\end{pmatrix}$$ +\[ \eta := \begin{pmatrix}x \\ y\end{pmatrix} \in \R^{n+1}, \ \widehat{f} : \R^{n+1} \to \R^{n+1}, \eta \mapsto \begin{pmatrix}1 \\ f(x,y)\end{pmatrix} \] AWP $\eta'=\widehat{f}(\eta)$ mit Bedingung: $\eta(0) = \begin{pmatrix}x_0 \\ y_0\end{pmatrix}$ @@ -119,7 +119,7 @@ AWP $\eta'=\widehat{f}(\eta)$ mit Bedingung: $\eta(0) = \begin{pmatrix}x_0 \\ y_ ESV $\Phi$ ist \emph{invariant gegen Autonomisierung}, wenn: -$$\widehat{\Phi}_1(\eta,h)=1, \ \Phi(x,y,h) = \widehat{\Phi}_2(\eta,h), \ \eta = \begin{pmatrix}x \\ y\end{pmatrix}$$ +\[ \widehat{\Phi}_1(\eta,h)=1, \ \Phi(x,y,h) = \widehat{\Phi}_2(\eta,h), \ \eta = \begin{pmatrix}x \\ y\end{pmatrix} \] Wobei $\widehat{\Phi} = \begin{pmatrix}\widehat{\Phi}_1, \widehat{\Phi}_2\end{pmatrix}$ die Anwendung von $\Phi$ auf das autonomisierte System ist. @@ -138,11 +138,11 @@ k_i &:= f(x+c_i h, y + h \sum_{j=1}^{i-1} a_{i,j} k_j) Darstellung der Koeffizienten $b_i, c_i$ und $a_{i,j}$: -$$\begin{array}{c|c} +\[ \begin{array}{c|c} c & A \\ \hline & b^\intercal -\end{array}$$ +\end{array} \] Hierbei ist $A$ strikte untere Dreiecksmatrix. @@ -156,37 +156,37 @@ Für die Ordnung $p$ eines $s$-stufigen RKV: $p \leq s$ RKV ist invariant gegen Autonomisierung gdw. es konsistent und $c_i$ die $i$-te Zeilensumme von $A$ ist: -$$\sum_{i=1}^s b_i = 1 \text{ und } \sum_{j=1}^{i-1} a_{i,j} = c_i \text{ für } i=1,\dots,s$$ +\[ \sum_{i=1}^s b_i = 1 \text{ und } \sum_{j=1}^{i-1} a_{i,j} = c_i \text{ für } i=1,\dots,s \] Somit genügt $(b, A)$ zur Definition von gegenüber Autonomisierung invarianter RKV. \subsection*{Konsistenzbedingung für Ordnung $2$} -$$\sum_{i=1}^s b_i = 1 , \sum_{i=1}^s b_i c_i = \frac{1}{2}$$ +\[ \sum_{i=1}^s b_i = 1 , \sum_{i=1}^s b_i c_i = \frac{1}{2} \] \subsection*{Konsistenzbedingung für Ordnung $3$} -$$\sum_{i=1}^s b_i = 1 , \sum_{i=1}^s b_i c_i = \frac{1}{2} , \sum_{i=1}^s b_i c_i^2 = \frac{1}{3} , \sum_{i,j=1}^s b_i a_{i,j} c_j = \frac{1}{6}$$ +\[ \sum_{i=1}^s b_i = 1 , \sum_{i=1}^s b_i c_i = \frac{1}{2} , \sum_{i=1}^s b_i c_i^2 = \frac{1}{3} , \sum_{i,j=1}^s b_i a_{i,j} c_j = \frac{1}{6} \] \section*{Explizite Extrapolationsverfahren} Numerische Lösung eines AWP in $k+1$ Gittern: -$$\begin{array}{c|ccc} +\[ \begin{array}{c|ccc} h & h_1 & \cdots & h_{k+1} \\ \hline \eta(x,h) & \eta(x,h_1) & \cdots & \eta(x,h_{k+1}) -\end{array}$$ +\end{array} \] Interpolation mit Polynom $\chi$: \vspace*{-2mm} -$$\chi(h_i) = \eta(x,h_i) \text{ für } i=1,\dots,k+1$$ +\[ \chi(h_i) = \eta(x,h_i) \text{ für } i=1,\dots,k+1 \] Auswertung von $\chi$ in $0$: \vspace*{-2mm} -$$\chi(0) = \lim_{h \to 0} \chi(h) \approx \lim_{h \to 0} \eta(x,h) = y(x)$$ +\[ \chi(0) = \lim_{h \to 0} \chi(h) \approx \lim_{h \to 0} \eta(x,h) = y(x) \] \section*{Schrittweitensteuerung} @@ -201,7 +201,7 @@ $\widehat{\eta}$ soll dazu von höherer Ordnung als $\eta$ sein. $h_i$ wird aktzeptiert, wenn $|[e_{i+1}]| \leq \text{tol}$ für $\text{tol} > 0$. \vspace{-2mm} -$$[e_{i+1}] = \widehat{\eta}_{i+1} - \eta_{i+1} = h_i(\widehat{\tau}_i - \tau_i)$$ +\[ [e_{i+1}] = \widehat{\eta}_{i+1} - \eta_{i+1} = h_i(\widehat{\tau}_i - \tau_i) \] Differenz lokaler Fehler schätzt globalen Fehler. @@ -261,7 +261,7 @@ $y$ ist \emph{asymptotisch stabil} gdw. $\forall \lambda \in \sigma(A) : \text{R Eine asymptotisch stabile DGL $y'=Ay+b$ ist \emph{steif}, wenn die negativen Realteile der Eigenwerte von $A$ sich um Größenordnungen unterscheiden: -$$\gamma := \frac{\max_{\lambda \in \sigma(A)}{|\text{Re}(\lambda)|}}{\min_{\lambda \in \sigma(A)}{|\text{Re}(\lambda)|}}$$ +\[ \gamma := \frac{\max_{\lambda \in \sigma(A)}{|\text{Re}(\lambda)|}}{\min_{\lambda \in \sigma(A)}{|\text{Re}(\lambda)|}} \] Typischerweise bewegt sich das \emph{Steifheitsmaß} $\gamma$ für reale Beispiele zwischen ${10}^3$ und ${10}^6$. @@ -285,8 +285,12 @@ Die Anzahl der Bedingungsgleichungen impliziter RKV entspricht der Anzahl für e Implizite RKV ohne Lösen der Bedingungsgl.: +\spacing + $u \in \Pi_s$ mit $u(x+h) = y+h\cdot\Phi(x,y,h)$ und $\forall i \in [s] : u'(x+c_i h) = f(x+c_i h,u(x+c_i h))$. +\spacing + d.h. $u$ erfüllt DGL in mindestens $s$ Stellen. Solche Verfahren sind durch $(c_1,\dots,c_s)$ gegeben. @@ -306,7 +310,8 @@ Für $k \in \N$ wird $\eta_{i+1}$ aus $\eta_{i+1-k},\dots,\eta_i$ berechnet. \emph{Lineares $k$-Schrittverfahren} berechnet $\eta(\cdot,h)$: -$$\sum_{i=0}^k \alpha_i \eta_{j+i} = h \cdot \sum_{i=0}^k \beta_i f(x_{j+i},\eta_{j+i})$$ +\vspace*{-2mm} +\[ \sum_{i=0}^k \alpha_i \eta_{j+i} = h \cdot \sum_{i=0}^k \beta_i f(x_{j+i},\eta_{j+i}) \] Mit Koeffizienten $\alpha_i, \beta_i \in \R$ für $i \in [k]$. @@ -318,11 +323,11 @@ Mit Koeffizienten $\alpha_i, \beta_i \in \R$ für $i \in [k]$. \subsection*{Darstellung mit Shiftoperator} -$$(E\varphi)(x) := \varphi(x+h)$$ - \vspace*{-4mm} - -$$\left(\sum_{i=0}^k \alpha_i E^i\right) \cdot \eta(x,h) = h \cdot \left(\sum_{i=0}^k \beta_i E^i\right) \cdot f(x,\eta(x,h))$$ +\begin{align*} +(E\varphi)(x) &:= \varphi(x+h) \\ +\left(\sum_{i=0}^k \alpha_i E^i\right) \cdot \eta(x,h) &= h \cdot \left(\sum_{i=0}^k \beta_i E^i\right) \cdot f(x,\eta(x,h)) +\end{align*} Noch kompakter mit Polynomen $\rho(\xi) = \sum_{i=0}^k \alpha_i \xi^i$ und $\sigma(\xi) = \sum_{i=0}^k \beta_i \xi^i$: $\rho(E)\eta = h \sigma(E) f$ @@ -330,7 +335,8 @@ Noch kompakter mit Polynomen $\rho(\xi) = \sum_{i=0}^k \alpha_i \xi^i$ und $\sig \emph{Differenzenoperator} aus $\rho(E)\eta - h\sigma(E)f = 0$: -$$L(x,y,h) := \frac{1}{h}\left(\rho(E)y(x) - h\sigma(E)y'(x)\right)$$ +\vspace*{-2mm} +\[ L(x,y,h) := \frac{1}{h}\left(\rho(E)y(x) - h\sigma(E)y'(x)\right) \] Ein lineares $k$-Schrittverfahren hat Konsistenzordnung $p$, wenn $\forall$ hinreichend glatte $f : L(x,y,h) \in \mathcal{O}(h^p)$ glm. $\forall x, h$ s.d. $[x,x+kh] \subset [x_0,b]$. @@ -351,6 +357,12 @@ Ein lineares $k$-Schrittverfahren hat Konsistenzordnung $p$ gdw. eine der folgen Insbesondere hat ein Mehrschrittverfahren die Ordnung $p=1$, falls: $\rho(1) = 0 \land \rho'(1) = \sigma(1)$ +\subsection*{Homogene lineare Differenzengleichung} + +\[ y_{n+k} + \sum_{i=0}^{k-1} \alpha_{i} y_{n+i} = 0 \] + +$k$-ter Ordnung mit Koeff. $\alpha_i \in \C$ für $i \in [k-1]$. + \subsection*{Stabilität} Lineares Mehrschrittverfahren $(\rho,\sigma)$ ist \emph{stabil}, wenn Differenzengleichung $\rho(E)\eta=0$ stabil ist. Dies ist der Fall gdw. $\forall$ Nullstellen $\xi$ von $\rho$ gilt: $|\xi| \leq 1$, dabei $|\xi|=1$ nur für einfache Nullstellen. @@ -361,15 +373,15 @@ Ein Mehrschrittverfahren ist \emph{strikt stabil}, wenn für Nullstellen $\xi \n \subsection*{Konvergenz} -Ein Mehrschrittverfahren konvergiert gegen Lösung $y \in \mathcal{C}^1(x_0,b)$ von $y'=f(x,y)$, $y(x_0)=y_0$, wenn sobald $\forall j \in [k-1] : \lim_{h \to 0} \eta(x_0+jh,h)=y_0$: +Ein Mehrschrittverfahren konvergiert gegen Lösung $y \in \mathcal{C}^1(x_0,b)$ von $y'=f(x,y)$, $y(x_0)=y_0$, wenn, sobald $\forall j \in [k-1] : \lim_{h \to 0} \eta(x_0+jh,h)=y_0$: -$$\forall x \in \mathcal{G}_k \cap [x_0,b] : \lim_{h \to 0} \eta(x,h) = y(x)$$ +\[ \forall x \in \mathcal{G}_k \cap [x_0,b] : \lim_{h \to 0} \eta(x,h) = y(x) \] Konvergentes lineares Mehrschrittverfahren ist stabil und konsistent. Insb. gilt $\rho'(1)=\sigma(1) \neq 0$. \spacing -Umgekehrt gilt auch: Stabiles und konsistentes Mehrschrittverfahren ist konvergent. +Umgekehrt auch: Ein stabiles und konsistentes Mehrschrittverfahren ist konvergent. \subsection*{Satz von Dahlquist} @@ -390,7 +402,7 @@ Verallgemeinerung der Euler-Verfahren. Setze $\rho(\xi) := \xi^k - \xi^{k-1}$ s.d. einfache Nst. $\xi=1$ und $(k-1)$-fache Nst. $\xi = 0$ gegeben sind. Dies ergibt: \vspace*{-2mm} -$$\eta_{k+1}-\eta_{j+k-1} = h \cdot \sigma(E) \cdot f(x_j,\eta(x_j,h))$$ +\[ \eta_{k+1}-\eta_{j+k-1} = h \cdot \sigma(E) \cdot f(x_j,\eta(x_j,h)) \] Für explizites Verfahren: $p = k$ mit $\beta_k = 0$. @@ -401,7 +413,7 @@ Für implizites Verfahren: $p = k+1$ mit $\beta_k \neq 0$. Lineare Differentialgleichungen in $d$ Variablen: \vspace*{-4mm} -$$-\sum_{i,j=1}^d a_{i,j}(x)\partial_{x_i x_j}^2 u + \sum_{i=1}^d b_i(x) \partial_{x_i} u + c(x)u(x) = f(x)$$ +\[ -\sum_{i,j=1}^d a_{i,j}(x)\partial_{x_i x_j}^2 u + \sum_{i=1}^d b_i(x) \partial_{x_i} u + c(x)u(x) = f(x) \] $A(x) := \{a_{i,k}(x)\}_{1\leq i,k \leq d}$ ist symmetrisch. @@ -452,17 +464,17 @@ Für $\ell = 1,\dots,d$ und Einheitsvektoren $e^{(\ell)} \in \R^d$ sei für $x \ \emph{Diskreter Laplace-Operator} $\Delta_h : V_h \to V_h^o$ ist geg.: \vspace*{-2mm} -$$\Delta_h v_h(x) := \sum_{\ell = 1}^d \partial_\ell^{+h} \partial_\ell^{-h} v_h(x)$$ +\[ \Delta_h v_h(x) := \displaystyle\sum\nolimits_{\ell = 1}^d \partial_\ell^{+h} \partial_\ell^{-h} v_h(x) \] Der \emph{allgemeine lineare Differentialoperator}: \vspace*{-4mm} -$$Lv(x) = -a(x)\Delta v(x) + \vec{b}(x) \cdot \nabla v(x) + c(x)v(x), \ x \in \Omega$$ +\[ Lv(x) = -a(x)\Delta v(x) + \vec{b}(x) \cdot \nabla v(x) + c(x)v(x), \ x \in \Omega \] wird auf $V_h$ für $x \in \mathcal{G}_h^o$ mit z.B. $\nabla^h := \left(\partial_1^h,\dots,\partial_d^h\right)$ approximiert durch: \vspace*{-4mm} -$$L_h v_h(x) = -a(x)\Delta_h v_h(x) + \vec{b}(x) \cdot \nabla^h v(x) + c(x)v_h(x)$$ +\[ L_h v_h(x) = -a(x)\Delta_h v_h(x) + \vec{b}(x) \cdot \nabla^h v(x) + c(x)v_h(x) \] \subsubsection*{Konsistenz von Operatoren} @@ -473,15 +485,25 @@ Der \emph{Restriktionsoperator} $I_h : \mathcal{C}^0(\overline\Omega) \to V_h$ i $L_h : V_h \to V_h^o$ und $L : \mathcal{C}^\infty(\Omega) \to \mathcal{C}^\infty(\Omega)$ sind \emph{konsistent} von Ordnung $\kappa > 0$ bzgl. $\|\cdot\|_h$ auf $V_h$, wenn: \vspace*{-4mm} -$$\forall v \in \mathcal{C}^\infty(\Omega) : \|I_h^o Lv - L_h I_h v\|_h \leq C h^\kappa \text{ für } h \to \infty$$ +\[ \forall v \in \mathcal{C}^\infty(\Omega) : \|I_h^o Lv - L_h I_h v\|_h \leq C h^\kappa \text{ für } h \to \infty \] Norm $\|\cdot\|_{h,\infty}$ auf $V_h$ ist def.: $\|v_h\|_{h,\infty} := \displaystyle\max_{x \in \mathcal{G}_h} |v_h(x)|$ +Konkret für $v \in \mathcal{C}^\infty(\Omega)$ und $x \in \mathcal{G}_h^o$: + +\vspace*{-4mm} +\begin{align*} +\partial_\ell v(x) - \partial_\ell^{\pm h} v(x) &= \mp \frac{1}{2} h \partial_\ell^2 v(x) + \mathcal{O}(h^2) \\ +\partial_\ell v(x) - \partial_\ell^h v(x) &= - \frac{1}{6} h^2 \partial_\ell^3 v(x) + \mathcal{O}(h^4) \\ +\Delta v(x) - \Delta_h v(x) &= - \frac{1}{12} h^2 \textstyle\sum_{i=1}^d \partial_i^4 v(x) + \mathcal{O}(h^4) +\end{align*} + \subsubsection*{Differenzensterne} Für $S := \{ e \in \Z^d | |e|_\infty \leq 1 \}$ können diskrete Operatoren dargestellt werden als: -$$L_h v_h(x) = \sum_{e \in S} a_e(x) v_h(x+he)$$ +\vspace*{-2mm} +\[ L_h v_h(x) = \displaystyle\sum\nolimits_{e \in S} a_e(x) v_h(x+he) \] \emph{Stencil} für $d=1$: $\begin{bmatrix} a_{-1}(x) & a_0(x) & a_1(x) \end{bmatrix}$. |