\section*{Existenzsatz von Peano} Sei $f : G \subset \R \times \R^n \to \R^n$ stg., $G$ Gebiet. Dann $\forall (\tilde x,\tilde y) \in G \exists$ Lösung $y'=f(x,y)$ im Gebiet. \section*{Existenz- und Eindeutigkeit} 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$$ Dann existiert für das AWP genau eine Lösung in $\mathcal{C}([a,b],\R^n)$ für jedes Element in $S$. \section*{Einzelschrittverfahren} 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$$ Für \emph{Verfahrensfunktion} $\Phi : [a,b] \times \R^n \times \R \to \R^n$. \spacing 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$$ \subsection*{Explizites Eulerverfahren} $$\Phi(x,y,h) := f(x,y) \text{ d.h. Butcher-Schema: } \begin{array}{c|c} 0 & 0 \\ \hline & 1 \end{array}$$ \subsection*{Implizites Eulerverfahren} $$\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 \\ \hline & 1 \end{array}$ \subsection*{Konsistenz} 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)$$ 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)$. \subsubsection*{Konsistenzordnung} 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$$ Hierzu ist eine Taylorentwicklung von $z$ hilfreich. 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))$$ für Konstanten $a_1, a_2, p_1, p_2 \in \R$. \spacing 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)))$$ \subsubsection*{Verfahren von Runge} $$\Phi(x,y,h) := f(x + \frac{h}{2}, y + \frac{h}{2} f(x,y) )$$ \subsubsection*{Implizite Trapezregel} \vspace*{-2mm} \begin{align*} \Phi(x,y,h) &:= \frac{1}{2} (f(x,y) + f(x+h, g(x,y,h)) \\ g(x,y,h) &:= y + \frac{h}{2} (f(x,y) + f(x+h,g(x,y,h)) \end{align*} \subsection*{Konvergenz} 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$$ 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$$ \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}$$ AWP $\eta'=\widehat{f}(\eta)$ mit Bedingung: $\eta(0) = \begin{pmatrix}x_0 \\ y_0\end{pmatrix}$ \subsection*{Invarianz gegen Autonomisierung} 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}$$ Wobei $\widehat{\Phi} = \begin{pmatrix}\widehat{\Phi}_1, \widehat{\Phi}_2\end{pmatrix}$ die Anwendung von $\Phi$ auf das autonomisierte System ist. \section*{Explizite Runge-Kutta-Verfahren} Verfahrensfunktion $\Phi$ eines $s$-stufigen RKV: \vspace*{-4mm} \begin{align*} \Phi(x,y,h) &:= b_1 k_1 + b_2 k_2 + \cdots + b_s k_s \\ k_i &:= f(x+c_i h, y + h \sum_{j=1}^{i-1} a_{i,j} k_j) \end{align*} \vspace*{-8mm} \subsection*{Butcher-Schema} Darstellung der Koeffizienten $b_i, c_i$ und $a_{i,j}$: $$\begin{array}{c|c} c & A \\ \hline & b^\intercal \end{array}$$ Hierbei ist $A$ strikte untere Dreiecksmatrix. \subsection*{Konsistenzbedingung für Ordnung 1} Konsistent mit Ordnung 1 gdw. $\displaystyle\sum_{i=1}^s b_i = 1$ Für die Ordnung $p$ eines $s$-stufigen RKV: $p \leq s$ \subsection*{Invarianzbedingung} 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$$ 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}$$ \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}$$ \section*{Explizite Extrapolationsverfahren} Numerische Lösung eines AWP in $k+1$ Gittern: $$\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}$$ Interpolation mit Polynom $\chi$: \vspace*{-2mm} $$\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)$$ \section*{Schrittweitensteuerung} $h_i = x_{i+1} - x_i$ soll groß genug sein, den Aufwand für die Lösung klein zu halten und gleichzeitig klein genug um Genauigkeit zu garantieren. \spacing Der globale Diskretisierungsfehler $e(x_{i+1},h_i)$ wird durch $[e_{i+1}] = \widehat{\eta}_{i+1} - \eta_{i+1}$ geschätzt. $\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)$$ Differenz lokaler Fehler schätzt globalen Fehler. \subsection*{Adaptiver Algorithmus} Während $x_i < b$ setze $x := x_i + h_i$ und: \vspace{-4mm} \begin{align*} y &:= \eta_i + h_i \Phi(x_i,\eta_i,h_i) \\ \widehat{y} &:= \eta_i + h_i \widehat{\Phi}(x_i,\eta_i,h_i) \\ [e] &:= |y-\widehat{y}| \\ h &:= \min\left\{rh, h_\text{max}, \varrho h_i \sqrt[p+1]{\frac{\text{tol}}{|[e]|}}\right\}, \ \varrho \in (0,1), \ r > 1 \end{align*} Falls $[e] \leq \text{tol}$: \vspace*{-10.7mm} \begin{align*} \hspace*{4mm} x_{i+1} &:= x \\ \eta_{i+1} &:= \widehat{y} \\ h_{i+1} &:= \min\{h, b-x_{i+1}\} \end{align*} Ansonsten verwerfe Schritt mit $h_i := h$. \section*{Stabilität von DGLs} Sei $y' = f(x,y), \ x \in [0,\infty), y(x) \in \R^n$ System von $n$ DGLs und habe $\forall (x_0, y_0) \in [0,\infty) \times \R^n$ eindeutige Lösung $\varphi \in \mathcal{C}^1([0,\infty))$. \spacing Diese Lösung $\varphi$ ist \emph{stabil}, wenn: $\forall \epsilon > 0 \ \exists \ \delta > 0 \ \forall y \in \mathcal{C}^1([0,\infty)) : \\ \|\varphi(x_0) - y(x_0)\| < \delta \implies \forall x \geq x_0 : \|\varphi(x)-y(x)\| < \epsilon$. \spacing Diese Lösung $\varphi$ ist \emph{asymptotisch stabil}, wenn sie stabil ist und zusätzlich $\exists \ \delta > 0 \ \forall y \in \mathcal{C}^1([0,\infty)) : \|\varphi(x_0)-y(x_0)\| < \delta \implies \displaystyle\lim_{x \to \infty} \|\varphi(x)-y(x)\| = 0$. \subsection*{Stabilität von linearen DGLs} Sei $y'=Ay, \ y(x_0) = y_0$ mit $A \in \R^{n \times n}$ eine lineare DGL mit Lösung $y(x) = e^{(x-x_0)A}y_0$. Hierbei ist $e^{xA} := \sum_{k=0}^\infty \frac{(xA)^k}{k!} \in \R^{n \times n}$ gegeben. \spacing $y$ ist \emph{stabil} gdw. $\forall \lambda \in \sigma(A) : \text{Re}(\lambda) \leq 0$ und für $\lambda \in \sigma(A)$ mit $\text{Re}(\lambda) = 0$ gilt $\mu_a(A,\lambda) = \mu_g(A,\lambda)$. \spacing $y$ ist \emph{asymptotisch stabil} gdw. $\forall \lambda \in \sigma(A) : \text{Re}(\lambda) < 0$. \subsection*{Steife Differentialgleichungen} 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)|}}$$ Typischerweise bewegt sich das \emph{Steifheitsmaß} $\gamma$ für reale Beispiele zwischen ${10}^3$ und ${10}^6$. \spacing Zur numerischen Lösung steifer DGLs sind implizite Verfahren geeignet. \subsection*{Implizite Runge-Kutta-Verfahren} Ein $s$-stufiges RKV ist \emph{implizit}, wenn zugehörige $A \in \R^{s \times s}$ keine strikte untere Dreiecksmatrix ist. \spacing $(c,b,A)$ ist invariant gegen Autonomisierung gdw. es konsistent ist und $\forall i \in [s] : c_i = \sum_{j=1}^s a_{i,j}$ gilt. \spacing Die Anzahl der Bedingungsgleichungen impliziter RKV entspricht der Anzahl für explizite RKV. Implizite RKV bieten jedoch mehr Freiheitsgrade. \subsubsection*{RKV vom Kollokationstyp} Implizite RKV ohne Lösen der Bedingungsgl.: $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))$. d.h. $u$ erfüllt DGL in mindestens $s$ Stellen. Solche Verfahren sind durch $(c_1,\dots,c_s)$ gegeben. Interpretiert als $s$-stufiges implizites RKV: \vspace*{-4mm} \begin{align*} a_{i,j} &:= \int_0^{c_i} L_j(\vartheta) \ d\vartheta \\ k_i &:= f(x+c_ih,y+h\sum_{j=1}^s a_{i,j} k_j) \\ b_j &:= \int_0^1 L_j(\vartheta) d\vartheta \end{align*} \section*{Mehrschrittverfahren} 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})$$ Mit Koeffizienten $\alpha_i, \beta_i \in \R$ für $i \in [k]$. \spacing \emph{Explizites $k$-Schrittverfahren}: $\beta_k = 0, \ |\alpha_0|+|\beta_0| > 0$ \emph{Implizites $k$-Schrittverfahren}: $\beta_k \neq 0, \ \alpha_k \neq 0$ \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))$$ 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$ \subsection*{Konsistenz} \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)$$ 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]$. \spacing Einsetzen von Einschrittverfahren in $L$ ergibt den lokalen Diskretisierungsfehler. \subsection*{Konsistenzcharakterisierung} Ein lineares $k$-Schrittverfahren hat Konsistenzordnung $p$ gdw. eine der folgenden Bed. gilt: \begin{enumerate}[label=(\alph*)] \item Für glatte $y: L(x,y,h) \in \mathcal{O}(h^p)$ glm. in $x, h$ \item $\forall Q \in \Pi_p : L(x,Q,h) = 0$ \item $L(0,\text{exp},h) = \frac{1}{h}(\rho(e^h)-h\sigma(e^h)) \in \mathcal{O}(h^p)$ \item For $m = 1, \dots, p$: \\ $\sum_{j=0}^k \alpha_j = 0, \ \sum_{j=0}^k \alpha_j j^m = m \sum_{j=0}^k \beta_j j^{m-1}$ \end{enumerate} Insbesondere hat ein Mehrschrittverfahren die Ordnung $p=1$, falls: $\rho(1) = 0 \land \rho'(1) = \sigma(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. \subsubsection*{Strikte Stabilität} Ein Mehrschrittverfahren ist \emph{strikt stabil}, wenn für Nullstellen $\xi \neq 1$ von $\rho$ gilt: $|\xi| < 1$ \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$: $$\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. \subsection*{Satz von Dahlquist} Für die Konsistenzordnung $p$ eines stabilen linearen $k$-Schrittverfahrens gilt: \begin{enumerate} \item $p \leq k + 2$ wenn $k$ gerade \item $p \leq k + 1$ wenn $k$ ungerade \item $p \leq k$ wenn $\frac{\beta_k}{\alpha_k} \leq 0$,\\ d.h. insb für explizite Verfahren \end{enumerate} Für die Konsistenzordnung $p$ von strikt stabilen linearen $k$-Schrittverfahren gilt $p \leq k + 1$. \subsection*{Adams-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))$$ Für explizites Verfahren: $p = k$ mit $\beta_k = 0$. Für implizites Verfahren: $p = k+1$ mit $\beta_k \neq 0$. \section*{Partielle Differentialgleichungen} \subsection*{Finite Differenzen}