Fuzzy Rendszerek és Genetikus Algoritmusok Előadás vázlat 1 előadás Összeállította: Harmati István Ph.D., egyetemi adjunktus Felhasznált Irodalom: Rózsa Pál: Lineáris algebra és alkalmazásai. Budapest, 1991.
[QR] Sajátérték-feladat megoldása QR transzformációval Cél: Valós elemű mátrixok sajátérték-feladatának megoldása általános esetben Kulcsszerep: Hessenberg-féle mátrix. (Csökken a számítási igény, ha ilyen alakon végezzük QR-t) [Def.] Hessenberg matrix. Egy mátrixot Hessenberg féle mátrixnak nevezünk, ha az i ≥ j + 2 , j = 1,2, K , n − 2 ( n a matrix mérete) egyenlőtlenséggel jellemzett indexpár által meghatározott elemei nullák: ⎡ f 11 ⎢f ⎢ 21 F=⎢ 0 ⎢ ⎢ M ⎢⎣ 0
f 12
L
f 1,n −1
f 22
L
f 2,n −1
f 32
L
f 3,n −1
O 0
O 0
M f n,n −1
f 1n ⎤ f 2n ⎥ ⎥ f 3n ⎥ ⎥ M ⎥ f nn ⎥⎦
Az eljárás lépései: 1. QR transzformáció bemutatása Lényege: Egy adott ( A) mátrixot ortogonális transzformációk (TF-k) sorozatával felső háromszögmátrixra (FHM) transzformálunk, amelynek főátlójában megjelennek a sajátértékek. Megmutatjuk, hogy a Hessenberg matrix alakja a QR transzformációra invariáns. 2. Transzformáció Hessenberg alakra. Eljárást adunk arra, hogy bármely matrix egy alsó háromszögmátrixszal végzett hasonlósági TF-val felső Hessenberg féle alakra hozható. 3. Hessenberg-féle mátrixra alkalmazva QR transzformációt, iterációs módszert kapunk sajátétékek meghatározására. (alkalmas eltolási transzformációval a konvergencia sebessége növelhető) 4. Sajátvektorok meghatározása rekurzív képlettel és a 2. pontban szereplő alsó háromszögmátrix (AHM) segítségével.
[QR].1. A QR transzformáció [QR].1.1. A QR felbontás Tétel QR.1. Bármely valós A mátrix felírható A = QR alakban, ahol Q ortogonális mátrix, R pedig FHM. Bizonyítás. Elöször bebizonyítjuk, hogy létezik olyan S1 ortogonális mátrix, hogy S1 A első oszlopának főátló alatti elemei nullák. Tekintsük elöször a következő ortogonális mátrixot:
S n1
⎡ cos ϑ n1 ⎢ 0 ⎢ =⎢ M ⎢ ⎢ 0 ⎢⎣− sin ϑ n1
0 L 0 sin ϑ n1 ⎤ 1 0 ⎥ ⎥ O M ⎥ ⎥ 1 0 ⎥ 0 L 0 cos ϑ n1 ⎥⎦
Legyen a11 ≠ 0 , tgϑ n1 =
sin ϑ n1 a := n1 cos ϑ n1 a11
Szorzással belátható, hogy egyenletét adja.)
(Ez egy síkbeli forgatás)
(Ha a11 = 0 , akkor ϑn1 =
π 2
)
M n −1 = S n1 A szorzat első oszlopának utolsó eleme 0, (mivel épp tgϑn1
Hasonlóan, az eredményül kapott ( miji elemekből álló) mátrix első oszlopának i. sora is nullázható
S i1
⎡ cos ϑi1 ⎢ ⎢ ⎢ ⎢ ⎢ = ⎢ − sin ϑi1 ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣
sin ϑi1 1 O 1 cos ϑi1
⎤ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ 1 ⎥ ⎥ 1 ⎥ O ⎥ 1⎥⎦
tgϑ1 =
mii1 i m11
i = 0 , akkor ϑi1 = (Ha m11
π 2
)
Rekurzívan folytatva eljutunk M 1 mátrixig, amelynek első oszlopa a főátló alatt zérus:
M 1 = S 21 S 31 L S n1 A
ahol
S1 = S 21 S 31 L S n1 ortogonális
Az eljárás lépéseit a második oszlop diagonális alatti elemek nullázására alkalmazva szintén egy ortogonális mátrixot kapunk: S 2 = S 32 S 42 L S n 2 , így az
M 2 = S 2 S1 A
mátrixnak már első és második oszlopában is a diagonális elemek alatt nullák szerepelnek.
( S 2 mátrixszal való szorzás nem rontja el az első oszlopban már meglévő nullákat)
Általánosan, az
⎞ ⎛ n −1 n R = ⎜⎜ ∏ ∏ S ji ⎟⎟ A ⎝ i =1 j =i +1 ⎠
S ji
⎡O ⎢ 1 ⎢ ⎢ cos ϑ ji ⎢ ⎢ =⎢ ⎢ ⎢ ⎢ − sin ϑ ji ⎢ ⎢ ⎢ ⎣
sin ϑ ji 1 O 1 cos ϑ ji
⎤ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ 1 ⎥ O⎥⎦
Ortogonális transzformációkkal végzett szorzat felső háromszög mátrixot ad, és az A mátrix Q
T
n −1 n
= ∏ ∏ S ji szorzója egy ortogonális mátrix. i =1 j = i +1
Azaz
R = QT A
(Q.E.D.)
→
A = QR
[QR].1.2. A QR transzformáció előállítása
A1 := A = Q1 R1
Képezzük a következő mátrixsorozatot:
R1 = QT A1
} =
Szorozzuk meg a komponenseket fordított sorrendben:
A2 = R1 Q1
Képezzük az A2 QR felbontását:
A2 = Q2 R 2
Megismételve az eljárást,
Ak = Qk R k = R k −1Qk −1
Az
R k −1 = Q kT−1 Ak −1
és
Q T A1 Q1
k = 1,2, K(QR/6-1) A1 = A
Q k −1 = Ak −1 R k−−11
(QR/6-2)
felírást behelyettesítve (QR/6-1) egyenletbe:
Ak = QkT−1 Ak −1Qk −1 = R k −1 Ak −1 R k−−11 Legyen
→
Az összes Ak mátrix hasonló, tehát sajátértékei megegyeznek.
Pk = R k R k −1 L R1
(FHM)
és
(QR/6-3)
N k = Q1Q2 L Qk
(ortogonális)
(QR/6-4)
Ezeket alkalmazva a (QR/6-2) rekurzív összefüggéssel együtt: Ak +1 = N kT A1 N k = Pk A1 Pk−1 .
(QR/6-5)
(QR/6-1), (QR/6-2), (QR/6-4) alapján: N k Pk = Q1 Q 2 L Q k −1 Q k R k R k −1 L R 2 R1
= Q1 Q 2 L Q k −1 R k −1 Q k −1 R k −1 L R 2 R1 = Q1 Q 2 L Q k − 2 (Q k −1 R k −1 ) 2 R k − 2 L R 2 R1
(QR/7)
= Q1 Q 2 L Q k − 2 (R k − 2 Q k − 2 ) 2 R k − 2 L R 2 R1 = L = (Q1 R1 ) k = A k
Az A k hatvány tehát az N k ortogonális és Pk felső háromszög matrix szorzatára bontható! [Def] QR transzformáció. Az A matrix (QR/6-1) szerinti rekurziós faktorizáció-sorozata az A matrix QR transzformációja Ak = Qk R k = R k −1Qk −1 k = 1,2, K A1 = A
[QR].1.3. A QR transzformáció mátrixsorozatának konvergenciája Tétel QR.2 Ha az A matrix QR transzformációjával meghatározott Ak mátrixsorozat konvergens, akkor annak határértéke felső háromszögmátrix. Bizonyítás: A feltétel alapján az Ak mátrixsorozat konvergens létezik → + (QR/6-4) → lim Qk +1
N k +1 = N k Qk +1
k →∞
=
lim N k = N ∞
k →∞
−1 lim N k N k +1 = I
k →∞
(Konvergencia esetén nagy k -ra N k egyre kevesebbet változik) Másrészt (QR/6-5) és (QR/6-1) alapján:
Ak +1 = N kT A1 N k = Qk +1 R k +1
→
N
=N Q
1 k +1 R k +1 = QkT+1 N kT A1 N k ⎯⎯k +⎯ ⎯k ⎯ ⎯→ R k +1 = N kT+1 A1 N k
(QR / 8−1) ⎯→ A∞ = lim Ak +1 = lim Qk +1 R k +1 ⎯⎯⎯⎯→ R∞ → lim R k +1 = lim N kT+1 A1 N k ⎯ k →∞
k →∞
k →∞
k →∞
Vagyis, ha Ak konvergens, akkor határértéke valóban FHM. Q.E.D. Következmény QR.1. Mivel Ak mátrixok hasonlóak az sorozat határértékeként adodó A∞ = R∞ FHM főátlójának elemei az A matrix sajátértékei.
Tétel QR.3 A Hessenberg féle mátrixok alakja QR-transzformációval szemben invariáns.
Bizonyítás: Legyen F egy felső Hessenberg-féle mátrix, amelyre a QR transzformáció:
F = F1 = Q1 R1 1. Az R1 FHM
2. Egy FHM ( R1 ) inverze is FHM ( A −1 = adjA / det A , FHM adjungáltjában a diagonális alatti elemekhez tartozó minormátrixok diagonális elemeiben lesz nulla, igy nullát ad azon a helyen az invez is.)
1-2 → Q1 = F1 R1−1 azaz mivel R1−1 FHM, így Q1 j. oszlopa az kombinációja → Q1 is Hessenberg mátrix.
⎡∗ ∗ ∗ ∗⎤ ⎡∗ ∗ ∗ ∗⎤ ⎡∗ ∗ ∗ ∗⎤ ⎢∗ ∗ ∗ ∗⎥ ⎢∗ ∗ ∗ ∗⎥ ⎢ ∗ ∗ ∗⎥ ⎥=⎢ ⎢ ⎥⎢ ⎥ ⎢ ∗ ∗ ∗⎥ ⎢ ∗ ∗ ∗⎥ ⎢ ∗ ∗⎥ ⎥ ⎢ ⎢ ⎥⎢ ⎥ ∗ ∗⎦ ⎣ ∗ ∗⎦ ⎣ ∗⎦ ⎣14 4244 3 14 4244 3 14 4244 3 F1
Q1
R1
F1 mátrix első j oszlopának lineáris (QR/9-B1)
A QR transzformáció alapján:
F2 = R1Q1 Mivel az R1 FHM és Q1 Hessenberg mátrix (QR/9-B1), az F2 mátrix i. sora a Q1 mátrix i, i + 1, K , n sorának lineáris kombinációja → F2 Hessenberg mátrix → Fk Hessenberg mátrixok alakja a QR transzformációra invariáns.
⎡∗ ∗ ∗ ∗⎤ ⎡∗ ∗ ∗ ∗⎤ ⎡∗ ∗ ∗ ∗⎤ ⎢∗ ∗ ∗ ∗⎥ ⎢ ∗ ∗ ∗⎥ ⎢∗ ∗ ∗ ∗⎥ ⎥=⎢ ⎢ ⎥⎢ ⎥ ⎢ ∗ ∗ ∗⎥ ⎢ ∗ ∗⎥ ⎢ ∗ ∗ ∗⎥ ⎥ ⎢ ⎢ ⎥⎢ ⎥ ∗ ∗⎦ ⎣ ∗⎦ ⎣ ∗ ∗⎦ ⎣14 4244 3 14 4244 3 14 4244 3 F2
Q.E.D.
R1
Q1
[QR].2. Transzformáció Hessenberg alakra Algoritmus: Az n -edrendű A mátrixot alkalmas transzformációval hozunk felső Hessenberg alakra:
Z
alsó háromszögmátrixszal végzett hasonlósági
1. Kiindulás: Tetszőleges z1 vektor
(Megjegyzés: z1 = (1,0, K ,0)T kiindulás jelentősen csökkenti az igényelt számítási kapacitást. )
z 2 := Az1 − f 11 z1
2. Képezzük:
Ahol f 11 értékét abból a feltételből határozzuk meg, hogy z 2 első eleme 0 legyen. 3. Az eljárást folytatva:
z k +1 := Az k − f 1k z1 − f 2k z 2 − L − f kk z k
(QR/11-1)
ahol f ik ( i = 1,2, K , k ) együtthatók megválasztása úgy történik, hogy z k +1 első k eleme 0 legyen →
→ A Z = [z1 L z n ] matrix alsó háromszögmátrix. A (QR/11-1) alak felírható mátrixformában: AZ = ZF ⎡ f 11 ⎢ 1 ⎢ z 22 F=⎢ 0 M ⎢ ⎢ M z n2 ⎢⎣ 0 Azaz F felső Hessenberg mátrix alakú!
⎡ z11 ⎢z Z = ⎢ 21 ⎢ M ⎢ ⎣ z n1
0
0 ⎤ O M ⎥ ⎥ O 0 ⎥ ⎥ L z nn ⎦ L
f 12
f 13
L
f 22
f 23
L
1 O
O
O
O
f n −1,n −1
L
0
1
f 1n ⎤ f 2n ⎥ ⎥ M ⎥ ⎥ f n −1,n ⎥ f nn ⎥⎦
4. A Hessenberg alak előállítása:
F = Z −1 AZ
[QR].3. Hessenberg-féle mátrix sajátértékeinek meghatározása QR transzformációval
A QR.3. Tétel alapján a Hessenberg –féle matrix sajátértéke a QR transzformációra invariáns → 1. Az A mátrixot Hessenberg alakra hozzuk [QR].2 fejezet alapján 2. Alkalmazzuk a [QR].1.2 fejezetben ismertetett QR transzformációt (mátrixsorozatot) ( n 3 nagyságrendű műveletigény helyett csak n 2 kell Hessenberg alaknál) A mátrixsorozat egy FHM-hez tart (Következmény QR.1.), aminek diagonális elemei adják a sajátértékeit. Konvergencia sebessége:
f i(,ik−)1
λ = i λ i −1
k
Ahol f i(,ik−)1 a mátrixsorozat előállításában a k . Hessenberg mátrix
λ i az i. sajátérték.
A konvergencia nem elég nagy, ha két sajátérték között nincs nagy különbség. → Konvergencia gyorsítása:
A helyett A − sI mátrixszal dolgozunk, aminek a sajátértékei λ i − s számok lesznek és a konvergencia sebességére jelemző
λi − s csökkenthető alkalmas s választással. λ i −1 − s
[QR].4. Hessenberg-féle mátrix sajátvektorainak meghatározása Sajátvektor: v k Sajátvektorok meghatározása:
(λ k I − F )v k
= 0 algebrai egyenletet kell megoldani.
Megjegyzés: A Hessenberg alak az egyenlet megoldásához szükséges számításokat csökkenti, így előnyösen használható.
[SVD] Szinguláris érték szerinti felbontás (SVD) [Def.] Szinguláris értékek.
Ha az A komplex elemű, n -edrendű és r -edrangú négyzetes matrix és σ i2
( i = 1,2, K , n ) jelöli a pozitív szemidefinit A H A matrix sajátértékeit, akkor a
σ 1 ≥ σ 2 L ≥ σ r > σ r +1 = L = σ n = 0 számokat a szinguláris értékeknek nevezzük. Tétel SVD.1. Legyen A tetszőleges m × n típusú komplex elemű mátrix, és tegyük fel, hogy m ≥ n . Ekkor létezik olyan m -edrendű U és n -edrendű V mátrix, hogy A = UDV
Ahol
H
(SVD/14-1)
UU H = I VV H = I
(U unitér mátrix) (V unitér mátrix)
⎡σ 1 ⎤ ⎢ ⎥ O ⎥ D=⎢ ⎢ σn⎥ ⎢ ⎥ 0 ⎣ ⎦
σ1 ≥ σ 2 L≥ σ n ≥ 0
A σ i , i = 1,2, K , n számok az A mátrix szinguláris értékei, V az A H A mátrix modálmátrixa, U pedig az AA H mátrix modálmátrixa
Bizonyítás:
Jelölje az A H A n -edrendű pozitív szemidefinit mátrix modálmátrixát V (sajátérték-sajátvektorfelbontásból kijön, megoldáshoz: QR), vagyis: ~ V H A H AV = D 2
~ Ahol D a nemnegatív szinguláris értékekből alkotott mátrix ⎡σ 1 ⎤ ~ ⎢ ⎥ D= O ⎢ ⎥ ⎢⎣ σ n ⎥⎦
~ Legyen F := AV . Akkor: F H F = D 2 ami diagonális, vagyis
(SVD/15-1)
ha ρ ( A) = r = n
→
f i H f i = σ i2
ha ρ ( A) = r < n
→
F mátrix r + 1, K , n oszlopvektora zérusvektor.
Képezzük az U r = [u1 L u r ] ui =
1
σi
és
f iH f k = 0
f i i = 1, K , r
i ≠ k ; i, k = 1, K , n
(SVD/15-2)
unitér vektorendszert és egészítsük ki az [u1 , K , u m ] teljes unitér vektorrendszerré (U rH U r = I r és I n − U r U rH mátrixot hermetikus diádokra felbontva I n − U r U rH = WW H ahol W oszlopai adják a hiányzó vektorokat) Legyen U = [u1 L u m ] →
U HU = E
(SVD/15-1),(SVD/15-2)
⎯⎯ ⎯ ⎯ ⎯ ⎯ ⎯ ⎯→ F = AV = UD →
A = UDV
H
Végül megmutatjuk, hogy U oszlopvektorai az AA H sajátvektorai. Az (SVD/14-1)-ből: A
H
= VD U T
H
→
~2 ⎡D AA U = U ⎢ ⎣ 0 H
0⎤ ⎥ 0⎦
azaz AA H ui = σ i2 ui
Vagyis U oszlopvektorai valóban az AA H sajátvektorai. Q.E.D. Következmény SVD.1: A = UDV
H
→
Avi = σ i ui A H ui = σ i vi
[MPI] A Moore-Penrose féle inverz (pszeudo inverz) Tétel MPI.1. Ha az r -edrangú m × n pszeudoinverz előállítható
( m ≥ n ) típusú A mátrix SVD felbontása A = UDV
A + = VD + U H
Alakban, ahol ⎡σ 1−1 ⎢ O ⎢ ⎢ σ r−1 ⎢ D+ = ⎢ ⎢ ⎢ ⎢ ⎢ 0 ⎣
Mert teljesül: 1. AA + A = A 2. A + AA + = A +
(AA + )H = AA + H 4. (A + A) = A + A 3.
⎤ ⎥ ⎥ ⎥ ⎥ 0 ⎥ O ⎥ ⎥ 0⎥ ⎥ ⎦
( m × n típusú)
H
, akkor az A +
