TEORIE MATIC Tomáš Vondra
2
Obsah 1 Opakování 1.1 Základní operace s maticemi . . . 1.2 Determinant matice . . . . . . . 1.2.1 Cauchyův-Binedův vzorec 1.3 Stopa matice . . . . . . . . . . . 2 Podobnost matic, Jordanův tvar
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
5 5 7 7 7 9
3 Pozitivní matice a Frobeniova věta 29 3.1 Nezáporné pozitivní matice . . . . . . . . . . . . . . . . . . . . . 29 3.2 Nezáporné matice . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 4 Metoda sdružených gradientů 33 4.1 Metoda největšího spádu . . . . . . . . . . . . . . . . . . . . . . . 34 4.2 Metoda sdružených gradientů . . . . . . . . . . . . . . . . . . . . 36 4.3 Předpodmínění . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 5 Normy matic
41
3
4
OBSAH
Kapitola 1
Opakování Definice 1.1. Matice je soubor m × n čísel uspořádaných do m řádků a n sloupců. a11 a12 · · · a1n a21 a22 · · · a2n A= (1.1) .. .. ... . . am1 am2 · · · amn Přitom aik jsou reálná nebo komplexní čísla. Pro m = 1 resp. n = 1 se jedná o řádkový resp. sloupcový vektor a pro m = n se jedná o čtvercovou matici. Pokud aik = a, potom se jedná o konstantní matici, pro aik = 0, jedná se o matici nulovou a pro aik = δik se jedná o matici jednotkovou (značíme E nebo I). Definice 1.2. Mějme matici A = (aik ). Vyberme podmnožinu M = {i1 , . . . , ir } z množiny řádkových indexů {1, . . . , m} a dále podmnožinu N = {k1 , . . . , ks } z množiny sloupcových indexů {1, . . . , n}. Potom matici ai1 k1 · · · ai1 ks .. A(M, N ) = ... (1.2) . air k1
···
air ks
nazýváme podmaticí A (specielně pro po sobě jdoucí indexy se jedná o blok). Definice 1.3. Pokud je A čtvercová matice, potom podmatici A(M, M ) nazýváme hlavní podmaticí.
1.1
Základní operace s maticemi
1. sčítání - matice musí mít stejné dimenze, potom (∀i, j)(cij = aij + bij ) 2. násobení číslem - α · A = (αaij )i∈m,j∈n 5
6
KAPITOLA 1. OPAKOVÁNÍ 3. násobení matic - C = A · B pokud A má dimenzi (m, n) a B má dimenzi (r, s) a r = n Pro násobení matic platí následující vlastnosti: 1. není komutativní A · B 6= B · A 2. je asociativní A · (B · C) = (A · B) · C 3. je distributivní A · (B + C) = A · B + A · C 4. existuje matice E tak že E · A = A 5. existuje nulová matice Θ tak, že Θ · A = A · Θ = Θ
Čtvercové matice s operací + tvoří grupu, ale čtvercové matice s operací · grupu netvoří (musíme vyhodit singulární matice). Definice 1.4. Řekneme, že matice A je regulární právě když existuje matice B tak, že B·A=A·B 1. regulární matice - det(A) 6= 0, h(a) = n 2. singulární matice - det(A) = 0, h(a) < n, tj. (∃x 6= θ)(Ax = θ) Definice 1.5. Nechť matice A je matice typu m×n, pak hodnost soustavy všech řádkových vektorů je rovna hodnosti soustavy všech sloupcových vektorů. Toto číslo se nazývá hodnost matice h(A). Mezi ”důležité” regulární matice patří například 1. jednotková matice a její nenulové násobky 2. diagonální matice s aii 6= 0 3. trojúhelníková matice s aii 6= 0 4. permutační matice 5. Vandermontova matice 6. exp(A) (pro všechna A) Přičemž Vandermondova matice je pro ai 6= aj pro i 6= j definována takto a0 a1 a2 · · · an−1 1 1 1 1 n−1 a02 a12 a22 · · · a2 . (1.3) .. . . . a0n a1n a2n · · · an−1 n Regulární čtvercové matice s operací · tvoří grupu a diagonální regulární čtvercové matice tvoří podgrupu. Platí že (M, +, ·) je těleso právě tehdy když: 1. (M, +) je grupa 2. (M \ {0}, ·) je grupa
1.2. DETERMINANT MATICE
1.2
7
Determinant matice
Definice 1.6. Nechť A je čtvercová matice řádu n a p je permutace množiny n ˆ . Potom determinant matice A definujeme takto: X det(A) = σ(p) · a1p(1) · a2p(2) · · · anp(n) (1.4) p
(tj. sumace přes všechny permutace množiny n ˆ ).
1.2.1
Cauchyův-Binedův vzorec
Mějme matice A(m, n), B(n, m), n ≥ m. Potom platí det(A · B) =
X
det(A(M, Ni )) · det(B(Ni , M ))
(1.5)
Ni
kde M = {1, . . . , n} a Ni je množina m čísel.
1.3
Stopa matice
Definice 1.7. Nechť A je čtvercová matice řádu n. Pak číslo stopou matice a značíme st(A), resp. Sp(A) nebo Tr(A).
Pn
i=1
aii nazýváme
Tvrzení 1.8. Nechť jsou matice A, B čtvercové. Potom 1. Tr(AB) = Tr(BA). 2. Tr(ABC) = Tr(CAB) = Tr(BCA) Příklad 1.9. Rozhodněte, zda platí: Tr(ABC) = Tr(CBA) Řešení Aby měly úvahy vůbec nějaký smysl, musí odpovídat rozměry matic, tj. a11 .. A·B·C= .
···
a1n b11 .. .. · . .
···
b1r c11 .. .. · . .
···
c1k .. .
an1
···
ann
···
brr
ck1
···
ckk
br1
takže nutně n = r, r = k. Stejně také c11 . C · B · A = ..
···
c1k b11 .. .. · . .
···
b1r a11 .. .. · . .
···
a1n .. .
ck1
···
ckk
···
brr
···
ann
br1
an1
8
KAPITOLA 1. OPAKOVÁNÍ
a tedy nutně n = r, r = k. Aby tedy oba výrazy ABC, CBA měly smysl, musí platit n = r = k. Podívejme se nyní na součiny podrobněji. Po provedení násobení dostaneme n X n X A·B·C= (aij bjk ckl ) k=1 j=1
C·B·A=
n X n X
il
! (apt bsp crs )
p=1 s=1
rt
Potom tedy ale platí Tr(A · B · C) =
n X n X n X
(aij bjk cki )
i=1 k=1 j=1
Tr(C · B · A) =
n X n X n X
(apr bsp crs )
r=1 p=1 s=1
Avšak tyto dva výrazy se obecně nemusí rovnat (stačí si všimnout, které indexy se vždy rovnají v prvním a ne v druhém výrazu). Podívejme se například na matice řádu 2. a11 a12 b11 b12 c11 c12 A= , B= , C= a21 a22 b21 b22 c21 c22 Tr(A · B · C) = a11 b11 c11 + a12 b21 c11 + a11 b12 c21 + a12 b22 c21 + a21 b11 c12 + +a22 b21 c12 + a21 b12 c22 + a22 b22 c22 Tr(C · B · A) = a11 b11 c11 + a11 b21 c12 + a21 b12 c11 + a21 b22 c12 + a12 b11 c21 + +a12 b21 c22 + a22 b12 c21 + a22 b22 c22
Kapitola 2
Podobnost matic, Jordanův tvar Mějme vektorový prostor Vn . Nechť x ∈ Vn a = {e1 , e2 , . . . , en } je báze ve Vn . Potom x značíme reprezentaci x v bázi (obecně platí x = · x . Nechť nyní e je jiná báze Vn . Potom existuje matice P (tzv. matice přechodu) taková, že X eej = Pij ei (2.1) i
x = · x = e · xe = · P · xe
(2.2)
x = P · xe
(2.3)
Nechť A je čtvercová matice a nechť φ je lineární zobrazení definované takto: X φ(ej ) = aij · ei (2.4) i
tj. φ() = · A
(2.5)
φ(x) = φ( · x ) = · A · x
(2.6)
φ(x) = A · x
(2.7)
P · φ(x)e = A · P · xe
(2.8)
φ(x)e = [P−1 · A · P]
(2.9)
Potom
Definice 2.1. Řekneme, že čtvercová matice B řádu n je podobná matici A pokud existuje regulární matice P taková, že platí B = P−1 · A · P. 9
10
KAPITOLA 2. PODOBNOST MATIC, JORDANŮV TVAR
Příklad 2.2. Nechť B=
0 0
0 2
A=
1 1
1 1
P=
1 −1
1 1
Ověřte, že B = P−1 · A · P Řešení B = P−1 · A · P ⇔ P · B = A · P 0 2 0 2 P·B= A·P= 0 2 0 2 takže tvrzení platí. Věta 2.3. Nechť platí, že matice B je podobná matici A (tj. A ∼ B). Pak 1. det(B) = det(A) 2. Tr(A) = Tr(B) Důkaz 1. det(B) = det(P−1 · A · P) = det(P−1 ) · det(A) · det(P) = det(A) 2. Tr(A) =
X
aii
i
Tr(B) = Tr(P−1 · A · P) =
XX i
=
X j,k
ajk
X
P−1 ij Pki
=
i
X
P−1 ij · ajk · Pki =
j,k
ajk δjk =
jk
X j
Věta 2.4. Podobnost je: 1. reflexivní (A ∼ A, protože A ∼ E−1 · A · E) 2. symetrická (A ∼ B ⇒ B ∼ A) 3. tranzitivní (A ∼ B ∧ B ∼ C ⇒ A ∼ C) Důkaz 1. zřejmé 2. zřejmé 3. A ∼ B ⇒ B = P−1 · A · P B ∼ C ⇒ C = Q−1 · A · Q takže C = (Q−1 · P−1 ) · A · (P · Q)
ajj
11 Označme [A] třídu matic, které jsou podobné A a [B] třídu matic podobných B. Potom nutně [A] = [B], nebo [A] ∩ [B] = ∅ (plyne triviálně z tranzitivnosti relace podobnosti). Mohli bychom se zeptat, zda je matice A podobná nějaké diagonální matici, tj. zda do [A] nějaká diagonální matice patří. Odpověď na tuto otázku zní ”ne vždy”. Existuje nicméně poměrně obecný tvar matice, tzv. matice Jordanova, a platí že ke každé matici A existuje Jordanova matice J tak, že A ∼ J. Jordanova matice je blokově diagonální, a její obecný tvar je
J1
0
J2
J3 ..
.
0
(2.10)
Jk
kde
λ
Js =
1 λ
1 λ
..
.
..
.
1
(2.11)
λ Definice 2.5. Řekneme, že x 6= 0 je vlastním vektorem matice A, pokud existuje číslo λ takové, že Ax = λx. Číslo λ nazýváme vlastním číslem příslušným vektoru x. Vraťme se nyní k otázce, kdy je matice A podobná diagonální matici Λ. Dle definice by muselo platit Λ = P−1 · A · P tj. P · Λ = A · P a matice Λ by musela mít tvar Λ=
λ1
λ2
λk
Označme k-tý sloupec matice P jako pk a vyjádřeme rovnost PΛ = AP podrobněji. λ1 λ2 = ( λ 1 p1 , λ 2 p 2 , . . . , λ k p k ) PΛ = ( p1 , p2 , . . . , pk ) .. . λk AP = ( Ap1 , Ap2 , . . . , Apk )
12
KAPITOLA 2. PODOBNOST MATIC, JORDANŮV TVAR
takže nutně Apj = λj pj To však znamená, že jsme našli jak všechna vlastní čísla matice A, totiž soubor (λ1 , . . . , λk ), tak i všechny vlastní vektory (p1 , . . . , pk ). Poznámka 2.6. Pokud je A podobná nějaké diagonální matici Λ, konkrétně A = P−1 ΛP, potom se na diagonále matice Λ vyskytují vlastní čísla matice A a matici P tvoří odpovídajícím způsobem setříděné vlastní vektory matice A. Věta 2.7. Nechť A je čtvercová matice řádu n. Potom číslo λ je vlastním číslem matice A právě tehdy, když je kořenem polynomu det(A−λ·E). Polynom P (λ) = det(A − λ · E) nazýváme charakteristickým polynomem matice A. Důkaz ⇒ Matice A−λ·E je podle předpokladu singulární, takže det(A−λ·E) = 0 Existuje tedy nenulový vektor x takový, že Ax = λx, tj. (A−λE)x = 0. ⇐ Dle předpokladu det(A−λ·E) = 0, takže matice A−λ·E je singulární. Existuje tedy nenulový vektor x takový, že Ax = λx. Příklad 2.8. Nechť
A=
Potom
det
1−λ 2
2 −2 − λ
1−λ 2
1 2
2 −2
2 −2 − λ
= (1 − λ)(−2 − λ) − 4 = −2 + λ + λ2 − 4 =
= (λ + 3)(λ − 2) = 0 ⇔ λ ∈ {−3; 2} Matice A je tedy podobná matici B=
−3 0
0 2
a platí Tr(A) = Tr(B) = −1. Spočtěme ještě vlastní vektory matice A: −1 λ = −3 ⇔ (A + 3E)x = θ ⇔ x = 2 λ = 2 ⇔ (A − 2E)x = θ ⇔ x =
2 1
Věta 2.9. Nechť A ∼ B, pak charakteristický polynom matice A je roven charakteristickému polynomu matice B.
13 Důkaz det(B − λE) = det(P−1 · AP − λE) = det(P−1 · AP − λP−1 · E · P) = = det[P−1 (A − λE)P] = det(A − λE) Poznámka 2.10. I když jsou pro pobodné matice vlastní čísla stejná, vektory stejné být nemusí! Příklad 2.11. Nechť A ∼ B, a nechť λ je jejich vlastní číslo. Dále nechť Ax = λx a B˜ x = λ˜ x. Potom B˜ x = P−1 AP˜ x = λ˜ x AP˜ x = λP˜ x a tudíž x = P˜ x. 1. Každá matice má alespoň jedno vlastní číslo a nejvýše n vlastních čísel (v oboru C). 2. Pokud uvažujeme násobnost vlastních čísel, pak je jich právě n. 3. V Jordanově tvaru má matice na diagonále všechna vlastní čísla, přičemž každé právě tolikrát, kolik je jeho násobnost. Pro trojúhelníkovou matici platí, že determinant je roven součinu prvků na diagonále, takže: det(J − λE) = (λ1 − λ)k1 (λ2 − λ)k2 . . . kde ki je násobnost λi . Tvrzení 2.12. Vlastní vektory příslušné různým vlastním číslům jsou lineárně nezávislé. (důkaz indukcí) Definice 2.13. Nechť A je čtvercová matice, a nechť λ je její vlastní číslo. Potom charakteristickým podprostorem příslušným k vlastnímu číslu λ nazýváme podprostor Nλ = {x ∈ Vn | Ax = λx} Poznámka 2.14.
1. Nλ je skutečně vektorový prostor/podprostor.
2. Nλ je invariantní vzhledem k násobení vektorů maticí A. Příklad 2.15.
1.
7 A = 0 0
0 7 0
0 0 7
má jedno trojnásobné vlastní číslo λ = 7, takže (A − λE) = Θ dim(N7 ) = 3, N7 = [(1, 0, 0), (0, 1, 0), (0, 0, 1)]λ
14
KAPITOLA 2. PODOBNOST MATIC, JORDANŮV TVAR 2.
7 A = 0 0
1 7 0
má jedno trojnásobné vlastní číslo λ = 7, 0 (A − λE) = 0 0
0 0 7 takže 1 0 0
0 0 0
dim(N7 ) = 2, N7 = [(1, 0, 0), (0, 0, 1)]λ 3.
7 A = 0 0
1 7 0
má jedno trojnásobné vlastní číslo λ = 7, 0 (A − λE) = 0 0
0 1 7 takže 1 0 0
0 1 0
dim(N7 ) = 1, N7 = [(1, 0, 0)]λ Věta 2.16. Nechť A je čtvercová řádu n. Potom dimenze prostoru Nλ je nejvýše rovna násobnosti čísla λ jakožto kořene charakteristivkého polynomu matice A. Poznámka 2.17.
1. Pokud λ je vlastní číslo matice A, potom dim(Nλ ) ≥ 1.
2. Každá metice je podobná nějaké Jordanově matici, ale nemusí být podobná nějaké matici diagonální. Věta 2.18. Nechť A je čtvercová matice řádu n. Pak následující výroky jsou ekvivalentní: 1. A je podobná diagonální matici 2. V prostoru Cn existuje báze λ vlastních vektorů matice A. 3. Pro každé λ je dim(Nλ ) rovna násobnosti λ jakožto kořene charakteristického polynomu. Důkaz Platí A ∼ Λ, potom tedy (1) ⇔ (2), protože Λ = P−1 · A · P P·Λ=A·P a P je tvořena z vlastních vektorů matice A (viz výše). Protože P je regulární matice, jsou její sloupce LN, a tvoří tedy bázi prostoru Cn .
15 (2) ⇒ (3): Označme jako nj násobnost vlastního čísla λj , dim(Nλj ) označme jako n fj , a h(A) jako n. Víme, že existuje báze z vlastních vektorů matice A, takže k X n fj = n j=1
a nj ≤ n fj (viz. předchozí věta). Potom ale nutně nj = n fj (3) ⇐ (2): Nechť x je vlastní vektor příslušný k λ. V každém Nλ vytvoříme bázi, čímž dostaneme n LN vektorů, které jsou navíc vlastními vektory. Tím jsme však důkaz dokončili. Poznámka 2.19. Postup pro vytvoření Λ a P pokud A ∼ Λ, kde Λ je diagonální matice 1. Nalezneme charakteristický polynom a jeho kořeny (i s násobnostmi). 2. Ověříme, zda jde dim(Nλ ) rovna násobnosti vlastního čísla λ jako kořene polynomu (tj. hledáme řešení (A − λE)x = θ, x 6= θ 3. Vytvoříme Λ a P. Poznámka 2.20. dim(Nλ ) = k ⇔ h(A − λE) = n − k Věta 2.21. Nechť A je řádu n a nechť charakteristický polynom matice A má n různých kořenů. Pak A je podobná diagonální matici. Důkaz(triviálně) Existuje n LN vlastních vektorů a n různých vlastních čísel. Z konstrukce matic Λ a P je diagonálnost matice zřejmá. Definice 2.22. Nechť A je řádu n a nechť λ je její vlastní číslo. Konečnou posloupnost různých vektorů a1 , a2 , . . . , ak nazveme řetězcem příslušným k vlastnímu číslu λ, pokud platí (A − λE)a1 = 0 (A − λE)ak = ak−1 pro k > 1 Příklad 2.23. Nechť 7 0 0
1 7 0
0 0 1 ⇒ (A − λE) = 0 0 7
1 0 0
0 1 0
potom vektory 0 p1 = 0 1 tvoří řetězec délky 3
0 p2 = 1 0
1 p3 = 0 0
16
KAPITOLA 2. PODOBNOST MATIC, JORDANŮV TVAR
Věta 2.24. Nechť A je čtvercová matice řádu n, a nechť p1 , . . . , pk je řetězec příslušný k vlastnímu číslu λ. Potom p1 , . . . , pk jsou LN. Důkaz(indukcí) 1. p1 je LN protože p1 6= 0 2. P sporem: Nechť je p1 , . . . , pk LZ. Potom tedy existuje netriviální kombinace k j=1 cj pj = 0. Potom ale k X (A − λE)( cj pj ) = 0 j=1
Dle předpokladu ale pro k − 1 platí, že p2 , . . . , P pk je LN, a tudíž c2 = · · · = k ck = 0. Zároveň ale musí platit c1 = 0 (aby j=1 cj pj = 0). To je však spor s existencí netriviální nulové lineární kombinace. Věta 2.25. Nechť A je čtvercová matice řádu n a nechť λ je její vlastní číslo. Pak vektor x ∈ Cn je k-tým členem řetězce příslušným k vlastnímu číslu λ právě tehdy, když platí 1. (A − λE)k x = 0 2. a přitom (A − λE)k−1 x 6= 0 Důkaz 1. ⇒ Máme řetězec p1 , . . . , pk−1 , x(= pk ). Potom (A − λE)x = pk−1 (A − λE)2 x = pk−2 (A − λE)3 x = pk−3 .. . (A − λE)k−1 x = p1 (A − λE)k x = 0
2. ⇐ Vektor x tvoří řetězec příslušný k λ, protože (A − λE)k−1 x, (A − λE)k−2 x, . . . , (A − λE)x, x tvoří řetězec příslušný k λ. Definice 2.26. Nλk = {x ∈ Cn | (A − λE)k x = 0} Poznámka 2.27.
1. Nλ = {x ∈ Cn | (A − λE)x = 0}
17 2. W λλ ≡ Nλ1 ⊂ Nλ2 ⊂ · · · Nλk 3. Nechť p1 , . . . , pk je řetězec příslušný k λ. Potom p1 , p2 , . . . , pk ∈ Nλk p1 ∈ Nλ1 , Nλ2 , . . . , Nλk a2 ∈ Nλ2 , . . . , Nλk .. . ak ∈ Nλk Věta 2.28. Nechť A je matice řádu n a λ její vlastní číslo, které má násobnost j. Pak v prostoru Nλj existuje báze z řetězců příslušných k λ. (bez důkazu) Věta 2.29. Nechť A je matice řádu n a λ její vlastní číslo s násobností j. Potom dim(Nλj ) = j. (bez důkazu) Poznámka 2.30.
1. To neznamená, že existuje řetězec délky k!
2. LN řetězců existuje právě tolik kolik existuje LN vlastních vektorů (včetně řetězců délky 1). 3. Nechť k vlastnímu číslu λ přísluší k vlastních vektorů, a nechť dim(Nλ ) = k dim(Nλ2 ) = k + l dim(Nλ3 ) = k + l + m .. . přičemž nutně musí platit (l ≤ k). Potom l řetězců má délku alespoň 2, m řetězců má délku alepoň 3, atd. 4. Nechť má vlastní číslo λ násobnost k. Potom v prostoru Nλk existuje báze z řetězců příslušných k λ, takže dim(Nλk ) = k. Věta 2.31. Nechť A je matice řádu n a λ1 , λ2 , . . . , λk její vlastní čísla s násobnostmi j1 , . . . , jk . Potom Cn = Nλj11 ⊕ Nλj22 ⊕ . . . ⊕ Nλjkk Důkaz Důkaz je důsledkem předchozích tvrzení. Stačí pouze dokázat, že řetězce příslušné k různým vlastním číslům jsou LN. Poznámka 2.32. 1. Počet řetězců, které tvoří bázi v Nλj je roven dim(Nλj ) (neboli počtu LN vlastních vektorů příslušných k λ).
18
KAPITOLA 2. PODOBNOST MATIC, JORDANŮV TVAR 2. Počet řetězců, které mají délku ≥ 2 je dim(Nλ2 ) − dim(Nλ1 ). 3. Počet řetězců s délkou ≥ 3 je dim(Nλ3 ) − dim(Nλ2 ). 4. Nechť λ je vlastní číslo matice A a nechť j je jeho násobnost. Pokud dim(Nλk−1 ) 6= j a dim(Nλk ) = j, potom k je délka nejdelšího řetězce.
Věta 2.33. Jordanova věta: Nechť A je čtvercová matice řádu n. Potom A je podobná Jordanově matici JA . Matice JA je určena jednoznačně až na pořadí bloků. Přitom: 1. na diagonále každého bloku je vlastní číslo matice A 2. počet bloků, které mají na diagonále vlastní číslo λ je roven dim(Nλ ) a součet řádů těchto bloků je roven násobnosti λ jakožto kořene charakteristického polynomu. Důkaz Důkaz provedeme ve dvou krocích: (1) zkonstruujeme matice JA a Q a (2) ověříme že platí QJA = AQ 1. Nalezneme báze všech prostorů Nλj11 , . . . , Nλjkk , a z báze každého prostoru postupně vyjmeme řetězce s maximální délkou. q1 , q 2 , . . . , q k , λ ! ! Q= JA =
λ
!
q1 , q2 , . . . , qk , . . .
1 λ
!
..
.
..
.
1 λ
kde je znázorněn blok řádu k
2. Nyní tedy ověřme, že Q · JA = A · Q. Pro první sloupec A · Q dostaneme (A · Q)•1 = A · Q•1 ale zároveň víme, že matice Q se skládá z vlastních vektorů matice A, takže A · q1 = λq1 . Podívejme se nyní na první sloupec matice Q · JA . Triviálně platí (čtenář si jistě rád dokáže sám. . .), že (Q · JA )•1 = λq1
19 Nyní se podívejme na další sloupce. Stejnou úvahou jako v předchozím odstavci dostaneme rovnost A · qk = λqk . Podívejme se tedy na (Q · JA )•1 : (Q · JA )•k = λqk + qk−1 přitom ale platí (A − λE)qk = qk−1 ⇒ Aqk = λqk + qk−1 takže (Q · JA )•k = Aqk Poznámka 2.34. poznámky k důkazu Jordanovy věty 1. V Cn existuje báze z řetězců. Nechť tedy {p1 , p2 , . . . , pn } je tato báze. 2. (konstrukce J, Q) Vezmeme jedno vlastní číslo λ a jemu příslušný řetězec (např. λ ∼ p1 , p2 , p3 ), do J umístíme blok odpovídající λ a do Q umístíme řetězec. λ 1 λ 1 J= λ .. .
Q = p1
p2
p3
···
poté vezmeme další vlastní číslo a příslušný řetězec a celý postup opakujeme. 3. Jednoznačnost J plyne z jednoznačnosti délek odpovídajících řetězců v bázi {p1 , . . . , pn }. 4. Jednoznačnost délek řetězců plyne z jednoznačnosti dimenzí Nλk . 5. Ukážeme JA ∼ A, tj. J = Q−1 AQ. Matice Q je regulární ({p1 , . . . , pn } je báze Cn , takže stačí ověřit QJA = AQ. To provádíme po sloupcích: (a) k-tý sloupec AQ AQ•k =
λpk λpk + pk−1
pokud je pk vektor příslušný k λ(1) pokud je pk prvkem řetězce s indexem > 1(2)
20
KAPITOLA 2. PODOBNOST MATIC, JORDANŮV TVAR (b) k-tý sloupec J pro případ (1): 0 .. . 0 λ 0 . .. 0 (λ je na k-tém řádku) (c) k-tý sloupec J pro případ (2): 0 .. . 0 1 λ 0 . .. 0 (λ je na k-tém řádku)
Příklad 2.35. Nechť má matice vlastní čísla λ1 = 7 a λ2 = 1. Nechť vlastnímu číslu 7 přísluší řetězce {q1 }, {qe1 , qe2 , qe3 } a vlastnímu číslu 1 nechť přísluší řetězce {p1 }, {pe1 }. Potom bude mít Jordanova matice J a transformační matice Q tvar J=
1
1 7 7
1 7
1 7
Q = p1
pe1
q1
qe1
qe2
qe3
Poznámka 2.36. 1. Na diagonále každého bloku Jordanovy matice JA jsou vlastní čísla matice A. 2. Počet bloků s číslem λ na diagonále je roven dim(Nλ ) 3. Dimenze bloků odpovídají délkám řetězců, které tvoří bázi v Nλk (k je násobnost λ). 4. Součet dimenzí bloků příslušných k λ je k. 5. Transformační matice Q je tvořena příslušně uspořádanými řetězci.
21 Příklad 2.37.
3 0 8 A = 3 −1 6 −2 0 −5 3 0 8 det(A) = 3 −1 6 = −(1 + λ)3 −2 0 −5
takže λ = −1 je trojnásobné vlastní číslo. Potom 4 0 8 h(A − λE) = h 3 0 6 = 1 −2 0 −4 takže vlastnímu číslu λ = −1 přísluší dva nezávislé vlastní vektory. Protože dim(Nλ ) = 2, budou Jordanovu matici tvořit dva bloky s λ = −1, a Jordanova matice tedy bude mít jeden z následujících tvarů: −1 1 0 −1 0 0 0 −1 0 0 −1 1 0 0 −1 0 0 −1 Zároveňto však znamená, že existují dva řetězce délky alespoň 1. Protože 0 0 0 (A+E)2 = 0 0 0 , platí dim(Nλ2 ) = 3, dim(Nλ2 )−dim(Nλ ) = 1, a existuje 0 0 0 tedy jeden řetězec délky alespoň 2. (Protože zřejmě dim(Nλ3 ) = 3, dim(Nλ3 ) − dim(Nλ2 ) = 0, je zřejmé že řetrězec delší než 2 neexistuje.) Hledejme nyní druhý vektor z řetězce (A + E)x 6= 0, (A + E)2 x = 0. Platí 2 2 dim(N−1 ) = 3 přičemž N−1 = {x | (A + E)2 x = 0}
Položme nyní 1 x = 0 0 potom
4 (A + E)x = 3 −2 −1 1 JA = −1
4 8 1 6 0 = 3 0 −2 −4 4 1 0 Q = 3 0 1 −1 −2 0 0 0 0 0
Hledáme tedy p tak, aby (A + E)p = 0 a aby p bylo LN s (A + E)p. Nechť tedy 0 p = 1 0
22
KAPITOLA 2. PODOBNOST MATIC, JORDANŮV TVAR
Potom
4 1 0 −1 1 Q · JA = 3 0 1 · −1 −2 0 0 −1 3 0 8 4 1 0 A · Q = 3 −1 6 · 3 0 1 −2 0 −5 −2 0 0
Klasifikace dle typu J do dim(A) = 4: 1. n = 1 A je v Jordanově tvaru 2. n = 2 (a) Existují tedy dva LN vlastní vektory (k jednomu nebo dvěma vlastním číslům). λ JA = µ (b) Existuje pouze jedno vlastní číslo, ale náleží k němu pouze jeden LN vlastní vektor. Existuje tedy řetězec délky 2. λ 1 JA = λ Nechť (A − λE)x 6= 0. Potom (A − λE)x 6= 0, x je příslušný řetězec. 3. n = 3 (a) Existují 3 LN vlastní vektory. JA =
λ µ
ν
(b) Existují 2 LN vlastní vektory. i. λ není trojnásobné vlastní číslo, takže existuje řetězec délky 2. λ 1 JA = λ µ Najdeme (A − λE)x 6= 0, potom (A − λE)x, x tvoří řetězec. K (A − λE)x naleznu LN vlastní vektor. ii. λ je trojnásobné vlastní číslo λ 1 JA = λ 1 µ najdeme (A − λE)2 6= 0, potom (A − λE)2 x = 0, (A − λE)x, x tvoří řetězec. K (A − λE)x naleznu LN vlastní vektor.
23 4. n = 4 (a) Existují 4 LN vlastní vektory.
λ
µ
JA =
ν ρ
(b) Existují 3 LN vlastní vektory.
λ
JA =
1 λ
µ ν
Obdobně jako pro 3(b). (c) Existují 2 LN vlastní vektory. Potom
λ
JA =
1 λ
µ
1 µ
(A − λE)x 6= 0, (A − λE)2 x = 0 (A − µE)y 6= 0, (A − µE)2 y = 0 (d) JA =
λ
1 λ
λ
1 λ
(A − λE)x 6= 0, (A − λE)2 x = 0 (A − λE)y 6= 0, (A − λE)2 y = 0 a máme dva řetězce (A−λE)x, x, (A−λE)y, y. Tento postup však není optimální, protože pro x 6= y může nastat (A − λE)x = (A − λE)y. Najděme tedy dva LN vlastní vektory p1 , q1 . V principu bychom mohli řešit soustavy (A − λE)p2 = p1 (A − λE)q2 = q1 Soustavy sice nejsou ”příjemné”, tato cesta k cíli vede, nicméně existuje jednodušší řešení. Doplňme vektory p1 , q1 do báze v prostoru C4 , čímž dostaneme {v1 , v2 , p1 , q1 } a vytvořme řetězce (A−λE)v1 , v1 , (A − λE)v2 , v2 . Tyto vektory jsou LN.
24
KAPITOLA 2. PODOBNOST MATIC, JORDANŮV TVAR (e) Existuje řetězec délky 3.
λ
JA =
1 λ
1 λ
µ
Najdeme (A − λE)2 x 6= 0. Potom (A − λE)2 x, (A − λE)x, x tvoří řetězec. Musíme ale ověřit, že (A − λE)3 x = 0. (f)
λ
JA =
1 λ
1 λ
µ
(A − λE)2 6= Θ dim(Nλ1 ) = 2 dim(Nλ2 ) = 3 dim(Nλ3 ) = 4 takže h((A − λE)2 ) = 4 − 3 = 1 Potom (A − λE)2 x, (A − λE)x, x je řetězec a stačí nám najít ještě jeden LN vektor. (g) JA =
λ
1 λ
1 λ
1 µ
(A − λE)4 = Θ (A − λE)3 6= Θ Potom (A − λE)3 x, (A − λE)2 x, (A − λE)x, x je řetězec délky 4. Poznámka 2.38. Toto vše jsme řešili v C. Jestliže je A reálná, a λ je její ¯ také vlastní číslo matice A. Nechť vlastní číslo, které reálné není, potom je i λ q1 , q2 , . . . , qk je řetězec příslušný k λ, potom řetězec q¯1 , q¯2 , . . . , q¯k je LN a přísluší ¯ k λ. Nechť A je čtvercová matice řádu n, a nechť A ∼ D, kde √ D je diagonální matice. Hledejme nyní matici B takovou, že B2 = A (ozn. B = A). Víme, že A = Q−1 · D · Q
25 kde
λ1 λ2
D= √ √
Potom ale
√
..
·
√
. λk
λ1
√
D=
−1
A∼Q
λ2 ..
.
√
λk
D · Q. Nechť nyní f (x) =
∞ X
ak xk
k=0
f (A) =
∞ X
ak Ak
k=0
Potom platí f (A) =
∞ X
" ak (Q−1 · D · Q)k = Q−1
∞ X
# ak Dk Q
k=0
k=0
Zároveň platí λk 1
Dk =
λk2 ..
. λkn
Odtud ale plyne, že P∞
k=0
f (A) = Q−1
ak λk1
P∞
k=0
ak λk2 ..
Q
. P∞
k=0
ak λkn
tj. f (λ ) 1 f (λ2 ) f (A) = Q−1
..
Q
. f (λn )
Pro Jordanovu matici triviálně platí λ 1 λ Jn (λ) =
..
.
..
.
1 λ
26
KAPITOLA 2. PODOBNOST MATIC, JORDANŮV TVAR
J2n (λ) =
λ2
2λ λ2
1
2λ
..
.
λ2
..
.
1
..
.
2λ λ2
a tedy Definice 2.39. Nechť A je čtvercová matice řádu n. Nechť λ je její v absolutní hodnotě největší vlastní číslo. Potom |λ| nazýváme spektrálním poloměrem matice A a označíme |λ| = ρ(A) O vztahu mezi A, f (A) a ρ(A), f (ρ(A)) pojednává následující věta. Věta 2.40. Oldenburger: Nechť A je řádu n. Potom limk→∞ Ak = 0 právě tehdy když ρ(A) < 1. Důkaz 1. ⇐ (triviálně): pokud λ < 1, potom nutně Jkn (λ) → 0 2. ⇒ sporem: stačí dokázat pro diagonální matici - pokud by λ ≥ 1, potom λk nebude konvergovat k nule (spor) Věta 2.41. Nechť A je čtvercová matice řádu n a nechť platí ρ(A) < 1. Pak řada E + A + A2 + . . . + Ak konverguje a je rovna (E − A)−1 . Důkaz 1. konvergence je zřejmá na základě předchozí věty 2. existence (E − A)−1 B je regulární ⇒ (∀i ∈ n ˆ )(λn 6= 0). Matice (E − A) má vlastní čísla ve tvaru 1 − λi , kde λi jsou vlastní čísla A, takže (∀i)(|λi | ≤ ρ(A) < 1). Potom tedy (∀i)(1 − λi 6= 0) a matice (E − A) je tedy regulární. Odtud již tedy plyne existence matice inverzní. 3. rovnost nastává právě tehdy když (E − A)−1 = E + A + A2 + . . . E = (E − A)(E + A + A2 + . . .) = E − Ak+1 A protože Ak → 0, rovnost platí. Věta 2.42. Nechť A je čtvercová matice řádu n. Potom λ je jednoduché vlastní číslo matice A právě tehdy, když
27 1. existuje jediný LN vlastní vektor v matice A příslušný vlastnímu číslu λ a jediný LN vlastní vektor u matice AT příslušný k λ 2. u · v 6= 0 Důkaz 1. ⇐ z (1) dostáváme, že v Jordanově matici existuje nejvýše jeden s λ na diagonále. Zároveň platí, že jestliže A ∼ J potom AT ∼ JT , protože J = Q−1 · A · Q ⇔ JT = QT · AT · Q − 1T Z (2) potom vyplývá, že tento blok v Jordanově matici musí mít řád 1, protože pokud λ2 1 λ2 0 T A= A = 0 λ2 1 λ2 potom 1 0 p1 = p2 = 0 1 λ2 1 Ap1 = Ap2 = = p1 + λ 2 p 2 0 λ2 a řetězec je tedy p1 , p2 . Současně ale λ2 0 A T p1 = A T p2 = 1 λ2 a řetězec je tedy p2 , p1 (tj. v opačném pořadí). Platí tedy p1 · p2 = 0. Uvažujme nyní p1 ∼ λ pro J a p2 ∼ λ pro JT . Potom platí: p1 · p2 = 0 ⇔ pokud platí jedno z následujících tvrzení (a) existuje více vlastních vektorů LN příslušných k λ (b) existuje řetězec délky > 2
28
KAPITOLA 2. PODOBNOST MATIC, JORDANŮV TVAR
Kapitola 3
Pozitivní matice a Frobeniova věta 3.1
Nezáporné pozitivní matice
Definice 3.1. Řekneme, že matice A je nezáporná (ozn. A ≥ 0), pokud pro každý prvek aij matice A platí aij ≥ 0. Definice 3.2. Řekneme, že matice A je nezáporná (ozn. A ≥ 0), pokud pro každý prvek aij matice A platí aij > 0. Poznámka 3.3. 1. Pokud jsou A, B nezáporné a stejného typu (rozměru), potom je i A + B nezáporná. 2. Pokud jsou A, B nezáporné, čtvercové, potom je i A · B nezáporná. Tvrzení 3.4. Nechť jsou x, y sloupcové vektory typu (n, 1), pro které x ≥ y ≥ 0, a nechť A je matice typu (m, n), A ≥ 0. Potom Ax ≥ Ay Pokud navíc x > y, A > 0, potom platí Ax > Ay Důkaz(triviální) Ax ≥ Ay A(x − y) ≥ 0 A ≥ 0 ∧ (x − y) ≥ 0
29
30
KAPITOLA 3. POZITIVNÍ MATICE A FROBENIOVA VĚTA
Definice 3.5. Dvě matice A = (aij ), B = (bij ) stejného typu mají stejnou strukturu nenulových prvků, pokud platí: (∀i, j)(aij 6= 0 ⇔ bij 6= 0) Definice 3.6. Booleovská matice je matice jejíž prvky jsou 0 nebo 1. Lze definovat operace sčítání, násobení číslem a násobení matic tak, že operace sčítání matic a násobení číslem se provádějí booleovsky (0+0 = 0, 0+1 = 1+0 = 1+1, 0 · 0 = 0 · 1 = 1 · 0 = 0, 1 · 1 = 1). Každé číselné matici A = (aik ) potom můžeme přiřadit booleovskou matici AB = (αik ), kde αik = 1 pro aik 6= 0 a αik = 0 pro aik = 0. Matici AB nazýváme booleovská reprezentace matice A. Věta 3.7. Struktura nenulových prvků součtu resp. součinu dvou nezáporných matic závisí jen na strukturách nenulových prvků obou sčítanců resp. činitelů. Přitom platí (pro A ≥ 0, B ≥ 0): 1. (A + B)B = AB + BB 2. (A · B)B = AB · BB (kde ovšem operace sčítání a násobení napravo jsou booleovské).
3.2
Nezáporné matice
Definice 3.8. Řekneme, že čtvercová matice A je rozložitelná, pokud má tvar A1 B 0 A2 nebo pokud ji lze na tento tvar převést simultánní permutací řádek a sloupců. Poznámka 3.9. Matice je nerozložitelná pokud není rozložitelná (překvapivě). Příklad 3.10. 0 0 0 0 0 1 0 1 0 1 0 0
0 1 0 3 a 4 0 → 1 0 0 0
0 0 0 1
0 1 0 0
1 1 a 2 0 0 → 0
0 1 0 2 a 3 1 0 0 → 0 0 1 0 0 0
0 0 0 1
0 1 0 0
0 0 0 1
1 0 1 a 2 → 0 0
0 1 0 0
Věta 3.11. Nechť je A nerozložitelná a nezáporná matice řádu n a nechť k0 , k1 , . . . , kn−1 jsou kladná čísla. Potom matice k0 E + k1 A + k2 A2 + · · · + kn−1 An−1 > 0.
3.2. NEZÁPORNÉ MATICE Příklad 3.12.
31
0 0 A= 0 1 0 1 A2 = 0 1 0 0 3 A = 1 0
0 0 1 0
1 0 0 0
1 0 0 0
0 0 0 0
0 0 0 1
0 1 0 0
0 1 0 0 0 0 1 0 1 0 0 0
A4 = E Definice 3.13. Nechť A = (aij ) je matice. Matici m(A) = (|aij |) nazveme modul matice A. Věta 3.14. Nechť A, B jsou čtvercové matice řádu n a nechť m(A) ≤ B. Potom ρ(A) ≤ ρ(B). (Specielně platí ρ(A) ≤ ρ(m(A)).) Důkaz(sporem) Nechť m(A) ≤ B a zároveň nechť ρ(A) > ρ(B). Potom nutně existuje s ∈ R tak, že ρ(A) > s > ρ(B). Definujme tedy e(A) = 1s A. Potom ale Věta 3.15. Nechť A je čtvercová a nezáporná matice, z je nezáporný vektor a nechť existuje η ∈ R takový, že Az > ηz. Potom ρ(A) > η Důkaz Nechť ρ ≥ 0, z 6= 0 a nechť existuje > 0 tak, že Az(η + ). Definujme e= A
1 A +η
Potom e>z A e > Az ≥ z A
Tvrzení 3.16. Peron: Nechť A je čtvercová kladná matice. Potom ρ(A) je vlastním číslem A a tomuto vlastnímu číslu přísluší jediný LN vlastní vektor, který lze zvolit kladný. Důkaz Existují λ, v tak, že Av = λv a přitom
32
KAPITOLA 3. POZITIVNÍ MATICE A FROBENIOVA VĚTA
Věta 3.17. Perronova - Frobeniova Nechť A je čtvercová nezáporná nerozložitelná matice n − tho řádu (n > 1). Potom ρ (A) je jednoduché vlastní číslo matice A a tomuto vlastnímu číslu odpovídá kladný vlastní vektor. Žádnému jinému vlastnímu číslu A už neodpovídá nezáporný vlastní vektor.
Kapitola 4
Metoda sdružených gradientů Nechť A je reálná, symetrická a positivně definitní (existují i ekvivalentní metody pro složitější matice), a nechť Ax = b. Budeme zkoumat chování funkce F (x) = 1 2 (Ax, x) − bx (tj. funkce v prostoru Rn ). Tato funkce má právě jedno (globální) minimum v bodě řešení Ax = b. Vzorec pro přírůstek je: 1 F (x + αx) − F (x) = α(Ax − b, v) + α2 (Av, v) 2 přičemž Ax − b nazýváme reziduum. Věta 4.1. Nechť xp je přesné řešení Ax = b. Funkce F (x) má v bodě xp minimum a jiná lokální minima nemá. Důkaz 1. v xp je minimum: 1 F (xp + αv) − F (xp ) = 0 + α2 (Av, v) > 0 pro α 6= 0, v 6= 0 2 takže v xp je skutečně minimum 2. F nemá jiná lokální minima: 1 F (x + αv) − F (x) = α(Ax − b, v) + α2 (Av, v) 2 pro malá α je |α(Ax − b, v)| > 12 α2 (Av, v) a pro +α, −α dostaneme opačná znaménka přírůstku. Pro všechny body a pro všechna jejich okolí existují x1 , x2 tak, že F (x1 ) > F (x) > F (x2 ) 33
34
KAPITOLA 4. METODA SDRUŽENÝCH GRADIENTŮ
Při iteračním využití této metody počítám x1 , x2 = x1 + α1 v1 , x3 = x2 + α2 v2 , . . . , xi+1 = xi + αi vi . Přitom chci minimalizovat rozdíl 1 F (xi+1 ) − F (xi ) = F (xi + αi vi ) − F (xi ) = αi (Axi − b, vi ) + αi2 (Avi , vi ) 2 takže volím αi = −
(Avi − b, vi ) (Avi , vi )
potom xi+1 = xi −
(Avi − b, vi ) (Avi , vi )
Otázkou však je, jak volit směr postupu v dalším kroku (totiž vektory vi ). Běžně používané metody jsou: 1. Gauss-Seidlova metoda (beru cyklicky e1 , e2 , . . .) 2. metoda největšího spádu (viz. dále) 3. metoda sdružených gradientů (viz. dále)
4.1
Metoda největšího spádu
Nechť kvi k = 1 a zkoumejme α(ri , vi ) + 12 α2 (Avi , vi ) F (x + αvi ) − F (x) = (ri , vi ) = lim α→0 α→0 α α lim
Spád je zřejmě největší pro vi =
ri kri k
a tak xi+1 = xi −
(ri , ri ) ri (Ari , ri )
Věta 4.2. Metoda největšího spádu konverguje při libovolné volbě počátečního přiblížení x1 k přesnému řešení rovnice Ax = b. Důkaz F (xi ) − F (xp ) = F (xp + i ) − F (xp ) = (ri , i ) + 1/over2(Ai , i ) F (xi+1 ) − F (xp ) =
1 (Ai+1 , i+1 ) 2
1 F (xi+1 ) − F (xi ) = F (xi + αi vi ) − F (xi ) = αi (ri , vi ) + αi2 (Avi , vi ) = 2 2 2 2 (ri , ri ) 1 (ri , ri ) 1 (ri , ri ) =− + =− (Ari , ri ) 2 (Ari , ri ) 2 (Ari , ri )
4.1. METODA NEJVĚTŠÍHO SPÁDU F (xi+1 ) − F (xi ) =
35
1 1 1 1 (ri , ri )2 (Ai+1 , i+1 ) − (Ai , i ) = − = − 2 2 2 2 (Ari , ri )
(Ai+1 , i+1 (ri , ri )2 =1− (Ai , i ) (Ari , ri )(Ai , i ) ki+1 kA je A-norma i+1 . Dokážeme nerovnost c2 ki+1 k ≤ ki+1 kA ≤ c1 ki+1 k A má všechna vlastní čísla kladná, a nechť m je nejmenší a M je největší vlastní číslo. Potom mki+1 k2 ≤ ki+1 kA ≤ M ki+1 k2 (ri , ri )2 = kri k4 (Ari , ri ) ≤ M kri k2 i = xi − xp Ai = Axi − b − Axp + b = ri (přičemž Axp − b = 0) Protože A je PD a symetrická, existuje úplný systém ortogonálních vlastních vektorů. x = α1 p1 + α2 p2 + · · · + αn pn (x, x) = α12 + · · · + αn2 Ax = λ1 α1 p1 + λ2 α2 p2 + · · · + λn αn pn (Ax, x) = λ1 α12 p1 + λ2 α22 p2 + · · · + λn αn2 pn M (x, x) ≥ (Ax, x) ≥ m(x, x) kde m = min{λi } a M = max{λi }. (Ai , i ) = (ri , A−1 ri ) ≤
1 kri k2 2
Přitom matice A−1 má nejmenší vlastní číslo 1/M a největší vlastní číslo 1/m. Potom (Ai+1 , i+1 ) M −m (ri , ri )2 kri k4 = ≤1 =1− ≤1− 1 2 2 M (Ai+1 , i+1 ) (Ari , ri )(Ai , i ) M kri k m kri k takže kkA ≤ k1 kA
M −m M
i−1
36
KAPITOLA 4. METODA SDRUŽENÝCH GRADIENTŮ
4.2
Metoda sdružených gradientů
Metoda největšího spádu má jednu nepřjemnou vlastnost - numusí nutně skončit po konečném počtu kroků. Modifikujme ji tedy tak, abychom tento nedostatek odstranili: x1 x2 = x1 + α1 v1 x3 = x2 + α2 v2 = x1 + α1 v1 + α2 v2 .. . xn = x1 +
n−1 X
αi vi
i=1
xn+1 = xp přičemž xp − x1 =
n X
αi vi
i=1
A(xp − x1 ) = Axp − b − Ax1 + b =
n X
αi Avi
i=1
a tedy αi = −
(r1 , vi ) (Avi , vi )
Tím jsme dostali sadu vi , která má následující vlastnost - pokud i 6= j, potom A(vi , vj ) = 0 a vi , vj jsou tedy navzájem ortogonální. Potom bude metoda konvergovat a skončí po konečném počtu kroků. Musíme najít taková vi , že vi = ri +
i−1 X
βij vj
j=1
βij = −
(Ari , vj ) (Avj , vj )
(Avi , vk ) = (Ari , vk ) +
i−1 X
βij (Avj , vk )
j=1
0 = (Ari , vk ) + βik (Avk , vk ) tvorba vi 1. vezmeme r1 , v1 = r1 2. vypočteme x2 , r2 → v2 atd.
4.2. METODA SDRUŽENÝCH GRADIENTŮ Tvrzení 4.3. Platí (ri , vj ) = (r1 , vj ) pro i ≤ j (ri , vj ) = 0 Důkaz / · A zleva
xi+1 = xi + αi vi
ri+1 = ri + αi · Avi ri = r1 +
i−1 X
αj Avj
j=1
(ri , vk ) = (r1 , vk ) +
i−1 X
αj (Avj , vk )
j=1
protože 1. k ≤ i ⇒ (Avj , vk ) = 0 ⇒ (ri , vk ) = (r1 , vk ) 2. k > i ⇒ (ri , vk ) = (r1 , vk ) + αk (Avk , vk ) α=−
(r1 , vk ) ⇒ (ri , vk ) = 0 (Avk , vk )
Tvrzení 4.4. (Avk , rj ) = 0 pro k > j (Avk , rk ) = (Avk , vk ) Důkaz vi = ri +
i−1 X
βik vk
k=1
ri = vi −
i−1 X
βik vk
k=1
(Avj , ri ) = (Avj , vi ) −
i−1 X
βik (Avj , vk ) = 0 pro j > i
k=1
(Avj , rj ) = (Avj , vj ) −
j−1 X
βjk (Avj , vk ) = (Avj , vj ) pro i = j
k=1
Věta 4.5. Vektory rk jsou navzájem ortogonální. Důkaz
37
38
KAPITOLA 4. METODA SDRUŽENÝCH GRADIENTŮ 1. r1 6= 0 (r1 , r1 ) 6= 0 (r2 , r1 ) x2 = x1 + α1 v1 xk = x1 +
k−1 X
αj vj
j=1
rk = r 1 +
k−1 X
αj Avj
j=1
αj = −
(rj , vj ) ⇒ (r1 + α1 Av1 , r1 ) = (r1 , r1 ) = 0; (Avj , vj )
2. s → s + 1
rs+1
(rs+1 , rk ) = 0 s > k X = r1 + j = 1s αj Avj = rs + αs Avs
(rs + αs Avs , rk ) = (rs , rk ) + αs (Avs , r + k) kde dle předpokladu (rs , rk ) = 0 a kvůli LZ platí také (Avs , vk ) = 0 3. s = k (rk+1 , rk ) = (rk , rk ) + αk (Avk , rk ) = (rk , rk ) −
(rk , vk ) (Avk , vk ) = (Avk , vk )
= (rk , rk ) − (rk , vk ) = (rk , vk ) = (rk , rk ) − rk , rk +
k−1 X j=1
LZ : (Avj , ri ) = 0 pro j > i Poznámka 4.6. Důsledek r
βij = −
rj+1 = rj + αj Avj ⇒ Avj = a nenulové je pouze βi,i−1
−r
ri , j+1α j (Ari , v + j) =− (Avj , vj ) (Avj , vj ) rj+1 − rs αj
βkj vj
4.3. PŘEDPODMÍNĚNÍ
39
Poznámka 4.7. Schéma: zvolíme x1 , vypočítáme ri = Axi − b, potom βi−1 = −
(Ari , vi−1 ) (Avi−1 , vi−1 )
i > 1, i = 1, β0 = 0
vi = ri + βi−1 vi−1 αi = −
(ri , vi ) (Avi , vi )
přičemž r1 = v1 . Potom xi+1 = xi + αi vi Poznámka 4.8. Metoda sdružených gradientů (Avi , vj ) = δij ({vi } je například báze z vlastních vektorů). Možnost volby báze: 1. tečné vektory 2. normály na nadplochu (kolmé na všechny ostatní)
4.3
Předpodmínění
Před iterací můžeme matici A vylepšit pomocí metody nazývané předpodmínění. Hledáme matici C C−1 Ax = C−1 b a chceme aby matice C−1 A měla co nejlepší vlastnosti. Za matici C je často volena hlavní diagonála z A nebo její násobek, aby šlo lehce najít C−1 . Je naprosto nelogické volit E (tím nic nezískáme), nebo A (protože po nalezení A−1 už bychom měli úlohu vyřešenu, ale chceme to udělat lépe než hledáním inverzní matice A). Přitom platí 1 1 1 1 1 1 C− 2 C− 2 AC− 2 C 2 = C−1 A ⇒ C− 2 AC− 2 ∼ C−1 A b x = bb, tak, že Zaveďme značení Ab b = C− 21 AC− 12 A 1
x b = C2 bb = C− 12 b Potom tedy 1 b xi − bb = C 12 AC− 12 x rbi = Ab bi − b = C− 2 ri 1 1 C− 2 AC− 2 ri , vbi−1 βbi−1 = − 1 1 C− 2 AC− 2 vbi−1 , vbi−1
40
KAPITOLA 4. METODA SDRUŽENÝCH GRADIENTŮ 1
C− 2 vbi−1 vbi = rbi + βbi−1 vbi−1 1 1 1 1 C− 2 vbi = C− 2 rbi + C− 2 βbi−1 vbi−1 = C−1 ri + βbi−1 C− 2 vbi
α bi = −
(b ri , vbi ) (Ab vi , vbi )
Nechť nyní
1
wi = C− 2 vbi si = C−1 ri Postup řešení je nyní následující: x1 , r1 = Ax1 − b, v1 = r1 , α1 ri = Axi − b (Asi , wi−1 ) βbi−1 = − (Awi−1 , wi−1 ) wi = si + βbi−1 wi−1 1 C− 2 ri , vbi (r , w ) =− i i w bi = − 1 1 (Awi , wi ) C− 2 AC− 2 vbi , vbi x bi+1 = x bi + ααi w bi C
− 12
1
1
x bi+1 = C− 2 x bi + α bi C− 2 vbi xi+1 = xi + α bi wi
Kapitola 5
Normy matic Definice 5.1. Zobrazení g(x) : Rn → R, resp. g(x) : C n → R je norma, právě když: 1. (∀x ∈ Rn (C n )) (g(x) ≥ 0) 2. g(x) = 0 ⇔ x = 0 3. g(x + y) ≤ g(x) + g(y) 4. g(αx) = |α|g(x) Poznámka 5.2. Takzvané Lp normy mají předpis n X
gp (x) =
! p1 p
|xi |
i=1
tj. například g1 (x) =
n X
|xi |
i=1 n X
g2 (x) =
! 2
|xi |
i=1
g∞ (x) = max |xi | i
Pro matice A typu (m, n) normy předepisujeme takto: g(A) = max x6=0
Ověřme že se skutečně jendá o normu: 1. platí triviálně díky vlastnostem g(x) 41
g(Ax) g(x)
42
KAPITOLA 5. NORMY MATIC 2.
g(Ax) = 0 ⇔ g(Ax) = 0 ∀x ⇔ g(x) ⇔ Ax = 0 ∀x ⇔ A = Θ
g(A) = 0 ⇔ max x6=0
3.
g ((A + B) x) g (Ax) + g (Bx) = max = x6=0 g(x) g(x) g (Ax) g (Bx) g (Ax) g (Bx) + max = = max + = max x6=0 g(x) x6=0 g(x) x6=0 g(x) g(x) = g (A + B)
g (A + B) = max x6=0
4.
g (Aαx) |α|g (Ax) = max = x6=0 g(x) g(x) g (Ax) = |α|g (A) = |α| max x6=0 g(x)
g (αA) = max x6=0
Normou generovanou nazýváme normu gαβ (A) = max gα (Ax) = gβ =1
g (Ax) gβ (x)
1. (∀x ∈ Rn )(gα (Ax) ≤ gαβ (A) gβ (x) 2. (∃x0 ∈ Rn )(gα (Ax) = gαβ (A) gβ (x) Potom g11 (A) = g1 (A) = max k
g1∞ (A) = max i
g2 (A) =
m X
|aik | tj. maximální sloupcový součet
i=1
n X
|aik | tj. maximální řádkový součet
k=1
p ¯T ρ (A∗ A) kde A je hermitovská, tj. A∗ = A
Důkaz g1 je generovaná norma 1. g1 (A) = max k
a nechť y = Ax, tj. yi =
X
|aik |
i
P
aik xk . Potom n m m X X X XX g1 (Ax) = g1 (y) = |yi | = |aik | |xk | ≤ ≤ i=1 i=1 k=1 i k ! X X X ≤ max |aik | |xk | = max |aik | g(x) k
k
k
i
k
i
43 2. existuje alespoň jeden nenulový vektor (x0 ) tak, že X g1 (Ax) = max |aik | g(x0 ) k
i
totiž vektor e = (0, . . . , 0, 1, 0, . . . , 0). g∞ je generovaná norma 1.
X g∞ (Ax) = max |yi | = max aik xk ≤ k k k X X X ≤ max |aik | |xk | ≤ max |aik | max |aik | = g∞ (A) g∞ (x) i
i
k
k
k
i
2. (∃x0 ) (g (A) = g∞ (A) g∞ (x)) tj. všechny nerovnosti musí přejít v rovnosti p (ρ(A∗ A) X g2 (x) = x ˆi xi
g2 (A) =
i
x1 x2 ∗ (ˆ x1 , x ˆ2 , . . . , x ˆn ) ... = x x
takže g2
√
xn x∗ x
1. g2 (Ax) =
2.
p p p (Ax, Ax) = (A∗ Ax, x) ≤ |λmax (A∗ A)|g2 (x) = p = ρ (A∗ A)g2 (x) p (∃x0 ∈ Rn ) g2 (Ax0 ) = ρ (A∗ A)g2 (x0 )
x0 je vlastní vektor matice A∗ A příslušný k λ, kde λ = ρ (A) Tvrzení 5.3. (Ax, Ax) = (A∗ Ax, x) Důkaz nápověda (x, x) = Tr (x∗ x) = Tr (xx∗ ) Definice 5.4. Schurovu normu definujeme jako v u m X n u X u 2 |aij | N (A) = t i=1 j=1
44
KAPITOLA 5. NORMY MATIC Platí g2 (A) ≤ N (A)
protože: 2
(N (A)) = Tr (A∗ A) (A∗ Ax, x) = (Ax, Ax) ≥ 0 Pro libovolné γ platí: gαβ (AB) ≤ gαγ (A) gγβ (B) kde A je typu (m, n), B je typu (n, p), takže AB je typu (m, p). Platí také N (AB) ≤ N (A) N (B) g2 (A) ≤ N (A) N (AB) ≤ g2 (A) N (B) N (AB) ≤ g2 (B) N (A)
