numerik-pdes.tex

\documentclass{cheat-sheet}

\pdfinfo{
  /Title (Zusammenfassung Numerik von partiellen Differentialgleichungen)
  /Author (Tim Baumann)
}

\usepackage{nicefrac}
\usepackage{tikz}
\usepackage{bbm} % Für 1 mit Doppelstrich (Indikatorfunktion)
\usepackage{tikzsymbols} % Smileys!

% Kleinere Klammern
\delimiterfactor=701

\newcommand{\Cont}{\mathcal{C}} % Menge der stetigen/diff'baren Funktionen
\newcommand{\clos}[1]{\overline{#1}} % topologischer Abschluss
\newcommand{\cOmega}{\clos{\Omega}} % weil's so häufig gebraucht wird
\newcommand{\bOmega}{\partial \Omega} % weil's so häufig gebraucht wird
\newcommand{\IntOmega}[2]{\AInt{\Omega}{#1}{#2}} % Integral über \Omega
\newcommand{\IntbOmega}[2]{\AInt{\bOmega}{#1}{#2}} % Integral über den Rand von \Omega
\newcommand{\LL}{\mathcal{L}} % Lösungsoperator
\newcommand{\RR}{\mathcal{R}} % Randoperator
\newcommand{\Laplace}{\Delta}
\DeclareMathOperator{\dive}{div} % Divergenz
\newcommand{\tss}[1]{\textsubscript{#1}} % Subskript, kürzer
\renewcommand{\O}{\mathcal{O}} % Landau-Symbol
\newcommand{\DO}{\mathcal{D}} % Differentialoperator
\newcommand{\scp}[2]{\left\langle #1 , #2 \right\rangle} % Skalarprodukt
\DeclareMathOperator*{\esssup}{ess\,sup} % Essentielles Supremum
\newcommand{\loc}{\text{loc}} % lokal
\newcommand{\ind}{\mathbbm{1}} % Indikatorfunktion
\newcommand{\Testfun}{\mathcal{D}} % Raum der Testfunktionen
\DeclareMathOperator{\spann}{span} % Spann
\DeclareMathOperator{\inte}{int} % Inneres (interior)
\DeclareMathOperator{\GL}{GL}
\newcommand{\Poly}{\mathbbm{P}} % Menge der Polynome
\newcommand{\Qoly}{\mathbbm{Q}} % Menge der in jeder Koordinate im Grad beschränkten Polynome
\newcommand{\tprime}{\ensuremath{^\prime}} % im Textmodus verwendbares \prime

% Folgender Code wird benötigt, um in einer Array-Umgebung eine rechtsausgerichtete Spalte einer bestimmten Breite zu erzeugen
% http://tex.stackexchange.com/a/21332
\usepackage{array}
\newcolumntype{R}[1]{>{\hbox to #1\bgroup\hfill$}c<{$\egroup}}
% LaTeX ist so ein Kack!

% Hervorhebung von Problembezeichnungen
\definecolor{ProblemColor}{rgb}{0.7,0.2,0.0}
\newcommand{\probl}[1]{\textcolor{ProblemColor}{#1}}

\begin{document}

\raggedcolumns % stretche Inhalt nicht über die gesamte Spaltenhöhe

\maketitle{Zusammenfassung Numerik von PDEs}

Dies ist ein verkürztes Skript zur gleichnamigen Vorlesung von Frau Prof. Dr. Tatjana Stykel an der Universität Augsburg im WS\,15/16.

% Vorlesung vom 13. Oktober 2015

% 1. Einführung

% Ausgelassen: Notationen

% 1.1. Klassifikation von partiellen DGLn

\begin{defn}
  Sei $\Omega \subseteq \R^n$ offen.
  Eine DGL der Form
  \[ F(x, u, \DO u, \ldots, \DO^k u) = 0 \]
  heißt \emph{partielle DGL/PDE} der Ordnung $k \geq 1$, wobei
  \[ F : \Omega \times \R \times \R^n \times \ldots \times \R^{n^k} \to \R \]
  eine gegebene Funktion und $u : \Omega \to \R$ gesucht ist.
\end{defn}

\begin{defn}[\emph{Klassifikation von PDEs}]\mbox{}\\
  \begin{itemize}
    \item Die PDE heißt \emph{linear}, wenn sie die Form
    \[ \sum_{\abs{\alpha} \leq k} a_\alpha(x) \DO^\alpha u = f(x) \]
    mit Funktionen $a_\alpha$, $f : \Omega \to \R$ besitzt.
    \item Die PDE heißt \emph{semilinear}, wenn sie die Form
    \[ \sum_{\abs{\alpha} = k} a_\alpha(x) \DO^\alpha u + a_0(x, u, \DO u, \ldots, \DO^{k-1} u) = 0 \]
    besitzt, wobei $a_\alpha : \Omega \to \R$ und $a_0 : \Omega \times \R \times \R^n \times \ldots \times \R^{n^{k-1}} \to \R$ gegeben sind.
    \item Die PDE heißt \emph{quasilinear}, wenn sie die Form
    \[ \sum_{\abs{\alpha} = k} a_\alpha(x, u, \DO u, \ldots, \DO^{k-1} u) \DO^\alpha u + a_0(x, u, \DO_u, \ldots, \DO^{k-1} u) = 0 \]
    hat, wobei $a_\alpha, a_0 : \Omega \times \R \times \R^n \times \ldots \times \R^{n^k}$ gegeben sind.
    \item Die PDE heißt \emph{nichtlinear}, falls die Ableitungen der höchsten Ordnung nicht linear vorkommen.
  \end{itemize}
\end{defn}

% Ausgelassen: Beispiele: Poisson-, Laplace-, Wärmeleitungs-, Wellengleichung sowie Navier-Stokes-Gleichung

\begin{defn}
  Sei $\Omega \subseteq \R^n$ offen und $F : \Omega \times \R \times \R^n \times \R^{n \times n} \to \R$ gegeben.
  Eine \emph{PDE zweiter Ordnung} ist eine PDE der Form
  \[ F(x, u, \partial_{x_1} u, \ldots, \partial_{x_n} u, \partial_{x_1} \partial_{x_1} u, \ldots, \partial_{x_1} \partial_{x_n} u, \ldots, \partial_{x_n} \partial_{x_n} u) = 0. \]
\end{defn}

\begin{nota}
  Für eine PDE 2. Ordnung sei
  $p_i \coloneqq \partial_{x_i} u$, $p_{ij} \coloneqq \partial^2_{x_i x_j} u$,
  \[
    M(x) \coloneqq \begin{pmatrix}
      \tfrac{\partial F}{\partial p_{11}} & \hdots & \tfrac{\partial F}{\partial p_{1n}} \\
      \vdots && \vdots \\
      \tfrac{\partial F}{\partial p_{n1}} & \hdots & \tfrac{\partial F}{\partial p_{nn}}
    \end{pmatrix} = M(x)^{T}.
  \]
\end{nota}

\begin{defn}[\emph{Typeneinteilung für PDEs der 2. Ordnung}]\mbox{}\\
  Obige PDE zweiter Ordnung heißt
  \begin{itemize}
    \item \emph{elliptisch} in~$x$, falls die Matrix~$M(x)$ positiv o. negativ definit ist.
    \item \emph{parabolisch} in~$x$, falls genau ein EW von~$M(x)$ gleich null ist und alle anderen EWe dasselbe Vorzeichen haben.
    \item \emph{hyperbolisch} in~$x$, falls genau ein EW von~$M(x)$ ein anderes Vorzeichen als die anderen EWe hat.
  \end{itemize}
\end{defn}

% Ausgelassen: Beispiele

% Vorlesung vom 19. Oktober 2015

% 2. Klassische Lösungstheorie für elliptische PDEs
\section{Lösungstheorie elliptischer PDEs}

\begin{defn}
  Sei $\Omega \subset \R^n$ offen, zusammenhängend und beschränkt.
  \begin{itemize}
    \item $\Cont(\cOmega, \R^m) \coloneqq \Set{u : \cOmega \to \R^m}{u \text{ stetig}}$, $\Cont(\cOmega) \coloneqq \Cont(\cOmega, \R)$, mit Norm
    \[
      \norm{u}_{\Cont(\cOmega, \R^m)} \coloneqq {\sup}_{x \in \cOmega} \norm{u(x)}.
      \tag{\textit{Supremumsnorm}}
    \]
    \item $\Cont^k(\cOmega, \R^m)$, $k \in \N$ ist der Raum aller auf $\Omega$ $k$-mal stetig diff'baren Funktionen $u : \Omega \to \R^m$, die zusammen mit ihren Ableitungen bis zur Ordnung $k$ stetig auf $\cOmega$ fortgesetzt werden können mit Norm
    \[ \norm{u}_{\Cont^k(\overline{\Omega}, \R^m)} \coloneqq \sum_{\abs{\alpha} \leq k} \norm{\DO^\alpha u}_{\Cont(\overline{\Omega}, \R^m)}. \]
    \item Für $\alpha \!\in\! \ocinterval{0}{1}$ ist $\Cont^{0,\alpha}(\cOmega, \R^m) \!\coloneqq\! \Set{u \!\in\! \Cont(\cOmega, \R^m)}{H_\alpha(u, \cOmega) \!<\! \infty}$ mit
    \[
      H_\alpha(u, \cOmega) \coloneqq \sup_{x, y \in \cOmega, x \neq y} \tfrac{\norm{u(x)-u(y)}}{\norm{x-y}^\alpha}
      \tag{\textit{Hölder-Koeffizient}}
    \]
    der \emph{Raum der glm. Hölder-stetigen Fktn} zum Exponent $\alpha$.
    Der Hölder-Koeffizient ist dabei eine Seminorm auf $\Cont^{0,\alpha}(\cOmega, \R^m)$.
    \item $\Cont^{k,\alpha}(\cOmega, \R^m) \coloneqq \Set{u \in \Cont^k(\cOmega, \R^m)}{\fa{\abs{\gamma} = k} \DO^\gamma u \in \Cont^{0, \alpha}(\cOmega, \R^m)}$ heißt \emph{Hölder-Raum}.
    Eine Norm ist gegeben durch
    \[ \norm{u}_{\Cont^{k,\alpha}(\cOmega, \R^m)} \coloneqq \norm{u}_{\Cont^k(\cOmega, \R^m)} + \sum_{\abs{\gamma} = k} H_\alpha(\DO^\gamma u, \cOmega). \]
  \end{itemize}
\end{defn}

\begin{bem}
  \begin{itemize}
    \item Jede Hölder-stetige Funktion ist gleichmäßig stetig.
    \item $\Cont^{0,1}(\cOmega, \R^m)$ heißt \emph{Raum der Lipschitz-stetigen Funktionen}.
    \item $\Cont$, $\Cont^k$ und $\Cont^{k,\alpha}$ sind Banach-Räume mit den jeweiligen Normen.
  \end{itemize}
\end{bem}

\iffalse
\begin{bsp}
  Betrachte $u(x) = \abs{x}^\beta$ auf $\ointerval{-1}{1} = \Omega$. Dann ist
  \[ \tfrac{\abs{u(x) - u(0)}}{\abs{x - 0}^\alpha} = \abs{X}^{\beta - \alpha} \]
  genau dann beschränkt, falls $\beta \geq \alpha$.
  In diesem Fall ist $u$ Hölder-stetig zum Exponent $\alpha$.
\end{bsp}
\fi

\begin{defn}
  Sei $\Omega \subset \R^n$ offen, zusammenhängend und beschränkt. \\
  Das Gebiet $\Omega$ gehört zur \emph{Klasse $\Cont^{k,\alpha}$}, wenn in jedem Punkt $x \in \bOmega$ eine Umgebung in $\bOmega$ existiert, die sich in einem geeigneten Koordinatensystem als ein Graph einer Funktion aus $\Cont^{k,\alpha}$ darstellen lässt und $\Omega$ lokal immer auf einer Seite von $\bOmega$ liegt.
\end{defn}

% Ausgelassen: Beispiele und Gegenbeispiele von Gebieten aus $\Cont^{k,\alpha}$

\begin{satz}[\emph{Gauß'scher Integralsatz}]
  Sei $\Omega \subset \R^n$ ein Lipschitz-Gebiet und $u \in \Cont(\cOmega, \R^n) \cap \Cont^1(\Omega, \R^n)$.
  Dann gilt
  \[ \IntOmega{\dive u}{x} = \IntOmega{\sum_{i=1}^n \tfrac{\partial u_i}{\partial x_i}}{x} = \IntbOmega{\sum_{i=1}^n u_i \nu_i}{\rho(x)} = \IntbOmega{u \cdot \nu}{\rho(x)}, \]
  wobei $\nu$ der äußere Normalenvektor an an den Rand von $\Omega$ ist.
\end{satz}

\begin{prob}
  Wir betrachten das Randwertproblem
  \[
    \text{\probl{(RWP)}} \enspace \left\{ \begin{array}{rllll}
      \LL u &=& f &\text{ in $\Omega$} & \text{(PDE)} \\
      \RR u &=& g &\text{ auf $\bOmega$} & \text{(Randbedingung)}
    \end{array} \right.
  \]
  wobei $\LL$ der lineare Differentialoperator
  \[
    \LL u = - \sum_{i,j=1}^n a_{ij}(x) \tfrac{\partial^2 u}{\partial x_i \partial x_j} + \sum_{i=1}^n b_i(x) \tfrac{\partial u}{\partial x_i} + c(x) u
  \]
  mit Fktn $a_{ij}, b_i, c, f : \Omega \to \R$, $g : \bOmega \to \R$ ist, sodass $A(x) \coloneqq (a_{ij}(x))$ symmetrisch ist.
  Als Randbedingung (RB) verlangen wir:
  \[ \begin{array}{rllll}
    \text{\emph{Dirichlet-RB}:} & u &=& g & \text{auf $\bOmega$,} \\
    \text{\emph{Neumann-RB}:} & (A(x) \nabla u) \cdot \nu &=& g & \text{auf $\bOmega$ oder} \\
    \text{\emph{Robin-RB}:} & (A(x) \nabla u) \cdot \nu + \delta u &=& g & \text{auf $\bOmega$.}
  \end{array} \]
\end{prob}

\begin{bemn}
  \begin{itemize}
    \item Man kann auch auf verschiedenen Teilstücken des Randes verschiedene Bedingungen stellen.
    \item Falls die Funktionen $a_{ij}$ differenzierbar sind, so kann $\LL$ in \emph{Divergenzform} geschrieben werden:
    \begin{align*}
      %\LL u & = - \sum_{i,j=1}^n a_{ij}(x) \tfrac{\partial^2 u}{\partial x_i \partial x_j} + \sum_{i=1}^n b_i(x) \tfrac{\partial u}{\partial x_i} + c(x) u  \\
      %& = - \sum_{i,j=1}^n \left( \tfrac{\partial}{\partial x_j} \left( a_{ij}(x) \tfrac{\partial u}{\partial x_i} \right) - \left( \tfrac{\partial}{\partial x_j} a_{ij}(x) \right) \tfrac{\partial u}{\partial x_i} \right) + \sum_{i=1}^n b_i(x) \tfrac{\partial u}{\partial x_i} + c(x) u \\
      \LL u & = - \!\!\! \sum_{i,j=1}^n \tfrac{\partial}{\partial x_j} \left( a_{ij}(x) \tfrac{\partial u}{\partial x_i} \right) \!+\! \sum_{i=1}^n \underbrace{\left((\sum_{j=1}^n \tfrac{\partial}{\partial x_j} a_{ij}(x) ) \!+\! b_i(x)\right)}_{\tilde{b}(x) \coloneqq} \tfrac{\partial u}{\partial x_i} \!+\! c(x) u \\
      & = - \dive(A(x) \nabla u) + \tilde{b}(x) \cdot \nabla u + c(x) u
    \end{align*}
  \end{itemize}
\end{bemn}

\begin{voraussetzung}
  Wir nehmen im Folgenden an:
  \begin{itemize}
    \item $\LL$ ist \emph{gleichmäßig elliptisch}, \dh{}
    \[ \ex{\lambda_0 > 0} \fa{\xi \in \R^n} \fa{x \in \Omega} \xi^T A(x) \xi \geq \lambda_0 \norm{\xi}^2. \]
    Dabei heißt $\lambda_0$ \textit{Elliptizitätskonstante}.
    \item $a_{ij}, b_i, c, f \in \Cont(\cOmega)$, $g \in \Cont(\bOmega)$
  \end{itemize}
\end{voraussetzung}

\begin{bem}
  $\LL$ ist elliptisch auf $\Omega$ $\coloniff$ $A(x) > 0$ (spd) für alle $x \in \Omega$
\end{bem}

\begin{defn}
  Eine Fkt $u \in \Cont^2(\Omega) \cap \Cont(\cOmega)$ heißt \emph{klassische Lsg} vom (RWP) mit $\RR u \coloneqq u$, wenn die beiden Gleichungen in (RWP) in jedem Punkt von $\Omega$ bzw. des Randes $\bOmega$ erfüllt sind.
\end{defn}

% 2.1
\begin{satz}[\emph{Maximumprinzip}]
  Sei $\Omega \subset \R^n$ offen, zshgd u. beschränkt.
  Sei $u \in \Cont^2(\Omega) \cap \Cont(\cOmega)$ eine Lösung vom (RWP), $f \leq 0$ in $\Omega$ und $c \equiv 0$. \\
  Dann nimmt $u$ sein Maximum auf dem Rand $\bOmega$ an, \dh{}
  \[ \sup_{x \in \cOmega} u(x) = \sup_{x \in \bOmega} u(x) = \sup_{x \in \bOmega} g(x). \]
\end{satz}

% Vorlesung vom 20.10.2015

% 2.2
\begin{kor}
  Sei $c \geq 0$ und $f \leq 0$.
  Dann gilt
  $\sup_{x \in \cOmega} u(x) \leq \max \{ \sup_{x \in \bOmega} u(x), 0 \}$.
\end{kor}

% 2.3
\begin{kor}[\emph{Vergleichsprinzip}]
  Für $u_1, u_2 \in \Cont^2(\Omega) \cap \Cont(\cOmega)$ und $c \geq 0$ gelte $\LL u_1 \leq \LL u_2$ in $\Omega$ und $u_1 \leq u_2$ auf $\bOmega$.
  Dann gilt $u_1 \leq u_2$ auf $\cOmega$.
\end{kor}

% 2.4
\begin{kor}[Eindeutigkeit]
  Sei $c \geq 0$. Dann hat (RWP) höchstens eine Lösung $u \in \Cont^2(\Omega) \cap \Cont(\cOmega)$.
\end{kor}

\iffalse
\begin{bsp}
  Betrachte $-u'' - \lambda u = 0$ in $\Omega = \ointerval{0}{1}$ mit $\lambda > 0$, $u(0) = u(1) = 0$.
  \begin{itemize}
    \item $u \equiv 0$ ist eine Lösung
    \item Für $\lambda = k^2 \pi^2$ ist $u(x) = a \sin(k \pi x)$ auch eine Lösung
  \end{itemize}
\end{bsp}
\fi

% 2.5
\begin{satz}
  Sei $\Omega$ ein beschr. Lipschitz-Gebiet, $a_{ij}, b_i, c \in \Cont(\cOmega)$, $c \geq 0$, $\LL$~glm. elliptisch, $f \in \Cont^{0,\alpha}(\cOmega)$ für ein $\alpha \in \ointerval{0}{1}$ und $g \in \Cont(\bOmega)$. \\
  Dann besitzt (RWP) genau eine Lsg $u \in \Cont^2(\Omega) \cap \Cont(\cOmega)$.
\end{satz}

% Beweis siehe J.H.Michael, "A general theory for linear elliptic partial differential equations", 1977

\begin{acht}
  Es muss aber nicht $u \in \Cont^2(\cOmega)$ gelten!
\end{acht}

\iffalse
\begin{bspe}
  \begin{itemize}
    \item $- \Laplace u = 0$ in $\ointerval{0}{1} \times \ointerval{0}{1}$, $u(0, x_2) = 0$, $u(1, x_2) = x_2$, $u(x_1, 0) = 0$, $u(x_1, 1) = x_1$ für $x_1, x_2 \in \cinterval{0}{1}$.
    Lösung: $u(x_1, x_2) = x_1 x_2$
    \item $- \Laplace u = 0$ in $\Omega = \ointerval{0}{1} \times \ointerval{0}{1}$,
    $u(x_1, x_2) = x_1^2$.
    Nach Satz 2.5 existiert eine Lösung $u \in \Cont^2(\Omega) \cap \Cont(\cOmega)$ aber $u \not\in \Cont^2(\cOmega)$, denn
    \[ \tfrac{\partial^2 u}{\partial x_1^2} + \tfrac{\partial^2 u}{\partial x_2^2} = 2 \neq 0 \]
    bei $x = (1, 1)$, auf $\bOmega$.
  \end{itemize}
\end{bspe}
\fi

% 3. Differenzenverfahren
\section{Differenzenverfahren}

% 3.1. Differenzenverfahren für die Poisson-Gleichung in $\Omega = \ointerval{0}{1}$

\begin{problem}[\emph{Poisson-Problem}]
  \[
    \text{\probl{(RWP\tss{1})}}\enspace
    \left\{ \begin{array}{rl}
      - \Laplace u = f &\text{ in $\Omega = \ointerval{0}{1}$} \\
      u(0) = g_0, u(1) = g_1 &\text{ auf $\bOmega$}
    \end{array} \right.
  \]
\end{problem}

\begin{verf}[\emph{DV}]
  Wir führen folgende Schritte durch:
  \begin{enumerate}
    \item Diskretisierung: Wähle $n \in \N$, setze $h \coloneqq \tfrac{1}{n}$ und
    \begin{align*}
      \Omega_h &\coloneqq \Set{x_i \coloneqq ih}{i = 1, \ldots, n-1}
      \tag{innere Gitterpunkte} \\
      \bOmega_h &\coloneqq \{ x_0 = 0, x_n = 1 \}
      \tag{Randpunkte}
    \end{align*}
    \item Approx. der Ableitungen durch Differenzenquotienten (DQ)
    \begin{align*}
      u'(x_i) &\approx \tfrac{1}{h} \left(u(x_i + h) - u(x_i)\right)
      \tag{\emph{Vorwärts-DQ}} \\
      u'(x_i) &\approx \tfrac{1}{h} \left(u(x_i) - u(x_i - h)\right)
      \tag{\emph{Rückwärts-DQ}} \\
      u'(x_i) &\approx \tfrac{1}{2h} \left(u(x_i + h) - u(x_i - h)\right)
      \tag{\emph{zentraler DQ}}
    \end{align*}
    Für die zweite Ableitung ergibt sich
    \begin{align*}
      u''(x_i) &= (u'(x_i))' \approx \tfrac{1}{h} \left(u'(x_i + h) - u'(x_i)\right) \approx \\
      &\approx \tfrac{1}{h} \cdot \left(\tfrac{1}{h} \left( u(x_i + h) - u(x_i) \right) - \tfrac{1}{h} \left( u(x_i) - u(x_i - h) \right)\right) \\
      &= \tfrac{1}{h^2} \left( u(x_i + h) - 2 \cdot u(x_i) + u(x_i - h) \right) =: \Laplace_h u
    \end{align*}
    Dabei heißt $\Laplace_h$ der diskrete eindim. Laplace-Operator. \\
    Das diskretisierte Randwertproblem ist nun
    % TODO: Bezeichnung davon?
    \[
      \text{\probl{(RWP\tss{1})\tss{h}}} \enspace
      \left\{ \begin{array}{rl}
        - \Laplace_h u_h = f &\text{ in $\Omega_h$,} \\
        u_h(0) = g_0, u_h(1) = g_1 &\text{ auf $\bOmega_h$.}
      \end{array} \right.
    \]
    \item Aufstellen des linearen Gleichungssystems
    \begin{align*}
      \tfrac{1}{h^2} \left( 2 u_h(x_1) - u_h(x_2) \right) &= f(x_1) + \tfrac{g_0}{h^2}
      \tag{$i\!=\!1$} \\
      \tfrac{1}{h^2} \left( -u_h(x_{i-1}) \!+\! 2 u_h(x_i) \!-\! u_h(x_{i+1}) \right) &= f(x_i)
      \tag{$i=2, \nldots, n-2$} \\
      \tfrac{1}{h^2} \left( -u_h(x_{n-2}) + 2 u_h(x_{n-1}) \right) &= f(x_{n-1}) + \tfrac{g_1}{h^2}
      \tag{$i\!=\!n{-}1$}
    \end{align*}
    
    Als lineares Gleichungssystem: $- \tilde{\Laplace}_h \tilde{u}_h = \tilde{f}_h$ mit
    \[
      - \tilde{\Laplace}_h = \frac{1}{h^2} \begin{pmatrix}
        2 & -1 & &&& 0 \\
        -1 & 2 & -1 &&& \\
        & -1 & 2 & -1 && \\
        && \ddots & \ddots & \ddots \\
        &&& -1 & 2 & -1 \\
        0 &&&& -1 & 2
      \end{pmatrix} \in \R^{(n-1) \times (n-1)},
    \]
    \[
      \tilde{u}_h = \begin{pmatrix}
        u_h(x_1) \\ \vdots \\ u_h(x_{n-1})
      \end{pmatrix}, \quad
      \tilde{f}_h = \begin{pmatrix}
        f(x_1) + \tfrac{g_0}{h^2} \\
        f(x_2) \\
        \vdots \\
        f(x_{n-2}) \\
        f(x_{n-1}) + \tfrac{g_1}{h^2}
      \end{pmatrix}
    \]
  \end{enumerate}
\end{verf}

% Vorlesung vom 26.10.2015

% Konvergenz, Konsistenz, Stabilität
\subsection{Konvergenz, Konsistenz und Stabilität des DV}

\begin{ziel}
  Herausfinden, was die Lösung~$u_h$ von (RWP)\tss{h} (die man durch Lösen von (LGS) erhält) mit der Lösung~$u$ zum ursprünglichen Problem (RWP) zu tun hat.
  Ist etwa~$u_h$ die Einschränkung von~$u$, oder zumindest annäherungsweise?
  Wenn ja, wie klein muss man~$h$ wählen, damit die Approximation gut wird?
  \begin{align*}
    \text{\probl{(RWP)}} \quad
    & \left\{ \begin{array}{rl}
      - \LL u = f &\text{ in $\Omega$,} \\
      u = g &\text{ auf $\bOmega$}
    \end{array} \right. \\
    \text{\probl{(RWP)\tss{h}}} \quad
    & \left\{ \begin{array}{rl}
      - \LL_h u = f_h &\text{ in $\Omega_h$,} \\
      u_h = g_h &\text{ auf $\bOmega_h$}
    \end{array} \right. \\
    \text{\probl{(LGS)}} \quad
    & \qquad \tilde{\LL}_h \tilde{u}_h = \tilde{f}_h
  \end{align*}
\end{ziel}

\begin{nota}
  %Sei $U_h$ der Raum aller Funktionen mit Werten in $\R$, die auf dem Gitter $\Omega_h$ definiert sind und sei  die Einschränkung stetiger Funktionen auf $\Omega_h$. \\
  $U_h \coloneqq \{ \Omega_h \to \R \}$, \quad
  $R_h : \Cont(\cOmega) \to U_h, \enspace u \mapsto u|_{\Omega_h}$
\end{nota}

\begin{defn}
  Das Differenzenverfahren (RWP)\tss{h} heißt
  \begin{itemize}
    \item \emph{konvergent} von der \textit{Ordnung}~$p$, falls $C > 0$, $h_0 > 0$ existieren, sodass für die Lsg~$u$ von (RWP) und die Lsg~$u_h$ von (RWP)\tss{h} gilt:
    \[
      \norm{u_h - R_h u}_h \leq C h^p \quad
      \text{für alle $0 < h \leq h_0$,}
    \]
    wobei~$\norm{\blank}_h$ die Maximums-Norm ist, \dh{} $\norm{u_h}_h \coloneqq \max_{x \in \Omega_h} \abs{u_h(x)}$.
    \item \emph{konsistent} von der \textit{Ordnung}~$p$, falls
    \[
      \norm{\LL_h R_h u - R_h \LL u}_h \leq c h^p \norm{u}_{\Cont^{p+2}(\cOmega)} \quad
      \forall u \in \Cont^{p+2}(\cOmega).
    \]
    % Falls u eine Lösung von (RWP) ist, so gilt
    %\[ \LL_h R_h u - R_h \LL u = \LL_h R_h u - R_h f = \LL_h u - f_h \]
    \item \emph{stabil}, falls $\tilde{\LL}_h$ invertierbar ist und ein $h_0 > 0$ existiert mit
    \[
      \sup_{0 < h \leq h_0} \norm{\tilde{\LL}_h^{-1}}_h < \infty, \quad
      \text{wobei} \enspace
      \norm{\tilde{\LL}_h^{-1}}_h \coloneqq \sup_{f \neq 0} \tfrac{\norm{\tilde{\LL}^{-1}_h f}_h}{\norm{f}_h}.
    \]
  \end{itemize}
\end{defn}

\begin{bem}
  Die ind. Matrixnorm ist $\norm{\tilde{\LL}_h^{-1}}_h = \norm{\tilde{\LL}_h^{-1}}_\infty = \max_{1 \leq i \leq n} \sum_{j=1}^n \abs{l_{ij}}$.
\end{bem}

% Was ist das Residuum??? Was heißt Konditionierung eines Problems?

% 3.1
\begin{satz}
  Ist das DV (RWP)\tss{h} konsistent und stabil, so auch konvergent.
  Genauer gilt: Ist (RWP)\tss{h} stabil und konsistent von der Ordnung~$p$ und $u \in \Cont^{p+2}(\cOmega)$, dann ist (RWP)\tss{h} konvergent von der Ordnung~$p$.
\end{satz}

% Was ist Spalten-, Spektrale und Zeilensummennorm?
% Spa-Spe-Zei

\begin{proof}
  Setze $w_h \coloneqq u_h - R_h u$.
  Für $x \in \bOmega_h$ gilt dann $w_h(x) = 0$ und für $x \in \Omega_h$ gilt
  \begin{align*}
    \tilde{\LL}_h w_h(x) &= \LL_h w_h(x) = \LL_h u_h(x) - \LL_h R_h u(x) \\
    &= f_h(x) - \LL_h R_h u(x) = R_h f(x) - \LL_h R_h u(x) \\
    &= R_h \LL u(x) - \LL_h R_h u(x)
  \end{align*}
  Somit gilt $w_h = \tilde{\LL}_h^{-1} \left( R_h \LL u - \LL_h R_h u \right)$ in $\Omega_h$, also
  \begin{align*}
    \norm{w_h}_h &= \norm{\tilde{\LL}_h^{-1} \left( R_h \LL u - \LL_h R_h u \right)}
    \leq \norm{\tilde{\LL}_h^{-1}}_h \cdot \norm{R_h \LL u - \LL_h R_h u}_h \\
    & \leq c_1 \cdot c_2 \cdot h^p \cdot \norm{u}_{\Cont^{p+2}(\cOmega)}
    \leq C h^p \qquad
    \text{für $0 < h \leq h_0$.} \qedhere
  \end{align*}
\end{proof}

% 3.2
\begin{lem}
  Das DV (RWP\tss{1})\tss{h} ist konsistent von der Ordnung~2.
  Es gilt
  \[
    \norm{\Laplace_h R_h u - R_h \Laplace u}_h \leq \tfrac{1}{12} \norm{u}_{\Cont^4(\cOmega)} h^2 \quad
    \forall u \in \Cont^4(\cOmega).
  \]
\end{lem}

% Beweis ähnlich wie auf ÜB2 mit Taylorn

\begin{bem}
  Um zu zeigen, dass (RWP\tss{1})\tss{h} konvergent ist, müssen wir noch zeigen, dass $\tilde{L}_h = - \tilde{\Laplace}_h$ invertierbar ist und dass $\sup_{0 < h \leq h_0} \norm{\tilde{\Laplace}_h} < \infty$.
\end{bem}

\begin{defn}
  Eine Matrix $A = (a_{ij}) \in \R^{n \times n}$ heißt \emph{M-Matrix}, falls
  \begin{enumerate}[label=\alph*),leftmargin=1.6em]
    \miniitem{0.43 \linewidth}{$a_{ii} > 0$ für $i = 1, \ldots, n$,}
    \miniitem{0.53 \linewidth}{$a_{ij} \leq 0$ für $i \neq j$, $i, j = 1, \ldots, n$,}
    \miniitem{0.43 \linewidth}{$A$ invertierbar ist und}
    \miniitem{0.53 \linewidth}{für $A^{-1} =: B = (b_{ij})$ gilt $b_{ij} \geq 0$.}
  \end{enumerate}
\end{defn}

% 4.3.9 im Hackbusch
\begin{lem}
  Erfülle $A \in \R^{n \times n}$ die Bedingungen a) und b).
  Zerlege $A = D + L + R$ in eine Diagonalmatrix und strikte untere/obere Dreiecksmatrizen.
  Dann ist $A$ genau dann eine M-Matrix wenn
  \[ \rho(D^{-1}(L + R)) < 1. \]
\end{lem}

\begin{bem}
  Es gilt folgende Monotonie-Eigenschaft für M-Matrizen:
  \[
    x \leq y \implies
    A^{-1} x \leq A^{-1} y.
  \]
  % je komponentenweise
\end{bem}

\begin{defn}
  Eine Matrix $A \in \R^{n \times n}$ heißt \emph{reduzibel} (oder \textit{zerlegbar}), wenn es eine Permutationsmatrix $P \in \R^{n \times n}$ gibt, sodass
  \[
    PAP^T = \begin{psmallmatrix}
      A_{11} & A_{12} \\
      0 & A_{22}
    \end{psmallmatrix} \quad
    \text{mit $A_{11} \in R^{k \times k}$, $0 < k < n$.}
  \]
  % Ist $A$ nicht reduzibel, so heißt $A$ irreduzibel
\end{defn}

% Lem 4.3.4 im Hackbusch
\begin{lem}[Gerschgorin]
  Alle EWe einer Matrix $A = (a_{ij}) \in \C^{n \times n}$ liegen in der Menge
  \[
    \bigcup_{i=1}^n \clos{B_{r_i}(a_{ii})}
    \quad \text{mit} \quad
    r_i \coloneqq \sum_{j=1}^n \abs{a_{ij}}.
  \]
  Falls $A$ irreduzibel ist, so liegen sie sogar in
  \[
    \left( \bigcup_{i=1}^n B_{r_i}(a_{ii}) \right) \cup
    \left( \bigcap_{i=1}^n \partial B_{r_i}(a_{ii}) \right)
  \]
\end{lem}

\begin{defn}
  Sei $A = (a_{ij}) \in \R^{n \times n}$ eine Matrix.
  \begin{itemize}
    \item $A$ heißt \emph{(schwach) diagonaldominant}, falls für $i = 1, \ldots, n$ gilt:
    \[
      \sum_{\substack{j=1\\j \neq i}}^n \abs{a_{ij}}
      \quad
      %\underset{(\leq)}{<}
      {< \atop (\leq)}
      \quad
      \abs{a_{ii}}.
      \tag{$\ddagger$}
    \]
    % Ausgelassen: Beispiel einer reduziblen Matrix
    % Vorlesung vom 27.10.2015
    \item $A$ heißt \emph{irreduzibel diagonaldominant}, falls $A$ irreduzibel und schwach diagonaldominant ist und für mind. ein $i \in \{ 1, \ldots, n \}$ die strikte Ungleichung in ($\ddagger$) gilt.
  \end{itemize}
\end{defn}

% 3.3
\begin{lem}
  Sei $A = (a_{ij}) \in \R^{n \times n}$ eine Matrix mit $a_{ii} > 0$, $i = 1, \ldots, n$ und $a_{ij} \leq 0$, $i, j = 1, \ldots, n$, $i \neq j$, die diagonaldominant oder irreduzibel diagonaldominant ist.
  Dann ist $A$ eine M-Matrix.
\end{lem}

\begin{bem}
  $- \tilde{\Laplace}_h$ ist irreduzibel diagonaldominant, also eine M-Matrix.
\end{bem}

% 4.3.11 im Hackbusch
\begin{lem}
  Sei $A$ eine irreduzible M-Matrix. Dann gilt $A^{-1} > 0$.
\end{lem}

% Noch zu zeigen: $\sup_{0 < h \leq h_0} \norm{\tilde{\Laplace}_h^{-1}} < \infty$

% 3.4
\begin{lem}
  Sei $A \in \R^{n \times n}$ eine M-Matrix und es existiere ein Vektor $v$, sodass $(Av)_j \geq 1$, $j = 1, \ldots, n$.
  Dann gilt $\norm{A^{-1}}_\infty \leq \norm{v}_\infty$.
\end{lem}

% 3.5
\begin{lem}
  $\norm{\tilde{\Laplace}_h^{-1}}_\infty \leq \tfrac{1}{8}$
\end{lem}

% Beweis folgt aus dem letzten Lemma mit $v = (v_1, \ldots, v_n)^T$ mit $v_i \coloneqq h^2/2 i (n-i)$

% 3.6
\begin{satz}
  Das DV (RWP\tss{1})\tss{h} ist konvergent von der Ordnung 2, falls die Lösung von (RWP\tss{1}) zu $\Cont^4(\cinterval{0}{1})$ gehört.
  Es gilt die Abschätzung
  \[ \norm{u_h - R_h u}_\infty \leq \tfrac{h^2}{96} \norm{u}_{\Cont^4(\cinterval{0}{1})}. \]
\end{satz}

% 3.2. Differenzenverfahren für die Poisson-Gleichung in $\Omega = \ointerval{0}{1} \times \ointerval{0}{1}$
\subsection{Differenzenverfahren in $\ointerval{0}{1} \times \ointerval{0}{1} \subset \R^2$}

\begin{problem}
  Wir betrachten nun
  \[
    \text{\probl{(RWP\tss{2})}} \quad
    \left\{ \begin{array}{rlll}
      - \Laplace u &=& f &\text{ in $\Omega = \ointerval{0}{1} \times \ointerval{0}{1}$} \\
      u &=& g &\text{ auf $\bOmega$}
    \end{array} \right.
  \]
\end{problem}

\begin{verf}
  \begin{enumerate}
    \item Diskretisierung: Setze $h \coloneqq \tfrac{1}{n}$, $n \in \N$ und
    \begin{align*}
      \Omega_h & \coloneqq \Set{(x, y) \in \Omega}{x = ih, y = jh, i,j = 1, \ldots, {n-1}} \\
      \bOmega_h & \coloneqq \Set{(x, y) \in \bOmega}{x = ih, y = jh, i,j = 1, \ldots, {n-1}}
    \end{align*}
    \item Approximation der Ableitungen
    \begin{align*}
    - & \Laplace u (x, y)
    = - \tfrac{\partial^2 u}{\partial x^2} (x,y) - \tfrac{\partial^2 u}{\partial y^2} (x, y) \\
    &\approx - \tfrac{u(x + h, y) - 2 u(x, y) + u(x-h, y)}{h^2} - \tfrac{u(x, y+h) - 2 u(x,y) + u(x, y-h)}{h^2} \\
    &= - \tfrac{u(x+h,y) + u(x-h,y) - 4 u(x, y) + u(x, y+h) + u(x, y-h)}{h^2} =: - \Laplace_h u
    \end{align*}
    Dabei hat der diskrete Laplace-Operator $\Laplace_h$ die Form eines \textit{Differenzensterns}.
    Gesucht ist die Lsg $u_h : \Omega_h \cup \bOmega_h \to \R$ von
    \[
      \text{\probl{(RWP\tss{2})\tss{h}}} \quad
      \left\{ \begin{array}{rlll}
        - \Laplace_h u_h &=& f_h &\text{ in $\Omega_h$} \\
        u_h &=& g &\text{ auf $\bOmega_h$.}
      \end{array} \right.
    \]
    \item Aufstellen des linearen Gleichungssystems $- \tilde{\Laplace}_h \tilde{u}_h = \tilde{f}_h$:
    % wir verwenden hier die zeilenweise Nummerierung
    \[
      \tilde{u}_h = \begin{pmatrix}
        u_{11} \\
        u_{12} \\
        \vdots \\
        u_{n-1,n-2} \\
        u_{n-1,n-1}
      \end{pmatrix} \in \R^{(n-1)^2}, \quad
      \tilde{f}_h = \ldots \in \R^{(n-1)^2},
    \]
    \begin{align*}
      - \tilde{\Laplace}_h = \frac{1}{h^2} & \begin{pmatrix}
        A & -I & && 0 \\
        -I & A & -I && \\
        & \ddots & \ddots & \ddots \\
        && -I & A & -I \\
        0 &&& -I & A
      \end{pmatrix} \in \R^{(n-1)^2 \times (n-1)^2}, \\
      A = & \begin{pmatrix}
        4 & -1 & && 0 \\
        -1 & 4 & -1 && \\
        & \ddots & \ddots & \ddots \\
        && -1 & 4 & -1 \\
        0 &&& -1 & 4
      \end{pmatrix} \in \R^{n-1 \times n-1}
    \end{align*}
  \end{enumerate}
\end{verf}

% Vorlesung vom 2.11.2015

% 3.7
\begin{lem}
  Das DV (RWP\tss{2})\tss{h} ist konsistent von der Ordnung 2.
  Es gilt
  \[ \norm{\Laplace_h R_h u - R_h \Laplace u}_h \leq \tfrac{1}{6} \norm{u}_{\Cont^r(\cOmega)} h^2. \]
\end{lem}

% 3.8
\begin{lem}
  Das DV (RWP\tss{2})\tss{h} ist stabil.
  Es gilt $\norm{\tilde{D}_h^{-1}}_\infty \leq \nicefrac{1}{8}$.
\end{lem}

% Begründung: $-\tilde{\Laplace}_h$ ist eine M-Matrix, da schwach diagonaldominant und irreduzibel

% 3.9
\begin{satz}
  Das DV (RWP\tss{2})\tss{h} ist konvergent von der Ordnung 2, falls die Lösung von (RWP\tss{2}) zu $\Cont^4(\cOmega)$ gehört.
  Es gilt
  \[ \norm{u_h - R_h u}_h \leq \nicefrac{1}{48} \norm{u} \]
\end{satz}

\begin{bem}
  Ein \textit{9-Punkte-Stern} bezieht weitere Gitterpunkte zur Approximation des Differentialoperators ein und erhöht die Konvergenzordnung auf~$4$:
  % Dies geht mit dem 9-Punkte-Stern
  %             1
  %             |
  %            -16
  %             |
  % 1 -- -16 -- 60 -- -16 -- 1
  %             |
  %            -16
  %             |
  %             1
  \begin{align*}
    - \Laplace_h^{(9)} & u(x, y) = \tfrac{1}{12 h^2} \left( u(x{-}2h, y) - 16 u(x{-}h, y) + 30 u(x, y) \right. \\
    & \left. - 16 u(x{+}h, y) + u(x{+}2h, y) + u(x, y{-}2h) - 16 u(x, y{-}h) \right. \\
    & \left. + 30 u(x, y) - 16 u(x, y{+}h) + u(x, y{+}2h) \right) \approx - \Laplace u(x, y)
  \end{align*}
  % oder:
  % -1/3  -1/3  -1/3
  % -1/3   8/3  -1/3
  % -1/3  -1/3  -1/3
  % Die Erweiterung auf nichtrechteckige Gebiete ist trivial
\end{bem}

% 3.3. Diskretisierung in einem beschränkten Gebiet in R^2
\subsection{Differenzenverfahren in allg. Gebieten $\Omega \subset \R^2$}

\begin{situation}
  Sei $\Omega \subset \R^2$ beschränkt.
\end{situation}

\begin{defn}
  \begin{itemize}
    \item $\Omega_h \coloneqq \Set{x, y \in \Omega}{\nicefrac{x}{h}, \nicefrac{y}{h} \in \Z}$ heißen \emph{innere Gitterpkte}.
    \item Ein Punkt $z_R \in \bOmega$ heißt \emph{Randgitterpunkt} (notiert $z_R \in \bOmega_h$), falls es einen inneren Gitterpunkt $z \in \Omega_h$ gibt, sodass $z_R = r + \alpha h e_1$ oder $z_R = z + \alpha h e_2$ mit $\abs{\alpha} \leq 1$.
    Die Nachbarn $N(x, y)$ eines Punktes $(x, y)$ sind $(x + s_r h, y)$, $(x - s_l h, y)$, $(x, y + y_o h)$, $(x, y - s_u h) $, falls $s_r, s_l, s_o, s_u \in \ocinterval{0}{1}$ und die Verbindungsstrecken zu $(x, y)$ in $\Omega$ liegen.
    \item Ein Punkt $(x, y) \in \Omega_h$ heißt \emph{randnah}, falls $(x, y)$ die Nachbarn $(x - s_l h, y)$, $(x + s_r h, y)$, $(x, y - s_u h)$, $(x, y+ s_o h)$ hat mit mindestens einem $s_i < 1$.
    Ansonsten heißt $(x, y)$ \emph{randfern}.
  \end{itemize}
\end{defn}

\begin{center}
  \begin{tikzpicture}[scale=0.6]
    \draw[->] (-3,1.5) -- node [left] {$s_o$} (-3,2.5);
    \draw[->] (-3,1.5) -- node [left] {$s_u$} (-3,0);
    \draw[->] (-3,1.5) -- node [below] {$s_r$} (-1.5,1.5);
    \draw[->] (-3,1.5) -- node [below] {$s_l$} (-4.5,1.5);
    \draw [magenta,fill=magenta] (-3,1.5) circle (.06) node [above right] {$x$};
    \draw [blue,fill=blue] (-3,2.6) circle (.06);
    \draw [blue,fill=blue] (-1.4,1.5) circle (.06);
    \draw [green,fill=green] (-3,-0.1) circle (.06);
    \draw [green,fill=green] (-4.6,1.5) circle (.06);
    
    
    \draw (-0.5,0) -- (3.5,0);
    \draw (-0.5,1) -- (3.5,1);
    \draw (-0.5,2) -- (3.5,2);
    \draw (-0.5,3) -- (3.5,3);
    \draw (0,-0.5) -- (0,3.5);
    \draw (1,-0.5) -- (1,3.5);
    \draw (2,-0.5) -- (2,3.5);
    \draw (3,-0.5) -- (3,3.5);
    \draw (-0.5,2.5) .. controls (0.5,2.75) and (0,3.3) .. (2.75,3.3) .. controls (3.5,3.3) and (3.5,2) .. (3, 1.5) .. controls (2.5,1) and (2.5,1.75) .. (2,1) .. controls (1.5,0) and (1.5,0) .. (1.5,-0.5);
    \foreach \point in {(1,1), (2,2), (1,2), (0,0), (0,1)} {
      \draw [green,fill=green] \point circle (.06);
    }
    \foreach \point in {(0,2), (1,3), (2,3), (3,3), (3,2), (1,0)} {
      \draw [magenta,fill=magenta] \point circle (.06);
    }
    \foreach \point in {(0,2.7), (1,3.16), (2,3.28), (3,3.22), (3.22,3), (3.28,2), (3,1.5), (2,1), (1.55,0)} {
      \draw [blue,fill=blue] \point circle (.06);
    }
    
    \draw [blue,fill=blue] (4.5,3) circle (.1);
    \node at (5,3) [right] { Randgitterpunkt };
    \draw [magenta,fill=magenta] (4.5,2) circle (.1);
    \node at (5,2) [right] { randnaher Punkt };
    \draw [green,fill=green] (4.5,1) circle (.1);
    \node at (5,1) [right] { randferner Punkt };
  \end{tikzpicture}
\end{center}

% 3.3.1 Shortley-Weller-Diskretisierung

\begin{lem}[\emph{Dividierte Differenzen von Newton}]\mbox{}\\
  Für $u \in \Cont^3(\cinterval{x_l}{x_r})$, $x \in \ointerval{x_l}{x_r}$ gilt
  \[
    u''(x) = \underbrace{\frac{2}{x_r - x_l} \left( \frac{u(x_r) - u(x)}{x_r - x} - \frac{u(x) - u(x_l)}{x - x_l} \right)}_{\mathclap{= \frac{2}{x_r - x_l} \left( \tfrac{1}{x_r - x} u(x_r) + \tfrac{1}{x - x_l} u(x_l) \right) - \frac{2}{(x_r - x)(x - x_l)} u(x)}} + \O(x_r - x_l)
  \]
  % = & \frac{2}{x_r - x_l} \left( \tfrac{1}{x_r - x} u(x_r) + \tfrac{1}{x - x_l} u(x_l) \right) \\
  % & - \frac{2}{(x_r - x)(x - x_l)} u(x) + \O(x_r - x_l).
\end{lem}

\begin{verf}[\emph{Shortley-Weller-Diskretisierung}] \mbox{}\\
  Dadurch inspiriert approximieren wir den Laplace-Operator durch
  \begin{align*}
    \DO_h & u(x, y) = \frac{1}{h^2} \left( \frac{2 u(x - s_l h, y)}{s_l (s_r {+} s_l)} + \frac{2 u(x+s_r h, y)}{s_r (s_r {+} s_l)} \right. \\
    & \left. + \frac{2 u(x, y {-} s_u h)}{s_u (s_o {+} s_u)}  + \frac{2 u(x, y {+} s_o h)}{s_o (s_o {+} s_u)} - \left( \frac{2}{s_l s_r} + \frac{2}{s_o s_u} \right) u(x, y) \right)
  \end{align*}
  wobei
  $x_r - x = s_r h$, \enspace
  $x - x_l = s_l h$, \enspace
  $y_o - y = s_o h$, \enspace
  $y - y_u = s_u h$.
  % Vorlesung vom 3.11.2015
  Wir betrachten nun
  \begin{align*}
    \text{\probl{(RWP\tss{2})\tss{h}\tprime}} \quad
    & \left\{ \begin{array}{rrcl}
      - \DO_h u_h &=& f_h &\text{ in $\Omega_h$} \\
      u_h &=& g &\text{ auf $\bOmega_h$}
    \end{array} \right. \\
    \text{\probl{(LGS\tss{2})\tprime}} \quad
    & - \tilde{\DO}_h \tilde{u}_h = \tilde{f}_h \coloneqq f_h + g_h
  \end{align*}
  \[
    \text{mit} \quad
    g_h(x, y) = \nicefrac{1}{h^2} \qquad \sum_{\mathclap{(x_N, y_N) \in N(x, y) \cap \bOmega_h}} \qquad S_{x_N,y_N} g(x_N, y_N)
  \]
  
  wobei\vspace{-0.3cm}
  \begin{align*}
    S_{x_N,y_N} \coloneqq & \begin{cases}
      \nicefrac{2}{s_l (s_l + s_r)} & \text{falls $(x_N, y_N) = (x - s_l h, y)$,} \\
      \nicefrac{2}{s_r (s_l + s_r)} & \text{falls $(x_N, y_N) = (x + s_r h, y)$,} \\
      \nicefrac{2}{s_o (s_o + s_u)} & \text{falls $(x_N, y_N) = (x, y + s_o h)$,} \\
      \nicefrac{2}{s_u (s_o + s_u)} & \text{falls $(x_N, y_N) = (x, y - s_u h)$,} \\
    \end{cases}
  \end{align*}
  \begin{align*}
    - \tilde{\DO}_h = (d_{ij}) & \quad \text{mit} \quad
    d_{ii} = \nicefrac{1}{h^2} \left( \tfrac{2}{s_{il} s_{ir}} + \tfrac{2}{s_{iu} s_{io}} \right) \quad \text{und} \\
    d_{ij} = \nicefrac{1}{h^2} & \begin{cases}
      - \nicefrac{2}{s_{il} (s_{il} + s_{ir})} & \text{falls $j$ der linke Nachbar von $i$ ist,} \\
      - \nicefrac{2}{s_{ir} (s_{il} + s_{ir})} & \text{falls $j$ der rechte Nachbar von $i$ ist,} \\
      - \nicefrac{2}{s_{iu} (s_{iu} + s_{io})} & \text{falls $j$ der untere Nachbar von $i$ ist,} \\
      - \nicefrac{2}{s_{io} (s_{iu} + s_{io})} & \text{falls $j$ der obere Nachbar von $i$ ist.} \\
    \end{cases}
  \end{align*}
\end{verf}

% 3.10
\begin{lem}
  \begin{itemize}
    \item Die Matrix $- \tilde{\DO}_h$ ist eine M-Matrix.
    \item Sei $\Omega \subset \R^2$ beschränkt und gehöre zu dem Streifen $(x_0, x_0 + d) \times \R$ oder $\R \times (y_0, y_0 + d)$.
    Dann gilt $\norm{\tilde{D}_h^{-1}} \leq \nicefrac{d^2}{8}$.
  \end{itemize}
\end{lem}

% Beweis: W. Hackbusch, Thm. 4.8.4

\begin{bem}
  Das DV (RWP\tss{2})\tss{h}\tprime{} hat in den randnahen Punkten nur die Konsistenzordnung 1. Dennoch gilt:
  \iffalse
  Sei $u \in \Cont^4(\cOmega)$.
  Dann ist
  \begin{align*}
    u(x + s_r h, y) & = u(x, y) + s_r h u_x(x, y) + \tfrac{s_r^2 h^2}{2} u_{xx}(x,y) + \tfrac{s_r^3 h^3}{6} u_{xxx}(x, y) \\
    & + \tfrac{s_r^4 h^4}{24} u_{xxxx}(\xi_1, y)
    \qquad \text{für ein $\xi_1 \in \ointerval{x}{x+s_r h}$,} \\
    u(x - s_l h, y) & = u(x, y) - s_l h u_x(x, y) + \tfrac{s_l^2 h^2}{2} u_{xx}(x, y) - \tfrac{s_l^3 h^3}{6} u_{xxx}(x, y) \\
    & + \tfrac{s_r^4 h^4}{24} u_{xxxx}(\xi_2, y)
    \qquad \text{für ein $\xi_2 \in \ointerval{x - s_l h}{x}$.}
  \end{align*}
  
  Es folgt
  \begin{align*}
    & \nicefrac{1}{h^2} \left( \tfrac{2}{s_l (s_l + s_r)} u(x - x_l h, y) + \tfrac{2}{s_r (s_r + s_l)} u(x+s_r h, y) - \tfrac{2}{s_r s_l} u(x, y) \right) = \\
    & u_{xx}(x, y) + \tfrac{1}{3} (s_r - s_l) h u_{xxx}(x, y) + \tfrac{1}{12} h^2 \left( \tfrac{s_r^3 u_{xxxx}(\xi_1, y)}{s_r + s_l} + \tfrac{s_l^3 u_{xxxx}(\xi_2, y)}{s_r + s_l} \right)
  \end{align*}
  % 0)
  \[ \nicefrac{1}{h^2} \left( \tfrac{2}{s_l (s_r + s_l)} + \tfrac{2}{s_r (s_l + s_r)} + \tfrac{2}{s_r s_l} \right) u(x, y) = 0 \]
  % 1)
  \[ \nicefrac{1}{h^2} \left( \tfrac{2 s_r h}{s_r (s_r + s_l)} + \tfrac{- 2 s_l h}{s_l (s_r + s_l)} \right) u_x(x,y) = 0 \]
  % 2)
  \[ \nicefrac{1}{h^2} \left( \tfrac{2 s_r^2 h^2}{2 s_r (s_r + s_l)} + \tfrac{2 s_l^2 s_r^2}{2 s_l (s_r + s_l)} \right) u_{xx}(x, y) = u_{xx}(x, y) \]
  % 3)
  \[ \nicefrac{1}{h^2} \left( \tfrac{2 s_r^3 h^3}{6 s_r (s_r + s_l)} + \tfrac{- 2 s_l^3 h^3}{6 s_l (s_r + s_l)} \right) u_{xxx}(x, y) = \nicefrac{1}{3} (s_r - s_l) h u_{xxx}(x, y) \]
  % 4) ...
  \[
    \norm{\DO_h R_h u - R_h \Laplace u}_h \leq
    \begin{cases}
      \nicefrac{1}{6} h^2 \norm{u}_{\Cont^4(\cOmega)} & \text{falls $s_r = s_l$, $s_o = s_u$}, \\
      \left( \tfrac{s_r^2 + s_l^2}{s (s_r + s_l)} + \tfrac{s_u^2 + s_o^2}{3 (s_u + s_o)} \right) h \norm{u}_{\Cont^3(\cOmega)} & \text{sonst}
    \end{cases}
  \]
  Somit: Konsistenzordnung = 1
  \fi
\end{bem}

% 3.11, 4.8.6 im Hackbusch
\begin{satz}
  Sei $\Omega \subset \R^2$ beschränkt.
  Dann ist das Verfahren (RWP\tss{2})\tss{h}\tprime{} konvergent von der Ordnung~2.
  Genauer gilt:
  Ist $\Omega$ eine Teilmenge des Streifens $\ointerval{x_0}{x_0 + d} \times \R$ oder $\R \times (y_0, y_0 + d)$, so ist
  \[ \norm{u_h - R_h u}_h \leq \left( \nicefrac{1}{3} h^3 + \nicefrac{d^2}{48} h^2 \right) \norm{u}_{\Cont^4(\cOmega)}. \]
\end{satz}

% Vorlesung vom 9.11.2015

% §3.3.2 Interpolation

Ein weiteres Verfahren beruht auf:

\begin{idee}
  Bestimme den Wert von $u$ bei randnahen Punkten $(x, y)$ durch lineare Interpolation:
  \begin{itemize}
    \item $u(x, y) \approx \frac{s_r}{s_r + s_l} u(x - s_l h, y) + \frac{s_l}{s_r + s_l} u(x+s_r h, y)$
    \item $u(x, y) \approx \frac{s_o}{s_u + s_o} u(x, y - s_u h) + \frac{s_u}{s_u + s_o} u(x, y + s_o h)$
  \end{itemize}
\end{idee}

Dies führt auf Gleichungen

\begin{align*}
  \text{\probl{(RWP\tss{2})\tss{h}\ensuremath{^{\prime\prime}}}} \quad
  & \left\{ \begin{array}{rlll}
    - \DO_h u &=& f_h &\text{ in $\Omega_h$} \\
    u_h &=& g &\text{ auf $\bOmega_h$}
  \end{array} \right. \\
  \text{\probl{(LGS\tss{2})\ensuremath{^{\prime\prime}}}} \quad
  & \qquad - \tilde{\DO}_h \tilde{u}_h = \tilde{f}_h
\end{align*}

\begin{lem}
  Dieses Verfahren besitzt Konsistenzordnung (und somit Konvergenzordnung) 2.
\end{lem}

\iffalse
Konsistenz: Mit Taylorn ...

\begin{itemize}
  \item \[ -s_r u_h(x - s_l h, y) + (s_r + s_l) u_h(x, y) - s_l u(x + s_r h, y) = 0 \]
  \item \[ -s_o u_h(x, y - s_u h) + (s_o + s_u) u_h(x, y) - s_u u(x, y + s_o h) = 0 \]
\end{itemize}
\fi

% §3.4. Allgemeine Differentialoperatoren
\subsection{Allgemeine Differentialoperatoren}

\begin{prob}
  Wir betrachten nun
  \[
    \text{\probl{(RWP\tss{3})}} \quad
    \left\{ \begin{array}{rlll}
      - \LL u &=& f &\text{ in $\Omega = \ointerval{0}{1} \times \ointerval{0}{1}$} \\
      u &=& g &\text{ auf $\bOmega$}
    \end{array} \right.
   \]
  mit
  \begin{align*}
    - \LL u&  = - (a_{11}(x, y) u_{xx} + 2 a_{12}(x, y) u_{xy} + a_{22}(x, y) u_{yy}) \\
    & + b_1(x, y) u_x + b_2(x, y) u_y + c(x, y) u
  \end{align*}
  wobei $c(x, y) \leq 0$, $\xi^T A(x, y) \xi \geq \lambda_0 \norm{\xi}^2$, $\lambda_0 > 0$ und
  \[
    A(x, y) = \begin{pmatrix}
      a_{11}(x,y) & a_{12}(x,y) \\
      a_{21}(x,y) & a_{22}(x,y)
    \end{pmatrix}
  \]
\end{prob}

\begin{verf}
  1. Diskretisierung: $h = \nicefrac{1}{n}$, $\Omega_h$, $\bOmega_h$ wie früher.

  2. Approximation:
  \begin{alignat*}{4}
    u_x(x, y) & \approx \tfrac{u(x + h, y) - u(x - h, y)}{2h}, \quad
    & u_y(x, y) & \approx \ldots \\
    u_{xx}(x, y) & \approx \tfrac{u(x + h, y) - 2 u(x, y) + u(x - h, y)}{h^2}, \quad
    & u_{yy}(x, y) & \approx \ldots
  \end{alignat*}
  Für die Approx. von $u_{xy}$ haben wir mehrere Möglichkeiten: \\ Wir könnten etwa den zentralen DQ in $x$- und $y$-Richrung verwenden und erhalten
  \begin{align*}
    & u_{xy}(x, y) \approx \tfrac{1}{2 h} \left( u_x (x, y+h) - u_x (x, y-h) \right) \\
    \approx \, & \tfrac{1}{4 h^2} \left( u(x{+}h, y{+}h) - u(x{+}h, y{-}h)  - u(x{-}h, y{+}h) + u(x{-}h, y{-}h) \right)
  \end{align*}
  Diese Annäherung hat allerdings den Nachteil, dass sie zu keiner M-Matrix führt.
  Stattdessen nehmen wir
  \iffalse
  \begin{align*}
    u_{xy}(x, y) & \approx \tfrac{1}{2 h^2} (- u(x-h, y) + 2 u(x,y) - u(x+h,y) \\
    & + u(x-h,y-h) - u(x, y+h) - u(x,y-h) \\
    & + u(x+h, y+h) ) \qquad \text{falls $a_{12}(x, y) \geq 0$,} \\
    u_{xy}(x, y) & \approx \tfrac{1}{2 h^2} ( u(x-h, y) - 2 u(x, y) + u(x+h, y) \\
    & + u(x, y+h) - u(x-h, y+h) - u(x+h, y-h) \\
    & + u(x,y-h) ) \qquad \text{falls $a_{12}(x, y) < 0$}
  \end{align*}
  \fi
  \begin{alignat*}{4}
    u_{xy}(x, y) \approx \qquad
    & \tfrac{1}{2 h^2} \begin{pmatrix}
      0 & -1 & 1 \\
      -1 & 2 & -1 \\
      1 & -1 & 0
    \end{pmatrix} \qquad
    && \tfrac{1}{2 h^2} \begin{pmatrix}
      -1 & 1 & 0 \\
      1 & -2 & 1 \\
      0 & 1 & -1
    \end{pmatrix} \\
    & \text{für } a_{12} \geq 0,
    && \text{für } a_{12} < 0.
  \end{alignat*}
  
  Wir fassen diese Approx. in folgendem \textit{7-Stern} zusammen:
  \begin{align*}
    - \LL_h u \coloneqq \enspace
    & \tfrac{1}{h^2} \begin{pmatrix}
      a_{12}^{-} & \abs{a_{12}} - a_{22} & - a_{12}^{+} \\
      \abs{a_{12}} - a_{11} & 2 (a_{11} + a_{22} - \abs{a_{12}}) & \abs{a_{12}} - a_{11} \\
      - a_{12}^{+} & \abs{a_{12}} - a_{22} & a_{12}^{-}
    \end{pmatrix} \\
    & + \tfrac{1}{2 h} \begin{pmatrix}
      & b_2 \\
      - b_1 & 0 & b_1 \\
      & - b_2
    \end{pmatrix}
    + \begin{pmatrix}
      \\ & c & \\ &
    \end{pmatrix}
  \end{align*}
  Dabei ist $a_{ij}^{+} \coloneqq \max(a_{ij}, 0)$ und $a_{ij}^{-} \coloneqq \min(a_{ij}, 0)$.
  \begin{align*}
    \text{\probl{(RWP\tss{3})\tss{h}}} \quad
    & \left\{ \begin{array}{rlll}
      - \LL_h u_h &=& f_h &\text{ in $\Omega_h$} \\
      u_h &=& g &\text{ auf $\bOmega_h$}
    \end{array} \right. \\
    \text{\probl{(LGS\tss{3})}} \quad
    & \qquad - \tilde{\LL}_h \tilde{u}_h = \tilde{f}_h
  \end{align*}
\end{verf}

% Vorlesung vom 10.11.2015

% 5.1.16 im Hackenbusch
\begin{satz}
  Sei $c \geq 0$ in $\Omega$ und $\LL$ gleichmäßig elliptisch. \\
  Falls $a_{ii} > \abs{a_{12}} + \tfrac{h}{2} \abs{b_i}$ für $i = 1, 2$ in $\Omega$ und $u \in \Cont^4(\cOmega)$, so ist das DV (RWP\tss{3})\tss{h} konvergent von der Ordnung 2.
\end{satz}

% 3.5 Differenzenverfahren für parabolische DGLn
\subsection{Differenzenverfahren für parabolische DGLn}

\begin{prob}
  \emph{Wärmeleitungsgleichung}
  \[
    \arraycolsep=2.5pt
    \text{\probl{(RWP\tss{4})}} \quad
    \left\{ \begin{array}{rcll}
      u_t(x,t) - \Laplace_x u(x, t) &=& f(x,t) &\text{in $\Omega = \ointerval{0}{1} \times \ointerval{0}{T}$} \\
      u(x,0) &=& g(x) & \text{für } x \in \ointerval{0}{1} \\
      u(0, t) &=& g_0(t) & \text{für } t \in \cinterval{0}{T} \\
      u(1, t) &=& g_1(t) & \text{für } t \in \cinterval{0}{T}
    \end{array} \right.
  \]
\end{prob}

\begin{verf}
  \begin{enumerate}
    \item Diskretisierung mit $n$ Raum- und $m$ Zeitschritten:
    \[
      x_i = ih, \enspace
      h = \nicefrac{1}{n}, \enspace
      t_k = k \tau, \enspace
      \tau = \nicefrac{T}{m}, \enspace
      u(x_i, t_k) \approx u_i^k
    \]
    \item Approximation der Ableitungen:
    \[ u_{xx}(x,t) \approx \tfrac{1}{h^2} \left( u(x-h, t) - 2u(x,t) + u(x+h, t) \right) =: \Laplace_h u(x,t) \]
    Wir wollen nun eine Lösung von
    \[ \left\{ \begin{array}{rll}
      \dot{u}_h(t) - \tilde{\Laplace}_h u_h(t) &=& f_h(t) \\
      u_h(0) &=& g_h
    \end{array} \right. \]
    für alle Zeiten $t$ mit
    \[
      u_h(t) = \begin{pmatrix}
        u_h(h, t) \\
        u_h(2h, t) \\
        \vdots \\
        u_h(1-h,t)
      \end{pmatrix}, \quad
      f_h(t) = \begin{pmatrix}
        f(h, t) + \tfrac{1}{h^2} g_0(t) \\
        f(2h, t) \\
        \vdots \\
        f(1-h,t) + \tfrac{1}{h^2} g_1(t)
      \end{pmatrix}
    \]
    berechnen.
    Dazu verwenden wir ein \textit{Einschrittverfahren}, wie das \textit{expl./impl. Gauß-Verfahren} oder das \textit{Crank-Nicolson-Verfahren}:
    \begin{align*}
      \text{\probl{(EEV)}} \enspace
      & \left\{ \begin{array}{R{130pt} c l}
        \tfrac{1}{\tau} (u_i^{k+1} - u_i^k) - \tilde{\Laplace}_h u_i^k &=& f_i^k \\
        u_i^0 &=& g_h
      \end{array} \right. \\
      %\tag{Expl. Euler-Verf}
      \text{\probl{(IEV)}} \enspace
      & \left\{ \begin{array}{R{130pt} c l}
        \tfrac{1}{\tau} (u_i^{k+1} - u_i^k) - \tilde{\Laplace}_h u_i^{k+1} &=& f_i^{k+1} \\
        u_i^0 &=& g_h
      \end{array} \right. \\
      %\tag{Impl. Euler-Verf}
      \text{\probl{(CNV)}} \enspace
      & \left\{ \begin{array}{R{130pt} c l}
        \tfrac{1}{\tau} (u_i^{k+1} - u_i^k) - \tfrac{1}{2} \tilde{\Laplace}_h (u_i^k + u_i^{k+1}) &=& f(x_i, t_k + \tfrac{\tau}{2}) \\
        u_i^0 &=& g_h
      \end{array} \right.
      %\tag{Crank-Nicolson-Verf}
    \end{align*}
  \end{enumerate}
\end{verf}

% 3.13
\begin{lem}
  Sei $f(x, \blank) \in \Cont^1(\cinterval{0}{T})$ für alle $x \in \cinterval{0}{1}$. \\
  Dann gilt für die Approximation von (RWP\tss{4}):
  \begin{itemize}
    \item Die Verfahren (EEV) und (IEV) besitzen einen Konsistenzfehler von $\O(h^2 + \tau)$, falls $u \in \Cont^4(\cinterval{0}{1} \times \cinterval{0}{T})$
    \item Das Verfahren (CNV) besitzt einen Konsistenzfehler von $\O(h^2 + \tau^2)$, falls $u \in \Cont^4(\cinterval{0}{1} \times \cinterval{0}{T})$.
  \end{itemize}
\end{lem}

% Vorlesung vom 16.11.2015

% Stabilität: $u_i^k \xra[k \to \infty]{} 0$

% 3.14
\begin{lem}
  Es gelte $2 \tau \leq h^2$ für (EEV).
  Die Verfahren (EEV), (IEV) und (CNV) sind stabil.
\end{lem}

\iffalse
\[
  (I - \sigma \tau \tilde{\Laplace}_h ) u_h(t_{k+1}) = (I + (1 - \sigma) \tau \tilde{\Laplace}_h ) u_h(t_k) + \tau f_h(t_k + \sigma \tau)
\]

Man erhält für $\sigma=0$ das EEV, für $\sigma=1$ das IEV und für $\sigma = \nicefrac{1}{2}$ das CNV.
Es folgt

\begin{align*}
  u_h(t_{k+1}) & = (I - \sigma \tau \tilde{\Laplace}_h)^{-1} (I + (1-\sigma) \tau \tilde{\Laplace}_h) u_h(t_k) + (I - \sigma \tau \tilde{\Laplace}_h)^{-1} f_h(t_k + \sigma \tau) = \ldots \\
  & \left( (I - \sigma \tau \tilde{\Laplace}_h)^{-1} (I + (1-\sigma) \tau \tilde{\Laplace}_h) \right)^{k} u_h(t_0) + (I - \sigma \tau \tilde{\Laplace}_h)^{-1} \sum_{j=0}^k \mu_j f_h(t_j + \sigma \tau)
\end{align*}

Ziel: $u_h(t_{k+1}) \xra[k \to \infty]{} 0$

Für Stabilität sollte $\abs{\lambda_j(M)} < 1$ gelten, wobei $M = (I - \sigma \tau \tilde{\Laplace}_h)^{-1} (I + (1-\sigma) \tau \tilde{\Laplace}_h)$.

Es gilt: $\lambda_j(M) = \frac{1 + (1 - \sigma) \tau \lambda_j(\tilde{\Laplace})}{1 - \sigma \tau \lambda_j(\tilde{\Laplace})}$

\begin{bem}
  Konsistenz + Stabilität $\implies$ Konvergenz
\end{bem}
\fi

\begin{samepage}

% §3.6 Differenzenverfahren für hyperbolische Gleichungen
\subsection{Differenzenverfahren für hyperbolische DGLn}

\begin{prob}
  \emph{Wellengleichung}
  \[
    \left\{ \begin{array}{rl}
      \partial_{tt} u - c^2 \partial_{xx} u = f(x,t) & \text{in $\Omega = \ointerval{0}{1} \times \cinterval{0}{T}$} \\
      u(0, t) = g_0(t), \enspace u(1, t) = g_1(t) & \text{für $t \in \cinterval{0}{T}$} \\
      u(x, 0) = q_0(x), \enspace u_t(x, 0) = q_1(x) & \text{für $x \in \ointerval{0}{1}$}
    \end{array} \right.
  \]
\end{prob}

\begin{verf}
  \begin{enumerate}
    \item Diskretisierung: $x_i = ih$, $h = \tfrac{1}{n}$, $t_k = k \tau$, $\tau = \tfrac{T}{m}$
    \item Approximation:
    \begin{align*}
      \partial_{xx} u(x_i, t_k) & \approx \tfrac{1}{h^2} \left( u(x_{i-1}, t_k) - 2 u(x_i, t_k) + u(x_{i+1}, t_k) \right) \\
      \partial_{tt} u(x_i, t_k) & \approx \tfrac{1}{\tau^2} \left( u(x_i, t_{k-1}) - 2 u(x_i, t_k) + u(x_i, t_{k+1}) \right) \\
      \partial_t u(x_i, 0) & \approx \tfrac{1}{2 \tau} ( u(x_i, t_1) - u(x_i, t_{-1}) )
    \end{align*}
    Wir erhalten das lineare Gleichungssystem
    \[
      \left\{ \begin{array}{r}
        \tfrac{1}{\tau^2} (u_i^{k-1} - 2 u_i^k + u_i^{k+1}) - \tfrac{c^2}{h^2} ( u_{i-1}^k - 2 u_i^k + u_{i+1}^k) = f_i^k \\
        \text{für $i = 1, \ldots, n-1$ und $k = 0, \ldots, m$.} \\
        u_0^k = g_0^k = g_0(t_k), \quad
        u_n^k = g_1^k = g_1(t_k), \\
        u_i^0 = q_{0,i} = q_0(x_i), \quad
        \tfrac{1}{2 \tau} ( u_i^1 - u_i^{-1} ) = q_{1,i} = q_1(x_i)
      \end{array} \right.
    \]
    % (ausgelassen: wie man jetzt ein LGS in Matrixschreibweise bekommt)
  \end{enumerate}
\end{verf}

\end{samepage}

\subsection{Fazit}

Das Differenzenverfahren \ldots
\begin{description}
  \item[{\Smiley[1.2]}] \ldots{} ist einfach in der Herleitung und Implementierung. 
  \item[{\Neutrey[1.2]}] \ldots{} besitzt eine gute Konvergenz (\zB{} Ordnung 2) bei genügend glatter Lösung. 
  \item[{\Sadey[1.2]}] \ldots{} ermöglicht Adaptivität bzw. unregelm. Gitter nur schwer. 
\end{description}

% Vorlesung vom 17.11.2015

%\begin{samepage}

\section{Schwache Lsgstheorie für elliptische DGLn}

\iffalse
\begin{bspe}
  \begin{itemize}
    \item $u''(x) = f$ in $\Omega = \ointerval{0}{1}$, $u(0) = g_0$, $u'(0) = g_1$
    \item $u_t(x, t) + c u_x(x, t) = 0$, $u(x, 0) = g(x)$, $g \in \Cont^1$. Lösung: $u(x, t) = g(x - c t)$
  \end{itemize}
\end{bspe}
\fi

% §4.1 Grundlagen aus der Funktionalanalysis

\begin{defn}
  Der \emph{$L^p$-Raum} ist für $1 \leq p < \infty$ definiert durch
  \[
    L^p(\Omega) \coloneqq \Set{v : \Omega \to \R}{\norm{v}_p < \infty}
    \quad \text{mit} \enspace
    \norm{v}_p \coloneqq \left( \IntOmega{\abs{v(x)}^p}{x} \right)^{\nicefrac{1}{p}},
  \]
  für $p = \infty$ durch
  \[
    L^\infty(\Omega) \coloneqq \Set{v : \Omega \to \R}{\norm{v}_\infty < \infty}
    \quad \text{mit} \enspace
    \norm{v}_\infty \coloneqq \esssup_{x \in \Omega} \abs{v(x)}.
  \]
\end{defn}

%\end{samepage}

\begin{bem}
  $(L^p(\Omega), \norm{\blank}_p)$ ist ein Banachraum, für $p = 2$ sogar ein Hilbertraum mit Skalarprodukt $\scp{u}{v}_{L^2(\Omega)} \coloneqq \AInt{\Omega}{u(x) v(x)}{x}$.
\end{bem}

\begin{satz}[\emph{Höldersche Ungleichung}]
  Sei $u \in L^p(\Omega)$ und $v \in L^q(\Omega)$ mit $1 \leq p, q, r \leq \infty$ und $\nicefrac{1}{p} + \nicefrac{1}{q} = \nicefrac{1}{r}$.
  Dann ist $uv \in L^r(\Omega)$ mit
  \[ \norm{uv}_r \leq \norm{u}_p \cdot \norm{v}_q. \]
\end{satz}

\begin{defn}
  Der Raum aller $k$-mal stetig differenzierbaren Funktionen auf~$\Omega$ mit \emph{kompaktem Träger} ist
  \[ \Cont_0^k(\Omega) \coloneqq \Set{\varphi \in \Cont^k(\Omega)}{\supp(\varphi) \coloneqq \clos{\Set{x \in \Omega}{\varphi(x) \neq 0}} \text{ ist kompakt}}. \]
\end{defn}

\begin{defn}
  $\Testfun(\Omega) \coloneqq \Cont^\infty_0 (\Omega)$ heißt Raum der \emph{Testfunktionen} in $\Omega$.
\end{defn}

\begin{lem}[Partielle Integration]
  Für $u, v \in \Cont^1(\cOmega)$ gilt
  \[ \AInt{\Omega}{v(x) \DO_i u(x)}{x} = \IntbOmega{v(x) u(x) \eta_i(x)}{x} - \AInt{\Omega}{\DO_i v(x) u(x)}{x}. \]
  % Falls $v(x) = 0$ auf $\bOmega$: $\IntOmega{v(x) \DO_i u(x)}{x} = - \IntOmega{\DO_i v(x) u(x)}{x}$
  Für $u \in \Cont^k(\cOmega)$, $\varphi \in \Cont_0^k(\Omega)$ und $\alpha = (\alpha_1, \ldots, \alpha_n)$, $\abs{\alpha} \leq k$ gilt
  \[ \IntOmega{\varphi(x) \DO^\alpha u(x)}{x} = (-1)^{\abs{\alpha}} \IntOmega{\DO^\alpha \varphi(x) u(x)}{x}. \]
\end{lem}

\begin{defn}
  $L_\loc^1(\Omega) \coloneqq \Set{v : \Omega \to \R}{v|_K \in L^1(K) \text{ für jedes kpkte $K \subset \Omega$}}$
  heißt Raum der \emph{lokal integrierbaren Funktionen}.
\end{defn}

\begin{defn}
  Sei $u \in L^1_\loc(\Omega)$ und $\alpha \in \N^n$.
  Eine Funktion $v \in L^1_\loc(\Omega)$ heißt \emph{schwache (partielle) Ableitung} von~$u$ (oder die Ableitung von $u$ im distributionellen Sinn) der Ordung~$\alpha$, wenn
  \[
    \IntOmega{\varphi(x) v(x)}{x} = (-1)^{\abs{\alpha}} \IntOmega{\DO^\alpha \varphi(x) u(x)}{x}
    \quad \text{für alle $\varphi \in \Testfun(\Omega)$}.
  \]
\end{defn}

\begin{bem}
  Ist eine Funktion im klassischen Sinne differenzierbar, so auch im schwachen mit derselben Ableitung.
\end{bem}

\begin{lem}[Fundamentallemma der Variationsrechung]
  Für $u \in L^1_\loc(\Omega)$:
  \[
    \IntOmega{u(x) \varphi(x)}{x} = 0 \enspace \forall \varphi \in \Testfun(\Omega)
    \enspace \implies \enspace
    u \equiv 0 \text{ (fast-überall).}
  \]
\end{lem}

\begin{kor}
  Die schwache Ableitung ist eindeutig bestimmt, \dh{} sind $v, w \in L^1_\loc(\Omega)$ schwache Ableitungen von $u$, so gilt $v \equiv w$ f.\,ü. in $\Omega$.
\end{kor}

\begin{bsp}
  Die schw. Abl. von $u(x) = \abs{x}$ ist $v(x) = \ind_{\ointerval{0}{\infty}} - \ind_{\ointerval{- \infty}{0}}$.
\end{bsp}

\begin{lem}
  \inlineitem{$\DO^\alpha (u + \lambda v) = \DO^\alpha u + \lambda \DO^\alpha v$} \quad
  \inlineitem{$\DO^{\alpha + \beta} u = \DO^\alpha (\DO^\beta u)$}
\end{lem}

% 4.1.2
\begin{defn}
  Der \emph{Sobolev-Raum} für $1 \leq p < \infty$ ist
  \begin{align*}
    W^{k,p}(\Omega) & \coloneqq \left\{ u \in L^p(\Omega) \;\middle|\; \begin{array}{l}
      \fa{\alpha \in \N^n \text{ mit } \abs{\alpha} \leq k} \\
      \exists \, \text{schwache Ableitung $\DO^\alpha u \in L^p(\Omega)$}
    \end{array} \right\} \\
    \norm{u}_{k,p} & \coloneqq \left( \sum_{\abs{\alpha} \leq k} \norm{\DO^\alpha u}_p^p \right)^{\nicefrac{1}{p}}.
  \end{align*}
\end{defn}

\begin{nota}
  $H^k(\Omega) \coloneqq W^{k,2}(\Omega)$
\end{nota}

% Bem: $W^{0,p}(\Omega) = L^p(\Omega)$

\begin{satz}
  $(W^{k,p}(\Omega), \norm{\blank}_{k,p})$ ist ein Banachraum.
\end{satz}

% Vorlesung vom 23.11.2015

% 4.2
\begin{bem}
  $H^k(\Omega)$ ist sogar ein Hilbertraum mit Skalarprodukt
  \[
    \scp{u}{v}_{H^k(\Omega)} \coloneqq \IntOmega{\sum_{\alpha \leq k} D^\alpha u D^\alpha v}{x}.
  \]
\end{bem}

% Beispiel: $H_1(\Omega)$, $\scp{u}{v}_{H^1(\Omega)} = \IntOmega{uv}{x} + \IntOmega{\nabla u \cdot \nabla v}{x}$.

\begin{satz}[Meyers/Serrin]
  $W^{k,p}(\Omega) \cap \Cont^\infty(\Omega)$ liegt dicht in $W^{k,p}(\Omega)$,
  \[
    %H^{k,p} \coloneqq
    \clos{W^{k,p}(\Omega) \cap \Cont^\infty(\Omega)}^{\norm{\blank}_{k,p}} = W^{k,p}(\Omega).
  \]
\end{satz}

\begin{defn}
  $W_0^{k,p}(\Omega) \coloneqq \clos{\Testfun(\Omega)}^{\norm{\blank}_{k,p}}$, \quad
  $H_0^1(\Omega) \coloneqq W^{1,2}_0(\Omega)$
\end{defn}

\begin{satz}
  Sei $\Omega$ ein beschränktes $\Cont^1$-Gebiet und $1 \leq p < \infty$. \\
  Dann existiert eine lineare stetige Abbildung $\tau : W^{1,p}(\Omega) \to L^p(\bOmega)$, sodass für alle $u \in W^{1,p}(\Omega) \cap \Cont(\clos{\Omega})$ gilt: $\tau(u) = u|_{\bOmega}$.
\end{satz}

% Beweis: Buch von Evans, Satz 1 in Abschnitt 5.5

\begin{defn}
  Die Abbildung $\tau$ heißt \emph{Spuroperator}, $\tau(u)$ heißt die \emph{Spur} von $u \in W^{1,p}(\Omega)$ auf $\bOmega$.
\end{defn}

\begin{satz}
  Sei $\Omega$ ein beschränktes $\Cont^1$-Gebiet.
  Dann gilt
  \[
    W_0^{1,p}(\Omega) = \Set{v \in W^{1,p}(\Omega)}{\tau(v) = 0}.
  \]
\end{satz}

% Beweis: Evans, Satz 2 in Abschnitt 5.5

% 4.1.3 Dualräume

\begin{defn}
  %Sei $(U, \norm{\blank}_U)$ ein Banachraum. \\
  %Der \emph{Dualraum} von $U$ ist $(U', \norm{\blank}_{U'})$ mit
  Der \emph{Dualraum} eines Banachraums $(U, \norm{\blank}_U)$ ist
  \begin{align*}
    U' & \coloneqq \{\, \text{lineare, stetige Abbildungen } \psi : U \to \R \,\}
    \quad \text{mit} \\
    \norm{\psi}_{U'} & \coloneqq \sup_{u \in U \setminus \{ 0 \}} \frac{\abs{\psi(u)}}{\norm{u}_U}
    \enspace = \enspace \sup_{\mathclap{u \in U, \, \norm{u}_U = 1}} \enspace \psi(u).
  \end{align*}
\end{defn}

\begin{bsp}
  %$(L^p(\Omega))' \cong L^q(\Omega)$
  Gelte $\nicefrac{1}{p} + \nicefrac{1}{q} = 1$ mit $p, q \in \ointerval{1}{\infty}$.
  Dann ist die Abbildung
  \[
    j : L^q(\Omega) \to (L^p(\Omega))', \quad
    f \mapsto (g \mapsto \IntOmega{f(x) g(x)}{x})
  \]
  ein isometrischer Isomorphismus.
\end{bsp}

\begin{nota}
  $\scp{\psi}{u}_{U', U} \coloneqq \psi(u)$ \enspace für $\psi \in U'$, $u \in U$.
\end{nota}

% 4.6
\begin{satz}[\emph{Riesz'scher Darstellungssatz}] \mbox{} \\
  Sei $(H, \scp{\blank}{\blank}_H)$ ein Hilbertraum.
  Dann ist 
  \[
    j : H \to H', \quad
    \psi \mapsto (\phi \mapsto \scp{\psi}{\phi}_H)
  \]
  ein isometrischer Isomorphismus.
\end{satz}

\begin{defn}
  \begin{minipage}[t]{0.8 \linewidth}
    $W^{-1,q} \coloneqq (W_0^{1,p}(\Omega))'$, wobei $\nicefrac{1}{p} + \nicefrac{1}{q} = 1$, \\
    $H^{-1}(\Omega) \coloneqq W^{-1,2} = (H_0^1(\Omega))'$.
  \end{minipage}
\end{defn}

\begin{defn}
  Für $\Omega \subset \R^d$ heißt $\gamma \coloneqq k - \nicefrac{d}{p}$ \emph{Sobolev-Zahl} zu $W^{k,p}(\Omega)$.
\end{defn}

\begin{satz}
  %Für $m < \gamma$ existiert eine stetige Einbettung $W^{k,p}(\Omega) \hookrightarrow \Cont^m(\Omega)$.
  Für $m < \gamma$ ist $W^{k,p}(\Omega) \hookrightarrow \Cont^m(\Omega)$ wohldefiniert und stetig.
\end{satz}

\begin{samepage}

% 4.2. Variationsgleichungen
\subsection{Variationsgleichungen}

\begin{situation}
  Sei $\Omega \subset \R^d$ beschränkt.
  Wir betrachten nun wieder
  \[
    \text{(RWP\tss{1})} \quad
    \left\{ \begin{array}{rlll}
      \LL u &=& f &\text{ in $\Omega$} \\
      u &=& 0 &\text{ auf $\bOmega$}
    \end{array} \right.
  \]
  \vspace{-0.5cm}
  \begin{align*}
    \text{mit} \quad
    \LL u(x) & = - \sum_{i=1}^d \DO_i (\sum_{j=1}^d a_{ij}(x) \DO_j u) + \sum_{i=1}^d b_i(x) \DO_i u + c(x) u \\
    & = - \dive(A(x) \DO u) + b(x) \cdot \DO u + c(x) u.
  \end{align*}
  Sei $u$ eine Lösung von (RWP\tss{1}) und $\varphi \in \Testfun(\Omega)$.
  Dann gilt
  \begin{align*}
    & \enspace \IntOmega{f(x) \varphi(x)}{x}
    = \enspace \IntOmega{\LL u(x) \varphi(x)}{x} \\
    = & \enspace - \IntOmega{\dive(A(x) \DO u(x)) \varphi(x)}{x} + \IntOmega{\left( b(x) \cdot \DO u(x) + c(x) u(x) \right) \cdot \varphi(x)}{x} \\
    = & \enspace \IntOmega{A(x) \DO u(x) \cdot \DO \varphi(x)}{x} + \IntOmega{\left( b(x) \cdot \DO u(x) + c(x) u(x) \right) \cdot \varphi(x)}{x}
  \end{align*}

  \iffalse
  Nebenrechnung:
  \begin{align*}
    & - \IntOmega{\sum_i \DO_i (\sum_j a_{ij}(x) \DO_j u(x) \varphi(x))}{x} \\
    = & - \IntbOmega{\sum_i (\sum_j a_{ij}(x) \DO_j u(x)) \eta_i(x) \varphi(x)}{s(x)} \\
    & + \IntOmega{\sum_i (\sum_j a_{ij}(x) \DO_j u(x)) \DO_i \varphi(x)}{x} \\
    = & \IntOmega{A(x) \DO u(x) \cdot \DO \varphi(x)}{x}
    % weil die Testfunktion auf dem Rand verschwindet
  \end{align*}
  \fi
\end{situation}

\end{samepage}

% Vorlesung vom 24.11.2015

\begin{defn}
  Eine Funktion $u \in H_0^1(\Omega)$ heißt \emph{schwache Lösung} von (RWP\tss{1}), wenn~$u$ folgende Variationsgleichung erfüllt:
  \begin{align*}
    & \IntOmega{A(x) \DO u(x) \cdot \DO \varphi(x) + b(x) \cdot \DO u(x) \varphi(x) + c(x) u(x) \varphi(x)}{x} \\
    = \enspace & \IntOmega{f(x) \varphi(x)}{x}
    \quad \text{für alle } \varphi \in H_0^1(\Omega).
    \qquad \qquad \text{\probl{(VGL\tss{1})}}
  \end{align*}
\end{defn}

\begin{sprechweise}
  Der Raum, in dem man~$u$ sucht, heißt \emph{Lsgsraum} (oder \textit{Ansatzraum}), der Raum von~$\varphi$ heißt \emph{Testraum}.
\end{sprechweise}

% Fragen:
% 1) Ist jede klassische Lösung von (RWP\tss{1}) auch Lösung von (VGL\tss{1})?
% 2) Ist (VGL\tss{1}) lösbar? Ist die Lösung von (VGL\tss{1}) eindeutig? Hängt die Lösung von (VGL\tss{1}) stetig von den Daten ab?
% 3) Wie löst man (VGL\tss{1}) numberisch?
% 4) Wie lautet die Variationsgleichungbei inhomogenen RWBn?

\begin{prob}[Allg. Variationsproblem]
  Seien Abb. $\ell : H_0^1(\Omega) \to \R$ und $B : H_0^1(\Omega) \times H_0^1(\Omega) \to \R$ gegeben.
  Gesucht ist $u \in H_0^1(\Omega)$, sodass
  \[
    \text{\probl{(VGL\tss{1})\tprime}} \qquad
    B(u, \varphi) = \ell(\varphi) \quad
    \forall \varphi \in H_0^1(\Omega).
  \]
\end{prob}

\begin{bem}
  Im obigen Setting ist \enspace
  $\ell(\varphi) \coloneqq \IntOmega{f(x) \varphi(x)}{x}$ \enspace
  und
  \[
    B(u, \varphi) \coloneqq \IntOmega{A(x) \DO u(x) \cdot \DO \varphi(x) + b(x) \cdot \DO u(x) \varphi(x) + c(x) u(x) \varphi(x)}{x}
  \]
\end{bem}

\begin{defn}
  Sei $X$ ein Banachraum.
  Eine bilin. Abb. $B : X \times X \to \R$ heißt
  \begin{itemize}
    %\item \emph{bilinear}, falls $B(u, \blank)$ und $B(\blank, \varphi)$ linear für alle $u, \varphi \in X$ sind,
    %\item \emph{symmetrisch}, falls $B(u, \varphi) = B(\varphi, u)$ für alle $u, \varphi \in X$,
    \item \emph{positiv}, falls $B(u, u) > 0$ für alle $u \in X \setminus \{ 0 \}$,
    \item \emph{stark positiv} (\textit{koerziv}, \textit{koerzitiv}), falls ein $\lambda > 0$ existiert, sodass
    \[ \fa{u \in X} B(u, u) \geq \lambda \norm{u}_X^2, \]
    \item \emph{beschränkt} (oder \textit{stetig}), falls ein $\mu > 0$ existiert, sodass
    \[ \fa{u, \varphi \in X} \abs{B(u, \varphi)} \leq \mu \norm{u}_X \norm{\varphi}_X. \]
  \end{itemize}
\end{defn}

\begin{lem}
  \begin{itemize}
    \item Die Abbildung~$B$ in (VGL\tss{1})\tprime{} ist bilinear und beschränkt.
    \item Die Abbildung $\ell$ in (VGL\tss{1})\tprime{} ist linear und stetig.
  \end{itemize}
\end{lem}

\begin{satz}
  Sei $\Omega$ ein beschr. Lipschitz-Gebiet.
  Dann ist jede klassische Lsg $u \in \Cont^2 \cap \Cont^1(\bOmega)$ von (RWP\tss{1}) eine schwache Lsg von (VGL\tss{1})\tprime{}.
\end{satz}

% 4.3 Eindeutige Lösung elliptischer PDEs
\subsection{Eindeutige Lösung elliptischer DGLn}

% 4.9
\begin{satz}[\emph{Lax-Milgram}]
  Sei H ein Hilbertraum und $B : H \times H \to \R$ eine beschränkte, koerzitive Bilinearform.
  Dann gibt es für jedes $\ell \in H'$ eine eindeutige Lösung $u \in H$ von  $\fa{\varphi \in H} B(u, \varphi) = \ell(\varphi)$.
  Es gilt $\norm{u}_H \leq \nicefrac{1}{\lambda} \norm{\ell}_{H'}$ mit der Koerzitivitätskonstante $\lambda$ von~$B$.
\end{satz}

% Vorlesung vom 30.11.2015

% 4.10
\begin{lem}[\emph{Poincaré-Ungleichung}] 
  Sei $\Omega$ beschränkt.
  Dann $\exists \, C > 0 :$
  \[
    \norm{u}_{L^2(\Omega)} \leq C \norm{\nabla u}_{L^2(\Omega, \R^d)} = C \left( \IntOmega{\sum_i \abs{\DO_i u}^2}{x} \right)^{\nicefrac{1}{2}} \quad
    \forall \, u \in H_0^1(\Omega).
  \]
\end{lem}

\begin{kor}
  Mit $C_1 \coloneqq (1 + C^2)^{\nicefrac{-1}{2}}$ und $C_2 \coloneqq 1$ gilt für alle $u \in H_0^1(\Omega)$:
  \[ C_1 \norm{u}_{H^1(\Omega)} \leq \norm{\nabla u}_{L^2(\Omega, \R^d)} \leq C_2 \norm{u}_{H^1(\Omega)}. \]
\end{kor}

% 4.11
\begin{lem}
  Falls $\LL$ glm. elliptisch ist und $b(x) \equiv 0$ sowie $c(x) \geq 0$ in~$\Omega$ gelten, so ist~$B$ in (VGL\tss{1})\tprime{} koerziv.
\end{lem}

% 4.12
\begin{satz}
  Sei $\Omega \subset \R^d$ beschränkt und sei $\mathcal{L} u = - \dive (A(x) \DO u) + c(x) u$ glm. elliptisch, $c(x) \geq 0$ in $\Omega$, $a_{ij}, c_j \in L^\infty(\Omega)$ und $f \in L^2(\Omega)$. \\
  Dann besitzt (VGL\tss{1})\tprime{} eine eindeutige Lösung $u \in H_0^1(\Omega)$. \\
  Außerdem existiert ein $\hat{C} > 0$, sodass $\norm{u}_{H^1(\Omega)} \leq \hat{C} \cdot \norm{f}_{L^2(\Omega)}$.
\end{satz}

\begin{samepage}

\begin{defn}
  Sei $f \in H^{-1}(\Omega)$.
  Eine Fktn $u \in H_0^1(\Omega)$ heißt \textit{schwache Lösung} von (RWP\tss{1}), falls \enspace
  $B(u, \varphi) = \scp{f}{\varphi}_{H^{-1}(\Omega), H_0^1(\Omega)}$ $\forall \, \varphi \in H_0^1(\Omega)$.
\end{defn}

\begin{bem}
  Gelte $b \equiv 0$, $c \geq 0$, glm. Elliptizität, $c, a_{ij} \in L^\infty(\Omega)$. \\
  Dann existiert nach Lax-Milgram genau eine schwache Lösung.
\end{bem}

\begin{lem}
  Sei $A$ gleichmäßig elliptisch und $a_{ij}, b_i, c \in L^\infty(\Omega)$. \\
  Dann existiert ein $\mu_0 > 0$, sodass für alle $\mu > \mu_0$ das RWP
  \[
    \left\{ \begin{array}{rlll}
      \LL u + \mu u &=& f &\text{ in $\Omega$} \\
      u &=& 0 &\text{ auf $\bOmega$}
    \end{array} \right.
  \]
  für alle $f \in H^{-1}(\Omega)$ eine eind. schwache Lösung $u \in H_0^1(\Omega)$ besitzt.
\end{lem}

% Vorlesung vom 1.12.2015

% 4.4 RWPe mit inhomogenen Dirichlet- und/oder Robin-Randbedingungen
\subsection{RWPe mit anderen Randbedingungen}

\end{samepage}

% a)

\begin{prob}
  Wir untersuchen nun das inhomogene Randwertproblem
  \[
    \text{\probl{(RWP\tss{2})}} \quad
    \left\{ \begin{array}{r c l l}
      \LL u & = & f & \text{in } \Omega, \\
      u & = & g & \text{auf } \bOmega.
    \end{array} \right.
  \]
  Angenommen, $g \in \Cont(\bOmega) \cap L^2(\bOmega)$ besitzt eine Fortsetzung $\tilde{g} \in \Cont^2(\Omega) \cap \Cont(\cOmega)$ mit $\tilde{g}|_{\bOmega} = g$.
  Dann ist $u \in \Cont^2(\Omega) \cap \Cont(\cOmega)$ genau dann eine Lösung von (RWP\tss{2}), wenn $v \coloneqq u - \tilde{g}$ eine Lösung von
  \[
    \text{\probl{(RWP\tss{2})\tprime}} \quad
    \left\{ \begin{array}{r c l l}
      \LL v & = & f - \LL \tilde{g} & \text{in } \Omega, \\
      v & = & 0 & \text{auf } \bOmega
    \end{array} \right.
  \]
  ist.
  Schwache Formulierung von (RWP\tss{2})\tprime{}:
  Ges. ist $v \in H_0^1(\Omega)$ mit
  \begin{align*}
    & \IntOmega{(A(x) \DO v(x) \cdot \DO \varphi(x) + b(x) \cdot \DO v(x) \varphi(x) + c(x) v(x) \varphi(x))}{x} \\
    = \enspace & \IntOmega{f \cdot \varphi}{x} + \IntOmega{(A(x) \DO \tilde{g} \cdot \DO \varphi + b \cdot \DO \tilde{g} \varphi + c \tilde{g} \varphi)}{x} \quad
    \forall \, \varphi \in H_0^1(\Omega).
  \end{align*}
  Voraussetzungen: $a_{ij}, b_i, c \in L^\infty(\Omega)$, $f \in L^2(\Omega)$, $\tilde{g} \in \Cont(\cOmega) \cap H^1(\Omega)$ und $g \in L^2(\bOmega)$.
  Ges. ist ein $u \in U \coloneqq \Set{w \in H^1(\Omega)}{\tau(w) = g}$ mit
  % Dabei ist $\tau : H^1(\Omega) \to L^2(\bOmega)$ der Spuroperator
  \[
    \underbrace{\IntOmega{A(x) \DO u \cdot \DO \varphi + b \DO u \varphi + c u \varphi}{x}}_{B(u, \varphi) \coloneqq} =
    \underbrace{\IntOmega{f \varphi}{x}}_{\ell(\varphi) \coloneqq} \quad
    \forall \, \varphi \in H_0^1(\Omega).
    \enspace \text{\probl{(VGL\tss{2})}}
  \]
  Für $f \in H^{-1}(\Omega)$ verwendet man
  \[
    B(u, \varphi) = \ell'(\varphi) \coloneqq \scp{f}{\varphi}_{H^{-1}(\Omega), H_0^1(\Omega)} \enspace
    \forall \, \varphi \in H_0^1(\Omega).
    \quad \text{\probl{(VGL\tss{2})\tprime}}
  \]
\end{prob}

\begin{satz}
  Sei $B : H_0^1(\Omega) \times H_0^1(\Omega) \to \R$ beschränkt und koerziv. \\
  Dann besitzt (VGL\tss{2}) genau dann eine eindeutige Lösung $u \in U$, wenn ein $u_0 \in H^1(\Omega)$ existiert, sodass $\tau(u_0) \equiv g$ f.\,ü. auf $\bOmega$.
\end{satz}

% b)

\begin{prob}
  Wir betrachten nun die Randbedingung
  \[
    \text{\probl{(RWP\tss{3})}} \quad
    \left\{ \begin{array}{r c l l}
      \LL u & = & f & \text{in } \Omega, \\
      A(x) \DO u \cdot \nu + \mu u & = & g & \text{auf } \bOmega \text{ (glatt)}
    \end{array} \right.
  \]
  Falls $u \in \Cont^2(\Omega) \cap \Cont(\cOmega)$ eine Lösung ist und $\varphi \in \Cont^\infty(\cOmega)$, so gilt
  \begin{align*}
    & \IntOmega{f \varphi}{x}
    = - \IntOmega{\dive(A(x) \DO u) \varphi + b(x) \DO u \varphi + c(x) u \varphi}{x} \\
    = & - \IntbOmega{A(x) \DO u \cdot \nu \varphi}{s} + \IntOmega{A(x) \DO u \DO \varphi + b(x) \DO u \varphi + c(x) u \varphi}{x}.
  \end{align*}
  Aus der Randbedingung bekommen wir
  \[
    \IntbOmega{A(x) \DO u \cdot \nu \varphi}{s} + \mu \IntbOmega{u \varphi}{s} = \IntbOmega{g \varphi}{s}.
  \]
  Zusammengesetzt erhalten wir die Variationsgleichung
  \[
    \mu \IntbOmega{u \varphi}{s} + \IntOmega{A \DO u \DO \varphi + b \cdot \DO u \varphi + c u \varphi}{x} = \IntOmega{f \varphi}{x} + \IntbOmega{g \varphi}{s}.
  \]
  Wegen Dichtheit von $\Cont^\infty(\cOmega)$ in $H^1(\Omega)$ ist diese Gleichung nicht nur für $\varphi \in \Cont^\infty(\cOmega)$ sondern allgemeiner für $\varphi \in H^1(\Omega)$ erfüllt.
\end{prob}

\begin{defn}
  Sei $\mu \in \R$, $f \in L^2(\Omega)$, $g \in L^2(\bOmega)$.
  Eine Fktn $u \in H^1(\Omega)$ heißt \textit{schwache Lösung} von (RWP\tss{3}), falls für alle $\varphi \in H^1(\Omega)$ gilt:
  \[
    \underbrace{\mu \IntbOmega{u \varphi}{s} + \IntOmega{A \DO u \DO \varphi + b \DO u \varphi + c u \varphi}{x}}_{B(u, \varphi) \coloneqq} =
    \underbrace{\IntOmega{f \varphi}{x} + \IntbOmega{g \varphi}{s}}_{\ell(\varphi) \coloneqq}.
  \]
\end{defn}

% Vorlesung vom 7.12.2015

% §4.5 Approximation von Variationsgleichungen
\subsection{Approximation von Variationsgleichungen}

\begin{verf}
  Gegeben sei ein Hilbertraum~$H$, eine beschränkte, koerzive Bilinearform $B : H \times H \to \R$ und ein $\ell \in H'$. \\
  Gesucht ist eine Lösung $u \in H$ der Variationsgleichung
  \[
    \text{\probl{(VGL)}} \qquad
    B(u, \varphi) = \ell(\varphi) \quad
    \forall \, \varphi \in H.
  \]
  Wir wollen diese Lösung annähern durch die Lösung eines möglichst ähnlichen, aber \textit{endlichdim.} Problems.
  Dazu wählen wir einen endlichdim. Unterraum $U_n \subset H$ (dieser ist wieder ein Hilbertraum), eine beschränkte, koerzitive Bilinearform $B_n : U_n \times U_n \to \R$ und ein Element $\ell_n \in U_n'$.
  Wir bestimmen dann die Lösung~$u_n$ von
  \[
    \text{\probl{(VGL)\tss{n}}} \qquad
    B_n(u_n, \varphi) = \ell_n(\varphi) \quad
    \forall \, \varphi \in U_n.
  \]
\end{verf}

\begin{fragen}
  \begin{enumerate}
    \item Wie berechnet man die Lösung $u_n$ von (VGL)\tss{n}?
    \item Wie kann man $U_n$, $B_n$ und~$\ell_n$ wählen, sodass $u_n \xra[n \to \infty]{} u$?
  \end{enumerate}
\end{fragen}

\begin{defn}
  Die Approximation von (VGL) mittels (VGL)\tss{n} mit $U_n \subset H$ und $B_n = B|_{U_n \times U_n}$ heißt \emph{konforme Approximation} von (VGL).
  Eine solche Methode wird als \emph{Verfahren von Ritz} bezeichnet.
\end{defn}

\begin{vorgehen}
  Um die Lösung~$u_n$ von (VGL)\tss{n} zu berechnen, wählen wir zunächst eine Basis $w_1, \ldots, w_{d_n}$ von $U_n$.
  Wir setzen
  \begin{align*}
    \hat{\ell} & \coloneqq (\ell_n(w_1), \ldots, \ell_n(w_{d_n}))^T \in \R^{d_n}, \quad \text{und} \\
    \hat{B} & \coloneqq (B_{ij}) \in \R^{d_n \times d_n}
    \enspace \text{mit} \enspace
    B_{ij} \coloneqq B(w_i, w_j).
  \end{align*}
  Dann ist $u_n = \gamma_1 w_1 + \ldots + \gamma_{d_n} w_{d_n} \in U_n$ genau dann eine Lösung von (VGL)\tss{n}, wenn $\gamma = (\gamma_1, \ldots, \gamma_{d_n})^T \in \R^{d_n}$ erfüllt:
  \[
    \hat{B} \gamma = \hat{\ell} \qquad
    \text{(\emph{Galerkin-Gleichung})}.
  \]
\end{vorgehen}

% 4.14
\begin{lem}[\emph{Céa}]
  Für die Lösungen $u_n$ der konformen Approximation (VGL)\tss{n} und die Lösung~$u$ von (VGL) gilt
  \[ \norm{u_n - u}_H \leq C \left( \inf_{v \in U_n} \norm{u - v}_H + \norm{\ell_n - \ell}_{U_n'} \right) \]
\end{lem}

\begin{folgerung}
  Für $u_n \xra[n \to \infty]{} u$ genügt es, $U_n$ u. $\ell_n$ so zu wählen, dass
  \[
    \fa{u \in H\!}\! \inf_{v_n \in U_n} \norm{u - v_n}_H \xra[n \to \infty]{} 0, \qquad
    \norm{\ell_n - \ell}_{U'_n} \xra[n \to \infty]{} 0.
  \]
\end{folgerung}

\begin{bem}
  Ist $\ell(\varphi)$ durch Integration einer Funktion gegeben, so kann man für $\ell_n(\varphi)$ eine Annäherung dieses Integrals etwa mittels der summierten Trapezregel verwenden.
\end{bem}

\begin{bem}
  Wir betrachten (VGL\tss{1}).
  Es gibt mehrere sinnvolle Möglichkeiten, die Basiselemente~$w_i$ zu wählen.
  Man versucht dabei zu erreichen, dass die Matrix $\hat{B}$ möglichst einfach (wenige von null verschiedene Einträge) und gut konditioniert ist.
  \begin{enumerate}
    \item Angenommen, es gibt eine Basis von Eigenfunktionen~$w_j$ von~$\LL$, $\LL w_j = \lambda_j w_j$, die in $L^2(\Omega)$ eine Orthonormalbasis bilden. \\
    Dann ist~$\hat{B}$ eine Diagonalmatrix mit Einträgen~$\lambda_j$.
    Beispielsweise ist $w_j(x) \coloneqq \sin(\pi j x)$ eine EF von $\LL \coloneqq - \Laplace$ auf $\Omega = \ointerval{0}{1}$ zum EW~$\pi^2 j^2$ und es gilt $\scp{w_i}{w_j}_{L^2(\Omega)} = 0$ für $i \neq j$.
    % Vorlesung vom 8.12.2015
    \item $U_n \coloneqq \spann \Set{w_j(x) = x^j (1 - x)}{j = 1, \ldots, n } \subset H_0^1(\Omega)$ \\
    (Das ist eine schlechte Wahl, da dann $\hat{B}$ vollbesetzt.)
    \item Wir unterteilen $\Omega = \ointerval{0}{1}$ durch das Gitter
    $0 = x_0 < x_1 < \ldots < x_n < x_{n+1} = 1$,
    $x_i = i h$ mit
    $h = \nicefrac{1}{n+1}$,
    \[
      U_n \coloneqq \Set{v \in \Cont(0, 1)}{\fa{i} v|_{\cinterval{x_{i-1}}{x_i}} \in \mathbb{P}_1[x], v(0) = v(1) = 0}
    \]
    Eine Basis von $U_n$ sind die \textit{Hutfunktionen} $w_1, \ldots, w_n$:
    \begin{center}
      \scriptsize
      \begin{tikzpicture}%[scale=0.8]
        %\draw (-0.5,0) -- (4.5,0);
        \draw [blue] (-0.5,0.03) -- (0,0.03) -- (1,1.03) -- (2,0.03) -- (4.5,0.03);
        \draw [red] (-0.5,-0.03) -- (1,-0.03) -- (2,0.97) -- (3,-0.03) -- (4.5,-0.03);
        \draw [green] (-0.5,0) -- (2,0) -- (3,1) -- (4,0) -- (4.5,0);
        \node at (5,0.9) [right,blue] {$w_{j-1}(x)$};
        \node at (5,0.5) [right,red] {$w_{j}(x)$};
        \node at (5,0.1) [right,green] {$w_{j+1}(x)$};
        \draw [fill=black] (0,0) circle (.05) node [below] {$x_{j-2}$};
        \draw [fill=black] (1,0) circle (.05) node [below] {$x_{j-1}$};
        \draw [fill=black] (2,0) circle (.05) node [below] {$x_{j}$};
        \draw [fill=black] (3,0) circle (.05) node [below] {$x_{j+1}$};
        \draw [fill=black] (4,0) circle (.05) node [below] {$x_{j+2}$};
      \end{tikzpicture}
    \end{center}
    Wir betrachten die VGL zu (RWP\tss{1}) mit $g_0 = g_1 = 0$. \\
    Wenn wir $\ell$ durch die Trapezregel approximieren, erhalten wir
    \[
      \hat{B} = \frac{1}{h} \begin{pmatrix}
        2 & -1 & &&& 0 \\
        -1 & 2 & -1 &&& \\
        & -1 & 2 & -1 && \\
        && \ddots & \ddots & \ddots \\
        &&& -1 & 2 & -1 \\
        0 &&&& -1 & 2
      \end{pmatrix}, \quad
      \ell_n(w_j) = h f(x_j),
    \]
    also das Finite-Differenzen-Verfahren.
  \end{enumerate}
\end{bem}

% §5. Methode der finiten Elementen (FEM)
\section{Methode der Finiten Elemente (FEM)}

\begin{ziel}
  (VGL) mittels (VGL)\tss{n} approximieren.
\end{ziel}

\begin{idee}
  Zerlege $\Omega$ in endlich viele Teilgebiete.
  Wir wählen $U_n$ als Raum der Funktionen, die sich als Linearkombination von Basisfktn schreiben lassen, deren Träger nur wenige Teilgebiete umfasst.
\end{idee}

\begin{bem}
  Als Teilgebiete verwendet man
  in $\R^1$ regelmäßige Teilintervalle, 
  in $\R^2$ Dreiecke oder Rechtecke und
  in $\R^3$ Tetraeder.
  Als lokale Ansatzfunktionen über den Teilgebieten verwenden wir Polynome.
  Globale Ansatzfktn über $\Omega$ sind lokale Ansatzfktn mit bestimmten Glattheitsbedingungen am Rand der Teilgebiete.
\end{bem}

\begin{defn}
  Ein \emph{finites Element} (FE) in $\R^d$ ist ein Tripel $(K, P, \Sigma)$ mit
  \begin{itemize}
    \miniitem{0.45 \linewidth}{$K \subset \R^d$ ist kompakt,}
    \miniitem{0.45 \linewidth}{$\partial K$ ist Lipschitz-stetig,}
    \item $P$ ist ein endlichdim. lin. Raum von Funktionen $p \in \Cont^s(K, \R)$
    \item $\Sigma = \{ b_1, \ldots, b_m \}$ mit $b_j \in (\Cont^s(K, \R))'$ ist \emph{$P$-unisolvent}, \dh{}
    \[
      \fa{\alpha \in \R^m} \exu{p \in P} b_j(p) = \alpha_j, \enspace j = 1, \ldots, m
    \]
  \end{itemize}
\end{defn}

\begin{bem}
  % Beobachtung von Christian
  $\Sigma$ ist $P$-unisolvent $\iff$ $\Sigma$ ist Basis von $P' \subset (\Cont^s(K, \R))'$
\end{bem}

\begin{samepage}

\begin{lem}
  \begin{itemize}
    \item Sei $\Sigma = \{ b_1, \ldots, b_m \}$ P-unisolvent.
    \begin{itemize}
      \item $b_1, \ldots b_m$ sind linear unabhängig.
      \item Sei $p_j \in P$ so gewählt, dass $b_i(p_j) = \delta_{ij}$. \\
      Dann ist $\{ p_1, \ldots, p_m \}$ eine Basis von $P$.
    \end{itemize}
    \item Sei $\{ p_1, \ldots, p_m \}$ eine Basis von $P$ und seien $b_i \in (\Cont^s(K, \R))'$ mit $b_i(p_j) = \delta_{ij}$, $i, j = 1, \ldots, m$.
    Dann ist $\{ b_1, \ldots, b_m \}$ P-unisolvent.
  \end{itemize}
\end{lem}

% Ciarlet, §2.3
\begin{defn}
  Ein finites Element $(K, P, \Sigma)$ heißt zu einem anderen FE $(\hat{K}, \hat{P}, \hat{\Sigma})$ \emph{affin äquivalent} \textit{vermöge} einer invertierbaren affinen Abbildung $F : \R^d \to \R^d, \enspace \hat{x} \mapsto B \hat{x} + b$, falls gilt:
  \begin{itemize}
    \miniitem{0.3 \linewidth}{$K = F(\hat{K})$}
    \miniitem{0.4 \linewidth}{$P = \Set{p \coloneqq \hat{p} \circ F^{-1}}{\hat{p} \in \hat{P}}$}
    \item $\Sigma = \Set{b_i : p \mapsto b_i(p \circ F)}{\hat{b}_i \in \hat{\Sigma}}$
  \end{itemize}
\end{defn}

% §5.1 Finite Elemente vom Lagrange-Typ
\subsection{Finite Elemente vom Lagrange-Typ}

\end{samepage}

\begin{defn}
  Der \emph{$d$-Simplex} mit Ecken $a_1, \ldots, a_{d+1} \in \R^d$ ist
  \[
    K = \Set{x = \sum_{j=1}^{d+1} \mu_j a_j}{0 \leq \mu_j \leq 1, \, j = 1, \ldots, d + 1, \sum_{j=1}^{d+1} \mu_j = 1} \subset \R^d.
  \]
  Dabei heißen $\mu_1, \ldots, \mu_{d+1}$ baryzentrische Koordinaten von~$x$. \\
  $K$ heißt \emph{nicht entartet}, falls $a_1, \ldots, a_{d+1}$ affin unabhängig sind. \\
  Das Simplex mit den Ecken $a_j = e_j \in \R^d$, $j = 1, \ldots, d$, und $a_{d+1} = 0$ heißt \emph{$d$-Einheitssimplex}~$\hat{K}$.
\end{defn}

% Vorlesung vom 14.12.2015

% ausgelassen: erstes Beispiel

\begin{bspe}
  Ein nichtentartetes Simplex im $\R^1$ ist ein geschlossenes Intervall, im $\R^2$ ein Dreieck und im $\R^3$ ein Tetraeder.
\end{bspe}

\begin{lem}
  Jedes nicht entartete $d$-Simplex~$K$ ist affin äquivalent zu~$\hat{K}$:
  Es gibt genau eine Abb. $F : \hat{K} \to K, \enspace \hat{x} \mapsto A_K \hat{x} + b_K$ mit einer Matrix $A_K \in \GL(d)$, sodass $F(e_j) = a_j$ und $F(0) = a_{d+1}$.
\end{lem}

\begin{samepage}
\begin{defn}
  Ein \emph{simpliziales finites Element vom Lagrange-Typ} der Ordnung~$k$ ist ein Tripel $(K, P, \Sigma)$ mit
  \begin{itemize}
    \item einem $d$-Simplex $K$ mit Ecken $a_1$, \ldots, $a_{d+1}$,
    \item $P = \Poly_k \coloneqq \R[x_1, \ldots, x_d]_{\leq k} = \{ \text{Polynome vom Grad $\leq k$} \}$
    \item $\Sigma = \Set{b_a : P \to \R, \enspace p \mapsto p(a)}{a \in \mathcal{K}_k}$ mit der \textit{Knotenmenge}
    \[
      \mathcal{K}_k = \Set{x = \sum_{j=1}^{d+1} \mu_j a_j}{\sum_{j=1}^{d+1} \mu_j = 1, \enspace \mu_j \in \{ 0, \tfrac{1}{k}, \ldots, \tfrac{k-1}{k}, 1 \}}.
    \]
  \end{itemize}
\end{defn}
\end{samepage}

\begin{bemn}
  \begin{itemize}
    \item Sei $K$ ein $d$-Simplex. Dann ist $\dim(\Poly_k) = \abs{\mathcal{K}_k} = \binom{k+d}{d}$.
    \item Die kanonische Basis von $\Poly_1$ für $\hat{K} \subset \R^d$ ist
    \[
      \hat{p}_i(\hat{x}) = \hat{x}_i \text{ für } i = 1, \ldots, d, \qquad
      \hat{p}_{d+1}(\hat{x}) = 1 - \hat{x}_1 - \ldots - \hat{x}_d.
    \]
    Dann bilden die $\hat{b}_j \in \Sigma$ eine Dualbasis der $\hat{p}_i$, \dh{} $\hat{b}_j(\hat{p}_i) = \delta_{ij}$.
    \item Die duale Basis von $\Poly_2$ zu $\Sigma$ für $\hat{K} \subset \R^d$ ist
    \begin{align*}
      & \Set{\hat{p}_i}{i \in \{ 1, \ldots, d+1 \} } \cup \Set{\hat{p}_{ij}}{i \neq j \in \{ 1, \ldots, d+1 \}} \quad \text{wobei} \\
      & \hat{p}_i(\hat{x}) = \mu_j(\hat{x}) (2 \mu_j(\hat{x}) - 1), \quad
      \hat{p}_{ij}(\hat{x}) = 4 \mu_i(\hat{x}) \mu_j(\hat{x}), \\
      & \mu_i(\hat{x}) = \hat{x}_i \text{ für } i = 1, \ldots, d, \quad
      \mu_{d+1}(\hat{x}) = 1 - \hat{x}_1 - \ldots - \hat{x}_d
    \end{align*}
    \item Kanonische Basiselemente $p_1, \ldots, p_m \in \Poly_k$ für einen allgemeinen Simplex $K \subset \R^d$ kann man wie folgt berechnen:
    \begin{enumerate}
      \item Finde eine affin lineare Bijektion $F : \hat{K} \to K$ wie früher.
      \item Setze $p_i(x) \coloneqq \hat{p}_i(F^{-1}(x))$ für $i = 1, \ldots, m$.
    \end{enumerate}
  \end{itemize}
\end{bemn}

% Vorlesung vom 15.12.2015

% §5.2 Räume von Finite-Elemente-Funktionen auf $\Omega$
\subsection{Räume von Finite-Elemente-Funktionen auf $\Omega$}

% Ziel: Finde endlichdimensionalen Raum $U_n$ und eine Basis davon.

\begin{defn}
  Sei $\Omega \subset \R^d$ ein beschränktes, polygonal berandetes Gebiet. \\
  Eine \emph{Triangulierung} von $\Omega$ mit simplizialen finiten Elementen vom Lagrange-Typ der Ordnung~$k$ ist eine endliche Menge
  \[
    T(\cOmega) = \Set{(K_i, P(K_i), \Sigma(K_i))}{i = 1, \ldots, N}
    \quad \text{mit}
  \]
  \begin{itemize}
    \item $(K_i, P(K_i), \Sigma(K_i))$ sind simpl. El. vom Lagrange-Typ der Ord. $k$,
    \miniitem{0.45 \linewidth}{$\cOmega = K_1 \cup \ldots \cup K_N$,}
    \miniitem{0.48 \linewidth}{$\inte(K_i) \cap \inte(K_j) = \emptyset$ für $i \neq j$,}
    \item Jede Seite von~$K_i$, \dh{} jedes von~$d$ Eckpunkten von~$K_i$ aufgesp. $(d-1)$-dimensionale Simplex, ist entweder Teil des Gebietrandes $\bOmega$ oder gleichzeitig Seite genau eines anderen Simplex~$K_j$.
  \end{itemize}
\end{defn}

\begin{defn}
  Die \textit{Knotenmenge} von $T(\cOmega)$ ist die Vereinigung der Knotenmengen der simpl. FE, \dh{} $\mathcal{K}_k = \mathcal{K}_k(K_1) \cup \ldots \cup \mathcal{K}_k(K_N)$.
\end{defn}

\begin{defn}
  Der \emph{Raum der finiten Elemente} zu einer Triang.~$T(\cOmega)$ von~$\Omega$ mit simplizialen FE vom Lagrange-Typ der Ordnung~$k$ und Knotenmenge $\mathcal{K}_k = \{ \tilde{a}_1, \ldots, \tilde{a}_n \}$ ist
  \[
    U_n = \Set{v \in \Cont(\cOmega)}{v|_{K_i} \in \Poly_1(K_i) \text{ für } i = 1, \ldots, N}.
  \]
\end{defn}

\begin{satz}[$k=1$]
  Sei $U_n$ der Raum der \textit{linearen finiten Elemente} zu einer Triang.~$T(\cOmega)$ mit simpl. FE vom Lagrange-Typ der Ord.~$1$.
  \begin{itemize}
    \item Sei $K$ ein nichtentart. $d$-Simplex mit Ecken $a_1$, \ldots, $a_{d+1}$. \\
    Dann ist durch $p(a_j)$, \ldots, $p(a_{d+1})$ ein Polynom $p \in \Poly_1(K)$ eindeutig bestimmt.
    Für alle $p \in \Poly_1(K)$ und $x \in K$ gilt
    \[
      p(x) = p(a_1) p_1(x) + \ldots + p(a_{d+1}) p_{d+1}(x).
      \enspace \text{wobei} \enspace
      p_i(a_j) = \delta_{ij}.
    \]
    \item Sind $\mathcal{K} = \{ \tilde{a}_1, \ldots, \tilde{a}_n \}$ die Knoten der Triangulierung, so ist eine Funktion $v \in U_n$ durch die Vorgabe von $v(\tilde{a}_1)$, \ldots, $v(\tilde{a}_n)$ eindeutig definiert.
    Es gilt $U_n \subset H^1(\Omega)$.
    \item Eine Basis von $U_n$ ist gegeben durch die Funktionen $p_j \in U_n$ mit $p_j(\tilde{a}_i) = \delta_{ij}$ für $i, j = 1, \ldots, n$.
    Insbesondere gilt $\dim U_n = n$.
  \end{itemize}
\end{satz}

% Vorlesung vom 21.12.2015

% ausgelassenes Beispiel: Triangulierung von $[0,1]^2$ mit zwei Dreiecken
% ausgelassene Bemerkung: Fall $k = 2$, $d = 2$

\begin{satz}[$k \geq 1$]
  Sei $T(\cOmega)$ eine Triangulierung mit finiten Lagrange-Elementen der Ordnung~$k$, $U_n$ der zugehörige Raum der FE und $\mathcal{K}_k$ die Knotenmenge von $T(\cOmega)$.
  Dann ist durch Vorgabe von $v|_{\mathcal{K}_k}$ eindeutig ein $v \in U_n \subset H^1(\Omega)$ bestimmt.
  Eine Basis von~$U_n$ ist durch $p_j \in U_n$ mit $p_j(\tilde{a}_i) = \delta_{ij}$, $i, j = 1, \ldots, n$, gegeben.
\end{satz}

\begin{samepage}

% §5.3 Realisierung der Finite-Elemente-Methode

\begin{verf}[Realisierung der Finite-Elemente-Methode] \mbox{} \\
  \begin{enumerate}
    \item Eingabe und Beschreibung des RWPs
    \item Umformulierung in ein Variationsproblem
    \item Generierung einer Triangulierung. Entweder \textit{uniforme Zerlegung} oder Zerlegung mit \textit{lokaler Verfeinerung} von~$\Omega$.
    \item Erzeugung eines endlich-dim. Problems, \dh{} Berechnen der Koeffizientenmatrix und der rechten Seite der Galerkin-Gleichung 
    \item Lösung der Galerkin-Gleichung
  \end{enumerate}
\end{verf}

% Vorlesung vom 22.12.2015

% §5.3.1 Beschreibung des RWPs (ausgelassen)

% §5.3.2 Gittergenerierung (ausgelassen)

% uniforme Zerlegung oder lokale Verfeinerung einer Zerlegung

% §5.3.3 Erzeugung eines endlich-dim. Problems (ausgelassen)

% §5.4 Konvergenz der FE-Methode
\subsection{Konvergenz der FE-Methode}

\end{samepage}

\begin{defn}
  Sei $(K, P, \Sigma)$ ein finites Element, $P \subset \Cont^s(K)$. \\
  Dann heißt $\Pi_K w$ \emph{$P$-Interpolierende} einer Fktn $w \in \Cont^s(K)$, falls
  \begin{itemize}
    \miniitem{0.3 \linewidth}{$\Pi_K w \in P$,}
    \miniitem{0.6 \linewidth}{$b_j(\Pi_K w) = b_j(w)$ für jedes $b_j \in \Sigma$.}
  \end{itemize}
\end{defn}

\begin{bem}
  \begin{itemize}
    %\item Für Lagrange-FE ist $s = 0$.
    \item Ist $p_1$, \ldots, $p_m$ eine zu $\Sigma$ duale Basis von~$P$, \dh{} $b_i(p_j) = \delta_{ij}$, so gilt $\Pi_K w = {\sum}_{i=1}^m b_i(w) p_i$.
    \item Für Lagrange-FE gilt \enspace
    $w(\tilde{a}_j) = b_j(w) = b_j(\Pi_K w) = \Pi_K w(\tilde{a}_j)$
    \item $\fa{p \in P} \Pi_K p = p$
  \end{itemize}
\end{bem}

% Vorlesung vom 11.1.2015

\begin{defn}
  Sei $U_n$ ein FE-Raum zu einer Triangulierung $T(\cOmega)$ und sei $\{ p_1, \ldots, p_n \}$ die kanonische Basis von $U_n$, \dh{} $b_i(p_j) = \delta_{ij}$. \\
  Die \emph{$U_n$-Interpolierende} einer Funktion $w \in \Cont^s(\cOmega)$ ist dann
  \[
    \Pi w \coloneqq \sum_{i=1}^n b_i(w) p_i \in U_n.
  \]
\end{defn}

\begin{lem}
  Für alle $K_i \in T(\cOmega)$ und $w \in \Cont^s(\cOmega)$ gilt $(\Pi w) |_K = \Pi_{K_i} (w|_{K_i})$ und somit $\norm{w - \Pi w}_{H^1(\Omega)} = \enspace \sum_{\mathclap{K_i \in T(\cOmega)}} \quad \norm{w - \Pi_{K_i} w}_{H^1(K_i)}$.
\end{lem}

% 5.5
\begin{lem}
  Sei $F : \hat{K} \to K$ mit $F(\hat{x}) = A \hat{x} + b$, $A \in \GL(d)$, und $l \in \N$.
  \begin{itemize}
    \item Es gilt \enspace
    $v \in H^l(K) \iff v \circ F \in H^l(\hat{K})$
    \item Es existiert eine Konstante $c > 0$, sodass
    \begin{align*}
      \abs{v \circ F}_{H^l(\hat{K})} & \leq c \cdot \norm{A}_2^l \cdot \tfrac{1}{\sqrt{\abs{\det(A)}}} \cdot \abs{v}_{H^l(K)} \\
      \abs{\hat{v} \circ F^{-1}}_{H^l(K)} & \leq c \cdot \norm{A^{-1}}_2^l \cdot \sqrt{\abs{\det(A)}} \cdot \abs{\hat{v}}_{H^l(\hat{K})}
    \end{align*}
    für alle $v \in H^l(K)$ bzw. $\hat{v} \in H^l(\hat{K})$ gilt, wobei
    \[
      \abs{v}_{H^l(K)} \coloneqq \left( \Int{K}{}{\sum_{\abs{\alpha} = l} \norm{\DO^\alpha v}^2} {x}\right)^{\nicefrac{1}{2}}
    \]
    eine Seminorm auf $H^l(K)$ ist.
  \end{itemize}
\end{lem}

% Vorlesung vom 12.1.2015

\begin{defn}
  Sei $K$ ein $d$-Simplex mit Ecken $a_1, \ldots, a_{d+1}$.
  Wir definieren:
  \begin{alignat*}{3}
    & h(K) \coloneqq {\max}_{i,j=1}^{d+1} \abs{a_i - a_j} &&
    \text{\emph{Durchmesser}} \\
    & \rho(K) \coloneqq 2 \sup \, \Set{R > 0}{\ex{x \!\in\! K\!}\! B_R(x) \subseteq K} \quad &&
    \text{\emph{Innendurchmesser}} \\
    & \sigma(K) \coloneqq \nicefrac{h(K)}{\rho(K)} > 1 &&
    \text{(misst "`Spitzheit"')}
  \end{alignat*}
\end{defn}

% 5.6
\begin{lem}
  Sei der $d$-Simplex $K$ affin äquivalent zu $\hat{K}$ vermöge $F : \hat{K} \to K$, \enspace $\hat{x} \mapsto A \hat{x} + b$, $A \in \GL(d)$.
  Dann gilt:
  \[
    \norm{A}_2 \leq \nicefrac{h(K)}{\rho(\hat{K})}, \qquad
    \norm{A^{-1}}_2 \leq \nicefrac{h(\hat{K})}{\rho(K)}.
  \]
\end{lem}

% 5.7
\begin{lem}
  Sei $k \geq 0$.
  Dann existiert eine Konstante $c > 0$, sodass
  \[
    \inf_{\hat{p} \in \Poly_k(\hat{K})} \norm{\hat{v} - \hat{p}}_{H^{k+1}(\hat{K})} \leq c \cdot \abs{\hat{v}}_{H^{k+1}(\hat{K})} \qquad
    \forall \, \hat{v} \in H^{k+1}(\Omega).
  \]
\end{lem}

% 5.8
% 3.1.5 im Ciarlet
\begin{satz}[Abschätzung des lokalen Interpolationsfehlers] \mbox{} \\
  Sei $(\hat{K}, P(\hat{K}), \Sigma(\hat{K}))$ ein finites Element mit $\Sigma(\hat{K}) \subset \Cont^s(\hat{K})'$. \\
  Angenommen, für $r, k \in \N$ mit $0 \leq r \leq k+1$ gilt
  \[
    H^{k+1}(\hat{K}) \hookrightarrow \Cont^s(\hat{K})
    \quad \text{und} \quad
    \mathbb{P}_k(\hat{K}) \subseteq P(\hat{K}) \subset H^r(\hat{K}).
  \]
  Dann existiert ein $C > 0$, sodass für alle zu $(\hat{K}, P(\hat{K}), \Sigma (\hat{K}))$ affin äquivalente FE $(K, P(K), \Sigma(K))$ und für alle $v \in H^{k+1}(K)$ gilt:
  \[
    \abs{v - \Pi_K v}_{H^r(K)} \leq C \cdot \frac{h(K)^{k+1}}{\rho(K)^r} \abs{v}_{H^{k+1}(K)}.
  \]
\end{satz}

% Vorlesung vom 12.1.2016

% 3.1.6 im Ciarlet
\begin{kor}
  Es gibt eine Konstante $\tilde{C} > 0$, sodass für jedes zu $(\hat{K}, P(\hat{K}), \Sigma(\hat{K}))$ affin äquivalente FE $(K, P(K), \Sigma(K))$ mit $h(K) \leq 1$ und jedes $v \in H^{k+1}(K_i)$ gilt:
  \begin{align*}
    \norm{v - \Pi_K v}_{H^r(K_i)} & \leq \tilde{C} \cdot \frac{h(K_i)^{k+1}}{\rho(K_i)^r} \abs{v}_{H^{k+1}(K_i)} \\
    & = \tilde{c}_K \sigma(K_i)^r h(K_i)^{k+1-r} \abs{v}_{H^{k+1}(K_i)}.
  \end{align*}
\end{kor}

\begin{bspe}
  Das letzte Korollar liefert für FE vom Lagrange-Typ:
  
  \begin{tabular}[t]{l l l l}
    & Ordnung & $k=1$ & $k=2$ \\ \hline
    % Lagrange FEM ($s = 0$) & Lagrange-Typ (1) & Lagrange-Typ (2) \\
    Voraussetzungen & Regularität für $v$ & $H^2(K)$ & $H^3(K)$ \\
    & Beschränkung für $d$ & $d \leq 3$ & $d \leq 5$ \\
    & Beschränkung für $r$ & $0 \leq r \leq 2$ & $0 \leq r \leq 3$ \\ \hline
    Konvergenz & $\norm{v - \Pi v}_{H^r(K)}$ & $\O(h^{2-r})$ & $\O(h^{3-r})$
  \end{tabular}
\end{bspe}

% 5.4.1. Abschätzung des globalen Interpolationsfehlers

\begin{voraussetzungen}
  Wir suchen die Lösung von (VGL) im Lösungsraum~$U$ mit $H_0^1(\Omega) \subseteq U \subseteq H^1(\Omega)$.
  Es gelte:
  \begin{enumerate}[leftmargin=2.5em]
    \item[(V\tss{1})] $\cOmega$ ist ein Polyeder und $\mathcal{T} = (T_n(\cOmega))_{n \in \N}$ ist eine Familie von Triangulierungen von~$\Omega$ mit finiten Elementen. \\
    Es sei $\mathcal{T}$ \emph{regulär}, \dh{} es existiert eine Konstante $\sigma_0 > 0$, sodass $\sigma(K) \leq \sigma_0$ für alle $n \in \N$ und $K \in T_n(\cOmega)$ und es gilt $h_n \coloneqq \enspace \max_{\mathclap{K \in T_n(\cOmega)}} \enspace h(K) \xra[n \to \infty]{} 0$.
    \item[(V\tss{2})] Alle FE $(K, P(K), \Sigma(K))$ der Familie $\mathcal{T}$ sind affin äquiv. zu einem Referenzelement $(\hat{K}, P(\hat{K}), \Sigma(\hat{K}))$ mit $\Sigma(\hat{K}) \subset \Cont^s(\hat{K})'$.
    \item[(V\tss{3})] $U_n \subset \Cont(\cOmega)$ ist der FE-Funktionenraum zu $T_n(\cOmega)$.
    \item[(V\tss{4})]
    Für $r, k \in \N$ mit $0 \leq r \leq k+1$ gilt
    \[
      H^{k+1}(\hat{K}) \hookrightarrow \Cont^s(\hat{K})
      \quad \text{und} \quad
      \mathbb{P}_k(\hat{K}) \subseteq P(\hat{K}) \subset H^r(\hat{K}).
    \]
  \end{enumerate}
\end{voraussetzungen}

\begin{satz}
  Seien obige Voraussetzungen erfüllt.
  Sei $\Pi_n : U \to U_n$ der zu~$T_n(\cOmega)$ gehörende \textit{$U_n$-Interpolationsoperator}.
  Dann existiert ein $c > 0$, sodass für alle $0 \leq l \leq r$, $n \in \N$ und $v \in H^{k+1}(\Omega) \cap U$ gilt:
  \[
    \left( \sum_{K \in T_n(\cOmega)} \norm{v - \Pi_n v}^2_{H^l(K)} \right)^{\nicefrac{1}{2}} \leq c \cdot h_n^{k+1-l} \cdot \abs{v}_{H^{k+1}(\Omega)}.
  \]
\end{satz}

\begin{bemn}
  Für $l = 0 \leq r$ gilt $U_n \subset L^2(\Omega)$ und
  \[
    \norm{v - \Pi_n v}_{L^2(\Omega)} = \left( \sum_{K \in T_n(\cOmega)} \!\!\! \norm{v - \Pi_K v}^2_{L^2(K)} \right)^{\nicefrac{1}{2}} \!\!\!\!\! \leq c \cdot h_n^{k+1} \cdot \abs{v}_{H^{k+1}(\Omega)}.
  \]
  Für $l = 1 \leq r$ gilt $U_n \subset H^1(\Omega)$ und
  \[
    \norm{v - \Pi_n v}_{H^1(\Omega)} = \left( \sum_{K \in T_n(\cOmega)} \!\!\! \norm{v - \Pi_K v}^2_{H^1(K)} \right)^{\nicefrac{1}{2}} \!\!\!\!\! \leq c \cdot h_n^k \cdot \abs{v}_{H^{k+1}(\Omega)}.
  \]
\end{bemn}

% 5.9
% 3.2.2 im Ciarlet
\begin{satz}[Konvergenz der konformen Approximation] \mbox{} \\
  Seien die Voraussetzungen (V\tss{1}) -- (V\tss{3}) und (V\tss{4}) mit $r = 1$ erfüllt. \\
  Dann gilt für die Lösung $u$ von (VGL) und die Lösung $u_n$ der konformen Approximation (VGL)\tss{n} mit $\ell_n = \ell|_{U_n}$ die Abschätzung
  \[
    \norm{u - u_n}_{H^1(\Omega)} \in \O(h_n^k \cdot \abs{u}_{H^{k+1}(\Omega)}) \qquad
    \text{falls $u \in H^{k+1}(\Omega)$.}
  \]
\end{satz}

\begin{bsp}
  Für $k=1$, $u \in H^2(\Omega)$ ist die Konvergenzordnung bloß~$1$.
  % sonst ($u \not\in H^2(\Omega)$) siehe Thm 3.2.3. in Ph.G.Garlet "The FEM for elliptic problems" für Konvergenz (aber ohne bekannte Konvergenzordnung)
\end{bsp}

\begin{bem}
  Die konforme Approximation von~$u$ hat gemessen mit der $L^2$-Norm (nach bisherigem Kenntnissstand) im Vergleich zur Interpolation von~$u$ eine um eins schlechtere Konvergenzordnung:
  \begin{alignat*}{3}
    \norm{u - u_n}_{L^2(\Omega)} & \leq \norm{u - u_n}_{H^1(\Omega)} && \in \O(h_n^k \cdot \abs{u}_{H^{k+1}(\Omega)}) \\
    \norm{u - \Pi_n u}_{L^2(\Omega)} &&& \in \O(h_n^{k+1} \cdot \abs{u}_{H^{k+1}(\Omega)})
  \end{alignat*}
  Dieser Missstand lässt sich mit weiteren Voraussetzungen beheben:
\end{bem}

% 5.12
\begin{lem}[\emph{Aubin-Nitsche}]
  Seien $U$ und $H$ Hilberträume, $E : U \to H$ eine stetige inj. Einbettung und $U_n \subset U$ ein endlichdim. Teilraum. \\
  Sei $B : U \times U \to \R$ eine stetige, koerzitive Bilinearform und $\ell \in U'$.
  Seien $u \in U$, $u_n \in U_n$ die Lösungen (VGL) bzw. (VGL)\tss{n}.
  Dann gilt
  \[
    \norm{E (u - u_n)}_H \leq c_B \cdot \norm{u - u_n}_{U} \cdot \enspace \sup_{\mathclap{r \in H \setminus \{ 0 \}}} \enspace \frac{\inf_{w \in U_n} \norm{w(r) - w}_U}{\norm{r}_H},
  \]
  wobei $w(r) \in U$ für $r \in H$ die Lösung des \emph{adjungierten Problems}
  \[
    B(\varphi, w(r)) = \scp{E(\varphi)}{r}_H \quad \forall \varphi \in U \qquad
    \text{ist.}
  \]
\end{lem}

% Vorlesung vom 19.1.2016

% 5.13
\begin{kor}
  Seien die Voraussetzungen aus dem Satz zur Konvergenz der konformen Approximation erfüllt.
  Zusätzlich existiere ein $c_a > 0$, sodass für alle $r \in L^2(\Omega)$ die Lösung $w(r)$ vom adjungierten Problem
  \[
    B(\varphi, w(r)) = \scp{\varphi}{r}_{L^2(\Omega)} \quad
    \forall \varphi \in H^1(\Omega)
  \]
  die Abschätzung $\norm{w(r)}_{H^2(\Omega)} \leq c_a \cdot \norm{r}_{L^2(\Omega)}$ erfüllt.
  Dann gilt
  \[
    \norm{u - u_n}_{L^2(\Omega)} \in \O(h^{k+1}_n \cdot \abs{u}_{H^{k+1}(\Omega)}) \qquad
    \text{falls $u \in H^{k+1}(\Omega)$.}
  \]
\end{kor}

% 5.5. Verallgemeinerungen

% 5.5.1. Rechteckige Elemente vom Lagrange-Typ
\subsection{Rechteckige finite Elemente}

\begin{defn}
  Ein \emph{rechteckiges finites Element vom Lagrange-Typ} der Ordnung~$k$ ist ein Tupel $(K, P(K), \Sigma(K))$ mit
  \begin{itemize}
    \item $K = \cinterval{c_1}{c_1 + r_1} \times \ldots \times \cinterval{c_d}{c_d + r_d} \subset \R^d$ ist ein Rechteck,
    \item $P(K) = \Qoly_k(K) \coloneqq \{\, p(x) = \enspace \sum_{\mathclap{\alpha \in \{ 0, \ldots, k \}^d}} \enspace \lambda_\alpha x_1^{\alpha_1} \cdot \ldots \cdot x_d^{\alpha_d} \,\} \subset \Poly_{dk}(K)$
    \item $\Sigma(K) = \Set{b : P(K) \to \R, \enspace p \mapsto p(a)}{a \in \mathcal{K}_k}$, wobei $\mathcal{K}_k = \Set{(c_1 + i_1 \tfrac{r_1}{k}, \ldots, c_d + i_d \tfrac{r_d}{k})}{i_j \in \{ 0, \ldots, k \}, \, j = 1, \ldots, d}$.
  \end{itemize}
\end{defn}

% ausgelassen: Beispiel

\begin{satz}
  Jedes Polynom $p \in \Qoly_k(K)$ ist eindeutig durch die Werte auf der Knotenmenge $\mathcal{K}_k$ definiert.
\end{satz}

\begin{defn}
  $T_n(\cOmega) \coloneqq \Set{(K_i, P(K_i), \Sigma(K_i))}{i = 1, \ldots, N}$ heißt Triangulierung von $\cOmega$ mit rechteckigen FE vom Lagrange-Typ, wenn
  \begin{itemize}
    \miniitem{0.4 \linewidth}{$\cOmega = K_1 \cup \ldots \cup K_N$,}
    \miniitem{0.5 \linewidth}{$\inte(K_i) \cap \inte(K_j) = \emptyset$ für $i \neq j$,}
    \item Jede Seite von $K_i$ ist entweder eine Teilmenge von $\bOmega$ oder die Seite von genau einem anderen~$K_j$.
  \end{itemize}
\end{defn}

\begin{defn}
  Der \textit{Finite-Element-Raum} zur Triangulierung $T_n(\cOmega)$ ist
  \[
    U_n \coloneqq \Set{v \in \Cont(\cOmega)}{v|_{K_i} \in \Qoly_k(K_i), \, i = 1, \ldots, N}.
  \]
\end{defn}

\begin{lem}
  \begin{itemize}
    \item $U_n \subset H^1(\Omega)$
    \item Eine Basis von $U_n$ ist durch Polynome $p_j \in U_n$ mit $p_i(a_j) = \partial_{ij}$ für alle $ia_j \in \mathcal{K}_k$ gegeben.
  \end{itemize}
\end{lem}

% Vorlesung vom 25.1.2016

% 5.5.2. Simpliziale Elemente vom Hermite-Typ
\subsection{Simpliziale Elemente vom Hermite-Typ}

\begin{defn}
  Ein \emph{simpliziales finites Element vom Hermite-Typ} ist ein Tupel $(K, P(K), \Sigma(K))$ mit
  \begin{itemize}
    \item einem $d$-Simplex $K$ mit Ecken $a_1$, \ldots, $a_{d+1}$,
    \item $P(K) \coloneqq \Poly_3(K)$
    \item $
      \arraycolsep=2pt
      \begin{array}[t]{r l}
        \Sigma(K) \coloneqq & \Set{p \mapsto p(a_i)}{i = 1, \ldots, d+1} \\
        \cup & \Set{p \mapsto p(a_{ijl})}{1 \!\leq\! i \!<\! j \!<\! l \!\leq\! d\!+\!1, \, a_{ijl} \coloneqq \tfrac{1}{3} (a_i \!+\! a_j \!+\! a_l)} \\
        \cup & \Set{p \mapsto \DO p(a_i) (a_j - a_i)}{1 \leq i \neq j \leq d+1}
      \end{array}$
  \end{itemize}
  Der zugehörige Finite-Elemente-Raum zu einer Triangulierung $T(\cOmega)$ mit simpl. finiten Elementen vom Hermite-Typ ist
  \[
    U_n \coloneqq \Set{v \in \Cont(\cOmega)}{v|_K \in \Poly_3(K) \, \forall K \in T(\cOmega)}
  \]
\end{defn}

% Ausgelassen: graphische Darstellung, Beispiel mit $d=2$, Berechnung (bzw. Aufstellen von Gleichungen) von dualer Basis

\begin{bem}
  $U_n \subset \Cont^1(\cOmega)$ gilt (nur) für $d = 1$. \\
  $U_n \subset \Cont^1(\cOmega)$ für $d = 2$ erreicht man mit folgenden Elementen:
  \begin{itemize}
    \item \emph{Argyris-Dreieck}: $(K, P(K), \Sigma(K))$ mit
    \begin{itemize}
      \item einem $2$-Simplex~$K$ mit Ecken $a_1, a_2, a_3$,
      \item $P(K) \coloneqq \Poly_5(K)$ und
      \item $
        \arraycolsep=0.5pt
        \begin{array}[t]{r l l l}
          \Sigma(K) \coloneqq & \Set{p \mapsto p(a_i)}{1 \leq i \leq 3} &
          \cup & \Set{p \mapsto \partial_x p(a_i)}{1 \leq i \leq 3} \\
          \cup & \Set{p \mapsto \partial_y p(a_i)}{1 \leq i \leq 3} &
          \cup & \Set{p \mapsto \partial_{yy} p(a_i)}{1 \leq i \leq 3} \\
          \cup & \Set{p \mapsto \partial_{xx} p(a_i)}{1 \leq i \leq 3} &
          \cup & \Set{p \mapsto \partial_{xy} p(a_i)}{1 \leq i \leq 3} \\
          \cup & \multicolumn{3}{l}{\Set{p \mapsto \DO p(\tfrac{a_i + a_j}{2}) \cdot \nu_{ij}}{1 \leq i < j \leq 3}}
        \end{array}$
       (wobei $\nu_{ij}$ der äußere Normalenvektor an $\nicefrac{(a_i + a_j)}{2}$ ist)
    \end{itemize}
    \item \emph{Bell-Dreieck}: $(K, P(K), \Sigma(K))$ mit
    \begin{itemize}
      \item einem $2$-Simplex~$K$ mit Ecken $a_1, a_2, a_3$,
      \item $P(K) \coloneqq \Set{p \in \Poly_5}{\tfrac{\partial p}{\partial \nu_{ij}} \in \Poly_3(K') \text{ für alle Kanten $K'$ von $K$}}$
      \item $
        \arraycolsep=2pt
        \begin{array}[t]{r l l l}
          \Sigma(K) \coloneqq & \Set{p \mapsto p(a_i)}{1 \leq i \leq 3} &
          \cup & \Set{p \mapsto \partial_x p(a_i)}{1 \!\leq\! i \!\leq\! 3} \\
          \cup & \Set{p \mapsto \partial_y p(a_i)}{1 \!\leq\! i \!\leq\! 3} &
          \cup & \Set{p \mapsto \partial_{xx} p(a_i)}{1 \!\leq\! i \!\leq\! 3} \\
          \cup & \Set{p \mapsto \partial_{yy} p(a_i)}{1 \!\leq\! i \!\leq\! 3} &
          \cup & \Set{p \mapsto \partial_{xy} p(a_i)}{1 \!\leq\! i \!\leq\! 3}
        \end{array}$
    \end{itemize}
  \end{itemize}
\end{bem}

% Vorlesung vom 27.1.2016

% 5.5.3. Nichtkonforme finite Elemente
\subsection{Nichtkonforme finite Elemente}

Bisher war $B_n = B|_{U_n \times U_n}$.
Manchmal ist es schwierig, $B$ exakt auszuwerten und muss daher angenähert werden, etwa wenn $B$ durch Integration definiert ist.
Dann hilft folgende Verallgemeinerung des Lemmas von Céa:

\begin{satz}[1. Lemma von \emph{Strang}]
  Sei $U$ ein Hilbertraum und $(U_n)_{n \in \N}$ eine Familie von Unterräumen.
  Sei $B : U \times U \to \R$ eine beschränkte, koerzitive Bilinearform und $(B_n : U_n \times U_n \to \R)_{n \in \N}$ eine \textit{gleichmäßig koerzitive} Familie beschränkter Bilinearformen, \dh{}
  \[
    \ex{\alpha > 0} \fa{n} B_n(u_n, u_n) \geq \alpha \norm{u_n}^2_U \quad
    \text{für alle $n \in \N$, $u \in U_n$.}
  \]
  Dann existiert eine Konstante $c > 0$, sodass
  \begin{align*}
    & \norm{u - u_n}_U \leq c \left( \inf_{v_n \in U_n} \Phi(v_n) + \norm{\ell - \ell_n}_{U_n'} \right)
    \quad \text{wobei} \\
    & \Phi(v_n) \coloneqq \norm{u - v_n}_U + \sup_{w_n \in U_n, w_n \neq 0} \tfrac{\abs{B(v_n, w_n) - B_n(v_n, w_n)}}{\norm{w_n}_U}
  \end{align*}
\end{satz}

\begin{defn}
  Das \emph{Fehlerfunktional der Quadraturformel} mit \textit{Stützpunkten}~$x_i^K$ und \textit{Gewichten}~$w_i^K$ ist
  \[
    E_K (\psi) \coloneqq \AInt{K}{\psi(x)}{x} - \sum_{i=1}^q w_i^K \psi(x_i^K).
  \]
\end{defn}

% 5.11
\begin{satz}[Konvergenzsatz für das Modellproblem] \mbox{} \\
  Seien die Voraussetzungen (V\tss{1}) -- (V\tss{3}) erfüllt, $P(\hat{K}) = \Poly_k(\hat{k})$ mit $k > \nicefrac{d}{2}$ (damit $H^{k+1}(\Omega) \hookrightarrow \Cont^s(\hat{K})$).
  Sei die Quadraturformel so gewählt, dass $E_{\hat{K}}(p) = 0$ für alle $p \in \Poly_{2k - 2}(\hat{K})$.
  Für die Lösung $u \in H_0^1(\Omega)$ von (VGL) mit $B(u, \varphi) \coloneqq \IInt{\DO u \cdot \DO \varphi}{x}$, $\ell(\varphi) \coloneqq \IInt{f \varphi}{x}$ mit $f \in H^k(\Omega)$ gelte $u \in H^{k+1}(\Omega)$.
  Dann gilt:
  \begin{itemize}
    \item Es gibt eine Konstante $C_1 > 0$, sodass
    $\forall \, p, q \in \Poly_k(K)$:
    \[
      E_K(\DO p \cdot \DO q) \leq C_1 \cdot h^k(K) \cdot \norm{p}_{H^k(K)} \cdot \norm{q}_{H^1(K)}
    \]
    \item Es gibt eine Konstante $C_2 > 0$, sodass
    $\forall$ $f \in H^k(K)$, $\varphi \in H^1(K)$:
    \[
      E_K(f \varphi) \leq C_2 \cdot h^k(K) \cdot \norm{f}_{H^k(K)} \cdot \norm{\varphi}_{H^1(K)}
    \]
    \item Für die Lsg $u_n \!\in\! U_n$ von (VGL)\tss{n} mit der nicht-konformen Approx. $B_n(u, \varphi)$ und $\ell_n(\varphi)$ mittels der Quadraturformel gilt:
    \[
      \norm{u - u_n}_{H^1(\Omega)} \leq C \cdot \left( \norm{u}_{H^{k+1}(\Omega)} + \norm{f}_{H^k(\Omega)} \right)
    \]
  \end{itemize}
\end{satz}

% Beweis: Ciarlet 4.1.4--4.1.6

\begin{defn}
  Sei $\Omega \subset \R^d$ ein Gebiet mit glattem Rand.
  Dann heißt $(\Omega_n, T(\cOmega_n))$ \emph{zulässige Gebietsapproximation}, falls $T_n(\cOmega_n)$ eine zulässige Triangulierung von~$\Omega_n$ ist und
  \[
    \bOmega_n \cap \{ \text{ Eckpunkte der Simplizes in $T(\cOmega_n)$ } \} \subset \bOmega.
  \]
\end{defn}

Wir betrachten nun

\begin{problem} \mbox{}
  \vspace{-1em}
  \[
    \text{\probl{(VGL\tss{n})}} \enspace \left\{ \begin{array}{l}
       \overbrace{\AInt{\Omega_n}{\DO u_n \cdot \DO \varphi_n}{x}}^{B_n(u_n, \varphi_n) \coloneqq} = \overbrace{\AInt{\Omega_n}{\tilde{f} \varphi_n}{x}}^{\ell_n (\varphi_n) \coloneqq} \quad \forall \, \varphi \in U_n \\
      u_n \in U_n
    \end{array} \right.
  \]
  wobei $\tilde{f} \in L^2(\Omega_n \cup \Omega)$ mit $\tilde{f}|_\Omega = f$
\end{problem}

% §5.5.4. Isoparametrische Finite Elemente
\subsection{Isoparametrische Finite Elemente}

\begin{defn}
  Sei $(\hat{K}, \hat{P}, \hat{\Sigma})$ ein gerades (simpliziales oder rechteckiges) FE vom Lagrange-Typ.
  Ein finites Element $(K, P, \Sigma)$ vom Lagrange-Typ (k) heißt \emph{isometrisch äquivalent} zu $(\hat{K}, \hat{P}, \hat{\Sigma})$, falls eine umkehrbare Abbildung
  \[
    F : \hat{K} \to K, \quad
    \hat{x} \mapsto (F_1(\hat{x}), \ldots, F_d(\hat{x}))
  \]
  mit $F_1, \ldots, F_d \in \hat{P}$ existiert, sodass
  \begin{itemize}
    \miniitem{0.3 \linewidth}{$K = F(\hat{K})$}
    \miniitem{0.65 \linewidth}{$P = \Set{p = \hat{p} \circ F^{-1}}{\hat{p} \in \hat{P}}$}
    \item $\Sigma = \Set{p \mapsto p(a_i)}{\text{ für Punkte } a_i \coloneqq F(\hat{a}_i), \hat{a}_i \in \mathcal{K}_k}$
  \end{itemize}
\end{defn}

\begin{bem}
  Die zu $(K, P, \Sigma)$ isoparametrische Abbildung~$F$ ist für isoparametrische FE vom Lagrange-Typ (k) eindeutig durch die Werte an den Knoten~$\hat{a}_i$ definiert.
\end{bem}

\columnbreak

% Vorlesung vom 1.2.2015

% §5.6. Finite Elemente für parabolische Probleme
\subsection{Finite Elemente für parabolische Probleme}

\begin{prob}
  Wärmeleitungsgleichung:
  \[
    \arraycolsep=2.5pt
    \left\{ \begin{array}{rcll}
      u_t(x,t) - \Laplace_x u(x, t) &=& f(x,t) &\text{in $\Omega \times \ointerval{0}{T}$} \\
      u(x,0) &=& u_0(x) & \text{für } x \in \Omega \\
      u(x, t) &=& 0 & \text{für } x \in \bOmega, t \in \cinterval{0}{T}
    \end{array} \right.
  \]
\end{prob}

Variationsgleichung: \enspace
Gesucht ist $u \in \Cont^1(\cinterval{0}{T}; H_0^1(\Omega))$ mit
\begin{align*}
  \IntOmega{u_t(x,t) \varphi(x)}{x}
  = \IntOmega{\Laplace u(x, t) \varphi(x)}{x} + \IntOmega{f(x,t) \varphi(x)}{x}
  & \quad \forall t \in \cinterval{0}{T} \\
  = - \IntOmega{\DO u(x, t) \cdot \DO \varphi(x)}{x} + \IntOmega{f(x,t) \varphi(x)}{x}
  & \quad \forall \varphi \in H_0^1(\Omega)
\end{align*}
und Anfangsbedingung $u(0) = u_0$.
Anders geschrieben:
\[
  \tfrac{\d}{\d t} \scp{u(t, \blank)}{\varphi} + B(u, \varphi) - \scp{f(t, \blank)}{\varphi} \qquad
  \forall \varphi \in H_0^1(\Omega).
\]


% §5.6.1. Die vertikale Linienmethode

\begin{verf}[\emph{Vertikale Linienmethode}] \mbox{} \\
  Idee: \enspace Erst Diskretisierung im Ort, dann Diskretisierung in der Zeit
  
  Wir wählen dazu einen endlichdim. Teilraum $U_n \subset U = H_0^1(\Omega)$ und betrachten dann die approximierte VGL
  \[
    \tfrac{\d}{\d t} \scp{u_n(t)}{\varphi_n} + B_n(u_n, \varphi_n) = \scp{f(t, \blank)}{\varphi_n} \quad \forall \, \varphi_n \in U_n
  \]
  Sei $\varphi_1, \ldots, \varphi_{d_n}$ eine Basis von $U_n$. Wir schreiben
  \[
    u_n(t, x) = {\sum}_{j=1}^{d_n} \gamma_j(t) \varphi_j(x).
  \]
  Sei $u_n^0 = \sum \gamma_j^0 \varphi_j$ eine Approximation von $u_0$.
  Wir erhalten die GGL
  \[
    \arraycolsep=2.5pt
    \left\{ \begin{array}{rcll}
      {\sum}_{i=1}^{d_n} \tfrac{\d}{\d t} \gamma_i(t) \scp{\varphi_j}{\varphi_i} + {\sum}_{i=1}^{d_n} \gamma_i(t) B_n(\varphi_j, \varphi_i) &=& \scp{f(t, \blank)}{\varphi_j} & \forall \, j, \\
      \gamma_j(0) &=& \gamma_j^0 & \forall \, j
    \end{array} \right.
  \]
  mit $\gamma(t) \!\in\! \R^{d_n}$.
  Wir definieren die \textit{Massenmatrix} $M \in \R^{d_n \times d_n}$, die Matrix $B \in \R^{d_n \times d_n}$ und $g : \cinterval{0}{T} \to \R^{d_n}$ durch
  \[
    M_{ij} = \IntOmega{\varphi_j(x) \varphi_i(x)}{x}, \enspace
    B_{ij} = \IntOmega{\DO \varphi_j \cdot \DO \varphi_i}{x}, \enspace
    g_j(t) = \IntOmega{f(t, x) \varphi_j(x)}{x}
  \]
  Dann können wir obige GGL wie folgt umschreiben:
  \[
    \left\{ \begin{array}{rcl}
      M \tfrac{\d}{\d t} \gamma(t) + B \gamma(t) &=& g(t) \\
      \gamma(0) &=& \gamma^0
    \end{array} \right.
  \]
  Durch Modellreduktion erhält man eine Gleichung
  \[
    \left\{ \begin{array}{rcl}
      \tilde{M} \tfrac{\d}{\d t} \tilde{\gamma}(t) + \tilde{B} \tilde{\gamma}(t) &=& \tilde{g}(t) \\
      \tilde{\gamma}(0) &=& \tilde{\gamma}^0
    \end{array} \right.
  \]
  sodass $\gamma \in \R^r$, $r < d_n$ und $\gamma \approx V \tilde{\gamma}$.
\end{verf}

% §5.6.2. Die horizontale Linienmethode (die Rothe-Methode)

\begin{verf}[\emph{Horizontale Linienmethode}, \textit{Rothe-Methode}] \mbox{} \\
  Idee: \enspace Erst Diskretisierung in der Zeit, dann Diskretisierung im Ort

  Sei $\tau \coloneqq \nicefrac{T}{q}$, $t_i \coloneqq i \cdot \tau$ und
  \[
    \psi_i (t) \coloneqq \begin{cases}
      \nicefrac{t - t_{i-1}}{\tau} & \text{für } t \in \cinterval{t_{i-1}}{t_i}, \\
      \nicefrac{t_i - t}{\tau} & \text{für } t \in \cinterval{t_i}{t_{i+1}}, \\
      0 & \text{sonst.}
    \end{cases}
  \]
  Wir verwenden die Approx. $u(x,t) \approx u_\tau(x, t) = {\sum}_{j=1}^q \psi_j(t) c_j(x)$, also $u_\tau (x, t_i) = c_i (x)$.
  Implizites Euler-Verfahren:
  \[
    \tfrac{\d}{\d t} u_\tau(x, t_{i+1}) \approx \tfrac{u_\tau(x, t_{i+1}) - u_\tau(x, t_i)}{\tau} = \tfrac{c_{i+1}(x) - c_i(x)}{\tau},
  \]
  Dies führt pro Zeitpunkt $t_i$ zu je einer VGL
  \[
    \scp{\tfrac{c_{i+1} - c_i}{\tau}}{\varphi} + B(c_{i+1}, \varphi) = \scp{f(t_{i+1})}{\varphi} \enspace
    \forall \, \varphi \quad
    \text{bzw.}
  \]
  \[
    \underbrace{\IntOmega{c_{i+1} \varphi}{x} + \tau \IntOmega{\DO c_{i+1} \cdot \DO \varphi}{x}}_{\hat{B}(c_{i+1}, \varphi)}
    = \underbrace{\tau \IntOmega{f(t_{i+1}, x) \varphi(x)}{x} + \IntOmega{c_i \varphi}{x}}_{\hat{\ell}(\varphi)} \enspace
    \forall \, \varphi.
  \]
  Diese VGLn lösen wir dann mittels der FEM iterativ für $i = 1, \ldots, q$.
\end{verf}

\end{document}