Sylvestrova rovnice - Sylvester equation

v matematika, v oblasti teorie řízení, a Sylvestrova rovnice je matice rovnice formuláře:^[1]

{displaystyle AX + XB = C.}

Poté dány matice A, B, a C, problém je najít možné matice X kteří se řídí touto rovnicí. Předpokládá se, že všechny matice mají koeficienty v komplexní čísla. Aby měla rovnice smysl, musí mít matice vhodné velikosti, například by mohly být všechny čtvercovými maticemi stejné velikosti. Ale obecněji, A a B musí být čtvercové matice velikostí n a m respektive a poté X a C oba mají n řádky a m sloupce.

Sylvestrova rovnice má jedinečné řešení pro X přesně, když neexistují žádná společná vlastní čísla A a -BObecněji rovnice SEKERA + XB = C byla považována za rovnici omezené operátory na (možná nekonečně-dimenzionální) Banachův prostor. V tomto případě podmínka jedinečnosti řešení X je téměř stejný: Existuje jedinečné řešení X přesně kdy spektra z A a -B jsou disjunktní.^[2]

Existence a jedinečnost řešení

Za použití Produkt Kronecker notace a operátor vektorizace ${displaystyle operatorname {vec}}$ , můžeme přepsat Sylvestrovu rovnici ve formě

{displaystyle (I_ {m} další A + B ^ {T} další I_ {n}) operatorname {vec} X = operatorname {vec} C,}

kde ${displaystyle A}$ má rozměr ${displaystyle n! imes! n}$ , ${displaystyle B}$ má rozměr ${displaystyle m! imes! m}$ , ${displaystyle X}$ dimenze ${displaystyle n! imes! m}$ a ${displaystyle I_ {k}}$ je ${displaystyle k imes k}$ matice identity. V této formě lze rovnici vnímat jako a lineární systém dimenze ${displaystyle mn imes mn}$ .^[3]

Teorém. Vzhledem k tomu, matice ${displaystyle Ain mathbb {C} ^ {n imes n}}$ a ${displaystyle Bin mathbb {C} ^ {m imes m}}$ , Sylvestrova rovnice ${displaystyle AX + XB = C}$ má jedinečné řešení ${displaystyle Xin mathbb {C} ^ {n imes m}}$ pro všechny ${displaystyle Cin mathbb {C} ^ {n imes m}}$ kdyby a jen kdyby ${displaystyle A}$ a ${displaystyle -B}$ nesdílejte žádné vlastní číslo.

Důkaz. Rovnice ${displaystyle AX + XB = C}$ je lineární systém s ${displaystyle mn}$ neznámé a stejné množství rovnic. Proto je jedinečně řešitelný pro jakýkoli daný ${displaystyle C}$ právě tehdy, pokud jde o homogenní rovnici ${displaystyle AX + XB = 0}$ připouští pouze triviální řešení ${displaystyle 0}$ .

(i) Předpokládejme, že ${displaystyle A}$ a ${displaystyle -B}$ nesdílejte žádné vlastní číslo. Nechat ${displaystyle X}$ být řešením výše uvedené homogenní rovnice. Pak ${displaystyle AX = X (-B)}$ , které lze zvednout na ${displaystyle A ^ {k} X = X (-B) ^ {k}}$ pro každého ${displaystyle kgeq 0}$ matematickou indukcí. Tudíž, ${displaystyle p (A) X = Xp (-B)}$ pro libovolný polynom ${displaystyle p}$ . Zejména nechte ${displaystyle p}$ být charakteristický polynom z ${displaystyle A}$ . Pak ${displaystyle p (A) = 0}$ v důsledku Cayley-Hamiltonova věta; mezitím věta o spektrálním mapování říká nám ${displaystyle sigma (p (-B)) = p (sigma (-B)),}$ kde ${displaystyle sigma (cdot)}$ označuje spektrum matice. Od té doby ${displaystyle A}$ a ${displaystyle -B}$ nesdílejte žádné vlastní číslo, ${displaystyle p (sigma (-B))}$ neobsahuje nulu, a tedy ${displaystyle p (-B)}$ je nesmyslná. Tím pádem ${displaystyle X = 0}$ podle přání. To dokazuje část „pokud“ věty.

ii) Nyní předpokládejme, že ${displaystyle A}$ a ${displaystyle -B}$ sdílet vlastní číslo ${displaystyle lambda}$ . Nechat ${displaystyle u}$ být odpovídajícím pravým vlastním vektorem pro ${displaystyle A}$ , ${displaystyle v}$ být odpovídající levý vlastní vektor pro ${displaystyle -B}$ , a ${displaystyle X = u {v} ^ {*}}$ . Pak ${displaystyle Xeq 0}$ , a ${displaystyle AX + XB = A (uv ^ {*}) - (uv ^ {*}) (- B) = lambda uv ^ {*} - lambda uv ^ {*} = 0.}$ Proto ${displaystyle X}$ je netriviální řešení výše uvedené homogenní rovnice, které odůvodňuje část věty „pouze pokud“. Q.E.D.

Jako alternativa k věta o spektrálním mapování, nesigularita ${displaystyle p (-B)}$ v části i) dokladu lze prokázat také Bézoutova identita pro coprime polynomy. Nechat ${displaystyle q}$ být charakteristickým polynomem ${displaystyle -B}$ . Od té doby ${displaystyle A}$ a ${displaystyle -B}$ nesdílejte žádné vlastní číslo, ${displaystyle p}$ a ${displaystyle q}$ jsou coprime. Proto existují polynomy ${displaystyle f}$ a ${displaystyle g}$ takhle ${displaystyle p (z) f (z) + q (z) g (z) ekviv. 1}$ . Podle Cayley-Hamiltonova věta, ${displaystyle q (-B) = 0}$ . Tím pádem ${displaystyle p (-B) f (-B) = I}$ z čehož vyplývá, že ${displaystyle p (-B)}$ je nesigular.

Věta zůstává pravdivá, pokud ${displaystyle mathbb {C}}$ je nahrazen ${displaystyle mathbb {R}}$ všude. Důkaz pro část „pokud“ je stále použitelný; u části „pouze pokud“ si všimněte, že obojí ${displaystyle mathrm {Re} (uv ^ {*})}$ a ${displaystyle mathrm {Im} (uv ^ {*})}$ uspokojit homogenní rovnici ${displaystyle AX + XB = 0}$ a nemohou být současně nulové.

Rothovo pravidlo odstranění

Vzhledem ke dvěma čtvercovým komplexním maticím A a B, o velikosti n a ma matici C velikosti n podle m, pak se můžeme zeptat, kdy jsou následující dvě čtvercové matice velikosti n + m jsou podobný navzájem: ${displaystyle {egin {bmatrix} A&C 0 & Bend {bmatrix}}}$ a ${displaystyle {egin {bmatrix} A & 0 0 & Bend {bmatrix}}}$ . Odpověď je, že tyto dvě matice jsou si podobné přesně tehdy, když existuje matice X takhle SEKERA − XB = C. Jinými slovy, X je řešením Sylvestrovy rovnice. Toto je známé jako Rothovo pravidlo odstranění.^[4]

Jeden snadno zkontroluje jeden směr: Pokud SEKERA − XB = C pak

{displaystyle {egin {bmatrix} I_ {n} & X 0 & I_ {m} end {bmatrix}} {egin {bmatrix} A&C 0 & Bend {bmatrix}} {egin {bmatrix} I_ {n} & - X 0 & I_ {m } end {bmatrix}} = {egin {bmatrix} A & 0 0 & Bend {bmatrix}}.}

Rothovo pravidlo odstraňování nezobecňuje na nekonečně rozměrné ohraničené operátory v Banachově prostoru.^[5]

Numerická řešení

Klasickým algoritmem pro numerické řešení Sylvestrovy rovnice je Algoritmus Bartels – Stewart, která spočívá v transformaci ${displaystyle A}$ a ${displaystyle B}$ do Schurova forma podle a Algoritmus QR, a poté výsledný trojúhelníkový systém vyřešit pomocí zpětná substituce. Tento algoritmus, jehož výpočetní náklady jsou ${displaystyle {mathcal {O}} (n ^ {3})}$ aritmetické operace,^{[Citace je zapotřebí ]} používá mimo jiné LAPACK a lyap funkce v GNU oktáva.^[6] Viz také sylvester funkce v tomto jazyce.^[7]^[8] V některých konkrétních aplikacích pro zpracování obrazu má odvozená Sylvesterova rovnice uzavřené řešení.^[9]

Viz také

Poznámky

^ Tato rovnice je také běžně psána v ekvivalentní formě SEKERA − XB = C.
^ Bhatia a Rosenthal, 1997
^ Přepis rovnice v této podobě se však pro numerické řešení nedoporučuje, protože řešení této verze je nákladné a může být špatně podmíněný.
^ Gerrish, F; Ward, A.G.B (listopad 1998). „Sylvestrova maticová rovnice a Rothovo pravidlo odstranění“. Matematický věstník. 82 (495): 423–430. doi:10.2307/3619888. JSTOR 3619888.
^ Bhatia a Rosenthal, s. 3
^ "Odkaz na funkci: Lyap".
^ "Funkce matice (GNU Octave (verze 4.4.1))" ".
^ The syl příkaz je zastaralý od GNU Octave verze 4.0
^ Wei, Q .; Dobigeon, N .; Tourneret, J.-Y. (2015). „Rychlá fúze vícepásmových obrazů na základě řešení Sylvestrovy rovnice“. IEEE. 24 (11): 4109–4121. arXiv:1502.03121. Bibcode:2015ITIP ... 24,4109W. doi:10.1109 / TIP.2015.2458572. PMID 26208345.

Reference

Sylvester, J. (1884). „Sur l'equations en matrices ${displaystyle px = xq}$ ". C. R. Acad. Sci. Paříž. 99 (2): 67–71, 115–116.
Bartels, R. H .; Stewart, G. W. (1972). "Řešení maticové rovnice ${displaystyle AX + XB = C}$ ". Comm. ACM. 15 (9): 820–826. doi:10.1145/361573.361582.
Bhatia, R .; Rosenthal, P. (1997). "Jak a proč vyřešit operátorskou rovnici ${displaystyle AX-XB = Y}$ ?". Býk. London Math. Soc. 29 (1): 1–21. doi:10.1112 / S0024609396001828.
Lee, S.-G .; Vu, Q.-P. (2011). „Simultánní řešení Sylvestrových rovnic a idempotentních matic oddělujících společné spektrum“. Aplikace lineární algebry 435 (9): 2097–2109. doi:10.1016 / j.laa.2010.09.034.
Wei, Q .; Dobigeon, N .; Tourneret, J.-Y. (2015). „Rychlá fúze vícepásmových obrazů na základě řešení Sylvestrovy rovnice“. Transakce IEEE na zpracování obrazu. 24 (11): 4109–4121. arXiv:1502.03121. Bibcode:2015ITIP ... 24,4109W. doi:10.1109 / TIP.2015.2458572. PMID 26208345.
Birkhoff a MacLane. Průzkum moderní algebry. Macmillana. 213, 299.

externí odkazy

[1] Tato rovnice je také běžně psána v ekvivalentní formě SEKERA − XB = C.

[2] Bhatia a Rosenthal, 1997

[3] Přepis rovnice v této podobě se však pro numerické řešení nedoporučuje, protože řešení této verze je nákladné a může být špatně podmíněný.

[4] Gerrish, F; Ward, A.G.B (listopad 1998). „Sylvestrova maticová rovnice a Rothovo pravidlo odstranění“. Matematický věstník. 82 (495): 423–430. doi:10.2307/3619888. JSTOR 3619888.

[5] Bhatia a Rosenthal, s. 3

[6] "Odkaz na funkci: Lyap".

[7] "Funkce matice (GNU Octave (verze 4.4.1))" ".

[8] The syl příkaz je zastaralý od GNU Octave verze 4.0

[9] Wei, Q .; Dobigeon, N .; Tourneret, J.-Y. (2015). „Rychlá fúze vícepásmových obrazů na základě řešení Sylvestrovy rovnice“. IEEE. 24 (11): 4109–4121. arXiv:1502.03121. Bibcode:2015ITIP ... 24,4109W. doi:10.1109 / TIP.2015.2458572. PMID 26208345.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]