Sylvester-Gleichung

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

$AX+XB=C,$

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

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

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_{m})\operatorname {vec} X=\operatorname {vec} C,$

Dabei bezeichnet $I_{k}$ die $k\times k$ 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.

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

Numerische Auflösung

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).

$AX+XB=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

• J. Sylvester: Sur l’equations en matrices $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 $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 $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