Quelltext der Seite Sattelpunktproblem

In der [[Mathematik]] bezeichnet ein '''Sattelpunktproblem''' eine spezielle Problemklasse, welche auf ein [[lineares Gleichungssystem]] in Blockgestalt führt, und zwar eine <math>(n+m)\times(n+m)</math>-[[Matrix (Mathematik)|Matrix]] <math>M</math> der Form
:<math>M = \begin{pmatrix}A & B \\ B^T & 0\end{pmatrix},</math>
wobei <math>A</math> eine <math>n\times n</math>-Matrix ist und <math>B</math> eine <math>n\times m</math>-Matrix. Der <math>0</math>-Block ist von der Größe <math>m\times m</math>.

== Ursprung von Sattelpunktproblemen ==

Gleichungssysteme in Sattelpunktform entstehen in vielen Anwendungen, beispielsweise bei [[Optimierung (Mathematik)|Optimierungsproblemen]] unter [[Nebenbedingung|Nebenbedingungen]].

Beispiel hierfür ist das Lösen von [[Quadratisches Programm|quadratischen Programmen mit Gleichungsrestriktionen]] durch Anwendung der [[Karush-Kuhn-Tucker-Bedingungen]]. Diese sind Äquivalent zur Bestimmung eines Sattelpunkt bei der [[Lagrange-Dualität]], was den Namen erklärt.

Eine weitere wichtige Klasse von Sattelpunktproblemen stammt aus der [[Diskretisierung]] von [[Partielle Differentialgleichung|partiellen Differentialgleichungen]]. Das wichtigste Beispiel sind die [[Inkompressibles Fluid|inkompressiblen]] [[Navier-Stokes-Gleichungen]] in [[Newton-Verfahren|linearisierter Form]], diskretisiert beispielsweise mit [[Finite-Elemente-Methode|finiten Elementen]], welches auf natürliche Weise ein lineares Gleichungssystem in obiger Blockgestalt ergibt. Die [[Blockmatrix]] <math>A</math> entsteht dort aus der Diskretisierung des [[Geschwindigkeit|Geschwindigkeitsterms]] <math>\vec{u}</math> in der ''Impulsgleichung'', die Matrix <math>B</math> aus der Diskretisierung des [[Druck (Physik)|Druckterms]] <math>p</math>, und die Matrix <math>B^T</math> resultiert aus der Diskretisierung der Geschwindigkeit in der ''Kontinuitätsgleichung''.

== Lösung von Sattelpunktgleichungen ==

Anwendungen wie die diskretisierten Navier-Stokes-Gleichungen erfordern die Lösung eines linearen Gleichungssystems
:<math>M x = b.</math>
Damit das Gleichungssystem eindeutig lösbar ist, muss die Matrix vollen [[Rang (Lineare Algebra)|Rang]] besitzen. Eine notwendige Voraussetzung dafür ist, dass die Anzahl der Zeilen in der Matrix <math>B^T</math> nicht größer ist als die Anzahl der Spalten. Eine [[Notwendige und hinreichende Bedingung|hinreichende Bedingung]] gibt die sog. [[LBB-Bedingung]] (nach [[Olga Alexandrowna Ladyschenskaja|Ladyschenskaja]], [[Ivo Babuška|Babuška]] und [[Franco Brezzi|Brezzi]]), oft auch ''inf-sup-Bedingung'' genannt.

Effiziente numerische Algorithmen zur Lösung von Gleichungssystemen mit Sattelpunktstruktur verwenden eine spezielle Form des [[Schur-Komplement|Schur-Komplements]], welche die Blockstruktur der Matrix ausnutzt. Insbesondere bei der numerischen Lösung der Navier-Stokes-Gleichungen ist diese Variante sehr beliebt.

Gewöhnliche [[Iteratives Verfahren|iterative Lösungsverfahren]] wie das [[Krylov-Unterraum-Verfahren]] [[GMRES-Verfahren|GMRES]] ohne Beachtung der Struktur von <math>M</math> eignen sich dagegen relativ schlecht, da die gängigen Methoden zur [[Vorkonditionierung]] wie das [[Jacobi-Verfahren|Jacobi]]-, [[Gauß-Seidel-Verfahren|Gauß-Seidel]]-Verfahren oder die [[ILU-Zerlegung]] wegen der Nullen auf der [[Hauptdiagonale]]n im unteren Diagonalblock nicht funktionieren. Ohne Vorkonditionierung [[Grenzwert (Folge)|konvergieren]] selbst die oft hervorragenden Krylov-Unterraum-Verfahren nur sehr langsam und sind unbrauchbar.

== Begriffsklärung ==
Die Bezeichnung ''Sattelpunktproblem'' für eine Gleichung der Form
: <math> Mx = \begin{pmatrix}A & B \\ B^T & 0\end{pmatrix} \begin{pmatrix}u \\ p\end{pmatrix}  = \begin{pmatrix}0 \\ 0\end{pmatrix}= b </math>
leitet sich aus den Eigenschaften der zugehörigen [[Quadratische Form|quadratischen Form]]
: <math> F(u,p) = u^T A u + u^T B p + p^T B^T u </math>
mit einer [[Symmetrische Matrix|symmetrisch]] [[Definitheit|positiv definiten]] Matrix <math>A</math> ab, wobei die Herleitung hier für eine homogene rechte Seite erfolgt. Der allgemeine Fall mit <math>b\neq 0</math> hat analoge Eigenschaften.

Sei <math>x^* = (u^*,p^*)</math> eine Lösung des linearen Gleichungssystems <math>Mx=0</math>. Dann ist <math>(u^*,p^*)</math> ein [[Sattelpunkt]] von <math>F</math>, denn für alle <math>u\in \mathbb{R}^n</math>:
: <math> F(u,p^*) = u^T A u + 2 u^T B p^* = u^T A u - 2 u^T A u^* + (u^*)^T A u^*, </math>
wobei die zweite Gleichheit durch Ersetzen von <math> Bp^* = - A u^*</math> und Einfügen des Terms <math>(u^*)^T A u^* = 0</math> erreicht ist. Nun
: <math> F(u,p^*) = (u-u^*)^T A (u-u^*) \geq 0 = F(u^*,p^*), </math>
Der Term <math>(u-u^*)^T A (u-u^*)</math> ist nichtnegativ für alle <math>u</math>, da die Matrix <math>A</math> symmetrisch positiv definit ist.

Zudem zeigt man die Ungleichheit
: <math> F(u^*,p) \leq 0</math>
für alle <math>p\in \mathbb{R}^m</math>, was die Existenz des Sattelpunktes zeigt.

== Siehe auch ==
* [[Schur-Komplement]]
* [[Oseen-Gleichungen]]
* [[Darcy-Gesetz]]

== Literatur ==
* Dietrich Braess: ''Finite Elemente. Theorie, schnelle Löser und Anwendungen in der Elastizitätstheorie.'' Abschnitt III.4, Springer-Verlag, Berlin 2003, ISBN 3-540-00122-0.

[[Kategorie:Numerische Mathematik]]
[[Kategorie:Variationsrechnung]]