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