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
2. hét
Lineáris algebra
Tipikus lineáris problémák:
- Lineáris egyenletrendszer (speciális esetek: tridiagonális mátrix, ritka mátrixok)
$${\bf A}\cdot{\bf x}={\bf b}\;,$$
- Több lineáris egyenletrendszer azonos együtthatómátrixszal
$${\bf A}\cdot{\bf x}_j={\bf b}_j\;,$$
- Mátrixinvertálás
$${\bf A}^{-1}\cdot{\bf A}={\bf A}\cdot{\bf A}^{-1}={\bf 1}\;,$$
- Determináns számítása
- Szinguláris érték dekompozíció
$${\bf A}={\bf U}\cdot {\bf S}\cdot {\bf V}^\dagger$$
- Legkisebb négyzetek módszere
$$\sum_{j=1}^M\left(y_j-\sum_{k=1}^N c_kf_k(x_j)\right)^2=min.$$
- Sajátértékproblémák
$${\bf A}\cdot{\bf v}_j=\lambda_j {\bf v}_j\;.$$
Konjugált gradiens módszer
A megoldandó lineáris egyenletrendszer legyen
$${\bf A}\cdot{\bf x}={\bf b}\;,$$
ahol ${\bf A}$ valamilyen $N\times N$-es szimmetrikus pozitív definit
mátrix.
Ez egyenértékű a
$$\frac{1}{2}\;{\bf x}^T\cdot{\bf A}\cdot{\bf x}-{\bf x}^T\cdot{\bf b}$$
kvadratikus alak minimumának meghatározásával.
Legyen ${\bf p}_1$, ${\bf p}_2,\dots {\bf p}_N$ $N$ db előre megadott
lineárisan független vektor. Az egyenletrendszer megoldása nyilván felírható
$${\bf x}=\lambda_1{\bf p}_1+\lambda_2{\bf p}_2+\dots+\lambda_N{\bf p}_N$$
alakban, ahol a $\lambda_j$ együtthatókat az előbbi kvadratikus alak, azaz
$$\sum_{j=1}^N\left(\frac{1}{2}\;{\bf p}_j^T\cdot{\bf A}\cdot{\bf
p}_j\;\lambda_j^2-{\bf p}_j^T\cdot{\bf b}\;\lambda_j\right)+\sum_{j\ne
k}\frac{1}{2}\;{\bf p}_j^T\cdot{\bf A}\cdot{\bf p}_k\;\lambda_j\lambda_k$$
minimuma határozza meg. A minimalizálás a különböző együtthatók szerint
egymástól függetlenül végezhető el, ha a minimalizálás ${\bf p}_j$
irányvektorai egymásra nézve konjugáltak, azaz
$${\bf p}_j^T\cdot{\bf A}\cdot{\bf p}_k=0\;,$$
ha $j\ne k$. Ilyen konjugált irányok a következőképpen kaphatók:
Legyen az első keresési irány
$${\bf p}_1={\bf r}_0\equiv{\bf b}\;.$$
Az ehhez tartozó $\lambda_1$ együttható a kvadratikus alak minimumából
számítható ki:
$${\bf p}_1^T\cdot{\bf A}\cdot{\bf
p}_1\;\lambda_1-{\bf p}_1^T\cdot{\bf b}=0$$
Ezzel a megoldás közelítése
$${\bf x}_1=\lambda_1{\bf p}_1\;,$$
a közelítés hibája pedig
$${\bf r}_1={\bf r}_0-\lambda_1\;{\bf A}\cdot{\bf p}_1\;.$$
A minimum feltétele ezzel felírható
$${\bf p}_1^T\cdot{\bf r}_1=0$$
alakban.
A következő keresési irány legyen
$${\bf p}_2={\bf r}_1+\beta_1{\bf p}_1\;.$$
A $\beta_1$ együtthatót a konjugáltság követelménye határozza meg:
$${\bf p}_1^T\cdot{\bf A}\cdot{\bf p}_2=0\;.$$
A minimum feltétele
$${\bf p}_2^T\cdot{\bf A}\cdot{\bf
p}_2\;\lambda_2-{\bf p}_2^T\cdot{\bf b}=0\;.$$
A megoldás következő közelítése
$${\bf x}_2={\bf x}_1+\lambda_2{\bf p}_2\;,$$
a közelítés hibája
$${\bf r}_2={\bf r}_1-\lambda_2\;{\bf A}\cdot{\bf p}_2\;.$$
A minimum feltétele felírható
$${\bf p}_2^T\cdot{\bf r}_2=0$$
alakban.
Az is teljesül, hogy
$${\bf p}_1^T\cdot{\bf r}_2=0\;.$$
Mivel azonban ${\bf p}_1={\bf r}_0$, valamint ${\bf r}_1={\bf p}_2-\beta_1{\bf
p}_1$, a fenti két egyenletből
$${\bf r}_2^T\cdot{\bf r}_0={\bf r}_2^T\cdot{\bf r}_1=0$$
következik. Mivel pedig ${\bf r}_1-{\bf r}_0=\lambda_1\;{\bf A}\cdot{\bf
p}_1$, ez azt jelenti, hogy
$${\bf r}_2^T\cdot{\bf A}\cdot{\bf
p}_1=0\;,$$
tehát az ${\bf r}_2$ maradékvektor és a ${\bf p}_1$ irányvektor konjugáltak.
Legyen ezért a soron következő irányvektor
$${\bf p}_3={\bf r}_2+\beta_2{\bf p}_2\;.$$
Általában
$${\bf p}_j={\bf r}_{j-1}+\beta_{j-1}{\bf p}_{j-1}\;,$$
$${\bf r}_j={\bf r}_{j-1}-\lambda_j\;{\bf A}\cdot{\bf p}_j\;,$$
$${\bf r}_j^T{\bf p}_{k}=0\quad k\le j$$
$${\bf r}_j^T{\bf r}_{k}=0\quad k< j$$
$${\bf r}_j^T\cdot{\bf A}\cdot{\bf p}_{k}=0\quad k< j$$
Prekondicionálás
Ritka mátrixok tárolása
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}|$.
Példák szinguláris dekompozícióra:
- Hilbert-mátrix
- Kevesebb egyenlet, mint ismeretlen
- Több egyenlet, mint ismeretlen
Az $LU$ dekompozíció speciális esetekre:
- Szimmetrikus, pozitív definit mátrix: Cholesky-dekompozíció
$${\bf A}={\bf L}{\bf L}^T$$
$${\bf L}=\left(\begin{array}{ccccc}
\alpha_{11}&0&0&\dots&0\\
\alpha_{21}&\alpha_{22}&0&\dots&0\\
\alpha_{31}&\alpha_{32}&\alpha_{33}&\dots&0\\
\vdots&&&\ddots&\vdots\\
\alpha_{N1}&\alpha_{N2}&\alpha_{N3}&\dots&\alpha_{NN}
\end{array}\right)$$
A szimmetria miatt elegendő a $j\ge k$ eseteket vizsgálni:
Ha $j= k$:
$$a_{kk}=\alpha_{k1}^2+\alpha_{k2}^2+\dots+\alpha_{kk}^2$$
Ha $j> k$:
$$a_{jk}=\alpha_{j1}\alpha_{k1}+\alpha_{j2}\alpha_{k2}+\dots+\alpha_{jk}\alpha_{kk}$$
Cholesky-felbontás (a Strout-féle algoritmus egy változata): kiválasztjuk a $k$-adik oszlopot ($k=1,2,\dots, N$
növekvő sorrendben) és
sorban megoldjuk az egyenleteket $\alpha_{jk}$-ra ($j\ge k$). A
kisebb oszlopindexű $\alpha_{jm}$
mátrixelemek a korábbi lépésekből ismertek.
Ha $j= k$:
$$\alpha_{kk}=\sqrt{ a_{kk}-\sum_{m=1}^{k-1}\alpha_{km}^2 }$$
Ha $j> k$:
$$\alpha_{jk}=\frac{1}{\alpha_{kk}}\left(a_{jk}-\sum_{m=1}^{k-1}\alpha_{jm}\alpha_{km}\right)$$
Az algoritmus nagyon stabil, főelemkiválasztás nem szükséges.
- Tridiagonális mátrix
- Szalagmátrix
bene@arpad.elte.hu