Sylvester-Gleichung

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Die Sylvester-Gleichung ist in der Mathematik und der Kontrolltheorie eine Matrix-Gleichung der Form

A X + X B = C,

Dabei sind A,B,X,C vier n \times n-Matrizen; A,B,C sind vorgegeben; X ist gesucht.

Allgemeiner kann C sogar eine m \times n-Matrix sein; dann ist A eine m \times m-Matrix, B eine n \times n-Matrix und X wie C eine m \times n-Matrix.

Sie ist nach James Joseph Sylvester benannt, der darüber 1884 veröffentlichte.

Der für Anwendungen wichtige Spezialfall, in dem B = A^* die zu A adjungierte Matrix ist, wird auch Ljapunow-Gleichung genannt (nach Alexander Michailowitsch Ljapunow).

Existenz und Eindeutigkeit der Lösung[Bearbeiten]

Wegen der Nichtkommutativität des Matrizenprodukts kann die Gleichung nicht direkt aufgelöst werden. Trotzdem ist sie einfach eine lineare Gleichung, die mit den n^2 unbekannten, in vektorisierter Form geschriebenen Matrixelementen X_{ij} ein lineares Gleichungssystem bildet.

In kompakter Form kann es mit dem Kroneckerprodukt und dem Vektorisierungsoperator \operatorname{vec} wie folgt geschrieben werden:

 (I_n \otimes A +  B^T \otimes I_n) \operatorname{vec}X = \operatorname{vec}C,

Dabei ist I_n die n \times n Einheitsmatrix.

Die direkte Lösung dieses Gleichungssystems ist aufwendig (n^4 Elemente in einer dünnbesetzten Matrix, n^2 Unbekannte und \mathcal{O}(n^6) FLOPs) und darüber hinaus numerisch instabil.

Die Lösung existiert genau dann und ist eindeutig, wenn A und -B keine gemeinsamen Eigenwerte haben.

Numerische Auflösung[Bearbeiten]

Klassisch wird die Lösung stabil und robust mit dem Bartels–Stewart-Algorithmus berechnet. Dabei werden A und B durch Ähnlichkeitstransformationen in die Schursche Normalform gebracht und dabei die Sylvestergleichung in eine einfachere und durch Rückwärtseinsetzen lösbare Dreiecksgestalt transformiert. Die Ähnlichkeitstransformationen erfolgen mit dem aus dem QR-Algorithmus abgeleiteten Francis-Algorithmus.

A = P^{-1}RP; B = Q^{-1}SQ; R und S sind geeignete Dreiecksmatrizen (Im reellen dürfen sie isolierte Subdiagonalelemente enthalten).

A X + X B = P^{-1}RPX + XQ^{-1}SQ = C
RPXQ^{-1} + PXQ^{-1}S = PCQ^{-1}
RY + YS = D

Dabei sind Y=PXQ^{-1} und D=PCQ^{-1}.

In der einfacheren Dreiecksgestalt kann Y jetzt direkt und X aus X = P^{-1}YQ bestimmt werden. Die Rechenzeit liegt in der Größenordnung der Schurschen Normalform (\mathcal{O}(n^3) FLOPs).

Neuere Algorithmen kommen mit einer Schur-Transformation (z.B. für B) aus und bilden mit der anderen Matrix (z.B. A) nur eine Hessenbergmatrix.

Auch mit den iterativen Solvern für lineare Systeme kann die Lösung berechnet werden.

Referenzen[Bearbeiten]

  •  J. Sylvester: Sur l’equations en matrices px = xq. In: C. R. Acad. Sc. Paris. 99, 1884, S. 67–71, 115–116.
  •  R. H. Bartels, G. W. Stewart: Solution of the matrix equation AX +XB = C. In: Communications of the ACM. 15, Nr. 9, 1972, S. 820–826, doi:10.1145/361573.361582.
  •  R. Bhatia, P. Rosenthal: How and Why to Solve the Operator Equation AX -XB = Y . In: Bulletin of the London Mathematical Society. 29, Nr. 1, 1997, S. 1–21, doi:10.1112/S0024609396001828.
  •  Sang-Gu Lee, Quoc-Phong Vu: Simultaneous solutions of Sylvester equations and idempotent matrices separating the joint spectrum. In: Linear Algebra and its Applications. 435, Nr. 9, 2011, S. 2097–2109, doi:10.1016/j.laa.2010.09.034.
  •  Jituan Zhou Ruirui Wang and Qiang Niu: A Preconditioned Iteration Method for Solving Sylvester Equations. 2012.http://www.hindawi.com/journals/jam/2012/401059/

Weblinks[Bearbeiten]