Maticové rozklady. Kapitola LU rozklad a Choleského rozklad

Kapitola 4

Maticové rozklady S rozkladem matice jsme se v předchozím textu vlastně již setkali, i když jsme tento název ještě nepoužili. Připomeňme (viz definici 2.2.4), že matice A ∈ Cn×n je diagonalizovatelná, jestliže pro nějakou regulární matici X ∈ Cn×n je X−1 AX = D = diag[λ1 , λ2 , . . . , λn ] (víme, že λ1 , λ2 , . . . , λn jsou potom právě všechna vlastní čísla matice A). Tuto rovnost můžeme ale napsat ve tvaru (4.1)

A = XDX−1 ;

zde jsme matici A napsali jako součin regulární matice X, diagonální matice D a matice X−1 , tj. matici A jsme rozložili na takový součin. Obecně o rozkladu matice většinou mluvíme, když danou matici vyjádříme jako součin (nebo např. součet a pod.) nějakých jiných matic. Podle toho, jaké matice se v tomto součinu vyskytují, rozlišujeme různé typy rozkladů. Poznamenejme, že rozklad tvaru (4.1) se v literatuře často nazývá spektrální rozklad — v předchozím jsme název spektrální rozklad použili v případě unitární diagonalizace, tj. v případě, že matici X v (4.1) lze volit unitární. Různé typy rozkladů matice se dají použít různými způsoby. Tak třeba o jednom z užití rozkladu tvaru (4.1), tj. diagonalizace matice, jsme mluvili v poznámce 2.2.11 v souvislosti s nehomogenní soustavou lineárních diferenciálních rovnic, viz též příklad 2.2.16. Rozklad tvaru (4.1) je jednoznačně svázán s vlastními čísly matice. Tento text se věnuje především otázkám, které mají co do činění s vlastními čísly a vlastními vektory matice, přesto se zde alespoň stručně zmíníme o některých rozkladech, které souvisí s řešením soustav lineárních (algebraických) rovnic. Mezi nejznámější z nich patří zřejmě LU rozklad.

4.1

LU rozklad a Choleského rozklad

Je-li A ∈ Cn×n , pak LU rozkladem této matice rozumíme vyjádření A ve tvaru (4.2)

A = LU,

kde L, U ∈ Cn×n , L je dolní trojúhelníková, U je horní trojúhelníková matice. Bez důkazu uveďme následující tvrzení o existenci LU rozkladu čtvercové matice. Připomeňme (viz 128

4.1. LU ROZKLAD A CHOLESKÉHO ROZKLAD odstavec 3.4.11), že je-li A ∈ Cn×n , pak symbolem ∆i značíme hlavní minor A řádu i (i = 1, 2, . . . , n), tj. ∆i = det Ai , kde Ai = A(1:i, 1:i). 4.1.1 Věta. Buď A ∈ Cn×n . Potom A má LU rozklad, tj. A lze napsat ve tvaru A = LU, kde L je dolní trojúhelníková, U horní trojúhelníková matice, právě když ∆i 6= 0

pro každé i = 1, 2, . . . , n.

Potom lze matice L, U volit tak, že všechny diagonální prvky matice L jsou rovny 1. Touto podmínkou jsou matice L, U určeny jednoznačně a je-li A reálná, jsou matice L, U také reálné. 4.1.2. Jsou-li podmínky věty splněny, je spec. det A = ∆n 6= 0, tj. matice je regulární. Poznamenejme, že LU rozklad mohou mít i mnohé neregulární matice. Pro aplikace LU rozkladu je ale případ regulárních matic nejdůležitější. Buď tedy A ∈ Cn×n regulární matice a předpokládejme, že A má LU rozklad, A = LU. Uvažujme soustavu lineárních rovnic (4.3)

Ax = b,

kde b ∈ Cn je dané. Víme, že za předpokladu regularity A má soustava (4.3) právě jedno řešení (viz odstavec 1.4). Známe-li LU rozklad matice A, můžeme toto řešení relativně snadno nalézt pomocí následujících dvou kroků. Nejprve řešíme soustavu Ly = b, pro neznámé y a jakmile y známe, řešíme soustavu Ux = y pro neznámé x (rozmyslete si, že je-li A regulární, pak matice L, U jsou nutně také regulární). Takto nalezené x je (jediné) řešení původní soustavy (4.3) — je totiž Ax = LUx = Ly = b. Řešit soustavy Ly = b a Ux = y je přitom snadné, neboť matice L, U jsou trojůhelníkové — viz třeba odstavec 3.1 ze skript [2]. Podle věty 4.1.1 ani zdaleka ne každá regulární matice má LU rozklad, takže by se mohlo zdát, že obecně není možné použít LU rozklad na řešení soustavy lineárních rovnic se čtvercovou regulární maticí. Dá se ale ukázat, že pokud A ∈ Cn×n je regulární, pak lze přeházet pořadí řádků A tak, že všechny hlavní minory takto vzniklé matice jsou nenulové a podle věty 4.1.1 tato nová matice má LU rozklad. Připomeňme, že matice P ∈ Rn×n je tzv. permutační matice, jestliže vznikla z jednotkové matice (řádu n) přeházením pořadí řádků (event. sloupců; viz odstavec 3.3.5). Je-li P ∈ Rn×n permutační matice, která vznikla z E přeházením řádků v jistém pořadí, pak součin PA lze dostat přímo z A přeházením řádků ve stejném pořadí (rozmyslete si podrobně). Platí následující tvrzení. 129

KAPITOLA 4. MATICOVÉ ROZKLADY 4.1.3 Věta. Buď A ∈ Cn×n regulární matice. Potom existuje permutační matice P, dolní trojůhelníková matice L a horní trojúhelníková matice U tak, že PA = LU. Např. ve skriptech [2], odstavec 3.3, je popsán efektivní algoritmus k nalezení matic P, L a U (zároveň je tak dokázána věta 4.1.3). Mluví se o algoritmu LU rozkladu se sloupcovým výběrem hlavního prvku (který je vlastně totožný s algoritmem Gaussovy eliminace). Poznamenejme jenom, že je-li P permutační matice, pak ovšem rovnost Ax = b je ekvivalentní rovnosti PAx = Pb (násobení maticí P zde vlastně jenom znamená přehození pořadí rovnic v dané soustavě). Pokud tedy samotná matice A nemá LU rozklad, lze řešení soustavy Ax = b převést na řešení soustavy PAx = Pb, kde P lze volit tak, že matice PA již LU rozklad má. 4.1.4. Choleského rozklad je speciální případ LU rozkladu pro případ pozitivně definitních matic. Všimněme si nejprve následující skutečnosti. Buď B ∈ Cn×n regulární matice. Potom matice A = BB∗ (a také C = B∗ B) je pozitivně definitní. Především je vidět, že A je hermitovská, neboť
∗
∗ A∗ = BB∗ = B∗ B∗ = BB∗ = A.

Je-li x ∈ Cn , x 6= 0, pak

2
∗ x∗ Ax = x∗ BB∗ x = B∗ x (B∗ x) = B∗ x .

Jelikož B je regulární, je také B∗ regulární, tj. je B∗ x 6= 0 a tedy x∗ Ax > 0. Vidíme, že A je opravdu pozitivně definitní (podobně pro C). Ukažme nyní, že naopak každou pozitivně definitní matici A lze napsat ve tvaru A = = BB∗ , kde B je nějaká regulární matice. Stačí ale např. položit B = A1/2 ; o existenci odmocniny pozitivně definitní matice (obecněji pozitivně semidefinitní) jsme mluvili v odstavci 3.4.13. Přitom B = A1/2 je pozitivně definitní a spec. tedy hermitovská, takže skutečně BB∗ = BB = B2 = A. Vidíme, že platí: 130

4.2. QR ROZKLAD 4.1.5 Tvrzení. Buď A ∈ Cn×n . Potom A je pozitivně definitní právě když A lze napsat ve tvaru A = BB∗ , kde B je nějaká regulární matice. Jak jsme viděli, v rozkladu pozitivně definitní matice A ve tvaru A = BB∗ lze matici B volit dokonce hermitovskou. Matice B v tomto rozkladu ale ani zdaleka není určena jednoznačně a nemusí být hermitovská. Pozitivně definitní matice má navíc LU rozklad. Podle Sylvestrova kritéria (věta 3.4.12) jsou totiž všechny hlavní minory pozitivně definitní matice A kladné a tedy podle věty 4.1.1 opravdu A má LU rozklad. Dá se ukázat, že potom lze dokonce v rozkladu A = LU volit U = L∗ nebo, což je totéž, v rozkladu A = BB∗ lze volit matici B dolní trojúhelníkovou. Platí následující tvrzení. 4.1.6 Věta. Buď A ∈ Cn×n . Potom A je pozitivně definitní právě když A lze napsat ve tvaru A = LL∗ ,

(4.4)

kde L je nějaká dolní trojúhelníková matice, jejíž všechny diagonální prvky jsou reálné a kladné. Matice L je potom určena jednoznačně. Je-li A reálná, je L také reálná. Označíme-li R = L∗ , můžeme rozklad (4.4) z právě uvedené věty psát ve tvaru A = R∗ R, kde R je horní trojúhelníková matice, která má na diagonále všechny prvky kladné. Tomuto rozkladu se říká Choleského rozklad a matici R Choleského faktor matice A. Jak jsme již poznamenali, na Choleského rozklad se můžeme dívat jako na speciální případ LU rozkladu. Na řešení soustavy lineárních rovnic s pozitivně definitní maticí se dá Choleského rozklad použít přesně stejně jako LU rozklad v případě obecné regulární matice. Relativně jednoduchý algoritmus hledání Choleského rozkladu je popsán např. ve skriptech [2], odstavec 3.2. Větu 4.1.6 zde nebudeme dokazovat. Později si ale všimneme souvislosti s QR rozkladem (viz poznámku 4.2.4).

4.2

QR rozklad

V případě čtvercových matic se QR rozkladem myslí vyjádření dané matice jako součin unitární a horní trojúhelníkové matice. Věta o QR rozkladu se dá ale formulovat obecněji i pro matice, které nejsou čtvercové. Platí následující tvrzení. 4.2.1 Věta. Buď A ∈ Cm×n , kde m ≥ n. Potom existují matice Q ∈ Cm×n , R ∈ Cn×n tak, že sloupce matice Q jsou ortonormální, R je horní trojúhelníková, a (4.5)

A = QR.

Je-li A reálná, lze matice Q, R volit reálné. Je-li hod A = n, pak lze matici R volit tak, že všechny její diagonální prvky jsou reálné a kladné — touto podmínkou jsou pak matice Q, R určeny jednoznačně. 131

KAPITOLA 4. MATICOVÉ ROZKLADY 4.2.2 Poznámka. Je-li A ∈ Cm×n , m ≥ n, pak je vždy hod A ≤ n; hod A je maximální počet lineárně nezávislých sloupců A. Připomeňme, že je-li zde hod A = n, pak říkáme, že matice A má plnou hodnost (viz odstavec 1.2.9). V případě m = n ovšem matice plné hodnosti není nic jiného než regulární matice. Poznamenejme ještě, že v případě m = n, tj. v případě čtvercové matice A, matice Q je unitární. Důkaz věty 4.2.1 zde nebudeme uvádět. Poznamenejme jenom, že důkaz existence QR rozkladu spočívá v ortogonalizaci sloupců matice A pomocí Grammova-Schmidtova ortogonalizačního procesu (viz důkaz věty 1.5.5). V odstavci 4.3.12 skript [2] je na základě Grammovy-Schmidtovy ortogonalizace odvozen jeden z algoritmů pro hledání QR rozkladu — zároveň je tak dokázána existence QR rozkladu. Tento algoritmus je odvozen za předpokladu, že A má plnou hodnost, tj. sloupce A jsou lineárně nezávislé. 4.2.3 Poznámka. V případě regulární čtvercové matice se dá QR rozklad použít např. jako alternativní metoda řešení soustavy lineárních rovnic s touto maticí. Je-li A ∈ Cn×n regulární matice s QR rozkladem A = QR, pak rovnost Ax = b (kde b ∈ Cn je dané) je ekvivalentní rovnosti Rx = Q∗ b, neboť Q je unitární, tj. Q−1 = Q∗ . Stačí tedy řešit soustavu s trojúhelníkovou maticí R a pravou stranou Q∗ b. Poznamenejme, že objem výpočtů při hledání QR rozkladu je přibližně dvojnásobný oproti hledání LU rozkladu (viz [2]). QR rozklad se používá především k řešení úlohy o nejmenších čtvercích. Pro podrobnosti odkazujeme opět na skripta [2]. 4.2.4 Poznámka. Všimněme si ještě jak z existence QR rozkladu plyne existence Choleského rozkladu pozitivně definitní matice. Buď tedy A ∈ Cn×n (hermitovská) pozitivně definitní matice. Podle tvrzení 4.1.5 existuje regulární matice B ∈ Cn×n tak, že A = = BB∗ . Matice B∗ je také regulární a existují matice Q, R ∈ Cn×n tak, že B∗ = QR, Q je unitární, R horní trojúhelníková, která má na diagonále reálné kladné prvky. Potom ale (neboť Q∗ Q = E)
∗ A = BB∗ = B∗ B∗ = (QR)∗ QR = R∗ Q∗ QR∗ = R∗ R,

což už je Choleského rozklad matice A.

4.3

Schurův rozklad a normální matice

V předchozím jsme se již setkali s pojmem unitární podobnost matic (poznámka 1.5.19). Připomínáme, že matice A, B ∈ Cn×n jsou unitárně podobné, jestliže pro nějakou unitární matici U ∈ Cn×n je B = U∗ AU. Matice A je unitárně diagonizovatelná, je-li unitárně podobná nějaké diagonální matici. Připomeňme, že podle věty o spektrálním rozkladu pro hermitovské matice (věta 3.1.6) 132

4.3. SCHURŮV ROZKLAD A NORMÁLNÍ MATICE každá hermitovská matice je unitárně diagonizovatelná. Ne každá čtvercová matice je diagonizovatelná a tedy tím spíše ne každá matice je unitárně diagonizovatelná. Otázka je, zda každá čtvercová matice je unitárně podobná matici nějakého relativně jednoduchého typu. Následujícímu důležitému tvrzení se říká věta o Schurově rozkladu. 4.3.1 Věta. Každá čtvercová matice je unitárně podobná nějaké horní trojúhelníkové matici. Podrobněji: Buď A ∈ Cn×n a nechť λ1 , λ2 , . . . , λn jsou všechna vlastní čísla A (každé se zde opakuje tolikrát, kolik činí jeho algebraická násobnost). Potom existuje unitární matice U tak, že U∗ AU = T,

(4.6)

kde T ∈ Cn×n je horní trojúhelníková matice, která má na diagonále prvky λ1 , λ2 , . . . , λn (v daném pořadí). Důkaz. Budeme postupovat indukcí vzhledem k n. Pro n = 1 tvrzení evidentně platí (rozmyslete si, jak budou vypadat matice T a U v případě n = 1). Buď nyní n > 1 a předpokládejme, že tvrzení platí pro matice řádu n − 1. Nechť x1 je nějaký vlastní vektor A s vlastním číslem λ1 , kx1 k = 1; je tedy Ax1 = λ1 x1 . Podle poznámky 1.5.8 lze vektor x1 doplnit na ortonormální bázi Cn , tj. existují vektory x2 , x3 , . . . , xn tak, že vektory x1 , x2 , . . . , xn jsou ortonormální. Označme
X = x1 x2 . . . xn .

Matice X je potom unitární a AX = =X

Ax1 Ax2 . . . ∗

Axn

u X Ax2 . . .




=

λ1 x1 Ax2 . . .
∗ X Axn ,

Axn




=

kde u = (λ1 , 0, . . . , 0)T ∈ Cn (rozmyslete si). Součin X∗ AX můžeme tedy napsat ve tvaru   λ1 v ∗ ∗ , X AX = 0 B kde v ∈ Cn−1 je nějaký vektor, B ∈ C(n−1)×(n−1) nějaká matice. Jelikož pA (λ) = pX∗ AX (λ) = (λ1 − λ) · pB (λ), matice B má vlastní čísla λ2 , λ3 , . . . , λn . Podle indukčního předpokladu existuje unitární matice U1 ∈ C(n−1)×(n−1) tak, že U∗1 BU1 = T1 , kde T1 ∈ C(n−1)×(n−1) je horní trojúhelníková matice, která má na diagonále prvky λ2 , λ3 , . . . , λn (v daném pořadí). Nyní stačí položit   1 0∗ . U=X 0 U1 133

KAPITOLA 4. MATICOVÉ ROZKLADY Zde druhá matice napravo je zřejmě unitární a jelikož součin unitárních matic je unitární (důsledek 1.5.16), je matice U také unitární. Přitom je     1 0∗ 1 0∗ ∗ ∗ = X AX U AU = 0 U1 0 U∗1     1 0∗ λ1 v ∗ 1 0∗ = = 0 U1 0 B 0 U∗1      λ1 v ∗ U1 λ1 v∗ U1 1 0∗ = = = 0 U∗1 0 BU1 0 U∗1 BU1   λ1 v ∗ U1 = . 0 T1 Součin U∗ AU je tedy horní trojúhelníková matice, která má na diagonále opravdu prvky λ1 , λ2 , . . . , λn . Indukční krok byl proveden a tvrzení je dokázáno.  V poznámce 3.1.8 jsme se již setkali s pojmem normální matice. Připomeňme tento pojem. 4.3.2 Definice. Řekneme, že matice A ∈ Cn×n je normální, je-li AA∗ = A∗ A. Dokažme nejprve následující dvě pomocná tvrzení. 4.3.3 Lemma. Jsou-li matice A, B ∈ Cn×n unitárně podobné, pak A je normální právě když B je normální. Důkaz. Nechť A = U∗ BU, kde U je nějaká unitární matice a předpokládejme, že B je normální, tj. BB∗ = B∗ B. Potom
∗ AA∗ = U∗ BU U∗ BU = U∗ BUU∗ B∗ U = U∗ BB∗ U = U∗ B∗ BU =
∗ = U∗ B∗ UU∗ BU = U∗ BU (U∗ BU) = A∗ A,

tj. A je také normální. Podobně pro obrácenou implikaci.



4.3.4 Lemma. Normální trojůhelníková matice je diagonální. Důkaz. Buď T = (tij ) ∈ Cn×n např. horní trojúhelníková (tj. tij = 0 kdykoli i > j) a předpokládejme, že T je normální. Označme TT∗ = A = (aij ),

T∗ T = B = (bij ).

Jelikož T je normální, je ovšem A = B,

tj.

aij = bij .

Přitom je např. b11 = t¯11 t11 = |t11 |2 ,

a11 =

n X j=1

134

t1j t¯1j = |t11 |2 +

n X j=2

|t1j |2 .

4.3. SCHURŮV ROZKLAD A NORMÁLNÍ MATICE Z rovnosti a11 = b11 dostáváme okamžitě, že n X

|t1j |2 = 0,

j=2

tj. t1j = 0 pro každé j = 2, 3, . . . , n (tedy první řádek matice T může mít nenulový prvek pouze na diagonále). Dále podobně vidíme, že 2

2

|t22 | = b22 = a22 = |t22 | +

n X

|t2j |2 ,

j=3

odkud dostáváme, že t2j = 0 pro j = 3, 4, . . . , n. Jelikož T je horní trojúhelníková, je t21 = 0 a vidíme, že ve druhém řádku matice T může být nenulový prvek opět pouze na diagonále. Takto můžeme postupovat dál, až zjistíme, že T je opravdu diagonální.  Nyní již můžeme snadno dokázat následující větu o spektrálním rozkladu. 4.3.5 Věta. Čtvercová matice je unitárně diagonalizovatelná právě když je normální. Důkaz. Skutečnosti, že každá unitárně diagonalizovatelná matice je normální, jsme si všimli již v poznámce 3.1.8. Předpokládejme nyní, že A ∈ Cn×n je normální. Podle věty 4.3.1 je A unitárně podobná nějaké horní trojúhelníkové matici T. Podle lemmatu 4.3.3 je T normální a podle lemmatu 4.3.4 je T diagonální, tj. A je unitárně podobná diagonální matici. Tvrzení je dokázáno.  4.3.6 Poznámka. Jelikož hermitovská matice je evidentně normální, můžeme se nyní na větu 3.1.6 o spektrálním rozkladu pro hermitovské matice dívat jako na speciální případ věty 4.3.5. Pouze by bylo potřeba v reálném případě využít skutečnosti, že všechna vlastní čísla hermitovské matice jsou reálná a vlastní vektory k nim lze volit reálné. Každá unitární matice je zřejmě normální. Odtud plyne následující důležité tvrzení, které jsme si již všimli v poznámce 3.1.8 (a kterou jsme již použili např. v odstavci 3.2). 4.3.7 Věta. Každá unitární matice je unitárně diagonalizovatelná. 4.3.8 Poznámka. Všimněme si ještě jedné zajímavé interpretace unitární diagonalizace. Buď tedy A ∈ Cn×n normální matice se spektrálním rozkladem A = UDU∗ , kde U=

u1 u2 . . .

un

je unitární matice (ui ∈ Cn jsou sloupce U),




D = diag[λ1 , λ2 , . . . , λn ] (λi jsou vlastní čísla A). Součin UD můžeme napsat ve tvaru
UD = λ1 u1 λ2 u2 . . . λn un ;

135

KAPITOLA 4. MATICOVÉ ROZKLADY formálně můžeme tuto rovnost dostat s použitím skutečnosti, že na j-tý sloupec součinu dvou matic se můžeme dívat jako na součin první matice a j-tého sloupce druhé matice [viz odstavec 1.2.13, rovnost (1.16)], tj. opravdu
(UD)(:, j) = U D(:, j) = Uλj E(:, j) = λj U(:, j) = λj uj .

Nyní dostáváme

UDU∗ =

λ1 u1 λ2 u2 . . .

λn u n

tj. matici A lze vyjádřit ve tvaru (4.7)

A=

n X




   

u∗1 u∗2 .. . u∗n



n  X  λi ui u∗i , =  i=1

λi ui u∗i .

i=1

Zde λi jsou právě všechna vlastní čísla matice A, ui příslušné vlastní vektory takové, že u1 , u2 , . . . , un tvoří ortonormální bázi Cn . Formálně ui ∈ Cn×1 , u∗i ∈ C1×n , takže součiny ui u∗i jsou čtvercové matice, ui u∗i ∈ Cn×n . Rozmyslete si, že tyto součiny jsou matice o hodnosti 1, tj. v (4.7) jsme matici A vyjádřili jako součet matic hodnosti 1 (když vynecháme sčítance odpovídající nulovým vlastním číslům). Vyjádření A ve tvaru (4.7) se často také říká spektrální rozklad matice A.

4.4

Singulární rozklad a pseudoinverze

Při aplikaci unitární diagonalizace čtvercové matice, tj. vyjádření matice A ve tvaru A = = UDU∗ , je podstatná právě unitárnost matice U. Na první pohled je zřejmé, že důležitou roli zde hraje skutečnost, že U−1 = U∗ , tj. inverzní matici k U není třeba počítat; z hlediska numerické matematiky jsou ale důležité i některé další vlastnosti unitárních (nebo reálných ortonormálních) matic. Jak víme, ne každá čtvercová matice je unitárně diagonalizovatelná. Pokud vynecháme požadavek, aby ve vyjádření A = XDX−1 byla matice X unitární, dostaneme o trochu širší třídu diagonalizovatelných matic, ale ztrácíme právě výhody unitárnosti. Jiná možnost je zkusit opustit požadavek, aby ve vyjádření A = UAU∗ byla pouze jedna matice U, ale zůstat u požadavku unitárnosti. Ukazuje se, že každou čtvercovou matici A lze napsat ve tvaru (4.8)

A = UDV∗ ,

kde U, V jsou unitární (a D diagonální). Ukazuje se, že zde matice A ani nemusí být čtvercová, což bude důležité např. v souvislosti s řešením úlohy o nejmenších čtvercích. Potom ovšem ani matice D napravo v (4.8) není čtvercová (pokud U, V jsou unitární, tj. čtvercové). V předchozím jsme používali termín diagonální matice pouze v případě, že 136

4.4. SINGULÁRNÍ ROZKLAD A PSEUDOINVERZE daná matice je čtvercová. U této konvence zůstaneme, ale pro naše účely zaveďme pojem matice pseudodiagonální. Buď A ∈ Cm×n (m, n ∈ N, obecně m 6= n). Je-li A = (aij ), pak řekneme, že A je pseudodiagonální, jestliže aij = 0 kdykoli i 6= j. Následující důležité tvrzení je známé pod názvem věta o existenci singulárního rozkladu matice. V literatuře bývá singulární rozklad označován zkratkou SVD (singular value decomposition). 4.4.1 Věta. Buď A ∈ Cm×n (m, n ∈ N). Potom existují unitární matice U ∈ Cm×m , V ∈ Cn×n a pseudodiagonální matice Σ ∈ Rm×n s diagonálními prvky (4.9)

σ1 ≥ σ2 ≥ · · · ≥ σp ≥ 0

(p = min{m, n}) tak, že (4.10)

A = UΣV∗ .

Je-li matice A reálná, lze volit U, V také reálné. Hodnoty σi jsou určeny jednoznačně. 4.4.2 Poznámka. Rozkladu matice A ve tvaru (4.10) se říká singulární rozklad, číslům σ1 , σ2 , . . . , σp se říká singulární čísla (nebo singulární hodnoty) matice A. Poznamenejme, že v literatuře se název singulární čísla někdy používá pouze pro ta z čísel σ1 , σ2 , . . . , σp , která jsou kladná, tj. nikoli pro nulové hodnoty. V jednom speciálním případě jsme se se singulárním rozkladem matic vlastně již setkali — v případě pozitivně semidefintních matic. Je-li A ∈ Cn×n hermitovská pozitivně semidefinitní matice, pak podle věty 3.4.6 jsou všechna její vlastní čísla λ1 , λ2 , . . . , λn nezáporná (reálná jsou podle věty 3.1.1). Podle věty 3.1.6 o spektrálním rozkladu hermitovských matic je A unitárně diagonalizovatelná, tj. existuje unitární matice U ∈ Cn×n tak, že A = UDU∗ , kde D je diagonální, D = diag[λ1 , λ2 , . . . , λn ]. Přitom vlastní čísla λi lze uspořádat např. podle velikost, λ1 ≥ λ2 ≥ · · · ≥ λn ≥ 0. V tomto případě singulární čísla σi se jednoduše rovnají vlastním číslům λi ; v singulárním rozkladu (4.10) lze přitom volit V = U, Σ = D. V případě jiné čtvercové diagonalizovatelné matice již není takovýto jednoduchý vztah mezi vlastními a singulárními čísly a mezi singulárním rozkladem a diagonalizací. Důležité je, že singulární čísla jsou vždy reálná nezáporná a singulární rozklad má každá matice (a to nejenom čtvercová!). Pro aplikace jsou podstatné některé další vlastnosti singulárního rozkladu. V literatuře lze nalézt různé důkazy věty o existenci singulárního rozkladu. Např. ve skriptech [2] se v důkazu využívá norma matice — v našem textu jsme ovšem tento pojem nezaváděli. Na rozdíl od [2] zde ale máme k dispozici aparát založený na vlastních číslech a vlastních vektorech matic. Je známo, že singulární rozklad matice A ∈ Cm×n (tedy obecně nečtvercové) úzce souvisí s vlastními čísly matic AA∗

a

A∗ A.

Tyto matice čtvercové už jsou — je AA∗ ∈ Cm×m , A∗ A ∈ Cn×n . Všimněme si proto některých vlastností těchto matic. 137

KAPITOLA 4. MATICOVÉ ROZKLADY 4.4.3 Tvrzení. Buď A ∈ Cm×n libovolná matice (m, n ∈ N). Potom matice AA∗ a A∗ A mají následující vlastnosti: (i) AA∗ a A∗ A jsou hermitovské a pozitivně semidefinitní; (ii) pro každé x ∈ Cn je Ax = 0 právě když A∗ Ax = 0; (iii) pro každé x ∈ Cm je A∗ x = 0 právě když AA∗ x = 0; (iv) hod(A∗ A) = hod(A) = hod(A∗ ) = hod(AA∗ ). Důkaz. Bod (i). Hermitovskost matic A∗ A a AA∗ je zřejmá — plyne okamžitě z třetí rovnosti v tvrzení 1.2.8. Ukažme, že např. A∗ A je pozitivně semidefinitní. Buď x ∈ Cn . Potom x∗ A∗ Ax = (Ax)∗ (Ax) = kAxk2 ≥ 0. Jelikož x ∈ Cn bylo libovolné, vidíme, že A∗ A je opravdu pozitivně semidefinitní (viz analogickou úvahu v odstavci 4.1.4 pro případ čtvercové regulární matice). Podobně pro matici AA∗ . Bod (ii). Je-li Ax = 0, pak je evidentně také A∗ Ax = 0. Obrácená implikace už není na první pohled tak zřejmá. S použitím rovnosti (1.52) z odstavce 1.5.9 ale snadno dostaneme, že pokud A∗ Ax = 0, pak 0 = hA∗ Ax, xi = hAx, Axi = kAxk2 , tj. také Ax = 0. Bod (iii) dostaneme stejným způsobem jako bod (ii) — stačí zaměnit roli matic A ∗ a A. Bod (iv). Buď k dimenze množiny všech řešení homogenní soustavy Ax = 0. Jelikož A ∈ Cm×n , podle věty 1.4.1 je k = n − hod(A). Podle bodu (ii) je dimenze množiny všech řešení soustavy (A∗ A)x = 0 také rovna k a jelikož A∗ A ∈ Cn×n , je k = n − hod(A∗ A) a vidíme, že hod(A∗ A) = hod(A). Rovnost hod(A) = hod(A∗ ) je zřejmá (viz odstavec 1.2.9). Poslední rovnost, tj. rovnost hod(A∗ ) = hod(AA∗ ), dostaneme podobně jako rovnost hod(A) = hod(A∗ A).  Dále se podívejme na některé vlastnosti matic A∗ A a AA∗ , které se týkají vlastních čísel a vlastních vektorů. 4.4.4 Tvrzení. Buď A ∈ Cm×n libovolná matice (m, n ∈ N). Potom platí: (i) všechna vlastní čísla matic A∗ A a AA∗ jsou reálná a nezáporná; (ii) je-li v vlastní vektor matice A∗ A s nenulovým vlastním číslem λ, pak Av je vlastní vektor matice AA∗ se stejným vlastním číslem λ; 138

4.4. SINGULÁRNÍ ROZKLAD A PSEUDOINVERZE (iii) je-li u vlastní vektor matice AA∗ s nenulovým vlastním číslem λ, pak A∗ u je vlastní vektor matice A∗ A se stejným vlastním číslem λ; (iv) jsou-li v 1 , v 2 ortogonální vlastní vektory matice A∗ A, pak vektory Av 1 , Av 2 jsou také ortogonální; (v) jsou-li u1 , u2 ortogonální vlastní vektory matice AA∗ , pak vektory Au1 , Au2 jsou také ortogonální; (vi) matice A∗ A a AA∗ mají stejná nenulová vlastní čísla včetně násobností. Důkaz. Bod (i) plyne okamžitě ze skutečnosti, že A∗ A a AA∗ jsou pozitivně semidefinitní a věty 3.4.6. Bod (ii). Buď v ∈ Cn (v 6= 0) vlastní vektor A∗ A s vlastním číslem λ > 0, tj. (∗)

A∗ Av = λv.

Jelikož λ 6= 0, v 6= 0, je nutně y = Av 6= 0. Vynásobímeli rovnost (∗) maticí A zleva, dostáváme AA∗ Av = λAv, tj. AA∗ y = λy a vidíme, že y = Av je opravdu vlastní vektor matice AA∗ s vlastním číslem λ. Bod (iii) dostaneme podobně jako bod (ii). Bod (iv). Nechť v1 , v 2 jsou vlastní vektory matice A∗ A s vlastními čísly po řadě λ1 , λ2 . Předpokládejme, že v 1 , v 2 jsou ortogonální a označme u1 = Av 1 , u2 = Av 2 . Chceme ukázat, že u1 , u2 jsou ortogonální. Je-li alespoň jedno z vlastních čísel λ1 , λ2 nulové, např. λ1 = 0, pak A∗ Av1 = 0. Podle bodu (ii) tvrzení 4.4.3 je potom u1 = Av 1 = 0 a vektory u1 , u2 jsou ortogonální. Předpokládejme, že λ1 6= 0 6= λ2 , λ1 6= λ2 . Jelikož u1 = Av 1 , u2 = Av 2 jsou vlastní vektory hermitovské matice AA∗ [bod (ii)], jsou ortogonální podle věty 3.1.3 (mimochodem, v tomto případě jsou podle téže věty vektory v 1 , v 2 nutně ortogonální). Zbývá uvažovat případ λ1 = λ2 6= 0. Jsou-li v 1 , v 2 ortogonální, tj. v ∗1 v 2 = 0, pak u∗1 u2 = (Av 1 )∗ (Av 2 ) = v∗1 (A∗ Av 2 ) = λ1 v ∗1 v 2 = 0, tj. u1 , u2 jsou opravdu ortogonální. Bod (v) dostaneme podobně jako bod (iv). Bod (vi). Podle bodů (ii) a (iii) je λ 6= 0 vlastní číslo matice A∗ A právě když je vlastní číslo matice AA∗ . Jelikož A∗ A je hermitovská, λ jakožto vlastní číslo A∗ A má stejnou algebraickou a geometrickou násobnost — stejně tak pro matici AA∗ . Stačí ukázat, že charakteristický podprostor matice A∗ A s vlastním číslem λ (viz definici 2.1.4) má stejnou dimenzi jako charakteristický podprostor AA∗ s vlastním číslem λ. Přenecháváme čtenáři, aby si rozmyslel, že tato skutečnost snadno plyne z bodů (iv) a (v) (ještě s použitím poznámky 1.5.7 o existenci ortonormální báze).  Nyní již můžeme poměrně snadno dokázat následující tvrzení, kterému se někdy říká geometrická věta o singulárním rozkladu (geometrický tvar singulárního rozkladu). 139

KAPITOLA 4. MATICOVÉ ROZKLADY 4.4.5 Věta. Buď A ∈ Cm×n nenulová matice, hod(A) = r. Potom existuje ortonormální báze v 1 , v 2 , . . . , v n prostoru Cn , existuje ortonormální báze u1 , u2 , . . . , um prostoru Cm a existují čísla σ1 ≥ σ2 ≥ · · · ≥ σr > 0 tak, že ( ( σi v i pro i = 1, 2, . . . , r, σi ui pro i = 1, 2, . . . , r, ∗ A ui = (4.11) Av i = 0 pro i = r + 1, . . . , m. 0 pro i = r + 1, . . . , n, Vektory v1 , v 2 , . . . , v n jsou potom vlastní vektory matice A∗ A, vektory u1 , u2 , . . . , um jsou vlastní vektory matice AA∗ a hodnoty σ12 , σ22 , . . . , σr2 jsou nenulová vlastní čísla matic A∗ A a AA∗ . Je-li matice A reálná, lze volit vektory v i , ui reálné. Důkaz. Nechť λ1 , λ2 , . . . , λn jsou vlastní čísla matice A∗ A (je A∗ A ∈ Cn×n ). Jelikož A∗ A je pozitivně semidefinitní, lze λi volit tak, že λ1 ≥ λ2 ≥ · · · ≥ λn ≥ 0. přitom je hod(A∗ A) = hod(A) = r [bod (iv) tvrzení 4.4.3], takže λi > 0 pro i = 1, 2, . . . , r a λi = 0 pro i > r je-li r < n (rozmyslete si). Nechť v 1 , v 2 , . . . , v n ∈ Cn jsou ortonormální vlastní vektory matice A∗ A s vlastními čísly po řadě λ1 , λ2 , . . . , λn ; je-li A reálná, je ovšem A∗ A = AT A také reálná a vektory v i lze volit reálné (v 1 , v 2 , . . . , v n je ortonormální báze Cn ; jelikož A∗ A je hermmitovská, taková ortonormální báze existuje). Pro i = 1, 2, . . . , r definujeme čísla σi a vektory ui tak, že položíme (4.12)

σi = kAv i k,

ui =

1 Avi σi

(je-li A reálná a vektory v i voleny reálné, jsou ovšem vektory ui také reálné). Pro tato i je potom (4.13)

Av i = σi ui ,

kui k =

1 1 kAv i k = σi = 1. σi σi

Jelikož vektory v i jsou ortononormální, jsou vektory u1 , u2 , . . . , ur ortogonální podle bodu (iv) tvrzení 4.4.4 a podle(4.13) tedy ortonormální. Podle bodu (ii) tvrzení 4.4.4 jsou vektory u1 , u2 , . . . , ur vlastní vektory matice AA∗ s vlastními čísly po řadě λ1 , λ2 , . . . , λr . Je-li m > r, nechť ur+1 , ur+2 , . . . , um je nějaká ortonormální báze množiny všech řešení homogenní soustavy AA∗ x = 0 [podle bodu (iv) je hod(AA∗ ) = hod(A) = r, takže dimenze této množiny je rovna m − r a taková báze existuje; je-li A reálná, je možné vektory ur+1 , ur+2 , . . . , um volit reálné]. Pro i = r + 1, r + 2, . . . , m je A∗ ui = 0 podle bodu (iii) tvrzení 4.4.3. Je-li 1 ≤ i ≤ r, r < j ≤ n, pak ui , uj jsou vlastní vektory matice AA∗ s různými vlastními čísly (ui odpovídá kladnému vlastnímu číslu, uj nulovému), takže jsou ortogonální (věta 3.1.3). Vidíme, že vektory u1 , u2 , . . . , um tvoří ortonormální bázi Cm . Všimněme si, že pro i = 1, 2, . . . , r je σi2 = λi — podle (4.12) je σi2 = hAv i , Av i i = hA∗ Av i , v i i = hλi v i , v i i = λi hvi , v i i = λi ; zde jsme ještě použili rovnost (1.52) z poznámky 1.5.9, toho, že v i je vlastní vektor matice A∗ A a kv i k = 1. Abychom viděli, že platí všechny rovnosti z (4.11), zbývá nyní ukázat, 140

4.4. SINGULÁRNÍ ROZKLAD A PSEUDOINVERZE že pro i = 1, 2, . . . , r je A∗ ui = σi v i . Použijeme-li ale (4.12) a skutečnosti, že v i je vlastní vektor matice A∗ A s vlastním číslem λi , máme A∗ ui =

1 ∗ λi A Av i = v i = σi v i , σi σi

neboť, jak jsme právě viděli, je σ 2 = λi . Tvrzení je dokázáno.



4.4.6 Poznámka. Všimněme si, jak z geometrické věty o singulárním rozkladu 4.4.5 plyne věta 4.4.1 o singulárním rozkladu. Připomeňme, že podle věty 4.4.1 ke každé matici A ∈ ∈ Cm×n existují unitární matice U ∈ Cm×m , V ∈ Cn×n a pseudodiagonální matice Σ ∈ ∈ Rm×n s nezápornými prvky na diagonále tak, že A = UΣV∗ .

(4.14)

Je-li matice A nulová, stačí volit matici Σ ∈ Rm×n nulovou a matice U, V libovolné unitární matice (příslušného řádu). Není-li A nulová, můžeme U, Σ, V na základě věty 4.4.5 jednoduše sestavit. Nechť tedy A ∈ Cm×n je nenulová a nechť vektory v 1 , v 2 , . . . , v n ∈ Cn ,

u1 , u 2 , . . . , um ∈ C m ,

číslo r a čísla σ1 ≥ σ2 ≥ · · · ≥ σr > 0 značí totéž, co ve větě 4.4.5. Položme ještě p = = min{m, n}. Pokud je r < p, položme dále σr+1 = σr+2 = · · · = σp = 0. Nechť (4.15)

U=

u1 u2 . . .

um




,

V=

v1 v 2 . . .

vn




a nechť Σ ∈ Rm×n je pseudodiagonální matice, která má na diagonále prvky σ1 , σ2 , . . . , σp . Matice U, V jsou unitární, protože vektory u1 , u2 , . . . , um a také v 1 , v 2 , . . . , v n jsou ortonormální. Vzhledem k tomu, že V je unitární, je rovnost (4.14) ekvivalentní rovnosti (4.16)

AV = UΣ.

Tato rovnost ale snadno plyne z rovností (4.11). Pro i = 1, 2, . . . , r je totiž (AV)(:, i) = A · V(:, i) = Av i = σi ui a (UΣ)(:, i) = U · Σ(:, i) = σi U · E(:, i) = σi (UE)(:, i) = σi ui . Matice napravo a nalevo v (4.16) mají tedy stejných prvních r sloupců. Další sloupce těchto dvou matic jsou nulové — pro matici UΣ proto, že pro i > r je i-tý sloupec matice Σ nulový, nulovost i-tého sloupce součinu AV plyne z toho, že podle (4.11) pro i = r + 1, r + 2, . . . , n je Av i = 0. Vidíme, že opravdu platí rovnost (4.16) a tedy i rovnost (4.14). Přenecháváme čtenáři, aby si rozmyslel, že naopak, pokud platí (4.14), kde U, V mají tvar (4.15), pak vektory ui , v i nutně splňují rovnosti (4.11). Je-li matice A 141

KAPITOLA 4. MATICOVÉ ROZKLADY reálná, pak podle věty 4.4.5 lze vektory ui , v i volit reálné, tj. matice U, V ve větě 4.4.1 lze volit reálné. Všimněme si ještě, jak přímo z rovnosti (4.14) plyne, že čísla σi (singulární čísla A) jsou rovna (nezáporným) druhým odmocninám vlastních čísel matic A∗ A a AA∗ . Je-li A = UΣV∗ , pak např.
∗ A∗ A = UΣV∗ (UΣV∗ ) = VΣ∗ U∗ UΣV∗ = VΣ∗ ΣV∗ .

Přitom Σ∗ = ΣT (Σ je reálná), Σ∗ Σ ∈ Rn×n ,

ΣT Σ = diag[σ12 , σ22 , . . . , σn2 ] (pro jednoduchost nyní uvažujeme případ, že m ≥ n — rozmyslete si, čím by se lišil případ m < n). Rovnost A∗ A = VΣT ΣV∗ ale znamená, že vlastní čísla matice A∗ A jsou rovna právě číslům σ12 , σ22 , . . . , σn2 (VΣT ΣV∗ je vlastně spektrální rozklad matice A∗ A). Zároveň vidíme, že singulární čísla σi jsou určena jednoznačně. Mimochodem, uvědomíme-li si, že AA∗ = (UΣV∗ ) UΣV∗


∗

= UΣV∗ VΣ∗ U∗ = UΣΣT U∗ ,

pak jiným způsobem vidíme, že matice A∗ A a AA∗ mají stejná nenulová vlastní čísla včetně násobností — srovnejte s bodem (vi) tvrzení 4.4.4. 4.4.7 Poznámka. V poznámce 4.3.8 jsme viděli, že např. unitárně diagonalizovatelnou matici lze napsat jako součet matic o hodnosti 1 — viz rovnost (4.7). Pro libovolnou matici můžeme ale stejným způsobem použít singulární rozklad. Buď A ∈ Cm×n , kde m ≥ n, hod(A) = r > 0, a nechť A = UΣV∗ je singulární rozklad A, tj. U, V jsou unitární matice, U ∈ Cm×m , V ∈ Cn×n , U=

u1 u2 . . .

um




V=

,

v1 v2 . . .

vn




;

dále je Σ ∈ Rm×n pseudodiagonální matice, která má na diagonále singulární čísla σi , σ1 ≥ σ2 ≥ · · · ≥ σr > 0,

σi = 0 pro i > r.

Singulárnímu rozkladu v daném tvaru se někdy podrobněji říká úplný singulární rozklad. Zastavme se nejprve ještě u tzv. redukovaného a kondenzovaného rozkladu. Je-li m > n, pak matice Σ má tvar 

142

    Σ=    

σ1 0 . . . 0 σ2 . . . .. .. . . . . . 0 0 ... .. .. . .

σn .. .

0

0

0

...

0 0 .. .



    ,    

4.4. SINGULÁRNÍ ROZKLAD A PSEUDOINVERZE tj. posledních m − n řádků je nulových. Označíme-li  σ1  0 b = diag[σ1 , σ2 , . . . , σn ] =  (4.17) Σ  ..  . 0

0 ... σ2 . . . .. . . . . 0 ...

0 0 .. . σn



  , 

b ∈ Rn×n čtvercová diagonální matice a původní matici Σ můžeme zapsat blokově ve je Σ tvaru   b Σ Σ= 0

[kde 0 značí nulovou matici typu (m − n) × n]. Označme ještě
b = u1 u2 . . . un , U U1 = un+1 un+2 . . .

um




;

b tedy vznikla z matice U vynecháním posledních m − n sloupců a U můžeme matice U blokově zapsat ve tvaru   b U1 . U= U Formálně ještě označme Potom je ∗

A = UΣV =



b = V. V

b U1 U

 b  Σ b∗ = U bΣ bV b ∗. V 0

b ∈ Cm×n , U b má ortonormální sloupce (není-li m = n, není U b unitární, neboť Zde je U b ∈ Rn×n je čtvercová diagonální, a V b ∈ Cn×n je unitární. Vyjádření není čtvercová), Σ matice A ve tvaru (4.18)

bΣ bV b∗ A=U

se říká redukovaný singulární rozklad matice A. b Jestliže A má plnou hodnost, tj. r = n (stále předpokládáme, že m ≥ n), je matice Σ regulární (všechny její diagonální prvky σi jsou nenulové). Pokud je r < n, pak jsou ovšem b nulové, a můžeme je opět redukovat. Předpokládejme tedy, že některé řádky a sloupce Σ r < n a označme   σ1 0 . . . 0  0 σ2 . . . 0   e = diag[σ1 , σ2 , . . . , σr ] =  Σ  .. .. . . ..  .  . . . .  0

0

...

σr

e ∈ Rr×r diagonální regulární matice a matici Σ b z předchozího můžeme blokově psát Je Σ ve tvaru   e 0 Σ b Σ= , 0 0 143

KAPITOLA 4. MATICOVÉ ROZKLADY kde 0 značí nulové matice vhodných řádů (rozmyslete si jakých). Dále označme

e = u1 u2 . . . ur , U U2 = ur+1 ur+2 . . . un a

e = V

v1 v2 . . .

vr




V2 =

,

v r+1 v r+2 . . .

vn




.

e ∈ Cm×r , V e ∈ Cn×r , U, e V e mají ortonormální sloupce. Matice U, b V b lze přitom Potom je U zapsat blokově ve tvaru     b = U b = V e U2 , e V2 . U V Odtud

bΣ bV b∗ = U



  e ∗   e∗  Σ 0 V eΣ eV e ∗, e U2 e V2 eΣ e 0 = U =U U V 0 0 V2∗

a podle (4.18) tedy

eΣ eV e ∗. A=U

(4.19)

Vyjádření matice A ve tvaru (4.19) se říká kondenzovaný singulární rozklad. Všimněme si, že pro j = 1, 2, . . . , r je

takže

e Σ)(:, e e · Σ(:, e j) = Uσ e j E(:, j) = σj U(:, e j) = σj uj , (U j) = U eΣ eV e∗ = U

σ1 u1 σ2 u2 . . .

σr ur

Podle (4.19) dostáváme (4.20)

A=

r X




   

v ∗1 v ∗2 .. . v ∗r



r  X  σi ui v ∗i . =  i=1

σi ui v ∗i .

i=1

Této rovnosti se někdy využívá k aproximaci matic (např. tak, že některé sčítance pro malá σi vynecháme — pro podrobnosti viz např. monografii [1]). Na základě věty o singulárním rozkladu můžeme snadno dokázat následující zajímavé tvrzení, kterému se říká věta o polárním rozkladu. Pro jednoduchost formulace se zde omezíme na čtvercové matice. 4.4.8 Věta. Buď A ∈ Cn×n libovolná čtvercová matice. Potom existuje pozitivně semidefinitní (hermitovská) matice P ∈ Cn×n a unitární matice U ∈ Cn×n tak, že (4.21)

A = PU.

Je-li A reálná, lze matice P, U volit reálné. 144

4.4. SINGULÁRNÍ ROZKLAD A PSEUDOINVERZE Důkaz. Nechť A má singulární rozklad A = WΣV∗ , kde W, V ∈ Cn×n jsou unitární, Σ ∈ Rn×n je diagonální s nezápornými prvky na diagonále. Jelikož W∗ W = E, je A = WΣV∗ = WΣW∗ WV∗ = PU, kde jsme označili P = WΣW∗ ,

U = WV∗ .

Zde matice P je zřejmě hermitovská a pozitivně semidefinitní (její vlastní čísla jsou diagonální prvky matice Σ, která jsou nezáporná) a matice U je unitární, neboť je to součin dvou unitárních matic. Je-li A reálná, lze matice W, V volit reálné, tj. P a U jsou potom také reálné.  4.4.9 Poznámka. Všimněme si, že matice P v polárním rozkladu je určena jednoznačně. Je-li A = PU polární rozklad A, pak (když použijeme skutečnosti, že P∗ = P) AA∗ = PUU∗ P∗ = P2 , tj. P je pozitivně semidefinitní odmocnina pozitivně semidefinitní matice AA∗ . Podle věty 3.4.14 je ale tato odmocnina určena jednoznačně. Matice U v polárním rozkladu obecně není určena jednoznačně. Je-li ale A regulární, pak už U je určena jednoznačně. V tom případě je totiž P také regulární a je-li A = PU, je nutně U = AP−1 . Všimněme si ještě, že na polární rozklad matice se můžeme dívat jako na zobecnění exponenciálního tvaru komplexního čísla. Je-li z ∈ C, z 6= 0, pak z můžeme napsat ve tvaru z = |z|ejϕ , kde |z| > 0 je absolutní hodnota z, ϕ je nějaká hodnota argumentu z. Přitom |ejϕ | = 1. I když ϕ není určeno jednoznačně, samotná hodnota ejϕ jednoznačně určena je. V případě z = 0 můžeme formálně psát 0 = 0 · u, kde u ∈ C, |u| = 1, je libovolné komplexní číslo na jednotkové kružnici. (Rozmyslete si, co přesně říká věta o polárním rozkladu v případě n = 1.) Přitom ejϕ = cos ϕ + j sin ϕ, což je vlastně vyjádření bodu jednotkové kružnice v polárních souřadnicích, a na rovnost z = |z|ejϕ = |z| cos ϕ + j|z| sin ϕ se můžeme dívat jako na vyjádření bodu z komplexní roviny v polárních souřadnicích. Odtud zřejmě název polární rozklad. Vraťme se zpátky k singulárnímu rozkladu matice. Asi nejznámější a nejzávažnější aplikace singulárního rozkladu je použití na řešení úlohy o nejmenších čtvercích. Algebraicky můžeme tuto úlohu formulovat následujícím způsobem. 145

KAPITOLA 4. MATICOVÉ ROZKLADY 4.4.10 Definice. Buď A ∈ Cm×n , b ∈ Cm (resp. A ∈ Rm×n , b ∈ Rm ). Řekneme, že x ∈ Cn (resp. x ∈ Rn ) je řešení úlohy o nejmenších čtvercích pro A, b, jestliže x minimalizuje hodnotu kb − Axk, tj. jestliže (4.22)

kb − Axk ≤ kb − Ayk

pro každé y ∈ Cn (resp. každé y ∈ Rn ).

Zůstaneme zde u takto abstraktně formulované úlohy o nejmenších čtvercích. V aplikacích se úloha o nejmenších čtvercích nejčastěji řeší v souvislosti s aproximačními problémy. Pro první přiblížení viz např. odstavec 4.1 ve skriptech [2]. V dalším budeme uvažovat případ, kdy m ≥ n — tento případ se nejčastěji objevuje v aplikacích. Řešit úlohu o nejmenších čtvercích je možné různými metodami. Známá je klasická metoda, ve které se používá soustavy tzv. normálních rovnic. Platí následující tvrzení. 4.4.11 Věta. Buď m ≥ n, A ∈ Cm×n , b ∈ Cm (resp. A ∈ Rm×n , b ∈ Rm ). Potom x ∈ Cn (resp. x ∈ Rn ) je řešení úlohy o nejmenších čtvercích pro A, b právě když (4.23)

A∗ (b − Ax) = 0.

4.4.12 Poznámka. Důkaz věty 4.4.11 lze nalézt např. v [2] (odstavec 4.2). Rovnost (4.23) můžeme ekvivalentně zapsat ve tvaru (4.24)

A∗ Ax = A∗ b.

V tomto tvaru se jedná o soustavu lineárních rovnic s maticí A∗ A. S maticí A∗ A jsme se v předchozím několikrát setkali. Např. podle bodu (i) tvrzení 4.4.3 je A∗ A hermitovská (A∗ A je čtvercová řádu n) a pozitivně semidefinitní. V odstavci 1.2.9 (též později v poznámce 4.2.2) jsme použili název matice plné hodnosti. Připomeňme, že matice A ∈ Cm×n má plnou hodnost, jestliže hod A = min{m, n}. V našem případě, kdy m ≥ n, má A plnou hodnost jestliže hod A = n, tj. když sloupce A jsou lineárně nezávislé. Všimněme si, že je-li A ∈ Cm×n , kde m ≥ n, pak A∗ A je regulární (a pozitivně definitní) právě když A má plnou hodnost. Tato skutečnost jednoduše plyne z bodu (iv) tvrzení 4.4.3. I když pro praktické řešení úlohy o nejmenších čtvercích se v současné době používají většinou jiné metody (zvláště v případě většího n a v případě, kdy A nemá plnou hodnost), ze soustavy normálních rovnic je vidět, jak je to s existencí a jednoznačností řešení. Můžeme si všimnou, že platí následující tvrzení. Buď A ∈ Cm×n , b ∈ Cm (resp. A ∈ Rm×n , b ∈ Rm ), kde m ≥ n. Potom úloha o nejmenších čtvercích pro A, b má řešení. Toto řešení je určeno jednoznačně právě když A má plnou hodnost. 146

4.4. SINGULÁRNÍ ROZKLAD A PSEUDOINVERZE Důkaz tohoto tvrzení je skoro samozřejmý. Jestliže A má plnou hodnost, pak podle předchozího A∗ A je regulární (dokonce pozitivně definitní) a soustava (4.24) tedy má právě jedno řešení. Pokud A nemá plnou hodnost, pak A∗ A je singulární a pokud soustava (4.24) má řešení, těchto řešení je nekonečně mnoho (viz odstavec 1.4.4 pro popis množiny všech řešení nehomogenní soustavy). Zbývá ukázat, že soustava (4.24) má vždy řešení. Víme, že nehomogenní soustava lineárních rovnic má řešení právě tehdy, je-li sloupec pravých stran lineární kombinací sloupců matice této soustavy — viz rovnost 1.34 před větou 1.4.3. Stačí tedy ukázat, že pro libovolné b ∈ Cm je vektor A∗ b lineární kombinací sloupců matice A∗ A. Nechť P je množina všech lineárních kombinací sloupců matice A∗ A, Q množina všech lineárních kombinací sloupců matice A∗ . Množiny P, Q jsou lineární podprostory v Cn , přičemž zřejmě P ⊂⊂ Q (rozmyslete si). S použitím bodu (iv) věty 4.4.3 ale dostáváme dim P = hod(A∗ A) = hod(A∗ ) = dim Q a tedy P = Q [viz větu 1.1.8, bod (f)]. Je ale A∗ b ∈ Q a tedy také A∗ b ∈ P , tj. soustava (4.24) opravdu má řešení. 4.4.13. Jak jsme již poznamenali dříve, pro řešení úlohy o nejmenších čtvercích je možné použít např. QR rozklad; pro podrobnosti viz např. skripta [2]. V [2] se mluví také o řešení úlohy o nejmenších čtvercích pomocí singulárního rozkladu matice. Pro úplnost zde příslušné úvahy zopakujme. V dalším stále předpokládejme, že m ≥ n (m, n ∈ N), A ∈ Cm×n , b ∈ Cm. Budeme předpokládat, že hod A = r > 0 (formálně je úloha o nejmenších čtvercích formulována i pro případ nulové matice, nemá ale valný smysl — rozmyslete si, jak v tomto případě vypadá řešení). Nechť (4.25)

A = UΣV∗

je singulární rozklad matice A, tj. U, V jsou unitární, U ∈ Cm×m , V ∈ Cn×n (je-li A reálná, pak předpokládáme, že U, V jsou také reálné), Σ ∈ Rm×n je pseudodiagonální matice, která má na diagonále singulární čísla σ1 ≥ σ2 ≥ · · · ≥ σn ≥ 0. Přitom σi > 0 pro 1 ≤ i ≤ r a (pokud r < n) σi = 0 pro r < i ≤ n. Označme dále   σ1 0 . . . 0  0 σ2 . . . 0   e = diag[σ1 , σ2 , . . . , σr ] =  (4.26) Σ  .. ..  . .. . .  . . .  . 0 0 . . . σr

e ∈ Rr×r regulární (diagonální) matice a matici Σ můžeme blokově zapsat ve Je tedy Σ tvaru   e 0 Σ (4.27) Σ= . 0 0

Připomeňme, že řešením úlohy o nejmenších čtvercích pro A, b se rozumí takové x ∈ ∈ Cn , pro které je kb − Axk minimální. Nejprve si všimneme, že 147

KAPITOLA 4. MATICOVÉ ROZKLADY kb − Axk je minimální právě když kU∗ b − ΣV∗ xk je minimální. To plyne jednoduše ze skutečnosti, že podle věty 1.5.12 unitární matice U zachovává eukleidovskou normu, tj. pro každé y ∈ Cm je kUyk = kyk. Je-li U unitární, je také U∗ unitární a pro každé x ∈ Cn je







kb − Axk = U∗ (b − Ax) = U∗ b − U∗ Ax = U∗ b − U∗ UΣV∗ x = U∗ b − ΣV∗ x .

Vidíme, že výše uvedené tvrzení platí. Označme ještě

c = U∗ b,

(4.28)

y = V∗ x.

Z předchozího vidíme, že x ∈ Cn minimalizuje kb − Axk právě když x = Vy, kde y ∈ Cn minimalizuje kc − Σyk. Vlastně jsme tak úlohu o nejmenších čtvercích pro A, b převedli na úlohu o nejmenších čtvercích pro pseudodiagonální matici Σ a vektor c = U∗ b. Podívejme se, jak řešit tuto novou úlohu. Je-li y = (y 1 , y 2 , . . . , y n )T ∈ Cn , pak      σ1 0 . . . 0 0 . . . 0 y1 σ1 y 1  0 σ2 . . . 0 0 . . . 0   y 2   σ2 y 2        .. .. . . .. .. ..   ..   ..   .     . . . . .  .   .         Σy =  0 0 . . . σr 0 . . . 0    y r  =  σr y r   0 0 . . . 0 0 . . . 0   yr+1   0        .. .. .. .. ..   ..   ..   . . . . .  .   .  0 0 ... 0 0 ... 0 yn 0 (je přitom Σy ∈ Cm ). Jestliže vektor c má složky ci , tj. c = (c1 , c2 , . . . , cm )T , pak 2

kc − Σyk =

r X i=1

2

|ci − σi yi | +

m X

|ci |2 .

i=r+1

Jelikož ci jsou konstantní (měníme pouze složky yi vektoru y), je tento výraz minimální právě když r X |ci − σi yi |2 = 0, i=1

tj. právě když (4.29)

148

yi =

ci σi

pro i = 1, 2, . . . , r.

4.4. SINGULÁRNÍ ROZKLAD A PSEUDOINVERZE Hodnoty yr+1 , yr+2 , . . . , yn (když r < n) mohou být přitom libovolné. Mimochodem opět vidíme, že úloha o nejmenších čtvercích má vždy řešení a toto řešení je určeno jednoznačně právě když r = n, tj. právě když A má plnou hodnost (stále předpokládáme, že m ≥ n). Vše můžeme shrnout do následujícího tvrzení. 4.4.14 Věta. Nechť m ≥ n, A ∈ Cm×n , hod A = r > 0, b ∈ Cm . Jestliže A má singulární rozklad A = UΣV∗ , σ1 ≥ σ2 ≥ · · · ≥ σr > 0 jsou nenulová singulární čísla A, pak x ∈ Cn je řešení úlohy o nejmenších čtvercích pro A, b právě když x = Vy, kde y = (y1 , y2 , . . . , yn )T ∈ Cn , yi =

ci σi

pro i = 1, 2, . . . , r;

ci jsou přitom složky vektoru c = (c1 , c2 , . . . , cm )T = U∗ b (je-li r < n, složky yr+1 , yr+2 , . . . , yn vektoru y jsou libovolné). 4.4.15 Poznámka. Jak víme, má-li matice A plnou hodnost, pak při libovolném b má úloha o nejmenších čtvercích pro A, b právě jedno řešení. V případě, že A plnou hodnost nemá, řešení existuje, ale není určeno jednoznačně — řešení je nekonečně mnoho. V aplikacích ale většinou potřebujeme pracovat pouze s jedním řešením. Je proto potřeba nějakým způsobem z nekonečně mnoha řešení vybrat jedno „správnéÿ, tj. je potřeba přidat nějaké podmínky zaručující jednoznačnost řešení. Někdy mohou tyto podmínky vycházet z konkrétní aplikace. Pokud takové podmínky vycházející z aplikace nemáme, pak většinou přidáváme obecnou podmínku, podle které uvažujeme řešení úlohy o nejmenších čtvercích, které má mezi ostatními řešeními nejmenší eukleidovskou normu. Můžeme tedy formulovat následující úlohu: Buď A ∈ Cm×n , b ∈ Cm . Nalezněte x ∈ Cn takové, že hodnota kb − Axk je minimální a zároveň kxk je minimální (mezi všemi x, které vyhovují předchozí podmínce). Takto formulované úloze můžeme např. říkat modifikovaná úloha o nejmenších čtvercích. Všimněme si, že modifikovaná úloha o nejmenších čtvercích má vždy právě jedno řešení. Má-li A plnou hodnost, pak ovšem řešení modifikované úlohy o nejmenších čtvercích je totéž jako řešení původní úlohy o nejmenších čtvercích. Uvažujme tedy případ, kdy A nemá plnou hodnost, tj. hod A = r < n (stále A ∈ Cm×n , m ≥ n, b ∈ Cn×n , r > 0, A = UΣV∗ je singulární rozklad A). Podle předchozího víme, že každé řešení úlohy o nejmenších čtvercích pro A, b můžeme napsat ve tvaru x = Vy, kde y = (y1 , y2 , . . . , yn )T ∈ Cn , yi =

ci σi

pro i = 1, 2, . . . , r, 149

KAPITOLA 4. MATICOVÉ ROZKLADY yi jsou libovolné pro r < i ≤ n, c = (c1 , c2 , . . . , cm )T = U∗ b. Pro tato x je r n X X ci 2 kxk = kVyk = kyk = |yi |2 . σi + 2

2

2

i=1

i=r+1

Je zřejmé, že kxk bude minimální právě když yr+1 = yr+2 = · · · = yn = 0. (Připomeňme, že v singulárním rozkladu jsou jednoznačně určena singulární čísla, nikoli matice U, V. Vektor c = U∗ b v předchozím tedy není určen jednoznačně a tedy ani prvních r složek vektoru y není určeno jednoznačně. Přenecháváme čtenáři, aby si rozmyslel, že nicméně vektor x = Vy jednoznačně určen je — vychází to ze skutečnosti, že všechna řešení úlohy o nejmenších čtvercích lze napsat ve výše uvedeném tvaru. 4.4.16 Poznámka. V předchozím jsme k vyjádření řešení modifikované úlohy o nejmenších čtvercích použili úplný singulární rozklad matice. Všimněme si, že k tomu ve skutečnosti stačí kondenzovaný singulární rozklad, o kterém jsme mluvili v poznámce 4.4.7. Nechť m ≥ n, A ∈ Cm×n , hod A = r > 0, a nechť A = UΣV∗ je singulární rozklad A, (4.30)

U=

u1 u2 . . .




um

,

V=

v1 v2 . . .

vn




,

σ1 ≥ σ2 ≥ · · · ≥ σr > 0 jsou všechna nenulová singulární čísla matice A. Z poznámky 4.4.7 víme, že pokud označíme (4.31)

e = v1 v2 . . . vr , e = diag[σ1 , σ2 , . . . , σr ], U e = u1 u2 . . . ur , V Σ pak

eΣ eV e ∗; A=U

(4.32)

mluvili jsme v tom případě o kondenzovaném singulárním rozkladu. Přitom je (4.33)



Σ=

e 0 Σ 0 0



,

kde 0 značí nulové matice vhodných řádů. Označíme-li ještě U3 =

ur+1 ur+2 . . .

um

je (4.34)

U=



e U3 U




,

V2 =

,

V=



v r+1 v r+2 . . .

e V2 V



vn




,

.

Buď dále b ∈ Cm a uvažujme modifikovanou úlohu o nejmenších čtvercích pro A, b. Označme e ∗b e c = (c1 , c2 , . . . , cn )T = U a dále

150

e −1 e e=Σ c. y

4.4. SINGULÁRNÍ ROZKLAD A PSEUDOINVERZE e je regulární a má tedy inverzní matici Σ e −1 , přičemž Matice Σ  1/σ1 0 ...    0 1/σ 2 ... e −1 = diag 1 , 1 , . . . , 1 =  Σ  .. .. .. σ1 σ2 σr  . . . 0 0 ... vidíme, že (4.35)

e = c1 /σ1 , c2 /σ2 , . . . , cr /σr y


T

0 0 .. . 1/σr

    

.

Vektor c, který v předchozím vystupoval ve vyjádření řešení úlohy o nejmenších čtvercích má tvar  ∗     ∗  e ∗  e b e c U U e U3 c = U∗ b = U b = = = , d U∗3 U∗3 b

kde jsme označili d = U∗3 b. Je-li

y=



e y 0



∈ Cn

(k vektoru y ∈ Cr jsme přidali n − r nulových složek), pak    y e e y. e V2 x = Vy = V = Ve 0

e má tvar (4.35), podle poznámky 4.4.15 je vektor x řešení modifikované úlohy Jelikož y o nejmenších čtvercích. Platí tedy následující tvrzení.

eΣ eV e ∗ je 4.4.17 Věta. Buď m ≥ n, A ∈ Cm×n nenulová matice, b ∈ Cm. Nechť A = U kondenzovaný singulární rozklad A, Potom vektor (4.36)

e ∗ b, e c=U

−1

e e=Σ y

e c.

ey = V eΣ e −1e eΣ e −1 U e ∗b x = Ve c=V

je řešení modifikované úlohy o nejmenších čtvercích pro A, b. e U3 , V, V, e V2 , Σ, Σ e značí totéž, co v poznámce 4.4.16. 4.4.18 Poznámka. Nechť A, U, U, Kromě jiného je A = UΣV∗ . Nechť (4.37)

Σ† =

e −1 0 Σ 0 0

!

, 151

KAPITOLA 4. MATICOVÉ ROZKLADY kde 0 značí nulové matice takových typů, že Σ† ∈ Rn×m — zdůrazněme, že zatímco Σ je typu m × n, matice Σ† je typu n × m. Položme A† = VΣ† U∗

(4.38) a podívejme se na součin A† b. Je †

†

∗

A b = VΣ U b = =



e V2 V





e V2 V

e −1 U e∗ Σ 0



!

e −1 0 Σ 0 0

!

e∗ U U∗3



b=

eΣ e −1 U e ∗ b. b=V

Podle věty 4.4.17 to znamená, že vektor A† b je řešení modifikované úlohy o nejmenších čtvercích pro A, b. Matice A† definovaná rovností (4.38) se nazývá pseudoinverzní matice k A nebo podrobněji Moore-Penroseova pseudoinverzní matice k matici A. Zatímco A ∈ Cm×n , je A† ∈ Cn×m . Poznamenejme, že právě uvedená definice pseudoinverzní matice zatím není korektní. Víme, že matice U, V v singulárním rozkladu A = UΣV∗ nejsou určeny jednoznačně, takže není jasné, zda matice A† je určena jednoznačně. Jednoznačnost, a tedy korektnost definice pseudoinverzní matice A† , dokážeme později. Zatím formulujme tvrzení, které jsme právě dokázali. 4.4.19 Věta. Buď m ≥ n, A ∈ Cm×n nenulová matice, A† příslušná pseudoinverzní matice definovaná rovností (4.38), b ∈ Cm . Potom vektor x = A† b je řešení modifikované úlohy o nejmenších čtvercích pro A, b. 4.4.20 Poznámka. Je-li A ∈ Cn×n regulární matice, b ∈ Cn , pak soustava Ax = b má právě jedno řešení. Víme, že toto řešení můžeme napsat ve tvaru x = A−1 b, kde A−1 je matice inverzní k A. V tomto smyslu je pojem pseudoinverzní matice zobecněním pojmu matice inverzní, neboť A† b je řešením modifikované úlohy o nejmenších čtvercích pro A, b (rozmyslete si, jak vypadá řešení této úlohy v případě, že A je čtvercová a regulární). Přímo z definice A† můžeme vidět, že v případě A čtvercové regulární je A† = A−1 . e Buď tedy A ∈ Cn×n regulární, A = UΣV∗ je singulární rozklad A. Potom je ale Σ = Σ (všechna singulární čísla A jsou nenulová a Σ je čtvercová) a např. AA† = (UΣV∗ )(VΣ−1 U∗ ) = UΣΣ−1 U∗ = UU∗ = E,

tj. opravdu A† = A−1 . Dokažme následující tvrzení. 4.4.21 Věta. Buď A ∈ Cm×n nenulová matice (m ≥ n), A† příslušná pseudoinverzní matice [definovaná rovností (4.38)]. Potom (i) AA† A = A, 152

4.4. SINGULÁRNÍ ROZKLAD A PSEUDOINVERZE (ii) A† AA† = A† ,
∗ (iii) AA† = AA† ,
∗ (iv) A† A = A† A.

Důkaz. Nechť hod A = r (podle předpokladu je r > 0) a nechť A = UΣV∗ je singulární rozklad A, kde   e 0 Σ e = diag[σ1 , σ2 , . . . , σr ] ∈ Rr×r . Σ= ∈ Rm×n , Σ 0 0

Je-li dále

Σ† =

e −1 0 Σ 0 0

!

∈ Rn×m ,

pak podle definice je A† = VΣ† U∗ . Všimněme si, že je !     −1 e e E 0 Σ 0 Σ 0 † (4.39) ΣΣ = = ∈ Rm×m , 0 0 0 0 0 0

kde E značí jednotkovou matici řádu r. Dále      e 0 e 0 E 0 Σ Σ † ΣΣ Σ = = = Σ. 0 0 0 0 0 0 Použijeme-li tuto rovnost, okamžitě dostáváme

AA† A = UΣV∗ VΣ† U∗ UΣV∗ = UΣΣ† ΣV∗ = UΣV∗ = A. Vidíme, že platí (i). Rovnost (ii) bychom dokázali podobně. S použitím rovnosti (4.39) spočteme   E 0 † ∗ † ∗ AA = UΣV VΣ U = U U∗ . 0 0 Jelikož prostřední matice ve výrazu napravo je reálná symetrická (čtvercová), okamžitě vidíme, že (AA† )∗ = AA† , tj. platí (iii). Podobně je vidět, že platí bod (iv).  Vlastnosti (i)–(iv) pseudoinverzní matice uvedené ve větě 4.4.21 jsou jednoduché, ale důležité. Ukazuje se, že to jsou dokonce určující vlastnosti pseudoinverzní matice. Platí totiž následující tvrzení. 4.4.22 Věta. Buď A ∈ Cm×n (m, n ∈ N). Potom existuje právě jedna matice A† ∈ ∈ Cn×m taková, že (i) AA† A = A, (ii) A† AA† = A† , 153

KAPITOLA 4. MATICOVÉ ROZKLADY (iii) AA† (iv) A† A


∗


∗

= AA† , = A† A.

Je-li A reálná, je také A† reálná. Důkaz. Uvažujme případ m ≥ n. Je-li A nulová, za matici A† volíme také nulovou matici (typu n × m). Není-li A nulová, existence matice A† , která vyhovuje bodům (i)–(iv), plyne z věty 4.4.21. Ukažme, že těmito vlastnostmi je A† určena jednoznačně. Předpokládejme, že B, C jsou dvě pseudoinverzní matice k A, tj. B, C ∈ Cn×m, ABA = A,

ACA = A,

BAB = B,

CAC = C,

∗

(AB) = AB,

(AC)∗ = AC,

(BA)∗ = BA,

(CA)∗ = CA.

Pomocí těchto rovností dostaneme postupně (čtenář nechť si rozmyslí, která z těchto rovností se v kterém okamžiku používá) B = BAB = B(AB)∗ = BB∗ A∗ = BB∗ (ACA)∗ = BB∗ A∗ (AC)∗ = BB∗ A∗ AC = = B(AB)∗ AC = BABAC = BAC = BACAC = (BA)∗ (CA)∗ C = = A∗ B∗ A∗ C∗ C = (ABA)∗ C∗ C = A∗ C∗ C = (CA)∗ C = CAC = C. Je tedy B = C a vidíme, že podmínkami (i)–(iv) je skutečně pseudoinverzní matice určena jednoznačně. Zde jsme nepoužili předpoklad m ≥ n, tj. jednoznačnost máme dokázánu i v případě m < n. Existenci bychom v případě m < n ukázali tak, že bychom A† zkostruovali pomocí singulárního rozkladu analogicky rovnosti (4.38) (podrobnosti přenecháváme čtenáři). Je-li A reálná, lze matice U, V v singulárním rozkladu volit reálné, takže podle (4.38) je A† také reálná.  4.4.23 Poznámka. Skutečnosti týkající se pseudoinverzní matice jsou hezké teoretické výsledky, zvláště ve spojitosti se skutečností, že x = A† b je řešení modifikované úlohy o nejmenších čtvercích (viz větu 4.4.19). Zdůrazněme ale, že při praktickém řešení této úlohy se ve skutečnosti pseudoinverzní matice A† nepoužívá, stejně jako se nepoužívá inverzní matice při praktickém řešení soustavy lineárních rovnic s regulární maticí. Nalezení pseudoinverzní matice je početně náročnější než řešešní úlohy o nejmenších čtvercích nějakou jinou metodou (stejně tak je méně početně náročné řešit soustavu lineárních rovnic než hledat nejprve inverzní matici). 4.4.24 Poznámka. Nakonec si všimněme, že z geometrické věty 4.4.5 o singulárním rozkladu je vidět, že pseudoinverze má jednoduchý geometrický význam. Buď A ∈ Cm×n , hod A = r > 0 (případ nulové matice není zajímavý), nenulová singulární čísla A jsou σ1 ≥ σ2 ≥ · · · ≥ σr > 0. 154

4.4. SINGULÁRNÍ ROZKLAD A PSEUDOINVERZE Podle věty 4.4.5 existuje báze v 1 , v 2 , . . . , v n prostoru Cn , báze u1 , u2 , . . . , um prostoru Cm tak že ( σi ui pro i = 1, 2, . . . , r, (4.40) Av i = 0 pro i = r + 1, . . . , n. V poznámce 4.4.6 jsme si potom uvědomili, že matice U, V v singulárním rozkladu A = = UΣV∗ můžeme dostat tak, že položíme

(4.41) U = u1 u2 . . . um , V = v1 v2 . . . vn .

Nechť A : Cn → Cm je lineární zobrazení určené maticí A, tj. pro x ∈ Cn je A(x) = Ax

(A je potom matice zobrazení A vzhledem ke standardním bázím v Cn a Cm ; pro pojem lineárního zobrazení a matice lineárního zobrazení viz odstavec 1.3). Označme P = [v 1 , v 2 , . . . , v r ],

Q = [u1 , u2 , . . . , ur ]

(připomeňme, že symbol [. . . ] značí lineární obal příslušných vektorů). Je tedy P ⊂⊂ Cn , Q ⊂⊂ Cm , dim P = dim Q = r, v 1 , v 2 , . . . , v r je báze P , u1 , u2 , . . . , ur je báze Q. Nechť A1 je restrikce zobrazení A na P , tj. A1 : P → Cm je takové zobrazení, že pro x ∈ P je A1 (x) = A(x) (= Ax). Spec. podle (4.40) je (4.42)

A1 (v i ) = σi ui

pro i = 1, 2, . . . , r.

Vidíme, že A1 : P → Q a zobrazení A1 je prosté a na (rozmyslete si). Existuje tedy inverzní zobrazení A−1 1 : Q → P , přičemž podle (4.42) je (4.43)

A−1 1 (ui ) =

1 vi σi

pro i = 1, 2, . . . , r

(ostatně těmito rovnostmi je lineární zobrazení A−1 1 : Q → P jednoznačně určeno — rozmyslete si). K restrikci A na P tedy existuje inverzní zobrazení definované na Q. K samotnému zobrazení A ale inverzní zobrazení obecně neexistuje (zvláště pokud m 6= n nebo i v případě m = n není-li A prosté). Nabízí se však definovat lineární zobrazení A† : Cm → Cn tak, že položíme ( 1 v i pro i = 1, 2, . . . , r, (4.44) A† (ui ) = σi 0 prp i = r + 1, . . . , m. Jelikož u1 , u2 , . . . , um je báze Cm , je rovnostmi (4.44) a podmínkou linearity zobrazení A† jednoznačně určeno (rozmyslete si). Přitom podle (4.43) je restrikce A† na Q rovna zob† razení A−1 1 . Zobrazení A můžeme nazývat pseudoinverzní zobrazení k zobrazení A. 155

KAPITOLA 4. MATICOVÉ ROZKLADY Zbývá si uvědomit, že matice zobrazení A† vzhledem ke standardním bázím v Cm a Cn je rovna právě pseudoinverzní matici A† = VΣ† U∗ , kde U, V mají tvar (4.41) [a Σ† je konstruována stejně jako v poznámce 4.4.18 — viz rovnost (4.37)]. Rovnost A† = VΣ† U∗ je ekvivalentní rovnosti (4.45)

A† U = VΣ† .

Je-li A† matice zobrazení A† , pro každé y ∈ Cm je A† y = A† (y) a podle (4.44) spec. ( 1 vi pro i = 1, 2, . . . , r, † A ui = σi 0 pro i = r + 1, . . . , m. Odtud můžeme dokázat rovnost (4.45) přesně stejně jako jsme v poznámce 4.4.6 dokazovali rovnost (4.16), tj. rovnost AV = UΣ. Podrobnosti přenecháváme čtenáři.

156

Literatura [1] J. W. Demmel: Applied Numerical Linear Algebra, SIAM 1997. [2] M. Dont: Elementy numerické lineární algebry, Vydavatelství ČVUT, Praha 2004. [3] R. A. Horn, C. R. Johnson: Matrix Analysis, Cambridge Univ. Press 1999. [4] E. Krajník: Základy maticového počtu, Vydavatelství ČVUT, Praha 2006. [5] C. D. Meyer: Matrix Analysis and Applied Linear Algebra, SIAM 2000. [6] P. Olšák: Úvod do algebry, zejména lineární, FEL ČVUT, Praha 2007. [7] L. N. Trefethen, D. Bau: Numerical Linear Algebra, SIAM 1997. [8] D. S. Watkins: Fundamentals of Matrix Computations, Wiley-Interscience 2002. [9] F. Zhang: Matrix Theory, Basic Results and Techniques, Springer-Verlag 1999.

157

Rejstřík algebra matic, 7 báze, 5 doplnění na, 6 ortonormální, 34, 37, 42 standardní, 6 výběr, 6 čísla singulární, 137 Z, 1 C, 1 N, 1 R, 1 číslo vlastní (charakteristické), 44 DFT, 115 diagonála matice, 9 diferenciální rovnice, 44, 50, 57, 64, 76, 86 dimenze, 6 fázový polynom, 116 FFT, 117 forma kvadratická, 122 Fourierova transformace diskrétní, 115 zpětná, 116 rychlá, 117 fundamentální systém řešení, 57 Geršgorinova věta, 51 Geršgorinovy kruhy, 51 Grammova-Schmidtova ortogonalizace, 35 hodnost matice, 15 plná, 15 158

charakteristická rovnice, 48 charakteristický polynom, 47 Choleského faktor, 131 rozklad, 131 izometrie, 41 lineární, 41, 43 izomorfismus, 23 souřadnicový, 23 kvadratická forma, 122 lineární kombinace, 2 netriviální, 2 nulová, 3 triviální, 2 lineární obal, 3 lineární operátor, 22 lineární podprostor, 4 lineární prostor komplexní, 2 reálný, 2 matice, 8 adjungovaná, 11 bloková, 17 blokově diagonální, 20, 73 blokově trojúhelníková, 20 číselná, 8 čtvercové, 9 definitní, 120 diagonalizovatelná, 71, 76 ortogonálně, 93 unitárně, 93 diagonálně dominantní, 52, 124 diagonální, 9 Fourierova, 115

REJSTŘÍK hermitovská, 11, 38, 91 hlavní minor, 125 hodnost, 15 indefinitní, 120 inverzní, 16 jednoduchá, 57, 70 jednotková, 10 komplexní, 8 konjugovaná, 11 kvazidiagonální, 20 normální, 97, 134 odmocnina, 126 ortogonálně diagonalizovatelná, 93 ortonormální, 38, 40, 41 permutační, 118, 129 plné hodnosti, 15, 146 podobné, 27, 70 prvek, 8 diagonální, 9 přechodu, 26, 42 pseudodiagonální, 137 pseudoinverzní, 152 reálná, 8 regulární, 15 řád, 9 semidefinitní, 120 soustavy, 29 rozšířená, 30 symetrická, 10, 91 transformační, 27 transponovaná, 10 trojúhelníková, 9 dolní, 9 horní, 9 typ, 8 unitárně diagonalizovatelná, 93 unitárně diagonizovatelná, 132 unitárně podobné, 43, 132 unitární, 38, 40–42, 91 matice zobrazení, 24 minor, 125 násobení matice maticí, 11 skalárem, 11 vektorem, 12

násobnost vlastního čísla algebraická, 48, 53, 57 geometrická, 47, 53, 57 nejmenší čtverce, 145 nerovnost Schwarzova, 33 trojúhelníková, 33 norma vektoru, 33 normální rovnice, 146 obraz množiny, 22 odmocnina matice, 126 operátor lineární, 22 ortogonalizace Grammova-Schmidtova, 35 otočení v rovině, 106 permutační matice, 118 podobnost matic, 27 podprostor, 4 charakteristický, 47 triviální, 5 vlastní, 5 polynom fázový, 116 Rn , 1 Cn , 1 reflexe, 105 rozklad spektrální, 93 rozklad matice, 128 Choleského, 130, 132 LU, 128 polární, 144 QR, 131 Schurův, 132 singulární, 137 kondenzovaný, 144, 150 redukovaný, 143 úplný, 142 spektrální, 135 rychlá Fourierova transformace, 117 sčítání matic, 11 singulární čísla, 137 skalár, 2 159

REJSTŘÍK skalární součin, 32 součin skalární, 32 standardní, 32 součin matic, 11 blokový, 19 vlastnosti, 13 součin zobrazení, 24 souřadnice vektoru, 7 souřadnicový izomorfismus, 23 vektor, 7 soustava lineární, 29 homogenní, 29 nehomogenní, 29 reálná, 29 normálních rovnic, 146 spektrální rozklad, 93 spektrum matice, 44 stopa matice, 49, 70 SVD, 137 geometrický tvar, 139 Sylvestrovo kritérium, 124 transpozice matice, 10 vektoru, 2 úloha o nejmenších čtvercích, 132, 145 modifikovaná, 149 vektor nulový, 2 souřadnic, 7 vlastní (charakteristický), 44 vektorová funkce, 45 vektory, 1 algebraické, 1 složka, 2 generující podprostor, 5 komplexní, 1 lineárně nezávislé, 3 lineárně závislé, 3 operace, 2 ortogonální, 33 160

ortonormální, 33, 40 reálné, 1 sloupcové, 1 vnější součin, 12 vzor množiny, 22 zobrazení, 21 aditivní, 22 homogenní, 22 identické, 24 inverzní, 23 izometrické, 41 izomorfní, 23 lineární, 22 na, 22 prosté, 22 pseudoinverzní, 155 složené, 24 vzájemně jednoznačné, 22