Zobrazení zdroje stránky 01NUM1:Kapitola6

%\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 j \neq 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}