PA081: Programování numerických výpočtů
9. Rozklady matic, singulární a vlastní hodnoty
Aleš Křenek
jaro 2012
Rozklad matic na singulární hodnoty
Základní tvrzení
► libovolnou reálnou (i komplexní) matici lze rozložit
AjvfxJV = UjvfxJV ' SjvxJV ' VjfxN    (= UjvfxM ■ ^MxJV ' ^ JVxJV")
► U je sloupcově ortogonální
► až na nulové sloupce v případě M < N
► S diagonální a V ortogonální
► rozklad je unikátni až na
► současnou perumutaci sloupců všech tří matic
► lineární kombinaci sloupců U, V odpovídajících nulovým 07
Rozklad matic na singulární hodnoty
Geometrický význam
► A je složení transformací
► rotace/zrcadlení V-1
► zvětšení/zmenšení faktory 07 ve směrech e;, včetně degenerace (07 = 0)
► rotace/zrcadlení a projekce do méně/více dimenzí U
Rozklad matic na singulární hodnoty
Geometrický význam
Rozklad matíc H na singulární hodnoty
► A je složení transformací viasmí
1 hodnoty a
► rotace/zrcadlení V
► zvětšení/zmenšení faktory crŕ ve směrech e;, včetně degenerace (07 = 0)
► rotace/zrcadlení a projekce do méně/více dimenzí U
► obor hodnot zobrazení A
► sloupce U odpovídající nenulovým 07 jsou jeho generátory
PA081:
Programování numerických výpočtů
A. Křenek
Rozklad matic na singulární hodnoty
Geometrický význam
A je složení transformací
► rotace/zrcadlení V-1
► zvětšení/zmenšení faktory crŕ ve směrech e;, včetně degenerace (07 = 0)
► rotace/zrcadlení a projekce do méně/více dimenzí U
obor hodnot zobrazení A
► sloupce U odpovídající nenulovým 07 jsou jeho generátory
nulový prostor N (A) = {x e RN : Ax = 0}
► řádky VT odpovídající nulovým crr jsou jeho generátory
Vlastní hodnoty a vektory
Rozklad matic na singulární hodnoty
Numerický význam
► „oddělení zrna od plev"
► sloupce U a V jsou kolmé a normované
► veškeré potenciální degenerace soustředěny do 2
► singularity A odpovídají nulovým 07
► včetně numerických (crr » 0)
► numericky velmi stabilní algoritmus dekompozice
► lze použít na řešení systémů lineárních rovnic
► M < N a M = N singulární: reprezentant řešení + generátor prostoru
► M > N: nejbližší řešení
Rozklad matic na singulární hodnoty
Použití pro M = N
řešení systému rovnic, resp. výpočet inverzní matice A"1 = V[diag(l/o-ŕ)]Ur
Vlastní
1       \rV Am      / 1 /      \~ITtF hodnoty a
kdy to nejde
► jedno nebo více 07 je nulových - A byla singulární * ^min/^max < £ (špatně podmíněná matice) - standardní metody řešení selhaly
vektory
Rozklad matic na singulární hodnoty
Použití pro M = N
► řešení systému rovnic, resp. výpočet inverzní matice
► kdy to nejde
► jedno nebo více 07 je nulových - A byla singulární *• Omin/Omax < e (špatně podmíněná matice) - standardní metody řešení selhaly
► označme
► rovnice Ax = b nemusí mít řešení, přesto zkusíme
x = vrurb
A"1 = V[diag(l/o-r)]Ur
Rozklad matic na singulární hodnoty
Použití pro M = N
*■ hledáme nejbližší řešení, tj. minimalizujeme |Ax - b|
► pro libovolné x' je A(x + x') - b = Ax - b + b', kde b' = Ax'
IAx-b + b'1 = |(USVr)(VS'Urb) - b + b'l = |(USS'Ur -I)b + b'| = |U((ZZ' - J)Urb + Urb')| =        - J)Urb + Urb'|
► XX' - I je diagonálni s nenulovými prvky pro 07 = 0
► b' je v oboru hodnot A, tedy Urb' má nenulové prvky právě pro 07 =ŕ 0
► minimum právě pro b' = 0 a tedy i x' = 0
Vlastní hodnoty a vektory
Rozklad matic na singulární hodnoty
Použití pro M = N
SVD solution of A x = d
Rozklad matic na singulární hodnoty
Použití pro M = N - prakticky
► singularitu A detekujeme podle 07 = 0
► vypočteme nejbližší řešení jako x = VS'Urb
► dosazením ověříme, zda je to přesné řešení
► když ne, víme, že přesné řešení neexistuje
► máme nejbližší aproximaci
Rozklad matic na singulární hodnoty
Použití pro M = N - prakticky
singularitu A detekujeme podle 07 = 0 vypočteme nejbližší řešení jako x = VS'Urb dosazením ověříme, zda je to přesné řešení
► když ne, víme, že přesné řešení neexistuje
► máme nejbližší aproximaci
špatně podmíněná matice | crmax | » | crmin |
► lépe v 2' vynulovat i taková 07
► paradoxní - zahazujeme část vstupní informace
► v praxi dává lepší výsledky - právě tento vstup má tendenci škodit
► stanovení prahu 07 ~ 0 není triviální
Vlastní hodnoty a vektory
□     s   4 :
■OQ.O
8/18
Rozklad matic na singulární hodnoty
Použití pro M * JV
► méně rovnic, M < N
► nekonečně mnoho řešení
► rozklad na singulární hodnoty - N - M nulových 07
► nemusí být přesně nulové (numerické nepřesnosti)
► může jich být více díky dalším singularitám
► 5/ vypočítáme vynulováním problematických 07
► přímo vypočteme reprezentativní řešení x
► včetně ověření, zdaje skutečně řešením
► sloupce V odpovídající nulovaným 07 generují prostor dalších řešení
Rozklad matic na singulární hodnoty
Použití pro M * JV
► více rovníc, M > N
► neexistuje přesné řešení, hledáme nejbližší aproximaci
► rozklad na singulární hodnoty
► obecně nemusí dát žádná nulová crŕ
► získáme nejbližší aproximaci řešení, viz naznačený důkaz
Rozklad matic na singulární hodnoty
Použití pro M * JV
Rozklad matíc H na singulární
► více rovnic, M > N hodnoty
► neexistuje přesné řešení, hledáme nejbližší aproximaci
vektory
► rozklad na singulární hodnoty
► obecně nemusí dát žádná nulová crŕ
► získáme nejbližší aproximaci řešení, víz naznačený důkaz
► (skoro) nulové singulární hodnoty
► skrytá degenerace systému
► může vést na jedno nebo i více přesných řešení
PA081: Programování numerických výpočtů
A. Křenek
Rozklad matic na singulární hodnoty
Použití pro M * JV
Rozklad matíc H na singulární
► více rovníc, M > N hodnoty
► neexistuje přesné řešení, hledáme nejbližší aproximaci
vektory
► rozklad na singulární hodnoty
► obecně nemusí dát žádná nulová crŕ
► získáme nejbližší aproximaci řešení, viz naznačený důkaz
► (skoro) nulové singulární hodnoty
► skrytá degenerace systému
► může vést na jedno nebo i více přesných řešení
► velmi malé singulární hodnoty
► ukazují na nízkou citlivost problému
► právě ve směrech odpovídajících sloupců V
► zpravidla lépe vynulovat v 2'
PA081: Programování numerických výpočtů
A. Křenek
Rozklad matic na singulární hodnoty
Aproximace matíc
► původní matici lze vyjádřit
fc
► je-li většina 07 skoro nulových
► má smysl ukládat jen několik sloupců U a V
► stále dostáváme poměrně přesnou aproximaci A
► násobení Ax je výrazně efektivnější - K(M + N) operací
Rozklad matic na singulární hodnoty
Algoritmus
numericky stabilní implementace postupu v důkazu věty využívá řadu pomocných tvrzení relativně komplikovaný, ale přímočarý výjimečně stabilní
► zaměření na vytažení problematických vlastností A do 2 použijeme existující implementaci:-)
► už to za nás jednou někdo udělal
► další vylepšující triky dodavatelů knihoven
► nezbavuje to odpovědnosti za interpretaci výsledku
původní algoritmus Golub a Reinsch, Singulár value decomposition and least squares solutions, 1970
Vlastní hodnoty a vektory
Vlastní hodnoty a vektory
více viz kursy lineární algebry
Vlastní hodnoty a vektory
► numericky velmi nepříjemný problém
► ještě jasnější případ, kdy sáhnout k hotovým řešením
► různé varianty pro různé případy
► reálné a komplexní
► vlastní hodnoty, vektory, obojí
► různé speciální typy matic
► vztah k singulárním hodnotám
► sloupce U v SVD jsou vlastní vektory AAT
► nenulové singulární hodnoty jsou odmocniny nenulových vlastních hodnot AAT
Vlastní hodnoty a vektory
Použití
► PA081
► hledání kořenů polynomů
► superpozice množiny bodů
PA081: Programování numerických
výpočtů
A. Křenek
Rozklad matic na singulární hodnoty
Vlastní hodnoty a vektory
□       4       ►   4 ■= *   < ►
Vlastní hodnoty a vektory
Použití
► PA081
► hledání kořenů polynomů
► superpozice množiny bodů
► kritické body funkce více proměnných
► první parciální derivace jsou nulové
► Hessián (matice druhých parciálních derivací) určuje aproximaci kvadrikou v daném bodě
► symetrická matice - reálné hodnoty, ortonormální vektory
► extrémy - všechny A kladné, sedla - některé záporné
► absolutní hodnoty A určují tvar, vektory orientaci
Vlastní hodnoty a vektory
Použití
kritické body vektorového pole
► velikost vektoru je nulová
► Jakobián (matice prvních parciálních derivací)
Rapelling focua R1 .R2>
Vlastní hodnoty a vektory
Použití
► Schródingerova rovnice
► řešení a interpretace speciálních případů
PA081: Programování numerických
výpočtů
A. Křenek
Rozklad matic na singulární hodnoty
Vlastní hodnoty a vektory
Vlastní hodnoty a vektory
Použití
► Schródingerova rovnice
► řešení a interpretace speciálních případů
► statistika - hlavní komponenty
► charakteristika korelace veličin
PA081: Programování numerických
výpočtů
A. Křenek
Rozklad matic na singulární hodnoty
Vlastní hodnoty a vektory
Vlastní hodnoty a vektory
Použití
► zpracování obrazu
► obrázky obličejů
► např. 200 x 200 pixelů
► vektory o 40.000 dimenzích
► vlastní vektory matice kovariance
► významnější lze použít jako generátory
► použití při rozpoznávání tváří