Sylvester-Gleichung

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

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

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

Allgemeiner kann ${\displaystyle C}${\displaystyle C} sogar eine ${\displaystyle m\times n}${\displaystyle m\times n}-Matrix sein; dann ist ${\displaystyle A}${\displaystyle A} eine ${\displaystyle m\times m}${\displaystyle m\times m}-Matrix, ${\displaystyle B}${\displaystyle B} eine ${\displaystyle n\times n}${\displaystyle n\times n}-Matrix und ${\displaystyle X}${\displaystyle X} wie ${\displaystyle C}${\displaystyle C} eine ${\displaystyle m\times n}${\displaystyle 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 ${\displaystyle B=A^{*}}${\displaystyle B=A^{*}} die zu ${\displaystyle A}${\displaystyle A} adjungierte Matrix ist, wird auch Ljapunow-Gleichung genannt (nach Alexander Michailowitsch Ljapunow).

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}}${\displaystyle n^{2}} unbekannten, in vektorisierter Form geschriebenen Matrixelementen ${\displaystyle X_{ij}}${\displaystyle X_{ij}} ein lineares Gleichungssystem bildet.

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

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

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

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

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

Klassisch wird die Lösung stabil und robust mit dem Bartels-Stewart-Algorithmus berechnet. Dabei werden ${\displaystyle A}${\displaystyle A} und ${\displaystyle B}${\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 A=P^{-1}RP}; ${\displaystyle B=Q^{-1}SQ}${\displaystyle B=Q^{-1}SQ}; ${\displaystyle R}${\displaystyle R} und ${\displaystyle S}${\displaystyle S} sind geeignete Dreiecksmatrizen (Im reellen dürfen sie isolierte Subdiagonalelemente enthalten).

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

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

${\displaystyle RY+YS=D}${\displaystyle RY+YS=D}

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

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

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

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

• J. Sylvester: Sur l’equations en matrices ${\displaystyle px=xq}${\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}${\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}${\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月03日4 . 
• Jituan Zhou Ruirui Wang and Qiang Niu: A Preconditioned Iteration Method for Solving Sylvester Equations. 2012 (hindawi.com). 

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

• Lineare Algebra
• Regelungstheorie