Sattelpunktproblem

In der Mathematik bezeichnet ein Sattelpunktproblem eine spezielle Problemklasse, welche auf ein lineares Gleichungssystem in Blockgestalt führt, und zwar eine $(n+m)\times (n+m)$ -Matrix $M$ der Form

M={\begin{pmatrix}A&B\\B^{T}&0\end{pmatrix}},

wobei $A$ eine $n\times n$ -Matrix ist und $B$ eine $n\times m$ -Matrix. Der $0$ -Block ist von der Größe $m\times m$ .

Ursprung von Sattelpunktproblemen

Gleichungssysteme in Sattelpunktform entstehen in vielen Anwendungen, beispielsweise bei Optimierungsproblemen unter Nebenbedingungen.

Beispiel hierfür ist das Lösen von 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 partiellen Differentialgleichungen. Das wichtigste Beispiel sind die inkompressiblen Navier-Stokes-Gleichungen in linearisierter Form, diskretisiert beispielsweise mit finiten Elementen, welches auf natürliche Weise ein lineares Gleichungssystem in obiger Blockgestalt ergibt. Die Blockmatrix $A$ entsteht dort aus der Diskretisierung des Geschwindigkeitsterms ${\vec {u}}$ in der Impulsgleichung, die Matrix $B$ aus der Diskretisierung des Druckterms $p$ , und die Matrix $B^{T}$ 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

Mx=b.

Damit das Gleichungssystem eindeutig lösbar ist, muss die Matrix vollen Rang besitzen. Eine notwendige Voraussetzung dafür ist, dass die Anzahl der Zeilen in der Matrix $B^{T}$ nicht größer ist als die Anzahl der Spalten. Eine hinreichende Bedingung gibt die sog. LBB-Bedingung (nach Ladyschenskaja, Babuška und Brezzi), oft auch inf-sup-Bedingung genannt.

Effiziente numerische Algorithmen zur Lösung von Gleichungssystemen mit Sattelpunktstruktur verwenden eine spezielle Form des 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 iterative Lösungsverfahren wie das Krylov-Unterraum-Verfahren GMRES ohne Beachtung der Struktur von $M$ eignen sich dagegen relativ schlecht, da die gängigen Methoden zur Vorkonditionierung wie das Jacobi-, Gauß-Seidel-Verfahren oder die ILU-Zerlegung wegen der Nullen auf der Hauptdiagonalen im unteren Diagonalblock nicht funktionieren. Ohne Vorkonditionierung 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

Mx={\begin{pmatrix}A&B\\B^{T}&0\end{pmatrix}}{\begin{pmatrix}u\\p\end{pmatrix}}={\begin{pmatrix}0\\0\end{pmatrix}}=b

leitet sich aus den Eigenschaften der zugehörigen quadratischen Form

F(u,p)=u^{T}Au+u^{T}Bp+p^{T}B^{T}u

mit einer symmetrisch positiv definiten Matrix $A$ ab, wobei die Herleitung hier für eine homogene rechte Seite erfolgt. Der allgemeine Fall mit $b\neq 0$ hat analoge Eigenschaften.

Sei $x^{*}=(u^{*},p^{*})$ eine Lösung des linearen Gleichungssystems $Mx=0$ . Dann ist $(u^{*},p^{*})$ ein Sattelpunkt von $F$ , denn für alle $u\in \mathbb {R} ^{n}$ :

F(u,p^{*})=u^{T}Au+2u^{T}Bp^{*}=u^{T}Au-2u^{T}Au^{*}+(u^{*})^{T}Au^{*},

wobei die zweite Gleichheit durch Ersetzen von $Bp^{*}=-Au^{*}$ und Einfügen des Terms $(u^{*})^{T}Au^{*}=0$ erreicht ist. Nun

F(u,p^{*})=(u-u^{*})^{T}A(u-u^{*})\geq 0=F(u^{*},p^{*}),

Der Term $(u-u^{*})^{T}A(u-u^{*})$ ist nichtnegativ für alle $u$ , da die Matrix $A$ symmetrisch positiv definit ist.

Zudem zeigt man die Ungleichheit

F(u^{*},p)\leq 0

für alle $p\in \mathbb {R} ^{m}$ , was die Existenz des Sattelpunktes zeigt.

Siehe auch

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.