Sattelpunktproblem

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.

Inhaltsverzeichnis

Ursprung von Sattelpunktproblemen

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

Eine 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 BT 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 BT kleiner 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 Diagonalen 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) = uTAu + uTBp + pTBTu

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 * ) = uTAu + 2uTBp * = uTAu − 2uTAu * + (u * )TAu * ,

wobei die zweite Gleichheit durch Ersetzen von Bp * = − Au * und Einfügen des Terms (u * )TAu * = 0 erreicht ist. Nun

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

Der Term (uu * )TA(uu * ) 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

  • Dieter Braess: Finite Elemente. Theorie, schnelle Löser und Anwendungen in der Elastizitätstheorie, Abschnitt III.4, Springer-Verlag, Berlin, 2003, ISBN 9-783540-001225

Wikimedia Foundation.

Игры ⚽ Поможем написать реферат

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Sattelstelle — Rot = Markierung des Sattelpunkts In der Mathematik bezeichnet man mit Sattelpunkt oder Terrassenpunkt einen kritischen Punkt einer Funktion, genauer eines Skalarfeldes, der kein Extremwert ist. Dieser Punkt ist ein Spezialfall des Wendepunktes …   Deutsch Wikipedia

  • Schur-Komplement — In der linearen Algebra bezeichnet das Schur Komplement eine Matrix, die sich aus den einzelnen Blöcken einer größeren Matrix berechnet. Das Schur Komplement ist nach Issai Schur benannt. Inhaltsverzeichnis 1 Definition 2 Interpretation als… …   Deutsch Wikipedia

  • Terrassenpunkt — Rot = Markierung des Sattelpunkts In der Mathematik bezeichnet man mit Sattelpunkt oder Terrassenpunkt einen kritischen Punkt einer Funktion, genauer eines Skalarfeldes, der kein Extremwert ist. Dieser Punkt ist ein Spezialfall des Wendepunktes …   Deutsch Wikipedia

  • Babuska — Ivo M. Babuška (* 22. März 1926 in Prag) ist ein tschechisch amerikanischer Mathematiker, bekannt vor allem durch seine Beiträge zur Finite Elemente Methode und den Beweis des Babuška Lax Milgram Theorems, eine Verallgemeinerung des Lemmas von… …   Deutsch Wikipedia

  • Babuška — Ivo M. Babuška (* 22. März 1926 in Prag) ist ein tschechisch amerikanischer Mathematiker, bekannt vor allem durch seine Beiträge zur Finite Elemente Methode und den Beweis des Babuška Lax Milgram Theorems, eine Verallgemeinerung des Lemmas von… …   Deutsch Wikipedia

  • Brezzi — Franco Brezzi (* 29. April 1945 in Vimercate) ist einer der bedeutendsten zeitgenössischen italienischen Mathematiker, bekannt durch seine Beiträge zur numerischen Mathematik. Er arbeitete in Grundlagen und Anwendungen der Finite Elemente Methode …   Deutsch Wikipedia

  • Gleichungen von Navier-Stokes — Die Navier Stokes Gleichungen [navˈjeː stəʊks] (nach Claude Louis Marie Henri Navier und George Gabriel Stokes) sind die Grundgleichungen der Strömungsmechanik. Sie beschreiben die Strömung in newtonschen Flüssigkeiten und Gasen. Die Navier… …   Deutsch Wikipedia

  • Ivo Babuska — Ivo M. Babuška (* 22. März 1926 in Prag) ist ein tschechisch amerikanischer Mathematiker, bekannt vor allem durch seine Beiträge zur Finite Elemente Methode und den Beweis des Babuška Lax Milgram Theorems, eine Verallgemeinerung des Lemmas von… …   Deutsch Wikipedia

  • Ladyschenskaja — Olga Alexandrowna Ladyschenskaja (russisch Ольга Александровна Ладыженская; * 7. März 1922 in Kologriw, Russland; † 12. Januar 2004 in Sankt Petersburg) war eine russische Mathematikerin und Physikerin, die besonders für ihre Resultate zu… …   Deutsch Wikipedia

  • Navier-Stokes-Gleichung — Die Navier Stokes Gleichungen [navˈjeː stəʊks] (nach Claude Louis Marie Henri Navier und George Gabriel Stokes) sind die Grundgleichungen der Strömungsmechanik. Sie beschreiben die Strömung in newtonschen Flüssigkeiten und Gasen. Die Navier… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”