Součásti dokumentu 01NUM1
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_i \vec u_i -\hat \lambda \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 {\left\lvert \alpha_i \right\rvert^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{remark*}
V roce 2016/17 se Oberhuber vrátil k Humhalovu "normování" pomocí \(\rho_{k+1} = \vec e_1^T \vec y^{(k+1)} \). To má za následek pozměnění předpokladů následujících vět.
\todo{Mám ty věty přepsat?}
\end{remark*}
\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_1 \). Nechť \(\matice T \) převádí \(\matice A \) do Jordanova tvaru, tj. \(\matice A = \matice T^{-1} \matice J_{\matice A} \matice T\).
Nechť je prvních \( r \) složek vektoru \(\matice T \vec x^{( 0 )} \) nenulových. Potom
\[ \lim_{k \rightarrow \infty} \rho_k = \lvert \lambda_1 \rvert \]
\[ \lim_{k \rightarrow \infty} \vec x^{( k )} = \vec y^{( s )} \]
kde je vektor \(\vec y^{( s )}\) vlastním vektorem k \(\lambda_1 \).
\begin{proof}
Z Jordanovy věty platí:
\[
\matice J_{\matice A}= \left (
\begin{matrix}
\underbrace{\begin{matrix}
\lambda_1\\
& \ddots\\
& & \lambda_1
\end{matrix}}_{r\text{-krát}}\\
& \matice J_{r+1}\\
& & \ddots
\end{matrix}
\right )
\]
Z věty \ref{MocninnaMetodaVektor} plyne
\begin{equation}
\label{momeiks}
\[\vec x^{(k+1)}=\frac{1}{\vec e_1^T \matice A \vec x} \matice A \vec x\]
\end{equation}
Vynásobíme-li tuto rovnici zleva vektorem \( \vec e_1^T \), dostaneme
\[ (\forall k\in \matice N)( \vec e_1^T \vec x^{(k)} =1) \]
Odtud můžeme rozepsat \(\rho_k\) jako:
\[
\rho_k= \vec e_1^T \matice A \vec x=\frac{ \vec e_1^T \matice A \vec x}{\vec e_1^T\vec x}=\frac{\rho_{k-1}\hdots\rho_0}{\rho_{k-1}\hdots\rho_0}\cdot\frac{\vec e_1^T \matice A^{k+1}
\vec x^{(0)}}{\vec e_1^T \matice A^k\vec x^{(0)}}=
\]
\[
=\frac{\vec e_1^T \matice T^{-1}\left (
\begin{matrix}
\underbrace{\begin{matrix}
\lambda_1^{k+1}\\
& \ddots\\
& & \lambda_1^{k+1}
\end{matrix}}_{r\text{-krát}}\\
& \matice J_{r+1}^{k+1}\\
& & \ddots
\end{matrix}
\right)\matice T\vec x^{(0)}}{\vec e_1^T \matice T^{-1}\left (
\begin{matrix}
\underbrace{\begin{matrix}
\lambda_1^{k}\\
& \ddots\\
& & \lambda_1^{k}
\end{matrix}}_{r\text{-krát}}\\
& \matice J_{r+1}^{k}\\
& & \ddots
\end{matrix}
\right)\matice T\vec x^{(0)}}
=\lambda_1\frac{\vec e_1^T \matice T^{-1}\left (
\begin{matrix}
\underbrace{\begin{matrix}
1\\
& \ddots\\
& & 1
\end{matrix}}_{r\text{-krát}}\\
& (\frac{1}{\lambda_1}\matice J_{r+1})^{k+1}\\
& & \ddots
\end{matrix}
\right)\matice T\vec x^{(0)}}{\vec e_1^T \matice T^{-1}\left (
\begin{matrix}
\underbrace{\begin{matrix}
1\\
& \ddots\\
& & 1
\end{matrix}}_{r\text{-krát}}\\
& (\frac{1}{\lambda_1}\matice J_{r+1})^{k}\\
& & \ddots
\end{matrix}
\right)\matice T\vec x^{(0)}}}.
\]
Podle věty \ref{GeomKSpektrum} konvergují diagonální bloky k nulové matici, a tak
\[
\rho_k\stackrel{k\rightarrow\infty}{\longrightarrow}\lambda_1\frac{\vec e_1^T \matice T^{-1}\left (
\begin{matrix}
\underbrace{\begin{matrix}
1\\
& \ddots\\
& & 1
\end{matrix}}_{r\text{-krát}}\\
& 0\\
& & \ddots
\end{matrix}
\right) \matice T\vec x^{(0)}}{\vec e_1^T \matice T^{-1}\left (
\begin{matrix}
\underbrace{\begin{matrix}
1\\
& \ddots\\
& & 1
\end{matrix}}_{r\text{-krát}}\\
& 0\\
& & \ddots
\end{matrix}
\right) \matice T\vec x^{(0)}}=\lambda_1
\]
za předpokladu, že \(\vec e_1^T \matice T \vec x^{(0)}\ne 0\). Jednak je ale nalezení takového vektoru \(\vec x^{(0)}\), že \(\vec e_1^T \matice T\vec x^{(0)}=0\), dosti obtížné, jednak vše spraví chyby vzniklé zaokrouhlováním.
Dále podle (\ref{momeiks}) a (\ref{MocninnaMetodaVektor}) platí
\[
\vec x=\frac{\matice A \vec x^{(k-1)}}{\vec e_1^T \matice A \vec x^{(k-1)}}=\frac{\rho_{k-2}\hdots\rho_0}{\rho_{k-2}\hdots\rho_0}\cdot\frac{ \matice A^k\vec x^{(0)}}{\vec e_1^T \matice A^k\vec x^{(0)}}=
\]
\[
=\frac{ \matice T^{-1}\left(
\begin{matrix}
\lambda_1^k\\
& \matice J_2^k\\
& & \ddots
\end{matrix}
\right) \matice T\vec x^{(0)}}{\vec e_1^T \matice T^{-1}\left(
\begin{matrix}
\lambda_1^k\\
& J_2^k\\
& & \ddots
\end{matrix}
\right) \matice T\vec x^{(0)}}=\frac{ \matice T^{-1}\left(
\begin{matrix}
1\\
& (\frac{1}{\lambda_1}J_2)^k\\
& & \ddots
\end{matrix}
\right) \matice T\vec x^{(0)}}{\vec e_1^T \matice T^{-1}\left(
\begin{matrix}
1\\
& (\frac{1}{\lambda_1} \matice J_2)^k\\
& & \ddots
\end{matrix}
\right) \matice T\vec x^{(0)}}.
\]
Analogicky jako výše dostaneme
\[
\vec x\stackrel{k\rightarrow\infty}{\longrightarrow}\frac{ \matice T^{-1}\left (
\begin{matrix}
\underbrace{\begin{matrix}
1\\
& \ddots\\
& & 1
\end{matrix}}_{r\text{-krát}}\\
& 0\\
& & \ddots
\end{matrix}
\right)
\matice T\vec x^{(0)}}{\vec e_1^T \matice T^{-1}\left (
\begin{matrix}
\underbrace{\begin{matrix}
1\\
& \ddots\\
& & 1
\end{matrix}}_{r\text{-krát}}\\
& 0\\
& & \ddots
\end{matrix}
\right) \matice T\vec x^{(0)}}\stackrel{\text{ozn.}}{=}\vec y^{(s)}.
\]
Zjistili jsme tedy, že posloupnost \(\vec x \) konverguje. Snadno se přesvědčíme, že její limitní vektor \(\vec y^{(s)}\) je vlastním vektorem matice \( \matice A\) příslušejícím k vlastnímu číslu \(\lambda_1\):
Z definice \(\rho_{k+1}\) a \(\vec x^{(k+1)}\) totiž vyplývá vztah \(\rho_k \vec x^{(k+1)}= \matice A\vec x\) a jeho zlimicením dostáváme \(\lambda_1 \vec y^{(s)}= \matice A\vec y^{(s)}\).
\end{proof}
\end{theorem}
\setcounter{define}{6}
\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}
Viz skripta doc. Humhala, resp. wikiskripta NM.
\todo{Důkaz 6.7}
\end{proof}
\end{theorem}
\subsection{Redukční metoda}
Konstruujeme dvě posloupnosti:
\begin{itemize}
\item Slouží k napočítání několika v absolutní hodnotě největších vlastních čísel
\item K napočítání celého spektra se nehodí, rychle ztrácí přesnost.
\end{itemize}
Za pomoci znalosti absolutní hodnotě největšího \( \lambda_1 \in \sigma (A)\) a jemu odpovídajícího vlastního vektoru \(\vec x\) převedeme matici \( \matice A \in \mathbbm C^{n, n} \) na matici \( \matice B \in \mathbbm C^{n-1, n-1} \) takovou, že má stejné spektrum jako \(\matice A\) až na o jedno sníženou násobnost \(\lambda_1 \).
Převedeme \(\matice A\) do báze \(\vec x, \vec e_2, \ldots \vec e_n):
\[\matice P ^-1 \matice A \matice P =
\begin{pmatrix}
\lambda_1 & \vec q^T \\
\vec \theta & \matice B \\
\end{pmatrix}
\]
kde \(\matice P \) je matice přechodu mezi bázemi.
\todo{Dokončit Redukční metodu. Nevím, jestli to sem mám psát.}
\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 Frobeniovy 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}
Z důkazu \ref{TrojuhelnikEigenvalues} (2) plyne, že \(\matice R \) je matice \(\matice A \) vyjádřená v bázi dané sloupci matice \(\matice L\). Vektor \(\vec x \) tedy dostaneme převedením vektoru \(\vec y \) do původní báze pomocí vynásobení maticí \(\matice L \), tj. \[\vec x = \matice L \vec y \] \qedhere
\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}
Pokud za \( \matice L ^{(0)}\) zvolíme \(\matice I\), pak \(\matice A \matice L ^{(0)}=\matice A\). V tomto případě stačí silná regularita. Ze spojitosti LU rozkladu (věta \ref{LUSpojity}) pak plyne zbytek věty.
\end{proof}
\end{theorem}
\begin{remark*}
Přesnější důkaz ani vysvětlení, co je „dostatečně malé“, Oberhuber neříkal (a nejspíš ani nevyžaduje).
\end{remark*}
\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}
Důsledek \ref{LUMaleOdchylky}. \qedhere
\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á. \qedhere
\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ť jsou vlastní čísla matice \(\matice A\) navzájem různá a \(\lvert \lambda_1 \rvert > \lvert \lambda_2 \rvert>\ldots>\lvert \lambda_n \rvert\). Nechť existují rozklady matic \(\matice X \) a \(\matice X^{-1}\matice L_0\). (Pomocí matice \(\matice X\) a její inverze diagonalizujeme matici \(\matice A\), \(\matice L_0\) libovolná.) Nechť dále pro dostatečně velké \( k \) existují LU rozklady matic \( \matice{A L}_k \) (doufáme, že můžeme dostatečně dlouho iterovat). 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ě.
\begin{proof}
\[\matice A^k\matice L_0=\matice X \matice D^k \matice X^{-1}\matice L_0=\matice L_X\matice R_X\matice D^k\matice L_Y\matice R_Y=\matice L_X\matice R_X\matice D^k\matice L_Y (\matice D^k)^{-1} \matice D^k \matice R_Y=\]
V prvním rovnítku jsme použili Jordanovu větu, v druhém LU rozklady \(\matice X=\matice L_X\matice R_X\) a \(\matice X^{-1}\matice L^{(0)}=\matice Y=\matice L_X\matice R_X\). V posledním jsme vložili identitu, protože potřebujeme dostat matici \(\matice D^k\) za \(\matice L_Y\).
Nyní dokážeme, že \(\matice D^k\matice L_Y (\matice D^k)^{-1} \to \matice I\):
\[ \left[ \matice D^k\matice L_Y (\matice D^k)^{-1} \right]_{ij} =
\begin{cases}
0 & j > i \\
\lambda_i^k l_{ii}\lambda_i^{-k} & i = j \\
\lambda_i^k l_{ij}\lambda_j^{-k}=l_{ij}\left(\frac{\lambda_i}{\lambda_j}\right)^k & i > j \\
\end{cases}\]
Z uspořádání plyne, že \(\matice D^k\matice L_Y (\matice D^k)^{-1} \to \matice I\) rychlostí danou \(\left(\frac{\lambda_i}{\lambda_j}\right)^k \).
Označíme si \(\matice D^k\matice L_Y (\matice D^k)^{-1}=\matice I + \matice F_k}\), kde \(\matice F_k} \to \Theta\). Vraťme se k započaté úpravě:
\[=\matice L_X\matice R_X (\matice I + \matice F_k) \matice D^k \matice R_Y=\matice L_X\matice R_X (\matice I + \matice F_k) (\matice R_x)^{-1}\matice R_X\matice D^k \matice R_Y=\]
V druhém rovnítku jsme znovu vložili identitu. Roznásobíme:
\[=\matice L_X \left( \matice R_X (\matice R_X)^{-1}+\matice R_X \matice F_k}(\matice R_X)^{-1}\right)\matice R_X\matice D^k \matice R_Y =
\matice L_X \left(\matice I+\matice G_k \right)\matice R_X\matice D^k \matice R_Y\]
kde jsme si označili \(\matice G_k=\matice R_X \matice F_k}(\matice R_X)^{-1}\) a díky regularitě \(\matice R_X\) jde \(\matice G_k \to \Theta\).
Jako \(\mathcal R_k\) si označíme \(\matice R_X\matice D^k \matice R_Y\), jako \(\mathcal L_k}=\matice L_X (\matice I+\matice G_k)\)
Dokázali jsme, že
\[\mathcal L_k} \to \matice L_X \Rightarrow \matice L_k} \to \matice L_X \]
Díky \(\matice A \matice L_{k-1}=\matice L_k \matice R_k\) implikuje konvergence \(\matice L_k \to \matice L_X\) konvergenci \(\matice R_k \to \matice R_X \), čímž je dokázána konvergence metody.
Zbývá dokázat, že na diagonále \(\matice R\) jsou vlastní čísla \(\matice A\):
Limitováním \(\matice A \matice L_{k-1}=\matice L_k \matice R_k\) dostaneme
\[\matice A \matice L_X=\matice L_X \matice R \Rightarrow \matice R=\matice L_X^{-1}\matice A \matice L_X=\matice L_X^{-1}\matice X \matice D \matice X^{-1} \matice L_X=\matice R_X \matice D \matice R_X^{-1}\]
Poslední rovnítko platí, protože
\[\matice X=\matice L_X\matice R_X \Rightarrow \matice L_X^{-1} \matice X=\matice R_X \Rightarrow \matice X^{-1}=\matice R_X^{-1}\]
Protože \(\matice R_X \matice D \matice R_X^{-1}\) je součin horních trojúhelníkových matic, platí dokazované tvrzení, tj.
\[\text{diag}~\matice R =\text{diag}~\matice D\] \qedhere
\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á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}
\[\matice A^{( k + 1 )} = \matice R^{( k )} \matice L^{( k )}=\left( (\matice L^{( k )})^{-1}\matice L^{( k )} \right)\matice R^{( k )} \matice L^{( k )}=(\matice L^{( k )})^{-1} \matice A^{( k )}\matice L^{( k )}=\]
Pokračujeme ve stejných úpravách a nakonec dostaneme:
\[=(\matice L^{( k )})^{-1} \ldots (\matice L^{( 1 )})^{-1} \matice A\matice L^{( 1 )} \ldots \matice L^{( k )}\]
Matice \(\matice B=\lim_{k \rightarrow \infty} \matice A^{( k+1 )}\) je tedy podobná matici \(\matice A\). \qedhere
\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 (\textit{existence})
Zajišťuje ji např. Gramm–Schmidtův ON proces (viz \ref{GramSchmidt}).
\item (\textit{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}' \) a regularitě \(\widetilde{\matice R}'\) platí \( \vec q_2 = \pvec q_2' \). Máme tedy rovnost prvních $n$ sloupců. Protože chceme OG matice \(\matice Q\) a \(\matice Q'\), musí být sloupce rámci obou matic ON. Tím je však určen směr posledních sloupců matic \(\matice Q\) a \(\matice Q'\) a platí
\[\begin{pmatrix}
\vec q_1 \\
\beta \\
\end{pmatrix}=\pm\begin{pmatrix}
\pvec q_1' \\
\beta' \\
\end{pmatrix}\]
S pomocí tohoto tvrzení upravíme rovnice pro zbylý sloupec matice na
\[\matice Q (\vec r_1 - \pvec r_1') + (\gamma \vec q_1 \pm \gamma' \vec q_1)=\vec 0\]
\[\vec q_2^T (\vec r_1 - \pvec r_1') + (\gamma \beta \pm \gamma' \beta)=0\]
Nyní označme část před plusem jako vektor \(\vec u\) a část za plusem jako vektor \(\vec v\), tj.
\[\vec u=\begin{pmatrix}
\matice Q (\vec r_1 - \pvec r_1') \\
\vec q_2^T (\vec r_1 - \pvec r_1') \\
\end{pmatrix}\]
\[\vec v=\begin{pmatrix}
\gamma \vec q_1 \pm \gamma' \vec q_1 \\
\gamma \beta \pm \gamma' \beta \\
\end{pmatrix}\]
Protože jsou vektory \(\vec u\) a \(\vec v\) vůči sobě OG a \(\vec u + \vec v = \vec 0\), musí být \(\vec u = \vec 0\) a \(\vec v = \vec 0\).
Z \(\vec u = \vec 0\) plyne rovnost \(\vec r_1 = \]vec r_1'\). Z \(\vec v = \vec 0\) plyne
\[\gamma \begin{pmatrix}
\vec q_1 \\
\beta \\
\end{pmatrix}=\gamma' \begin{pmatrix}
\vec q_1 \\
\beta \\
\end{pmatrix}\]
To spolu s kladností \(\gamma \) a \(\gamma'\) (plyne požadavku na kladnost \(\matice R\)) implikuje \(\gamma = \gamma'\). Z toho již snadno plyne \(\vec q_1 = \pvec q_1'\). \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} \]
Nejprve provedeme ortogonalizaci:
\[ \vec p^{( 1 )} = \vec a^{( 1 )} \]
\[ \vec p^{( k )} = \vec a^{( k )} - \sum_{i = 1}^{k - 1} \braket{\vec a^{( k )} |\vec p^{( i )}} \vec p^{( i )} \]
a následně normalizujeme
\[ \vec q^{( k )} = \frac{\vec p^{( k )}}{\left\lVert \vec p^{( k )} \right\rVert_2} \]
Prvky matice \( \matice R \) pak budou
\[ \matice R_{ij} = \braket{\vec a^{( j )} | \vec q^{( i )}} \]
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.
\[ \vec p^{( k )}_1 = \vec a^{( k )} \]
\[ \vec p^{( k )}_m = \vec a^{( k )} - \frac{\braket{\vec p^{( k )}_{m-1}|\vec q^{( m )}}}{\left\lVert \vec p^{( k )}_{m-1} \right\rVert_2} \vec p^{( k )}_{m-1} \]
\[\vec p^{( k )}=\vec p^{( k )}_{k-1}\]
\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}
\[\vec a^{( k )}=\left\lVert \vec p^{( k )} \right\rVert_2\vec q^{( n )}+\sum_{i = 1}^{k - 1}\braket{\vec a^{( k )} |\vec q^{( i )}} \vec q^{( i )} \]
Označíme si
\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}
