Partielle Differentialgleichungen – Finite-Elemente-Methode

Galerkin-Verfahren

Diskrete Lösung und Galerkin-Projektion

Bemerkung: Die Idee des Galerkin-Verfahrens ist, dass man zur numerischen Lösung schwacher Formen von PDEs diese auf endlich-dimensionale Teilräume einschränkt.

diskrete Lösung: Seien $V$ ein Hilbertraum, $a(\cdot , \cdot )$ eine stetige, koerzive Bilinearform auf $V$, $\ell (\cdot ) \in V’$, $\forall _{v \in V}\; a(u, v) = \ell (v)$ die schwache Form einer PDE und $V_h \le V$ ein endlich-dimensionaler Unterraum. Dann heißt $u_h \in V_h$ mit $\forall _{v \in V_h}\; a(u_h, v) = \ell (v)$ diskrete Lösung.

Satz (Ex. + Eind. + Beschr.): Die diskrete Lösung $u_h \in V_h$ existiert, ist eindeutig und erfüllt $\norm {u_h} \le \frac {1}{\alpha } \norm {\ell }_{V’}$ mit $\alpha $ der Koerzivitätskonstanten von $a$ auf $V$.

Bemerkung: Das „$h$“ in $V_h$ zeigt an, dass der Raum von $V_h$ durch einen Diskretisierungsparameter (z. B. Gitterweite) $h \in \real ^+$ charakterisiert wird und Hoffnung besteht, dass $\lim _{h \to 0} u_h = u$ mit genügend schneller Konvergenz. Es treten folgende Fragen auf:

Wie ist $V_h$ geschickt zu konstruieren?
Existieren a-priori-Fehlerschranken $\norm {u - u_h} \le C(u) h^p$?
Existieren a-posterori-Fehlerschranken $\norm {u - u_h} \le C(u_h) h^p$?
Wie löst man numerisch das entsprechende LGS?

Lemma (Galerkin-Orthogonalität): Seien $u \in V$ die schwache Lösung der PDE und $u_h \in V_h$ die diskrete Lösung. Dann gilt $\forall _{v \in V_h}\; a(u - u_h, v) = 0$.

Bemerkung: Für $a(\cdot , \cdot )$ symmetrisch ist dies gerade die Orthogonalität des Projektionsfehlers der orth. Projektion von $u$ auf $V_h$ bzgl. des Energieskalarprodukts, denn für die orth. Projektion $P_a\colon V \to V_h$ mit $\forall _{v \in V} \forall _{w \in V_h}\; \innerproduct {v - P_a v, w}_a = 0$ folgt nach dem Lemma $P_a u = u_h$ für die schwache Lösung $u$. Damit ist für $a$ symmetrisch die diskrete Lösung $u_h$ genau das Bild der orth. Projektion der schwachen Lösung $u$ auf $V_h$ bzgl. $\innerproduct {\cdot , \cdot }_a$ und heißt daher Galerkin-Projektion.

Für $a(\cdot , \cdot )$ nicht-symmetrisch ist die Galerkin-Projektion i. A. keine orth. Projektion bzgl. irgendeines Skalarprodukts, aber das Lemma gilt weiterhin und man spricht immer noch von Galerkin-Projektion/-Orthogonalität.

Eigenschaften der diskreten Lösung

Lemma (Reproduktion der schw. Lsg.): Sei $u \in V$ die schw. Lösung. Ist $u \in V_h$, dann $u_h = u$.

Bemerkung: Daher ist $V_h := \Span (u)$ ein optimaler, höchstens eindimensionaler Approximationsraum, der aber zur Berechnung so aufwendig ist wie $u$ selbst, also inpraktikabel.

Satz (diskretes Problem als LGS): Sei $(\varphi _j)_{j=1}^n$ eine Basis von $V_h$. Definiere die Steifigkeitsmatrix $A_h = (a_{i,j})_{i,j=1}^n$ und die rechte Seite $b_h = (b_i)_{i=1}^n$ durch $a_{i,j} := a(\varphi _j, \varphi _i)$ und $b_i := \ell (\varphi _i)$.
Dann ist $A_h d = b$ eindeutig lösbar und es gilt $u_h = \sum _{j=1}^n d_j \varphi _j$.

Bemerkung: $A_h$ ist symmetrisch für $a(\cdot , \cdot )$ symmetrisch (im Gegensatz zum Kollokationsverf.).
$A_h$ ist positiv definit wg. $a(\cdot , \cdot )$ koerziv (für $d \not = 0$ gilt $d^\tp A_h d = \sum _{i,j=1}^n d_i d_j a(\varphi _j, \varphi _i)$
$= a(\sum _{j=1}^n d_j \varphi _j, \sum _{i=1}^n d_i \varphi _i) = a(v, v) \ge \alpha \norm {v}^2 > 0$ mit $v := \sum _{j=1}^n d_j \varphi _j \not = 0$).

Beispiele für Ansatzräume

Beispiel: Wählt man $V_h$ als Aufspann von Eigenfunktionen des Diff.operators, so erhält man eine optimale Basis bei unbekannter/variabler rechter Seite.

Eigenfunktionen und -werte erhält man dabei aus der schwachen Form des EW-Problems des Diff.operators: $w \in V$ heißt Eigenfunktion zum Eigenwert $\lambda $, falls $\forall _{v \in V}\; a(w, v) = \lambda \innerproduct {w, v}_{L^2(\Omega )}$.

Unter gewissen Voraussetzungen ($a(\cdot , \cdot )$ symmetrisch und $\Omega $ zush.) kann man zeigen,

dass alle EWe $\lambda _j \in (0, \infty )$ erfüllen (und insb. reell sind),
dass es abzählbar unendlich viele, unbeschränkte Eigenwerte gibt, also $0 < \lambda _1 \le \lambda _2 \le \dotsb $ und $\lim _{j \to \infty } \lambda _j = \infty $, und
dass es eine bzgl. $\innerproduct {\cdot , \cdot }_{L^2(\Omega )}$ orthonormale Menge $\{w_j\}_{j\in \natural }$ von Eigenfunktionen zu den Eigenwerten $\lambda _j$ gibt.

Wählt man nun $n \in \natural $, $h := \frac {1}{n}$, $V_h := \Span (\varphi _1, \dotsc , \varphi _n)$, $\varphi _j := w_j$, so folgt für $A_h$, dass $a_{ij} = a(\varphi _j, \varphi _i) = \lambda _j \innerproduct {w_j, w_i}_{L^2(\Omega )} = \lambda _j \delta _{ij}$, also ist $A_h$ diagonal und $d_h = \frac {b_j}{\lambda _j}$.

Allerdings ist dieser Ansatz i. A. inpraktikabel, da $w_j$ und $\lambda _j$ selten bekannt sind.

Beispiel: $V_h$ kann man auch als polynomiellen Ansatzraum wählen. Seien dazu $d := 1$, $\Omega := [0, 1]$ und $a(u, v) := \int _0^1 u’v’ \dx $ auf $H^1_0(\Omega )$. Dann hat ein Polynom mit Nullrandwerten die Gestalt $p(x) = x(1-x)q(x)$ für $q \in \PP _m$ mit $\PP _m$ den Polynomen vom Grad $\le m$.

Wählt man nun $n \in \natural $, $h := \frac {1}{n}$, $\varphi _j(x) := x(1-x) \cdot x^{j-1} = x^j (1-x)$, so folgt für $A_h$, dass i. A. $a_{ij} = a(\varphi _j, \varphi _i) = \int _0^1 \varphi _j’ \varphi _i’ \dx \not = 0$, also ist $A_h$ i. A. dicht besetzt. Für große $n$ führt dies zu einem Speicherproblem, für mäßig große $n$ ist das Verfahren realisierbar (Spektralverfahren).

Céa-Lemma

Lemma (Céa): Seien $a(\cdot , \cdot )$ eine stetige, koerzive Bilinearform auf $V$ mit Stetigkeitskonstante $\gamma $ und Koerzivitätskonstante $\alpha $ und $\ell $ eine Bilinearform.
Dann gilt $\norm {u - u_h} \le \frac {\gamma }{\alpha } \inf _{v \in V_h} \norm {u - v}$ für $u \in V$ schw. Lsg. und $u_h \in V_h$ diskr. Lsg.

Bemerkung: Das Céa-Lemma erlaubt einen Zusammenhang zwischen dem Galerkin-Projektionsfehler und der Bestapproximation, weil $\inf _{v \in V_h} \norm {u - v}$ der Bestapproximationsfehler der orth. Projektion $P\colon V \to V_h$ ist (unabhängig von $a$ und $\ell $). Weil der Galerkin-Projektionsfehler höchstens um einen konstanten Faktor schlechter als die Bestapproximation ist, spricht man von Quasi-Optimalität der Galerkin-Projektion.

$V_h$ sollte man daher so wählen, dass alle möglichen $u \in V$ möglichst gut approximiert werden können (weil $\lim _{h \to 0} \inf _{v \in V_h} \norm {u - v} = 0 \implies \lim _{h \to 0} \norm {u - u_h} = 0$).

Für $a(\cdot , \cdot )$ symmetrisch gilt das Céa-Lemma sogar mit Faktor $\sqrt {\frac {\gamma }{\alpha }}$. Es gilt dann nämlich Normäquivalenz zur Energienorm mit $\sqrt {\alpha } \norm {v} \le \norm {v}_a \le \sqrt {\gamma } \norm {v}$ (wenn man $\norm {v}_a^2 = a(v, v)$ einsetzt und Stetigkeit/Koerzivität ausnutzt). Daraus erhält man für $v \in V_h$
$\norm {u - u_h}_a^{\cancel {2}} = a(u - u_h, u - u_h) = a(u - u_h, u - v) = \innerproduct {u - u_h, u - v}_a \le \cancel {\norm {u - u_h}_a} \norm {u - v}_a$, also $\norm {u - u_h}_a \le \norm {u - v}_a$ bzw. $\norm {u - u_h} \le \sqrt {\frac {\gamma }{\alpha }} \norm {u - v}$.

Notwendigkeit der Koerzivität

Bemerkung: Die Koerzivität ist bei der Galerkin-Projektion wesentlich. Für $a(\cdot , \cdot )$ nicht-koerziv kann die Galerkin-Projektion aus einem regulären System in $V$ ein singuläres System in $V_h$ erzeugen.

Beispiel: Setze $V := \real ^2$, $a(u, v) := u^\tp \smallpmatrix {1&0\\0&-1} u$, $\ell (v) := \smallpmatrix {1&1} v$. Dann ist $a(\cdot , \cdot )$ nicht-koerziv (negativer EW), aber das System ist regulär, weil
$\forall _{v \in V}\; a(u, v) = \ell (v) \iff \forall _{v \in V}\; u^\tp \smallpmatrix {1&0\\0&-1} v = \smallpmatrix {1&1} v \iff u^\tp \smallpmatrix {1&0\\0&-1} = \smallpmatrix {1&1} \iff u = \smallpmatrix {1\\-1}$.
Wählt man nun $V_h := \Span (\varphi _1)$ mit $\varphi _1 := \smallpmatrix {1\\1}$, dann ist das diskrete System singulär, weil das LGS $A_h d = b_h$ mit $A_h = a_{1,1} = a(\varphi _1, \varphi _1) = 0$ und $b_h = \ell (\varphi _1) = 2$ nicht lösbar ist.

Bemerkung: Ein Ausweg kann es sein, getrennte Ansatz- und Testräume zu verwenden
(Petrov-Galerkin-Projektion), d. h. seien $V_h, \widetilde {V}_h \le V$ endlich-dimensional, suche $u_h \in V_h$ mit $\forall _{v \in \widetilde {V}_h}\; a(u_h, v) = \ell (v)$. $\widetilde {V}_h$ sollte so gewählt werden, dass das diskrete System regulär ist.

Beispiel: Im Beispiel von eben seien $\varphi _1 \in \real ^2 \setminus \Span (\smallpmatrix {1\\1})$, $\widetilde {\varphi }_1 := \smallpmatrix {1&0\\0&-1} \varphi _1$, $V_h := \Span (\varphi _1)$ und $\widetilde {V}_h := \Span (\widetilde {\varphi }_1)$. Damit ist $A_h = a(\varphi _1, \widetilde {\varphi }_1) = \varphi _1^\tp \smallpmatrix {1&0\\0&-1} \widetilde {\varphi }_1 = \varphi _1^\tp \cancel {\smallpmatrix {1&0\\0&-1} \smallpmatrix {1&0\\0&-1}} \varphi _1 = \norm {\varphi _1}^2 > 0$ und $b_h := \ell (\widetilde {\varphi }_1)$, d. h. das diskrete System ist jetzt regulär.

Implementierung der Finite-Elemente-Methode

1D-Beispiel (Poisson-Gleichung)

Bemerkung: Üblicherweise wählt man Galerkin-Verfahren mit stückweise polynomiellen, globalen stetigen Ansatzfunktionen, die einen lokalen Träger besitzen.

Beispiel: Für $d := 1$, $\Omega := (0, 1)$ sei das äquidistante Gitter $x_i := ih$, $i = 0, \dotsc , n + 1$, mit $n \in \natural $ und $h := \frac {1}{n+1}$ gegeben. Wähle als Ansatzfunktionen die Hütchenfunktionen $\varphi _j$ für $j = 1, \dotsc , n$ (d. h. stückweise linear mit $\varphi _j(x_i) = \delta _{i,j}$). Man spricht auch von der nodalen Basis. Es gilt $\supp \varphi _j = [x_{j-1}, x_{j+1}]$. Als Ansatzraum erhält man den Raum $V_h := \Span ((\varphi _j)_{j=1}^n) \le H^1_0(\Omega )$ der linearen Splines.

Für das Poisson-Problem $-u’’ = f$ in $\Omega $ und $u(0) = 0 = u(1)$ wählt man $a(u, v) := \int _\Omega u’v’\dx $ und $\ell (v) := \int _\Omega fv\dx $. Mit der Ableitung $\varphi _j’(x) = 1/h$ für $x \in (x_{j-1}, x_j)$ und $\varphi _j’(x) = -1/h$ für $x \in (x_j, x_{j+1})$ bekommt man $a_{j,j} = \int _{x_{j-1}}^{x_{j+1}} \frac {1}{h^2} \dx = \frac {2}{h}$, $a_{j+1,j} = \int _{x_j}^{x_{j+1}} \frac {1}{h} (-\frac {1}{h}) \dx = -\frac {1}{h} = a_{j-1,j}$ und $a_{i,j} = 0$ für $|i - j| \ge 2$, weil dann $|\supp (\varphi _i) \cap \supp (\varphi _j)| = 0$.

Somit ist $A_h = \frac {1}{h} \smallpmatrix {2&-1&&\\-1&2&-1&\&\ddots &\ddots &\ddots &\&&-1&2&-1\&&&-1&2}$ tridiagonal und dünn besetzt, weswegen es selbst für große $n$ kein Speicherproblem gibt. Wegen der guten Approximationsfähigkeit von Splines erhält man mit dem Céa-Lemma eine gute Approximation durch die Galerkin-Projektion.

Simplizes

Simplex: Seien $a_0, \dotsc , a_s \in \real ^d$ in allgemeiner Lage, d. h. $a_1 - a_0, \dotsc , a_s - a_0 \in \real ^d$ linear unabhängig. Dann heißt $T := \Conv (a_0, \dotsc , a_s) := \{\sum _{j=0}^s \lambda _j a_j \;|\; \lambda _j \ge 0,\; \sum _{j=0}^s \lambda _j = 1\}$ (nicht-degeneriertes) $s$-dim. Simplex in $\real ^d$ mit Eckenmenge $\E (T) := \{a_0, \dotsc , a_s\}$.

Seitensimplex: Seien $r \in \{0, \dotsc , s\}$ und $\{a_0’, \dotsc , a_r’\} \subset \{a_0, \dotsc , a_s\}$. Dann heißt
$S := \Conv (a_0’, \dotsc , a_r’)$ $r$-dim. Seitensimplex von $T$ mit Eckenmenge $\E (S) := \{a_0’, \dotsc , a_r’\}$.

Einheitssimplex: Der Simplex mit Ecken $0, e_1, \dotsc , e_d \in \real ^d$ heißt Einheitssimplex oder Referenzelement $\widehat {T}$ in $\real ^d$.

Bemerkung: $T$ heißt Strecke, falls $s = 1$ und $d \ge 1$, Dreieck, falls $s = 2$ und $d \ge 2$, und Tetraeder, falls $s = 3$ und $d \ge 3$. $S$ ist Ecke von $T$, falls $r = 0$, und Kante von $T$, falls $r = 1$.

Lemma (baryzentrische Koordinaten): Sei $T$ ein $s$-dim. Simplex in $\real ^d$ und $x \in T$. Dann gibt es eind. bestimmte baryzentrische Koord.en $(\lambda _j)_{j=0}^s$ mit $x = \sum _{j=0}^s \lambda _j a_j$, $\lambda _j \ge 0$ und $\sum _{j=0}^s \lambda _j = 1$.

Bemerkung: Mit baryzentrischen Koordinaten kann man $x \in T$ testen (für $x \in \Span (a_j)_{j=0}^d$ gilt $x \in T \iff \forall _{j=0,\dotsc ,s}\; \lambda _j \ge 0$). Außerdem lässt sich für $x \in T$ herausfinden, ob $x$ auf einem echten Seitensimplex von $T$ liegt ($|\{j \;|\; \lambda _j \not = 0\}| - 1$ ist die Dimension des Seitensimplex).

geometrische Maße: Für einen Simplex $T$ seien $h_T := \diam (T)$ der Durchmesser von $T$, $\varrho _T := 2 \cdot \sup \{R > 0 \;|\; \exists _{x_0 \in T}\; B_R(x_0) \subset T\}$ der Inkugeldurchmesser und $\sigma _T := \frac {h_T}{\varrho _T}$.

Bemerkung: $\sigma _T$ ist ein Maß für die Degeneriertheit von $T$ ($\sigma _T$ groß, falls $T$ einen sehr spitzen Winkel hat, und $\sigma _T$ klein, falls $T$ ähnliche Winkel besitzt) und ist invariant unter Translation und Skalierung.

Bemerkung: Bei der Fehleranalyse und bei der Implementierung der FEM werden Operationen oft auf dem Referenzelement durchgeführt und dann auf beliebige Simplizies durch Transformation übertragen.

Satz (Referenzabbildung):
Seien $T \subset \real ^d$ ein $d$-dim. Simplex mit Ecken $\{a_j\}_{j=0}^d$ und $\widehat {T}$ das Referenzelement. Dann gilt:

Es gibt genau eine affine Abbildung (Referenzabbildung) $F_T\colon \widehat {T} \to T$, $F_T(\widehat {x}) := B\widehat {x} + t$, mit $B \in \real ^{d \times d}$ regulär und $t \in \real ^d$, sodass $F_T(e_j) = a_j$ für $j = 0, \dotsc , d$.
$\norm {B} \le \frac {h_T}{\varrho _{\widehat {T}}}$ (mit $\norm {B} = \norm {B}_2 := \sup _{\widehat {x}\not =0} \frac {\norm {B\widehat {x}}}{\norm {\widehat {x}}}$) und
$\norm {B^{-1}} \le \frac {h_{\widehat {T}}}{\varrho _T}$
$|\det B| = \frac {|T|}{|\widehat {T}|}$ und $\exists _{c, C > 0}\; c\varrho _T^d \le |\det B| \le Ch_T^d$ mit $c, C$ unabhängig von $T$ (abh. von $d$)

Triangulierungen in d Dimensionen

Triangulierung: Seien $\Omega \subset \real ^d$ offen, beschränkt und polygonal berandet sowie $I$ eine endliche Indexmenge. Dann heißt $\T _h := \{T_i \;|\; i \in I\}$ zulässige Triangulierung von $\Omega $, falls

$\forall _{i \in I}\; [\text {$T_i \subset \real ^d$ ist $d$-dim. Simplex}]$,
$\bigcup _{i \in I} T_i = \overline {\Omega }$ (Überdeckung),
$\forall _{i \not = j}\; \interior (T_i) \cap \interior (T_j) \not = \emptyset $ (keine Überlappung) und
für $i \not = j$ ist $S := T_i \cap T_j$ leer oder $S$ ist Seitensimplex von $T_i$ und von $T_j$ (Konformität).

In diesem Fall heißt $h := \max _{i \in I} h_{T_i}$ globale Gitterweite/Feinheit von $\T _h$, $\varrho := \min _{i \in I} \varrho _{T_i}$ minimaler Inkugelradius von $\T _h$ und $\E (\T _h) = \bigcup _{i \in I} \E (T_i)$ Ecken-/Knotenmenge von $\T _h$.

Bemerkung: Eine zulässige Triangulierung besitzt keine hängenden Knoten.
Man kann die FEM auch für nicht-konforme Gitter definieren (aber technisch aufwändiger).
Wenn $\Omega $ keinen polygonalen Rand besitzt, dann kann man mit isoparametrischen Elementen dem Rand approximieren (Zulassen von nicht-linearen Referenzabbildungen).
Man kann die FEM auch für Vierecksgitter, allgemeine polygonale Triangulierungen oder Gitter gemischter Typen durchführen.

Polynome in baryzentrischen Koordinaten

Polynome auf Simplex: Seien $T \subset \real ^d$ ein Simplex und $k \in \natural _0$.
Dann heißt $\PP _k(T) := \{p\colon T \to \real \;|\; p(x) = \sum _{|\beta | \le k,\; \beta \in \natural _0^d} a_\beta x^\beta ,\; a_\beta \in \real \}$ Raum der polynomialen Funktionen bis Grad $k$ auf $T$, wobei $x^\beta := x_1^{\beta _1} \dotsm x_d^{\beta _d}$.

Polynome auf Triangulierung: Sei $\T _h$ eine zul. Triangulierung von $\Omega $ und $k \in \natural _0$.
Dann heißt $\PP _k(\T _h) := \{p \in \C ^0(\Omega ) \;|\; \forall _{T \in \T _h}\; p|_T \in \PP _k(T)\}$ Raum der global stetigen, stückweise polynomialen Fkt.en und $\PP _{k,0}(\T _h) := \{p \in \PP _k(\T _h) \;|\; p|_{\partial \Omega } \equiv 0\}$ Teilraum mit Nullrandwerten.

Lemma (Polynome in baryzentrischen Koordinaten): Sei $T \subset \real ^d$ ein $d$-dim. Simplex. Dann gilt:

Für alle $p \in \PP _k(T)$ gibt es ein $\overline {p} \in \PP _k(\real ^{d+1})$ in der Form $\overline {p}(\lambda ) = \sum _{1 \le |\beta | \le k,\; \beta \in \natural _0^{d+1}} d_\beta \lambda ^\beta $, sodass $\forall _{x \in T}\; p(x) = \overline {p}(\lambda (x))$ mit $\lambda (x)$ den baryzentr. Koord.en von $x$ bzgl. $T$.
Für alle $\overline {p} \in \PP _k(\real ^{d+1})$ gilt $\overline {p}(\lambda (x))|_T \in \PP _k(T)$.

Lineare Interpolation auf Triangulierungen

Satz (lineares Finite Element/Courant-Element):
Seien $T \subset \real ^d$ ein $d$-dim. Simplex mit Ecken $\{a_j\}_{j=0}^d$ und $p_0, \dotsc , p_d \in \real $.
Dann gibt es genau ein $p \in \PP _1(T)$ mit $\forall _{j=0,\dotsc ,d}\; p(a_j) = p_j$.

Bemerkung: Für die Numerik wählt man eine konkrete lokale Basis $\Phi := (\varphi _j)_{j=1}^d$ von $\PP _1(T)$ (z. B. nodale Basis zu den Ecken) und schreibt $p \in \PP _1(T)$ als Linearkombination dieser Basis.
Die $\varphi _j$ heißen auch Formfaktoren (shape functions).

Satz (Ex. + Eind. der $\PP _1(\T _h)$-Intp.):
Seien $\T _h$ eine zul. Triangulierung mit $n_\E := |\E (\T _h)|$, $\{v_j\}_{j=1}^{n_\E } := \E (\T _h)$ und $p_1, \dotsc , p_{n_\E } \in \real $.
Dann gibt es genau ein $p \in \PP _1(\T _h)$ mit $\forall _{j=1,\dotsc ,n_\E }\; p(v_j) = p_j$.

Bemerkung: Die $n_\E $-fache Anwendung des Satzes auf $p_j = \delta _{i,j}$ für $i = 1, \dotsc , n_\E $ liefert die Lagrange-Basis für $\PP _1(\T _h)$.

Satz (Lagrange-Basis für $k = 1$): Sei $\T _h$ eine zul. Triangulierung mit $\{v_j\}_{j=1}^{n_\E } := \E (\T _h)$.
Dann gibt es $\varphi _1, \dotsc , \varphi _{n_\E } \in \PP _1(\T _h)$ mit $\forall _{i,j=1,\dotsc ,n_\E }\; \varphi _i(v_j) = \delta _{i,j}$.
$\Phi := (\varphi _i)_{i=1}^{n_\E }$ ist eine Basis von $\PP _1(\T _h)$ und heißt Lagrange-/nodale Basis von $\PP _1(\T _h)$.

Bemerkung: Man kann zeigen, dass $\PP _1(\T _h) \le H^1(\Omega )$ (siehe folgender Satz) und
$\PP _{1,0}(\T _h) = \{p \in \PP _1(\T _h) \;|\; \forall _{v_j \in \E (\T _h) \cap \partial \Omega }\; p(v_j) = 0\} \le H^1_0(\Omega )$, d. h. man kann $V_h := \PP _{1,0}(\T _h)$ im Galerkin-Verfahren verwenden (lineare FEM). Freiheitsgrade sind nur Werte in inneren Knoten.

Bemerkung: Der folgende Satz begründet im Fall $k = 1$ die Forderung der globalen Stetigkeit (dann ist nämlich $\PP _1(\T _h) \le H^1(\Omega )$).

Satz (schwache Ableitung auf Seitensimplizes):
Seien $\T _h$ eine zul. Triangulierung, $k \in \natural $ und $v\colon \Omega \to \real $ mit $\forall _{T \in \T _h}\; v|_{\interior (T)} \in \C ^k(\interior (T))$.
Dann gilt $v \in H^k(\Omega ) \iff v \in \C ^{k-1}(\overline {\Omega })$.

Polynomiale Interpolation auf Triangulierungen

Bemerkung: Es folgt eine Erweiterung von $\PP _1(\T _h)$ auf höhere Polynomgrade.

Lagrange-Gitter: Sei $T$ ein $d$-dim. Simplex mit Ecken $\{a_j\}_{j=0}^d$.
Dann ist das Lagrange-Gitter der Ordnung $k \in \natural $ von $T$ definiert durch
$G_k(T) := \{\sum _{j=0}^d \lambda _j a_j \;|\; \lambda _j \in \{\frac {i}{k} \;|\; i = 0, \dotsc , k\},\; \sum _{j=0}^d \lambda _j = 1\}$.

Bemerkung: Für $k = 1$ ist $G_1(T) = \E (T)$ und $|G_1(T)| = d+1$.
Für $k \ge 1$ ist $G_k(T) \supset \E (T)$ mit $|G_k(T)| = \binom {d+k}{k}$.
Für einen $(d-1)$-dim. Seitensimplex $S \subset T$ gilt $|G_k(T) \cap S| = |G_k(S)| = \binom {d-1+k}{k}$.
Es gilt $\{\lambda \in \real ^{d+1} \;|\; \lambda _j \in \{\frac {i}{k} \;|\; i = 0, \dotsc , k\},\; \sum _{j=0}^d \lambda _j = 1\} \cong \{\beta \in \natural _0^{d+1} \;|\; |\beta | = k\}$ via $\lambda := \frac {\beta }{k}$.

Lemma (baryzentrische Lagrange-Polynome):
Seien $k \in \natural $ und $p_\beta (\lambda ) := \prod _{\ell =0}^d \prod _{j=0}^{\beta _\ell -1} \frac {\lambda _\ell - j/k}{\beta _\ell /k - j/k}$ für $\beta \in \natural _0^{d+1}$, $|\beta | = k$, und $\lambda \in \real ^{d+1}$. Dann gilt

$p_\beta (\lambda ) \in \PP _k(\real ^{d+1})$ und
$\forall _{\overline {\beta } \in \natural _0^{d+1},\; |\overline {\beta }| \le k}\; p_\beta (\frac {\overline {\beta }}{k}) = \delta _{\beta ,\overline {\beta }}$ (mit $\delta _{\beta ,\overline {\beta }} := \prod _{i=0}^d \delta _{\beta _i,\overline {\beta _i}}$).

Satz (allg. simpl. Lagrange-Element): Seien $k \in \natural $, $T$ ein $d$-dim. Simplex mit Lagrange-Gitter $\{v_j\}_{j=1}^{n_k} := G_k(T)$ für $k \in \natural $ und $n_k := |G_k(T)|$ sowie $p_1, \dotsc , p_{n_k} \in \real $.
Dann gibt es genau ein $p \in \PP _k(T)$ mit $\forall _{j=1,\dotsc ,n_k}\; p(v_j) = p_j$.

Satz (Ex. + Eind. der $\PP _k(\T _h)$-Interpolation):
Seien $\T _h$ eine zul. Triangulierung, $k \in \natural $, $\{v_j\}_{j=1}^{m_k} := G_k(\T _h) := \bigcup _{T \in \T _h} G_k(T)$ die Vereinigung aller Lagrange-Gitter mit $m_k := |G_k(\T _h)|$ und $p_1, \dotsc , p_{m_k} \in \real $.
Dann gibt es genau ein $p \in \PP _k(\T _h)$ mit $\forall _{j=1,\dotsc ,m_k}\; p(v_j) = p_j$.

Bemerkung: Die $m_k$-fache Anwendung des Satzes auf $p_j = \delta _{i,j}$ für $i = 1, \dotsc , m_k$ liefert die Lagrange-Basis für $\PP _k(\T _h)$.

Satz (Lagrange-Basis für $k \in \natural $):
Seien $\T _h$ eine zul. Triangulierung, $k \in \natural $ und $\{v_j\}_{j=1}^{m_k} := G_k(\T _h)$.
Dann existieren $\varphi _1, \dotsc , \varphi _{m_k} \in \PP _k(\T _h)$ mit $\forall _{i,j=1,\dotsc ,m_k}\; \varphi _i(v_j) = \delta _{i,j}$.
$\Phi := \{\varphi _i\}_{i=1}^{m_k}$ ist eine Basis von $\PP _k(\T _h)$ und heißt Lagrange-/nodale Basis der Ordnung $k$.
$\Phi _0 := \{\varphi _i \in \Phi \;|\; v_i \notin \partial \Omega \}$ ist eine Basis von $\PP _{k,0}(\T _h)$ und heißt Lagrange-/nodale Basis von $\PP _{k,0}(\T _h)$ zur Knotenmenge $G_{k,0}(\T _h) := G_k(\T _h) \setminus \partial \Omega $, wobei $m_{k,0} := \dim \PP _{k,0}(\T _h) = |\Phi _0|$.

Lagrange-FEM-Approximation: Seien $a(\cdot , \cdot )$ stetig, koerziv, $\ell (\cdot )$ stetig auf $H^1_0(\Omega )$ und $\T _h$ eine zul. Triangulierung mit inneren Lagrange-Knoten $G_{k,0}(\T _h)$ und nodalen Basisfunktionen $\Phi _0 = \{\varphi _i\}_{i=1}^{m_{k,0}}$. Setze $V_h := \PP _{k,0}(\T _h) = \Span (\Phi _0)$.
Dann heißt $u_h \in V_h$ Lagrange-FEM-Approximation, falls $\forall _{v \in V_h}\; a(u_h, v) = \ell (v)$.

Quadraturen

Bemerkung: Für die Aufstellung des Galerkin-LGS (Assemblierung) werden Integrale der Form $\int _\Omega (A\nabla \varphi _i) \nabla \varphi _j \dx $, $\int _\Omega f\varphi _j \dx $ und $\int _{\partial \Omega } g_N \varphi _j \dsigma (x)$ durch Quadratur berechnet. Es reicht dabei, die Quadratur nur auf Referenzelementen zu betrachten, die auf beliebige Simplizes transformiert und zu zusammengesetzten Quadraturen für Gebietsintegrale kombiniert werden können.

Quadratur: Seien $\widehat {T} \subset \real ^d$ der Einheitssimplex, $\widehat {x}_i \in \widehat {T}$ und $w_i \in \real $ für $i = 1, \dotsc , \ell $.
Dann heißt $\widetilde {I}(g) := \sum _{i=1}^\ell w_i g(\widehat {x}_i)$ Quadratur für $g \in \C ^0(\widehat {T})$.
$\widetilde {I}$ heißt exakt auf $\PP _k(\widehat {T})$ oder von Ordnung $\ge k$, falls $\forall _{g \in \PP _k(\widehat {T})}\; \widetilde {I}(g) = I(g) := \int _{\widehat {T}} g(\widehat {x})\d \widehat {x}$.

Beispiel:

Für $d \in \natural $ erhält man mit dem Schwerpunkt $x_S := \frac {1}{d+1} (1, \dotsc , 1)^\tp \in \real ^d$ von $\widehat {T}$ die Mittelpunktsintegration $\widetilde {I}(g) := |\widehat {T}| g(x_S)$ (von Ordnung $0$).
Für $d = 2$ erhält man mit den Kantenmittelpunkten $m_{i,j} := \frac {1}{2} (e_i + e_j)$ für $i, j = 0, 1, 2$, $i \not = j$, die Formel $\widetilde {I}(g) := \frac {1}{3} |\widehat {T}| \sum _{i,j=0,\; i<j}^2 g(m_{i,j})$ (von Ordnung $2$).
Für $d = 2$ erhält man die Formel
$\widetilde {I}(g) := \frac {1}{60} |\widehat {T}| (3 \sum _{i=0}^2 g(e_i) + 8 \sum _{i,j=0,\; i<j}^2 g(m_{i,j}) + 27 g(x_S))$ (von Ordnung $3$).

Bemerkung: Für einen $d$-dim. Simplex $T \subset \real ^d$ mit Referenzabb. $F_T\colon \widehat {T} \to T$, $F_T(\widehat {x}) = B_T \widehat {x} + t_T$, gilt $\int _T g(x)\dx = |\det B_T| \cdot \int _{\widehat {T}} g(F_T(\widehat {x})) \d \widehat {x} \approx |\det B_T| \cdot \widetilde {I}(g \circ F_T) =: \widetilde {I}_T(g)$.
$\widetilde {I}_T$ ist exakt auf $\PP _k(T)$ genau dann, wenn $\widetilde {I}$ exakt auf $\PP _k(\widehat {T})$ ist.

Bemerkung: Bei Differentialausdrücken muss man die Transformation richtig durchführen. Sei $\varphi \in \C ^1(T)$, dann ist $\widehat {\varphi } := \varphi \circ F_T \in \C ^1(\widehat {T})$ und es gilt $\nabla _{\widehat {x}} \widehat {\varphi }(\widehat {x}) = (\D \widehat {\varphi }(\widehat {x}))^\tp = (\D \varphi (x) \cdot \D F_T)^\tp $
$= ((\nabla _x \varphi (x))^\tp \cdot B)^\tp = B^\tp \nabla _x \varphi (x)$ mit $x = F_T(\widehat {x})$.
Damit gilt z. B. für die Steifigkeitsmatrix-Einträge
$\int _T (\nabla _x \varphi _i)^\tp A (\nabla _x \varphi _j) \dx = \int _{\widehat {T}} (\nabla _{\widehat {x}} \widehat {\varphi }_{\widehat {i}})^\tp B^{-1} A B^{-\tp } (\nabla _{\widehat {x}} \widehat {\varphi }_{\widehat {j}}) |\det B| \d \widehat {x}$
für die nodale Basis $\{\widehat {\varphi }_{\widehat {i}}\}_{\widehat {i}=1}^{n_k}$ und geeignete $\widehat {i}, \widehat {j} \in \{1, \dotsc , n_k\}$.

Bemerkung: Gebietsintegrale werden einfach approximiert durch zusammengesetzte Quadraturen, d. h. $\int _\Omega g(x)\dx = \int _{T \in \T _h} \int _T g(x)\dx \approx \sum _{T \in \T _h} \widetilde {I}_T(g) = \sum _{T \in \T _h} |\det B_T| \sum _{i=1}^\ell w_i g(F_T(\widehat {x}_i))$.

Bemerkung: Die Ordnung der Quadratur sollte der (noch zu diskutierenden) FEM-Konvergenzordnung angepasst sein. Zum einen sollte die Quadraturordnung hoch genug sein, damit die Konvergenz für $h \to 0$ nicht beeinträchtigt wird. Zum anderen sollte sie aber auch nicht zu hoch sein, damit nicht ein Großteil der Rechenzeit für die Quadratur verwendet wird.

Assemblierung

Bemerkung: Der Zusammenhang zwischen den lokalen und den globalen Freiheitsgraden wird durch eine sog. globale Indexabbildung realisiert. Seien dazu $\{\widehat {\varphi }_{\widehat {j}}\}_{\widehat {j}=1}^{n_k}$ eine Basis von $\PP _k(\widehat {T})$ und $\{\varphi _i\}_{i=1}^{m_k}$ eine Basis von $\PP _k(\T _h)$. Dann heißt $\widehat {g}\colon \T _h \times \{1, \dotsc , n_k\} \to \{1, \dotsc , m_k\}$ globale Indexabbildung, falls $\forall _{T \in \T _h} \forall _{\widehat {j}=1,\dotsc ,n_k}\; \widehat {\varphi }_{\widehat {j}} = \varphi _i \circ F_T$ für $i := \widehat {g}(T, \widehat {j})$.
Mit der globalen Indexabb. ist die Kenntnis von $\{\varphi _i\}_{i=1}^{m_k}$ nicht mehr nötig, es reicht, eine Basis auf dem Referenzelement zu definieren.

Bemerkung: Die direkte Berechnung der Steifigkeitsmatrix ist i. A. teuer. Für die Poisson-Gleichung muss man $a_{i,j} = \int _\Omega (\nabla \varphi _i)^\tp (\nabla \varphi _j) \dx = \sum _{T \in \T _h} \int _T (\nabla \varphi _i)^\tp (\nabla \varphi _j) \dx $ für $i,j = 1, \dotsc , m$ mit $m := m_{k,0}$ berechnen. Für $k = 1$ ist $|\T _h| = \O (m)$, d. h. der Gesamtaufwand für die Berechnung von $A_h$ ist $\O (m^3)$ (inpraktikabel für $m$ groß).

Stattdessen nutzt man die Lokalität und die globale Indexabbildung:
Für $S_{i,j} := \supp (\varphi _i) \cap \supp (\varphi _j)$ gilt $a_{i,j} = \int _{S_{i,j}} (\nabla \varphi _i)^\tp (\nabla \varphi _j) \dx $
$= \sum _{T \in \T _h,\; T \subset S_{i,j}} \int _T \nabla \varphi _i \nabla \varphi _j \dx = \sum _{T \in \T _h,\; T \subset S_{i,j}} \widehat {a}_{\widehat {i},\widehat {j}}$, $\widehat {a}_{\widehat {i},\widehat {j}} := \int _{\widehat {T}} |\det B_T| (\nabla \widehat {\varphi }_{\widehat {i}})^\tp B_T^{-1} B_T^{-\tp } (\nabla \widehat {\varphi }_{\widehat {j}}) \d \widehat {x}$,
mit $\widehat {i}, \widehat {j} \in \{1, \dotsc , n_k\}$, sodass $i = \widehat {g}(T, \widehat {i})$ und $j = \widehat {g}(T, \widehat {j})$.

Statt einer Schleife über $(i,j)$ kann man nun durch Addition der Beiträge der lokalen Steifigkeitsmatrix $A_{h,T} := (\widehat {a}_{\widehat {i},\widehat {j}})_{\widehat {i},\widehat {j}=1}^{n_k}$ die globale Steifigkeitsmatrix $A_h$ assemblieren:

Setze $A_h := 0$.
Wiederhole für alle $T \in \T _h$:
- Berechne $A_{h,T}$.
- Wiederhole für alle $\widehat {i}, \widehat {j} = 1, \dotsc , n_k$: Setze $(A_h)_{g(T,\widehat {i}),g(T,\widehat {j})} \;+\!\!:= (A_{h,T})_{\widehat {i},\widehat {j}}$.

Die Gesamtkomplexität beträgt nun $\O (|\T _h| n_k^2) = \O (mn_k^2)$ was wegen $n_k$ konstant und klein wesentlich besser als $\O (m^3)$ ist.

Ähnlich ist die Assemblierung von $b_h$ möglich. Das geht sogar simultan mit $A_h$ (ohne zusätzliche Schleifen), d. h. ein einziger Gitterdurchlauf reicht zur Assemblierung des gesamten Systems aus.

Bemerkung: $A_h$ ist dünnbesetzt, da $(A_h)_{i,j} = 0$ für $|\supp (\varphi _i) \cap \supp (\varphi _j)| = 0$.
Ist $r$ die maximale Kantenzahl für einen Knoten, dann existieren für $k = 1$ höchstens $r + 1$ Nichtnull-Einträge pro Zeile und für $k > 1$ höchstens $r \cdot |G_k(T)|$.
Dies muss man bei der Implementierung durch Sparse-Matrizen berücksichtigen (insb. sollte bei Verfeinerungen $r$ nicht unbegrenzt wachsen).

Bemerkung: Für $k \ge d+1$ gibt es innere Lagrange-Knoten. Die entsprechenden Zeilen von $A_h$ haben nur Einträge für Knoten desselben Simplex, nicht aber seiner Nachbarn. Dies kann man ausnutzen, indem man z. B. durch Zeilenumformungen Einheitsvektoren in den jeweiligen Zeilen erzeugt und so nur Unbekannte auf Seitensimplizes übrig bleiben (vorteilhaft für $k$ groß).
Man nennt dies innere/statische Kondensation.

Verallgemeinerungen

finites Element: Das Tripel $(T, \Phi , \N )$ heißt finites Element, falls

$T \subset \real ^d$ beschr. und abg. mit Lipschitz-Rand und $\interior (T) \not = \emptyset $ (Element-Geometrie),
$\Phi := \{\varphi _1, \dotsc , \varphi _k\}$ l. u. Fkt.en auf $T$ (Formfaktoren/-fkt.en, shape functions) mit
$\P := \Span (\Phi )$ dem zugehörigen diskreten Fkt.enraum und
$\N := \{N_1, \dotsc , N_k\}$ eine Basis von $\P ’$ ist (Menge der lokalen Freiheitsgrade).

$\Phi $ heißt nodale Basis und die $N_i$ heißen nodale Variablen, falls $\forall _{i,j=1,\dotsc ,k}\; N_i(\varphi _j) = \delta _{i,j}$.

Bemerkung: Die Definition verallgemeinert Lagrange-Elemente.
Sei $T$ ein Simplex mit Lagrange-Gitter $\{v_i\}_{i=1}^{n_{\widetilde {k}}} := G_{\widetilde {k}}(T)$, $k := n_{\widetilde {k}}$, $\Phi $ die nodale Basis von $\PP _{\widetilde {k}}(T)$ (d. h. $\varphi _i(v_j) = \delta _{i,j}$) und $N_i(p) := p(v_i)$ für $p \in \PP _{\widetilde {k}}(T)$, dann ist $(T, \Phi , \N )$ ein finites Element. Wegen $N_i(\varphi _j) = \varphi _j(v_i) = \delta _{i,j}$ sind die $N_i$ nodale Variablen.

Bemerkung: Statt Simplizes kann man auch andere Geometrien verwenden. Auf Rechtecken und Würfeln verwendet man statt linearen Formfaktoren eher bi- bzw. trilineare.
Allgemein sei für $d \in \natural $ der Funktionenraum $Q_1([0,1]^d) := \bigotimes _{i=1}^d \PP _1([0,1])$ aller $d$-variaten Polynome mit Koordinatengrad $\le 1$ definiert.
Beispielsweise hat $p \in Q_1([0,1]^2)$ für $d = 2$ die Gestalt $p(x_1, x_2) = a + bx_1 + cx_2 + dx_1 x_2$. Man setzt nun $\Phi := (x_1 x_2, (1-x_1)x_2, x_1(1-x_2), (1-x_1)(1-x_2))^\tp $ und $\N _i(p) := p(a_i)$ für $p \in Q_1([0,1]^2)$ und $i = 1, \dotsc , 4$ mit $a_1, \dotsc , a_4 \in \{0, 1\}^2$ den Ecken von $[0, 1]^2$.
Analog verfährt man für $d = 3$ (trilineare Elemente) oder für $\widetilde {k} = 2$ (bi-/triquadratische Elemente).

Bemerkung: Statt Punktauswertungen kann man auch Ableitungswerte vorgeben. Das kubische Hermite-Element erhält man wie folgt: Sei $T \subset \real ^2$ ein Dreieck mit Ecken $a_0, a_1, a_2$ und Schwerpunkt $x_S$. Dann ist durch Vorgabe von $p(a_i), \nabla p(a_i), p(x_S)$ für $i = 0, 1, 2$ eindeutig ein interpolierendes Polynom $p \in \PP _3(T)$ definiert. Die lokalen Freiheitsgrade sind somit gegeben durch $\N := (N_1(p), \dotsc , N_{10}(p))$
$:= (p(x_S), p(a_0), p(a_1), p(a_2), \partial _{x_1} p(a_0), \partial _{x_1} p(a_1), \partial _{x_1} p(a_2), \partial _{x_2} p(a_0), \partial _{x_2} p(a_1), \partial _{x_2} p(a_2))$.
Dabei existiert eine eindeutige Basis $\Phi := (\varphi _1, \dotsc , \varphi _{10})$ von $\PP _3(T)$ mit $N_i(\varphi _j) = \delta _{i,j}$.
Man kann zeigen, dass zusammengesetzte Funktionen aus kubischen Hermite-Elementen (auf zul. Triangulierungen) in $H^1(\Omega )$ sind, i. A. aber nicht in $H^2(\Omega )$.

Bemerkung: Ein Element, welches durch Zusammensetzen $H^2(\Omega )$-Funktionen liefert, ist das sog. Agyris-Element auf Dreiecken. Dazu sei $T \subset \real ^2$ ein Dreieck mit Ecken $a_0, a_1, a_2$ und Kantenmittelpunkten $m_0, m_1, m_2$. Dann ist durch Vorgabe von $p(a_i), \nabla p(a_i), \D ^2 p(a_i), \nabla p(m_i) \cdot n_i$ für $i = 0, 1, 2$ (mit $n_i \in \real ^2$ dem Normalenvektor in $m_i$) eindeutig ein interpolierendes Polynom
$p \in \PP _5(T)$ definiert (dabei enthält $\D ^2 p(a_i)$ die drei Unbekannten $\partial _{x_1}^2 p(a_i), \partial _{x_2}^2 p(a_i), \partial _{x_1} \partial _{x_2} p(a_i)$).

Approximationssätze und FEM-Fehlerabschätzung

Bemerkung: Zur Motivation sei $I_h\colon V \to V_h$ ein linearer (Interpolations-)Operator mit Approximationsgüte $\norm {u - I_h u} \le Ch^r$ mit $C > 0$ möglichst klein und $r > 0$ möglichst groß. Dann folgt mit dem Lemma von Céa, dass $\norm {u - u_h} \le \frac {\gamma }{\alpha } \inf _{v \in V_h} \norm {u - v} \le \frac {\gamma }{\alpha } \norm {u - I_h u} \le \frac {\gamma }{\alpha } Ch^r$, also die Konvergenz für $h \to 0$, die Konvergenzordnung $r$ und eine Fehlerschranke für die Galerkin-Projektion $u_h$.

Bemerkung: Seien $\Omega \subset \real ^d$ polygonal berandet, $V := H^m(\Omega )$, $V_h := \PP _k(\T _h)$ für eine zul. Triang. $\T _h$ von $\Omega $ und $I_h$ der Lagrange-Interpolationsoperator. Damit $I_h\colon H^m(\Omega ) \to \PP _k(\T _h)$ sinnvoll definiert ist, muss $H^m(\Omega )$ Punktauswertungen erlauben, d. h. jedes $v \in H^m(\Omega )$ muss einen stetigen Repräsentanten $\widetilde {v} \in \C ^0(\Omega )$ besitzen mit $\norm {v - \widetilde {v}}_{H^m(\Omega )} = 0$, damit Punkauswertungen von $v$ als Punktauswertungen von $\widetilde {v}$ definiert werden können.
Nach dem 2. Sobolevschen Einbettungssatz kann $m$ je nach $d$ aber immer so gewählt werden, dass $I_h$ wohldefiniert ist (z. B. für $d = 2$ reicht z. B. $m = 2$). Im Folgenden seien $d, m$ immer derart, dass $I_h$ wohldefiniert ist.

Bramble-Hilbert-Lemma

gebrochene Normen: Sei $\T _h$ eine zul. Triang. von $\Omega $. Dann ist der gitterabhängige Raum $H^m(\T _h) := \{v\colon \Omega \to \real \;|\; \forall _{T \in \T _h}\; v|_T \in H^m(T)\}$ zusammen mit der Seminorm
$|v|_{H^m(\T _h)} := \sqrt {\sum _{T \in \T _h} |v|_{H^m(T)}^2}$ und der Norm $\norm {v}_{H^m(\T _h)} := \sqrt {\sum _{T \in \T _h} \norm {v}_{H^m(T)}^2}$ definiert.

Bemerkung: Offensichtlich gilt $H^m(\T _h) \supset H^m(\Omega )$ und $\forall _{v \in H^m(\Omega )}\; \norm {v}_{H^m(\T _h)} = \norm {v}_{H^m(\Omega )}$.

Satz (Rellichscher Auswahlsatz): Seien $m \in \natural _0$ und $\Omega \subset \real ^d$ polygonal berandet.
Dann ist die Einbettung $H^{m+1}(\Omega ) \to H^m(\Omega )$ kompakt.

Bemerkung: Die Einheitskugel in $H^{m+1}(\Omega )$ ist kompakt bzgl. der $\norm {\cdot }_{H^m(\Omega )}$-Norm bzw. jede bzgl. $\norm {\cdot }_{H^{m+1}(\Omega )}$ beschränkte Folge enthält eine bzgl. $\norm {\cdot }_{H^m(\Omega )}$ konvergente Teilfolge.

Satz (lokaler Interpolationsfehler): Seien $K \subset \real ^p$ polygonal berandet und abgeschlossen sowie $k \ge 2$ und $\{x_i\}_{i=1}^{n_k} \subset K$, sodass die Polynominterpolation $I\colon H^k(K) \to \PP _{k-1}(K)$ wohldefiniert ist (insb. ist die Einbettung $H^k(K) \to \C ^0(K)$ stetig und $n_k := \binom {k+1}{2}$).
Dann gilt $\exists _{C = C(K, k) > 0} \forall _{v \in H^k(K)}\; \norm {v - Iv}_{H^k(K)} \le C |v|_{H^k(K)}$.

Bemerkung: Die Voraussetzungen sind z. B. für $d = k = 2$, $K = T$ Dreieck und $\{x_1, x_2, x_3\}$ Ecken von $T$ erfüllt.

Lemma (Bramble-Hilbert): Seien $K \subset \real ^d$ polygonal berandet und abgeschlossen sowie $k \ge 2$ und $g \in (H^k(K))’$ mit $\forall _{p \in \PP _{k-1}(K)}\; g(p) = 0$.
Dann gilt $\exists _{C = C(g, K, k) > 0} \forall _{v \in H^k(K)}\; |g(v)| \le C |v|_{H^k(K)}$.

Interpolationsabschätzung

Satz (Transformationsformel):
Seien $T$ ein $d$-dim. Simplex mit Referenzabbildung $F_T(\widehat {x}) = B\widehat {x} + t$ sowie $v \in H^m(T)$.
Dann ist $\widehat {v} := v \circ F_T \in H^m(\widehat {T})$ und es gilt
$\exists _{C = C(d, m) > 0} \forall _{v \in H^m(T)}\; |\widehat {v}|_{H^m(\widehat {T})} \le C \norm {B}^m |\det B|^{-1/2} |v|_{H^m(T)}$.

Satz (Interpolationsabschätzung):
Seien $k \ge 2$, $\T _h$ eine zul. Triangulierung von $\Omega \subset \real ^d$, $h \le h_{\max }$ und $\sigma > 0$ mit $\forall _{T \in \T _h}\; \sigma _T \le \sigma $. Sei außerdem $I_h\colon H^k(\Omega ) \to \PP _{k-1}(\T _h)$ die Lagrange-Interpolation.
Dann gilt $\exists _{C = C(k, \Omega , d, h_{\max }, \sigma ) > 0} \forall _{m=0,\dotsc ,k} \forall _{u \in H^k(\Omega )}\; \norm {u - I_h u}_{H^m(\T _h)} \le Ch^{k-m} |u|_{H^k(\Omega )}$.

Bemerkung: Für $k = 2$ und $I_h\colon H^2(\Omega ) \to \PP _1(\T _h)$ erhält man
$\norm {u - I_h u}_{H^1(\Omega )} \le Ch |u|_{H^2(\Omega )}$ und $\norm {u - I_h u}_{L^2(\Omega )} \le Ch^2 |u|_{H^2(\Omega )}$.
Ähnliche Abschätzungen gelten auch für quadratische Gitter und bilineare Elemente.

nicht-entartet: Eine Folge $(\T _i)_{i\in \natural }$ von zul. Triang.en mit $\lim _{i \to \infty } h_i = 0$ heißt nicht-entartet, falls $\exists _{\sigma >0} \forall _{i \in \natural } \forall _{T \in \T _i}\; \sigma _T = \frac {h_T}{\varrho _T} \le \sigma $.

quasi-uniform: Eine Folge $(\T _i)_{i\in \natural }$ von zul. Triang.en mit $\lim _{i \to \infty } h_i = 0$ heißt quasi-uniform, falls $\exists _{\sigma >0} \forall _{i \in \natural } \forall _{T \in \T _i}\; \frac {h_i}{\sigma _T} \le \sigma $.

Bemerkung: Nicht-entartete Gittersequenzen lassen auch lokale Verfeinerungen zu und die Innenwinkel sind nach unten beschränkt. Bei quasi-uniformen Gittersequenzen ist $h_T \le h \le Ch_T$.
Quasi-uniforme Gittersequenzen sind nicht-entartet.

Satz (Konvergenz der Interpolation): Seien $k \ge 2$, $\{\T _i\}$ eine nicht-entartete Gittersequenz, $h_{\max } := \max _{i \in \natural } h_i$ und $I_{h_i}\colon H^k(\Omega ) \to \PP _{k-1}(\T _i)$ die Lagrange-Interpolation.
Dann gilt $\forall _{m = 0, \dotsc , k - 1} \forall _{u \in H^m(\Omega )}\; \lim _{i \to \infty } \norm {u - I_{h_i} u}_{H^m(\T _i)} = 0$.

Bemerkung: Die Interpolationsabschätzung sagt insb. aus, dass
$\norm {u - I_h u}_{H^m(\T _h)} \le Ch^{k-m} \norm {u}_{H^k(\Omega )}$, d. h. der Interpolationsfehler wird für $m < k$ in schwächeren Normen gemessen als $u$, wobei man $h$-Potenzen gewinnt.
Sog. inverse Abschätzungen leisten das Umgekehrte, indem man $h$-Potenzen opfert. Sie gelten aber nur für FE-Ansatzfunktionen, nicht für den ganzen Sobolev-Raum.

Satz (inverse Abschätzung):
Seien $k \in \natural $, $\T _h$ eine zul. Triangulierung von $\Omega \subset \real ^d$ und $\sigma > 0$ mit $\forall _{T \in \T _h}\; \sigma _T \le \sigma $.
Dann gilt $\exists _{C = C(k, \Omega , d, \sigma ) > 0} \forall _{m=0,\dotsc ,k} \forall _{v_h \in \PP _k(\T _h)}\; \norm {v_h}_{H^k(\T _h)} \le Ch^{m-k} \norm {v_h}_{H^m(\T _h)}$.

Bemerkung: Für $d = 2$ und lineare Elemente ($k = 1$, $m = 0$) gilt also
$\norm {v_h}_{H^1(\T _h)} \le Ch^{-1} \norm {v_h}_{L^2(\T _h)}$.

FEM-a-priori-Abschätzungen

Satz (FEM-a-priori-Fehlerschranke in $H^1$):
Seien $\Omega \subset \real ^d$ offen, beschränkt und polygonal berandet, $a(\cdot , \cdot )$ stetig, koerziv und $\ell (\cdot )$ stetig auf $H^1_0(\Omega )$, $u \in H^1_0(\Omega )$ die eindeutige schwache Lösung, $\T _h$ eine zulässige Triangulierung und $\sigma > 0$ mit $\forall _{T \in \T _h}\; \sigma _T \le \sigma $ sowie $V_h := \PP _{k,0}(\T _h)$ mit $k \in \natural $ und $u_h \in V_h$ der Lagrange-FEM-Lösung.
Wenn es ein $s \in \natural $ gibt mit $h \in H^{s+1}(\Omega ) \cap H^1_0(\Omega )$, dann gilt
$\exists _{C = C(\Omega , d, \sigma , k) > 0}\; \norm {u - u_h}_{H^1(\Omega )} \le Ch^s \norm {u}_{H^{s+1}(\Omega )}$.

Satz (Konvergenz der FEM): Sei $(\T _i)_{i \in \natural }$ eine nicht-entartete Gittersequenz ($\lim _{i \to \infty } h_i = 0$), sodass die Voraussetzungen des vorherigen Satzes für jedes $\T _i$ erfüllt seien.
Dann gilt $\lim _{i \to \infty } \norm {u_{h_i} - u}_{H^1(\Omega )} = 0$.

Bemerkung: Um $u \in H^{s+1}(\Omega )$ zu garantieren, wären zusätzlich $\C ^{s+1}$-Regularität von $\partial \Omega $ und $f \in H^{s-1}(\Omega )$ für $\ell (v) = \int _\Omega fv \dx $ notwendig (Satz von Friedrichs).
Für lineare FEM ($k = 1$) reicht $H^2$-Regularität ($s = 1$), denn dann folgt lineare Konvergenz in der $H^1$-Norm, weil $\norm {u - u_h}_{H^1(\Omega )} \le Ch\norm {u}_{H^2(\Omega )} \le Ch\norm {f}_{L^2(\Omega )}$.
Für polygonal berandete Gebiete kann man eigentlich keine $H^3$-Regularität garantieren, weil kein $\C ^3$-Rand vorhanden ist. Daher kann man nicht garantieren, dass quadratische oder kubische FEM eine bessere Konvergenzordnung besitzen. In der Praxis sind allerdings quadratische/kubische FEM gegenüber linearen FEM zu bevorzugen.

Aubin-Nitsche-Trick

Bemerkung: Wegen $\norm {\cdot }_{L^2(\Omega )} \le \norm {\cdot }_{H^1(\Omega )}$ folgt aus der A-priori-$H^1$-Fehlerschranke trivialerweise eine $L^2$-Abschätzung mit derselben $h$-Potenz. Dies ist jedoch nicht optimal, mittels eines Dualitätsarguments (Aubin-Nitsche-Trick) gewinnt man eine $h$-Potenz.

Satz (Aubin-Nitsche): Seien $H$ ein Hilbertraum mit Skalarprodukt $\innerproduct {\cdot , \cdot }_H$ und Norm $\norm {\cdot }_H$ und $V \le H$ ein Unterraum, der mit dem Skalarprodukt $\innerproduct {\cdot , \cdot }_V$ und der Norm $\norm {\cdot }_V$ ein Hilbertraum ist, sodass die Einbettung $V \to H$ stetig ist (d. h. $\forall _{v \in V}\; \norm {v}_H \le C \norm {v}_V$).
Sei außerdem die schwache Form $\forall _{v \in V}\; a(u, v) = \ell (v)$ mit $a\colon V \times V \to \real $ einer stetigen, koerziven Bilinearform, wobei $u \in V$ die schwache Lösung und $u_h \in V_h \le V$ die Galerkin-Projektion ist.
Dann gilt $\norm {u - u_h}_H = \gamma \norm {u - u_h}_V \cdot \sup _{g \in H \setminus \{0\}} (\frac {1}{\norm {g}_H} \inf _{v_h \in V_h} \norm {\varphi _g - v_h}_V)$, wobei für $g \in H$ die duale Lösung $\varphi _g \in V$ definiert ist als die schwache Lösung von $\forall _{w \in V}\; a(w, \varphi _g) = \innerproduct {g, w}_H$ ist.

Satz (FEM-a-priori-Fehlerschranke in $L^2$): Unter den Vor.en der A-priori-$H^1$-Fehlerschranke gilt $\norm {u - u_h}_{L^2(\Omega )} \le Ch \norm {u - u_h}_{H^1(\Omega )}$, d. h. insb. im Fall von $H^{s+1}$-Regularität
$\norm {u - u_h}_{L^2(\Omega )} \le Ch^{s+1} \norm {u}_{H^{s+1}(\Omega )} \le Ch^{s+1} \norm {f}_{H^{s-1}(\Omega )}$.

Bemerkung: Für lineare FEM ($k = 1$, $s = 1$) folgt im Fall von $H^2$-Regularität
$\norm {u - u_h}_{L^2(\Omega )} \le Ch^2 \norm {u}_{H^2(\Omega )}$.

Bemerkung: Die bisherigen Abschätzungen können keine lokal großen Fehler ausschließen, was das Folgende macht.

Satz (FEM-a-priori-Fehlerabschätzung in $L^\infty $): Unter den Vor.en der A-priori-$H^1$-Fehlerschranke sowie $d = 2$ und $\T _h$ quasi-uniform gilt $\norm {u - u_h}_{L^\infty (\Omega )} \le Ch\norm {f}_{L^2(\Omega )}$.

Bemerkung: Die Abschätzung ist nicht scharf, für $d = 2$ gilt z. B.
$\norm {u - u_h}_{L^\infty (\Omega )} \le Ch^2 |\log h|^{3/2} \norm {D^2 u}_{L^\infty (\Omega )}$, für $d = 3$ verschwindet der $\log $-Term sogar.

A-posteriori-Schätzer und Gitteradaptivität

Bemerkung: Lagrange-Interpolationsoperatoren erfordern Punktauswertungen, d. h. mindestens $u \in H^2(\Omega )$. Sog. Clément-Operatoren bieten eine Appr.möglichkeit für $H^1(\Omega )$-Funktionen.

Patches: Sei $\T _h$ eine zul. Triangulierung von $\Omega $ mit $\{v_i\}_{i=1}^{m_\E } := \E (\T _h)$.
Zu jedem $v_i$ definiere den Patch aller angrenzenden Elemente $w_i := \bigcup _{T \in \T _h,\; v_i \in T} T$ und für jedes $T \in \T _h$ den Patch der Nachbarn $w_T := \bigcup _{v_i \in T} w_i = \bigcup _{T’ \in \T _h,\; T’ \cap T \not = \emptyset } T’$.

Clément-Approximation: Für $V_h := \PP _1(\T _h)$ mit nodaler Basis $\{\varphi _i\}_{i=1}^{m_\E }$ sei der
Clément-Operator $C_h\colon H^1(\Omega ) \to \PP _1(\T _h)$ definiert durch $C_h v := \sum _{i=1}^{m_\E } (P_i v)(v_i) \varphi _i$ mit der orthogonalen $L^2$-Projektion $P_i\colon L^2(w_i) \to \PP _0(w_i)$ auf Konstanten.

Satz (Clément-Approximationsfehler): Seien $\T _h$ eine zul. Triang. und $\sigma > 0$ mit $\forall _{T \in \T _h}\; \sigma _T \le \sigma $.
Dann gilt $\exists _{C = C(d, \sigma ) > 0} \forall _{T \in \T _h} \forall _{\text {$S \subset \partial T$ Seitensimplex}} \forall _{v \in H^1(\Omega )} \forall _{m = 0, 1}$
$\norm {v - C_h v}_{H^m(T)} \le Ch_T^{1-m} \norm {v}_{H^1(w_T)},\; \norm {v - C_h v}_{L^2(S)} \le Ch_T^{1/2} \norm {v}_{H^1(w_T)}$.

Bemerkung: Die FEM-Approximation $u_h \in V_h$ erzeugt ein Residuum, wenn man $u_h$ in die starke Form der PDE einsetzt. Daraus kann man A-posteriori-Fehlerschätzer definieren, die bis auf Konstanten obere und untere Schranken für den Fehler darstellen. Im Folgenden wird nur das Poisson-Problem betrachtet.

Residuum: Seien $\T _h$ eine zul. Triangulierung und $u_h \in V_h := \PP _{k,0}(\T _h) \le H^1_0(\Omega )$ die FEM-Lösung der Poisson-Gleichung. Dann ist das elementbasierte Residuum für $T \in \T _h$ definiert als $R_T = R_T(u_h) := \Delta u_h + f|_T$ und das kantenbasierte Residuum der Ableitungssprünge ist für $S \in \S _0$ mit der Menge der inneren Kanten $\S _0 := \{\text {$S$ Seitensimplex} \;|\; \exists _{T \in \T _h}\; S \subset \partial T,\; S \not \subset \partial \Omega \}$ definiert als $R_S = R_S(u_h) := [\frac {\partial u_h}{\partial n}] := \frac {\partial u_h}{\partial n}|_{T_1} - \frac {\partial u_h}{\partial n}|_{T_2}$ für $T_1, T_2 \in \T _h$ mit $T_1 \not = T_2$ und $S \subset T_1 \cap T_2$.

residualer Fehlerschätzer:
Für $T \in \T _h$ heißt $\eta _{T,R} := (h_T^2 \norm {R_T}_{L^2(T)}^2 + \frac {1}{2} \sum _{S \subset \partial T} h_S \norm {R_S}_{L^2(S)}^2)^{1/2}$ lokaler Fehlerschätzer und
$\eta _R := (\sum _{T \in \T _h} \eta _{T,R}^2)^{1/2} = (\sum _{T \in \T _h} h_T^2 \norm {R_T}_{L^2(T)}^2 + \sum _{S \in \S _0} h_S \norm {R_S}_{L^2(S)}^2)^{1/2}$ globaler Fehlersch.

Satz (obere A-posterori-Fehlerschranke): Seien $\T _h$ eine zul. Triang. und $\sigma > 0$ mit $\forall _{T \in \T _h}\; \sigma _T \le \sigma $.
Dann gilt $\exists _{C = C(\Omega , \sigma )}\; \norm {u - u_h}_{H^1(\Omega )} \le C\eta _R$.

Bemerkung: Diese Schranke ist ein A-posteriori-Fehlerschätzer, d. h. erst nach Bestimmung der numerischen Lösung $u_h$ kann die Schranke (bis auf die Konstante) berechnet werden.
Für $u_h \in \PP _1(\T _h)$ ist $\Delta u_h \equiv 0$, d. h. $R_T$ ist dann ohne Kenntnis von $u_h$ a priori berechenbar.
Bei nicht-trivialem $f$ ist $\norm {R_T}_{L^2(T)}$ i. A. nicht exakt berechenbar. Daher wählt man in der Praxis eine Approximation $f_h \approx f$ und approximiert die Residuen durch $\widetilde {R}_T := \Delta u_h + f_h$, $\widetilde {\eta }_{T,R} := (h_T \norm {\widetilde {R}_T}_{L^2(T)}^2 + \frac {1}{2} \sum _{S \subset \partial T} h_S \norm {R_S}_{L^2(S)}^2)^{1/2}$ und $\widetilde {\eta }_R := (\sum _{T \in \T _h} \widetilde {\eta }_{T,R}^2)^{1/2}$. Durch die Dreiecksungleichung erhält man $\norm {\Delta u_h + f}_{L^2(T)}^2 \le \norm {\Delta u_h + f_h}_{L^2(T)} + \norm {f - f_h}_{L^2(T)}$ und damit $\norm {u - u_h}_{H^1(\Omega )} \le C\widetilde {\eta }_R + C (\sum _{T \in \T _h} h_T^2 \norm {f - f_h}_{L^2(T)}^2)^{1/2}$.

Bemerkung: $\eta _R$ ist bis auf eine Konstante eine obere Schranke des Fehlers und heißt daher zuverlässiger Schätzer. Man kann zeigen, dass $\eta _R$ und $\widetilde {\eta }_R$ auch untere Schranken des Fehlers sind, man spricht von einem effizienten Schätzer.

Satz (untere A-posteriori-Fehlerschranke): Seien $\T _h$ eine zul. Triang., $\sigma > 0$ mit $\forall _{T \in \T _h}\; \sigma _T \le \sigma $.
Definiere für einen Seitensimplex $S$ den Patch der Kantennachbarn $w_S := \bigcup _{T \in \T _h,\; S \subset \partial T} T$ und für $T \in \T _h$ analog $\widetilde {w}_T := \bigcup _{S \subset \partial T} w_S$.
Dann gilt $\exists _{C = C(\Omega , \sigma ) > 0}\; \widetilde {\eta }_{T,R} \le C(\norm {u - u_h}_{H^1(\widetilde {w}_T)}^2 + \sum _{T’ \subset w_T} h_{T’}^2 \norm {f - f_h}_{L^2(T’)}^2)^{1/2}$ und
$\widetilde {\eta }_R \le C(\norm {u - u_h}_{H^1(\Omega )}^2 + \sum _{T \in \T _h} h_T^2 \norm {f - f_T}_{L^2(T)}^2)^{1/2}$.