%% LyX 1.3 created this file. For more info, see http://www.lyx.org/. %% Do not edit unless you really know what you are doing. \documentclass[german]{book} \usepackage[T1]{fontenc} \usepackage[latin1]{inputenc} \usepackage{a4wide} \setcounter{secnumdepth}{3} \setcounter{tocdepth}{3} \setlength\parskip{\medskipamount} \setlength\parindent{0pt} \usepackage{varioref} \usepackage{makeidx} \makeindex \usepackage{graphicx} \usepackage{amssymb} \makeatletter %%%%%%%%%%%%%%%%%%%%%%%%%%%%%% LyX specific LaTeX commands. %% Because html converters don't know tabularnewline \providecommand{\tabularnewline}{\\} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Textclass specific LaTeX commands. \usepackage{amssymb} \usepackage{amsmath} \usepackage{amsthm} % \usepackage[thmmarks,amsmath]{ntheorem} \theoremstyle{plain} \newtheorem{thm}{Satz}[chapter] \numberwithin{equation}{chapter} \numberwithin{figure}{chapter} \theoremstyle{definition} \newtheorem{defn}[thm]{Definition} \theoremstyle{definition} \newtheorem{remark}[thm]{Bemerkung} \theoremstyle{definition} \newtheorem*{example*}{Beispiel} \theoremstyle{definition} \newtheorem*{annotation*}{Anmerkung} \theoremstyle{plain} \newtheorem{lem}[thm]{Lemma} %%Delete [thm] to re-start numbering \theoremstyle{definition} \newtheorem*{ziel*}{Ziel} \theoremstyle{definition} \newtheorem*{notation*}{Notation} \theoremstyle{definition} \newtheorem*{convention*}{Konvention} \theoremstyle{definition} \newtheorem*{implementation*}{Implementation} \usepackage{algorithmic} \renewcommand{\algorithmicrequire}{\textbf{Input:}} \renewcommand{\algorithmicensure}{\textbf{Output:}} \newcommand{\COMPUTE}{\item[\textbf{Compute:}]} \theoremstyle{definition} \newtheorem{algorithm}[thm]{Algorithmus} \theoremstyle{definition} \newtheorem*{remark*}{Bemerkung} \theoremstyle{plain} \newtheorem{prop}[thm]{Proposition} %%Delete [thm] to re-start numbering \theoremstyle{plain} \newtheorem{cor}[thm]{Korollar} %%Delete [thm] to re-start numbering \theoremstyle{definition} \newtheorem{conclusion}[thm]{Folgerung} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%% User specified LaTeX commands. \DeclareMathOperator{\dist}{dist} \DeclareMathOperator{\id}{id} \DeclareMathOperator{\Bild}{Bild} \DeclareMathOperator{\AC}{AC} \DeclareMathOperator{\supp}{supp} \DeclareMathOperator{\myspan}{span} \DeclareMathOperator{\conv}{conv} \DeclareMathOperator{\mydiv}{div} \DeclareMathOperator{\card}{card} \DeclareMathOperator{\diam}{diam} \newcommand{\intm}{-\negthickspace\negthickspace\negthickspace\negthickspace\int} \newcommand{\intmm}{-\negthickspace\negthickspace\negthickspace\int} \newcommand{\Cebysev}{\v{C}eby\v{s}ev} \usepackage{eepic} \RequirePackage{epic,eepic} \usepackage{nicefrac} \usepackage{babel} \makeatother \begin{document} \title{Einführende Kapitel der Numerik partieller Differentialgleichungen und Differentialungleichungen in Theorie und Praxis} \author{Mitschrift% \footnote{{\small Gefundene Fehler bitte an vigerske@mathematik.hu-berlin.de.}% } zur Vorlesung von Prof. Carstensen} \date{Sommersemester 2004} \maketitle \tableofcontents{} \newpage \chapter{Projektion auf konvexe Mengen} \section{Skalarprodukt} \begin{defn} [Skalarprodukt, Prä-Hilbert-Raum, Innenproduktraum]Für einen \underbar{reellen} Vektorraum (VR) $X$ heißt eine Abbildung $\left\langle \cdot,\cdot\right\rangle :X\times X\rightarrow\mathbb{R}$ \emph{Skalarprodukt}\index{Skalarprodukt}, falls $\forall x,y,z\in X$ $\forall\alpha,\beta\in\mathbb{R}$ \begin{enumerate} \item $\left\langle \alpha x+\beta y,z\right\rangle =\alpha\left\langle x,z\right\rangle +\beta\left\langle y,z\right\rangle $, \item $\left\langle x,y\right\rangle =\left\langle y,x\right\rangle $, \item $\left\langle x,x\right\rangle \geq0$ und ($\left\langle x,x\right\rangle =0$ $\Leftrightarrow$ $x=0$). \end{enumerate} Dann heißt $\left(X,\left\langle \cdot,\cdot\right\rangle \right)$ \emph{Prä-Hilbert-Raum}\index{Prä-Hilbert-Raum} oder \emph{Innenproduktraum}\index{Innenproduktraum}. \end{defn} % \begin{defn} [Orthogonalität]Zwei Vektoren $x,y\in X$ mit $\left\langle x,y\right\rangle =0$ heißen \emph{orthogonal}\index{orthogonal}. Schreibweise: $x\bot y$ \end{defn} \begin{remark} Wir betrachten hier nur \emph{reelle} Vektorräume, Banach-Räume und Hilbert-Räume. \end{remark} \begin{example*} Prä-Hilbert-Räume sind $\mathbb{R}^{n}$,\begin{eqnarray*} \ell^{2} & := & \left\{ \left(x_{j}\right)\in\mathbb{R}^{n}\left|\sum_{j=1}^{\infty}x_{j}^{2}<\infty\right.\right\} ,\\ L^{2}\left(\Omega\right) & := & \left\{ f:\Omega\rightarrow\mathbb{R}\textrm{ L-meßbar}\left|\int_{\Omega}\left|f\right|^{2}dx<\infty\right.\right\} .\end{eqnarray*} Keine Prä-Hilbert-Räume sind $L^{p}$ oder $\ell^{p}$ für $p\neq2$. \end{example*} \section{Eigenschaften von Innenprodukträumen} In diesem Abschnitt bezeichne $\left(X,\left\langle \cdot,\cdot\right\rangle \right)$ einen Innenproduktraum und $\left\Vert \cdot\right\Vert :=\sqrt{\left\langle \cdot,\cdot\right\rangle }$ die induzierte Norm. \subsection{Cauchy-Ungleichung} \index{Cauchy-Ungleichung}Für alle $x,y\in X$ gilt \[ \left\langle x,y\right\rangle \leq\left\Vert x\right\Vert \,\left\Vert y\right\Vert .\] Gleichheit (also $\left\langle x,y\right\rangle =\left\Vert x\right\Vert \,\left\Vert y\right\Vert $) gilt genau dann, wenn $x=0$ oder $y=\lambda x$ für ein $\lambda\geq0$. \subsection{Parallelogrammgleichung} \index{Parallelogrammgleichung}Für alle $x,y\in X$ gilt\[ \left\Vert x+y\right\Vert ^{2}+\left\Vert x-y\right\Vert ^{2}=2\left\Vert x\right\Vert ^{2}+2\left\Vert y\right\Vert ^{2}.\] Umgekehrt: Wenn $\left\Vert \cdot\right\Vert $ eine Norm ist, welche die Parallelogrammgleichung erüllt, dann existiert ein Skalarprodukt $\left\langle \cdot,\cdot\right\rangle $, welches $\left\Vert \cdot\right\Vert $ induziert. \subsection{Innenprodukträume im $\mathbb{R}^{n}$} $\left(\mathbb{R}^{n},\left\langle \cdot,\cdot\right\rangle \right)$ ist Innenproduktraum genau dann, wenn eine symmetrische positiv definite Matrix $A\in\mathbb{R}^{n\times n}$ existiert, so daß für alle $x,y\in\mathbb{R}^{n}$ gilt: \[ \left\langle x,y\right\rangle =x^{T}Ay.\] \section{Normierte lineare Räume} \begin{defn} [Norm, normierter linearer Raum]Für einen Vektorraum $X$ heißt eine Abbildung $\left\Vert \cdot\right\Vert :X\rightarrow\left[0,\infty\right)$ \emph{Norm}\index{Norm}, falls $\forall x,y\in X$ $\forall\alpha\in\mathbb{R}$ \begin{enumerate} \item $\left\Vert x\right\Vert \geq0$ und ($\left\Vert x\right\Vert =0$ $\Leftrightarrow$ $x=0$), \item $\left\Vert \alpha x\right\Vert =\left|\alpha\right|\left\Vert x\right\Vert $, \item $\left\Vert x+y\right\Vert \leq\left\Vert x\right\Vert +\left\Vert y\right\Vert $. \end{enumerate} $\left(X,\left\Vert \cdot\right\Vert \right)$ heißt dann \emph{normierter linearer Raum} (NLR). \end{defn} % \begin{defn} [Cauchy-Folge]Eine Folge $\left(x_{j}\right)\in X^{\mathbb{N}}$ heißt \emph{Cauchy-Folge} (CF)\index{Cauchy-Folge} im normierten linearen Raum $\left(X,\left\Vert \cdot\right\Vert \right)$, falls\[ \forall\varepsilon>0\,\exists n\in\mathbb{N}\,\forall j,k\geq n\quad\left\Vert x_{j}-x_{k}\right\Vert \leq\varepsilon.\] \end{defn} %~ \begin{defn} [Konvergenz, Limes]Eine Folge $\left(x_{j}\right)\in X^{\mathbb{N}}$ heißt \emph{konvergent}\underbar{\index{konvergent}}, falls \[ \exists x\in X\,\forall\varepsilon>0\,\exists n_{0}\in\mathbb{N}\,\forall n\geq n_{0}\quad\left\Vert x-x_{n}\right\Vert <\varepsilon.\] Dieses $x$ heißt dann \emph{Limes}\index{Limes} der Folge. \end{defn} %~ \begin{defn} [Vollständigkeit, Hilbert-Raum, Banach-Raum]Ein normierter linearer Raum heißt \emph{vollständig}\index{Vollständigkeit}, falls darin jede Cauchy-Folge konvergiert. Ein vollständiger Innenproduktraum heißt \emph{Hilbert-Raum}\index{Hilbert-Raum} (HR). Ein vollständiger normierter linearer Raum heißt \emph{Banach-Raum}\index{Banach-Raum} (BR). \end{defn} \section{Mengen in Banachräumen} In diesem Abschnitt bezeichne $\left(X,\left\Vert \cdot\right\Vert \right)$ einen Banach-Raum. \begin{defn} [Abgeschlossenheit]Eine Menge $M\subseteq X$ heißt \emph{abgeschlossen}\underbar{\index{abgeschlossen}}, falls für jede Folge $\left(x_{j}\right)\in M^{\mathbb{N}}$ mit $\left(x_{j}\right)\rightarrow x$ für ein $x\in X$ gilt, daß $x\in M$. \end{defn} % \begin{defn} [Vollständigkeit]Eine Menge $M\subseteq X$ heißt \emph{vollständig}\index{Vollständigkeit}, falls jede Cauchy-Folge in $M$ konvergiert (mit Limes in $M$). \end{defn} In Banach-Räumen ist $M$ genau dann vollständig , wenn $M$ abgeschlossen ist. \begin{defn} [Konvexität]Eine Menge $M\subseteq X$ heißt \emph{konvex}\underbar{\index{konvex}}, falls $\forall x,y\in M$ $\forall\lambda\in\left(0,1\right)$\[ \lambda x+\left(1-\lambda\right)y\in M.\] \end{defn} % \begin{defn} [Unterraum]Eine Menge $M\subseteq X$ heißt \emph{Unterraum}\index{Unterraum}, falls $0\in M$ und $\forall x,y\in M$ $\forall\alpha,\beta\in\mathbb{R}$ \[ \alpha x+\beta y\in M.\] \end{defn} Unterräume sind konvex. \section{Bestapproximation in konvexen Mengen} \begin{defn} [Abstand]Für eine Menge $M\subset X$, $M\neq\emptyset$, in einem normierten linearen Raum $\left(X,\left\Vert .\right\Vert \right)$, und ein $x\in X$ heißt\[ \dist\left(x,M\right)=\dist_{\left\Vert .\right\Vert }\left(x,M\right):=\inf_{m\in M}\left\Vert x-m\right\Vert \] \emph{Abstand} \index{Abstand}von $x$ zu $M$. \end{defn} % \begin{defn} [Bestapproximierende]Ein Element $m\in M$ heißt \emph{Bestapproximierende} \index{Bestapproximierende}von $x$ in $M$, falls \[ \left\Vert x-m\right\Vert =\dist\left(x,M\right).\] Schreibweise: $\mathcal{P}_{M}\left(x\right):=$Menge aller Bestapproximierenden von $x$ in $M$. \end{defn} \begin{thm} [Charakterisierungssatz]\label{thm:Charakterisierungssatz}\index{Charakterisierungssatz}In einem Innenproduktraum $\left(X,\left\langle \cdot,\cdot\right\rangle \right)$ sei $M\subseteq X$ eine konvexe, nichtleere Menge. Für $m\in M$ und $x\in X$ gilt dann\[ m\in\mathcal{P}_{M}\left(x\right)\quad\Leftrightarrow\quad\left(\forall k\in M\quad\left\langle x-m,k-m\right\rangle \leq0\right).\] \end{thm} \begin{proof} \begin{description} \item [$\left(\Rightarrow\right)$]Für $k\in M$ und $0<\lambda<1$ ist $\left(1-\lambda\right)m+\lambda k\in M$, denn $M$ ist konvex. Wegen $m\in\mathcal{P}_{M}\left(x\right)$ gilt\begin{eqnarray*} 0 & \leq & \underbrace{\left\Vert x-\lambda k-\left(1-\lambda\right)m\right\Vert ^{2}}_{\left\Vert x-m+\lambda\left(m-k\right)\right\Vert ^{2}}-\left\Vert x-m\right\Vert ^{2}\\ & = & \left\Vert x-m\right\Vert ^{2}+\lambda^{2}\left\Vert m-k\right\Vert ^{2}+2\lambda\left\langle x-m,m-k\right\rangle -\left\Vert x-m\right\Vert ^{2}\\ & = & -2\lambda\left\langle x-m,k-m\right\rangle +\lambda^{2}\left\Vert m-k\right\Vert ^{2}.\end{eqnarray*} Also folgt für $\lambda\searrow0$\[ \left\langle x-m,k-m\right\rangle \leq\frac{1}{2}\lambda\left\Vert m-k\right\Vert ^{2}\searrow0.\] \item [$\left(\Leftarrow\right)$]Für alle $k\in M$ gilt\begin{eqnarray*} 0\leq\left\Vert x-m\right\Vert ^{2} & = & \left\langle x-m,x-k\right\rangle +\underbrace{\left\langle x-m,k-m\right\rangle }_{\leq0}\\ & \leq & \left\Vert x-m\right\Vert \left\Vert x-k\right\Vert \end{eqnarray*} Also folgt $x=m$ oder $\left\Vert x-m\right\Vert \leq\left\Vert x-k\right\Vert $, d.h. $m\in\mathcal{P}_{M}\left(x\right)$.\qedhere \end{description} \end{proof} \begin{thm} [\Cebysev-Eigenschaft]\label{thm:CebysevEigenschaft}\index{Cebysev-Eigenschaft}In einem Hilbert-Raum $\left(X,\left\langle \cdot,\cdot\right\rangle \right)$ sei $M\subset X$ eine konvexe, abgeschlossene, nichtleere Menge. Dann ist für $x\in X$ die Menge $\mathcal{P}_{M}\left(x\right)$ der Bestapproximierenden einelementig und die Abbildung $P_{M}:X\rightarrow X$, $x\mapsto P_{M}\left(x\right)$ mit $\left\{ P_{M}\left(x\right)\right\} =\mathcal{P}_{M}\left(x\right)$ ist idempotent, nicht-expansiv und monoton. \end{thm} \begin{remark} $\mathcal{P}_{M}$ heißt \emph{\Cebysev-Operator}\index{Cebysev-Operator} oder \emph{Bestapproximations-Operator}\index{Bestapproximierende-Operator} zur Menge $M$. \end{remark} \begin{proof} % \begin{description} \item [\textmd{\emph{Eindeutigkeit:}}]Für $x\in X$, $m_{1},m_{2}\in\mathcal{P}_{M}\left(x\right)$ folgt aus dem Charakterisierungssatz \ref{thm:Charakterisierungssatz}\begin{eqnarray*} \left\langle x-m_{1},m_{2}-m_{1}\right\rangle & \leq & 0\\ \textrm{und }\left\langle x-m_{2},m_{1}-m_{2}\right\rangle & \leq & 0.\end{eqnarray*} Deren Summe zeigt\[ \left\Vert m_{2}-m_{1}\right\Vert ^{2}=\left\langle x-m_{1}+m_{2}-x,m_{2}-m_{1}\right\rangle \leq0,\] also $\left\Vert m_{2}-m_{1}\right\Vert \leq0$, d.h. $m_{1}=m_{2}$. \item [\textmd{\emph{Existenz:}}]Für $j\in\mathbb{N}$, $j>0$, und $d:=\dist\left(x,M\right)\geq0$ existiert ein $m_{j}\in M$ mit\[ d^{2}\leq\left\Vert x-m_{j}\right\Vert ^{2}\leq d^{2}+1/j\] \noindent Aus der Parallelogrammgleichung folgt dann für $j,k\in\mathbb{N}$ \begin{eqnarray*} \left\Vert m_{j}-m_{k}\right\Vert ^{2}+\left\Vert m_{j}-x+m_{k}-x\right\Vert ^{2} & = & 2\left\Vert m_{j}-x\right\Vert ^{2}+2\left\Vert m_{k}-x\right\Vert ^{2}\\ & \leq & 4d^{2}+2/j+2/k\end{eqnarray*} Da $\frac{m_{j}+m_{k}}{2}\in M$ ist\[ 4d^{2}\leq4\left\Vert x-\frac{m_{j}+m_{k}}{2}\right\Vert ^{2}=\left\Vert 2x-m_{j}-m_{k}\right\Vert ^{2}\] und so\[ \left\Vert m_{j}-m_{k}\right\Vert ^{2}\leq2/j+2/k.\] Also ist $\left(m_{j}\right)$ Cauchy-Folge in $M$. Mit der Abgeschlossenheit von $M$ im Hilbert-Raum $X$ konvergiert $\left(m_{j}\right)\rightarrow m$ in $X$ für ein $m\in M$. Nach Wahl von $m_{j}$ folgt\[ \left\Vert x-m\right\Vert \leq\left\Vert x-m_{j}\right\Vert +\left\Vert m-m_{j}\right\Vert \leq\sqrt{d^{2}+1/j}+\left\Vert m-m_{j}\right\Vert \xrightarrow{j\rightarrow\infty}d,\] also $\left\Vert x-m\right\Vert =d$. \item [\textmd{\emph{Idempotenz:}}]$P_{M}^{2}=P_{M}$ ist klar. \item [\textmd{\emph{Monotonie:}}]$0\leq\left\langle P_{M}\left(x\right)-P_{M}\left(y\right),x-y\right\rangle $ für $x,y\in X$. Für $x,y\in X$ gilt nach dem Charakterisierungssatz \ref{thm:Charakterisierungssatz}\begin{eqnarray*} \left\langle P_{M}\left(x\right)-x,P_{M}\left(x\right)-P_{M}\left(y\right)\right\rangle & \leq & 0\\ \textrm{und }\left\langle P_{M}\left(y\right)-y,P_{M}\left(y\right)-P_{M}\left(x\right)\right\rangle & \leq & 0.\end{eqnarray*} Die Summe zeigt\[ 0\leq\left\langle P_{M}\left(y\right)-P_{M}\left(x\right),P_{M}\left(y\right)-P_{M}\left(x\right)\right\rangle \leq\left\langle y-x,P_{M}\left(y\right)-P_{M}\left(x\right)\right\rangle .\] \item [\textmd{\emph{Nicht-Expansivität:}}]Mit der Cauchy-Ungleichung folgt in der vorhergegangenen Abschätzung weiter\[ \left\Vert P_{M}\left(y\right)-P_{M}\left(x\right)\right\Vert \leq\left\Vert y-x\right\Vert .\] Also ist $P_{M}$ Lipschitzstetig mit Lipschitz-Konstante $\leq1$, d.h. $P_{M}$ ist nicht-expansiv.\qedhere \end{description} \end{proof} \section{Orthogonale Komplemente} In einem Hilbert-Raum $\left(X,\left\langle \cdot,\cdot\right\rangle \right)$ sei $U$ ein linearer, abgeschlossener Teilraum von $X$ (also $U\neq\emptyset$, $U$ konvex und abgeschlossen). Dann ist \[ P:=P_{U}\] eine lineare Projektion und orthogonal, d.h. für alle $x\in X$ ist\[ x-Px\bot U.\] Weiter ist \[ Q:=\id-P\] eine orthogonale Projektion auf das orthogonale Komplement\index{orthogonales Komplement} \[ U^{\bot}:=\left\{ x\in X\left|x\bot U\right.\right\} \] von $U$. Insbesondere ist $U^{\bot}$ abgeschlossen. Es ist $\Bild\left(P\right)=U$ und $\Bild\left(Q\right)=U^{\bot}$. Für alle $x\in X$ gilt \[ x=Px+Qx\] mit $Px\bot Qx$. \section{Riesz-Darstellungssatz} \begin{defn} [Dualraum, Dualnorm]Für einen normierten linearen Raum $\left(X,\left\Vert \cdot\right\Vert \right)$ heißt\[ X^{*}:=\left\{ f:X\rightarrow\mathbb{R}\left|f\textrm{ ist linear und stetig}\right.\right\} \] \emph{Dualraum} \index{Dualraum}zu $X$ und \[ \left\Vert \cdot\right\Vert _{X^{*}}:X^{*}\rightarrow\mathbb{R},\qquad f\mapsto\sup_{\left\Vert x\right\Vert \leq1}f\left(x\right)\] heißt \emph{Dualnorm}\index{Dualnorm}. \end{defn} \begin{remark} $\left(X^{*},\left\Vert \cdot\right\Vert _{X^{*}}\right)$ ist ein normierter linearer Raum. \end{remark} \begin{thm} [Riesz-Darstellung]\label{thm:RieszDarstellung}Im Hilbert-Raum $\left(X,\left\langle \cdot,\cdot\right\rangle \right)$ ist \[ \Lambda:X\rightarrow X^{*},\qquad x\mapsto\left\langle x,\cdot\right\rangle \] ein Normisomorphismus (d.h. $\Lambda$ ist eine lineare Bijektion mit $\left\Vert \Lambda x\right\Vert _{X^{*}}=\left\Vert x\right\Vert _{X}$ für alle $x\in X$). \end{thm} \begin{proof} [Beweis der Surjektivität]Für $f\in X^{*}$ ist ein $x\in X$ mit $\left\langle x,\cdot\right\rangle =f$ zu finden. Für $f=0$ ist $x=0$. Sonst ist $U:=\ker f$ abgeschlossen in $X$ und $U\neq X$. Also existiert ein $z\in U^{\bot}\setminus\left\{ 0\right\} $ und das Element \[ x:=\frac{f\left(z\right)}{\left\Vert z\right\Vert ^{2}}z\in U^{\bot}\] erfüllt für alle $y\in X$\begin{eqnarray*} \left(\Lambda x\right)\left(y\right)=\left\langle x,y\right\rangle & = & \left\Vert z\right\Vert ^{-2}f\left(z\right)\left\langle z,y\right\rangle \\ & = & \left\Vert z\right\Vert ^{-2}\left\langle z,f\left(z\right)y\right\rangle \qquad\textrm{und }z\bot U\\ & = & \left\Vert z\right\Vert ^{-2}\left\langle z,f\left(y\right)z\right\rangle \quad\textrm{da }f\left(z\right)y-f\left(y\right)z\in U\\ & = & f\left(y\right).\end{eqnarray*} Also ist $\Lambda x=f$. Übrige Beweisdetails als Übungsaufgabe. \end{proof} \section{Sobolev-Räume in einer Dimension} Konstruktion geeigneter Hilberträume Im ganzen Abschnitt sei $\Omega=\left(a,b\right)$ für $-\infty0\,\exists\delta>0 & \forall n\in\mathbb{N}\,\forall a0$ wähle man ein z.B. ein Polynom $g$ mit \[ \left\Vert f'-g\right\Vert _{p}<\varepsilon.\] Dann definiert\[ G\left(x\right):=f\left(a\right)+\int_{a}^{x}g\left(y\right)dy\] ein Polynom mit $G'=g$ fast überall und\begin{eqnarray*} \left|f\left(x\right)-G\left(x\right)\right| & = & \left|f\left(a\right)+\int_{a}^{x}f'\left(y\right)dy-f\left(a\right)-\int_{a}^{x}g\left(y\right)dy\right|\\ & \leq & \int_{a}^{x}\left|f'\left(y\right)-g\left(y\right)\right|dy\\ & \leq & \underbrace{\left|x-a\right|^{\frac{1}{q}}}_{\leq\left(b-a\right)^{\frac{1}{q}}}\,\left\Vert f'-g\right\Vert _{p}\qquad\textrm{für }\frac{1}{p}+\frac{1}{q}=1.\end{eqnarray*} Also folgt\[ \left\Vert f-G\right\Vert _{p}\leq\underbrace{\left(b-a\right)^{\frac{1+\frac{1}{q}}{p}}}_{=:c_{1}}\,\underbrace{\left\Vert f'-g\right\Vert _{p}}_{<\varepsilon}\leq c_{1}\varepsilon\] und weiter\[ \left\Vert f-G\right\Vert _{1,p}\leq c_{2}\,\varepsilon.\qedhere\] \end{proof} \begin{remark} Zu $f\in W_{0}^{1,p}$ ist $G\in W_{0}^{1,p}$ konstruierbar. \end{remark} \section{\label{sub:1DRWP}Eindimensionale Randwertprobleme} Der Riesz-Darstellungssatz zeigt: Es existiert genau eine schwache Lösung. In diesem Abschnitt sei $\Omega=\left(a,b\right)$ mit $-\infty0$,\[ \varphi_{\varepsilon}\left(x\right):=\int_{\alpha}^{\beta}\eta_{\varepsilon}\left(x-y\right)dy\qquad\textrm{für }x\in\left(a,b\right).\] Die Funktion $\eta_{\varepsilon}$ heißt der Standard-Mollifier in $C_{c}^{\infty}\left(\mathbb{R}\right)$ mit $\supp\eta_{\varepsilon}=\left[-\varepsilon,\varepsilon\right]$,\[ \eta_{\varepsilon}\left(x\right):=\begin{cases} {\displaystyle \varepsilon^{-1}c\exp\left(\frac{1}{\left(x/\varepsilon\right)^{2}-1}\right)} & \textrm{falls }\left|x\right|<\varepsilon,\\ 0 & \textrm{falls }\left|x\right|\geq\varepsilon,\end{cases}\] wobei die positive Konstante $c$ so gewählt ist, daß $\int_{\mathbb{R}}\eta_{\varepsilon}\left(x\right)dx=1$ gilt. Man rechnet nach\[ \varphi_{\varepsilon}\left(x\right)\xrightarrow{\varepsilon\searrow0}\chi_{\left(\alpha,\beta\right)}\left(x\right)\qquad\textrm{für fast alle }x\in\Omega\] und\[ 0=\int_{a}^{b}g\left(x\right)\varphi_{\varepsilon}\left(x\right)dx\xrightarrow{\varepsilon\searrow0}\int_{\alpha}^{\beta}g\left(x\right)dx.\] Also $\int_{\alpha}^{\beta}g\left(x\right)dx=0$ für alle $\alpha,\beta\in\Omega$. Da $\alpha$ und $\beta$ beliebig gewählt waren, verschwindet $g$ in allen Lebesgue-Punkten. Also ist $g=0$ fast überall. \end{proof} \begin{thm} [Existenz und Eindeutigkeit schwacher L\"osungen]\label{thm:ExEindSchwLsg}Sofern \[ \lambda>-\frac{\pi^{2}}{\left(b-a\right)^{2}}\] existiert genau eine schwache Lösung $u$ in $V$. \end{thm} \begin{remark} Diese schwache Lösung $u$ ist dann in der Tat auch eine starke Lösung, d.h. $u\in W^{2,1}\left(a,b\right)$, nach dem Regularitätssatz \vref{thm:H=F6hereRegularit=E4t}. \end{remark} \begin{proof} Da $F:=\left(f,\cdot\right)_{L^{2}\left(\Omega\right)}\in V^{*}=:H^{-1}\left(\Omega\right)$ genügt es mit dem Riesz-Darstellungssatz (Satz\vref{thm:RieszDarstellung}) nachzuweisen, daß \begin{enumerate} \item $a$ ein Skalarprodukt ist und \item dessen induzierte Norm $\left\Vert \cdot\right\Vert _{a}$ äquivalent zu $\left\Vert \cdot\right\Vert _{1,2}$ ist. \end{enumerate} Nach Definition ist\[ a\left(v,w\right):=\left(v',w'\right)+\lambda\left(v,w\right)\qquad\textrm{für alle }v,w\in V.\] \begin{enumerate} \item Bilinearität und Symmetrie von $a$ sind direkt einzusehen. Die Positivität und Definitheit folgen mit der Friedrichs-Ungleichung ((\ref{eq:Friedrichs}) auf Seite \pageref{eq:Friedrichs}: $\left(\frac{\pi}{b-a}\right)^{2}\left\Vert v\right\Vert _{2}^{2}\leq\left\Vert v'\right\Vert _{2}^{2}$):\[ \underbrace{\left(\lambda+\left(\frac{\pi}{b-a}\right)^{2}\right)}_{>0}\left\Vert v\right\Vert _{2}^{2}\leq\left\Vert v'\right\Vert _{2}^{2}+\lambda\left\Vert v\right\Vert _{2}^{2}=a\left(v,v\right),\] also $a\left(v,v\right)\geq0$ und falls $a\left(v,v\right)=0$, so folgt $\left\Vert v\right\Vert _{2}=0$, also $v=0$. \item $a\left(v,v\right)\leq\max\left\{ 1,\lambda\right\} \left\Vert v\right\Vert _{1,2}^{2}$ und wie oben folgt für jedes $0<\mu<1$\[ a\left(v,v\right)\geq\underbrace{\left(\lambda+\mu\left(\frac{\pi}{b-a}\right)^{2}\right)}_{>0\textrm{ für }\mu\in\left(0,1\right)\textrm{ groß genug}}\left\Vert v\right\Vert _{2}^{2}+\left(1-\mu\right)\left\Vert v'\right\Vert _{2}^{2}\gtrsim\left\Vert v\right\Vert _{1,2}^{2}\] ({}``$A\lesssim B$'' bezeichnet {}``$A\leq C\cdot B$'' mit einer universellen Konstante $C>0$).\qedhere \end{enumerate} \end{proof} \begin{remark} Der Beweis benutzt $C_{F}=\frac{b-a}{\pi}$. Jede Schranke von $C_{F}$ führt auf ein $\lambda_{0}<0$, so daß $a$ für $\lambda>\lambda_{0}$ ein Skalarprodukt mit $\left\Vert \cdot\right\Vert _{a}\approx\left\Vert \cdot\right\Vert _{1,2}$ definiert. ({}``$A\approx B$'' bezeichnet {}``$A\lesssim B\lesssim A$''). \end{remark} % \begin{remark} Die Konstante $-\frac{\pi^{2}}{\left(b-a\right)^{2}}$ im Satz \ref{thm:ExEindSchwLsg} ist scharf in dem Sinne, daß für jedes $\mu\in\mathbb{R}$ \[ u\left(x\right):=\mu\sin\left(\frac{x-a}{b-a}\pi\right)\] eine starke Lösung von (\ref{eq:RWPstark}) mit $\lambda=-\frac{\pi^{2}}{\left(b-a\right)^{2}}$ und $f\equiv0$ ist (also die Eindeutigkeit verloren geht). \end{remark} Jede schwache Lösung ist \underbar{hier} sogar starke Lösung: \begin{thm} [Höhere Regularität]\index{Höhere Regularität}\label{thm:H=F6hereRegularit=E4t}Für $\lambda\in\mathbb{R}$ und $u\in V$ gelte \[ a\left(u,v\right):=\left(u',v'\right)_{L^{2}\left(\Omega\right)}+\lambda\left(u,v\right)_{L^{2}\left(\Omega\right)}\stackrel{!}{=}\left(f,v\right)\qquad\textrm{für alle }v\in V.\] Dann gilt das {}``Shift-Theorem''\index{Shift-Theorem} :\[ f\in H^{m}\left(\Omega\right),m\in\mathbb{N}_{0}\quad\Rightarrow\quad u\in H^{m+2}\left(\Omega\right).\] \end{thm} \begin{proof} Mit $g:=f-\lambda u\in L^{2}\left(\Omega\right)$ gilt\[ \left(u',v'\right)=\left(g,v\right)\qquad\textrm{für alle }v\in V.\] Zu $g$ definiere man $G\in H^{1}\left(\Omega\right)$ vermöge\[ G\left(x\right):=\int_{a}^{x}g\left(y\right)dy-\underbrace{\frac{1}{b-a}\int_{a}^{b}\int_{a}^{y}g\left(z\right)dzdy}_{\textrm{Integralmittel von }x\mapsto\int_{a}^{x}g\left(z\right)dz}\qquad\textrm{für alle }x\in\Omega.\] Dann ist $G'=g$ und $\int_{a}^{b}G\left(x\right)dx=0$. Die Definition \[ v\left(x\right):=u\left(x\right)+\int_{a}^{x}G\left(y\right)dy\qquad\textrm{für alle }x\in\Omega\] ergibt ein $v\in V$ mit $v'=u'+G$ und \[ \left(u',u'+G\right)=\left(u',v'\right)=\left(g,v\right)=\left(G',v\right).\] Mit partieller Integration folgt\[ \left(u',u'+G\right)=-\left(G,v'\right)=-\left(G,G+u'\right)\] und so insgesamt \[ \left(u'+G,u'+G\right)_{L^{2}\left(\Omega\right)}=0.\] Also ist $u'=-G\in H^{1}\left(\Omega\right)$. Dies ist die Behauptung für $m=0$. Folglich gilt die starke Form $-u''+\lambda u=f$ und sukzessives Weiterdifferenzieren liefert die Behauptung für $m=1,2,3,\ldots$ \end{proof} \begin{remark} Eigenvektoren sind beliebig glatt! \end{remark} % \begin{remark} Für {}``glatte Gebiete'' gilt ein Shift-Theorem auch in höheren Raumdimensionen, aber mit anderem Beweis. \end{remark} \section{\label{sub:1D-FEM}Eindimensionale Finite Elemente Methode} \begin{ziel*} Ritz-Projektion auf endlich-dimensionale Teilräume. \end{ziel*} \begin{defn} [$P_k$-FEM]\index{$P_k$-FEM}\index{FER}\index{FEM} \begin{enumerate} \item Zu $\Omega=\left(0,1\right)$ und einer \emph{Triangulierung}\index{Triangulierung}\[ \mathcal{T}=\left\{ I_{j}\left|j=1,\ldots,m\right.\right\} \] in abgeschlossene Intervalle $I_{j}=\left[z_{j-1},z_{j}\right]$ bzgl. der \emph{Knoten\index{Knoten}} $0=z_{0}-\frac{\pi^{2}}{\left(b-a\right)^{2}}$, Satz \ref{thm:ExEindSchwLsg}) und $F\in V^{*}$ und dem $P_{k}$-FER $V_{h}$ bzgl. der Triangulierung $\mathcal{T}$ heißt ein $u_{h}\in V_{h}$ \emph{diskrete Lösung} (oder FE-Lösung), falls\begin{equation} a\left(u_{h},v_{h}\right)=F\left(v_{h}\right)\qquad\textrm{für alle }v_{h}\in V_{h}.\label{eq:diskretesRWP}\end{equation} \item Der Übergang von (\ref{eq:kontinuierlichesRWP}) nach (\ref{eq:diskretesRWP}) heißt hier speziell \emph{Galerkin-Diskretisierung}\underbar{\index{Galerkin-Diskretisierung}} und für den FER $V_{h}$ auch \emph{FEM}. (\ref{eq:kontinuierlichesRWP}) heißt \emph{kontinuierliches}\index{Problem!kontinuierlich}, (\ref{eq:diskretesRWP}) heißt \emph{diskretes Problem}\underbar{\index{Problem!diskret}} mit kontinuierlicher bzw. diskreter Lösung. \end{enumerate} \end{defn} \begin{remark} Anstatt der Bezeichnung Triangulierung findet man in der Literatur auch Partition, Netz, Gitter, mesh, grid, triangulation. Vorsicht: Details können anders sein. \end{remark} \begin{thm} [Ritz-Projektion]\renewcommand{\labelenumi}{(\alph{enumi})}~ \begin{enumerate} \item (\ref{eq:kontinuierlichesRWP}) und (\ref{eq:diskretesRWP}) haben jeweils eindeutige Lösungen. \item $u_{h}$ ist die Bestapproximierende zu $u$ im Hilbert-Raum $\left(V,a\right)$. \end{enumerate} \end{thm} \begin{defn} [Ritz-Projektion]Die Abbildung $P_{V_{h}}:V\rightarrow V_{h}$, $u\mapsto u_{h}$ heißt \underbar{Ritz-Projektion}\index{Ritz-Projektion}. \end{defn} \begin{remark} Die Gleichheit $\left\Vert u-u_{h}\right\Vert _{a}=\min_{v_{h}\in V_{h}}\left\Vert u-v_{h}\right\Vert _{a}$ heißt in der FE-Literatur auch Cea-Lemma\index{Cea-Lemma}. \end{remark} \begin{proof} \renewcommand{\labelenumi}{(\alph{enumi})} \begin{enumerate} \item $V_{h}$ ist als endlichdimensionaler Vektorraum ein vollständiger Unterraum von $V$, also ist $\left(V_{h},a\left|_{V_{h}\times V_{h}}\right.\right)$ ein Hilbert-Raum. Der Riesz-Darstellungssatz\vref{thm:RieszDarstellung} zeigt: Es existiert genau eine Riesz-Darstellung $u_{h}$ von $F\left|_{V_{h}}\right.\in V_{h}^{*}$. \item Für alle $v_{h}\in V_{h}$ ist $a\left(u_{h},v_{h}\right)=F\left(v_{h}\right)=a\left(u,v_{h}\right)$, d.h. $u-u_{h}\bot_{a}V_{h}$. Damit folgt 2. aus dem Charakterisierungssatz\vref{thm:Charakterisierungssatz} (jetzt für Unterräume).\qedhere \end{enumerate} \end{proof} \begin{example*} [uniforme $P_1$-FEM]Es sei $k=1$, $\dim V_{h}=n$, $h=\left(n+1\right)^{-1}$, $n\in\mathbb{N}$, $n\geq1$ und\[ z_{j}:=jh\quad\textrm{für }j=0,\ldots,n+1.\] Man definiere $\varphi_{j}\in V_{h}$ vermöge \[ \varphi_{j}\left(z_{k}\right):=\delta_{jk}:=\begin{cases} 1 & \textrm{für }j=k,\\ 0 & \textrm{sonst},\end{cases}\] d.h. \[ \varphi_{j}\left(z\right)=\begin{cases} \frac{z-z_{j-1}}{h} & \textrm{für }z_{j-1}\leq z1,\\ -\frac{1}{h} & \textrm{falls }\left|j-k\right|=1,\\ \frac{2}{h} & \textrm{falls }j=k,\end{cases}\] \[ A=\left(a\left(\varphi_{j},\varphi_{k}\right)\right)_{j,k}=\frac{1}{h}\left(\begin{array}{cccc} 2 & -1\\ -1 & \ddots & \ddots\\ & \ddots & \ddots & -1\\ & & -1 & 2\end{array}\right)\] und\[ b_{j}=F\left(\varphi_{j}\right)=\int_{\Omega}f\left(x\right)\varphi_{j}\left(x\right)dx\approx f\left(z_{j}\right)h,\] also\[ \left(\begin{array}{cccc} 2 & -1\\ -1 & \ddots & \ddots\\ & \ddots & \ddots & -1\\ & & -1 & 2\end{array}\right)x=hb\approx h^{2}\left(\begin{array}{c} f\left(z_{1}\right)\\ \vdots\\ \vdots\\ f\left(z_{n}\right)\end{array}\right).\] \end{example*} \begin{defn} [Nodale Interpolation, nodale Basis]Für ein Triangulierung $\mathcal{T}$ von $\left(0,1\right)=\Omega$ in abgeschlossene Intervalle und die $P_{1}$-FEM heißt der Operator\[ I:C\left[0,1\right]\rightarrow V_{h},\quad f\mapsto\sum_{j=1}^{N}f\left(x_{j}\right)\varphi_{j}\] \emph{nodale Interpolation}\index{nodale Interpolation}. Dabei sind $z_{0}=00$ auf einer kompakten Teilmenge $S:=\textrm{supp}v=\overline{\left\{ v\neq0\right\} }\Subset\left(\alpha,\beta\right)$, daß\[ u-\chi\leq-\delta<0.\] Also existiert ein $\varepsilon>0$ mit\[ u-\chi\leq-\varepsilon\left|v\right|\leq\pm\varepsilon v\qquad\left(v\equiv0\textrm{ auf }\mathbb{R}\setminus S\right)\] Dann ist $u\pm\varepsilon v\in K$ und\begin{eqnarray*} F\left(\pm\varepsilon v\right) & \leq & a\left(u,\pm\varepsilon v\right)\\ \Rightarrow\, F\left(v\right) & = & a\left(u,v\right)\quad\textrm{für alle }v\in C_{c}^{1}\left(I\right)\\ \Rightarrow\, F & = & a\left(u,\cdot\right)\quad\textrm{in }H^{-1}\left(I\right):=\left(H_{0}^{1}\left(I\right)\right)^{*}.\end{eqnarray*} Nach dem Regularitätssatz\vref{thm:H=F6hereRegularit=E4t} folgt $u\in H^{2}\left(I\right)$. Zudem ist $-u''\left|_{I}\right.=f\left|_{I}\right.$. \end{proof} \begin{remark} Für glattes $\chi$ ist tatsächlich $u\in H^{2}\left(\Omega\right)$. Dann bedeutet $\rho\geq0$ punktweise, daß $f+u''\geq0$ fast überall, und es gelten die punktweisen Kuhn-Tucker-Bedingungen (Komplementaritätsbedingungen)\[ 0\leq\chi-u,\quad0\leq f+u'',\quad\left(\chi-u\right)\left(f+u''\right)\leq0.\] \end{remark} \begin{example*} Deutung: $\chi$ beschreibt einen Stempel und $u$ die heruntergedrückte Membran. \begin{enumerate} \item Für $\Omega=\left(-1,1\right)$, $V=H_{0}^{1}\left(\Omega\right)$, $f\equiv0$, $u_{f}\equiv0\not\in K$ und \begin{minipage}[c]{0.50\columnwidth}% \[ \chi\left(x\right)=\left|x\right|-\frac{1}{2}\] definiert\[ u\left(x\right)=\frac{1}{2}\left(\left|x\right|-1\right)\] eine Funktion mit\begin{eqnarray*} \left\{ \chi=u\right\} & = & \left\{ 0\right\} ,\\ u'\left(x\right) & = & \frac{1}{2}\textrm{sign}\left(x\right).\end{eqnarray*} \end{minipage}% \begin{minipage}[c]{0.50\columnwidth}% \begin{flushright}\includegraphics[% width=1.0\columnwidth]{stempel.eps}\end{flushright}\end{minipage}% Für dieses $u\in K$ und jedes $v\in K$ gilt\begin{eqnarray*} a\left(u,v-u\right) & = & -\frac{1}{2}\int_{-1}^{0}\left(v'+\frac{1}{2}\right)dx+\frac{1}{2}\int_{0}^{1}\left(v'-\frac{1}{2}\right)dx\\ & = & -\frac{1}{2}-\frac{1}{2}v\left(0\right)+\frac{1}{2}\underbrace{v\left(-1\right)}_{=0}+\frac{1}{2}\underbrace{v\left(1\right)}_{=0}-\frac{1}{2}v\left(0\right)\\ & = & -\underbrace{v\left(0\right)}_{\leq-\frac{1}{2}}-\frac{1}{2}\geq0=F\left(v-u\right).\end{eqnarray*} Also ist $u$ \underbar{die} Lösung.\qed \item Für $\Omega=\left(0,1\right)$ und $\chi\left(x\right)=x^{2}-lx+\frac{l^{2}}{8}$, $f\equiv0$ bestimme man die Lösung $u$ (und beweise, daß es eine ist). \end{enumerate} \end{example*} \subsection{$P_{1}$-Diskretisierung} Für den FER $V_{h}$ wie in §\ref{sub:1D-FEM} und $\chi_{h}\in P_{1}\left(\mathcal{T}\right)\cap C^{0}\left[\Omega\right]$, z.B. $\chi_{h}\left(z\right):=\chi\left(z\right)$ für alle Knoten $z\in\mathcal{N}$, sei\[ K_{h}:=\left\{ v_{h}\in V_{h}\left|\forall z\in\mathcal{N},v_{h}\left(z\right)\leq\chi_{h}\left(z\right)\right.\right\} .\] Sprechweise: \emph{Konforme FEM}\index{FEM!konform}, falls $K_{h}\subseteq K$, und sonst \emph{nicht-konforme FEM}. Das \emph{diskrete Problem} ergibt sich durch Projektion auf $K_{h}$, also analog zum kontinuierlichen Fall. Sei weiterhin $K_{h}\neq\emptyset$ vorausgesetzt ($K_{h}=\emptyset$ ist möglich, sei hier aber ausgeschlossen). Es existiert genau eine Lösung $u_{h}\in K_{h}$ mit\begin{subequations}\begin{eqnarray} \left\Vert u_{f}-u_{h}\right\Vert _{a} & \leq & \left\Vert u_{f}-v_{h}\right\Vert _{a}\qquad\textrm{für alle }v_{h}\in K_{h};\label{eq:VarUnglBestApproxDiskret}\\ F\left(v_{h}-u_{h}\right) & \leq & a\left(u_{h},v_{h}-u_{h}\right)\quad\textrm{für alle }v_{h}\in K_{h};\label{eq:VarUnglVarUnglDiskret}\\ E\left(u_{h}\right) & = & \min E\left(K_{h}\right).\label{eq:VarUnglEnergieFunktionalDiskret}\end{eqnarray} \end{subequations}Mit der Matrix $A_{jk}:=a\left(\varphi_{j},\varphi_{k}\right)$ und dem Vektor $b_{j}:=F\left(\varphi_{j}\right)$ aus §\ref{sub:1D-FEM} führt (\ref{eq:VarUnglVarUnglDiskret}) zu\[ b\cdot\left(y-x\right)\leq\left(Ax\right)\cdot\left(y-x\right)\] für Koeffizienten $y_{j}:=v_{h}\left(z_{j}\right)\leq\chi\left(z_{j}\right)=:\chi_{j}$, $x_{j}:=u_{h}\left(z_{j}\right)$. Das Problem (\ref{eq:VarUnglEnergieFunktionalDiskret}) heißt in der Optimierung QP oder quadratisches Problem:\[ \min_{\substack{y_{j}\leq\chi\left(z_{j}\right)\\ j=1,\ldots,n} }\frac{1}{2}y\cdot Ay-b\cdot y\] Zur Lösung gibt es Standardsoftware in MATLAB, z.B. Verfahren von Wolfe oder Einzelschrittverfahren. \begin{thm} Sofern $Iu\in K_{h}$ und $u_{h}\in K$ (also im wesentlichen im konformen Fall) folgt\[ \left\Vert u-u_{h}\right\Vert _{a}\leq a\left(u_{f}-Iu_{f},u-Iu\right)^{\frac{1}{2}}\leq\left\Vert \frac{h}{\pi}f\right\Vert _{L^{2}\left(\Omega\right)}=O\left(\left\Vert h\right\Vert _{L^{\infty}}\right)\] \end{thm} \begin{proof} Für alle $v\in K$ und alle $v_{h}\in K_{h}$ ist\begin{eqnarray*} a\left(u,u-v\right) & \leq & F\left(u-v\right)=a\left(u_{f},u-v\right),\\ a\left(u_{h},u_{h}-v_{h}\right) & \leq & F\left(u_{h}-v_{h}\right)=a\left(u_{f},u_{h}-v_{h}\right).\end{eqnarray*} und so\begin{eqnarray*} \left\Vert u-u_{h}\right\Vert _{a}^{2} & = & a\left(u_{h},u_{h}-v_{h}\right)+a\left(u,u-v\right)+a\left(u_{h},v_{h}-u\right)+a\left(u,v-u_{h}\right)\\ & \leq & a\left(u_{f},u_{h}-v_{h}\right)+a\left(u_{f},u-v\right)+a\left(u_{h},v_{h}-u\right)+a\left(u,v-u_{h}\right)\\ & = & F\left(u_{h}\right)-F\left(v_{h}\right)+F\left(u\right)-F\left(v\right)+a\left(u_{h},v_{h}-u\right)+a\left(u,v-u_{h}\right)\\ & = & a\left(u,v-u_{h}\right)-F\left(v-u_{h}\right)+a\left(u_{h},v_{h}-u\right)-F\left(v_{h}-u\right).\end{eqnarray*} Also ist\begin{eqnarray*} \left\Vert u-u_{h}\right\Vert _{a}^{2} & \leq & \underbrace{\min_{v\in K}\left(a\left(u,v-u_{h}\right)-F\left(v-u_{h}\right)\right)}_{\leq0,\textrm{ da }v=u_{h}\in K\textrm{ möglich}}\\ & & +\underbrace{\min_{v_{h}\in K_{h}}\left(a\left(u_{h},v_{h}-u\right)-F\left(v_{h}-u\right)\right)}_{\leq a\left(u_{h},Iu-u\right)-F\left(Iu-u\right),\textrm{ denn }Iu\in K_{h}}\\ & \leq & 0+a\left(u_{f}-u_{h},u-Iu\right).\end{eqnarray*} Für die 1D FEM hier ist $u-Iu\bot_{a}V_{h}$ (Beweis als Aufgabe!). Dann ist $u_{h}-Iu_{f}\bot_{a}u-Iu$ und damit\[ a\left(u_{f}-u_{h},u-Iu\right)=a\left(u_{f}-Iu_{f},u-Iu\right).\] Da nun auch $Iu_{f}\bot_{a}u-Iu$ gilt, erhalten wir\[ a\left(u_{f}-Iu_{f},u-Iu\right)=a\left(u_{f},u-Iu\right)=\left(f,u-Iu\right).\] Die Anwendung einer Friedrichs-Ungleichung liefert\begin{eqnarray*} \left(f,u-Iu\right) & \leq & \left\Vert \frac{h}{\pi}f\right\Vert _{L^{2}\left(\Omega\right)}\,\left\Vert \left(u-Iu\right)'\right\Vert _{L^{2}\left(\Omega\right)}\\ & = & \left\Vert \frac{h}{\pi}f\right\Vert _{L^{2}\left(\Omega\right)}\,\left\Vert u-Iu\right\Vert _{a}\\ & \leq & \left\Vert \frac{h}{\pi}f\right\Vert _{L^{2}\left(\Omega\right)}\,\left\Vert u-u_{h}\right\Vert _{a},\end{eqnarray*} da $\left\Vert u-Iu\right\Vert _{a}=\min_{v_{h}\in V_{h}}\left\Vert u-v_{h}\right\Vert $. Benutzen wir nun die Young-Ungleichung% \footnote{Für $10\] gilt. (Damit ist auch garantiert, daß keine Entartung auftreten kann.) \end{convention*} Im Fall $n=2$ sind die Ecken dann gegen den Uhrzeigersinn zu nummerieren, um der Konvention zu genügen. \begin{remark} Das $n$-dimensionale Volumen von $T$ ist\[ \left|T\right|=\frac{1}{n!}\det\left(\left[\begin{array}{ccc} P_{1} & \cdots & P_{n+1}\\ 1 & \cdots & 1\end{array}\right]\right)>0.\] Für nichtentartete Punkte $P_{1},\ldots,P_{n+1}\in\mathbb{R}^{n}$ gilt\[ \left(\lambda_{1}\left(x\right),\ldots,\lambda_{n+1}\left(x\right)\right)=\Lambda\left(x\right)=\left[\begin{array}{ccc} P_{1} & \cdots & P_{n+1}\\ 1 & \cdots & 1\end{array}\right]^{-1}\left(\begin{array}{c} x\\ 1\end{array}\right)\] und für $j=1,\ldots,n+1$ und $k=1,\ldots,n$ ist\begin{align*} \lambda_{j,k}\left(x\right): & =\frac{\partial\Lambda_{j}}{\partial x_{k}}\left(x\right)=\left(\left[\begin{array}{ccc} P_{1} & \cdots & P_{n+1}\\ 1 & \cdots & 1\end{array}\right]^{-1}\right)_{j,k}.\end{align*} \end{remark} % \begin{remark} $\Lambda_{j}\left(x\right)$ ist die affine Funktion mit $\Lambda_{j}\left(P_{k}\right)=\delta_{j,k}$ für $j,k=1,\ldots,n+1$. \end{remark} % \begin{remark} Für $n=2$ und Zahlen $p,q,r\in\mathbb{N}_{0}$ ist\[ \int_{T}\lambda_{1}^{p}\left(x\right)\lambda_{2}^{q}\left(x\right)\lambda_{3}^{r}\left(x\right)dx=\frac{p!q!r!}{\left(p+q+r+2\right)!}\,2\left|T\right|\] (Gilt $\int_{T}\Lambda^{\alpha}\left(x\right)dx=\frac{\alpha!n!}{\left(\left|\alpha\right|+n\right)!}\left|T\right|$ für allgemeine Multiindizes $\alpha\in\mathbb{N}_{0}^{n+1}$?) \end{remark} \begin{notation*} Ein \emph{polygonal (polyhydral) berandetes Gebiet}\index{Gebiet!polygonal berandet} $\Omega$ ist eine beschränkte, offene, zusammenhängende, nichtleere Teilmenge des $\mathbb{R}^{n}$, so daß sich $\bar{\Omega}$ als endliche Vereinigung von (nicht-entarteten) Simplizes schreiben läßt. \end{notation*} \begin{defn} [Triangulierung, Knoten, Kanten, Seitenflächen]\label{def:Triangulierung}Eine \emph{Triangulierung}\index{Triangulierung} $\mathcal{T}$ eines polygonal berandeten Gebietes $\Omega$ ist eine endliche Menge \[ \mathcal{T}=\left\{ T_{1},\ldots,T_{m}\right\} \] von nicht-entarteten Simplices \[ T_{j}=\conv\left\{ P_{1}^{j},\ldots,P_{n+1}^{j}\right\} \] mit Ecken $P_{1}^{j},\ldots,P_{n+1}^{j}\in\mathbb{R}^{n}$, so daß gilt:\begin{eqnarray*} \bigcup\mathcal{T}:=T_{1}\cup T_{2}\cup\ldots\cup T_{m} & = & \bar{\Omega}\\ \textrm{und }\left|T_{j}\cap T_{k}\right| & = & 0\qquad\textrm{für }j,k=1,\ldots,m,j\neq k.\end{eqnarray*} Zu $\mathcal{T}$ bezeichne \[ \mathcal{N}:=\left\{ z\in\mathbb{R}^{n}\left|z\textrm{ Ecke eines }T\in\mathcal{T}\right.\right\} \] die Menge aller \emph{Knoten}\index{Knoten} und\[ \mathcal{E}:=\left\{ E\subseteq\mathbb{R}^{n}\left|E\textrm{ Kante eines }T\in\mathcal{T}\right.\right\} \] die Menge aller \emph{Kanten}\index{Kante} ($E$ ist Kante von $T=\conv\left\{ P_{1},\ldots,P_{n+1}\right\} $, wenn $E=\conv\left\{ P_{j},P_{k}\right\} $ für $j,k\in\left\{ 1,\ldots,n+1\right\} $ mit $j\neq k$.) und für $n\geq3$ bezeichne\[ \mathcal{F}:=\left\{ F\subseteq\mathbb{R}^{n}\left|F\textrm{ Seitenfläche eines }T\in\mathcal{T}\right.\right\} \] die Menge aller \emph{Seitenflächen}\index{Seitenflächen} ($F$ ist Seitenfläche von $T=\conv\left\{ P_{1},\ldots,P_{n+1}\right\} $, wenn $F=\conv\left\{ P_{j},P_{k},P_{l}\right\} $ für $j,k,l\in\left\{ 1,\ldots,n+1\right\} $ mit $j,k,l$ paarweise verschieden.) etc. \end{defn} % \begin{defn} [reguläre Triangulierung]Eine Triangulierung $\mathcal{T}$ im $\mathbb{R}^{n}$ mit $n\leq3$ heißt \emph{regulär}\index{Triangulierung!regulär}, sofern für alle $T,K\in\mathcal{T}$ gilt: $T\cap K$ ist gemeinsamer Simplex, oder gemeinsame Fläche ($n\geq3$) oder gemeinsame Kante ($n\geq2$) oder gemeinsamer Knoten ($n\geq1$) oder leer. \end{defn} \begin{notation*} Zum Rand \[ \Gamma:=\partial\Omega=\bar{\Omega}\setminus\Omega\] mit\[ \Gamma=\Gamma_{D}\dot{\cup}\Gamma_{N}\] ($\dot{\cup}$ bezeichne die disjunkte Vereinigung) für $\Gamma_{D}$ abgeschlossen und $\Gamma_{N}:=\Gamma\setminus\Gamma_{D}$ relativ offen, bezeichne $\Gamma_{D}$ den \emph{Dirichlet-Rand\index{Rand!Dirichlet}} und $\Gamma_{N}$ den \emph{Neumann-Rand}\index{Rand!Neumann} von $\Omega$. Für eine gegebene Triangulierung von $\Omega$ mit Kanten $\mathcal{E}$ ($n=2$) bzw. Seitenflächen $\mathcal{F}$ ($n=3$) ist dann\begin{eqnarray*} \Gamma_{D} & = & \begin{cases} \bigcup\mathcal{F}_{D} & \textrm{für }n=3,\\ \bigcup\mathcal{E}_{D} & \textrm{für }n=2,\end{cases}\\ \textrm{und }\overline{\Gamma_{N}} & = & \begin{cases} \bigcup\mathcal{F}_{N} & \textrm{für }n=3,\\ \bigcup\mathcal{E}_{N} & \textrm{für }n=2,\end{cases}\end{eqnarray*} für \begin{eqnarray*} \mathcal{E}_{D} & := & \left\{ E\in\mathcal{E}\left|E\subseteq\Gamma_{D}\right.\right\} ,\\ \mathcal{E}_{N} & := & \left\{ E\in\mathcal{E}\left|E\subseteq\overline{\Gamma_{N}}\right.\right\} ,\\ \mathcal{F}_{D} & := & \left\{ F\in\mathcal{F}\left|F\subseteq\Gamma_{D}\right.\right\} ,\\ \mathcal{F}_{N} & := & \left\{ F\in\mathcal{F}\left|F\subseteq\overline{\Gamma_{N}}\right.\right\} .\end{eqnarray*} ($n=1$: keine Extrabedingung) \end{notation*} \begin{implementation*} Die Knoten $\mathcal{N}=\left\{ P_{1},\ldots,P_{\ell}\right\} $ werden in einer Datei mit Namen \texttt{coordinates.dat} oder \texttt{coordinates4nodes.dat} gespeichert. In Zeile $j$ stehen die $n$ Komponenten von $P_{j}$, d.h. \texttt{coordinates(j,k)}$=\left(P_{j}\right)_{k}$, die $k$-te Komponente von $P_{j}$, $j=1,\ldots,\ell$, $k=1,\ldots,n$. Die Elemente $\mathcal{T}=\left\{ T_{1},\ldots,T_{m}\right\} $ werden in einer Datei mit Namen \texttt{elements.dat} gespeichert. In Zeile $j\in\left\{ 1,\ldots,m\right\} $ und Spalte $k\in\left\{ 1,\ldots,n+1\right\} $ steht \texttt{elements(j,k)}, die Nummer des Knotens $P_{k}\in\mathcal{N}$ in einer fixierten Aufzählung $\left(P_{1},\ldots,P_{n+1}\right)$ der Ecken von $T_{j}$, welche der Konvention $\det\left(\left[\begin{array}{ccc} P_{1} & \cdots & P_{n+1}\\ 1 & \cdots & 1\end{array}\right]\right)>0$ genügt. Im Falle $n=2$ bezeichnen die Knoten $P_{1}$, $P_{2}$ die \emph{Referenzkante}\index{Referenzkante}. \end{implementation*} \begin{example*} Für $n=2$ betrachte eine Triangulierung von $\Omega=\left(0,1\right)^{2}$ in $m=8$ Elemente: \begin{minipage}[c]{0.60\columnwidth}% \begin{picture}(240,230)(-20,-20) \multiput(0,0)(0,100){3}{\line(1,0){200}} \multiput(0,0)(100,0){3}{\line(0,1){200}} \multiput(0,0)(100,0){2}{\line(1,1){100}} \multiput(0,100)(100,0){2}{\line(1,1){100}} \put(0,-12){1}\put(2,-9){\circle{15}} \put(100,-12){2}\put(102,-9){\circle{15}} \put(200,-12){3}\put(202,-9){\circle{15}} \put(-12,105){4}\put(-10,108){\circle{15}} \put(88,105){5}\put(90,108){\circle{15}} \put(210,105){6}\put(212,108){\circle{15}} \put(0,206){7}\put(2,209){\circle{15}} \put(100,206){8}\put(102,209){\circle{15}} \put(200,206){9}\put(202,209){\circle{15}} \put(25,75){\framebox(15,15){1}} \put(70,25){\framebox(15,15){2}} \put(125,75){\framebox(15,15){3}} \put(170,25){\framebox(15,15){4}} \put(25,175){\framebox(15,15){5}} \put(70,125){\framebox(15,15){6}} \put(125,175){\framebox(15,15){7}} \put(170,125){\framebox(15,15){8}} \end{picture}\end{minipage}% \begin{minipage}[t]{0.32\columnwidth}% \begin{tabular}{ll} \texttt{coordinates.dat}:& \texttt{elements.dat}:\tabularnewline & \tabularnewline \begin{tabular}{|c||c|c|} \hline 1& 0& 0\tabularnewline \hline 2& .5& 0\tabularnewline \hline $\vdots$& & \tabularnewline \hline 6& 1& .5\tabularnewline \hline $\vdots$& & \tabularnewline \hline 9& 1& 1\tabularnewline \hline \end{tabular}& \begin{tabular}{|c||c|c|c|} \hline 1& 1& 5& 4\tabularnewline \hline 2& 5& 1& 2\tabularnewline \hline $\vdots$& & & \tabularnewline \hline 6& 8& 4& 5\tabularnewline \hline $\vdots$& & & \tabularnewline \hline 8& 9& 5& 6\tabularnewline \hline \end{tabular}\tabularnewline \end{tabular}\end{minipage}% \end{example*} \begin{picture}(210,230)(-10,-20) \multiput(0,0)(30,0){3}{\line(0,1){200}} \multiput(0,0)(0,30){3}{\line(1,0){200}} \multiput(170,0)(30,0){2}{\line(0,1){200}} \multiput(0,170)(0,30){2}{\line(1,0){200}} \put(18,18){1}\put(20,21){\circle{15}} \put(48,18){2}\put(50,21){\circle{15}} \put(156,18){$N$}\put(160,21){\circle{15}} \put(6,48){$N$+1}\put(16,51){\oval(24,10)} %\put(18,48){\circle{18}} \put(36,48){$N$+2}\put(46,51){\oval(24,10)} %\put(38,45){N+2}\put(48,48){\circle{18}} \put(153,154){$N^2$}\put(159,158){\circle{18}} \multiput(90,90)(10,10){5}{$\cdot$} \end{picture} \section{Finite Elemente Räume} Für eine reguläre Triangulierung $\mathcal{T}$ von $\Omega$ und $k\in\mathbb{N}_{0}$ bezeichne \begin{eqnarray*} P_{k}\left(\mathcal{T}\right) & := & \left\{ f\in L^{\infty}\left(\Omega\right)\left|\forall T\in\mathcal{T},f\left|_{T}\right.\in P_{k}\left(T\right)\right.\right\} \\ P_{k}\left(T\right) & := & \left\{ f\in C^{\infty}\left(T\right)\left|f\textrm{ algebraisches Polynom vom totalen Grad}\leq k\right.\right\} \end{eqnarray*} \begin{remark} Für $n\in\mathbb{N}$ und $k\in\mathbb{N}_{0}$ sei \[ P_{k}:=\left\{ \left.\sum_{\substack{\alpha\in\left\{ 0,\ldots,k\right\} ^{n}\\ \left|\alpha\right|\leq k} }a_{\alpha}x^{\alpha}\right|a_{\alpha}\in\mathbb{R}\,\forall\alpha\right\} \] der Vektorraum der Polynome von \emph{totalem Grad}\index{Polynomgrad!total} höchstens $k$ und\[ Q_{k}:=\left\{ \left.\sum_{\alpha\in\left\{ 0,\ldots,k\right\} ^{n}}a_{\alpha}x^{\alpha}\right|a_{\alpha}\in\mathbb{R}\,\forall\alpha\right\} \] der Vektorraum der Polynome von \emph{partiellem Grad\index{Polynomgrad!partiell}} höchstens $k$. \end{remark} \begin{example*} Für $n=1$ ist \[ P_{k}=Q_{k}=\left\{ \left.a_{0}+a_{1}x+\ldots+a_{k}x^{k}\right|a_{0},\ldots,a_{k}\in\mathbb{R}\right\} .\] Für $n=2$ ist\begin{align*} P_{1} & =\myspan\left\{ 1,x,y\right\} ,\\ Q_{1} & =\myspan\left\{ 1,x,y,xy\right\} \\ \textrm{und }P_{2} & =\myspan\left\{ 1,x,y,x^{2},y^{2},xy\right\} ,\\ Q_{2} & =\myspan\left\{ 1,x,y,xy,x^{2},x^{2}y,x^{2}y^{2},xy^{2},y^{2}\right\} .\end{align*} \end{example*} Wir definieren nun den $P_{k}$-FE-Raum\index{FER} durch \[ V_{h}:=P_{k}\left(\mathcal{T}\right)\cap C_{0}\left(\Omega\right),\qquad C_{0}\left(\Omega\right):=\left\{ f:\bar{\Omega}\rightarrow\mathbb{R}\textrm{ stetig}\left|f=0\textrm{ auf }\partial\Omega\right.\right\} .\] Der $P_{1}$-FER ist $V_{h}$ für $k=1$. Für jeden \emph{freien Knoten\index{Knoten!frei}} $z$, d.h. \[ z\in\mathcal{K}:=\mathcal{N}\cap\Omega,\] bezeichne $\varphi_{z}$ \underbar{die} Funktion $\varphi_{z}\in P_{1}\left(\mathcal{T}\right)$ mit \[ \varphi_{z}\left(x\right)=\begin{cases} 1 & x=z\\ 0 & \textrm{sonst}\end{cases}\qquad\textrm{für alle }x\in\mathcal{N},\] d.h. für alle $T\in\mathcal{T}$ ist $\left.\varphi_{z}\right|_{T}\left(z\right)=1$, falls $z\in T$, und $\left.\varphi_{z}\right|_{T}\left(x\right)=0$ für $x\in\left(\mathcal{N}\cap T\right)\setminus\left\{ z\right\} $. Da $\mathcal{T}$ regulär ist, ist $\varphi_{z}$ an allen Knoten stetig und damit global stetig auf $\bar{\Omega}$. \begin{lem} [nodale Basis]Für eine reguläre Triangulierung $\mathcal{T}$ ist $\left(\varphi_{z}\right)_{z\in\mathcal{K}}$ Basis von $V_{h}$ für $k=1$, $n=2$ und heißt \emph{nodale Basis}.\index{nodale Basis} \end{lem} \begin{proof} Die Eigenschaft $\varphi_{z}\in V_{h}$ folgt nach Konstruktion von $V_{h}$ und der Stetigkeit von $\varphi_{z}$ für innere Knoten $z\in\mathcal{K}$. Es bleibt zu zeigen, daß jede Funktion $f\in V_{h}$ als Linearkombination der $\left(\varphi_{z}\right)_{z\in\mathcal{K}}$ darstellbar ist. Für $x\in\bar{\Omega}$ betrachte Dreiecke $T\in\mathcal{T}$ mit $x\in T$. Sei $x=\lambda_{1}P_{1}+\lambda_{2}P_{2}+\lambda_{3}P_{3}$ mit den Ecken $P_{1},P_{2},P_{3}$ von $T$ und den Baryzentrischen Koordinaten $\lambda_{j}$, $j=1,2,3$. Wegen \[ "\left\{ \varphi_{z}>0\right\} ":=\textrm{Int}\left(\bigcup\left\{ T\in\mathcal{T}\left|z\in T\right.\right\} \right)=\textrm{Int}\left(\textrm{supp}\varphi_{z}\right)\] ist $\lambda_{j}\left(x\right)=\varphi_{P_{j}}\left(x\right)$ und\begin{eqnarray*} f\left(x\right) & = & \lambda_{1}\left(x\right)f\left(P_{1}\right)+\lambda_{2}\left(x\right)f\left(P_{2}\right)+\lambda_{3}\left(x\right)f\left(P_{3}\right)\\ & = & \varphi_{P_{1}}\left(x\right)f\left(P_{1}\right)+\varphi_{P_{2}}\left(x\right)f\left(P_{2}\right)+\varphi_{P_{3}}\left(x\right)f\left(P_{3}\right),\end{eqnarray*} also \[ f\left(x\right)=\sum_{z\in\mathcal{K}}f\left(z\right)\varphi_{z}\left(x\right).\qedhere\] \end{proof} \begin{remark} Allgemeines Prinzip der FEM: Reguläre Triangulierungen werden so definiert, daß sie nodale Basisfunktionen erlauben. \end{remark} Für $E=\conv\left\{ A,B\right\} \in\mathcal{E}$ definiere mittels\[ \varphi_{E}:=4\varphi_{A}\varphi_{B}\] eine {}``\emph{edge-bubble}\index{edge-bubble}''. Dann ist eine (hierarchische) Basis vom $P_{2}$-FER gegeben durch\[ P_{2}\left(\mathcal{T}\right)\cap C\left(\bar{\Omega}\right)=\myspan\left\{ \varphi_{z}\left|z\in\mathcal{N}\right.\right\} \oplus\myspan\left\{ \varphi_{E}\left|E\in\mathcal{E}\right.\right\} \] Weiterhin sei für $T=\conv\left\{ A,B,C\right\} \in\mathcal{T}$\[ \varphi_{T}:=27\varphi_{A}\varphi_{B}\varphi_{C}\] eine {}``\emph{element-bubble}\index{element-bubble}''. Dann ist\[ P_{3}\left(\mathcal{T}\right)\cap C\left(\bar{\Omega}\right)\supsetneq\myspan\left\{ \varphi_{z}\left|z\in\mathcal{N}\right.\right\} \oplus\myspan\left\{ \varphi_{E}\left|E\in\mathcal{E}\right.\right\} \oplus\myspan\left\{ \varphi_{T}\left|T\in\mathcal{T}\right.\right\} \] \section{Diskretes Problem} Zum Modellproblem\begin{eqnarray*} -\Delta u & = & f\quad\textrm{in }\Omega,\\ u & = & 0\quad\textrm{auf }\partial\Omega\end{eqnarray*} und einer gegebenen Triangulierung von $\Omega$ in lauter Dreiecke lautet das diskrete Problem\index{Problem!diskret}: Man finde ein \[ u_{h}=\sum_{z\in\mathcal{K}}x_{z}\varphi_{z}\in V_{h}:=P_{1}\left(\mathcal{T}\right)\cap C_{0}\left(\bar{\Omega}\right)\] ($\mathcal{K}:=\mathcal{N}\cap\Omega$ die freien Knoten, $\varphi_{z}$ nodale Basisfunktionen) mit\[ a\left(u_{h},v_{h}\right)=F\left(v_{h}\right)\qquad\textrm{für alle }v_{h}\in V_{h},\] wobei\begin{eqnarray*} a\left(u_{h},v_{h}\right) & := & \int_{\Omega}\nabla u_{h}\cdot\nabla v_{h}dx,\\ F\left(v_{h}\right) & := & \int_{\Omega}f\left(x\right)v_{h}\left(x\right)dx.\end{eqnarray*} Dies ist äquivalent zu\[ a\left(u_{h},\varphi_{z}\right)=\sum_{y\in\mathcal{K}}x_{y}a\left(\varphi_{y},\varphi_{z}\right)=F\left(\varphi_{z}\right)\qquad\textrm{für alle }z\in\mathcal{K}.\] Also $Ax=b$ mit \begin{eqnarray*} A & := & \left(a\left(\varphi_{y},\varphi_{z}\right)\right)_{y,z\in\mathcal{K}}\in\mathbb{R}^{N\times N},\\ b & := & \left(b_{z}\right)_{z\in\mathcal{K}}:=\left(F\left(\varphi_{z}\right)\right)_{z\in\mathcal{K}}\in\mathbb{R}^{N},\\ x & := & \left(x_{z}\right)_{z\in\mathcal{K}}\in\mathbb{R}^{N}\end{eqnarray*} für $N=\card\left(\mathcal{K}\right)$. Die Berechnung von $A$ und $b$ erfolgt elementweise: Für $\alpha,\beta\in\mathcal{N}$ ist\index{STEMA}\[ \textrm{STEMA}_{\alpha,\beta}:=a\left(\varphi_{\alpha},\varphi_{\beta}\right)=\sum_{T\in\mathcal{T}}\int_{T}\nabla\varphi_{\alpha}\cdot\nabla\varphi_{\beta}dx.\] Sofern $\alpha\not\in T$ oder $\beta\not\in T$ ist $\int_{T}\nabla\varphi_{\alpha}\cdot\nabla\varphi_{\beta}=0$. Für $T=\conv\left\{ P_{1},P_{2},P_{3}\right\} $ mit $P_{j}=\alpha$ und $P_{k}=\beta$ ist\[ \int_{T}\nabla\varphi_{\alpha}\cdot\nabla\varphi_{\beta}dx=\left(\textrm{STEMA}\left(T\right)_{j,k}\right)_{j,k\in\left\{ 1,2,3\right\} },\] wobei \[ \textrm{STEMA}\left(T\right)_{j,k}:=\int_{T}\nabla\lambda_{j}\cdot\nabla\lambda_{k}dx\] mit den Baryzentrischen Koordinaten $\lambda_{1},\lambda_{2},\lambda_{3}$ zu den Ecken $P_{1},P_{2},P_{3}$ von $T$. $\alpha$ und $\beta$ sind globale Bezeichner, $j$ und $k$ sind lokale Bezeichner. \begin{lem} Für \begin{eqnarray*} Q & := & \left[\begin{array}{ccc} P_{1} & P_{2} & P_{3}\\ 1 & 1 & 1\end{array}\right],\\ R & := & Q^{-1}\left(\begin{array}{cc} 1 & 0\\ 0 & 1\\ 0 & 0\end{array}\right)\end{eqnarray*} ist \[ \mathrm{STEMA}\left(T\right)=\frac{1}{2}\det\left(Q\right)\, RR^{T}.\] \end{lem} \begin{proof} ~\[ \textrm{STEMA}\left(T\right)_{j,k}=\int_{T}\left(\lambda_{j,1}\lambda_{k,1}+\lambda_{j,2}\lambda_{k,2}\right)dx\] mit\[ \lambda_{j,\ell}=\frac{\partial\lambda_{j}}{\partial x_{\ell}}=\left(\left[\begin{array}{ccc} P_{1} & P_{2} & P_{3}\\ 1 & 1 & 1\end{array}\right]^{-1}\right)_{j,\ell},\quad\ell=1,2.\] Dann also $\left(Q^{-T}:=\left(Q^{-1}\right)^{T}\right)$\begin{align*} \textrm{STEMA}\left(T\right)_{j,k} & =\left|T\right|\left(\left(Q^{-1}\right)_{j,1}\left(Q^{-T}\right)_{1,k}+\left(Q^{-1}\right)_{j,2}\left(Q^{-T}\right)_{2,k}\right)\\ & =\frac{1}{2}\det\left(Q\right)\,\left(RR^{T}\right)_{j,k}.\qedhere\end{align*} \end{proof} \begin{implementation*} In Matlab: Für eine $3\times2$ Matrix \texttt{vertices:} \texttt{function stema=stema(vertices)} \texttt{$P=\left[\begin{array}{c} \begin{array}{ccc} 1 & \cdots & 1\end{array}\\ \textrm{vertices'}\end{array}\right]$ \%$3\times3$} \texttt{$Q=P\backslash\left[\begin{array}{cc} 0 & 0\\ 1 & 0\\ 0 & 1\end{array}\right]$} \texttt{stema$=\det\left(P\right)*Q*Q'/2$} \end{implementation*} Assemblieren von STEMA (ZUSBAU): $\left(\textrm{STEMA}_{\alpha,\beta}\right)_{\alpha,\beta\in\mathcal{N}}$ ist Anfangs Null und wird elementweise durch $\textrm{STEMA}\left(T\right)$ additiv verändert\[ \textrm{STEMA}=\sum_{T\in\mathcal{T}}\sum_{j,k=1}^{3}\textrm{STEMA}\left(T\right)_{j,k}\underbrace{e_{\alpha\left(j,T\right)}\otimes e_{\alpha\left(k,T\right)}}_{\textrm{Boolsche Matrizen}}\] wobei $e_{z}:\mathcal{N}\rightarrow\left\{ 0,1\right\} $ definiert vermöge\[ e_{z}\left(x\right)=\begin{cases} 1 & \textrm{falls }x=z,\\ 0 & \textrm{sonst}\end{cases}\] und $\alpha\left(j,T\right)$ ist der (globale) Knoten der in $T$ die lokale Nummer $j$ hat, d.h. $\alpha\left(j,T\right)=P_{j}$. \begin{implementation*} In Matlab: \texttt{STEMA(elements(j,:),elements(j,:))=...}~\\ \texttt{STEMA(elements(j,:),elements(j,:))+STEMA($T$)} mit $T$\texttt{=vertices=coordinates(elements(j,:),:)} bzw.\\ $T$\texttt{=coordinates4node(nodes4elements(j,:),:).} $b$ wird elementweise mittels $b_{j}=b_{j}+\int_{T}\varphi_{j}dx$, wobei $\int_{T}\varphi_{j}dx=\left|T\right|\frac{1}{3!}$, berechnet. Einbau der geometrischen Randbedingungen durch Reduzierung des Gleichungssystems \[ \textrm{STEMA}\cdot x=b\] auf die freien Knoten $\mathcal{K}$: \[ x\left(\mathcal{K}\right)=\textrm{STEMA}\left(\mathcal{K},\mathcal{K}\right)\backslash b\left(\mathcal{K}\right).\] \end{implementation*} \section{Zweidimensionale FEM für allgemeine elliptische partielle Differentialgleichungen 2. Ordnung} \underbar{Starke Form}:\index{Randwertproblem!starke Form} Gegeben seien Funktionen $A,A^{-1}\in L^{\infty}\left(\Omega;\mathbb{R}^{d\times d}\right)$, $b\in L^{2}\left(\Omega;\mathbb{R}^{d}\right)$, $\gamma\in L^{\infty}\left(\Omega;\mathbb{R}\right)$ auf einem polygonal berandetem Gebiet $\Omega\Subset\mathbb{R}^{d}$, $d=2$, mit Rand $\partial\Omega=\Gamma=\Gamma_{D}\dot{\cup}\Gamma_{N}$ und (äußerem) Einheitsnormalenvektor $\nu$. $\Gamma_{D}$ sei abgeschlossen und habe positives Oberflächenmaß. $\Gamma_{N}:=\Gamma\setminus\Gamma_{D}$ sei relativ offen. Zu den rechten Seiten $f\in L^{2}\left(\Omega\right)$, $u_{D}\in C^{1}\left(\bar{\Omega}\right)$ (oder größer) und $g\in L^{2}\left(\Gamma_{N}\right)$ finde man ein $u:\Omega\rightarrow\mathbb{R}$ mit hinreichenden Glattheitseigenschaften (z.B. $u\in C^{2}\left(\Omega\right)\cap C^{1}\left(\bar{\Omega}\right)$) und\begin{eqnarray*} -\mydiv\left(ADu\right)+b\cdot Du+\gamma u & = & f\qquad\textrm{f.ü. in }\Omega,\\ u & = & u_{D}\qquad\textrm{f.ü. auf }\Gamma_{D},\\ \left(ADu\right)\cdot\nu & = & g\qquad\textrm{f.ü. auf }\Gamma_{N}.\end{eqnarray*} Formale partielle Integration führt auf die schwache Form mit Bilinearform\begin{eqnarray*} a\left(u,v\right) & := & \int_{\Omega}\left(ADu\right)\cdot Dvdx+\int_{\Omega}\left(b\cdot Du+\gamma u\right)vdx.\\ F\left(v\right) & := & \int_{\Omega}fvdx+\int_{\Gamma_{N}}gvds.\end{eqnarray*} Aus den Randtermen bei der partiellen Integration entsteht\[ -\int_{\partial\Omega}v\underbrace{\left(ADu\right)\cdot\nu}_{=g\textrm{ auf }\Gamma_{N}}ds=-\int_{\Gamma_{N}}gvds-\int_{\Gamma_{D}}v\left(ADu\right)\cdot\nu ds\] und für $v:\bar{\Omega}\rightarrow\mathbb{R}$ mit $Dv\in L^{2}\left(\Omega;\mathbb{R}^{d}\right)$ und $v=0$ auf $\Gamma_{D}$ gilt \[ a\left(u,v\right)=F\left(v\right).\] \underbar{Schwache Form}:\index{Randwertproblem!schwache Form} Zu $F$ finde man ein \[ u\in H^{1}\left(\Omega\right):=\left\{ v\in L^{2}\left(\Omega\right)\left|Dv\textrm{ ex. im schwachen Sinne und }Dv\in L^{2}\left(\Omega;\mathbb{R}^{d}\right)\right.\right\} ,\] mit $u=u_{D}$ auf $\Gamma_{D}$ und für alle \[ v\in V:=H_{D}^{1}\left(\Omega\right):=\left\{ w\in H^{1}\left(\Omega\right)\left|w=0\textrm{ auf }\Gamma_{D}\right.\right\} \] gilt\[ a\left(u,v\right)=F\left(v\right).\] \underbar{Definitheit von $a$}: Obwohl $a$ i.a. ($b\not\equiv0$, $A\not\equiv A^{T}$) keine symmetrische Bilinearform ist, kann man unter gewissen Bedingungen an $A$, $b$, $\gamma$ zeigen, daß $a\geq0$ gilt im Sinne von $0\leq a\left(v,v\right)$ für alle $v\in V=H_{D}^{1}\left(\Omega\right)$ ({}``Testfunktionen''). Dann definiert man $\left|\left|\left|\cdot\right|\right|\right|:=a\left(\cdot,\cdot\right)^{\frac{1}{2}}$ obwohl dies i.a. \underbar{keine} Norm ist und spricht von der {}``\emph{Energie-Norm}''\index{Energie-Norm}. \begin{remark} Die Forderung $u\in H^{1}\left(\Omega\right)$ mit $u=u_{D}$ auf $\Gamma_{D}$ ist äquivalent als $u\in u_{D}+V$ notiert. Also ist $V$ Vektorraum und $u_{D}+V$ affiner Raum (Bisher $u_{D}\equiv0$, also beide Räume gleich.). $V$ heißt \emph{Test(funktionen)raum}\index{Testfunktionenraum} und $u_{D}+V$ heißt \emph{Ansatz(funktionen)raum}\index{Ansatzfunktionenraum}. \end{remark} Entsprechend definiere\[ V_{h}:=\left\{ v_{h}\in P_{1}\left(\mathcal{T}\right)\cap C\left(\bar{\Omega}\right)\left|v_{h}=0\textrm{ auf }\Gamma_{D}\right.\right\} \subseteq V,\] und $u_{Dh}\in P_{1}\left(\mathcal{T}\right)\cap C\left(\bar{\Omega}\right)$ approximiert $u_{D}$ (z.B. mittels nodaler Interpolation). \section{Netzverfeinerungen} \begin{defn} [Referenzkante]In einer regulären Triangulierung $\mathcal{T}$ mit Kantenmenge $\mathcal{E}$ wird jedem Dreieck $T\in\mathcal{T}$ genau eine Kante $E\left(T\right)\in\mathcal{E}\left(T\right):=\left\{ E\in\mathcal{E}\left|E\subset T\right.\right\} $ zugeordnet. Diese Kante $E\left(T\right)$ heißt \emph{Referenzkante\index{Referenzkante}} und definiert eine Abbildung $E:\mathcal{T}\rightarrow\mathcal{E}$. \end{defn} \begin{convention*} Im Datensatz \texttt{elemente} zu $\mathcal{T}$ bezeichnen die Einträge der ersten beiden Spalten die Endpunkte der jeweiligen Referenzkante. \end{convention*} \begin{example*} Zu Beginn wird eine längste Kante als Referenzkante gewählt. \end{example*} Basierend auf der Markierung durch Fixierung der Referenzkante betrachte man die folgenden Verfeinerungen von $\mathcal{T}$: \subsection{Bisections-Netzverfeinerung} Zu $\mathcal{M}\subseteq\mathcal{T}$ und Referenzkantenabbildung $E:\mathcal{T}\rightarrow\mathcal{E}$ bezeichne \begin{eqnarray*} \tilde{\mathcal{T}} & := & \left(\mathcal{T}\setminus\mathcal{M}\right)\cup\textrm{bisec}\left(\mathcal{M}\right)\\ \textrm{mit bisec}\left(\mathcal{M}\right) & := & \left\{ K\left|K\in\textrm{bisec}\left(T\right),T\in\mathcal{M}\right.\right\} \end{eqnarray*} die (i.a. \underbar{nicht} reguläre) Triangulierung, die als Verfeinerung von $\mathcal{T}$ durch Bisection\index{Bisection} der Elemente in $\mathcal{M}$ entsteht: \begin{center}\setlength{\unitlength}{0.45cm} \begin{picture}(15,3.5) \Thicklines \put(0,0){\line(1,0){7}} \thinlines \put(0,0){\line(1,1){3.5}} \put(7,0){\line(-1,1){3.5}} \put(3.3,1.4){$T$} \put(7.2,1.75){\vector(1,0){3.2}} \put(7.3,2){bisection} \put(10,0){\line(1,0){7}} \put(13.5,0){\line(0,1){3.5}} \Thicklines \put(17,0){\line(-1,1){3.5}} \put(10,0){\line(1,1){3.5}} \thinlines \put(12.2,1.4){$T_1$} \put(14,1.4){$T_2$} \end{picture}\end{center} \begin{center}$\left\{ T_{1},T_{2}\right\} :=\textrm{bisec}\left(T\right)$. Dicke Linien deuten Referenzkanten an.\end{center} \begin{remark} Als hängende Knoten kommen hier nur Mittelpunkte von Kanten der Ausgangstriangulierung in Frage, d.h. eine Ecke von 2 Dreiecken ist Mittelpunkt einer Kante eines 3. Dreiecks. \end{remark} \begin{algorithm} [Bisection]~ \begin{algorithmic} \REQUIRE Eine reguläre Triangulierung $\mathcal{T}$ mit Kantenmenge $\mathcal{E}$. Eine Referenzkantenabbildung $E:\mathcal{T}\rightarrow\mathcal{E}$. Eine Menge $\mathcal{M}\subseteq\mathcal{T}$ von Elementen. \ENSURE Eine Triangulierung $\hat{\mathcal{T}}$ mit Kantenmenge $\hat{\mathcal{E}}$ und Referenzkantenabbildung $E:\hat{\mathcal{T}}\rightarrow\hat{\mathcal{E}}$. \COMPUTE\STATE $\ell:=0$ \STATE $\mathcal{T}_{0}:=\left(\mathcal{T}\setminus\mathcal{M}\right)\cup\textrm{bisec}\left(\mathcal{M}\right)$ mit Referenzkantenabbildung $E_{0}:\mathcal{T}_{0}\rightarrow\mathcal{E}_{0}$. \REPEAT \STATE Berechne hängende Knoten $\mathcal{H}_{\ell}$ in $\mathcal{T}_{\ell}$. \STATE Berechne $\mathcal{M}_{\ell}:=\left\{ T\in T_{\ell}\left|\exists z\in\mathcal{H}_{\ell}\,\exists E\in\mathcal{E}\left(T\right),\, z=\textrm{mid}\left(E\right)\right.\right\} $ \STATE $\mathcal{T}_{\ell+1}:=\left(\mathcal{T}_{\ell}\setminus\mathcal{M}_{\ell}\right)\cup\textrm{bisec}\left(\mathcal{M}_{\ell}\right)$ \STATE $\ell:=\ell+1$ \UNTIL{$\mathcal{H}_\ell=\emptyset$} \STATE $\hat{\mathcal{T}}:=\mathcal{T}_{\ell}$ \end{algorithmic} \end{algorithm} \begin{thm} Der Algorithmus bricht nach endlich vielen Schritten ab und berechnet eine reguläre Triangulierung $\hat{\mathcal{T}}$. \end{thm} \begin{proof} In jedem Schritt des Algorithmus ist $\mathcal{T}_{\ell}$ eine Vergröberung der regulären Triangulierung $\textrm{bisec3}\left(\mathcal{T}\right)$, bei der jedes Dreieck $T$ in $\mathcal{T}$ in, wie nachfolgend gezeigt, 4 Teildreiecke zerlegt wird: \setlength{\unitlength}{0.45cm} \begin{picture}(15,3.5) \Thicklines \put(0,0){\line(1,0){7}} \thinlines \put(0,0){\line(1,1){3.5}} \put(7,0){\line(-1,1){3.5}} \put(7.2,1.75){\vector(1,0){3}} \put(7.5,2.1){bisec3} \Thicklines \put(10.5,0){\line(1,0){7}} \put(14,0){\line(0,1){3.5}} \thinlines \put(17.5,0){\line(-1,1){3.5}} \put(10.5,0){\line(1,1){3.5}} \put(12.25,1.75){\line(1,-1){1.75}} \put(15.75,1.75){\line(-1,-1){1.75}} \end{picture} D.h. für alle $T\in\mathcal{T}$ besteht $\mathcal{T}_{\ell}\left|_{T}\right.:=\left\{ K\in\mathcal{T}_{\ell}\left|K\subseteq T\right.\right\} $ aus \setlength{\unitlength}{0.2cm} \begin{picture}(7,3.5) \put(0,0){\line(1,0){7}} \put(0,0){\line(1,1){3.5}} \put(7,0){\line(-1,1){3.5}} \end{picture}, \begin{picture}(7,3.5) \put(0,0){\line(1,0){7}} \put(3.5,0){\line(0,1){3.5}} \put(0,0){\line(1,1){3.5}} \put(7,0){\line(-1,1){3.5}} \end{picture}, \begin{picture}(7,3.5) \put(0,0){\line(1,0){7}} \put(3.5,0){\line(0,1){3.5}} \put(0,0){\line(1,1){3.5}} \put(7,0){\line(-1,1){3.5}} \put(5.25,1.75){\line(-1,-1){1.75}} \end{picture}, \begin{picture}(7,3.5) \put(0,0){\line(1,0){7}} \put(3.5,0){\line(0,1){3.5}} \put(0,0){\line(1,1){3.5}} \put(7,0){\line(-1,1){3.5}} \put(1.75,1.75){\line(1,-1){1.75}} \end{picture} oder \begin{picture}(7,3.5) \put(0,0){\line(1,0){7}} \put(3.5,0){\line(0,1){3.5}} \put(0,0){\line(1,1){3.5}} \put(7,0){\line(-1,1){3.5}} \put(1.75,1.75){\line(1,-1){1.75}} \put(5.25,1.75){\line(-1,-1){1.75}} \end{picture}. Beweis dieser Aussage durch vollständige Induktion über $\ell$: $\ell=0$: Nach Konstruktion besteht $\mathcal{T}_{0}$ nur aus Dreiecken \setlength{\unitlength}{0.1cm} \begin{picture}(7.5,3.5) \put(0,0){\line(1,0){7}} \put(0,0){\line(1,1){3.5}} \put(7,0){\line(-1,1){3.5}} \end{picture} und \begin{picture}(7.5,3.5) \put(0,0){\line(1,0){7}} \put(3.5,0){\line(0,1){3.5}} \put(0,0){\line(1,1){3.5}} \put(7,0){\line(-1,1){3.5}} \end{picture}. $\ell\rightarrow\ell+1$: Betrachte die Situation\setlength{\unitlength}{0.2cm} \begin{picture}(11,3.5) \put(3,0.7){$T_1$} \put(0,0){\line(1,0){7}} \put(0,0){\line(1,1){3.5}} \Thicklines \put(7,0){\line(-1,1){3.5}} \thinlines \put(3.5,3.5){\line(1,0){7}} \put(7,0){\line(1,1){3.5}} \put(6.3,1.6){$T_2$} \end{picture} mit der Referenzkante $F=T_{1}\cap T_{2}$, für die $\textrm{mid}\left(F\right)\in\mathcal{H}_{\ell}$ gilt. Also ist $T_{1},T_{2}\in\mathcal{M}_{\ell}$ und Bisection von $T_{1}$ ergibt \setlength{\unitlength}{0.2cm} \begin{picture}(7.5,3.5) \put(0,0){\line(1,0){7}} \put(0,0){\line(1,1){3.5}} \Thicklines \put(7,0){\line(-1,1){3.5}} \end{picture}, \begin{picture}(7.5,3.5) \put(0,0){\line(1,0){7}} \put(0,0){\line(1,1){3.5}} \put(3.5,0){\line(0,1){3.5}} \Thicklines \put(7,0){\line(-1,1){3.5}} \end{picture}, \begin{picture}(7.5,3.5) \put(0,0){\line(1,0){7}} \put(0,0){\line(1,1){3.5}} \put(7,0){\line(-3,1){5.25}} \Thicklines \put(7,0){\line(-1,1){3.5}} \end{picture}, \begin{picture}(7.5,3.5) \put(0,0){\line(1,0){7}} \put(0,0){\line(1,1){3.5}} \put(3.5,0){\line(0,1){3.5}} \put(3.5,0){\line(-1,1){1.75}} \Thicklines \put(7,0){\line(-1,1){3.5}} \end{picture} oder \begin{picture}(7.5,3.5) \put(0,0){\line(1,0){7}} \put(0,0){\line(1,1){3.5}} \put(7,0){\line(-3,1){5.25}} \put(3.5,0){\line(-1,1){1.75}} \Thicklines \put(7,0){\line(-1,1){3.5}} \end{picture} , d.h. $\mathcal{T}_{\ell+1}$ ist auch eine Vergröberung von $\textrm{bisec3}\left(\mathcal{T}\right)$. Also gilt \[ \card\left(\mathcal{T}\right)\leq\card\left(\mathcal{T}_{\ell}\right)\leq\card\left(\textrm{bisec3}\left(\mathcal{T}\right)\right)=4\card\left(\mathcal{T}\right)\] und $\card\left(\mathcal{T}_{\ell}\right)<\card\left(\mathcal{T}_{\ell+1}\right)$ oder $\card\left(\mathcal{T}_{\ell}\right)=\card\left(\mathcal{T}_{\ell+1}\right)$ mit Abbruch. Also bricht der Algorithmus nach maximal $4\card\left(\mathcal{T}\right)$ Schritten ab. Da dann keine hängenden Knoten vorliegen, ist $\hat{\mathcal{T}}$ regulär. \end{proof} \begin{thm} Für eine reguläre Triangulierung $\mathcal{T}$ mit Referenzkantenabbildung $E:\mathcal{T}\rightarrow\mathcal{E}$, eine Menge $\mathcal{M}\subseteq\mathcal{T}$ von Elementen und eine reguläre Triangulierung $\mathcal{T}'$, welche Verfeinerung von $\left(\mathcal{T}\setminus\mathcal{M}\right)\cup\mathrm{bisec}\left(\mathcal{M}\right)$ ist, gilt $\card\left(\hat{\mathcal{T}}\right)\leq\card\left(\mathcal{T}'\right)$ für den Output $\hat{\mathcal{T}}$ aus dem Algorithmus. \end{thm} \begin{proof} Übungsaufgabe. \end{proof} \begin{thm} [Binev-Dahmen-DeVore (2004)]Zu einer Triangulierung $\mathcal{T}$ mit Referenzkantenabbildung $E:\mathcal{T}\rightarrow\mathcal{E}$ und Mengen $\mathcal{M}_{0},\mathcal{M}_{1},\ldots,\mathcal{M}_{L-1}$ mit $\mathcal{M}_{0}\subseteq\mathcal{T}_{0}:=\mathcal{T}$, $\mathcal{M}_{1}\subseteq\mathcal{T}_{1}$, $\ldots$, $\mathcal{M}_{L-1}\subseteq\mathcal{T}_{L-1}$ sei $\mathcal{T}_{\ell+1}$ das Ergebnis des Bisectionsalgorithmus mit Input $\mathcal{T}_{\ell}$, $E_{\ell}:\mathcal{T}_{\ell}\rightarrow\mathcal{E}_{\ell}$ und $\mathcal{M}_{\ell}$, $\ell=0,1,\ldots,L-1$. Unter gewissen Bedingungen an $E:\mathcal{T}_{0}\rightarrow\mathcal{E}_{0}$ gilt\[ \card\left(\mathcal{T}_{L}\setminus\mathcal{T}_{0}\right)\leq C\sum_{\ell=0}^{L-1}\card\left(\mathcal{M}_{\ell}\right)\] mit einer Konstanten $C$, die nur von $\mathcal{T}_{0}$ und $E_{0}:\mathcal{T}_{0}\rightarrow\mathcal{E}_{0}$ abhängt und insbesondere unabhängig von $L$ ist. \end{thm} \begin{proof} Später für allgemeinere Verfeinerungen und Details an die Anfangsbedingungen. \end{proof} \begin{remark} [Bisektion von Tetraedern]Auch dreidimensionale Bisection ist möglich, vgl. Literatur, z.B. B\"{a}nsch: E. Local Mesh Refinement in 2 and 3 Dimensions. \textit{IMPACT of Computing in Science and Engineering} 1991; 3: 181--191. Sie beinhaltet 5 Typen von Tetraedern (bezeichnet als $P_{u}$, $A$, $M$, $O$ und $P_{f}$ auf der linken Seite) und ihre Bisektionen die mit $M\rightarrow2\, P_{u}$ und $O\rightarrow2\, P_{u}$ beginnen und dann von einer sukzessiven Schleife der Form $A\rightarrow2\, P_{u}\rightarrow4\, P_{f}\rightarrow8\, A$ etc. fortgesetzt werden. Beachte, dass die Formen von $P_{u}$ und $P_{f}$ identisch sind, aber eine unterschiedliche Rolle in der Verfeinerungsschleife spielen. \begin{center}\setlength{\unitlength}{5mm} \begin{picture}(25,5) \Thicklines \put(0,0){\line(1,0){7}} \put(1.75,1.75){\line(1,0){3.5}} \put(0,0){\line(1,1){3.5}} \put(7,0){\line(-1,1){3.5}} \put(1.75,1.75){\line(1,-1){1.75}} \put(5.25,1.75){\line(-1,-1){1.75}} \put(14,0){\line(1,0){3.5}} \put(14,0){\line(1,1){3.5}} \put(17.5,0){\line(0,1){3.5}} \put(15.75,1.75){\line(1,0){3.5}} \put(15.75,1.75){\line(1,-1){1.75}} \put(17.5,0){\line(1,1){1.75}} \put(25.5,0){\line(-1,0){3.5}} \put(25.5,0){\line(-1,1){3.5}} \put(22,0){\line(0,1){3.5}} \put(23.75,1.75){\line(-1,0){3.5}} \put(23.75,1.75){\line(-1,-1){1.75}} \put(22,0){\line(-1,1){1.75}} \put(1.35,1.75){1} \put(5.3,1.75){2} \put(-0.4,-0.6){4} \put(3.5,-0.6){3} \put(7.05,-0.6){4} \put(3.5,3.6){4} \put(13.6,-0.6){4} \put(17.5,-0.6){3} \put(22,-0.6){3} \put(25.55,-0.6){4} \put(15.35,1.75){1} \put(17.7,1.9){5} \put(19.0,1.9){4} \put(20,1.9){4} \put(21.5,1.9){5} \put(23.80,1.75){2} \put(17.5,3.6){4} \put(22,3.6){4} \put(6.8,1.6){\(P_u\)} \put(19.4,0.8){\(P_f\)} \thinlines \put(9,1.75){\vector(1,0){2}} \drawline[1](3.21715729,0)(1.6085786,1.6085786) \drawline[1](3.78284271,0)(5.3914214,1.6085786) \drawline[1](5.1085786,1.8914214)(1.8914214,1.8914214) \drawline[1](5.1085786,1.6085786)(1.8914214,1.6085786) \drawline[1](16.0328427,1.75)(17.5,3.217157288) \drawline[1](17.21715729,0)(15.6085786,1.6085786) \drawline[1](22.28284271,0)(23.8914214,1.6085786) \drawline[1](18.96715729,1.75)(17.5,0.28284271) \drawline[1](17.5,0.28284271)(16.0328427,1.75) \drawline[1](23.46715729,1.75)(22,0.28284271) \drawline[1](22,0.28284271)(20.5328427,1.75) \drawline[1](23.46715729,1.75)(22,3.217157288) \end{picture} \begin{picture}(25,5) \Thicklines \put(0,0){\line(1,0){7}} \put(1.75,1.75){\line(1,0){3.5}} \put(0,0){\line(1,1){3.5}} \put(7,0){\line(-1,1){3.5}} \put(1.75,1.75){\line(1,-1){1.75}} \put(5.25,1.75){\line(-1,-1){1.75}} \put(14,0){\line(1,0){3.5}} \put(14,0){\line(1,1){3.5}} \put(17.5,0){\line(0,1){3.5}} \put(15.75,1.75){\line(1,0){3.5}} \put(15.75,1.75){\line(1,-1){1.75}} \put(17.5,0){\line(1,1){1.75}} \put(25.5,0){\line(-1,0){3.5}} \put(25.5,0){\line(-1,1){3.5}} \put(22,0){\line(0,1){3.5}} \put(23.75,1.75){\line(-1,0){3.5}} \put(23.75,1.75){\line(-1,-1){1.75}} \put(22,0){\line(-1,1){1.75}} \put(1.35,1.75){1} \put(5.3,1.75){2} \put(-0.4,-0.6){4} \put(3.5,-0.6){3} \put(7.05,-0.6){4} \put(3.5,3.6){4} \put(13.6,-0.6){4} \put(17.5,-0.6){3} \put(22,-0.6){3} \put(25.55,-0.6){4} \put(15.35,1.75){1} \put(17.7,1.9){5} \put(19.0,1.9){4} \put(20,1.9){4} \put(21.5,1.9){5} \put(23.80,1.75){2} \put(17.5,3.6){4} \put(22,3.6){4} \put(6.8,1.6){\(A\)} \put(19.4,0.8){\(P_u\)} \thinlines \put(9,1.75){\vector(1,0){2}} \drawline[1](1.8914214,1.6085786)(0.28284271,0) \drawline[1](3.78284271,0)(5.3914214,1.6085786) \drawline[1](5.1085786,1.8914214)(1.8914214,1.8914214) \drawline[1](5.1085786,1.6085786)(1.8914214,1.6085786) \drawline[1](16.0328427,1.75)(17.5,3.217157288) \drawline[1](15.8914214,1.6085786)(14.28284271,0) \drawline[1](18.96715729,1.75)(17.5,0.28284271) \drawline[1](17.5,0.28284271)(16.0328427,1.75) \drawline[1](23.46715729,1.75)(22,0.28284271) \drawline[1](22,0.28284271)(20.5328427,1.75) \drawline[1](23.46715729,1.75)(22,3.217157288) \drawline[1](22.28284271,0)(23.8914214,1.6085786) \end{picture} \begin{picture}(25,5) \Thicklines \put(0,0){\line(1,0){7}} \put(1.75,1.75){\line(1,0){3.5}} \put(0,0){\line(1,1){3.5}} \put(7,0){\line(-1,1){3.5}} \put(1.75,1.75){\line(1,-1){1.75}} \put(5.25,1.75){\line(-1,-1){1.75}} \put(14,0){\line(1,0){3.5}} \put(14,0){\line(1,1){3.5}} \put(17.5,0){\line(0,1){3.5}} \put(15.75,1.75){\line(1,0){3.5}} \put(15.75,1.75){\line(1,-1){1.75}} \put(17.5,0){\line(1,1){1.75}} \put(25.5,0){\line(-1,0){3.5}} \put(25.5,0){\line(-1,1){3.5}} \put(22,0){\line(0,1){3.5}} \put(23.75,1.75){\line(-1,0){3.5}} \put(23.75,1.75){\line(-1,-1){1.75}} \put(22,0){\line(-1,1){1.75}} \put(1.35,1.75){1} \put(5.3,1.75){2} \put(-0.4,-0.6){4} \put(3.5,-0.6){3} \put(7.05,-0.6){4} \put(3.5,3.6){4} \put(13.6,-0.6){4} \put(17.5,-0.6){3} \put(22,-0.6){3} \put(25.55,-0.6){4} \put(15.35,1.75){1} \put(17.7,1.9){5} \put(19.0,1.9){4} \put(20,1.9){4} \put(21.5,1.9){5} \put(23.80,1.75){2} \put(17.5,3.6){4} \put(22,3.6){4} \put(6.8,1.6){\(M\)} \put(19.4,0.8){\(P_u\)} \thinlines \put(9,1.75){\vector(1,0){2}} \drawline[1](0.1414213562,0.1414213562)(3.3585786,0.1414213562) \drawline[1](3.78284271,0)(5.3914214,1.6085786) \drawline[1](5.1085786,1.8914214)(1.8914214,1.8914214) \drawline[1](5.1085786,1.6085786)(1.8914214,1.6085786) \drawline[1](16.0328427,1.75)(17.5,3.217157288) \drawline[1](14.1414213562,0.1414213562)(17.3585786,0.1414213562) \drawline[1](18.96715729,1.75)(17.5,0.28284271) \drawline[1](17.5,0.28284271)(16.0328427,1.75) \drawline[1](23.46715729,1.75)(22,0.28284271) \drawline[1](22,0.28284271)(20.5328427,1.75) \drawline[1](23.46715729,1.75)(22,3.217157288) \drawline[1](22.28284271,0)(23.8914214,1.6085786) \end{picture} \begin{picture}(25,5) \Thicklines \put(0,0){\line(1,0){7}} \put(1.75,1.75){\line(1,0){3.5}} \put(0,0){\line(1,1){3.5}} \put(7,0){\line(-1,1){3.5}} \put(1.75,1.75){\line(1,-1){1.75}} \put(5.25,1.75){\line(-1,-1){1.75}} \put(14,0){\line(1,0){3.5}} \put(14,0){\line(1,1){3.5}} \put(17.5,0){\line(0,1){3.5}} \put(15.75,1.75){\line(1,0){3.5}} \put(15.75,1.75){\line(1,-1){1.75}} \put(17.5,0){\line(1,1){1.75}} \put(25.5,0){\line(-1,0){3.5}} \put(25.5,0){\line(-1,1){3.5}} \put(22,0){\line(0,1){3.5}} \put(23.75,1.75){\line(-1,0){3.5}} \put(23.75,1.75){\line(-1,-1){1.75}} \put(22,0){\line(-1,1){1.75}} \put(1.35,1.75){1} \put(5.3,1.75){2} \put(-0.4,-0.6){4} \put(3.5,-0.6){3} \put(7.05,-0.6){4} \put(3.5,3.6){4} \put(13.6,-0.6){4} \put(17.5,-0.6){3} \put(22,-0.6){3} \put(25.55,-0.6){4} \put(15.35,1.75){1} \put(17.7,1.9){5} \put(19.0,1.9){4} \put(20,1.9){4} \put(21.5,1.9){5} \put(23.80,1.75){2} \put(17.5,3.6){4} \put(22,3.6){4} \put(6.8,1.6){\(O\)} \put(19.4,0.8){\(P_u\)} \thinlines \put(9,1.75){\vector(1,0){2}} \drawline[1](0.1414213562,0.1414213562)(3.3585786,0.1414213562) \drawline[1](3.6414213562,0.1414213562)(6.8585786,0.1414213562) \drawline[1](5.1085786,1.8914214)(1.8914214,1.8914214) \drawline[1](5.1085786,1.6085786)(1.8914214,1.6085786) \drawline[1](16.0328427,1.75)(17.5,3.217157288) \drawline[1](14.1414213562,0.1414213562)(17.3585786,0.1414213562) \drawline[1](18.96715729,1.75)(17.5,0.28284271) \drawline[1](17.5,0.28284271)(16.0328427,1.75) \drawline[1](23.46715729,1.75)(22,0.28284271) \drawline[1](22,0.28284271)(20.5328427,1.75) \drawline[1](23.46715729,1.75)(22,3.217157288) \drawline[1](22.1414213562,0.1414213562)(25.3585786,0.1414213562) \end{picture} \begin{picture}(25,5) \Thicklines \put(0,0){\line(1,0){7}} \put(1.75,1.75){\line(1,0){3.5}} \put(0,0){\line(1,1){3.5}} \put(7,0){\line(-1,1){3.5}} \put(1.75,1.75){\line(1,-1){1.75}} \put(5.25,1.75){\line(-1,-1){1.75}} \put(14,0){\line(1,0){3.5}} \put(14,0){\line(1,1){3.5}} \put(17.5,0){\line(0,1){3.5}} \put(15.75,1.75){\line(1,0){3.5}} \put(15.75,1.75){\line(1,-1){1.75}} \put(17.5,0){\line(1,1){1.75}} \put(25.5,0){\line(-1,0){3.5}} \put(25.5,0){\line(-1,1){3.5}} \put(22,0){\line(0,1){3.5}} \put(23.75,1.75){\line(-1,0){3.5}} \put(23.75,1.75){\line(-1,-1){1.75}} \put(22,0){\line(-1,1){1.75}} \put(1.35,1.75){1} \put(5.3,1.75){2} \put(-0.4,-0.6){4} \put(3.5,-0.6){3} \put(7.05,-0.6){4} \put(3.5,3.6){4} \put(13.6,-0.6){4} \put(17.5,-0.6){3} \put(22,-0.6){3} \put(25.55,-0.6){4} \put(15.35,1.75){1} \put(17.7,1.9){5} \put(19.0,1.9){4} \put(20,1.9){4} \put(21.5,1.9){5} \put(23.80,1.75){2} \put(17.5,3.6){4} \put(22,3.6){4} \put(6.8,1.6){\(P_f\)} \put(19.4,0.8){\(A\)} \thinlines \put(9,1.75){\vector(1,0){2}} \drawline[1](3.21715729,0)(1.6085786,1.6085786) \drawline[1](3.78284271,0)(5.3914214,1.6085786) \drawline[1](5.1085786,1.8914214)(1.8914214,1.8914214) \drawline[1](5.1085786,1.6085786)(1.8914214,1.6085786) \drawline[1](16.0328427,1.75)(17.5,3.217157288) \drawline[1](17.21715729,0)(15.6085786,1.6085786) \drawline[1](17.78284271,0.28284271)(17.78284271,1.75) \drawline[1](17.5,0.28284271)(16.0328427,1.75) \drawline[1](23.46715729,1.75)(22,0.28284271) \drawline[1](21.78284271,0.28284271)(21.78284271,1.75) \drawline[1](23.46715729,1.75)(22,3.217157288) \drawline[1](22.28284271,0)(23.8914214,1.6085786) \end{picture}\end{center} \end{remark} \subsection{Erweiterte Rot-Grün-Blau-Netzverfeinerung} \index{Rot-Grün-Blau-Netzverfeinerung}Dieser Abschnitt behandelt die nachfolgend skizzierten Verfeinerungsregeln, die auch die neuen Referenzkanten (durch dicke Linien) beschreiben.\setlength{\unitlength}{0.3cm} \begin{center}\begin{tabular}{|cl|} \hline \begin{picture}(7,3.5) \Thicklines \put(0,0){\line(1,0){7}} \thinlines \put(0,0){\line(1,1){3.5}} \put(7,0){\line(-1,1){3.5}} \end{picture} & keine\tabularnewline \hline \begin{picture}(7,3.5) \Thicklines \put(7,0){\line(-1,1){3.5}} \put(0,0){\line(1,1){3.5}} \thinlines \put(3.5,3.5){\line(0,-1){3.5}} \put(0,0){\line(1,0){7}} \end{picture}& bisec$2$=bisec={}``grün''\tabularnewline \hline \begin{picture}(7,3.5) \Thicklines \put(0,0){\line(1,0){3.5}} \put(3.5,0){\line(0,1){3.5}} \put(3.5,3.5){\line(1,-1){3.5}} \thinlines \put(3.5,0){\line(1,0){3.5}} \put(3.5,3.5){\line(-1,-1){3.5}} \put(3.5,0){\line(-1,1){1.75}} \end{picture}& bisec$3\ell$={}``blau$_{\ell}$''\tabularnewline \hline \begin{picture}(7,3.5) \Thicklines \put(3.5,0){\line(1,0){3.5}} \put(3.5,0){\line(0,1){3.5}} \put(0,0){\line(1,1){3.5}} \thinlines \put(0,0){\line(1,0){3.5}} \put(7,0){\line(-1,1){3.5}} \put(3.5,0){\line(1,1){1.75}} \end{picture} & bisec$3r$={}``blau$_{r}$''\tabularnewline \hline \begin{picture}(7,3.5) \Thicklines \put(0,0){\line(1,0){7}} \put(1.75,1.75){\line(1,0){3.5}} \thinlines \put(0,0){\line(1,1){3.5}} \put(7,0){\line(-1,1){3.5}} \put(1.75,1.75){\line(1,-1){1.75}} \put(5.25,1.75){\line(-1,-1){1.75}} \end{picture}& rot\tabularnewline \hline \begin{picture}(7,3.5) \Thicklines \put(0,0){\line(1,0){7}} \put(3.5,0){\line(0,1){3.5}} \thinlines \put(0,0){\line(1,1){3.5}} \put(7,0){\line(-1,1){3.5}} \put(1.75,1.75){\line(1,-1){1.75}} \put(5.25,1.75){\line(-1,-1){1.75}} \end{picture}& bisec3\tabularnewline \hline \begin{picture}(7,3.5) \Thicklines \put(0,0){\line(1,0){7}} \put(1.75,1.75){\line(1,-1){1.75}} \put(5.25,1.75){\line(-1,-1){1.75}} \put(1.75,1.75){\line(1,1){1.75}} \put(5.25,1.75){\line(-1,1){1.75}} \thinlines \put(3.5,0){\line(0,1){3.5}} \put(1.75,1.75){\line(1,0){3.5}} \put(0,0){\line(1,1){3.5}} \put(7,0){\line(-1,1){3.5}} \end{picture}& bisec5 (mit neuem Innenknoten)\tabularnewline \hline \end{tabular}\end{center} Alle diese Verfeinerungen entstehen durch Markierung von Kanten und deren Bisection und sind Vergröberungen von $\textrm{bisec5}\left(T\right)$. \subsubsection*{Übergang von Element- zu Kanten-Markierungen} In einer Triangulierung $\mathcal{T}$ werden gewisse Kanten $\mathcal{M}\subseteq\mathcal{E}$ zur Bisection markiert. \begin{defn} [(R)]\index{(R)}Eine Menge $\mathcal{M}\subseteq\mathcal{E}$ markierter Kanten in einer regulären Triangulierung $\mathcal{T}$ (in lauter Dreiecke in 2D) und eine Referenzkantenabbildung $E:\mathcal{T}\rightarrow\mathcal{E}$ erfüllt (R), gdw.\[ \forall T\in\mathcal{T}\qquad\left(\mathcal{M}\cap\mathcal{E}\left(T\right)=\emptyset\textrm{ oder }E\left(T\right)\in\mathcal{M}\right)\tag{\textrm{R}},\] $\mathcal{E}\left(T\right):=\left\{ E\in\mathcal{E}\left|E\subset\partial T\right.\right\} $. \end{defn} \begin{remark} Sofern (R) gilt, kann jedes $T\in\mathcal{T}$ mit den obigen Regeln so verfeinert werden, daß alle Kanten in $\mathcal{M}\cap\mathcal{E}\left(T\right)$ halbiert werden. Jede dieser so entstandenen Verfeinerungen ist eine \emph{reguläre} Triangulierung! (Beweis: Es werden \emph{keine} hängenden Knoten erzeugt.) \end{remark} \textbf{Idee:} (R) herstellen durch sukzessive Vergrößerung von $\mathcal{M}$: \begin{algorithm} [Rot-Grün-Blau-Abschluß]\label{alg:RotGruenBlau}\index{Rot-Grün-Blau-Abschluß}~ \begin{algorithmic} \REQUIRE Eine reguläre Triangulierung $\mathcal{T}$ mit Kantenmenge $\mathcal{E}$. Eine Referenzkantenabbildung $E:\mathcal{T}\rightarrow\mathcal{E}$. Eine Menge $\mathcal{M}\subseteq\mathcal{E}$ markierter Kanten. \COMPUTE\STATE $k:=0$, $\mathcal{M}^{\left(0\right)}:=\mathcal{M}$, $\mathcal{N}^{\left(0\right)}:=\mathcal{M}$. \WHILE{$\mathcal{N}^{\left(k\right)}\neq\emptyset$} \STATE Wähle $E\in\mathcal{N}^{\left(k\right)}$ mit Nachbarelementen $T_{\pm}\in\mathcal{T}$, d.h. $E\subset\partial T_{\pm}$ (bzw. nur ein Nachbarelement $T_{+}$, falls $E$ Außenkante ist). \STATE $\mathcal{M}^{\left(k+1\right)}:=\mathcal{M}^{\left(k\right)}\cup\left\{ E_{+},E_{-}\right\} $ (bzw. $\mathcal{M}^{\left(k+1\right)}:=\mathcal{M}^{\left(k\right)}\cup\left\{ E_{+}\right\} $, falls $E$ Außenkante ist) für die Referenzkante $E_{\pm}:=E\left(T_{\pm}\right)$ von $T_{\pm}$. \STATE $\mathcal{N}^{\left(k+1\right)}:=\begin{cases} \mathcal{N}^{\left(k\right)}\setminus\left\{ E\right\} & \textrm{falls }\mathcal{M}^{\left(k\right)}=\mathcal{M}^{\left(k+1\right)},\\ \left(\mathcal{N}^{\left(k\right)}\cup\left\{ E_{+},E_{-}\right\} \right)\setminus\left\{ E\right\} & \textrm{falls }\mathcal{M}^{\left(k\right)}\neq\mathcal{M}^{\left(k+1\right)}.\end{cases}$ \STATE $k:=k+1$. \ENDWHILE \ENSURE $\hat{\mathcal{M}}:=\mathcal{M}^{\left(k\right)}$. \end{algorithmic} \end{algorithm} \begin{thm} \renewcommand{\labelenumi}{(\alph{enumi})} \begin{enumerate} \item Der Algorithmus bricht nach endlich vielen Schritten ab. \item $\hat{\mathcal{M}}$ erfüllt \emph{(R)}. \item $\hat{\mathcal{M}}$ ist minimal mit \emph{(R)} und $\mathcal{M}\subseteq\hat{\mathcal{M}}$, d.h. für jedes $\tilde{\mathcal{M}}$ mit \emph{(R)} und $\mathcal{M}\subseteq\tilde{\mathcal{M}}$ gilt $\hat{\mathcal{M}}\subseteq\tilde{\mathcal{M}}$. \end{enumerate} \end{thm} \begin{proof} \begin{description} \item [\textmd{\emph{(a):}}]Da $m_{j}:=\card\left(\mathcal{M}_{j}\right)$ monoton wächst, aber $m_{j}\leq\card\left(\mathcal{E}\right)$, gilt\[ \mathcal{M}_{J}=\mathcal{M}_{J+1}=\mathcal{M}_{J+2}=\ldots\] ab einem Index $J$, oder der Algorithmus bricht ab. Im ersten Fall erfüllt $n_{J}:=\card\left(\mathcal{N}^{\left(J\right)}\right)$ aber\[ n_{J}>n_{J+1}>n_{J+2}>\ldots>0.\] Dieser Widerspruch zeigt $n_{k}=0$ für ein $k<\infty$. \item [\textmd{\emph{(b):}}] \begin{enumerate} \item \underbar{Behauptung}: \[ \hat{\mathcal{M}}\subseteq\hat{\mathcal{N}}:=\bigcup_{m=0}^{k}\mathcal{N}^{\left(m\right)}.\] \underbar{Beweis}: Für jedes $E\in\hat{\mathcal{M}}$ gilt $E\in\mathcal{M}^{\left(\ell\right)}\setminus\mathcal{M}^{\left(\ell-1\right)}$ für ein $\ell\in\left\{ 0,1,\ldots,k\right\} $, wobei $\mathcal{M}^{\left(-1\right)}:=\emptyset$. Für $\ell=0$ ist $E\in\mathcal{N}^{\left(0\right)}=\mathcal{M}\subseteq\hat{\mathcal{N}}$. Für $\ell\geq1$ gilt $E=E\left(K_{+}\right)$ für ein $K_{+}\in\mathcal{T}$ mit $K_{+}\cap K_{-}=F\in\mathcal{N}^{\left(\ell-1\right)}\setminus\mathcal{N}^{\left(\ell\right)}$ (und Modifikation für $F\subseteq\partial\Omega$). Da $E\not\in\mathcal{M}^{\left(\ell-1\right)}$ ist $\mathcal{M}^{\left(\ell\right)}\neq\mathcal{M}^{\left(\ell-1\right)}$ und daher $\mathcal{N}^{\left(\ell\right)}=\left(\mathcal{N}^{\left(\ell-1\right)}\cup\left\{ E\left(K_{+}\right),E\left(K_{-}\right)\right\} \right)\setminus\left\{ F\right\} $. Falls $E=F$, so ist $E\in\hat{\mathcal{N}}$, da $F\in\mathcal{N}^{\left(\ell-1\right)}\subseteq\hat{\mathcal{N}}$. Falls $E\neq F$, so ist $E\in\mathcal{N}^{\left(\ell\right)}\subseteq\hat{\mathcal{N}}$. Also stets $E\in\hat{\mathcal{N}}$. \underbar{Nebenbemerkung}: \[ \hat{\mathcal{N}}\subseteq\hat{\mathcal{M}}.\] \underbar{Beweis}: Zu $E\in\hat{\mathcal{N}}$ existiert ein $j$ mit $E\in\mathcal{N}^{\left(j\right)}\setminus\mathcal{N}^{\left(j+1\right)}$. $E=T_{+}\cap T_{-}$, $E\left(T_{\pm}\right)\in\hat{\mathcal{M}}$ (und Modifikation für $E\subseteq\partial\Omega$). Wenn $E\in\left\{ E\left(T_{+}\right),E\left(T_{-}\right)\right\} $, so ist $E\in\hat{\mathcal{M}}$. Andernfalls ist $E$ keine Referenzkante. Da in $\hat{\mathcal{N}}\setminus\mathcal{N}^{\left(0\right)}$ nur Referenzkanten liegen, ist $E\not\in\hat{\mathcal{N}}\setminus\mathcal{N}^{\left(0\right)}$. Da $E\in\hat{\mathcal{N}}$, folgt $E\in\mathcal{N}^{\left(0\right)}\subseteq\hat{\mathcal{M}}$. \item \underbar{Behauptung}:\[ \left\{ E\left(K\right)\left|\exists K\in\mathcal{T}\quad\hat{\mathcal{N}}\cap\mathcal{E}\left(K\right)\neq\emptyset\right.\right\} \subseteq\hat{\mathcal{M}}.\] \underbar{Beweis}: Betrachte ein $K\in\mathcal{T}$ mit $\mathcal{\hat{N}}\cap\mathcal{E}\left(K\right)\neq0$ und ein $E\in\mathcal{\hat{N}}\cap\mathcal{E}\left(K\right)$. Dann existiert ein Index $j\in\left\{ 0,1,\ldots,k\right\} $, so daß $E\in\mathcal{N}^{\left(j\right)}\setminus\mathcal{N}^{\left(j+1\right)}$, also $E=T_{+}\cap T_{-}$ und $E\left(T_{+}\right),E\left(T_{-}\right)\in\hat{\mathcal{M}}$, $T_{+},T_{-}\in\mathcal{T}$ (und Modifikation für $E\in\partial\Omega$). Da $E\in\mathcal{E}\left(K\right)$, ist $K=T_{+}$ oder $K=T_{-}$ und somit $E\left(K\right)\in\hat{\mathcal{M}}$. \item \underbar{Behauptung}: $\hat{\mathcal{M}}$ erfüllt (R). \underbar{Beweis}: Wenn $T\in\mathcal{T}$ mit $\hat{\mathcal{M}}\cap\mathcal{E}\left(T\right)\neq\emptyset$, existiert nach 1. eine Kante $E\in\mathcal{E}\left(T\right)\cap\hat{\mathcal{N}}\neq\emptyset$. Nach 2. ist dann $E\left(T\right)\in\hat{\mathcal{M}}$. \end{enumerate} \item [\textmd{\emph{(c):}}]Für $\tilde{\mathcal{M}}$ mit (R) und $\mathcal{M}^{\left(0\right)}=\mathcal{M}\subseteq\tilde{\mathcal{M}}\subseteq\mathcal{E}$ wird $\mathcal{M}^{\left(j\right)}\subseteq\tilde{\mathcal{M}}$ durch vollständige Induktion über $j=0,1,2,\ldots,k$ gezeigt. $j=0$: klar. $j\rightarrow j+1$: $j\leq k-1$, d.h. zu zeigen ist $E\left(K\right)\in\tilde{\mathcal{M}}$ für $K\in\mathcal{T}$ mit $E\left(K\right)\in\mathcal{M}^{\left(j+1\right)}\setminus\mathcal{M}^{\left(j\right)}$ (sonst $E\left(K\right)\in\mathcal{M}^{\left(j\right)}\subseteq\tilde{\mathcal{M}}$ nach Induktionsvoraussetzung). Es gilt $E\in\mathcal{N}^{\left(j\right)}\cap\mathcal{E}\left(K\right)$, $\mathcal{M}^{\left(j+1\right)}\neq\mathcal{M}^{\left(j\right)}$, $\mathcal{N}^{\left(j+1\right)}=\left(\mathcal{N}^{\left(j\right)}\cup\left\{ E_{+},E_{-}\right\} \right)\setminus\left\{ E\right\} $. o.B.d.A. $E_{+}=E\left(K\right)$ und $E\in\mathcal{E}\left(K\right)$. Im Fall $E\in\mathcal{M}^{\left(0\right)}\subseteq\tilde{\mathcal{M}}$ ist $\tilde{\mathcal{M}}\cap E\left(K\right)\neq\emptyset$, also $E\left(K\right)\in\tilde{\mathcal{M}}$ wegen (R). Sei nun also $E\not\in\mathcal{M}^{\left(0\right)}=\mathcal{N}^{\left(0\right)}$. Dann existiert ein $\ell\in\left\{ 0,1,\ldots,j\right\} $, $T\in\mathcal{T}$ mit $E=E\left(T\right)$ und $E\in\left(\mathcal{N}^{\left(\ell\right)}\setminus\mathcal{N}^{\left(\ell-1\right)}\right)\cap\mathcal{E}\left(T\right)$. Wegen $E\in\mathcal{M}^{\left(\ell\right)}\subseteq\mathcal{M}^{\left(j\right)}\subseteq\tilde{\mathcal{M}}$ nach Induktionsvoraussetzung folgt $E\in\tilde{\mathcal{M}}\cap\mathcal{E}\left(K\right)\neq\emptyset$. Mit (R) dann $E\left(K\right)\in\tilde{\mathcal{M}}$.\qedhere \end{description} \end{proof} \begin{algorithm} [Adaptive Netzverfeinerung]\label{alg:adapNetzverfeinerung}\index{adaptive Netzverfeinerung}~ \begin{algorithmic}\REQUIRE Eine reguläre Triangulierung $\mathcal{T}^{\left(0\right)}$. Eine Referenzkantenabbildung $E^{\left(0\right)}:\mathcal{T}^{\left(0\right)}\rightarrow\mathcal{E}^{\left(0\right)}$. Mengen $\mathcal{M}^{\left(0\right)}\subseteq\mathcal{E}^{\left(0\right)}$, $\mathcal{M}^{\left(1\right)}\subseteq\mathcal{E}^{\left(1\right)}$, $\ldots$, $\mathcal{M}^{\left(L\right)}\subseteq\mathcal{E}^{\left(L\right)}$ \COMPUTE \FOR{$\ell=1,\ldots,L-1$} \STATE $\hat{\mathcal{M}}^{\left(\ell\right)}:=$Abschluß von $\mathcal{M}^{\left(\ell\right)}$ in regulärer Triangulierung $\mathcal{T}^{\left(\ell\right)}$ mit Algorithmus \ref{alg:RotGruenBlau} \STATE Verallgemeinere die Rot-Grün-Blau-Netzverfeinerung mit Bisektion aller Kanten in $\hat{\mathcal{M}}^{\left(\ell\right)}$ mit Output $\mathcal{T}^{\left(\ell+1\right)}$ und $E^{\left(\ell+1\right)}:\mathcal{T}^{\left(\ell+1\right)}\rightarrow\mathcal{E}^{\left(\ell+1\right)}$ \ENDFOR \ENSURE Reguläre Triangulierungen $\mathcal{T}^{\left(0\right)},\mathcal{T}^{\left(1\right)},\ldots,\mathcal{T}^{\left(L\right)}$ \end{algorithmic} \end{algorithm} \begin{notation*} $\mathcal{T}^{\left(0\right)}$ heißt \emph{grobe Triangulierung\index{Triangulierung!grob}} oder \emph{Anfangstriangulierung}. Idee: $\mathcal{T}^{\left(0\right)}$ hat möglichst wenige Elemente, so daß $\bar{\Omega}=\cup\mathcal{T}^{\left(0\right)}$ beschrieben wird. Die Elemente in $\mathcal{T}^{\left(0\right)}$ heißen \emph{grobe Elemente} oder \emph{Makroelemente}\index{Makroelement}. (Diese Bezeichnungen sind \underbar{nicht} standardisiert.) \end{notation*} \begin{thm} \label{thm:algNetzverfeinerung}Für eine reguläre Triangulierung $\mathcal{T}^{\left(0\right)}$(und geeignete Referenzkantenabbildung $E^{\left(0\right)}:\mathcal{T}^{\left(0\right)}\rightarrow\mathcal{E}^{\left(0\right)}$) und geeignete Mengen $\mathcal{M}^{\left(0\right)},\ldots,\mathcal{M}^{\left(L-1\right)}$ markierter Kanten sei $\mathcal{T}:=\mathcal{T}^{\left(k\right)}$ eine der durch den Algorithmus \ref{alg:adapNetzverfeinerung} definierte Triangulierung. Dann gelten (a)-(e):\renewcommand{\labelenumi}{(\alph{enumi})} \begin{enumerate} \item $\mathcal{T}$ ist reguläre Triangulierung. \item Für alle $T\in\mathcal{T}$ existiert genau ein $K\in\mathcal{T}^{\left(0\right)}$ mit $T\subseteq K$. Für alle $K\in\mathcal{T}^{\left(0\right)}$ existiert genau eine Affinität (d.h. affine Bijektion) $\Phi:=\Phi_{K}:K\rightarrow T_{\mathrm{ref}}$, $T_{\mathrm{ref}}:=\conv\left\{ \left(0,0\right),\left(1,0\right),\left(0,1\right)\right\} $, $\Phi\left(x\right)=Ax+b$, $A\in\mathbb{R}^{2\times2}$ regulär, wobei $\Phi\left(E^{\left(0\right)}\left(K\right)\right)=\conv\left(\left(1,0\right),\left(0,1\right)\right)$. $\Phi^{-1}\left(x\right):=P_{1}+\left(P_{2}-P_{1},P_{3}-P_{1}\right)x$, $\det D\Phi>0$. \begin{center}\setlength{\unitlength}{0.5cm} \begin{picture}(21,5)(1,0.1) \Thicklines \put(0,0){\line(1,1){3.5}} \put(-1,0){$P_3$} \thinlines \put(0,0){\line(1,0){7}} \put(7.1,0){$P_1$} \put(7,0){\line(-1,1){3.5}} \put(3.6,3.5){$P_2$} \put(-0.25,2.2){$E^{(0)}(K)$} \put(3,1){$K$} \put(8,1.75){\vector(1,0){3}} \put(9,2){$\Phi$} \put(13,0){\line(1,0){5}} \put(13,0){\line(0,1){5}} \Thicklines \put(18,0){\line(-1,1){5}} \put(16.3,2.2){$\Phi(E^{(0)}(K))$} \put(14,1){$\Phi(K)$} \end{picture} \end{center} Dann ist das affine Bild $\left\{ \Phi\left(T\right)\left|T\in\mathcal{T},T\subseteq K\right.\right\} $ von $\mathcal{T}\left|_{K}\right.:=\left\{ T\in\mathcal{T}\left|T\subseteq K\right.\right\} $ eine reguläre Triangulierung von $T_{\mathrm{ref}}$ in lauter gleichschenklige rechtwinklige Dreiecke. \item Die Referenzkante $E\left(T\right)$ wird für $T\in\mathcal{T}\left|_{K}\right.$, $K\in\mathcal{T}^{\left(0\right)}$, durch $\Phi_{K}$ auf die Hypotenuse von $\Phi_{K}\left(T\right)$ abgebildet. \item Die $L^{2}$-Projektion $\Pi:H^{1}\left(\Omega\right)\rightarrow L^{2}\left(\Omega\right)$ auf den FER $P_{1}\left(\mathcal{T}\right)\cap C\left(\bar{\Omega}\right)$ ist $H^{1}$-stabil in dem Sinne, daß ein $C:=C\left(\mathcal{T}^{\left(0\right)},E^{\left(0\right)}\right)$ existiert, so daß für alle $v\in H^{1}\left(\Omega\right)$\[ \left\Vert D\Pi v\right\Vert _{L^{2}\left(\Omega\right)}\leq C\left\Vert Dv\right\Vert _{L^{2}\left(\Omega\right)}.\] \item Es existiert ein $C:=C\left(\mathcal{T}^{\left(0\right)},E^{\left(0\right)}\right)$, so daß\[ \card\left(\mathcal{T}\setminus\mathcal{T}^{\left(0\right)}\right)\leq C\sum_{\ell=0}^{k-1}\card\left(\mathcal{M}^{\left(\ell\right)}\right).\] Dabei ist $C$ von $L$, $k$, etc. unabhängig. \end{enumerate} \end{thm} \begin{remark} [Vergleich zur longest-edge-bisection]Statt Referenzkanten zu definieren, hat M.C. Rivara (1984) vorgeschlagen, eine längste Kante als Bezugskante für rot-grün-blau-Verfeinerung zu benutzen. Dies ist nicht dasselbe wie die hier betrachtete verallgemeinerte rot-grün-blau-Verfeinerung (Algorithmus \ref{alg:RotGruenBlau}). \begin{center}\setlength{\unitlength}{0.4cm}\begin{tabular}{cc} \begin{picture}(10,13)(0,-1) \thicklines \put(0,0){\line(1,0){8}} \put(0,0){\line(2,5){4}} \put(4,10){\line(2,-5){4}} \put(2,5){\line(6,-5){6}} \put(0,-1){$A$} \put(7.5,-1){$B$} \put(3.8,10.2){$C$} \put(1.2,5){$D$} \end{picture}& \begin{picture}(10,13)(0,-1) \thicklines \put(0,0){\line(1,0){8}} \put(0,0){\line(2,5){4}} \put(4,10){\line(2,-5){4}} \put(2,5){\line(6,-5){6}} \put(0,-1){$A$} \put(7.5,-1){$B$} \put(3.8,10.2){$C$} \put(1.2,5){$D$} \end{picture}\tabularnewline \begin{picture}(10,12)(0,-1) \thicklines \put(0,0){\line(1,0){8}} \put(0,0){\line(2,5){4}} \put(4,10){\line(2,-5){4}} \put(2,5){\line(6,-5){6}} \put(0,0){\line(2,1){5}} \put(3,7.5){\line(2,-5){2}} \put(5,2.5){\line(2,5){1}} \put(3,7.5){\line(6,-5){3}} \put(0,-1){$A$} \put(7.5,-1){$B$} \put(3.8,10.2){$C$} \put(1.2,5){$D$} \put(4.6,1.5){$E$} \put(6.2,5){$F$} \put(2.2,7.5){$G$} \end{picture} & \begin{picture}(12,12)(0,-1) \thicklines \put(0,0){\line(1,0){10}} \put(0,0){\line(0,1){10}} \put(0,10){\line(1,-1){10}} \put(0,0){\line(1,1){5}} \put(0,10){\line(1,-3){2.5}} \put(2.5,2.5){\line(1,0){5}} \put(2.5,2.5){\line(1,-1){2.5}} \put(7.5,2.5){\line(-1,-1){2.5}} \put(0,10.2){$A'$} \put(0,-1){$B'$} \put(9.5,-1){$C'$} \put(5.2,5.2){$D'$} \put(1.4,2.2){$E'$} \put(4.8,-1){$F'$} \put(7.7,2.7){$G'$} \end{picture} \tabularnewline \begin{picture}(10,13)(0,-1) \thicklines \put(0,0){\line(1,0){8}} \put(0,0){\line(2,5){4}} \put(4,10){\line(2,-5){4}} \put(2,5){\line(6,-5){6}} \put(2,5){\line(2,-5){2}} \put(0,-1){$A$} \put(7.5,-1){$B$} \put(3.8,10.2){$C$} \put(1.2,5){$D$} \put(3.7,-1){$H$} \end{picture}& \begin{picture}(12,13)(0,-1) \thicklines \put(0,0){\line(1,0){10}} \put(0,0){\line(0,1){10}} \put(0,10){\line(1,-1){10}} \put(0,0){\line(1,1){5}} \put(0,5){\line(1,0){5}} \put(0,10.2){$A'$} \put(0,-1){$B'$} \put(9.5,-1){$C'$} \put(5.2,5.2){$D'$} \put(0.1,4){$H'$} \end{picture}\tabularnewline \end{tabular}\end{center} Eine grün-Verfeinerung des Dreiecks $\left(A,B,C\right)$ (oben), gefolgt von einer grün-Verfeinerung von $\left(A,B,D\right)$ in Bezug auf die Referenzkante $\overline{BD}$ (Mitte) oder $\overline{AB}$ (unten). Die rechte Spalte zeigt das affine Bild auf dem Referenzdreieck $\left(A',B',C'\right)$. Der Algorithmus \ref{alg:adapNetzverfeinerung} vermeidet die mittlere Konfiguration durch $E\left(A,B,D\right)=\overline{AB}$. \end{remark} \begin{remark} Als Folgerung von Satz \ref{thm:algNetzverfeinerung}c treten in Dreiecken von $\mathcal{T}$ nur endlich viele Winkel auf, unabhängig von $k$, $\card\left(\mathcal{T}\right)$, etc. und nur abhängig von $\mathcal{T}^{\left(0\right)},\mathcal{E}^{\left(0\right)}$. Z.B. ist\[ h_{T}/\rho_{T}\leq C\left(\mathcal{T}^{\left(0\right)},\mathcal{E}^{\left(0\right)}\right)\] für $T\in\mathcal{T}$ mit $h_{T}=\mathrm{diam}\left(T\right)=2\cdot$Außenkreisradius und $\rho_{T}:=$Innenkreisradius. Man sagt: $\mathcal{T}$ ist \emph{lokal quasi-uniform}\index{quasi-uniform}. (Denn benachbarte Elemente $T,K\in\mathcal{T}$ mit $T\cap K\neq\emptyset$ erfüllen $\frac{h_{T}}{\rho_{K}}+\frac{h_{K}}{\rho_{T}}\lesssim1$ und $A\lesssim B$ bezeichnet $A\leq C\left(\mathcal{T}^{\left(0\right)},\mathcal{E}^{\left(0\right)}\right)B$). \end{remark} \begin{proof} [Beweisskizzen:] \begin{description} \item [\textmd{\emph{(a):}}]Das Konzept der Kantenmarkierungen vermeidet automatisch das Auftreten hängender Knoten. \item [\textmd{\emph{(b),(c):}}]Die Konstruktion von $\Phi_{K}$ ist offensichtlich und sofern $\mathcal{T}^{\left(\ell\right)}\left|_{K}\right.$ und $\mathcal{E}^{\left(\ell\right)}\left|_{K}\right.$ durch $\Phi_{K}$ auf eine Triangulierung von $T_{\mathrm{ref}}$ und Referenzkantenabbildung abgebildet wird, vererben sich die Referenzkanten wie in $\left\{ \Phi_{K}\left(T\right)\left|T\in\mathcal{T}^{\left(\ell+1\right)}\left|_{K}\right.\right.\right\} $ durch Wahl der längsten Kanten. \item [\textmd{\emph{(d)}}\textmd{:}]Die wesentlichen Beweisideen sind nachfolgend skizziert. \begin{defn} [Knotenabstand]\index{Knotenabstand}Zu $a,b\in\mathcal{N}:=$Menge der Knoten in $\mathcal{T}=\mathcal{T}^{\left(k\right)}$ definiere $\delta\left(a,b\right)$ als die kleinste ganze Zahl $J$ von Elementen $T_{1},\ldots,T_{J}\in\mathcal{T}$ mit $a\in T_{1}$, $T_{1}\cap T_{2}\neq\emptyset$, $T_{2}\cap T_{3}\neq\emptyset$, $\ldots$, $T_{J-1}\cap T_{J}\neq0$, $b\in T_{J}$, falls $a\neq b$, und $\delta\left(z,z\right):=0$ für $z\in\mathcal{N}$. \end{defn} \begin{remark*} $\left(\mathcal{N},\delta\right)$ ist ein metrischer Raum. \end{remark*} \begin{defn} [Verfeinerungslevel]\index{Verfeinerungslevel}Zu $T\in\mathcal{T}$ definiere $\ell\left(T\right)\geq0$ vermöge $K\in\mathcal{T}^{\left(0\right)}$, $T\subseteq K$ und\[ \ell\left(T\right):=\log_{2}\sqrt{\frac{\left|K\right|}{\left|T\right|}}.\] \end{defn} \begin{remark*} $\ell\left(T\right)\in\left\{ 0,\nicefrac{1}{2},1,\nicefrac{3}{2},2,\nicefrac{5}{2},\ldots\right\} =:\nicefrac{1}{2}\mathbb{N}_{0}$. \end{remark*} \begin{prop} Für $a,b\in\mathcal{N}\setminus\mathcal{N}^{\left(0\right)}$ mit $\delta\left(a,b\right)\leq1$, $a\in T$, $b\in K$, $T,K\in\mathcal{T}$ ist\[ \left|\ell\left(T\right)-\ell\left(K\right)\right|\leq3.\] \end{prop} \begin{proof} [Beweisidee]Patche im affinen Bild ansehen: Betrachte $a,b$ im Innern eines Makroelementes und analysiere 2 benachbarte Patche. Vorsicht bei Randpatchen. \end{proof} \begin{defn} Für $z\in\mathcal{N}$ definiere \[ d_{z}:=\min_{T\in\mathcal{T}}2^{\frac{3}{2}\delta\left(z,T\right)-\ell\left(T\right)}\qquad\textrm{mit }\delta\left(z,T\right):=\min_{x\in T}\delta\left(z,x\right).\] \end{defn} \begin{prop} \renewcommand{\labelenumi}{(\alph{enumi})} \begin{enumerate} \item Für $a,b\in\mathcal{N}$ mit $\delta\left(a,b\right)=1$ ist $d_{a}/d_{b}\leq\sqrt{8}$. \item Für $z\in\mathcal{N}\left(T\right)$, $T\in\mathcal{T}$ gilt \[ \frac{d_{z}^{2}}{\left|T\right|}+\frac{\left|T\right|}{d_{z}^{2}}\lesssim1.\] \end{enumerate} \end{prop} Als letztes Argument verbleibt einem die Analysis von lokalen Massenmatrizen (siehe auch C. Carstensen, Merging the Bramble-Pasciak-Steinbach and the Crouzeix-Thomee criterion for $H^{1}$-stability of the $L^{2}$-projection onto finite element spaces, Math. Comp., 71, 237, 157-163). \item [\textmd{\emph{(e)}}]Für den Rest des Beweises ersetze $\mathcal{M}^{\left(k\right)}$ durch die Menge \[ \tilde{\mathcal{M}}^{\left(k\right)}:=\left\{ T\in\mathcal{T}^{\left(k\right)}\left|\textrm{wenigstens eine der Kanten von $T$ ist markiert, d.h. }E\left(T\right)\cap\mathcal{M}^{\left(k\right)}\neq\emptyset\right.\right\} .\] \begin{defn} [$N_\alpha^\beta$]In einer Triangulierung $\mathcal{T}^{\left(\alpha\right)}$ definiere $N_{\alpha}^{\beta+1}:=N_{\alpha}\circ N_{\alpha}^{\beta}$, $N_{\alpha}^{1}:=N_{\alpha}$, $N_{\alpha}^{0}:=\textrm{Id}$ und für $T\in\mathcal{T}^{\left(\alpha\right)}$ bezeichne\[ N_{\alpha}\left(T\right):=\begin{cases} K & \textrm{falls ex. }K\in\mathcal{T}^{\left(\alpha\right)}\setminus\left\{ T\right\} \textrm{ mit }E^{\left(\alpha\right)}\left(T\right)=K\cap T\in\mathcal{E}^{\left(\alpha\right)}\textrm{ bzgl. }\mathcal{T}^{\left(\alpha\right)};\\ T & \textrm{sonst}.\end{cases}\] \end{defn} \begin{center}\setlength{\unitlength}{0.4cm} \begin{picture}(11,3.5) \put(3,0.7){$T$} \put(0,0){\line(1,0){7}} \put(0,0){\line(1,1){3.5}} \Thicklines \put(7,0){\line(-1,1){3.5}} \thinlines \put(3.5,3.5){\line(1,0){7}} \put(7,0){\line(1,1){3.5}} \put(4.9,2.4){$K=N_\alpha(T)$} \end{picture}\setlength{\unitlength}{0.4cm} \begin{picture}(11,4)(0,-.5) \put(1.6,0.5){$T=N_\alpha(T)$} \put(0,0){\line(1,0){7}} \put(0,0){\line(1,1){3.5}} \put(7,0){\line(2,-1){1}} \put(3.5,3.5){\line(-2,3){.6}} \Thicklines \put(7,0){\line(-1,1){3.5}} \put(5.5,2){$E(T)\subseteq\partial\Omega$} \end{picture}\end{center} \begin{prop} \label{pro:AdapNetzverfBewBeh1}Für alle $\alpha=1,2,\ldots,L$ und alle $T\in\mathcal{T}^{\left(\alpha\right)}\setminus\mathcal{T}^{\left(0\right)}$ existiert genau ein $\beta=0,1,\ldots,\alpha-1$, genau ein $K\in\mathcal{M}^{\left(\beta\right)}$ und genau ein $\gamma\in\mathbb{N}_{0}$, so daß $T\subseteq N_{\beta}^{\gamma}\left(K\right)$, d.h. $T$ ist aus der Verfeinerung von $N_{\beta}^{\gamma}\left(K\right)$ im Schritt zur Erzeugung von $\mathcal{T}^{\left(\beta\right)}$ hervorgegangen. \end{prop} \begin{proof} [Beweisidee]$N_{\beta}$ beschreibt eine Nachbarschaftsrelation im RGB-Abschluß: Ist $T\in\mathcal{T}^{\left(\beta\right)}$ markiert, so auch $E\left(T\right)$ (wegen Eigenschaft (R)), und damit ebenfalls $N_{\beta}\left(T\right)$. Setzt man dies fort, so sieht man, daß $\left\{ N_{\beta}^{\gamma}\left(T\right)\left|\gamma=0,1,2,\ldots\right.\right\} $ markiert sind. Zur Berechnung von $\mathcal{T}^{\left(\beta+1\right)}$ werden genau die Elemente in $\bigcup_{\gamma=0}^{\infty}\left\{ N_{\beta}^{\gamma}\left(T\right)\left|T\in\mathcal{M}^{\left(\beta\right)}\right.\right\} $ verfeinert. \end{proof} \begin{prop} \label{pro:AdapNetzverfBewBeh2}Für $T,K\in\mathcal{T}^{\left(\beta\right)}$ sei $T=N_{\beta}\left(K\right)$. Dann ist \[ -\frac{1}{2}\leq\ell\left(T\right)-\ell\left(K\right)\leq1.\] \end{prop} \begin{proof} Falls $T$ und $K$ affine Bilder von rechtwinkligen, gleichschenkligen Dreiecken auf einem Referenzelement sind, dann sind wir fertig. Alternativ sind $T$ und $K$ stückweise affine Bilder von rechtwinkligen, gleichschenkligen Dreiecken. \end{proof} \textbf{Bequemlichkeitshypothese}: Für alle $T,K\in\mathcal{T}^{\left(0\right)}$ gilt ($T\cap K\in\mathcal{E}^{\left(0\right)}$ $\Rightarrow$ $E\left(T\right)=E\left(K\right)$ oder $E\left(T\right)\neq T\cap K\neq E\left(K\right)$). Dann gilt in der Proposition \ref{pro:AdapNetzverfBewBeh2} (für $T,K\in\mathcal{T}^{\left(\beta\right)}$, $T=N_{\beta}\left(K\right)$) die Ungleichung\[ 0\leq\ell\left(T\right)-\ell\left(K\right)\leq\frac{1}{2}.\] \begin{prop} \label{pro:AdapNetzverfBewBeh3}Zu $T\in\mathcal{T}^{\left(L\right)}\setminus\mathcal{T}^{\left(0\right)}$ existiert genau eine endliche Folge $T_{1},\ldots,T_{s}$ (mit $s\geq1$) in $\mathcal{M}=\bigcup_{\ell=0}^{L-1}\mathcal{M}^{\left(\ell\right)}$ mit $T_{0}=T$ und für alle $\alpha=0,1,\ldots,s-1$ existiert ein $\beta\geq0$ und $\gamma\geq0$, so daß für $\alpha=0,1,2,\ldots,s-1$ gilt \[ \ell\left(T_{\alpha}\right)\leq\ell\left(T_{\alpha+1}\right)+\frac{3}{2},\] $T_{\alpha}$ ist Verfeinerung von $N_{\gamma}^{\beta}\left(T_{\alpha+1}\right)$ in $\mathcal{T}^{\left(\gamma\right)}$ und \[ \ell\left(T_{\alpha}\right)\geq\ell\left(T\right),\quad\textrm{aber }\ell\left(T_{s}\right)\leq\ell\left(T\right)-\frac{1}{2}.\] \end{prop} \begin{proof} Die Existenz der Folge $T_{1},\ldots,T_{s}$ folgt aus sukzessiver Anwendung von Proposition \ref{pro:AdapNetzverfBewBeh1}. Für $\alpha=0,1,\ldots,s-1$ wird $T_{\alpha}$ als Verfeinerung eines $\hat{T}_{\alpha}$ zunächst $\ell\left(T_{\alpha}\right)-\ell\left(\hat{T}_{\alpha}\right)\in\left\{ \nicefrac{1}{2},1,\nicefrac{3}{2}\right\} $ erfüllen ($\nicefrac{3}{2}$ ist nur für $T_{\alpha}\in\textrm{bisec}5\left(\hat{T}_{\alpha}\right)$ möglich). Die Level der $N_{\gamma}^{\beta}\left(T_{\alpha}\right)$ sind aber echt größer oder gleich $\ell\left(\hat{T}_{\alpha}\right)$. Also gilt\[ \ell\left(T_{\alpha+1}\right)\geq\ell\left(T_{\alpha}\right)-\frac{3}{2}.\qedhere\] \end{proof} \begin{remark} Für $\alpha=0,1,\ldots,s$ gilt \[ \ell\left(T_{\alpha}\right)-\ell\left(T\right)\in\mathcal{K}:=\left\{ -1,-\nicefrac{1}{2},0,\nicefrac{1}{2},\ldots\right\} =-1+\nicefrac{1}{2}\mathbb{N}_{0}\] (Der Beweis kombiniert $\ell\left(T_{s}\right)\leq\ell\left(T\right)\leq\ell\left(T_{s-1}\right)$ und $\ell\left(T_{s-1}\right)\leq\ell\left(T_{s}\right)+\frac{3}{2}$). \end{remark} \begin{prop} \label{pro:AdapNetzverfBewBeh4}Es existiert ein $c_{1}=c_{1}\left(\mathcal{T}^{\left(0\right)},\mathcal{E}^{\left(0\right)},E_{0}\right)>0$, so daß für alle $\alpha=0,1,\ldots,s-1$: \[ \diam\left(T_{\alpha}\cup T_{\alpha+1}\right)\leq c_{1}\diam\left(T\right)2^{\ell\left(T\right)-\ell\left(T_{\alpha+1}\right)}.\] \end{prop} \begin{proof} Es ist\begin{eqnarray*} \diam\left(T_{\alpha}\cup T_{\alpha+1}\right) & \leq & \diam\left(N_{\gamma}^{\beta}\left(T_{\alpha+1}\right)\cup T_{\alpha+1}\right)\qquad\textrm{(mit $\beta$ minimal)}\\ & \leq & \sum_{\mu=0}^{\beta}\diam\left(N_{\gamma}^{\mu}\left(T_{\alpha+1}\right)\cup N_{\gamma}^{\mu+1}\left(T_{\alpha+1}\right)\right)\qquad\textrm{(mit Dreiecksungl.)}\\ & \lesssim & \sum_{\mu=0}^{\beta}2^{-\ell\left(N_{\gamma}^{\mu+1}\left(T_{\alpha+1}\right)\right)}\qquad\textrm{(lokale Quasiuniformität)}\end{eqnarray*} Die Bequemlichkeitshypothese zeigt\[ \ell\left(N_{\gamma}^{\mu}\left(T_{\alpha+1}\right)\right)_{\mu=0,\ldots,\beta-1}=\left(\ell\left(T_{\alpha+1}\right),\ell\left(T_{\alpha+1}\right)+\frac{1}{2},\ell\left(T_{\alpha+1}\right)+1,\ldots\right),\] also ist\begin{align*} \diam\left(T_{\alpha}\cup T_{\alpha+1}\right) & \lesssim2^{-\ell\left(T_{\alpha+1}\right)}\,\left(1+2^{-\frac{1}{2}}+2^{-1}+2^{-\frac{3}{2}}+\ldots\right)\\ & \lesssim2^{-\ell\left(T_{\alpha+1}\right)}\\ & \lesssim\diam\left(T\right)2^{\ell\left(T\right)-\ell\left(T_{\alpha+1}\right)}.\qedhere\end{align*} \end{proof} \begin{defn} Definiere $c_{2}:=c_{1}\left(2^{\nicefrac{3}{2}}+\left(1-2^{-\nicefrac{1}{4}}\right)^{-1}\right)$ mit $c_{1}$ aus Proposition \ref{pro:AdapNetzverfBewBeh4} und\[ \Lambda\left(T,K\right):=\begin{cases} \left(\ell\left(K\right)-\ell\left(T\right)+\frac{5}{2}\right)^{-2} & \begin{array}{l} \textrm{falls }T\in\mathcal{T}^{\left(L\right)}\setminus\mathcal{T}^{\left(0\right)},K\in\mathcal{M},\ell\left(K\right)-\ell\left(T\right)\geq\frac{3}{2}\\ \textrm{und }\diam\left(T\cup K\right)\leq c_{2}\diam\left(T\right);\end{array}\\ 0 & \textrm{sonst.}\end{cases}\] \end{defn} \underbar{Beweisidee} für den Beweis von \emph{(e)}: $\Lambda$ erfüllt\begin{eqnarray*} & 1. & \forall K\in\mathcal{M}:\,\sum_{T\in\mathcal{T}^{\left(k\right)}\setminus\mathcal{T}^{\left(0\right)}}\Lambda\left(T,K\right)\lesssim1;\\ & 2. & \forall T\in\mathcal{T}^{\left(k\right)}\setminus\mathcal{T}^{\left(0\right)}:\,\sum_{K\in\mathcal{M}}\Lambda\left(T,K\right)\gtrsim1.\end{eqnarray*} Daraus folgt die Behauptung \emph{(e)}, denn\[ \card\left(\mathcal{T}^{\left(L\right)}\setminus\mathcal{T}^{\left(0\right)}\right)=\sum_{T\in\mathcal{T}^{\left(k\right)}\setminus\mathcal{T}^{\left(0\right)}}1\stackrel{2.}{\leq}\sum_{K\in\mathcal{M}}\sum_{T\in\mathcal{T}^{\left(k\right)}\setminus\mathcal{T}^{\left(0\right)}}\Lambda\left(T,K\right)\stackrel{1.}{\lesssim}\sum_{K\in\mathcal{M}}1=\card\left(\mathcal{M}\right).\] \begin{defn} [$m(j,k)$]Für fixiertes $T=T_{0}\in\mathcal{T}^{\left(L\right)}\setminus\mathcal{T}^{\left(0\right)}$ und in Proposition \ref{pro:AdapNetzverfBewBeh3} definierter Folge $T_{1},\ldots,T_{s}$ bezeichne \[ m\left(j,k\right):=\card\left\{ T_{\nu}\left|\nu=0,1,2,\ldots,j\textrm{ mit }\ell\left(T_{\nu}\right)=\ell\left(T\right)+k\right.\right\} \] für $j=0,1,2,\ldots,s$ und $k\in-\nicefrac{1}{2}+\mathcal{K}=\left\{ -\nicefrac{3}{2},-1,-\nicefrac{1}{2},0,\nicefrac{1}{2},\ldots\right\} $. \end{defn} \begin{prop} \label{pro:AdapNetzverfBewBeh5}Wenn ein $j\in\left\{ 1,2,\ldots,s\right\} $ mit\[ \sup_{\mu\in\nicefrac{1}{2}\mathbb{N}_{0}}m\left(j,\mu\right)2^{-\frac{\mu}{2}}\leq1\] existiert, dann gilt\[ \diam\left(T\cup T_{j}\right)\leq c_{2}\diam\left(T\right).\] \end{prop} \begin{proof} Mit der Dreiecksungleichung folgt für $j\in\left\{ 1,2,\ldots,s-1\right\} $\begin{align*} \diam\left(T_{j}\cup T_{0}\right) & \leq\sum_{\nu=0}^{j-1}\underbrace{\diam\left(T_{\nu+1}\cup T_{\nu}\right)}_{\leq c_{1}\diam\left(T\right)2^{\ell\left(T\right)-\ell\left(T_{\nu+1}\right)}\textrm{ mit Prop. \ref{pro:AdapNetzverfBewBeh4}}}\\ & \leq c_{1}\diam\left(T\right)\underbrace{\sum_{\nu=0}^{j-1}2^{-\mu\left(\nu+1\right)}}_{\sum_{\nu=1}^{j}2^{-\mu\left(\nu\right)}},\qquad\mu\left(\nu+1\right):=\ell\left(T_{\nu+1}\right)-\ell\left(T\right)\geq0\\ & \leq c_{1}\diam\left(T\right)\sum_{k\in\nicefrac{1}{2}\mathbb{N}}\underbrace{m\left(j,k\right)2^{-k}}_{\leq2^{-k/2}}\\ & \leq c_{1}\diam\left(T\right)\sum_{k\in\nicefrac{1}{2}\mathbb{N}}2^{-k/2}\\ & \leq c_{2}\diam\left(T\right)\qquad\textrm{mit }c_{2}\textrm{ wie oben definiert.}\end{align*} Für$j=s$ ist $\mu\left(s\right)\in\left\{ -\nicefrac{3}{2},-1,-\nicefrac{1}{2}\right\} $ und $m\left(s,\mu\left(s\right)\right)=1$. Die obige Abschätzung modifiziert sich daher und zeigt\[ \diam\left(T_{s}\cup T_{0}\right)\leq c_{1}\diam\left(T\right)\left(\frac{1}{1-2^{-\nicefrac{1}{4}}}+2^{\nicefrac{3}{2}}\right)\leq c_{2}\diam\left(T\right).\qedhere\] \end{proof} \begin{prop} [Eigenschaft 2. von $\Lambda$]Für alle $T\in\mathcal{T}^{\left(L\right)}\setminus\mathcal{T}^{\left(0\right)}$ ist\[ 1\lesssim\sum_{K\in\mathcal{M}}\Lambda\left(T,K\right).\] \end{prop} \begin{proof} \begin{description} \item [\textmd{1.~Fall:}]Es existiert ein $j\in\left\{ 1,\ldots,s\right\} $ mit \begin{equation} 1<\sup_{k\in\nicefrac{1}{2}\mathbb{N}_{0}}2^{-k/2}m\left(j,k\right).\label{eq:AdapNetzverfBewBeh6_1}\end{equation} O.B.d.A. sei $j\in\left\{ 1,\ldots,s\right\} $ minimal mit (\ref{eq:AdapNetzverfBewBeh6_1}) gewählt. Zu diesem fixierten $j$ existiert ein $k$ mit \begin{equation} 2^{k/2}2^{k/2}-1$ für $\mu=k>0$ mit (\ref{eq:AdapNetzverfBewBeh6_2}) folgt\[ \sum_{\nu=1}^{j-1}\Lambda\left(T_{\nu},T\right)\geq\left(k+\frac{5}{2}\right)^{-2}\left(2^{k/2}-1\right)\geq\min_{\mu\in\nicefrac{1}{2}\mathbb{N}}\left(\mu+\frac{5}{2}\right)^{-2}\left(2^{\mu/2}-1\right)=\frac{\left(2^{\nicefrac{1}{4}}-1\right)}{16}>0,\] denn die Funktion $x\mapsto\left(x+\frac{5}{2}\right)^{-2}\left(2^{x/2}-1\right)$ ist streng monoton wachsend für $x\geq0$ weil die Ableitung erfüllt\[ \frac{\partial}{\partial x}\left(x+\frac{5}{4}\right)^{-1}\left(2^{x}-1\right)=\left(x+\frac{5}{4}\right)^{-3}\left(2^{x}\left(\ln2\left(x+\frac{5}{4}\right)-1\right)+1\right)>0.\] \item [\textmd{2.~Fall:}]Für alle $\mu\in\nicefrac{1}{2}\mathbb{N}_{0}$ ist\[ m\left(5,\mu\right)\leq2^{\mu/2}.\] Nach Proposition \ref{pro:AdapNetzverfBewBeh5} folgt $\diam\left(T\cup T_{s}\right)\leq c_{2}\diam\left(T\right)$ und so\[ \Lambda\left(T_{s},T\right)=\left(\ell\left(T_{s}\right)-\ell\left(T\right)+\frac{3}{2}\right)^{-2}\geq1>0.\qedhere\] \end{description} \end{proof} \begin{prop} Für alle $K\in\mathcal{M}$ gilt\[ \sum_{T\in\mathcal{T}^{\left(L\right)}\setminus\mathcal{T}^{\left(0\right)}}\Lambda\left(T,K\right)\lesssim1.\] \end{prop} \begin{proof} Für fixiertes $K\in\mathcal{M}$ und $k\in\mathcal{K}$ definiere man\[ \mathcal{A}_{k}:=\left\{ T\in\mathcal{T}^{\left(L\right)}\setminus\mathcal{T}^{\left(0\right)}\left|\diam\left(T\cup K\right)\leq c_{2}\diam\left(T\right)\textrm{ und }\ell\left(T\right)=k\right.\right\} .\] Da $\left|T\right|\gtrsim2^{-2k}$ und $\bigcup\mathcal{A}_{k}\subseteq$Kugel mit Mittelpunkt $\textrm{mid}\left(T\right)$ und Radius \[ R:=\max_{T\in\mathcal{A}}c_{2}\diam\left(T\right)\lesssim2^{-k}\] folgt\[ a_{k}:=\card\left(\mathcal{A}_{k}\right)\leq\frac{\left|\bigcup\mathcal{A}\right|}{\min_{T\in\mathcal{A}_{k}}\left|T\right|}\lesssim\pi R^{2}2^{-2k}\lesssim1.\] Folglich gilt\[ \sum_{T\in\mathcal{T}^{\left(L\right)}\setminus\mathcal{T}^{\left(0\right)}}\Lambda\left(T,K\right)\leq\sum_{k\in\mathcal{K}}\frac{a_{k}}{\left(k+\nicefrac{5}{2}\right)^{2}}\lesssim\sum_{k=-\frac{3}{2}}^{\infty}\frac{1}{\left(k+\nicefrac{5}{2}\right)^{2}}\leq\infty\qedhere\] \end{proof} \end{description} Dies beendet den Beweis des Satzes \ref{thm:algNetzverfeinerung}. \end{proof} \section{Nichtkonforme und gemischte FEM} \begin{notation*} Ein FER $V_{h}\subseteq V=H_{0}^{1}\left(\Omega\right)$ heißt \emph{konform\index{konform}} im Zusammenhang mit elliptischen partiellen Differentialgleichungen 2ter Ordnung. Die bisherigen FEM waren alle konform. Nun betrachten wir einen FER $V_{h}\not\subseteq V$, der dann nicht konform ist, und \emph{nichtkonform\index{nichtkonform}} heißt. Abkürzung: NC:=nichtkonform (Englisch: nonconforming). \emph{Gemischte FEM\index{FEM!gemischt}} (Abkürzung MFEM, Englisch: mixed FEM) diskretisieren $-\Delta u=f$ als System von partiellen Differentialgleichungen erster Ordnung: $\nabla u=p$, $f+\mydiv p=0$. \end{notation*} \subsection{Gebrochene Sobolev-Räume} Englisch: broken Sobolev spaces Besser ist vielleicht die Bezeichnung \emph{stückweise Sobolev-Räume}. \begin{defn} [$H^1(\omega)$]Für \index{Sobolev-Raum}ein nichtleeres Gebiet $\omega$ im $\mathbb{R}^{n}$ definiere\[ H^{1}\left(\omega\right):=\left\{ f\in L^{2}\left(\omega\right)\left|f\textrm{ ist schwach diff.bar und }Df\in L^{2}\left(\omega;\mathbb{R}^{n}\right)\right.\right\} \] mit Sobolev-Norm\index{Sobolev-Norm}\[ \left\Vert \cdot\right\Vert _{1,2}:=\left\Vert \cdot\right\Vert _{H^{1}\left(\omega\right)}\] und Halbnorm\[ \left|\cdot\right|_{1,2}:=\left|\cdot\right|_{H^{1}\left(\omega\right)}:=\left\Vert D\cdot\right\Vert _{L^{2}\left(\omega\right)}.\] \end{defn} \begin{remark} \begin{enumerate} \item $H^{1}\left(\omega\right)$ ist ein Hilbert-Raum. \item $H^{1}\left(\omega\right)\not\subseteq C\left(\omega\right)$ für $n\geq2$. \item Für zwei Dreiecke $T_{+}$, $T_{-}$ im $\mathbb{R}^{2}$, $n=2$, mit gemeinsamer Kante $E=T_{+}\cap T_{-}$ und 2 Funktionen $f_{+}$ und $f_{-}$, $f_{\pm}\in H^{1}\left(T_{\pm}\right):=H^{1}\left(\textrm{Inneres}\left(T_{\pm}\right)\right)$, $\omega_{E}:=\textrm{Inneres}\left(T_{+}\cup T_{-}\right)$ definiere vermöge\[ f\left(x\right):=\begin{cases} f_{+}^{*}\left(x\right) & \textrm{falls }x\in T_{+}\setminus E\\ f_{-}^{*}\left(x\right) & \textrm{falls }x\in T_{-}\setminus E\end{cases}\] ein $f$ in $L^{2}\left(\omega_{E}\right)$. Dann gilt $f\in H^{1}\left(\omega_{E}\right)\Leftrightarrow\left[f\right]_{E}\left(x\right)=0$ für alle $x$ in $E$ außerhalb einer Menge vom eindimensionalen Lebesgue-Maß 0. Für den Sprung $\left[f\right]_{E}$ von $f$ über $E$ definiere\begin{eqnarray*} \left[f\right]_{E}\left(x\right) & := & \lim_{\substack{T_{+}\ni x_{+}\rightarrow x\\ T_{-}\ni x_{-}\rightarrow x} }\left(f^{*}\left(x_{+}\right)-f^{*}\left(x_{-}\right)\right),\\ \left[f\right]_{E}\left(x\right) & = & f_{+}^{*}\left(x\right)-f_{-}^{*}\left(x\right),\end{eqnarray*} wobei\[ f_{\pm}^{*}\left(x\right)=\begin{cases} {\displaystyle \lim_{\delta\rightarrow0}\intm_{B\left(x,\delta\right)\cap T_{\pm}}f\left(y\right)dy} & \textrm{falls der Limes existiert,}\\ 0 & \textrm{sonst.}\end{cases}\] \begin{proof} [Beweisidee] \begin{enumerate} \item Sprungsatz (vgl. unten) \item Partielle Integration: Für alle $\varphi\in\mathcal{D}\left(\omega_{E}\right)^{n}$:\[ -\int_{\omega_{E}}f\mydiv\varphi dx=-\int_{T_{+}}f_{+}\mydiv\varphi dx-\int_{T_{-}}f_{-}\mydiv\varphi dx\] Bezeichne mit $\nu_{+}$ die äußere Normale. Dann\[ \int_{T_{+}}f_{+}\mydiv\varphi dx=\int_{T_{+}}\left(Df_{+}\right)\cdot\varphi dx-\int_{\partial T_{+}}f_{+}^{*}\varphi\cdot\nu_{+}ds,\] also, für $D_{h}f$ stückweise durch $Df_{\pm}$ definiert,\[ -\int_{\omega_{E}}f\mydiv\varphi dx=\int_{\omega_{E}}D_{h}f\cdot\varphi dx-\int_{E}\underbrace{\left(f_{+}^{*}\nu_{+}+f_{-}^{*}\nu_{-}\right)}_{=\left(f_{+}^{*}-f_{-}^{*}\right)\nu_{E}=0\textrm{ für }\nu_{+}=:\nu_{E}=-\nu_{-}\textrm{ auf }E}\varphi ds.\] Folglich ist der stückweise definierte Gradient gleich der schwachen Ableitung.\qedhere \end{enumerate} \end{proof} \end{enumerate} \end{remark} \begin{defn} [NCFER]\index{NCFER}Für eine reguläre Triangulierung $\mathcal{T}$ von $\Omega\subseteq\mathbb{R}^{2}$ mit Kantenmenge $\mathcal{E}$ und $\mathcal{E}_{\partial\Omega}:=\left\{ E\in\mathcal{E}\left|E\subseteq\partial\Omega\right.\right\} $ definiere\begin{eqnarray*} H^{1}\left(\mathcal{T}\right) & := & \left\{ f\in L^{2}\left(\Omega\right)\left|\forall T\in\mathcal{T}\quad f\left|_{T}\in H^{1}\left(T\right)\right.\right.\right\} \equiv\prod_{T\in\mathcal{T}}H^{1}\left(T\right)\\ P_{1}\left(\mathcal{T}\right) & := & \left\{ f\in L^{2}\left(\Omega\right)\left|\forall T\in\mathcal{T}\quad f\left|_{T}\in P_{1}\left(T\right)\right.\right.\right\} \\ CR\left(\mathcal{T}\right) & := & \left\{ f\in P_{1}\left(\mathcal{T}\right)\left|\forall E\in\mathcal{E}\quad f\textrm{ ist stetig bei mid}\left(E\right)\right.\right\} \\ CR_{0}\left(\mathcal{T}\right) & := & \left\{ f\in CR\left(\mathcal{T}\right)\left|\forall E\in\mathcal{E}_{\partial\Omega}\quad f\left(\textrm{mid}\left(E\right)\right)=0\right.\right\} \end{eqnarray*} \end{defn} \begin{remark} \begin{enumerate} \item CR steht für \emph{Crouzeix-Raviart}\index{Crouzeix-Raviart}. Der Raum $CR_{0}\left(\mathcal{T}\right)=:V_{h}\not\subset V$ (für $\card\mathcal{T}>1$) ist der einfachste NCFER. \item Die Stetigkeitsbedingungen an $f$ in $V$ sind für $f_{h}\in CR_{0}\left(\mathcal{T}\right)$ abgeschwächt im Integralmittel:\begin{eqnarray*} \forall E\in\mathcal{E}_{\Omega}:=\mathcal{E}\setminus\mathcal{E}_{\partial\Omega} & & \int_{E}\left[f_{h}\right]_{E}ds=0\\ \textrm{und }\forall E\in\mathcal{E}_{\partial\Omega} & & \int_{E}fds=0.\end{eqnarray*} \item $Df_{h}$ existiert im Distributionensinne, ist i.a. aber keine $L^{p}$-Funktion, d.h. i.a. ist $f_{h}$ nicht schwach differenzierbar. $D_{h}f_{h}:=$stückweiser Gradient existiert für alle $f_{h}\in H^{1}\left(\mathcal{T}\right)$, z.B. für $f\in CR\left(\mathcal{T}\right)\subsetneqq H^{1}\left(\mathcal{T}\right)$. (alternative Notation: $D_{\mathcal{T}}f_{h}$) \item $P_{1}\left(\mathcal{T}\right)\cap C\left(\Omega\right)=:P_{1}\textrm{-FER}\subset CR\left(\mathcal{T}\right)=:P_{1}^{\textrm{NC}}\textrm{-FER}.$ \item $P_{1}\left(\mathcal{T}\right)\cap H_{0}^{1}\left(\Omega\right)\subset CR_{0}\left(\mathcal{T}\right)$. \end{enumerate} \end{remark} \subsection{NCFEM} \begin{defn} [CRFEM]Die \emph{Crouzeix-Raviart FEM (CRFEM)}\index{CRFEM} zum Poisson-Problem $-\Delta u=f$ in $\Omega$, $u=0$ auf $\partial\Omega$ bzgl. einer regulären Triangulierung $\mathcal{T}$ von $\Omega$ lautet\[ \exists!u_{h}\in V_{h}:=CR_{0}\,\forall v_{h}\in V_{h}\quad a_{h}\left(u_{h},v_{h}\right)=F\left(v_{h}\right)\tag{CRFEM}\] Hier ist\begin{eqnarray*} a_{h}\left(\tilde{u}_{h},\tilde{v}_{h}\right) & := & \int_{\Omega}D_{h}\tilde{u}_{h}\cdot D_{h}\tilde{v}_{h}dx,\\ F\left(\tilde{v}_{h}\right) & := & \int_{\Omega}f\left(x\right)\tilde{v}_{h}\left(x\right)dx\end{eqnarray*} für alle $\tilde{u}_{h},\tilde{v}_{h}\in H^{1}\left(\mathcal{T}\right)$. \end{defn} \begin{proof} [Beweis der Eindeutigkeit] Falls $u_{h}\in V_{h}$ erfüllt $a\left(u_{h},v_{h}\right)=0$ für alle $v_{h}\in V_{h}$, folgt $\left\Vert D_{h}u_{h}\right\Vert _{L^{2}\left(\Omega\right)}=0$. Dann ist $u_{h}\left|_{T}\right.=\textrm{const}\left(T\right)$ für alle $T\in\mathcal{T}$. Da also $\left[u_{h}\right]_{E}=\textrm{const}$ und $\int_{E}\left[u_{h}\right]_{E}ds=0$ für alle $E\in\mathcal{E}$, folgt $\left[u_{h}\right]_{E}=0$ und $u_{h}=0$ auf $\partial\Omega$. Also ist $u_{h}\equiv0$. \end{proof} \begin{remark} (CRFEM) ist ein lineares Gleichungssystem. Aus der Eindeutigkeit von Lösungen folgt auch deren Existenz! \end{remark} \subsection{Nodale Basis von CRFER} Bezeichne mit\[ \mathcal{M}:=\left\{ \textrm{mid}\left(E\right)\left|E\in\mathcal{E}\right.\right\} \] die Menge der Kantenmittelpunkt in einer Triangulierung $\mathcal{T}$. Die Werte $\left(u_{h}\left(m\right)\right)_{m\in\mathcal{M}}$ bestimmen $u_{h}$ eindeutig in $CR\left(\mathcal{T}\right)$ durch stückweise lineare Interpolation. \begin{defn} [nodale Basis von CRFER]Zu $E\in\mathcal{E}$ mit Mittelpunkt $m:=\textrm{mid}\left(E\right)$ definiere $\psi_{E}$ in $CR\left(\mathcal{T}\right)$ vermöge $\psi_{E}\left(m\right)=1$ und $\psi_{E}\left(n\right)=0$ für alle $n\in\mathcal{M}\setminus\left\{ m\right\} $ (und elementweise lineare Interpolation dieser Werte). $\left(\psi_{E}\right)_{E\in\mathcal{E}}$ heißt \emph{nodale Basis\index{nodale Basis}} von $CR\left(\mathcal{T}\right)$. $\mathcal{E}_{\Omega}:=\mathcal{E}\setminus\mathcal{E}_{\partial\Omega}$. $\left(\psi_{E}\right)_{E\in\mathcal{E}_{\Omega}}$ heißt \emph{nodale Basis} von $CR_{0}\left(\mathcal{T}\right)$. \end{defn} \begin{remark} Es gilt\begin{eqnarray*} \myspan\left\{ \psi_{E}\left|E\in\mathcal{E}\right.\right\} & = & CR\left(\mathcal{T}\right),\\ \myspan\left\{ \psi_{E}\left|E\in\mathcal{E}_{\Omega}\right.\right\} & = & CR_{0}\left(\mathcal{T}\right).\end{eqnarray*} \end{remark} \begin{remark} Es ist $\supp\psi_{E}=\overline{\omega_{E}}=T_{+}\cup T_{-}$ für $E\in\mathcal{E}_{\Omega}$. Es gilt $u_{h}\in CR_{0}\left(\mathcal{T}\right)$, gdw. ein $\left(x_{E}\right)_{E\in\mathcal{E}_{\Omega}}$ existiert, so daß $u_{h}=\sum_{E\in\mathcal{E}_{\Omega}}x_{E}\psi_{E}$. \end{remark} \begin{defn} [lokale STEMA]\index{STEMA}Für ein Dreieck $T$ mit NC nodalen Basisfunktionen $\psi_{1}$, $\psi_{2}$, $\psi_{3}$ ist\[ \mathrm{NCSTEMA}\left(T\right):=\left(\int_{T}D\psi_{j}\cdot D\psi_{k}dx\right)_{j,k=1,2,3}\in\mathbb{R}^{3\times3}.\] \end{defn} \begin{prop} Es gilt\[ \mathrm{NCSTEMA}\left(T\right)=4\,\mathrm{STEMA}\left(T\right)\] für die lokale Steifigkeitsmatrix der $P_{1}$-FEM $\mathrm{STEMA}\left(T\right)$ von $T$. \end{prop} \begin{proof} [Beweisidee]Auf dem Teildreieck $T_{4}:=\conv\left\{ M_{1},M_{2}M_{3}\right\} $ ist $\left(D\psi_{j}\cdot D\psi_{k}\right)$ (auf $T$ konstant) gleich dem Eintrag für die konforme FEM zu den Baryzentrischen Koordinaten $\psi_{1},\psi_{2},\psi_{3}$. Der Faktor 4 erscheint durch Skalierung und die Umrechnung von $M_{j}=\left(P_{j+1}+P_{j+2}\right)/2$ auf die Eckpunkte $P_{j}$. \end{proof} \chapter{Konvergenzanalysis} \begin{ziel*} Fehlerabschätzungen für FEM \begin{center}\begin{tabular}{|l|l|} \hline a$\tilde{\;}$priori& a$\tilde{\;}$posteriori\tabularnewline \hline vor der Rechung& nach der Rechnung\tabularnewline \hline $u$ glatt, scheinbar bekannt& $u$ völlig unbekannt und kommt auf RHS \underbar{nicht} vor\tabularnewline $u_{h}$ unbekannt kommt auf RHS \underbar{nicht} vor& $u_{h}$ bekannt und geht in RHS ein\tabularnewline \hline \end{tabular}\end{center} \end{ziel*} allgemeine Argumente: Quasi-Optimalität spezielle Argumente: Approximationsaussage $\left\Vert \left|u-Iu\right|\right\Vert $ etc. \section{Sobolev-Räume} \begin{defn} [$H^m$]Für ein nichtleeres Gebiet $\Omega$ im $\mathbb{R}^{n}$ mit Rand $\partial\Omega$, $m\in\mathbb{N}$, $n\in\mathbb{N}$, $m,n\geq1$, $H^{0}\left(\Omega\right)=L^{2}\left(\Omega\right)$, bezeichne den Vektorraum\[ H^{m}\left(\Omega\right):=\left\{ u\in H^{m-1}\left(\Omega\right)\left|Du\textrm{ ex. im schwachen Sinn und }Du\in H^{m-1}\left(\Omega;\mathbb{R}^{n}\right)\right.\right\} \] als den \emph{Sobolev-Raum\index{Sobolev-Raum}} $m$-ter Ordnung. $\left\Vert \cdot\right\Vert _{m,2}$ bzw. $\left|\cdot\right|_{m,2}$ heißt \emph{Sobolev-Norm\index{Sobolev-Norm}} bzw. \emph{-Halbnorm}. \end{defn} \begin{thm} Der Raum $H^{m}\left(\Omega\right)$ ist ein Hilbert-Raum. \end{thm} \begin{proof} Wie im eindimensionalen Fall (Satz \ref{thm:Sobolev1D_BR_HR}, Seite \pageref{thm:Sobolev1D_BR_HR}). \end{proof} \begin{thm} [Spursatz]\index{Spursatz}Für ein Lipschitz-Gebiet ist die Abbildung \[ \gamma:H^{1}\left(\Omega\right)\rightarrow L^{2}\left(\partial\Omega\right),\qquad u\mapsto u^{*}\left|_{\partial\Omega}\right.,\] wohldefiniert, linear und stetig. \end{thm} \begin{remark} Man sagt, {}``$H^{1}$-Funktionen haben Spuren'' und $\gamma$ heißt \emph{Spuroperator}\index{Spuroperator}. \end{remark} \begin{proof} Liegt tiefer, insbesondere weil i.a. $L^{2}\left(\partial\Omega\right)$ bzgl. des $\left(n-1\right)$-dimensionalen Hausdorff-Maßes $\mathcal{H}_{n-1}$ definiert ist. Für stückweise affine Ränder aber ist $\mathcal{H}_{n-1}$ gleich dem (transformierten) $\left(n-1\right)$-dimensionalen Lebesgue-Maß $\mathcal{L}_{n-1}$. Details z.B. in {[}EG{]}. \end{proof} \begin{thm} [partielle Integration]\index{Partielle Integration}Für ein beschränktes Lipschitz-Gebiet $\Omega$ mit Rand $\Gamma:=\partial\Omega$ ist der äußere Einheitsnormalenvektor $\nu\left(x\right)$ für $\mathcal{H}_{n-1}$-fast alle $x$ auf $\Gamma$ im klassischen Sinne als Limes von Differenzenquotienten definiert und für alle $u,v_{1},\ldots,v_{n}\in H^{1}\left(\Omega\right)$ ist\[ \int_{\Omega}u\mydiv v\, dx+\int_{\Omega}v\cdot Du\, dx=\int_{\partial\Omega}u\left(v\cdot\nu\right)ds,\] wobei $u$ und $v=\left(v_{1},\ldots,v_{n}\right)$ auf $\partial\Omega$ im oben genannten Sinn als Spuren verstanden werden (d.h. \emph{RHS}$=\int_{\partial\Omega}u^{*}\left(x\right)v^{*}\left(x\right)\cdot\nu\left(x\right)ds$, $ds=d\mathcal{H}_{n-1}\left(x\right)$) \end{thm} \begin{proof} Beweisideen in der Übung. Für Details siehe {[}EG{]} etc. \end{proof} \begin{thm} [Meyers]\index{Meyers, Satz}Für\[ \mathcal{D}\left(\Omega\right):=\left\{ f\in C^{\infty}\left(\mathbb{R}^{n}\right)\left|\supp f\Subset\Omega\right.\right\} =C_{c}^{\infty}\left(\Omega\right)\] gilt \renewcommand{\labelenumi}{(\alph{enumi})} \begin{enumerate} \item $\mathcal{D}\left(\mathbb{R}^{n}\right)$ ist dicht in $H^{1}\left(\Omega\right)$ und \[ \overline{\mathcal{D}\left(\mathbb{R}^{n}\right)}^{\left\Vert \cdot\right\Vert _{H^{1}\left(\Omega\right)}}=H^{1}\left(\Omega\right).\] \item Es gilt\[ H_{0}^{1}\left(\Omega\right)=\left\{ u\in H^{1}\left(\Omega\right)\left|\gamma u=0\right.\right\} \stackrel{!}{=}\overline{\mathcal{D}\left(\Omega\right)}^{\left\Vert \cdot\right\Vert _{H^{1}\left(\Omega\right)}}.\] \end{enumerate} \end{thm} \begin{proof} Siehe {[}EG{]}, es werden Regularisierungen benutzt. \end{proof} \begin{remark} Es ist\[ H^{1}\left(\mathbb{R}^{n}\right)=\left\{ f\in L^{2}\left(\mathbb{R}^{n}\right)\left|\begin{array}{l} \forall j=1,2,\ldots n,\textrm{ für fast alle }x'\in\mathbb{R}^{n-1}\textrm{ ist die Funktion}\smallskip\\ f\left(x_{1}',\ldots,x_{j-1}',\cdot,x_{j}',\ldots,x_{n-1}'\right)\textrm{ absolut stetig und}\smallskip\\ \frac{\partial f}{\partial x_{j}}:=\textrm{Ableitung von }f\left(x_{1}',\ldots,x_{j-1}',\cdot,x_{j}',\ldots,x_{n-1}'\right)\smallskip\\ \textrm{ist definiert als Funktion in }L^{2}\left(\mathbb{R}^{n}\right)\end{array}\right.\right\} \] Beweis mit Fubini in {[}EG{]}. \end{remark} \begin{thm} [Rellich]\label{thm:Rellich}\index{Rellich, Satz}Die Einbettung $H^{1}\left(\Omega\right)\hookrightarrow L^{2}\left(\Omega\right)$ ist kompakt, d.h. jede in $H^{1}\left(\Omega\right)$ beschränkte Folge $\left(f_{j}\right)$ hat eine in $L^{2}\left(\Omega\right)$ konvergente Teilfolge (d.h. es existiert ein $g\in H^{1}\left(\Omega\right)$ und eine Teilfolge $\left(f_{j_{k}}\right)$ mit $\lim_{k\rightarrow\infty}\left\Vert g-f_{j_{k}}\right\Vert _{L^{2}\left(\Omega\right)}=0$). \end{thm} \begin{proof} [Beweisidee für den eindimensionalen Fall]Sei $\left(f_{j}\right)$ eine beschränkte Folge in $H^{1}\left(\Omega\right)$, $\Omega=\left(a,b\right)$.\[ m_{j}:=\intm_{\Omega}f_{j}\left(x\right)dx\rightarrow m\] in $\mathbb{R}$. Durch Übergang zu $f_{j}-m_{j}$ sieht man, daß man o.B.d.A. $m{}_{j}=0$ annehmen kann. Nun ist\[ \left|f_{j}\left(x\right)-f_{j}\left(y\right)\right|=\left|\int_{x}^{y}f_{j}'\left(z\right)dz\right|\leq\left|x-y\right|^{\frac{1}{2}}\underbrace{\left\Vert f_{j}'\right\Vert _{L^{2}\left(\Omega\right)}}_{\leq M}.\] Dann ist $\left(f_{j}\right)$ \underbar{gleichgradig stetig} auf dem Kompaktum $\left[a,b\right]=\bar{\Omega}$. Da $f_{j}$ eine Nullstelle hat, ist $f_{j}$ beschränkt unabhängig von $j$ (denn für eine Nullstelle $\xi$ von $f_{j}$ ist $\left|f_{j}\left(x\right)\right|=\left|\int_{\xi}^{x}f_{j}'\left(z\right)dz\right|\leq\left(b-a\right)^{\frac{1}{2}}M$). Mit dem Satz von Arzela-Ascoli existiert eine Teilfolge $\left(f_{j_{k}}\right)\rightarrow g$ in $C\left[a,b\right]$. \end{proof} \begin{thm} [Poincar\'e-Ungleichung]\index{Poincar\'e-Ungleichung}Für ein beschränktes, nichtleeres Gebiet $\Omega$ existiert eine Konstante $c_{P}\left(\Omega\right)>0$, so daß\[ \forall f\in H^{1}\left(\Omega\right)\,\exists m\in\mathbb{R}\quad\left\Vert f-m\right\Vert _{L^{2}\left(\Omega\right)}\leq c_{P}\left(\Omega\right)\,\left\Vert Df\right\Vert _{L^{2}\left(\Omega\right)}.\] \end{thm} \begin{proof} [Beweis (indirekt)]Andernfalls existiert eine Folge $f_{j}\in H^{1}\left(\Omega\right)$ mit \[ \intm_{\Omega}f_{j}\left(x\right)dx=0\] (dies fixiert $m_{j}$) und \[ 1=\left\Vert f_{j}\right\Vert _{2},\] aber\[ \left|f_{j}\right|_{1,2}\leq\nicefrac{1}{j},\qquad\textrm{für }j=1,2,\ldots\] Also ist $\left(f_{j}\right)$ beschränkt in $H^{1}\left(\Omega\right)$. Aus dem Satz \ref{thm:Rellich} von Rellich folgt, daß eine Teilfolge $\left(f_{j_{k}}\right)$ und ein $f\in H^{1}\left(\Omega\right)$ mit\[ \left\Vert f-f_{j_{k}}\right\Vert _{2}\rightarrow0.\] Dann ist $\left\Vert f\right\Vert _{2}=1.$ Wegen $\left|f_{j_{k}}\right|_{1,2}\rightarrow0$ folgt $Df=0$ fast überall. Da $\Omega$ zusammenhängend ist, folgt $f=\textrm{konst.}$ (Technisch müßte man diese Aussage noch für den schwachen Ableitungsbegriff zeigen (z.B. mit Regularisierung)). Wegen \[ \intm_{\Omega}f\left(x\right)dx=0\] folgt dann $f\equiv0$, also $\left\Vert f\right\Vert _{2}=0$. Widerspruch. \end{proof} \begin{thm} [Friedrichs-Ungleichung]\index{Friedrichs-Ungleichung}Für ein Gebiet $\Omega$ der Breite $\leq b$ (d.h. $\Omega$ liegt zwischen 2 parallelen Hyperebenen mit Abstand $b>0$) und $f\in H_{0}^{1}\left(\Omega\right)$ gilt\[ \left\Vert f\right\Vert _{L^{2}\left(\Omega\right)}\leq\frac{b}{\pi}\left\Vert Df\right\Vert _{L^{2}\left(\Omega\right)}.\] \end{thm} \begin{cor} Die Abbildung\[ a\left(u,v\right):=\int_{\Omega}Du\cdot Dvdx\] ist ein Skalarprodukt auf $H_{0}^{1}\left(\Omega\right)$ mit Norm $\left|\cdot\right|_{1,2}\approx\left\Vert \cdot\right\Vert _{1,2}$. \end{cor} \begin{proof} O.B.d.A. ist $\Omega\subseteq\left(0,b\right)\times\mathbb{R}^{n-1}=:S$ und $f\in\mathcal{D}\left(\Omega\right)$ auf $S$ durch Null fortgesetzt. Für jeden Parameter $x'\in\mathbb{R}^{n-1}$ ist $f\left(\cdot,x'\right)\in H_{0}^{1}\left(0,b\right)$. Also ist\[ \left\Vert f\left(\cdot,x'\right)\right\Vert _{L^{2}\left(a,b\right)}\leq\frac{b}{\pi}\left\Vert \frac{\partial f}{\partial x_{1}}\left(\cdot,x'\right)\right\Vert _{L^{2}\left(a,b\right)}\] nach der eindimensionalen Friedrichsungleichung (\ref{eq:Friedrichs}) (Seite \pageref{eq:Friedrichs}, der Beweis von $C_{F}=\frac{b}{\pi}$ folgt später). Quadratur und Integration über $x'\in\mathbb{R}^{n-1}$,\[ \int_{\mathbb{R}^{n-1}}\left\Vert f\left(\cdot,x'\right)\right\Vert _{L^{2}\left(a,b\right)}^{2}dx'\leq\int_{\mathbb{R}^{n-1}}\left(\frac{b}{\pi}\right)^{2}\left\Vert \frac{\partial f}{\partial x_{1}}\left(\cdot,x'\right)\right\Vert _{L^{2}\left(a,b\right)}^{2}dx'\] zeigt die Behauptung. \end{proof} \section{Poincar\'e-Ungleichung} \begin{ziel*} Beweis von $c_{P}\left(\Omega\right)\leq\frac{1}{\pi}\diam\left(\Omega\right)$ für ein konvexes Gebiet $\Omega\subseteq\mathbb{R}^{n}$. \end{ziel*} \underbar{Hilfsmittel}: Eindimensionale Abschätzungen mit Gewichten. \begin{thm} [Payne-Weinberger, 1961]\label{thm:PayneWeinberger1}$\rho$ sei eine konkave Funktion auf $\left(a,b\right)$ mit \[ 0\leq\rho_{0}\leq\rho\left(x\right)\leq\rho_{1}<\infty\qquad\textrm{für alle }x\in\left[a,b\right]\] und Konstanten $a0$, denn sonst betrachte $\rho+\varepsilon$ für $\varepsilon>0$ und lasse am Schluß $\varepsilon\rightarrow0$. \end{enumerate} Für den Rest des Beweises sei also: $a=0$, $b=1$, $0<\rho_{0}\leq\rho$, $\rho$ konkav mit $\rho\in C^{2}\left[a,b\right]$. Schwache Formen: $L_{\rho}$ sei definiert als der Hilbert-Raum $L^{2}\left(0,1\right)$ mit Skalarprodukt \[ \left(\cdot,\cdot\right)_{\rho}:=\int_{0}^{1}\rho\left(x\right)\cdot\cdot\; dx\] mit Norm \[ \left\Vert \cdot\right\Vert _{\rho}:=\left\Vert \rho^{\frac{1}{2}}\,\cdot\right\Vert _{2}.\] Der Operator $M:L_{\rho}\rightarrow L_{\rho}$ ist selbstadjungiert. Definiere nun weiter die Operatoren $S_{\pm}:L^{2}\left(0,1\right)\rightarrow L^{2}\left(0,1\right)$ vermöge\begin{eqnarray*} \left(S_{+}f\right)\left(x\right) & := & \int_{0}^{x}f\left(y\right)dy,\\ \left(S_{-}f\right)\left(x\right) & := & \int_{x}^{1}f\left(y\right)dy,\end{eqnarray*} und \[ T:=\left(1-M\right)S_{+}:L^{2}\left(0,1\right)\rightarrow L^{2}\left(0,1\right).\] Dann sind $M$, $S_{+}$, $S_{-}$, $T:L^{2}\left(0,1\right)\rightarrow L^{2}\left(0,1\right)$ linear und beschränkt. \underbar{Übungsaufgaben}: \begin{enumerate} \item $M:L_{\rho}\rightarrow L_{\rho}$ ist selbstadjungiert und kompakt. \item $S_{\pm}$ ist adjungiert zu $S_{\mp}$in $L^{2}\left(0,1\right)$ und $S_{\pm}$ ist kompakt. \item $T^{*}:=\rho^{-1}S_{-}\rho\left(1-M\right)$ ist adjungiert zu $T$ in $L_{\rho}$. \item $A:=T^{*}T:L_{\rho}\rightarrow L_{\rho}$ ist linear, beschränkt, selbstadjungiert, kompakt und positiv semidefinit. \item $\left\Vert T\right\Vert _{L\left(L_{\rho},L_{\rho}\right)}^{2}\leq\left\Vert A\right\Vert _{L\left(L_{\rho},L_{\rho}\right)}$ \end{enumerate} Spektraltheorie kompakter selbstadjungierter Operatoren: Die Operatornorm $\lambda:=\left\Vert A\right\Vert _{L\left(L_{\rho},L_{\rho}\right)}>0$ ist ein Eigenwert von $A$ mit Eigenvektor $u\in L_{\rho}$, $\left\Vert u\right\Vert _{\rho}=1$, und $Au=\lambda u$. \begin{prop} \label{pro:Poincare_Beh3}Für alle $f\in H^{1}\left(0,1\right)$ gilt\[ \min_{m\in\mathbb{R}}\int_{0}^{1}\rho\,\left(f-m\right)^{2}dx\leq\lambda\int_{0}^{1}\rho\,\left(f'\right)^{2}dx.\] \end{prop} \begin{proof} O.B.d.A. sei $f\in H^{1}\left(0,1\right)$ mit $f\left(0\right)=0$. Dann ist\[ S_{+}f'=f\] und \[ \left\Vert Tf'\right\Vert _{\rho}=\left\Vert \left(1-M\right)f\right\Vert _{\rho}=\left(\min_{m\in\mathbb{R}}\int_{0}^{1}\rho\,\left(f-m\right)^{2}dx\right)^{\nicefrac{1}{2}}.\] Weiterhin ist $\left\Vert Tf'\right\Vert _{\rho}\leq\left\Vert T\right\Vert _{L\left(L_{\rho},L_{\rho}\right)}\left\Vert f'\right\Vert _{\rho}$, also\[ \min_{m\in\mathbb{R}}\int_{0}^{1}\rho\left(f-m\right)^{2}dx\leq\left\Vert T\right\Vert _{L\left(L_{\rho},L_{\rho}\right)}^{2}\left\Vert f'\right\Vert _{\rho}^{2}\stackrel{\textrm{5.}}{\leq}\underbrace{\left\Vert A\right\Vert _{L\left(L_{\rho},L_{\rho}\right)}}_{\lambda}\int_{0}^{1}\rho\,\left(f'\right)^{2}dx.\qedhere\] \end{proof} \begin{prop} \label{pro:Poincare_Beh4}Der Eigenvektor $u$ und $\mu:=\frac{1}{\lambda}$ lösen das Sturm-Liouville-Eigenwertproblem\index{Sturm-Liouville-Eigenwertproblem}\[ \left(\rho^{-1}\left(\rho u\right)'\right)'+\mu u=0\quad\textrm{in }\left(0,1\right),\] \[ u\left(0\right)=u\left(1\right)=0,\] im klassischen Sinn, d.h. $u,v:=\rho u\in H_{0}^{1}\left(0,1\right)\cap H^{2}\left(0,1\right)$ und\[ \left(\rho^{-1}v'\right)'+\mu\rho^{-1}v=0\] gilt wie\[ v''-\left(\frac{\rho'}{\rho}\right)v'+\mu v=0\] punktweise in $\left(0,1\right)$. \end{prop} \begin{proof} $w:=Tu\in H\left(0,1\right)$ erfüllt $\lambda u=T^{*}w$, also \[ \lambda v=\lambda\rho u=\rho T^{*}w=S_{-}\rho\left(1-M\right)w\in H^{2}\left(0,1\right)\] mit\[ \lambda v\left(1\right)=\int_{1}^{1}\rho\left(1-M\right)wdx=0\] und\[ \lambda v\left(0\right)=\int_{0}^{1}\rho\left(1-M\right)wdx=\int_{0}^{1}\rho wdx-\left(Mw\right)\int_{0}^{1}\rho dx=0.\] Also ist $v,u\in H_{0}^{1}\left(0,1\right)\cap H^{2}\left(0,1\right)$ und \[ v'\left(x\right)=-\mu\left(\rho\left(1-M\right)w\right)\left(x\right),\] also\[ \rho^{-1}v'+\mu\left(1-M\right)w=0,\] und dann auch\[ \left(\rho^{-1}v'\right)'+\mu w'=0,\] $w'=\left(Tu\right)'=\left(S_{+}u\right)'=u$. Also\[ 0=\left(\rho^{-1}v'\right)'+\mu u=\rho^{-1}v''-\rho^{-2}\rho'v'+\rho^{-1}\mu v.\qedhere\] \end{proof} \begin{prop} $c_{P}\left(0,1\right)=\frac{1}{\pi}$. \end{prop} \begin{proof} Für $\rho\equiv1$ folgt in Prop. \ref{pro:Poincare_Beh4}: \[ u''+\mu u=0\quad\textrm{mit }u\left(0\right)=u\left(1\right)=0.\] Ein allgemeiner Ansatz mit $\cos-$ und $\sin-$Funktionen zeigt \[ u\left(x\right)=\sin\left(k\pi x\right)\quad\textrm{für }k=1,2,\ldots\] und $\mu$ ist minimal für $k=1$, d.h. \[ \mu=\pi^{2}.\qedhere\] \end{proof} \begin{prop} \label{pro:Poincare_cF}$c_{F}\left(0,1\right)=\frac{1}{\pi}$. \end{prop} \begin{proof} Ein Transformationsargument führt die Behauptung auf $c_{P}=\frac{1}{\pi}$ zurück. \end{proof} Die folgende Proposition zeigt $\lambda\leq\pi^{-2}$ und beschließt damit den Beweis zu Satz \ref{thm:PayneWeinberger1}. \end{proof} \begin{prop} Für eine konkave Funktion $\rho$ gilt\[ \pi^{2}\leq\mu\] (d.h. $\lambda\leq\frac{1}{\pi^{2}}$ und das zeigt den Satz!). \end{prop} \begin{proof} Die Funktion $v\in H_{0}^{1}\left(0,1\right)\cap H^{2}\left(0,1\right)$ aus Prop. \ref{pro:Poincare_Beh4} erfüllt\[ v''-\left(\frac{\rho'}{\rho}\right)v'+\mu v=0,\] also\[ \underbrace{\int_{0}^{1}vv''dx}_{-\left\Vert v'\right\Vert _{2}^{2}}\underbrace{-\int_{0}^{1}\frac{\rho'}{\rho}v'vdx}_{-\frac{1}{2}\int_{0}^{1}\frac{\rho'}{\rho}\left(v^{2}\right)'dx}+\underbrace{\int_{0}^{1}\mu v^{2}dx}_{\mu\left\Vert v\right\Vert _{2}^{2}}=0.\] Wegen \[ -\frac{1}{2}\int_{0}^{1}\frac{\rho'}{\rho}\left(v^{2}\right)'dx=\frac{1}{2}\int_{0}^{1}\left(\frac{\rho'}{\rho}\right)'v^{2}dx=\frac{1}{2}\int_{0}^{1}\left(\underbrace{\frac{\rho''}{\rho}}_{\leq0}-\frac{\rho'^{2}}{\rho^{2}}\right)v^{2}dx\leq0\] gilt also mit Proposition \ref{pro:Poincare_cF}\[ \pi^{2}\left\Vert v\right\Vert _{2}^{2}\leq\left\Vert v'\right\Vert _{2}^{2}=\int_{0}^{1}\left(\frac{1}{2}\underbrace{\left(\frac{\rho'}{\rho}\right)'}_{\leq0}+\mu\right)v^{2}dx\leq\mu\left\Vert v\right\Vert _{2}^{2},\] d.h. $\pi^{2}\leq\mu$ (da $\left\Vert v\right\Vert _{2}\neq0$).\qedhere \end{proof} \begin{thm} [Payne-Weinberger]Für eine konvexe Menge $\Omega\Subset\mathbb{R}^{n}$ gilt\[ c_{P}\left(\Omega\right)\leq\frac{1}{\pi}\diam\left(\Omega\right).\] Diese Abschätzung ist optimal in dem Sinne, daß\[ \sup_{\Omega\textrm{ konvex}}\frac{c_{P}\left(\Omega\right)}{\diam\left(\Omega\right)}=\pi.\] \end{thm} \begin{proof} Das Integralmittel von $f$ aus $\Omega$ werde mit\[ f_{\Omega}:=\intm_{\Omega}f\left(x\right)dx\] bezeichnet. Dann lautet die Behauptung\[ \left\Vert f-f_{\Omega}\right\Vert _{2}\leq\frac{1}{\pi}\diam\left(\Omega\right)\left|f\right|_{1,2}.\] \begin{enumerate} \item O.B.d.A. kann in der Behauptung $f\in C^{\infty}\left(\mathbb{R}^{n}\right)\left|_{\Omega}\right.$ mit $\int_{\Omega}fdx=0$ angenommen werden. Für ein solches $f$ ist\[ M:=\left\Vert f\right\Vert _{\infty}+\left\Vert Df\right\Vert _{\infty}\] eine fixe Konstante, $\left|\Omega\right|=:A$. Der Beweis wird nur für $n=2$ ausgeführt. \item Definiere $\Omega_{0,1}:=\Omega$ und zu $\Omega_{j,1}$, $\ldots$, $\Omega_{j,2^{j}}$ definiere man $\Omega_{j+1,1},\ldots,\Omega_{j+1,2^{j+1}}$ durch Bisektion jedes der konvexen und beschränkten $\Omega_{j,1}$, $\ldots$, $\Omega_{j,2^{j}}$. Dabei wird $\Omega_{j,m}$ in zwei flächengleiche konvexe Gebiete $\Omega_{j+1,m},\Omega_{j+1,m+1}$ mit \[ \int_{\Omega_{j+1,m}}f\left(x\right)dx=0=\int_{\Omega_{j+1,m+1}}f\left(x\right)dx\] geteilt. (Sandwich-Problem erlaubt Lösungen!) Dann ist\[ \left|\Omega_{j,m}\right|=2^{-j}A.\] \item Für alle $\varepsilon>0$ existieren konvexe, paarweise disjunkte, offene Mengen $\Omega_{1},\ldots,\Omega_{m}$ mit $\bar{\Omega}=\bar{\Omega}_{1}\cup\ldots\cup\bar{\Omega}_{m}$,\[ \frac{A}{m}=\left|\Omega_{1}\right|=\ldots=\left|\Omega_{m}\right|,\qquad\int_{\Omega_{j}}f\left(x\right)dx=0\quad\textrm{für alle }j=1,2,\ldots,m,\] und $\Omega_{j}$ ist kongruent zu einer Teilmenge von $\left(0,\ell_{j}\right)\times\left(-\frac{\varepsilon}{2},+\frac{\varepsilon}{2}\right)$, $\ell_{j}:=\diam\left(\Omega_{j}\right)$. \begin{minipage}[c]{0.45\columnwidth}% \begin{proof} Für $j$ in 2. groß sei $b:=\beta-\alpha\leq\ell_{j}$. Dann gilt\[ \frac{b\ell_{j}}{2}\leq\left|\Omega_{j}\right|\leq2^{-j}A,\] also wegen\[ \frac{b^{2}}{2}\leq\frac{b\ell_{j}}{2}\xrightarrow{j\rightarrow\infty}0\] dann $b\xrightarrow{j\rightarrow\infty}0$.\end{proof} \end{minipage}% \hfill{}\begin{minipage}[c]{0.50\columnwidth}% \setlength{\unitlength}{0.2cm} \begin{picture}(40,23)(-3,-10) \put(-1,0){\line(1,0){32}} \put(0,-11){\line(0,1){22}} \put(30,-11){\line(0,1){22}} \thicklines \put(30,0){\line(-1,2){2}} \put(28,4){\line(-3,1){18}} \put(20,0){\arc{20}{0}{1.57}} \spline(0,0)(10,-8)(20,-10) \put(0,0){\line(1,3){2}} \put(2,6){\line(6,3){8}} \Thicklines \put(0,0){\line(1,1){10}} \put(30,0){\line(-2,1){20}} \put(0,0){\line(4,-2){20}} \put(30,0){\line(-1,-1){10}} \thinlines \put(-1,-10){\line(1,0){32}} \put(-1,10){\line(1,0){32}} \put(-2,-9.8){$\alpha$} \put(-2,10){$\beta$} \put(-1,-11.5){$0$} \put(29,-11.5){$\ell_j$} \multiput(3,0)(2,-1){9}{\line(1,1){8}} \end{picture}\end{minipage}% \item Für $\Omega\subseteq\left(-\frac{\varepsilon}{2},\frac{\varepsilon}{2}\right)\times\left(0,\ell\right)$ konvex und $f\in H^{1}\left(\Omega\right)$ mit $\int_{\Omega}f\left(x\right)dx=0$ ist\[ \left\Vert f\right\Vert _{L^{2}\left(\Omega\right)}\leq\frac{\ell}{\pi}\left\Vert f\right\Vert _{H^{1}\left(\Omega\right)}+\varepsilon\left(2+\frac{\ell}{\pi}\right)\left\Vert f\right\Vert _{W^{1,\infty}\left(\Omega\right)}\left|\Omega\right|^{\nicefrac{1}{2}}\] für $\ell_{j}:=\diam\left(\Omega_{j}\right)\leq\diam\left(\Omega\right)$. \begin{proof} O.B.d.A. sei $\ell=\diam\left(\Omega\right)=\left|a-b\right|$ für $a,b\in\partial\Omega$, $a=\left(0,0\right)$, $b=\left(\ell,0\right)$ und \[ \Omega=\left\{ \left(\xi,\eta\right)\in\mathbb{R}^{2}\left|0<\xi<\ell,\,\underline{p}\left(\xi\right)<\eta<\bar{p}\left(\xi\right)\right.\right\} \] für Funktionen $\underline{p}$, $\bar{p}$ die den Rand von $\Omega$ parametrisieren mit $\underline{p}\leq0\leq\bar{p}$, $\left(0,\ell\right)\times\left\{ 0\right\} \subseteq\Omega$. Dann ist\[ g\left(\xi\right):=f\left(\xi,0\right)\] für alle $0<\xi<\ell$ definiert, die Funktion $\rho\left(x\right):=\bar{p}\left(x\right)-\underline{p}\left(x\right)$ ist konkav und mit\[ m:=\frac{\int_{0}^{\ell}g\rho d\xi}{\int_{0}^{\ell}\rho d\xi}\] gilt nach dem Satz \ref{thm:PayneWeinberger1} \[ \left\Vert \rho^{\nicefrac{1}{2}}\left(g-m\right)\right\Vert _{L^{2}\left(0,\ell\right)}\leq\frac{\ell}{\pi}\left\Vert \rho^{\nicefrac{1}{2}}g'\right\Vert _{L^{2}\left(0,\ell\right)}.\] Da $f$ und $Df$ Lipschitz-stetig sind, gilt\begin{eqnarray*} \left\Vert f-g\right\Vert _{L^{2}\left(\Omega\right)} & \leq & \varepsilon\left|\Omega\right|^{\nicefrac{1}{2}}\textrm{Lip}\left(f\right),\\ \left\Vert \frac{\partial f}{\partial x_{1}}-g'\right\Vert _{L^{2}\left(\Omega\right)} & \leq & \varepsilon\left|\Omega\right|^{\nicefrac{1}{2}}\textrm{Lip}\left(Df\right)\end{eqnarray*} und daher auch\begin{eqnarray*} \left\Vert \rho^{\nicefrac{1}{2}}m\right\Vert _{L^{2}\left(0,\ell\right)} & = & \frac{\left|\int_{\Omega}g\left(x_{1}\right)dx\right|}{\left\Vert \rho^{\nicefrac{1}{2}}\right\Vert _{L^{2}\left(0,\ell\right)}}\\ & = & \frac{\left|\int_{\Omega}f\left(x_{1},0\right)-f\left(x_{1},x_{2}\right)dx\right|}{\left|\Omega\right|^{\nicefrac{1}{2}}}\\ & \leq & \varepsilon\textrm{Lip}\left(f\right)\left|\Omega\right|^{\nicefrac{1}{2}}.\end{eqnarray*} Folglich gilt\begin{align*} \left\Vert f\right\Vert _{L^{2}\left(\Omega\right)} & \leq\left\Vert f-g\right\Vert _{L^{2}\left(\Omega\right)}+\left\Vert \rho^{\nicefrac{1}{2}}\left(g-m\right)\right\Vert _{L^{2}\left(0,\ell\right)}+\left\Vert \rho^{\nicefrac{1}{2}}m\right\Vert _{L^{2}\left(0,\ell\right)}\\ & \leq2\varepsilon\left|\Omega\right|^{\nicefrac{1}{2}}\textrm{Lip}\left(f\right)+\frac{\ell}{\pi}\left\Vert \rho^{\nicefrac{1}{2}}g'\right\Vert _{L^{2}\left(0,\ell\right)}\\ & =2\varepsilon\left|\Omega\right|^{\nicefrac{1}{2}}\textrm{Lip}\left(f\right)+\frac{\ell}{\pi}\left\Vert g'\right\Vert _{L^{2}\left(\Omega\right)}\\ & \leq2\varepsilon\left|\Omega\right|^{\nicefrac{1}{2}}\textrm{Lip}\left(f\right)+\frac{\ell}{\pi}\left\Vert g'-\frac{\partial f}{\partial x_{1}}\right\Vert _{L^{2}\left(\Omega\right)}+\frac{\ell}{\pi}\left\Vert \frac{\partial f}{\partial x_{1}}\right\Vert _{L^{2}\left(\Omega\right)}\\ & \leq\left(2+\frac{\ell}{\pi}\right)\varepsilon\left|\Omega\right|^{\nicefrac{1}{2}}\left\Vert f\right\Vert _{W^{1,\infty}\left(\Omega\right)}+\frac{\ell}{\pi}\left\Vert Df\right\Vert _{L^{2}\left(\Omega\right)}.\qedhere\end{align*} \end{proof} \item Beweis von $c_{P}\left(\Omega\right)\leq\frac{1}{\pi}\diam\left(\Omega\right)$: Für $\ell_{j}:=\diam\left(\Omega_{j}\right)\leq\diam\left(\Omega\right)$ folgt aus 4. für alle $j$\[ \left\Vert f\right\Vert _{L^{2}\left(\Omega_{j}\right)}\leq\frac{\ell_{j}}{\pi}\left\Vert f\right\Vert _{H^{1}\left(\Omega_{j}\right)}+\varepsilon\left(2+\frac{\ell}{\pi}\right)\left\Vert f\right\Vert _{W^{1,\infty}\left(\Omega\right)}2^{-\nicefrac{j}{2}}\left|A\right|^{\nicefrac{1}{2}}.\] Diese Aussage wird quadriert und summiert und liefert für $\varepsilon\rightarrow0$ die Behauptung. \item Beweis zur Optimalität: Auf dem Gebiet $\Omega_{\varepsilon}=\left(0,\ell\right)\times\left(0,\varepsilon\right)$ betrachte man \[ f\left(\xi,\eta\right):=\cos\left(\frac{\pi}{\ell}\xi\right),\] unabhängig von $\eta$. Wie im eindimensionalen Fall folgt\[ \left\Vert f\right\Vert _{2}=\frac{\ell}{\pi}\left\Vert Df\right\Vert _{2}.\] Also \[ \frac{\ell}{\pi}\leq c_{P}\left(\Omega_{\varepsilon}\right)\leq\frac{\sqrt{\ell^{2}+\varepsilon^{2}}}{\pi}\] und insgesamt\[ \lim_{\varepsilon\searrow0}\frac{c_{P}\left(\Omega_{\varepsilon}\right)}{\diam\left(\Omega_{\varepsilon}\right)}=\frac{1}{\pi}.\qedhere\] \end{enumerate} \end{proof} \begin{remark*} In der Originalarbeit ist $n\geq3$ unklar (betrachtete Flächenfunktionen sind nicht konkav). Aber: Die Aussage läßt sich verifizieren! \end{remark*} \section{Interpolationsfehlerabschätzungen} \begin{ziel*} Interpolationsfehler $u-Iu$ für abstrakte Fehlerabschätzung\[ \left\Vert u-u_{h}\right\Vert _{V}\lesssim\min_{v_{h}\in V_{h}}\left\Vert u-v_{h}\right\Vert _{V}\lesssim\left\Vert u-Iu\right\Vert _{V}\] abschätzen. \end{ziel*} \begin{notation*} In diesem Abschnitt ist $\mathcal{T}$ eine reguläre Triangulierung mit der Kantenmenge $\mathcal{E}$ und Knotenmenge $\mathcal{N}$ von $\Omega$ in lauter Dreiecke. \end{notation*} \begin{defn} [nodale Interpolation]In der $P_{1}$-FEM bezeichne $\left(\varphi_{z}\right)_{z\in\mathcal{N}}$ die nodale Basis von $P_{1}\left(\mathcal{T}\right)\cap C_{0}^{0}\left(\bar{\Omega}\right)$. Für $f\in C^{0}\left(\bar{\Omega}\right)$ heißt\[ If:=\sum_{z\in\mathcal{N}}f\left(z\right)\varphi_{z}\in P_{1}\left(\mathcal{T}\right)\cap C^{0}\left(\bar{\Omega}\right)\] \emph{nodaler Interpolant}\index{nodale Interpolation} und $f-If$ heißt \emph{Interpolationsfehler}.\index{Interpolationsfehler} \end{defn} \begin{remark*} Für $n=1,2,3$ gilt $H^{2}\left(\Omega\right)\hookrightarrow C^{0}\left(\bar{\Omega}\right)$ ({}``Sobolev-Einbettung''). \end{remark*} \begin{remark*} Für $f\in H^{2}\left(\Omega\right)$ ($\Omega\subseteq\mathbb{R}^{n}$, $n\geq2$) ist auf $E\in\mathcal{E}$ \[ \left.\left(f-If\right)\right|_{E}\in H_{0}^{1}\left(E\right)\] und \[ \left.\frac{\partial}{\partial s}\left(f-If\right)\right|_{E}\in L^{2}\left(E\right)\quad\textrm{mit}\quad\intm_{E}\frac{\partial}{\partial s}\left(f-If\right)ds=0.\] \end{remark*} \begin{thm} [lokaler Approximationsfehler]\label{thm:lokApproxfehler}\index{Approximationsfehler, lokal}Für ein Dreieck $T=\conv\left\{ P,E\right\} $ mit Kante $E$ und gegenüberliegendem Knoten $P$ und eine Funktion $g\in H^{1}\left(T\right)$ mit $\intmm_{E}gds=0$ ist\[ \left\Vert g\right\Vert _{L^{2}\left(T\right)}\leq h_{T}\left\Vert Dg\right\Vert _{L^{2}\left(T\right)}\sqrt{\pi^{-2}+\frac{1}{8}}.\] \end{thm} \begin{lem} [Spuridentität]\label{lem:Spuridentitaet}\index{Spuridentität}Für $f\in W^{1,1}\left(T\right)$ gilt \[ \intm_{E}fds-\intm_{T}fdx=\frac{1}{n}\intm_{T}\left(x-P\right)Df\, dx.\] \end{lem} \begin{proof} [Beweis von Satz \ref{thm:lokApproxfehler}]Nach Lemma \ref{lem:Spuridentitaet} ist wegen $g_{E}:=\intmm_{E}gds=0$\[ g_{T}:=\intm_{T}gdx=\frac{1}{2}\intm_{T}\left(P-x\right)Dg\, dx.\] Dann ist\begin{eqnarray*} \left\Vert g\right\Vert _{L^{2}\left(T\right)}^{2} & = & \left\Vert g-g_{T}\right\Vert _{L^{2}\left(T\right)}^{2}+\left\Vert g_{T}\right\Vert _{L^{2}\left(T\right)}^{2}\qquad\textrm{(nach Pythagoras)}\\ & \leq & \left(\frac{h_{T}}{\pi}\right)^{2}\left|g\right|_{W^{1,2}\left(T\right)}^{2}+\frac{1}{4}\left|T\right|^{-1}\left|\int_{T}\left(P-x\right)Dg\, dx\right|^{2}\quad\textrm{(nach Poincar\' e, (\ref{eq:PoincareGewichtet}))}\\ & \leq & \left(\left(\frac{h_{T}}{\pi}\right)^{2}+\frac{1}{4}\left|T\right|^{-1}\left\Vert P-\cdot\right\Vert _{L^{2}\left(T\right)}^{2}\right)\left|g\right|_{W^{1,2}\left(T\right)}^{2}\end{eqnarray*} und weiter\[ \left\Vert P-\cdot\right\Vert _{L^{2}\left(T\right)}^{2}=\int_{0}^{\omega}\int_{0}^{R\left(\varphi\right)}r^{2}r\, dr\, d\varphi=\int_{0}^{\omega}\frac{R\left(\varphi\right)^{4}}{4}d\varphi\leq\frac{h_{T}^{2}}{2}\underbrace{\int_{0}^{\omega}\frac{1}{2}R\left(\varphi\right)^{2}d\varphi}_{\left|T\right|}.\qedhere\] \end{proof} \begin{thm} [lokale Interpolationsfehlerabschätzung]Für $f\in H^{2}\left(T\right)$ für ein Dreieck $T=\conv\left\{ P_{1},P_{2},P_{3}\right\} $ mit einem Innenwinkel $0<\omega<\pi$ gilt:\begin{alignat*}{2} \left(A\right)\qquad\qquad & \left|f-If\right|_{H^{1}\left(T\right)}\; & \leq & \;\sqrt{\frac{1}{4}+\frac{2}{\pi^{2}}}\,\frac{h_{T}}{\sqrt{1-\left|\cos\omega\right|}}\left|f\right|_{H^{2}\left(T\right)}\\ \left(B\right)\qquad\qquad & \left\Vert f-If\right\Vert _{L^{2}\left(T\right)}\; & \leq & \;\frac{3h_{T}^{2}}{\sqrt{1-\left|\cos\omega\right|}}\left|f\right|_{H^{2}\left(T\right)}\qquad\textrm{(Ist die 3 scharf?)}\end{alignat*} \end{thm} \begin{remark*} Bezeichne mit $h_{\mathcal{T}}$ die Netzweite. Für $s=0,1$ ist\[ \left|f-If\right|_{H^{s}\left(T\right)}\lesssim\left\Vert h_{\mathcal{T}}^{2-s}D^{2}f\right\Vert _{L^{2}\left(\Omega\right)}.\] \end{remark*} \begin{proof} O.B.d.A. sei $E=E_{1}=\conv\left\{ P_{2},P_{3}\right\} $, $\cos\omega=-\tau_{2}\cdot\tau_{3}=:-\gamma$ und $\left|\tau_{2}\right|=\left|\tau_{3}\right|=1$. \begin{minipage}[c]{0.70\columnwidth}% \textbf{Behauptung}: Für alle $a\in\mathbb{R}^{2}$ ist\[ \left|a\right|^{2}\leq\frac{\left(a\cdot\tau_{2}\right)^{2}+\left(a\cdot\tau_{3}\right)^{2}}{1-\left|\cos\omega\right|},\] denn: sei $a=a_{2}\tau_{2}+a_{3}\tau_{3}$ für $a_{2},a_{3}\in\mathbb{R}$.\end{minipage}% \hfill{}\begin{minipage}[c]{0.30\columnwidth}% \begin{picture}(11,7)(-1,-1) \put(0,0){\line(1,0){10}} \put(0,0){\line(1,1){5}} \put(10,0){\line(-1,1){5}} \put(0,0){\arc{5}{5.5}{0}} \put(1.2,0.5){$\omega$} \put(-1,-1){$P_1$} \put(10,-1){$P_2$} \put(5.5,5){$P_3$} \put(7.2,3){$E$} \thicklines \put(4,4){\vector(-1,-1){2}} \put(2,3.2){$\tau_2$} \put(4,0){\vector(1,0){3}} \put(5,-1){$\tau_3$} \end{picture}\end{minipage}% O.B.d.A. ist $a_{2}^{2}+a_{3}^{2}=1$. Nach Young-Ungleichung folgt dann $-1\leq2a_{2}a_{3}\leq1$. Dann\begin{eqnarray*} 0 & \leq & \underbrace{\gamma^{2}-2a_{2}a_{3}\gamma\left|\gamma\right|}_{\geq0}+\underbrace{\left|\gamma\right|+2a_{2}a_{3}\gamma}_{\geq0}\\ \Leftrightarrow\,\underbrace{\left(2a_{2}a_{3}\gamma+1\right)}_{=\left|a\right|^{2}}\underbrace{\left(1-\left|\gamma\right|\right)}_{>0} & \leq & 1+\gamma^{2}+4a_{2}a_{3}\gamma\\ & = & \left(a\cdot\tau_{2}\right)^{2}+\left(a\cdot\tau_{3}\right)^{2}\\ & = & \left(a_{2}+a_{3}\gamma\right)^{2}+\left(a_{3}+a_{2}\gamma\right)^{2}.\end{eqnarray*} Zum \textbf{Beweis von (A)}: Die Funktion \[ g_{j}:=D\left(f-If\right)\cdot\tau_{j},\qquad j=2,3,\] erfüllt $\int_{E_{j}}g_{j}ds=0$. Dann folgt mit Satz \ref{thm:lokApproxfehler}\[ \left\Vert g_{j}\right\Vert _{L^{2}\left(T\right)}^{2}\leq\left(\frac{1}{\pi^{2}}+\frac{1}{8}\right)h_{T}^{2}\left\Vert Dg_{j}\right\Vert _{L^{2}\left(T\right)}^{2}\leq\left(\frac{1}{\pi^{2}}+\frac{1}{8}\right)h_{T}^{2}\left|f\right|_{H^{2}\left(T\right)}^{2}\] (mit $D\left(f-If\right)\cdot\tau_{j}=\frac{\partial}{\partial s_{j}}\left(f-If\right)$). Die obige Behauptung liefert nun\[ \left\Vert D\left(f-If\right)\right\Vert _{2}^{2}\leq\frac{\left\Vert g_{2}\right\Vert _{2}^{2}+\left\Vert g_{3}\right\Vert _{2}^{2}}{1-\left|\cos\omega\right|}\leq\frac{h_{T}^{2}\left(\frac{2}{\pi^{2}}+\frac{1}{4}\right)}{1-\left|\cos\omega\right|}\left|f\right|_{H^{2}\left(T\right)}^{2}.\] \textbf{Aufgabe}: Man bestimme die Konstanten in (A) und (B) für $T_{\textrm{ref}}$. \textbf{Aufgabe}: Sei $g:=f-If\in H^{2}\left(T\right)$ und $\left.g\right|_{E}\in H_{0}^{1}\left(E\right)$, $g_{T}:=\intmm_{T}gdx$. Dann ist\begin{equation} \left\Vert g_{T}\right\Vert _{L^{2}\left(T\right)}\leq\frac{3}{2}h_{T}\left|g\right|_{H^{1}\left(T\right)}+\frac{h_{T}^{2}}{2}\left|g\right|_{H^{2}\left(T\right)}.\label{eq:Interpolfehlerabsch1}\end{equation} \textbf{Beweis von (B)}:\begin{eqnarray*} \left\Vert f-If\right\Vert _{L^{2}\left(T\right)}^{2} & = & \left\Vert g\right\Vert _{L^{2}\left(T\right)}^{2}\\ & = & \underbrace{\left\Vert g_{T}\right\Vert _{L^{2}\left(T\right)}^{2}}_{(\ref{eq:Interpolfehlerabsch1})}+\underbrace{\left\Vert g-g_{T}\right\Vert _{L^{2}\left(T\right)}}_{\leq\left(\frac{h_{T}}{\pi}\right)^{2}\left|g\right|_{H^{1}\left(T\right)}^{2}}\\ & \leq & \frac{h_{T}^{4}}{2}\left|f\right|_{H^{2}\left(T\right)}^{2}+h_{T}^{2}\left(\frac{9}{2}+\frac{1}{\pi^{2}}\right)\left|g\right|_{H^{1}\left(T\right)}^{2}\\ & \leq & \frac{h_{T}^{4}}{2}\left|f\right|_{H^{2}\left(T\right)}^{2}+h_{T}^{2}\left(\frac{9}{2}+\frac{1}{\pi^{2}}\right)\left(\frac{1}{4}+\frac{2}{\pi^{2}}\right)\frac{h_{T}^{2}}{1-\left|\gamma\right|}\left|f\right|_{H^{2}\left(T\right)}^{2}\end{eqnarray*} Nebenrechnung:\[ \frac{1}{2}+\left(\frac{9}{2}+\frac{1}{\pi^{2}}\right)\left(\frac{1}{4}+\frac{2}{\pi^{2}}\right)\left(\frac{1}{1-\left|\gamma\right|}\right)\leq\frac{1}{1-\left|\gamma\right|}\left(\frac{1}{2}+\frac{9}{8}+\frac{9}{\pi^{2}}+\frac{1}{4\pi^{2}}+\frac{2}{\pi^{4}}\right)\leq\frac{2.59}{1-\left|\gamma\right|}\qedhere\] \end{proof} \begin{defn} [Maximumwinkelbedingung]Sofern die größten Winkel in jedem Dreieck einer Familie von Triangulierungen $\left(\mathcal{T}_{h}\right)_{h\in H}$ durch eine Konstante $c_{\sphericalangle}<\pi$ nach oben beschränkt sind, sagt man: $\left(\mathcal{T}_{h}\right)_{h\in H}$ erfüllt die \emph{Maximumwinkelbedingung}\index{Maximumwinkelbedingung}. \end{defn} \begin{remark} Unter der Maximumwinkelbedingung kann stets $\omega$ so gewählt werden, daß im Approximationssatz \[ \left(1-\left|\cos\omega\right|\right)^{-1}\leq\left(1-\left|\cos c_{\sphericalangle}\right|\right)^{-1}\lesssim1\] \end{remark} \begin{remark} [Minimumwinkelbedingung]\index{Minimumwinkelbedingung}Der kleinste Winkel ist durch eine Konstante $c_{\min\sphericalangle}>0$ beschränkt. Es ist klar, daß aus der Minimumwinkelbedingung die Maximumwinkelbedingung folgt. Die Äquivalenz gilt hingegen nicht, wie folgendes Beispiel zeigt. \end{remark} \begin{example*} $f\left(x,y\right)=1-x^{2}$ für $\left(x,y\right)\in T_{1}:=\conv\left\{ \left(0,1\right),\left(0,1\right),\left(h,0\right)\right\} $, $\omega=\nicefrac{\pi}{2}$. \begin{minipage}[c]{0.50\columnwidth}% Interpolationsfehlerabschätzung: Konstante, unabhängig von $h\searrow0$. $T_{1}$ erfüllt die Maximumwinkelbedingung, aber für $h\searrow0$ \underbar{nicht} die Minimumwinkelbedingung.\end{minipage}% \hfill{}\begin{minipage}[c]{0.45\columnwidth}% \begin{picture}(21,6)(-1,-1) \put(0,0){\line(1,0){20}} \put(0,0){\line(0,1){4}} \put(20,0){\line(-5,1){20}} \put(-1,2){$h$} \put(10,-1){$1$} \put(3,1){$T_1$} \put(0,0){\arc{3}{4.71}{0}} \put(.5,.5){$\cdot$} \end{picture}\end{minipage}% \begin{minipage}[c]{0.50\columnwidth}% Auf $T_{2}:=\conv\left\{ \left(1,0\right),\left(0,h\right),\left(-1,0\right)\right\} $ wird für $h\searrow0$ die Maximumwinkelbedingung verletzt.\[ \frac{\partial\left(f-If\right)}{\partial y}\left(x,y\right)=-\frac{\partial If}{\partial y}=-h^{-1}\xrightarrow{h\searrow0}\infty\] \end{minipage}% \hfill{}\begin{minipage}[c]{0.45\columnwidth}% \begin{picture}(21,5)(-1,0) \put(0,0){\line(1,0){20}} \put(0,0){\line(2,1){10}} \put(20,0){\line(-2,1){10}} \multiput(10,0)(0,1){5}{\line(0,1){.5}} \put(10.5,2){$h$} \put(7,1){$T_2$} \end{picture}\end{minipage}% \end{example*} \section{Modellproblem und Regularität} Betrachte ein polygonal berandetes Lipschitz-Gebiet $\Omega\subseteq\mathbb{R}^{2}$ und Funktionen $f\in L^{2}\left(\Omega\right)$, $u\in H_{0}^{1}\left(\Omega\right)$ mit $f+\Delta u=0$ in $\Omega$. \begin{thm} \renewcommand{\labelenumi}{(\alph{enumi})} \begin{enumerate} \item Für $\omega\Subset\Omega$ offen gilt $u\left|_{\omega}\right.\in H^{2}\left(\omega\right)$ und es existiert $c\left(\omega,\Omega\right)>0$ mit\[ \left\Vert u\right\Vert _{H^{2}\left(\omega\right)}\leq c\left(\omega,\Omega\right)\left(\left\Vert f\right\Vert _{L^{2}\left(\Omega\right)}+\left\Vert u\right\Vert _{H^{1}\left(\Omega\right)}\right).\] \item Für $\Omega$ konvex gilt $u\in H^{2}\left(\Omega\right)$ und\[ \left\Vert u\right\Vert _{H^{2}\left(\Omega\right)}^{2}\leq\left\Vert f\right\Vert _{L^{2}\left(\Omega\right)}^{2}+\left\Vert u\right\Vert _{H^{1}\left(\Omega\right)}^{2}.\] (Die Konstante ist {}``$1$''.) \end{enumerate} \end{thm} \begin{remark*} Für glatte Ränder, $\Omega$ $C^{2}$-Gebiet, gilt ebenfalls globale Regularität: $u\in H^{2}\left(\Omega\right)$ und $\left\Vert u\right\Vert _{H^{2}\left(\Omega\right)}\lesssim\left\Vert f\right\Vert _{L^{2}\left(\Omega\right)}$. \end{remark*} \begin{proof} [Beweisskizze] \begin{prop} \label{pro:Regularitaet1}Es existiert ein $c\left(\omega,\Omega\right)$, so daß für alle $v\in H^{2}\left(\Omega\right)$\[ \left\Vert v\right\Vert _{2,2,\omega}\leq c\left(\omega,\Omega\right)\left(\left\Vert \Delta v\right\Vert _{2,\supp\chi}+\left\Vert v\right\Vert _{1,2,\Omega}\right)\] für $\chi\in C_{c}^{\infty}\left(\Omega\right)$ mit $0\leq\chi\leq1$ auf $\mathbb{R}^{2}$ und $\chi\left|_{\omega}\right.\equiv1$. \end{prop} \begin{proof} Für $w:=v\chi$ gilt\[ \left\Vert \Delta w\right\Vert _{L^{2}\left(\Omega\right)}=\left(\int_{\Omega}\left(w_{xx}+w_{yy}\right)^{2}d\Omega\right)^{\nicefrac{1}{2}}\leq\left(\int_{\Omega}\left(\chi\Delta v\right)^{2}dx\right)^{\nicefrac{1}{2}}+4\left\Vert \chi\right\Vert _{2,\infty,\Omega}\left\Vert v\right\Vert _{1,2,\Omega},\] da $\left|w_{xx}\right|=\left|\left(v\chi\right)_{xx}\right|\leq\left|v_{xx}\right|\left\Vert \chi\right\Vert _{\infty}+2\left|v_{x}\right|\left\Vert \chi_{x}\right\Vert _{\infty}+v\left\Vert \chi_{xx}\right\Vert _{\infty}$. Für $\omega\in H_{0}^{3}\left(\Omega\right)$ folgte\[ \int_{\Omega}w_{xx}w_{yy}d\Omega=-\int_{\Omega}w_{xyx}w_{y}d\Omega=\int_{\Omega}w_{xy}^{2}d\Omega=\left\Vert w_{xy}\right\Vert _{2,\Omega}^{2}\qquad\textrm{für alle }v\in H^{3}\left(\Omega\right).\] Da $H^{3}$ dicht in $H^{2}$ folgt dieses sogar für alle $v\in H^{2}\left(\Omega\right)$. Also gilt\begin{eqnarray*} \left\Vert D^{2}v\right\Vert _{2,\omega}^{2} & \leq & \left\Vert D^{2}w\right\Vert _{2}^{2}=\left\Vert w_{xx}\right\Vert _{2,\Omega}^{2}+\left\Vert w_{yy}\right\Vert _{2,\Omega}^{2}+2\left\Vert w_{xy}\right\Vert _{2,\Omega}^{2}\\ & = & \left\Vert \Delta w\right\Vert _{2,\Omega}^{2}\\ & \leq & 2\left\Vert \underbrace{\chi}_{\leq1}\Delta v\right\Vert _{2}^{2}+8\left\Vert \chi\right\Vert _{\infty,2,\Omega}^{2}\left\Vert v\right\Vert _{1,2,\Omega}^{2}\end{eqnarray*} und das ist die Behauptung. \end{proof} \textbf{Beweis zu} \textbf{\emph{a)}}: Zu $u\in H_{0}^{1}\left(\Omega\right)$ reguliert man $u\chi$ zu $w_{\varepsilon}:=\left(u\chi\right)*\eta_{\varepsilon}$ für $0<\varepsilon<\dist\left(\omega,\partial\Omega\right)$. Dann ist $w_{\varepsilon}\in\mathcal{D}\left(\Omega\right)$ mit\[ \left\Vert f+\Delta w_{\varepsilon}\right\Vert _{2,\Omega}+\left\Vert u-w_{\varepsilon}\right\Vert _{1,2,\Omega}\xrightarrow{\varepsilon\searrow0}0.\] Mit Proposition \ref{pro:Regularitaet1} für $v=\omega_{\varepsilon}$ und $\varepsilon\searrow0$ folgt\[ \limsup_{\varepsilon\searrow0}\left\Vert w_{\varepsilon}\right\Vert _{2,2,\omega}\leq c\left(\omega,\Omega\right)\left(\left\Vert f\right\Vert _{2,\Omega}+\left\Vert u\right\Vert _{1,2,\Omega}\right).\] Die Folge $\left(w_{\varepsilon}\right)$ ist beschränkt im Hilbert-Raum $H^{2}\left(\omega\right)$ und besitzt eine schwach konvergente Teilfolge $\left(w_{\varepsilon}\right)\rightharpoonup w$ in $H^{2}\left(\omega\right)$, also $w=u\left|_{\omega}\right.$ und \[ \left\Vert w\right\Vert _{2,2,\omega}=\left\Vert u\right\Vert _{2,2,\omega}\leq c\left(\omega,\Omega\right)\left(\left\Vert f\right\Vert _{L^{2}\left(\Omega\right)}+\left\Vert u\right\Vert _{1,2,\Omega}\right).\] \begin{prop} Für alle glatten $v$ mit $v\left|_{\partial\Omega}\right.=0$ und $\partial\Omega$ glatt und konvex gilt\[ \left|v\right|_{2,2,\Omega}\leq\left\Vert \Delta v\right\Vert _{2,\Omega}.\] \end{prop} \begin{proof} [Beweisidee]Sei $x\left(s\right)$ eine Randparametrisierung von $\partial\Omega$ bzgl. Bogenlängenparameter $s$. Für einen Punkt $A\in\partial\Omega$ ist $\tau\left(A\right)=\frac{\partial x}{\partial s}\left(A\right)\bot\nu\left(A\right)$. Konvexität: $\frac{\partial\tau\left(x\left(s\right)\right)}{\partial s}\cdot\nu\left(x\left(s\right)\right)\leq0$ Randbedingung $\frac{\partial v\left(x\left(s\right)\right)}{\partial s}=0$ Partielle Integration wie in Proposition \ref{pro:Regularitaet1} zeigt \underbar{mit} Randtermen\begin{eqnarray*} \left\Vert \Delta v\right\Vert _{2,\Omega}^{2}-\left|v\right|_{2,2,\Omega}^{2} & = & 2\int_{\partial\Omega}\left(v_{xx}v_{y}\underbrace{\nu_{y}}_{-\tau_{x}}-v_{xy}v_{y}\underbrace{\nu_{x}}_{\tau_{y}}\right)dx\\ & = & -2\int_{\partial\Omega}v_{y}\frac{\partial v_{x}}{\partial s}ds\\ & = & 2\int_{\partial\Omega}\frac{\partial v_{y}}{\partial s}v_{x}ds\end{eqnarray*} Sei $v_{\nu}:=\frac{\partial v}{\partial\nu}:=\nabla v\cdot\nu$, also $Dv=v_{\nu}\cdot\nu$, also $v_{x}=v_{\nu}\nu_{x}$. Weiterhin folgt $\frac{\partial v_{y}}{\partial s}=\frac{\partial\left(v_{\nu}\nu_{y}\right)}{\partial s}=\frac{\partial v_{\nu}}{\partial s}\nu_{y}+v_{\nu}\frac{\partial\nu_{y}}{\partial s}$. Aus $0=v_{\tau}:=\frac{\partial v}{\partial\tau}:=\nabla v\cdot\tau=\nabla v\cdot\left(-\nu_{y},\nu_{x}\right)^{T}$ folgt $v_{x}\nu_{y}=v_{y}\nu_{x}$. Dies ergibt dann weiter\begin{align*} \left\Vert \Delta v\right\Vert _{2,\Omega}^{2}-\left|v\right|_{2,2,\Omega}^{2} & =2\int_{\partial\Omega}v_{\nu}\nu_{x}\left(\frac{\partial v_{\nu}}{\partial s}\nu_{y}+v_{\nu}\frac{\partial\nu_{y}}{\partial s}\right)\\ & =2\int_{\partial\Omega}\frac{1}{2}v_{\nu}^{2}\left(-\frac{\partial}{\partial s}\left(\nu_{x}\nu_{y}\right)\right)+v_{\nu}^{2}\nu_{x}\frac{\partial\nu_{y}}{\partial s}dx\quad\textrm{(part. Integration für }\frac{\partial}{\partial s}\left(\frac{1}{2}v_{\nu}\right)^{2}\\ & =\int_{\partial\Omega}v_{\nu}^{2}\left(\nu_{x}\underbrace{\frac{\partial\nu_{y}}{\partial s}}_{-\frac{\partial\tau_{x}}{\partial s}}-v_{y}\underbrace{\frac{\partial\nu_{x}}{\partial s}}_{\frac{\partial\tau_{y}}{\partial s}}\right)ds\\ & =-\int_{\partial\Omega}v_{\nu}^{2}\underbrace{\left(\frac{\partial\tau}{\partial s}\cdot\nu\right)}_{\leq0}ds\\ & \geq0.\qedhere\end{align*} \end{proof} \textbf{Beweis von} \textbf{\emph{b)}}: Dichtigkeitsargumente für $u$ und konvexe Approximation von $\Omega$ durch glatte Gebiete.\qedhere \end{proof} \begin{remark*} In der Umgebung $\omega=B\left(x,\delta\right)\cap\Omega$ eines Punktes $x$ bei dem $\partial\Omega$ glatt ist, gilt $u\in H^{2}\left(\omega\right)$. Bei konvexen Eckpunkten auch, aber bei stumpfen Ecken nicht. \end{remark*} \begin{defn} [$\mathcal{H}^2$-regulär]Ein Gebiet $\Omega$ (bzw. ein Problem $-\Delta u=f$ in $\Omega$ mit $u\in H_{0}^{1}\left(\Omega\right)$) heißt \emph{$\mathcal{H}^{2}$-regulär}\index{regulär!$H^2$}, falls eine Konstante $c\left(\Omega\right)>0$ existiert, so daß für alle $f\in L^{2}\left(\Omega\right)$ genau ein $u\in H_{0}^{1}\left(\Omega\right)\cap H^{2}\left(\Omega\right)$ existiert, so daß\[ f=-\Delta u\quad\textrm{und}\quad\left\Vert u\right\Vert _{H^{2}\left(\Omega\right)}\leq c\left(\Omega\right)\left\Vert f\right\Vert _{L^{2}\left(\Omega\right)}.\] \end{defn} \begin{conclusion} Für $H^{2}$-reguläre Probleme und deren Finite Elemente-Approximation gilt\[ \left\Vert u-u_{h}\right\Vert _{H^{1}\left(\Omega\right)}\lesssim\left\Vert h_{\mathcal{T}}D^{2}u\right\Vert _{L^{2}\left(\Omega\right)}\lesssim\left\Vert h_{\mathcal{T}}\right\Vert _{\infty}\left\Vert f\right\Vert _{L^{2}\left(\Omega\right)},\] also lineare Konvergenz für quasi-uniforme Netze (d.h. für $\left\Vert h_{\mathcal{T}}\right\Vert _{\infty}\left\Vert \nicefrac{1}{h_{\mathcal{T}}}\right\Vert _{\infty}\lesssim1$). \end{conclusion} \begin{thm} Es sei $\Omega\subseteq\mathbb{R}^{2}$ ein Lipschitz-Gebiet mit polygonalem Rand $\Gamma$, das durch die Ecken $P_{1},\ldots,P_{J}$ definiert ist vermöge\[ \Gamma=\underbrace{\conv\left\{ P_{1},P_{2}\right\} }_{\Gamma_{1}}\cup\underbrace{\conv\left\{ P_{2},P_{3}\right\} }_{\Gamma_{2}}\cup\ldots\cup\underbrace{\conv\left\{ P_{J-1},P_{J}\right\} }_{\Gamma_{J-1}}\cup\underbrace{\conv\left\{ P_{J},P_{1}\right\} }_{\Gamma_{J}}.\] Die Randbedingungen wechseln höchstens bei $P_{1},\ldots,P_{J}$, d.h. $\Gamma_{j}$ ist entweder ganz Dirichlet-Rand, $\left.u\right|_{\Gamma_{j}}=0$, oder Neumann-Rand, $\left.\frac{\partial u}{\partial\nu}\right|_{\Gamma_{j}}\in H^{s-\nicefrac{1}{2}}\left(\Gamma_{j}\right)$, $s>0$. Die Funktion $u\in H_{D}^{1}\left(\Omega\right)$ erfülle\[ -\Delta u=f\in H^{s-1}\left(\Omega\right).\] Dann gilt $u=u_{r}+u_{s}$ mit $u_{r}\in H^{1+s}\left(\Omega\right)$ und \[ u_{s}=\sum_{j=1}^{J}\sum_{\substack{k=1\\ a_{jk