Implizite RK-Verfahren (Teil 2/2)

steife-differentialgleichungen.tex

@@ -556,7 +556,7 @@ Fase die Koeffizienten zusammen in zwei Vektoren $b,c \in \R^s$ und Matrix $\mat
 				&= \max_{1\le i \le s} \abs{F_i(\tau,g) - F_i(\tau, \bar g)} \\
 				&= \max_{1\le i \le s} \abs{x_0 + \tau \sum_{j=1}^s a_{ij} f(t_0 + c_j \tau, g_j ) - x_0
 					- \tau \sum_{j=1}^s a_{ij} f(t_0 + c_j \tau, \bar g_j ) } \\
-				& \le \tau_\ast \norm{\mathcal A}_\infty  \max_{1\le i \le s}  \abs{f(t_0 + c \widetilde s, g_j) - f(t_0 + c_j \tau, \bar g_j)}
+				& \le \tau_\ast \norm{\mathcal A}_\infty  \max_{1\le i \le s}  \abs{f(t_0 + c \tau, g_j) - f(t_0 + c_j \tau, \bar g_j)}
 		\end{align*} 
 		\item Da $f$ lokal Lipschitz-stetig im zweiten Argument ist, gilt:
 		\begin{align*}
@@ -576,6 +576,89 @@ Fase die Koeffizienten zusammen in zwei Vektoren $b,c \in \R^s$ und Matrix $\mat
 		\item $g(\tau)$ ist stetig in $\tau$, insbesondere ist $g(0) = g_\ast$.
 	\end{itemize}
 \end{proof}
+Darstellung der impliziten RK-Verfahren wieder im Butcher-Schema:
+\begin{center}
+	\begin{tabular}{c|c}
+		$c$ & $\mathcal A$ \\
+		\hline
+		& $b^T$
+	\end{tabular}
+\end{center}
+\begin{bsp}[Implizites Euler-Verfahrens]~\\
+	\begin{center}
+		\begin{tabular}{c|c}
+			$1$ & $1$ \\
+			\hline
+			& $1$
+		\end{tabular}
+	\end{center}
+\end{bsp}
+Implizite RK-Verfahren sind wohldefiniert.
+\begin{satz} \label{satz:RK_Existenz_und_Eindeutigkeit}
+	Falls $f$ stetig und in $x$ lokal Lipschitz-stetig ist, so hat das RK-System f\"ur kleine $\tau$ eine eindeutige L\"osung, die stetig von $\tau$ abh\"angt.
+\end{satz}
+Wie sieht es mit Konsistenz und Stabilit\"at aus?
+\begin{satz}
+	Unter den Bedingingungen des obigen Satzes gilt:
+	\begin{itemize}
+		\item Die Evolution $\Psi$ ist genau dann konsistent, wenn 
+		  $$\sum_{i=1}^s b_i = 1. $$
+		\item Ist $f \in C^p(\Omega, \R^d)$, so ist auch $\Psi^{t+\tau, t} x$ in $\tau$ $p$-fach differenzierbar. 
+	\end{itemize}
+\end{satz}
+\textbf{Erinnerung:} Konsistenztheorie f\"ur explizite RK-Verfahren
+\begin{itemize}
+	\item Entwickle $\Phi$ und $\Psi$ als Taylorreihen
+	\item W\"ahle die Koeffizienten $b,c, \mathcal A$ so, dass m\"oglichst viele Terme aus der Taylorreihe von $\Phi$  reproduziert werden.
+\end{itemize}
+Im Prinzip funktioniert das f\"ur implizite Verfahren genauso.
+\begin{itemize}
+	\item Alles etwas komplizierter: Es m\"ussen mehr Koeffizienten bestimmt werden.
+	\item Alles etwas einfacher: F\"ur eine gegebene Ordnung $p$ erh\"alt man die gleiche Anzahl von Bestimmungsgleichungen wie im expliziten Fall \cite[Satz~4.24]{deuflhard_bornemann:2008}. Man hat aber mehr Freiheitsgrade, um diese zu erf\"ullen.
+	\item Wie f\"ur explizite Verfahren zeigt man: Ein implizites Verfahren ist genau dann invariant unter Autnomosierung, wenn es konsistent ist, und 
+	$$ c_i = \sum_{j=1}^{s} a_{ij} \qquad \text{f\"ur } i=1,\dots, s. $$ 
+\end{itemize}
+Wie bestimmt man jetzt die Koeffizienten? Eine Technik kommt gleich!
+
+Welche Ordnung kann man maximal erzielen?
+\begin{itemize}
+	\item Daf\"ur braucht man die Stabilit\"atsfunktion.
+\end{itemize}
+
+\begin{lemma} 
+	Die Stabilit\"atsfunktion $R$ eines $s$-stufigen RK-Verfahrens $(b,\mathcal A)$ ist durch 
+	$$ R(z) = 1 + zb^T (I - z\mathcal A)^{-1} (1,\dots,1)^T $$
+	gegeben. Die Funktion $R$ kann in eindeutiger Weise als 
+	$$ R(z) = \frac{P(z)}{Q(z)} $$
+	dargestellt werden, wobei $P,Q$ teilerfremde Polynome h\"ochstens $s$-ten Grades mit $P(0) = Q(0) = 1$ sind.
+\end{lemma}
+\begin{proof}
+	\"Ubung.
+\end{proof}
+\textbf{Erinnerung:} Ein $s$-stufiges explizites RK-Verfahren hat h\"ochstens die Konsistenzordnugn $p \le s$.
+\begin{lemma}
+	Ein $s$-stufiges implizites RK-Verfahren besitze f\"ur alle $f \in C^\infty(\Omega, \R^d)$ die Konsistenzordnung $p \in \N$. Dann gilt $ p \le 2s$.
+\end{lemma}
+\begin{proof}
+	\begin{itemize}
+		\item Betrachte das AWP $x' = x$, $x(0) =1$.
+		\item L\"osung: $x(\tau) = e^{\tau}$, RK-Approximation $\Psi^\tau$.
+		\item Das Verfahren ist konsistent mit Konsistenzordnung $p$, also gilt
+			$$ \Psi^\tau 1 - \Phi^\tau 1 = R(\tau) - e^\tau = \mathcal O(\tau^{p+1}).$$
+		\item $R = P / Q$ ist Quotient zweier Polynome mit Ordnung jeweils $\le s$.
+		\item Es folgt $p \le \deg P + \deg Q \le 2s$
+	\end{itemize}
+	Warum?
+	\begin{itemize}
+		\item Angenommen es g\"abe Polynome $P, Q$ mit 
+			$$ \deg P \le k, \qquad \deg Q \le j,$$
+			und $k+j < p$.
+		\item Das hie\ss e $P(z) / Q(z) - e^z = \mathcal O(z^{k+j+2})$.
+		\item Multiplikation mit $Q(z)$: $P(z) - Q(z)e^z =  \mathcal O(z^{k+j+2})$.
+		\item Daraus folgt $P = Q = 0$. Widerspruch!
+	\end{itemize}
+	Beweis davon: \"Ubung. \cite[Lemma~6.4]{deuflhard_bornemann:2008}
+\end{proof}
 \section{Kollokationsverfahren}
 
 \section{Dissipative Differentialgleichungen}