In der Mathematik bezeichnet ein Sattelpunktproblem eine spezielle Problemklasse, welche auf ein lineares Gleichungssystem in Blockgestalt führt, und zwar eine -Matrix der Form
wobei eine -Matrix ist und eine -Matrix. Der -Block ist von der Größe .
Ursprung von Sattelpunktproblemen Bearbeiten
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 in der Impulsgleichung, die Matrix aus der Diskretisierung des Druckterms , und die Matrix resultiert aus der Diskretisierung der Geschwindigkeit in der Kontinuitätsgleichung.
Lösung von Sattelpunktgleichungen Bearbeiten
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 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 Bearbeiten
Die Bezeichnung Sattelpunktproblem für eine Gleichung der Form
leitet sich aus den Eigenschaften der zugehörigen quadratischen Form
mit einer symmetrisch positiv definiten Matrix ab, wobei die Herleitung hier für eine homogene rechte Seite erfolgt. Der allgemeine Fall mit hat analoge Eigenschaften.
Sei eine Lösung des linearen Gleichungssystems . Dann ist ein Sattelpunkt von , denn für alle :
wobei die zweite Gleichheit durch Ersetzen von und Einfügen des Terms erreicht ist. Nun
Der Term ist nichtnegativ für alle , da die Matrix symmetrisch positiv definit ist.
Zudem zeigt man die Ungleichheit
für alle , was die Existenz des Sattelpunktes zeigt.
Siehe auch Bearbeiten
Literatur Bearbeiten
- 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.