Modern numerikus módszerek
Bene Gyula
Eötvös Loránd Tudományegyetem, Elméleti Fizikai Tanszék
1117 Budapest, Pázmány Péter sétány 1/A
3. hét keddi előadás
Lineáris algebra
Szinguláris érték felbontás
Bármely mátrix felírható
$${\bf A}={\bf U}\cdot {\bf S}\cdot {\bf V}^\dagger$$
alakban, ahol ${\bf S}$ diagonálmátrix, ${\bf U}$ és ${\bf V}$ pedig unitér
mátrixok, azaz
$${\bf U}\cdot {\bf U}^\dagger={\bf 1}\;,\quad {\bf V}\cdot {\bf V}^\dagger={\bf 1}$$
Amennyiben ${\bf A}$ valós, ${\bf U}$, ${\bf S}$ és ${\bf V}$ is valósak,
tehát ${\bf U}$ és ${\bf V}$ ortogonális mátrixok.
Ha ${\bf A}$ $n\times m$ típusú, akkor ${\bf U}$ $n\times n$-es, ${\bf V}$
$m\times m$-es, míg ${\bf S}$ csupa nullát tartalmazó sorokkal vagy
oszlopokkal $n\times m$-esre bővítendő.
Legyen
$${\bf M}={\bf A}\cdot{\bf A}^\dagger$$
és
$${\bf N}={\bf A}^\dagger\cdot{\bf A}$$
Ekkor ${\bf M}$ $n\times n$-es, hermitikus, pozitív definit, míg
${\bf N}$ $m\times m$-es, hermitikus, pozitív definit. Mindkét mátrixnak
ugyanazok a sajátértékei: $|S_{i,i}|^2$-tel egyenlők (ha több is van, azok
nullák). ${\bf M}$ sajátvektorai ${\bf U}$ oszlopai, ${\bf N}$ sajátvektorai
${\bf V}$ oszlopai. Ui. ${\bf A}$ szinguláris érték felbontását felhasználva
$${\bf M}={\bf A}\cdot{\bf A}^\dagger={\bf U}\cdot {\bf S}\cdot {\bf
V}^\dagger\cdot {\bf V}\cdot {\bf S}^\dagger\cdot {\bf U}^\dagger={\bf U}\cdot
{\bf S}\cdot {\bf S}^\dagger\cdot {\bf U}^\dagger$$
ill.
$${\bf N}={\bf A}^\dagger\cdot{\bf A}={\bf V}\cdot {\bf S}^\dagger\cdot
{\bf U}^\dagger\cdot {\bf U}\cdot {\bf S}\cdot {\bf
V}^\dagger={\bf V}\cdot
{\bf S}^\dagger\cdot {\bf S}\cdot {\bf V}^\dagger$$
Fordítva, a szinguláris érték felbontás bizonyítása:
${\bf M}$ és ${\bf N}$ hermitikus és pozitív definit, ezért léteznek
olyan $n\times n$-es ill. $m\times m$-es unitér ${\bf U}$ és ${\bf V}$
mátrixok, továbbá nemnegatív $n\times n$-es ill. $m\times m$-es ${\bf D_1}$ és
${\bf D_2}$ diagonálmátrixok úgy, hogy
$${\bf M}={\bf U}\cdot{\bf D_1}\cdot{\bf U}^\dagger$$
és
$${\bf N}={\bf V}\cdot{\bf D_2}\cdot{\bf V}^\dagger$$
Legyen
$$ {\bf S}={\bf U}^\dagger\cdot{\bf A}\cdot{\bf V}$$
Ezzel nyilvánvalóan
$$ {\bf A}={\bf U}\cdot{\bf S}\cdot{\bf V}^\dagger$$
Számítsuk ki ezzel az alakkal újra $ {\bf M}$-et:
$${\bf M}={\bf A}\cdot{\bf A}^\dagger={\bf U}\cdot{\bf S}\cdot{\bf
S}^\dagger\cdot{\bf U}^\dagger$$
Ezt öszehasonlítva $ {\bf M}$ előbbi felbontásával, kapjuk, hogy
$${\bf S}\cdot{\bf S}^\dagger={\bf D_1}$$
Hasonlóan,
$${\bf N}={\bf A}^\dagger\cdot{\bf A}={\bf V}\cdot{\bf S}^\dagger\cdot{\bf
S}\cdot{\bf V}^\dagger$$
és
$${\bf S}^\dagger\cdot{\bf S}={\bf D_2}$$
Ezt megszorozzuk balról ${\bf S}$-sel, és felhasználjuk a másik hasonló
összefüggést. Kapjuk:
$${\bf D_1}\cdot{\bf S}={\bf S}\cdot{\bf D_2}$$
Mindkét oldal $i,j$ elemét felírva kapjuk (nincs összegzés a többször
előforduló indexekre!):
$$(D_1)_{i,i}S_{i,j}=S_{i,j}(D_2)_{j,j}$$
Ha tehát $i\ne j$ és $(D_1)_{i,i}\ne (D_2)_{j,j}$, az következik, hogy
$S_{i,j}=0$. Tehát az ${\bf S}$ mátrixnak csak a diagonális elemei különböznek
nullától. Így viszont
$$ (D_1)_{i,i}=(D_2)_{i,i}=|S_{ii}|^2$$
Ha ${\bf A}$ négyzetes mátrix, determinánsának abszolút értéke ${\bf S}$
diagonális elemei abszolút értékének szorzatával egyenlő:
$$\left|{\rm det}{\bf A}\right|=\left|{\rm det}{\bf U}\right|\left|{\rm det}{\bf
S}\right| \left|{\rm det}{\bf V}^\dagger\right|=\left|{\rm det}{\bf
S}\right|=\Pi_{i=1}^n \left|S_{i,i}\right|$$
Lineáris egyenletrendszer megoldása:
$${\bf A}\cdot{\bf x}={\bf b}$$
$${\bf U}\cdot {\bf S}\cdot {\bf V}^\dagger\cdot{\bf x}={\bf b}$$
$${\bf S}\cdot {\bf V}^\dagger\cdot{\bf x}={\bf U}^\dagger\cdot{\bf b}$$
${\bf w}={\bf V}^\dagger\cdot{\bf x}$ és ${\bf q}={\bf U}^\dagger\cdot{\bf b}$
definícióval
$${\bf S}\cdot{\bf w}={\bf q}$$
Szinguláris eset: akkor lesz ${\bf w}$ a legrövidebb, ha az $S_{i,i}=0$-hoz
tartozó $w_i=0$. Másrészt $|{\bf w}|=|{\bf x}|$.
Ritka mátrixok, konjugált gradiens módszer
bene@arpad.elte.hu