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 der Form

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

wobei eine $n\times n$ -Matrix ist und 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 entsteht dort aus der Diskretisierung des Geschwindigkeitsterms ${\vec {u}}$ in der Impulsgleichung, die Matrix aus der Diskretisierung des Druckterms , 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

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 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 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 , 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 , da die Matrix 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.

Basierend auf einem Artikel in:

Wikipedia.de