Kapitola 11
Numerická lineární algebra. QR a SVD rozklad
QR rozklad (faktorizace)
Základní myšlenka QR rozkladu je následující: sloupce matice \(A\) jsou vektory, jejichž lineární obal tvoří obor hodnot \(R(A)\) zobrazení \(Ax\), volíme-li \(x\) libovolně. Neboli
\begin{equation}\label{eq:10:sloupce_jako_vektory} \left( a_1 \,\middle|\, a_2 \,\middle|\, \dots \,\middle|\, a_n \right) \begin{pmatrix} x_1 \\ \vdots \\ x_n \end{pmatrix} = x_1 \begin{pmatrix} a_1 \end{pmatrix} + x_2 \begin{pmatrix} a_2 \end{pmatrix} + \dots + x_n \begin{pmatrix} a_n \end{pmatrix} , \end{equation}kde \(A\) je matice \(m \times n\), \(m \geq n\).
Vektory \(a_1, \dots, a_n\) dávají postupně podprostory (lineární obaly)
\[ \mathcal{L}(a_1) \,,\; \mathcal{L}(a_1, a_2) \,, \dots \qquad \mathcal{L}(a_1, \dots, a_n) = R(A) , \]přičemž v nich můžeme postupně konstruovat ortonormální bázi \(q_1, \dots, q_n\) (za předpokladu úplné hodnosti matice \(A\)) takovou, že \(\mathcal{L}(a_1) = \mathcal{L}(q_1)\), \(\mathcal{L}(a_1, a_2) = \mathcal{L}(q_1, q_2)\) atd.
Vektory \(a_i\) pak můžeme vyjádřit v bázi \(q_i\) například takto:
\begin{equation}\label{eq:10:qr_rozepsane} \begin{aligned} a_1 &= r_{11} q_1 \\ a_2 &= r_{12} q_1 + r_{22} q_2 \\ &\;\;\vdots \\ a_n &= r_{1n} q_1 + \dots + r_{nn} q_n \end{aligned} \qquad (\Longleftrightarrow) \qquad \left( a_1 \,\middle|\, \dots \,\middle|\, a_n \right) = \left( q_1 \,\middle|\, \dots \,\middle|\, q_n \right) \begin{pmatrix} r_{11} & r_{12} & \dots & r_{1n} \\ 0 & r_{22} & \dots & r_{2n} \\ \vdots & & \ddots & \\ 0 & \dots & 0 & r_{nn} \end{pmatrix} , \end{equation}tj.
\begin{equation}\label{eq:10:redukovany_qr} A = \hat{Q} \cdot \hat{R} , \end{equation}kde \(\hat{Q}\) je obecně část (pro \(m > n\)) ortonormální matice \(Q\) splňující \(Q^\dagger Q = Q Q^\dagger = \mathbf{1}\) a \(\hat{R}\) je horní trojúhelníková matice.
Tomuto rozkladu se říká redukovaný QR rozklad (reduced). Pokud \(\hat{Q}\) doplníme na \(Q\) libovolnými vektory ortogonálními na \(q_1, \dots, q_n\) a \(\hat{R}\) doplníme řádky s nulami, dostaneme plný QR rozklad.
Blokové schéma plného QR rozkladu \(A(m \times n) = Q(m \times m) \cdot R(m \times n)\). Bloky se kreslí v poměru podle posuvníků \(m\) a \(n\) a odstín každé buňky odpovídá velikosti prvku spočteného Householderovou triangularizací náhodné matice. Přepínáním mezi plným a redukovaným rozkladem uvidíte, jak v \(Q\) přibude \(m-n\) doplněných sloupců (oddělených svislou čarou) a v \(R\) stejně vysoký nulový blok pod trojúhelníkem — a že se přitom součin \(Q\cdot R\) vůbec nezmění, jak potvrzují kontrolní normy pod plátnem.
Existence a jednoznačnost
Lze ukázat, že každá matice \(A \in \mathbb{C}^{m \times n}\), \(m \geq n\), má QR rozklad, a tedy i rozklad \(\hat{Q}\hat{R}\); plyne to z přímé konstrukce pomocí Gramovy–Schmidtovy ortogonalizace.
Je-li navíc hodnost \(A = n\) (tedy maximální), pak existuje právě jeden rozklad \(\hat{Q}\cdot\hat{R}\) s \(r_{jj} > 0\), tj. s \(r_{jj}\) reálným a kladným, čímž fixujeme „fázi“ vektoru \(q_j\).
Pokud je hodnost \(A < n\), pak pro určité \(j\) budou vektory \(q_1, \dots, q_j\) lineárně závislé, pak bude \(r_{jj} = 0\) a jako \(q_j\) volíme libovolný normovaný vektor kolmý na \(q_1, \dots, q_{j-1}\).
Použití na řešení soustavy \(Ax = b\)
Máme-li matici \(A\) typu \((m \times m)\) a její rozklad \(Q\cdot R\), pak řešení \(x\) dostaneme přímo zpětnou substitucí pro
\begin{equation}\label{eq:10:zpetna_substituce} Rx = Q^\dagger b , \end{equation}neboť \(Q^\dagger\) je inverzní k \(Q\).
U některých metod (např. u Householderovy triangularizace) se \(Q\) přímo nekonstruuje — z \(A\) dostáváme rovnou \(R\) — a v průběhu výpočtu \(R\) se počítá i \(Q^\dagger b\).
Výpočet QR rozkladu
K výpočtu QR rozkladu se používá několik metod; u každé uvádíme i počet operací.
- 1) Přímá Gramova–Schmidtova ortogonalizace, \(\sim 2mn^2\) operací. Není obecně stabilní, ztrácí se ortogonalita kvůli zaokrouhlovacím chybám.
- 2) Modifikovaná Gramova–Schmidtova ortogonalizace, \(\sim 2mn^2\) operací. Je o něco lepší, ale také ne zcela přesná.
- 3) Householderova triangularizace, \(\sim 2mn^2 - \frac{2}{3}n^3\) operací. Jde o nejlepší metodu, je zpětně stabilní.
- 4) Givensovy rotace, \(\sim 3mn^2\) operací. Jsou o něco pomalejší, ale mají své uplatnění např. v iteračních metodách (viz např. metoda GMRES v letním semestru).
Přímá konstrukce pomocí Gramovy–Schmidtovy ortogonalizace
Z matice \(A\) typu \(m \times n\) dává tato metoda redukovaný QR rozklad. Ortogonalizujeme postupně \(a_2\) na \(a_1\), pak \(a_3\) na \(a_1\) a \(a_2\) atd., a zároveň normalizujeme. Předpokládáme přitom plnou hodnost \(A\); jinak je nutno testovat, zda \(r_{jj} = 0\), a případně volit \(q_j\) jinak.
Algoritmus je následující:
\begin{align*} &\text{pro } j = 1, \dots, n \\ &\quad q_j = a_j \\ &\quad \text{pro } i = 1, \dots, j-1 \\ &\qquad r_{ij} = q_i^\dagger a_j \\ &\qquad q_j = q_j - r_{ij} q_i \\ &\quad r_{jj} = \|q_j\|_2 \\ &\quad q_j = q_j / r_{jj} \end{align*}Dvojice řádků \(r_{ij} = q_i^\dagger a_j\) a \(q_j = q_j - r_{ij} q_i\) provádí ortogonalizaci: pokud je \(a_j\) blízko \(q_i\), jde o odečítání dvou blízkých čísel (vektorů), a tedy \(\Rightarrow\) ztráta přesnosti a ortogonality. Poslední dva řádky, \(r_{jj} = \|q_j\|_2\) a \(q_j = q_j / r_{jj}\), provádějí normalizaci.
Vnitřní část algoritmu představuje \(\sim 4m\) operací a opakuje se \(\sim \frac{n^2}{2}\)-krát, celkem tedy \(O(2mn^2)\) operací.
Modifikovaná Gramova–Schmidtova metoda
Ve standardní Gramově–Schmidtově metodě jsou jednotlivá \(q_j\) dána jako \(P_j a_j\), tj. projektorem
\begin{equation}\label{eq:10:projektor_pj} P_j = I - q_1 q_1^\dagger - \dots - q_{j-1} q_{j-1}^\dagger \end{equation}na podprostor kolmý na \(\mathcal{L}(q_1, \dots, q_{j-1}) = \mathcal{L}(a_1, \dots, a_{j-1})\) (alespoň v přesné aritmetice).
Díky ortogonalitě vektorů \(q_i\) lze tento projektor napsat jako součin projektorů
\begin{equation}\label{eq:10:soucin_projektoru} P_j = P_{\perp q_{j-1}} P_{\perp q_{j-2}} \dots P_{\perp q_2} P_{\perp q_1} \quad , \text{ kde } P_{\perp q_i} = I - q_i q_i^\dagger . \end{equation}Takto je to numericky výhodnější: \(P_j\) má hodnost \(m - (j-1)\), kdežto \(P_{\perp q_i}\) mají stále hodnost \(m - 1\).
Algoritmus modifikované Gramovy–Schmidtovy metody vypadá takto:
\begin{align*} &\text{pro } i = 1, \dots, n \\ &\quad q_i = a_i \qquad\qquad (\text{inicializace všech } q_i) \\ &\text{pro } i = 1, \dots, n \\ &\quad r_{ii} = \|q_i\|_2 \\ &\quad q_i = q_i / r_{ii} \\ &\quad \text{pro } j = i+1, \dots, n \\ &\qquad r_{ij} = q_i^\dagger q_j \\ &\qquad q_j = q_j - r_{ij} q_i \end{align*}Dvojice řádků \(r_{ii} = \|q_i\|_2\) a \(q_i = q_i / r_{ii}\) provádí normalizaci (opět neošetřujeme, zda \(r_{ii} = 0\)); jde přitom opět o \(\sim 4m\) operací. Poslední dva řádky, \(r_{ij} = q_i^\dagger q_j\) a \(q_j = q_j - r_{ij} q_i\), představují postupnou ortogonalizaci všech vektorů \(q_j\) najednou — i zde dochází ke ztrátě přesnosti, ale menší. Celkem je i zde potřeba \(O(2mn^2)\) operací.
Trojúhelníková versus ortogonální triangularizace
Gramova–Schmidtova ortogonalizace je vlastně trojúhelníková ortogonalizace, neboť ji jde přepsat jako
\begin{equation}\label{eq:10:trojuhelnikova_ortogonalizace} A R_1 R_2 \dots R_n = \hat{Q} , \end{equation}kde
\[ R_1 = \begin{pmatrix} \frac{1}{r_{11}} & -\frac{r_{12}}{r_{11}} & \cdots & -\frac{r_{1n}}{r_{11}} \\ 0 & 1 & 0 & \cdots & 0 \\ \vdots & & \ddots & & 0 \\ 0 & \cdots & 0 & & 1 \end{pmatrix} \]a obecně
\[ R_i = \begin{pmatrix} 1 & & & 0 & & \\ & \ddots & & & & \\ & & 1 & & & \\ & & \frac{1}{r_{ii}} & -\frac{r_{i\,i+1}}{r_{ii}} & \cdots & -\frac{r_{in}}{r_{ii}} \\ & 0 & & 1 & & 0 \\ & & & & \ddots & \\ & & & & & 1 \end{pmatrix} , \]přičemž \(\hat{R} = R_n^{-1} R_{n-1}^{-1} \dots R_1^{-1}\).
Myšlenka Householderovy a Givensovy metody je opačná: jde v nich o ortogonální triangularizaci.
Householderova triangularizace
Nyní budeme převádět \(A\) na horní \(\triangle\) tvar pomocí ortogonálních matic \(Q_1, \dots, Q_n\), tj.
\begin{equation}\label{eq:10:householder_princip} \underbrace{Q_n \dots Q_1}_{Q^\dagger} A = R , \end{equation}a dostaneme tak plný QR rozklad.
Matice \(Q_1, \dots, Q_n\) musí být takové, aby nulovaly prvky pod diagonálou, tj.
\[ \begin{array}{ccccccc} A & \xrightarrow{\;Q_1\;} & \begin{pmatrix} x & x & x & \cdots & x \\ 0 & x & & & \vdots \\ \vdots & x & & & \\ \vdots & \vdots & & & \vdots \\ 0 & x & \cdots & & x \end{pmatrix} & \xrightarrow{\;Q_2\;} & \begin{pmatrix} x & x & x & \cdots & x \\ 0 & x & x & & \vdots \\ 0 & 0 & x & & \vdots \\ \vdots & \vdots & \vdots & & \vdots \\ 0 & 0 & x & \cdots & x \end{pmatrix} & \quad \text{atd.} \\[2ex] & & Q_1 A & & Q_2 Q_1 A & \end{array} \]kde \(x\) zde značí obecně nenulovou hodnotu.
To lze provést např. Householderovým zrcadlením
\begin{equation}\label{eq:10:qk_blokove} Q_k = \left. \begin{pmatrix} I & 0 \\ 0 & F \end{pmatrix} \right\} \begin{aligned} &k-1 \text{ řádků} \\ &m-(k-1) \text{ řádků} \end{aligned} \end{equation}(první blok tvoří \(k-1\) řádků, druhý blok \(m-(k-1)\) řádků), kde \(F\) je takové, aby z vektoru tvořeného prvky od diagonály dolů v \(k\)-tém sloupci udělalo násobek jednotkového vektoru \(e_1\):
\begin{equation}\label{eq:10:zrcadleni_ucinek} \begin{pmatrix} x_1 \\ \vdots \\ x_p \end{pmatrix} \;\xrightarrow{F}\; \begin{pmatrix} \|x\|_2 \\ 0 \\ \vdots \\ 0 \end{pmatrix} = \|x\|_2 e_1 . \end{equation}Zrcadlení v rovině: vektor \(x\) vycházející z počátku, dvě čárkované nadroviny \(H^+\) a \(H^-\), obrazy \(F^+x = +\|x\|e_1\) a \(F^-x = -\|x\|e_1\) na vodorovné ose a bod \(z\) na spojnici. Konec vektoru \(x\) je uchopitelný myší i prstem; nadroviny, vektory \(v = \pm\|x\|e_1 - x\), projekce \(Px = x - z\) i celá matice \(F = I - 2\,vv^\dagger/(v^\dagger v)\) se dopočítávají průběžně. Tlačítkem „x blízko \(\|x\|e_1\)“ si ověřte, proč se \(v\) volí podle \(\text{sign}(x_1)\): druhá volba dává nepatrné \(\|v\|\), tedy odečítání dvou blízkých vektorů.
Matice \(F\) tedy musí provést zrcadlení v „nadrovině“ \(H^+ \perp v = \|x\|e_1 - x\), případně v „nadrovině“ \(H^- \perp v = -\|x\|e_1 - x\), pokud je \(x\) příliš blízko \(\|x\|e_1\).
Projekce do \(H^+\) je dána projektorem
\[ Px = \left(I - \frac{vv^\dagger}{v^\dagger v}\right)x = x - z , \]ovšem my potřebujeme, aby \(Fx = x - 2z\), neboli
\begin{equation}\label{eq:10:householderova_matice} Fx = \left(I - 2\,\frac{vv^\dagger}{v^\dagger v}\right)x . \end{equation}Vektor \(v\) se obvykle volí podle znaménka \(x_1\), tj. \(v = -\text{sign}(x_1)\|x\|e_1 - x\). Protože však \(F\) na znaménku vektoru \(v\) nezávisí, lze vzít jednoduše
\begin{equation}\label{eq:10:volba_v} v = \text{sign}(x_1)\|x\|e_1 + x \qquad (\text{a např. } \text{sign}(0) = 1) . \end{equation}Algoritmus pak upravuje \(A\) na \(R\) takto:
\begin{align*} &\text{pro } k = 1,\dots,n \\ &\quad x = A_{k:m,k} && (\text{proměnlivá délka } x!) \\ &\quad v_k = \text{sign}(x_1)\|x\|_2 e_1 + x && (\text{volba } v) \\ &\quad v_k = v_k / \|v_k\|_2 && (\text{normalizace } v) \\ &\quad A_{k:m,k:n} = A_{k:m,k:n} - 2 v_k \left(v_k^\dagger A_{k:m,k:n}\right) \end{align*}Dvojku v posledním řádku lze přitom „schovat“ do \(v_k\).
Poslední řádek je nejnáročnější částí algoritmu: upravuje se \(\sim(m-k)\cdot(n-k)\) prvků, vždy 4 operace. Celkový počet upravovaných prvků odpovídá objemu klínovitého tělesa (viz interaktivní ukázka Objem klínu), tedy \(\frac{1}{2}mn^2 - \frac{1}{6}n^3\), což krát 4 operace dává celkem \(\sim 2mn^2 - \frac{2}{3}n^3\) operací.
Klínovité těleso (zkosený hranol) s popisky \(m\), \(n\) a \(m-n\), poskládané z vrstev: vrstva \(k\) odpovídá \(k\)-tému kroku Householderovy triangularizace, v němž se upravuje podmatice \(A_{k:m,k:n}\). Posuvníky \(m\) a \(n\) mění tvar klínu, posuvník \(k\) zvýrazní jednu vrstvu; ta má \((m-k)(n-k)\) prvků, což je model používaný pro odhad počtu operací — skutečně upravovaných prvků je \((m-k+1)(n-k+1)\) a vypisuje se obojí. Pod plátnem se počítá přesný součet vrstev a jeho poměr k objemu \(\frac{1}{2}mn^2 - \frac{1}{6}n^3\) — zkuste zvětšovat \(m\) a \(n\) a sledovat, jak se poměr blíží jedné.
Matice \(Q\) se často nekonstruuje, ale počítá se buď \(Q^\dagger b\) (kde \(Q^\dagger = Q_n \dots Q_1\))
\begin{align*} &Q^\dagger b : \quad \text{pro } k = 1,\dots n \\ &\qquad\qquad b_{k:m} = b_{k:m} - 2v_k\left(v_k^\dagger b_{k:m}\right) \end{align*}nebo \(Qb\) (neboť \(Q = Q_1 \dots Q_n\), jelikož \(Q_i^\dagger = Q_i\))
\begin{align*} &Qb : \quad \text{pro } k = n,\dots,1 \\ &\qquad\qquad b_{k:m} = b_{k:m} - 2v_k\left(v_k^\dagger b_{k:m}\right) \end{align*}Zde je nutné uchovat vektory \(v_k\)! Obě tyto úpravy \(b_{k:m}\) představují už jen \(\sim 4mn\) operací.
Pokud potřebujeme přímo matici \(Q\), působíme takto na jednotkovou matici, tj. na vektory \(e_j\).
Givensovy rotace
Givensovy rotace používají místo zrcadlení otočení, ale nebudeme je zde podrobněji probírat.
Stabilita Householderovy triangularizace
Lze ukázat, že Householderova triangularizace je zpětně stabilní, tj. pro spočtené \(\tilde{Q}\) a \(\tilde{R}\) platí pro určité \(\delta A \in \mathbb{C}^{m \times n}\)
\begin{equation}\label{eq:10:zpetna_stabilita} \tilde{Q}\cdot\tilde{R} = A + \delta A \ , \qquad \frac{\|\delta A\|}{\|A\|} = \mathcal{O}(\varepsilon_M) . \end{equation}Též řešení soustavy \(Ax = b\) je stabilní, pokud ji řešíme pomocí \(Q\cdot R = A\) a následně \(y = Q^\dagger b\) a \(x = R^{-1}y\).
Pozor ovšem na podmíněnost úlohy: obecně budou jak \(\tilde{Q}\) a \(\tilde{R}\), tak \(\tilde{x}\) mít chybu \(\mathcal{O}(\kappa(A)\varepsilon_M)\), kde
\begin{equation}\label{eq:10:cislo_podminenosti} \kappa(A) = \|A\|\|A^{-1}\| = \frac{\sigma_1}{\sigma_m} , \end{equation}přičemž \(\sigma_1\) a \(\sigma_m\) jsou největší a nejmenší singulární hodnoty.
Singulární rozklad matice (SVD)
Singulární rozklad matice (Singular Value Decomposition — SVD) vychází z následující představy. Matice \(A\) typu \(m \times n\) zobrazuje vektory \(x\) z \(\mathbb{R}^n\) do prostoru \(\mathcal{R}(A) \subset \mathbb{R}^m\), přitom jednotkové vektory z \(\mathbb{R}^n\) (1-sféru) zobrazí na hyperelipsu v \(\mathbb{R}^m\).
Vlevo jednotková kružnice \(S\) v \(\mathbb{R}^n\) s vektory \(\vec{v}_1, \vec{v}_2\), uprostřed šipka \(A\) a vpravo natočená elipsa v \(\mathbb{R}^m\) s poloosami \(\sigma_1\vec{u}_1\) a \(\sigma_2\vec{u}_2\). Zelené body vpravo jsou obrazy \(e_1\) a \(e_2\), tedy přímo sloupce matice \(A\) — tažením jimi měníte matici a elipsa se překresluje. Singulární hodnoty i vektory se počítají SVD (Jacobiho rotace na \(A^\dagger A\)). Tlačítkem „singulární matice“ uděláte sloupce rovnoběžné: \(\sigma_2\) klesne na nulu, směr zdegeneruje a elipsa se zhroutí na úsečku.
Přitom některé směry mohou být degenerované, \(\sigma_i = 0\) (pro matice, které nemají hodnost \(n\)).
Lze najít ortonormální bázi v \(\mathbb{R}^n\) (vektory \(\vec{v}_1, \vec{v}_2 \dots\)) takovou, že
\begin{equation}\label{eq:10:singularni_vztah} A\vec{v}_i = \sigma_i \vec{u}_i , \end{equation}kde \(\vec{u}_i\) jsou jednotkové vektory ve směrech hlavních poloos hyperelipsy a \(\sigma_i\) budou seřazeny, tj. \(\sigma_1 \geq \sigma_2 \geq \dots \geq \sigma_n \geq 0\).
Maticově zapsáno
\[ \overset{m\times n}{A}\ \overset{n\times n}{\left(\begin{array}{c|c|c|c} v_1 & v_2 & \dots & v_n\end{array}\right)} = \overset{m\times n}{\left(\begin{array}{c|c|c|c} u_1 & u_2 & \dots & u_n\end{array}\right)} \overset{n\times n}{\begin{pmatrix} \sigma_1 & & & 0 \\ & \sigma_2 & & \\ & & \ddots & \\ 0 & & & \sigma_n \end{pmatrix}} , \]neboli
\begin{equation}\label{eq:10:svd_redukovane} A\hat{V} = \hat{U}\hat{\Sigma} \qquad \Rightarrow \qquad A = \hat{U}\hat{\Sigma}\hat{V}^\dagger . \end{equation}Přitom \(\hat{V}\) je unitární a \(\hat{U}\) splňuje \(\hat{U}^\dagger\hat{U} = \mathbf{1}_{n\times n}\).
Blokové schéma redukovaného rozkladu: šrafovaný obdélník \(A\), rovnítko, pruhovaný obdélník \(\hat{U}\), čtvereček \(\hat{\Sigma}\) s diagonálou a dvěma nulami a čtvereček \(\hat{V}^\dagger\). Bloky mají rozměry podle posuvníků \(m\) a \(n\) a odstíny buněk odpovídají hodnotám ze SVD náhodné matice. Posuvník „hodnost \(A\)“ vyrábí matice s nižší hodností — poslední singulární hodnoty spadnou na nulu, jak je vidět na sloupečkovém grafu pod \(\hat{\Sigma}\). Kontrolní normy pod plátnem ukazují, že \(\hat{U}^\dagger\hat{U} = \mathbf{1}\) platí vždy, kdežto \(\hat{U}\hat{U}^\dagger = \mathbf{1}\) pro \(m > n\) nikoli.
Hodnoty \(\sigma_i\) jsou tzv. singulární hodnoty (na rozdíl od vlastních čísel jsou reálné), \(u_i\) jsou levé singulární vektory a \(v_i\) jsou pravé singulární vektory.
Doplněním báze v \(\mathbb{R}^m\) dostaneme tzv. plný singulární rozklad; každá matice je tedy diagonální ve vhodné bázi.
Blokové schéma plného rozkladu \(A = U\Sigma V^\dagger\): silná svislá čára uvnitř \(U\) odděluje sloupce vzniklé doplněním báze a v \(\Sigma\) jsou nulové bloky. Posuvníkem \(k\) se navíc oranžově zvýrazní prvních \(k\) sloupců \(U\), prvních \(k\) hodnot \(\sigma\) a prvních \(k\) řádků \(V^\dagger\), tedy dyadický rozvoj \(A_k = \sum_{j\le k}\sigma_j u_j v_j^\dagger\) podle \eqref{eq:10:dyadicky_rozvoj}. Pod plátnem se počítá \(\|A - A_k\|_2\) a porovnává se s \(\sigma_{k+1}\) — právě v tom je smysl „nejlepší aproximace \(A\)“ maticí dané hodnosti.
Pro \(m < n\) se rozkládá \(A^T\).
Každá matice \(A\) typu \(m\times n\) má SVD rozklad. Navíc \(\{\sigma_i\}\) jsou dány jednoznačně, a pokud jsou navzájem různé, pak i \(\{u_i\}\) a \(\{v_i\}\) jsou dány jednoznačně až na komplexní fázi (\(\pm 1\) u reálných matic).
Indukcí: nechť existuje SVD pro matici \((m-1)\times(n-1)\). Položme
\[ \sigma_1 = \|A\|_2 = \sup_{x \neq 0} \frac{\|Ax\|_2}{\|x\|_2} = \sup_{\|x\|_2 = 1} \|Ax\|_2 . \]Určitě existují \(v_1\) a \(u_1\) takové, že
\[ \|v_1\|_2 = 1 \ , \quad \|u_1\|_2 = 1 \quad \text{a} \quad Av_1 = \sigma_1 u_1 . \]Doplněním \(v_1\) a \(u_1\) na ortonormální bázi (libovolně) dostaneme unitární matice \(U_1\) a \(V_1\), pro které
\[ U_1^\dagger A V_1 = S = \begin{pmatrix} \sigma_1 & w^\dagger \\ 0 & B\end{pmatrix} , \]a platí
\[ \left\|S\begin{pmatrix}\sigma_1\\ w\end{pmatrix}\right\|_2 \geq \sigma_1^2 + w^\dagger w = \left(\sigma_1^2 + w^\dagger w\right)^{1/2}\left\|\begin{pmatrix}\sigma_1\\ w\end{pmatrix}\right\|_2 . \]Odtud \(\|S\|_2 \geq \left(\sigma_1^2 + w^\dagger w\right)^{1/2}\), ale \(U_1, V_1\) jsou unitární, a tedy \(\|S\|_2 = \|A\|_2 = \sigma_1\), z čehož plyne \(w = 0\); zbytek plyne indukcí.
□Základní vlastnosti SVD rozkladu
SVD vyjadřuje možnou změnu báze v \(\mathbb{R}^m\) a \(\mathbb{R}^n\) tak, aby
\begin{equation}\label{eq:10:zmena_baze} b = Ax \quad \text{přešlo na} \quad b' = \Sigma x', \ \text{kde} \ x' = V^\dagger x \ \text{a} \ b' = U^\dagger b . \end{equation}Rozdíl oproti vlastním hodnotám a vektorům je následující. Ty mají smysl jen pro čtvercové matice a rozklad \(A = X \Lambda X^{-1}\) existuje jen pro nedefektní matice (viz později), přičemž oba prostory jsou ve stejné bázi. Pokud je matice hermitovská \((A = A^\dagger)\), pak lze \(\lambda_i\) volit tak, že \(\sigma_i = |\lambda_i|\).
Hodnost matice \(A\) je rovna hodnosti \(\Sigma\) (\(U\) i \(V\) mají plnou hodnost), a tedy
\[ \Rightarrow \ \# \text{ nenulových } \sigma_i \ \text{ určuje hodnost } A . \]Pokud je \(r\) nenulových \(\sigma_i\), pak \(\mathcal{R}(A) = \mathcal{L}(u_1, \dots, u_r)\) a \(\mathrm{Ker}(A) = \mathrm{null}(A) = \mathcal{L}(v_{r+1}, \dots, v_n)\).
Dále platí
\begin{equation}\label{eq:10:normy} \|A\|_2 = \sigma_1 = \max \sigma_i = \|\Sigma\|_2 \qquad \text{a} \qquad \|A\|_F = \left(\sum_{i,j} |a_{ij}|^2\right)^{1/2} = \sqrt{\sigma_1^2 + \sigma_2^2 + \dots + \sigma_r^2} . \end{equation}Sestrojme matici \(A^\dagger A\) typu \(n \times n\); pak
\begin{equation}\label{eq:10:ada} A^\dagger A = (U \Sigma V^\dagger)^\dagger (U \Sigma V^\dagger) = V(\Sigma^\dagger \Sigma) V^\dagger , \end{equation}a tedy \(A^\dagger A\) a \(\Sigma^\dagger \Sigma\) mají stejná vlastní čísla \(\sigma_1^2, \sigma_2^2, \dots, \sigma_n^2\).
Pro matici \(A\) typu \(m \times m\) je
\begin{equation}\label{eq:10:determinant} \det(A) = \prod_{i=1}^{m} \sigma_i . \end{equation}Rozepsáním \(\Sigma\) na součet matic tvaru
\[ \begin{pmatrix} 0 & & 0 \\ & \sigma_i & \\ 0 & & 0 \end{pmatrix} \]dostaneme (přes počet \(r\) nenulových \(\sigma_i\))
\begin{equation}\label{eq:10:dyadicky_rozvoj} A = \sum_{j=1}^{r} \sigma_j u_j v_j^\dagger , \end{equation}odkud \(\Rightarrow\) aproximace \(A\) omezením na velká \(\sigma_i\), tedy „nejlepší aproximace \(A\)“ pomocí matice určité hodnosti.
Výpočet SVD rozkladu (nástin)
Přímočaré by bylo najít vlastní čísla \(A^\dagger A = V \Lambda V^\dagger\) a spočítat \(\Sigma\) jako odmocninu \(\Lambda\), pak vyřešit \(U\Sigma = AV\) (např. QR faktorizací). Ukazuje se ovšem, že jde o nestabilní algoritmus, pokud některá \(\sigma_k \ll \|A\|\).
Stabilní algoritmus je založen na převedení na bidiagonální matici.
Převod matice na bidiagonální tvar: vyšrafovaná matice \(A\) s rozměry \(m\) a \(n\), šipka na matici se šikmým pruhem a nulami a druhá šipka na matici s bidiagonální strukturou. Prostřední matice se počítá Golubovou–Kahanovou bidiagonalizací (Householderovy reflexe zleva i zprava) a přepínačem si vybíráte fázi. Pod plátnem porovnejte singulární hodnoty \(A\) a \(B\): ortogonální transformace je nemění (stejně jako Frobeniovu normu), takže druhá — levná, \(O(n^2)\) — fáze už opravdu může pracovat jen s bidiagonální maticí.
První přeměnu obstarává Golubova–Kahanova bidiagonalizace, \(O(mn^2)\), přesněji \(4mn^2 - \frac{4}{3}n^3\) operací. Druhou přeměnu pak velmi efektivní iterační metody, \(O(n^2)\), založené na QR faktorizaci nebo na metodě rozděl a panuj.
Pro bidiagonalizaci se používají např. Householderovy reflexe zleva i zprava.
Householderovy reflexe krok za krokem — v matici postupně přibývají nuly. Posloupnost si odkrokujete sami: reflexe zleva a zprava se v prvních krocích střídají, pravé reflexe ale existují jen pro \(k \le n-2\), takže poslední kroky jsou vždy jen zleva (popisek pod maticí říká, o který krok jde). Oranžově svítí prvky, které se právě změnily, a „0“ znamená skutečnou nulu, ne malé číslo. Sledujte, že Frobeniova norma zůstává během celého procesu konstantní — reflexe jsou ortogonální.
Pro \(m \gg n\) to jde i lépe, až \(2mn^2 + 2n^3\) operací.