Sattelpunktproblem

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

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

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

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 ${\displaystyle A}$ entsteht dort aus der Diskretisierung des Geschwindigkeitsterms ${\displaystyle {\vec {u}}}$ in der Impulsgleichung, die Matrix ${\displaystyle B}$ aus der Diskretisierung des Druckterms ${\displaystyle p}$, und die Matrix ${\displaystyle B^{T}}$ resultiert aus der Diskretisierung der Geschwindigkeit in der Kontinuitätsgleichung.

Anwendungen wie die diskretisierten Navier-Stokes-Gleichungen erfordern die Lösung eines linearen Gleichungssystems

${\displaystyle 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 ${\displaystyle 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 ${\displaystyle 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.

Die Bezeichnung Sattelpunktproblem für eine Gleichung der Form

${\displaystyle 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

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

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

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

${\displaystyle 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 ${\displaystyle Bp^{*}=-Au^{*}}$ und Einfügen des Terms ${\displaystyle (u^{*})^{T}Au^{*}=0}$ erreicht ist. Nun

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

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

Zudem zeigt man die Ungleichheit

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

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

• Schur-Komplement
• Oseen-Gleichungen
• Darcy-Gesetz

• 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.