PA081: Programování numerických výpočtů
9. Rozklady matic, singulární a vlastní hodnoty
Aleš Křenek
jaro 2011
Rozklad matic na singulární hodnoty
Základní tvrzení
► libovolnou reálnou (i komplexní) matici lze rozložit
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 <Jí
Rozklad matic na singulární hodnoty
Geometrický význam
► A je složení transformací
► rotace/zrcadlení V-1
► zvětšení/zmenšení faktory <Jí ve směrech eu včetně degenerace (oí = 0)
► rotace/zrcadlení a projekce do méně/více dimenzí U
Rozklad matic na singulární hodnoty
Geometrický význam
► A je složení transformací
► rotace/zrcadlení V-1
► zvětšení/zmenšení faktory <Jí ve směrech eu včetně degenerace (oí = 0)
► rotace/zrcadlení a projekce do méně/více dimenzí U
► obor hodnot zobrazení A
► sloupce U odpovídající nenulovým <Jí jsou jeho generátory
Rozklad matic na singulární hodnoty
Geometrický význam
► A je složení transformací
► rotace/zrcadlení V-1
► zvětšení/zmenšení faktory <Jí ve směrech e*, včetně degenerace (oí = 0)
► rotace/zrcadlení a projekce do méně/více dimenzí U
► obor hodnot zobrazení A
► sloupce U odpovídající nenulovým <Jí jsou jeho generátory
► nulový prostor M (A) = {x e RN : Ax = 0}
► řádky Vr odpovídající nulovým <Jí jsou jeho generátory
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 <Ji
► včetně numerických (oí « 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
-i
V[diag(l/a-í)]Ur
► kdy to nejde
► jedno nebo více <Ji je nulových - A byla singulární
> ^min/^max < e (špatně podmíněná matice) - standardní metody řešení selhaly
PA081: Programování numerických
výpočtů
A. Křenek
Rozklad matic na singulární hodnoty
Vlastní hodnoty a vektory
5/18
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 <Jí 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 = VS'Urb
A
i
V[diag(l/o-()]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'
| Ax - b + b' | = | (USVr) (VS'Urb) - b + b' | = |(USS'Ur-J)b + b'| = |U((SS' -J)Urb + Urb')l =        - J)Urb + Urb'|
► ££' - I je diagonálni s nenulovými prvky pro 07 = 0
► b' je v oboru hodnot A, tedy Ur má nenulové prvky právě pro (Ji =ŕ 0
► minimum právě pro b' = 0 a tedy i x' = 0
Rozklad matic na singulární hodnoty
Použití pro M = N
null
space
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
PA08i:
Programování numerických výpočtů
A. Křenek
Rozklad matic na singulární hodnoty
Vlastní hodnoty a vektory
8/18
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 I » I crmin I
► lépe v £' vynulovat i taková <Jí
► paradoxní - zahazujeme část vstupní informace
► v praxi dává lepší výsledky - právě tento vstup má tendenci škodit
► stanovení prahu <Jí ~ 0 není triviální
Vlastní hodnoty a vektory
8/18
Rozklad matic na singulární hodnoty
Použití pro M * N
► méně rovnic, M < N
► nekonečně mnoho řešení
rozklad na singulární hodnoty - N - M nulových 07
► nemusí být presne nulové (numerické nepřesnosti)
► může jich být více díky dalším singularitám
► J' vypočítáme vynulováním problematických oy *■ 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 =f= N
► více rovnic, M > N
► neexistuje přesné řešení, hledáme nejbližší aproximaci
► rozklad na singulární hodnoty
► obecně nemusí dát žádná nulová <Ji
► získáme nejbližší aproximaci řešení, viz naznačený důkaz
PA081: Programování numerických
výpočtů
A. Křenek
Rozklad matic na singulární hodnoty
Vlastní hodnoty a vektory
10/18
Rozklad matic na singulární hodnoty
Použití pro M =t= N
► 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á <Jí
► 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í
Vlastní hodnoty a vektory
4 □ ► 4 ŕS ► 4 :
Rozklad matic na singulární hodnoty
Použití pro M =t= N
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á <Jí
► 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 £'
Vlastní hodnoty a vektory
10/18
Rozklad matic na singulární hodnoty
Aproximace matic
► původní matici lze vyjádřit
k
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í
PA08i:
Programování numerických výpočtů
A. Křenek
Rozklad matic na singulární hodnoty
Vlastní hodnoty a vektory
11/18
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 S
► 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 matice (transformace)
kalk
Ax = Ax
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 AAr
► nenulové singulární hodnoty jsou odmocniny nenulových vlastních hodnot AAr
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
15/18
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
4 □ ► 4 rS ► < J ► < J >
15/18
Vlastní hodnoty a vektory
Použití
A. Křenek
► kritické body vektorového pole
► velikost vektoru je nulová
► Jakobián (matice prvních parciálních derivací)
Vlastní hodnoty a vektory
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
17/18
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
17/18
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áří