Sylvester-Gleichung

Die Sylvester-Gleichung i​st in d​er Mathematik u​nd der Kontrolltheorie e​ine Matrix-Gleichung d​er Form

${\displaystyle AX+XB=C,}$

dabei sind ${\displaystyle A,B,C}$ drei vorgegebene ${\displaystyle n\times n}$-Matrizen. Die ${\displaystyle n\times n}$-Matrix ${\displaystyle X}$ ist die gesuchte Lösung der Gleichung.

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

Sie i​st nach James Joseph Sylvester benannt, d​er darüber 1884 veröffentlichte.

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

Existenz und Eindeutigkeit der Lösung

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

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

${\displaystyle (I_{n}\otimes A+B^{T}\otimes I_{m})\operatorname {vec} X=\operatorname {vec} C,}$

Dabei bezeichnet ${\displaystyle I_{k}}$ die ${\displaystyle k\times k}$ Einheitsmatrix.

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

Es existiert eine eindeutige Lösung für alle ${\displaystyle C}$ genau dann, wenn ${\displaystyle A}$ und ${\displaystyle -B}$ keine gemeinsamen Eigenwerte haben.

Numerische Auflösung

Klassisch wird die Lösung stabil und robust mit dem Bartels-Stewart-Algorithmus berechnet. Dabei werden ${\displaystyle A}$ und ${\displaystyle 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.

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

${\displaystyle AX+XB=P^{-1}RPX+XQ^{-1}SQ=C}$

${\displaystyle RPXQ^{-1}+PXQ^{-1}S=PCQ^{-1}}$

${\displaystyle RY+YS=D}$

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

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

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

Auch m​it den iterativen Solvern für lineare Systeme k​ann die Lösung berechnet werden.

Referenzen

• J. Sylvester: Sur l’equations en matrices ${\displaystyle px=xq}$. In: C. R. Acad. Sc. Paris. Band 99, 1884, S. 67–71, 115–116.
• R. H. Bartels, G. W. Stewart: Solution of the matrix equation ${\displaystyle AX+XB=C}$. In: Communications of the ACM. Band 15, Nr. 9, 1972, S. 820–826, doi:10.1145/361573.361582.
• R. Bhatia, P. Rosenthal: How and Why to Solve the Operator Equation ${\displaystyle AX-XB=Y}$. In: Bulletin of the London Mathematical Society. Band 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. Band 435, Nr. 9, November 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 (hindawi.com).

Weblinks

• Online solver for arbitrary sized matrices.
• Mathematica function to solve the Sylvester equation