\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}
