Sattelpunktproblem

Kernidee und Matrixform

Ein Sattelpunktproblem ist in der Mathematik eine spezielle Klasse von Problemen, die auf ein lineares Gleichungssystem in Blockgestalt führen. Die zugehörige Matrix M hat die Form

M = ( A B ; B^T 0 ).

Dabei ist A eine n × n-Matrix, B eine n × m-Matrix, B^T die transponierte Matrix von B und der 0-Block eine m × m-Matrix. Insgesamt ist M also eine (n + m) × (n + m)-Matrix. Solche Matrizen sind wichtig, weil sie in vielen Anwendungen auftreten, in denen verschiedene Größen gekoppelt sind, zum Beispiel eine Hauptvariable und eine Nebenbedingung.

Entstehung in Anwendungen

Sattelpunktprobleme entstehen häufig bei Optimierungsproblemen unter Nebenbedingungen. Ein wichtiges Beispiel ist das Lösen von quadratischen Programmen mit Gleichungsrestriktionen mithilfe der Karush-Kuhn-Tucker-Bedingungen. Diese Bedingungen sind äquivalent zur Bestimmung eines Sattelpunktes bei der Lagrange-Dualität. Daher stammt auch die Bezeichnung Sattelpunktproblem.

Eine weitere wichtige Quelle sind Diskretisierungen von partiellen Differentialgleichungen, also Verfahren, bei denen kontinuierliche Gleichungen näherungsweise in endlich viele Rechenschritte oder Gleichungen übersetzt werden. Besonders wichtig sind die inkompressiblen Navier-Stokes-Gleichungen in linearisierter Form, zum Beispiel nach Diskretisierung mit finiten Elementen. Dabei entsteht auf natürliche Weise ein lineares Gleichungssystem mit genau der oben beschriebenen Blockstruktur.

Bei den Navier-Stokes-Gleichungen kommt die Blockmatrix A aus der Diskretisierung des Geschwindigkeitsterms u in der Impulsgleichung. Die Matrix B entsteht aus der Diskretisierung des Druckterms p. Die Matrix B^T resultiert aus der Diskretisierung der Geschwindigkeit in der Kontinuitätsgleichung.

Lösbarkeit und Bedingungen

In Anwendungen wie den diskretisierten Navier-Stokes-Gleichungen muss man ein lineares Gleichungssystem der Form

Mx = b

lösen. Damit dieses Gleichungssystem eindeutig lösbar ist, muss die Matrix M 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 für die Lösbarkeit ist die sogenannte LBB-Bedingung, benannt nach Ladyschenskaja, Babuška und Brezzi. Sie wird häufig auch inf-sup-Bedingung genannt. Der Artikel nennt diese Bedingung als wichtiges Kriterium, ohne sie weiter auszuschreiben.

Numerische Lösung

Für Gleichungssysteme mit Sattelpunktstruktur verwendet man effiziente numerische Algorithmen, die die besondere Blockstruktur der Matrix ausnutzen. Besonders wichtig ist dabei eine spezielle Form des Schur-Komplements. Ein Schur-Komplement ist ein Verfahren beziehungsweise Ausdruck aus der Blockmatrixrechnung, mit dem Teile eines Gleichungssystems gezielt eliminiert oder zusammengefasst werden können. Diese Methode ist besonders bei der numerischen Lösung der Navier-Stokes-Gleichungen beliebt.

Gewöhnliche iterative Lösungsverfahren sind dagegen oft ungeeignet, wenn sie die Struktur von M nicht berücksichtigen. Dazu gehört zum Beispiel das Krylov-Unterraum-Verfahren GMRES. Ohne passende Vorkonditionierung konvergieren selbst solche leistungsfähigen Verfahren nur sehr langsam und werden dadurch unbrauchbar.

Ein Grund dafür ist, dass gängige Vorkonditionierungsverfahren wie das Jacobi-Verfahren, das Gauß-Seidel-Verfahren oder die ILU-Zerlegung wegen der Nullen auf der Hauptdiagonalen im unteren Diagonalblock nicht funktionieren.

Warum es Sattelpunkt heißt

Die Bezeichnung lässt sich über eine zugehörige quadratische Form erklären. Für eine Gleichung der Form

Mx = ( A B ; B^T 0 )( u ; p ) = ( 0 ; 0 ) = b

betrachtet man die Funktion

F(u,p) = u^T A u + u^T B p + p^T B^T u,

wobei A symmetrisch positiv definit ist. Symmetrisch bedeutet, dass A gleich ihrer Transponierten ist. Positiv definit bedeutet hier, dass quadratische Ausdrücke der Form v^T A v für v ≠ 0 positiv sind und daher insbesondere nichtnegativ auftreten.

Die Herleitung im Artikel wird für eine homogene rechte Seite durchgeführt, also für b = 0. Der allgemeine Fall b ≠ 0 besitzt analoge Eigenschaften.

Ist x* = (u*, p*) eine Lösung des linearen Gleichungssystems Mx = 0, dann ist (u*, p*) ein Sattelpunkt von F. Für alle u ∈ R^n gilt

F(u,p*) = (u − u*)^T A (u − u*) ≥ 0 = F(u*,p*).

Der Ausdruck ist nichtnegativ, weil A symmetrisch positiv definit ist. Zusätzlich zeigt man für alle p ∈ R^m die Ungleichung

F(u*,p) ≤ 0.

Zusammen bedeutet das: In der u-Richtung liegt ein Minimum vor, während in der p-Richtung eine entgegengesetzte Ungleichung gilt. Diese gemischte Situation erklärt den Namen Sattelpunkt.