01NUM1:Kapitola6: Porovnání verzí
Z WikiSkripta FJFI ČVUT v Praze
(oprava překlepů v předchozí editaci.) |
(TYPOGRAFICKÉ CHYBY.) |
||
Řádka 13: | Řádka 13: | ||
\todo{Důkaz 6.1 vzala Hanele z feláckých vut skript (ale zdá se, že funguje), podle zápisků z přednášky není vyžadován} | \todo{Důkaz 6.1 vzala Hanele z feláckých vut skript (ale zdá se, že funguje), podle zápisků z přednášky není vyžadován} | ||
Mějme \(\lambda\) vlastní číslo \(\matice A\), \(\vec x\) příslušný vlastní vektor. Z rovnosti \(\matice A \vec x = \lambda \vec x\) rozepsáním podle definice násobení matice a vektoru dostaneme: | Mějme \(\lambda\) vlastní číslo \(\matice A\), \(\vec x\) příslušný vlastní vektor. Z rovnosti \(\matice A \vec x = \lambda \vec x\) rozepsáním podle definice násobení matice a vektoru dostaneme: | ||
− | \[(\lambda - \matice | + | \[(\lambda - \matice A_{ii}) = \sum_{j = 1, j \neq i}^n\lvert \matice A_{ij} x_j \rvert\] |
− | Vezměme \(x_k\) největší prvek \(\vec x\) v absolutní hodnotě, platí tedy \(\frac{\lvert x_j \rvert}{\lvert x_k \rvert} \leq 1 pro | + | Vezměme \(x_k\) největší prvek \(\vec x\) v absolutní hodnotě, platí tedy \(\frac{\lvert x_j \rvert}{\lvert x_k \rvert} \leq 1\) pro \(\ jneq k\). Z toho plyne \[\lvert \lambda - \matice A_{kk} \rvert \leq \sum_{j=1}^n \lvert \matice A_{kj} \rvert \frac{\lvert x_j\rvert}{\lvert x_k\rvert} \leq \sum_{j=1, j \neq k}^n \lvert \matice A_{kj} \rvert \] |
− | Tedy \(\lambda\) leží v kruhu o poloměru \(\sum_{j=1, j \neq k}^n \lvert \matice | + | Tedy \(\lambda\) leží v kruhu o poloměru \(\sum_{j=1, j \neq k}^n \lvert \matice A_{kj} \rvert\). Všechny vlastní čísla tedy leží ve sjednocení kruhů o poloměrech odpovídajících indexu i. |
\end{proof} | \end{proof} | ||
\end{theorem*} | \end{theorem*} |
Verze z 14. 11. 2016, 16:20
[ znovu generovat, | výstup z překladu ] | Kompletní WikiSkriptum včetně všech podkapitol. | |
PDF Této kapitoly | [ znovu generovat, | výstup z překladu ] | Přeložení pouze této kaptioly. |
ZIP | Kompletní zdrojový kód včetně obrázků. |
Součásti dokumentu 01NUM1
součást | akce | popis | poslední editace | soubor | |||
---|---|---|---|---|---|---|---|
Hlavní dokument | editovat | Hlavní stránka dokumentu 01NUM1 | Dedicma2 | 3. 6. 2024 | 19:49 | ||
Řídící stránka | editovat | Definiční stránka dokumentu a vložených obrázků | Dedicma2 | 3. 6. 2024 | 19:48 | ||
Header | editovat | Hlavičkový soubor | Dedicma2 | 17. 1. 2016 | 16:20 | header.tex | |
Kapitola0 | editovat | Značení | Dedicma2 | 23. 5. 2017 | 21:32 | znaceni.tex | |
Kapitola2 | editovat | Opakování a doplnění znalostí z lineární algebry | Dedicma2 | 3. 6. 2024 | 15:41 | prezentace2.tex | |
Kapitola3 | editovat | Úvod do numerické matematiky | Dedicma2 | 3. 6. 2024 | 15:51 | prezentace3.tex | |
Kapitola4 | editovat | Přímé metody pro lineární soustavy | Dedicma2 | 3. 6. 2024 | 16:47 | prezentace4.tex | |
Kapitola5 | editovat | Iterativní metody | Dedicma2 | 3. 6. 2024 | 16:59 | prezentace5.tex | |
Kapitola6 | editovat | Vlastní čísla a vektory matic | Dedicma2 | 3. 6. 2024 | 17:07 | prezentace6.tex | |
Kapitola7 | editovat | Nelineární rovnice | Kubuondr | 31. 1. 2017 | 14:27 | prezentace7.tex | |
Kapitola8 | editovat | Interpolace | Kubuondr | 31. 1. 2017 | 15:43 | prezentace8.tex | |
Kapitola9 | editovat | Derivace a integrace | Kubuondr | 31. 1. 2017 | 17:33 | prezentace9.tex |
Zdrojový kód
%\wikiskriptum{01NUM1} \section{Vlastní čísla a vektory matic} \subsection{Lokalizace vlastních čísel} \begin{theorem*}[Gershgorin] \label{Gershgorin} Nechť \( \matice A \in \mathbbm C^{n, n} \). Potom \[ \sigma ( \matice A) \subset \mathcal S_{\mathcal R} = \bigcup_{i = 1}^n \mathcal R_i \] kde definujeme \[ \mathcal R_i = \left\{ z \in \mathbbm C \; \Big | \; \lvert z - \matice A_{ii} \rvert \leq \sum_{j = 1, j \neq i}^n \lvert \matice A_{ij} \rvert \right\} \] \begin{proof} \todo{Důkaz 6.1 vzala Hanele z feláckých vut skript (ale zdá se, že funguje), podle zápisků z přednášky není vyžadován} Mějme \(\lambda\) vlastní číslo \(\matice A\), \(\vec x\) příslušný vlastní vektor. Z rovnosti \(\matice A \vec x = \lambda \vec x\) rozepsáním podle definice násobení matice a vektoru dostaneme: \[(\lambda - \matice A_{ii}) = \sum_{j = 1, j \neq i}^n\lvert \matice A_{ij} x_j \rvert\] Vezměme \(x_k\) největší prvek \(\vec x\) v absolutní hodnotě, platí tedy \(\frac{\lvert x_j \rvert}{\lvert x_k \rvert} \leq 1\) pro \(\ jneq k\). Z toho plyne \[\lvert \lambda - \matice A_{kk} \rvert \leq \sum_{j=1}^n \lvert \matice A_{kj} \rvert \frac{\lvert x_j\rvert}{\lvert x_k\rvert} \leq \sum_{j=1, j \neq k}^n \lvert \matice A_{kj} \rvert \] Tedy \(\lambda\) leží v kruhu o poloměru \(\sum_{j=1, j \neq k}^n \lvert \matice A_{kj} \rvert\). Všechny vlastní čísla tedy leží ve sjednocení kruhů o poloměrech odpovídajících indexu i. \end{proof} \end{theorem*} \subsection{Aposteriorní odhad chyby} \begin{theorem} \label{AposterioriEigenvalue} Nechť \( \matice A \in \mathbbm C^{n, n} \) je hermitovská. Nechť \( \hat \lambda \) a \( \hat{\vec x} \neq \vec 0 \) jsou napočítané aproximace vlastního čísla \( \lambda \) a vlastního vektoru \( \vec x \). Pro reziduum \[ \vec r = \matice A \hat{\vec x} - \hat \lambda \hat{\vec x} \] potom platí \[ \min\limits_{\lambda_i \in \sigma ( \matice A )} \left\lvert \hat \lambda - \lambda_i \right\rvert \leq \frac{\lVert \vec r \rVert_2}{\left\lVert \hat{\vec x} \right\rVert_2} \] \begin{proof} \( \matice A \) je hermitovská a tudíž existuje ON báze z vlastních vektorů \( \vec u_1, \ldots, \vec u_n \). Vektor \( \hat{\vec x} \) lze napsat jako \[ \hat{\vec x} = \sum_{i=1}^n \alpha_i \vec u_i \] kde \( \alpha_i = \vec u_i^*\hat{\vec x} \) jsou Furierovy koeficienty z LAA. Rozepíšeme reziduum: \[ \vec r = \matice A \sum_{i=1}^n \alpha_i \vec u_i - \hat \lambda \sum_{i=1}^n \alpha_i \vec u_i = \sum_{i=1}^n \alpha_i \lambda \vec u_i -\hat \lambda_i \sum_{i=1}^n \alpha_i \vec u_i = \sum_{i=1}^n (\lambda_i - \hat \lambda) \alpha_i \vec u_i \] U druhého rovnítka jsme vtáhli matici \(\matice A\) do sumy a aplikovali na vektory \( \vec u_1, \ldots, \vec u_n \). Z toho plyne: \[\lVert \vec r \rVert_2^2=\sum_{i=1}^n \left\lvert \lambda_i - \hat \lambda \right\rvert^2 \left\lvert \alpha_i \right\rvert^2 \] \[\lVert \hat{\vec x} \rVert_2^2=\sum_{i=1}^n \left\lvert \alpha_i \right\rvert^2 \] \[ \frac {\lVert \vec r \rVert_2^2}{\lVert \hat{\vec x} \rVert_2^2}= \frac {\sum_{i=1}^n \left\lvert \lambda_i - \hat \lambda \right\rvert^2 \left\lvert \alpha_i \right\rvert^2 }{\sum_{i=1}^n \left\lvert \alpha_i \right\rvert^2}=\] Zavedeme \(\beta_i = \frac {\alpha_i^2} {\sum_{i=1}^n \left\lvert \alpha_i \right\rvert^2}\), tudíž \(\sum_{i=1}^n \beta_i = 1 \). \[= \sum_{i=1}^n \beta_i \left\lvert \lambda_i - \hat \lambda \right\rvert^2 \geq \min\limits_{\lambda_i \in \sigma ( \matice A )} \left\lvert \lambda_i - \hat \lambda \right\rvert^2 \sum_{i=1}^n \beta_i = \min\limits_{\lambda_i \in \sigma ( \matice A )} \left\lvert \lambda_i - \hat \lambda \right\rvert^2 \] \end{proof} \end{theorem} \subsection{Mocninná metoda} Zvolíme libovolný vektor \( \vec x^{( 0 )} \) a napočítáváme \[ \rho_{k + 1} = \left\lVert \matice A \vec x^{( k )} \right\rVert_2 \] \[ \vec x^{( k + 1 )} = \frac{\matice A \vec x^{( k )}}{\rho_{k + 1}} \] \begin{theorem} \label{MocninnaMetodaVektor} Vektor \( \vec x^{(k)} \) z mocninné metody lze vyjádřit jako \[ \vec x^{(k)} = \frac{\matice A^k \vec x^{( 0 )}}{\prod_{i = 1}^k \rho_i} \] \begin{proof} Z definice posloupností v mocninné metodě plyne: \[ \vec x^{( k )} = \frac{\matice A \vec x^{( k - 1 )}}{\rho_k} = \frac{\matice A^2 \vec x^{( k - 2 )}}{\rho_k \rho_{k - 1}} = \dots = \frac{\matice A^k \vec x^{( 0 )}}{\prod_{i = 1}^k \rho_i} \] \end{proof} \end{theorem} \begin{theorem} \label{MocninnaMetodaNejvetsiEigenvalue} Nechť matice \( \matice A \) má vlastní číslo \( \lambda \) s algebraickou i geometrickou násobností \( r \), které má největší absolutní hodnotu. Nechť \( \vec y^{( 1 )}, \dots, \vec y^{( r )} \) jsou vlastní vektory příslušné vlastnímu číslu \( \lambda \). Nechť \( s \in \hat r \) a \( \vec x^{( 0 )} \) takový, že \( \braket{\vec x^{( 0 )} | \vec y^{( s )}} \neq 0 \). Potom \[ \lim_{k \rightarrow \infty} \rho_k = \lvert \lambda \rvert \] \[ \lim_{k \rightarrow \infty} \vec x^{( k )} = \vec y^{( s )} \] \begin{proof} \todo{Důkaz 6.4 - jak to pořádně zapsat?} \end{proof} \end{theorem} \setcounter{define}{7} \begin{theorem} \label{MocninnaMetodaNejvetsi2Eigenvalues} Nechť matice \( \matice A \) má vlastní čísla \( \lambda \), \( - \lambda \), která jsou v absolutní hodnotě největší a jejichž algebraická i geometrická násobnost je \( 1 \). Nechť \( \vec y^{( 1 )} \) je vlastní vektor příslušný vlastnímu číslu \( \lambda \) a \( \vec y^{( 2 )} \) je vlastní vektor příslušný vlastnímu číslu \( - \lambda \). Nechť je \( x^{( 0 )} \) takový, že \( \braket{\vec x^{( 0 )} | \vec y^{( 1 )}} \neq 0 \) a \( \braket{\vec x^{( 0 )} | \vec y^{( 2 )}} \neq 0 \). Potom \[ \lim_{k \rightarrow \infty} \sqrt{\rho_{2k} \rho_{2k + 1}} = \lvert \lambda \rvert \] \[ \lim_{k \rightarrow \infty} \matice A \vec x^{( 2k )} + \lambda \vec x^{( 2k )} = \vec y^{( 1 )} \] \[ \lim_{k \rightarrow \infty} \matice A \vec x^{( 2k )} - \lambda \vec x^{( 2k )} = \vec y^{( 2 )} \] \begin{proof} \todo{Důkaz 6.8} \end{proof} \end{theorem} \subsection{Výpočet kompletního spektra matice} \setcounter{define}{12} \begin{theorem} \label{KorenyPnomuSpektrum} Nechť \( p_n ( x ) = \sum_{k = 0}^n a_k x^k \) je polynom stupně \( n \). Potom jeho kořeny jsou vlastními čísly matice \( \matice F \in \mathbbm R^{n, n} \), definované jako: \[ \matice F = \begin{pmatrix} -\frac{a_{n - 1}}{a_n} & -\frac{a_{n - 2}}{a_n} & \cdots & -\frac{a_1}{a_n} & -\frac{a_0}{a_n} \\ 1 & 0 & \cdots & 0 & 0 \\ 0 & 1 & \cdots & 0 & 0 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & \cdots & 1 & 0 \\ \end{pmatrix} \] \begin{proof}\renewcommand{\qedsymbol}{} Bez důkazu. \end{proof} \end{theorem} \subsection{Trojúhelníková metoda} Konstruujeme dvě posloupnosti: \begin{itemize} \item \( \left\{ \matice L^{( k )} \right\}_{k = 0}^\infty \) dolní trojúhelníkové s jedničkami na diagonále \item \( \left\{ \matice R^{( k )} \right\}_{k = 1}^\infty \) horní trojúhelníkové \end{itemize} Můžeme volit libovolnou \( \matice L_0 \) (dokonce ani nemusí být dolní trojúhelníková) a pomocí Doolittlovy faktorizace napočítáváme \[ \matice L_{k + 1} \matice R_{k + 1} = \matice{A L}_k \] \setcounter{define}{14} \begin{remark} \label{TrojuhelnikEigenvalues} Pokud existují \( \matice L \in \mathbbm C^{n, n} \) a \( \matice R \in \mathbbm C^{n, n} \) takové, že \[ \lim_{k \rightarrow \infty} \matice L^{( k )} = \matice L \] \[ \lim_{k \rightarrow \infty} \matice R^{( k )} = \matice R \] Potom platí \[ \matice A = \matice{L R L}^{-1} \] a na diagonále matice \( \matice R \) jsou vlastní čísla matice \( \matice A \). \begin{proof} \begin{enumerate}[(1)] \item Je důsledkem vztahu \( \matice{L R} = \matice{A L} \). \item Platí díky \[ \det ( \matice A - \lambda \matice I ) = \det \left( \matice{L R L}^{-1} - \lambda \matice{L L}^{-1} \right) = \det \left( \matice L ( \matice R - \lambda \matice I ) \matice L^{-1} \right) = \det ( \matice R - \lambda \matice I ) \] \end{enumerate} \end{proof} \end{remark} \begin{remark} \label{TrojuhlenikEigenvectors} Nechť \( \lambda \) je díky \ref{TrojuhelnikEigenvalues} vlastním číslem matic \( \matice A \) a \( \matice R \). Nechť \( \vec y \) je vlastním vektorem matice \( \matice R \) příslušný vlastnímu číslu \( \lambda \). Potom pro vektor \( \vec x \), který je vlastním vektorem matice \( \matice A \) příslušným vlastnímu číslu \( \lambda \) platí \[ \vec x = \matice L \vec y \] \begin{proof} \todo{Důkaz 6.16} \end{proof} \end{remark} Trojúhelníková metoda je \textbf{samoopravná}, pokud je napočítaná \( \matice L^{( k )} \) chybná, lze ji brát jako novou \( \matice L^{( 0 )} \). \subsection{Existence LU rozkladu} \setcounter{define}{17} \begin{theorem} \label{LUMaleOdchylky} Nechť matice \( \matice A \) je silně regulární, tj. existuje její LU rozklad. Nechť dále matice \( \matice E \) je taková, že \( \lVert \matice E \rVert \) je \todo{To je co?} dostatečně malé. Pak existuje i LU rozklad matice \( \matice A + \matice E \). \begin{proof} \todo{Důkaz 6.18} \end{proof} \end{theorem} \begin{theorem} \label{LUTemerIdentita} Nechť matice \( \matice A = \matice I + \matice E \), kde \( \lVert \matice E \rVert \) je \todo{To je co?} dostatečně malé. Pak existuje i rozklad \( \matice A = \matice{L R} \), kde \( \matice L \) je dolní trojůhelníková s jedničkami na diagonále a \( \matice R \) je horní trojúhelníková. Pokud \( \lVert \matice E \rVert \rightarrow 0 \), pak \( \matice L \rightarrow \matice I \) a \( \matice R \rightarrow \matice I \). \begin{proof} \todo{Důkaz 6.19} \end{proof} \end{theorem} \subsection{Konvergence trojúhelníkové metody} \begin{theorem} \label{IteraceTrojuhelniku} Nechť existuje trojúhelníkový rozklad matice \( \matice A^k \matice L_0 = \mathcal L_k \mathcal R_k \). Potom \[ \mathcal L_k = \matice L_k \] \[ \mathcal R_k = \prod_{i = 0}^{k - 1} \matice R_{k - i} \] \begin{proof} Budeme postupně aplikovat trojúhelníkovou metodu, tj. \( \matice L_{k + 1} \matice R_{k + 1} = \matice{A L}_k \): \[ \matice A^k \matice L_0 = \matice A^{k - 1} \matice L_1 \matice R_1 = \matice A^{k - 2} \matice L_2 \matice R_2 \matice R_1 = \dots = \matice A \matice L_{k - 1} \prod_{i = 1}^{k - 1} \matice R_{k - i} = \matice L_k \prod_{i = 0}^{k - 1} \matice R_{k - i} \] Matice \( \matice L_k \) je dolní trojúhelníková a matice \( \prod_{i = 0}^{k - 1} \matice R_{k - i} \) je díky \ref{SoucinTrojuhelniku} horní trojúhelníková. \end{proof} \end{theorem} \setcounter{define}{21} \begin{theorem} \label{KTrojuhelnikoveMetody} Nechť je matice \( \matice A \in \mathbbm C^{n, n} \) regulární a diagonalizovatelná. Nechť dále pro dostatečně velké \( k \) \todo{To je co?} existují LU rozklady matic \( \matice{A L}_k \). Pak posloupnosti \( \left( \matice L_k \right)_{k = 0}^\infty \) a \( \left( \matice R_k \right)_{k = 1}^\infty \) konvergují a na diagonále matice \( \matice R \) je spektrum matice \( \matice A \) seřazené sestupně podle velikosti v absolutní hodnotě. \todo{Doplnit předpoklady} \begin{proof} \todo{Důkaz 6.22} \end{proof} \end{theorem} \subsection{LR algoritmus} Konstruujeme tři posloupnosti: \begin{itemize} \item \( \left\{ \matice A^{( k )} \right\}_{k = 1} \) \item \( \left\{ \matice L^{( k )} \right\}_{k = 1}^\infty \) dolní trojúhelníkové s jedničkami na diagonále \item \( \left\{ \matice R^{( k )} \right\}_{k = 1}^\infty \) horní trojúhelníkové \end{itemize} Volíme \( \matice A^{( 0 )} = \matice A \) a pomocí Doolittlovy faktorizace napočítáváme \[ \matice L^{( k )} \matice R^{( k )} = \matice A^{( k )} \] \[ \matice A^{( k + 1 )} = \matice R^{( k )} \matice L^{( k )} \] \begin{remark} \label{LREigenvaluesTriv} Pokud existuje horní trojúhelníková matice \( \matice B \in \mathbbm C^{n, n} \) taková, že \[ \lim_{k \rightarrow \infty} \matice A^{( k )} = \matice B \] potom na diagonále \( \matice B \) jsou vlastní čísla matice \( \matice A \). \begin{proof} \todo{Důkaz 6.23} \end{proof} \end{remark} V LR rozkladu potřebujeme méně paměti než pro trojúhelníkovou metodu, neukládáme totiž matici \( \matice A \). To ovšem také znamená, že jakékoliv chyby se neopraví, tedy algoritmus není tolik samoopravný. K tomu také přispívá to, že počáteční matici nemůže volit libovolně. \subsection{Konvergence LR algoritmu} \setcounter{define}{23} \begin{theorem} \label{KLR} Nechť existuje trojúhelníkový rozklad matice \( \matice A^k = \mathcal L_k \mathcal R_k \). Potom platí \[ \mathcal L_k = \prod_{i = 1}^k \hat{\matice L}_i \] \[ \mathcal R_k = \prod_{i = 0}^{k - 1} \hat{\matice R}_{k - i} \] \begin{proof} Využijeme vlastnosti \( \hat{\matice R}_{l - 1} \hat{\matice L}_{l - 1} = \matice A_l = \hat{\matice L}_l \hat{\matice R}_l \) a postupně upravujeme \[ \matice A^k = \matice A_1 \matice A_1 \dots \matice A_1 = \hat{\matice L}_1 \hat{\matice R}_1 \hat{\matice L}_1 \hat{\matice R}_1 \dots \hat{\matice L}_1 \hat{\matice R}_1 = \hat{\matice L}_1 \matice A_2 \matice A_2 \dots \matice A_2 \hat{\matice R}_1 = \dots = \prod_{i = 1}^{k - 1} \hat{\matice L}_i \matice A_k \prod_{i = 1}^{k - 1} \hat{\matice R}_{k - i} = \prod_{i = 1}^k \hat{\matice L}_i \prod_{i = 0}^{k - 1} \hat{\matice R}_{k - i} \] Díky \ref{SoucinTrojuhelniku} je \( \prod_{i = 1}^k \hat{\matice L}_i \) dolní trojúhelníková matice a \( \prod_{i = 0}^{k - 1} \hat{\matice R}_{k - i} \) horní trojúhelníková matice. \end{proof} \end{theorem} \setcounter{define}{26} \begin{theorem} \label{LREigenvalues} Nechť je matice \( \matice A \in \mathbbm C^{n, n} \) regulární a diagonalizovatelná. Nechť dále konverguje trojúhelníková metoda při volbě \( \matice L_0 = \matice I \). Pak LR algoritmus také konverguje a posloupnost \( \left( \matice A_k \right)_{k = 1}^\infty \) konverguje k horní trojúhelníkové matici, na jejíž diagonále jsou vlastní čísla matice \( \matice A \) seřazená sestupně podle velikosti v absolutní hodnotě. \begin{proof} \todo{Důkaz 6.27} \end{proof} \end{theorem} \subsection{QR algoritmus} \setcounter{define}{28} \begin{theorem} \label{QR} Nechť je \( \matice A \in \mathbbm C^{n, n} \). Potom existuje rozklad \( \matice A = \matice{Q R} \), kde matice \( \matice Q \) je unitární a \( \matice R \) horní trojúhelníková. Pokud budeme požadovat, aby diagonální prvky matice \( \matice R \) byly kladné a matice \( \matice A \) je regulární, tak je tento rozklad jednoznačný. \begin{proof} \begin{enumerate}[(1)] \item existence \\ \todo{Důkaz 6.29} \item jednoznačnost \\Důkaz indukcí podle n \begin{itemize} \item \( n = 1 \) \[ \matice A = ( \matice A_{11} ) = \underbrace{\matice I}_{\matice Q} \underbrace{( \matice A_{11} )}_{\matice R} \] \item \( n \rightarrow n + 1 \) \\Předpokládáme existenci 2 různych rozkladů \( \matice A = \matice{Q R} = \matice Q' \matice R' \). Matice blokově zapíšeme jako \[ \matice A = \begin{pmatrix} \widetilde{\matice A} & \vec a_1 \\ \vec a_2^T & \alpha \\ \end{pmatrix} \] \[ \matice Q = \begin{pmatrix} \widetilde{\matice Q} & \vec q_1 \\ \vec q_2^T & \beta \\ \end{pmatrix} \] \[ \matice R = \begin{pmatrix} \widetilde{\matice R} & \vec r \\ \vec 0^T & \gamma \\ \end{pmatrix} \] \[ \matice Q' = \begin{pmatrix} \widetilde{\matice Q}' & \pvec q_1' \\ \pvec q_2'^T & \beta' \\ \end{pmatrix} \] \[ \matice R' = \begin{pmatrix} \widetilde{\matice R}' & \pvec r' \\ \vec 0^T & \gamma' \\ \end{pmatrix} \] a tedy musí \[ \matice A = \begin{pmatrix} \widetilde{\matice Q} \widetilde{\matice R} & \widetilde{\matice Q} \vec r + \gamma \vec q_1 \\ \vec q_2^T \widetilde{\matice R} & \vec q_2^T \vec r + \beta \gamma \\ \end{pmatrix} = \begin{pmatrix} \widetilde{\matice Q}' \widetilde{\matice R}' & \widetilde{\matice Q}' \pvec r' + \gamma' \pvec q_1' \\ \pvec q_2'^T \widetilde{\matice R}' & \pvec q_2'^T \pvec r' + \beta' \gamma' \\ \end{pmatrix} \] Díky indukčnímu předpokladu, tj. jednoznačnosti rozkladu \( \widetilde{\matice A} = \widetilde{\matice Q} \widetilde{\matice R} \) můžeme určit \( \widetilde{\matice Q} = \widetilde{\matice Q}' \) a \( \widetilde{\matice R} = \widetilde{\matice R}' \). Tím pádem díky rovnosti \( \vec q_2^T \widetilde{\matice R} = \pvec q_2'^T \widetilde{\matice R}' \) platí \( \vec q_2 = \pvec q_2' \). \todo{Dokončit důkaz 6.29} \qedhere \end{itemize} \end{enumerate} \end{proof} \end{theorem} \begin{remark*} Pokud je matice \( \matice A \) reálná, je matice \( \matice Q \) orthogonální a matice \( \matice R \) reálná. \end{remark*} Existují tři způsoby, jak najít QR rozklad: \begin{itemize} \item Grammův-Schmidtův ortonormalizační proces \item Householderovy transformace \item Givensovy rotace \end{itemize} \subsection{Gramův-Schmidtův ortonormalizační proces} Budeme hledat matici \( \matice Q \) po sloupcích jako soubor vektorů. Označíme \[ \vec a^{( k )} = \matice A_{\bullet k} \] Definujeme \textbf{projekční operátor} jako \[ \proj_{\vec u} \left( \vec v \right) = \frac{\braket{\vec v | \vec u}}{\braket{\vec u | \vec u}} \vec u \] Nejprve provedeme ortogonalizaci: \[ \vec p^{( 1 )} = \vec a^{( 1 )} \] \[ \vec p^{( k )} = \vec a^{( k )} - \sum_{l = 1}^{k - 1} \proj_{\vec p^{( l )}} \left( \vec a^{( k )} \right) \] a následně normalizujeme \[ \vec q^{( k )} = \frac{\vec p^{( k )}}{\left\lVert \vec p^{( k )} \right\rVert_2} \] Prvky matice \( \matice R \) budou upravené koeficienty projekčního operátoru, přesně \[ \matice R_{ij} = \braket{\vec q^{( i )} | \vec a^{( j )}} \] Pro lepší numerickou stabilitu se však používá takzvaný \textbf{modifikovaný Gramův-Schmidtův ortonormalizační proces}, který se liší tak, že v ortogonalizaci používáme už napočítané vektory, tj. \todo{Tohle je potřeba zkontrolovat, to Mlha napsal ve spěchu po zkoušce a ani tam si tím nebyl jistý. Je to mix Oberhuberova výkladu a anglické wikipedie (třeba ten projekční operátor, to je moc pěkná a užitečná konstrukce).} \[ \vec p_1^{( k )} = \vec a^{( k )} \] \[ \vec p_m^{( k )} = \vec a^{( k )} - \proj_{\vec p_{ m - 1 }^{( k )}} \left( \vec a^{( k )} \right) \] \[ \vec p^{( k )} = \vec p_{k - 1}^{( k )} \] \begin{theorem} \label{GramSchmidt} Nechť je matice \( \matice A \in \mathbbm R^{n, n} \) regulární. Potom pro QR rozklad matice \( \matice A \) platí \[ \matice Q = \begin{pmatrix} \vec q^{( 1 )} & \vec q^{( 2 )} & \cdots & \vec q^{( n )} \\ \end{pmatrix} \] \begin{proof} \todo{Důkaz 6.30} \end{proof} \end{theorem} \subsection{Householderovy transformace} \setcounter{define}{31} \begin{theorem} Viz \ref{HouseholderReflekcni} \end{theorem} \subsection{QR algoritmus} Je stejný jako LR algoritmus, pouze místo LU rozkladu počítáme QR rozklad. \subsection{Konvergence QR algoritmu} \setcounter{define}{35} \begin{lemma} \label{KQR} Nechť existuje QR rozklad matice \( \matice A^k = \mathcal Q_k \mathcal R_k \). Potom platí \[ \mathcal Q_k = \prod_{i = 1}^k \matice Q^{( i )} \] \[ \mathcal R_k = \prod_{i = 0}^{k - 1} \matice R^{( k - i )} \] \begin{proof} Využijeme vlatnosti \( \matice R^{( l - 1 )} \matice Q^{( l - 1 )} = \matice T^{( l )} = \matice Q^{( l )} \matice R^{( l)} \) a postupně upravujeme \[ \matice A^k = \matice T^{( 1 )} \matice T^{( 1 )} \dots \matice T^{( 1 )} = \matice Q^{( 1 )} \matice R^{( 1 )} \matice Q^{( 1 )} \matice R^{( 1 )} \dots \matice Q^{( 1 )} \matice R^{( 1 )} = \matice Q^{( 1 )} \matice T^{( 2 )} \matice T^{( 2 )} \dots \matice T^{( 2 )} \matice R^{( 1 )} = \dots = \] \[ = \prod_{i = 1}^{k - 1} \matice Q^{( i )} \matice T^{( k )} \prod_{i = 1}^{k - 1} \matice R^{( k - i )} = \prod_{i = 1}^k \matice Q^{( i )} \prod_{i = 0}^{k - 1} \matice R^{( k - i )} \] Díky \ref{SoucinTrojuhelniku} je \( \prod_{i = 0}^{k - 1} \matice R^{( k - i )} \) horní trojúhelníková matice. Ověření, že součin unitárních matic je unitární matice, je triviální. \end{proof} \end{lemma} \begin{theorem} \label{QREigenvalues} Nechť matice \( \matice A \in \mathbbm R^{n, n} \) je taková, že všechna její vlastní čísla \( \lambda_i \) jsou jednonásobná a splňují \[ \lvert \lambda_1 \rvert > \lvert \lambda_2 \rvert > \dots > \lvert \lambda_n \rvert \] Potom \( \lim\limits_{k \rightarrow \infty} \matice T^{( k )} = \matice T \). Matice \( \matice T \) je horní trojúhelníková a \( \matice T_{ii} = \lambda_i \). Pokud je matice \( \matice A \) symetrická, tak je matice \( \matice T \) diagonální. \begin{proof} \todo{Důkaz 6.37} \end{proof} \end{theorem} \subsection{Hessenbergovy QR iterace} \begin{lemma} \label{Hessenberg} Matice \( \matice H^{( k )} \) v Hessenbergových QR iteracích je v Hessenberegově tvaru. \begin{proof} \todo{Důkaz 6.38} \end{proof} \end{lemma}