01NUM1:Kapitola6: Porovnání verzí
Z WikiSkripta FJFI ČVUT v Praze
(Dokončení důkazu 6.1 (dříve 6.2)) |
(Oprava kompilace) |
||
(Není zobrazeno 105 mezilehlých verzí od jednoho dalšího uživatele.) | |||
Řádka 1: | Řádka 1: | ||
%\wikiskriptum{01NUM1} | %\wikiskriptum{01NUM1} | ||
\section{Vlastní čísla a vektory matic} | \section{Vlastní čísla a vektory matic} | ||
− | + | ||
\subsection{Lokalizace vlastních čísel} | \subsection{Lokalizace vlastních čísel} | ||
− | + | ||
\begin{theorem*}[Gershgorin] | \begin{theorem*}[Gershgorin] | ||
\label{Gershgorin} | \label{Gershgorin} | ||
Řá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*} | ||
− | + | ||
\subsection{Aposteriorní odhad chyby} | \subsection{Aposteriorní odhad chyby} | ||
− | + | ||
\begin{theorem} | \begin{theorem} | ||
\label{AposterioriEigenvalue} | \label{AposterioriEigenvalue} | ||
Řádka 27: | Řádka 27: | ||
potom platí | 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} \] | \[ \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} | \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 | + | \( \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: | \[ \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 \ | + | \[ \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: | 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 \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 | + | \[\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 | + | \[ \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 \). | + | 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 | + | \[= \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{proof} | ||
\end{theorem} | \end{theorem} | ||
− | + | ||
\subsection{Mocninná metoda} | \subsection{Mocninná metoda} | ||
Zvolíme libovolný vektor \( \vec x^{( 0 )} \) a napočítáváme | 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 \] | \[ \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}} \] | \[ \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} | \begin{theorem} | ||
\label{MocninnaMetodaVektor} | \label{MocninnaMetodaVektor} | ||
Řádka 55: | Řádka 60: | ||
\end{proof} | \end{proof} | ||
\end{theorem} | \end{theorem} | ||
− | + | ||
\begin{theorem} | \begin{theorem} | ||
\label{MocninnaMetodaNejvetsiEigenvalue} | \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 \( \ | + | 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\). |
− | \[ \lim_{k \rightarrow \infty} \rho_k = \lvert \ | + | Nechť je alespoň jedna z 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 )} \] | \[ \lim_{k \rightarrow \infty} \vec x^{( k )} = \vec y^{( s )} \] | ||
+ | kde je vektor \(\vec y^{( s )}\) vlastním vektorem k \(\lambda_1 \) (může to být libovolná lineární kombinace vektorů \( \vec y^{( 1 )}, \dots, \vec y^{( r )} \)). | ||
\begin{proof} | \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{align} | ||
+ | \label{momeiks} | ||
+ | \vec x^{(k+1)}=\frac{1}{\vec e_1^T \matice A \vec x^{(k)}} \matice A \vec x^{(k)} | ||
+ | \end{align} | ||
+ | |||
+ | 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^{(k)}=\frac{\vec e_1^T \matice A \vec x^{(k)}}{\vec e_1^T\vec x^{(k)}}=\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 (dostaneme tam členy \(\frac{\lambda_m}{\lambda_1}, m \in \hat n\), které jsou menší než jedna, tudíž konvergují k 0), 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 \eqref{momeiks} a \ref{MocninnaMetodaVektor} platí | ||
+ | \[ | ||
+ | \vec x^{(k)}=\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\\ | ||
+ | & \matice J_2^k\\ | ||
+ | & & \ddots | ||
+ | \end{matrix} | ||
+ | \right) \matice T\vec x^{(0)}}=\frac{ \matice T^{-1}\left( | ||
+ | \begin{matrix} | ||
+ | 1\\ | ||
+ | & (\frac{1}{\lambda_1}\matice 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^{(k)}\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^{(k)}\)) 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^{(k)}\) a přechodem k limitě dostáváme \(\lambda_1 \vec y^{(s)}= \matice A\vec y^{(s)}\). | ||
+ | |||
\end{proof} | \end{proof} | ||
\end{theorem} | \end{theorem} | ||
− | + | ||
− | \setcounter{define}{ | + | \setcounter{define}{6} |
\begin{theorem} | \begin{theorem} | ||
\label{MocninnaMetodaNejvetsi2Eigenvalues} | \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ť | + | 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ť \(\matice T \) převádí \(\matice A \) do Jordanova tvaru, tj. \(\matice A = \matice T^{-1} \matice J_{\matice A} \matice T\). Nechť je \( x^{( 0 )} \) takový, že alespoň jedna z prvních dvou složek vektoru\(\matice T x^{(0)}\) nenulová. Potom |
\[ \lim_{k \rightarrow \infty} \sqrt{\rho_{2k} \rho_{2k + 1}} = \lvert \lambda \rvert \] | \[ \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^{( 1 )} \] | ||
\[ \lim_{k \rightarrow \infty} \matice A \vec x^{( 2k )} - \lambda \vec x^{( 2k )} = \vec y^{( 2 )} \] | \[ \lim_{k \rightarrow \infty} \matice A \vec x^{( 2k )} - \lambda \vec x^{( 2k )} = \vec y^{( 2 )} \] | ||
\begin{proof} | \begin{proof} | ||
− | \todo{Důkaz 6. | + | Viz skripta doc. Humhala, resp. wikiskripta NM. |
+ | \todo{Důkaz 6.7} | ||
\end{proof} | \end{proof} | ||
\end{theorem} | \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} | \subsection{Výpočet kompletního spektra matice} | ||
− | + | ||
\setcounter{define}{12} | \setcounter{define}{12} | ||
\begin{theorem} | \begin{theorem} | ||
\label{KorenyPnomuSpektrum} | \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: | + | 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 = | \[ \matice F = | ||
\begin{pmatrix} | \begin{pmatrix} | ||
Řádka 97: | Řádka 277: | ||
\end{proof} | \end{proof} | ||
\end{theorem} | \end{theorem} | ||
− | + | ||
\subsection{Trojúhelníková metoda} | \subsection{Trojúhelníková metoda} | ||
Konstruujeme dvě posloupnosti: | Konstruujeme dvě posloupnosti: | ||
Řádka 106: | Řádka 286: | ||
Můžeme volit libovolnou \( \matice L_0 \) (dokonce ani nemusí být dolní trojúhelníková) a pomocí Doolittlovy faktorizace napočítáváme | 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 \] | \[ \matice L_{k + 1} \matice R_{k + 1} = \matice{A L}_k \] | ||
− | + | ||
\setcounter{define}{14} | \setcounter{define}{14} | ||
\begin{remark} | \begin{remark} | ||
Řádka 124: | Řádka 304: | ||
\end{proof} | \end{proof} | ||
\end{remark} | \end{remark} | ||
− | + | ||
\begin{remark} | \begin{remark} | ||
\label{TrojuhlenikEigenvectors} | \label{TrojuhlenikEigenvectors} | ||
Řádka 130: | Řádka 310: | ||
\[ \vec x = \matice L \vec y \] | \[ \vec x = \matice L \vec y \] | ||
\begin{proof} | \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{proof} | ||
\end{remark} | \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 )} \). | 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} | \subsection{Existence LU rozkladu} | ||
− | + | ||
\setcounter{define}{17} | \setcounter{define}{17} | ||
\begin{theorem} | \begin{theorem} | ||
Řádka 143: | Řádka 323: | ||
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 \). | 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} | \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{proof} | ||
\end{theorem} | \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} | \begin{theorem} | ||
\label{LUTemerIdentita} | \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 \). | 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} | \begin{proof} | ||
− | \ | + | Důsledek \ref{LUMaleOdchylky}. \qedhere |
\end{proof} | \end{proof} | ||
\end{theorem} | \end{theorem} | ||
− | + | ||
\subsection{Konvergence trojúhelníkové metody} | \subsection{Konvergence trojúhelníkové metody} | ||
− | + | ||
\begin{theorem} | \begin{theorem} | ||
\label{IteraceTrojuhelniku} | \label{IteraceTrojuhelniku} | ||
Řádka 165: | Řádka 348: | ||
Budeme postupně aplikovat trojúhelníkovou metodu, tj. \( \matice L_{k + 1} \matice R_{k + 1} = \matice{A L}_k \): | 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 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á. | + | 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{proof} | ||
\end{theorem} | \end{theorem} | ||
− | + | ||
\setcounter{define}{21} | \setcounter{define}{21} | ||
\begin{theorem} | \begin{theorem} | ||
\label{KTrojuhelnikoveMetody} | \label{KTrojuhelnikoveMetody} | ||
− | Nechť je matice \( \matice A \in \mathbbm C^{n, n} \) regulární a diagonalizovatelná. Nechť dále pro dostatečně velké \( k \) | + | Nechť je matice \( \matice A \in \mathbbm C^{n, n} \) regulární a diagonalizovatelná, tj. \(\nu_a(\lambda)=\nu_g(\lambda)\). 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} | \begin{proof} | ||
− | \ | + | \begin{enumerate} |
+ | \item (\textit{konvergence})\[\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_Y\matice R_Y\). 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 \matice L_{ii}\lambda_i^{-k} = 1 & i = j \\ | ||
+ | \lambda_i^k \matice L_{ij}\lambda_j^{-k}=\matice L_{ij}\left(\frac{\lambda_i}{\lambda_j}\right)^k & i > j \\ | ||
+ | \end{cases}\] | ||
+ | Z uspořádání vlastních čísel 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 \). (Používáme Doolittlovu faktorizaci, platí tedy \(\matice L_{ii}=1\)) | ||
+ | |||
+ | 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\), čímž je dokázána konvergence metody. | ||
+ | |||
+ | \item (\textit{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 L_X=\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í | ||
+ | \[\text{diag}~\matice R =\text{diag}~\matice D,\] | ||
+ | z čehož plyne dokazované tvrzení. | ||
+ | \qedhere | ||
+ | \end{enumerate} | ||
\end{proof} | \end{proof} | ||
\end{theorem} | \end{theorem} | ||
− | + | ||
\subsection{LR algoritmus} | \subsection{LR algoritmus} | ||
Konstruujeme tři posloupnosti: | Konstruujeme tři posloupnosti: | ||
Řádka 185: | Řádka 401: | ||
\item \( \left\{ \matice R^{( k )} \right\}_{k = 1}^\infty \) horní trojúhelníkové | \item \( \left\{ \matice R^{( k )} \right\}_{k = 1}^\infty \) horní trojúhelníkové | ||
\end{itemize} | \end{itemize} | ||
− | Volíme \( \matice A^{( 0 )} = \matice A \) a pomocí Doolittlovy faktorizace | + | Volíme \( \matice A^{( 0 )} = \matice A \) a pomocí Doolittlovy faktorizace napočítáme |
\[ \matice L^{( k )} \matice R^{( k )} = \matice A^{( k )} \] | \[ \matice L^{( k )} \matice R^{( k )} = \matice A^{( k )} \] | ||
\[ \matice A^{( k + 1 )} = \matice R^{( k )} \matice L^{( k )} \] | \[ \matice A^{( k + 1 )} = \matice R^{( k )} \matice L^{( k )} \] | ||
− | + | ||
\begin{remark} | \begin{remark} | ||
\label{LREigenvaluesTriv} | \label{LREigenvaluesTriv} | ||
Řádka 195: | Řádka 411: | ||
potom na diagonále \( \matice B \) jsou vlastní čísla matice \( \matice A \). | potom na diagonále \( \matice B \) jsou vlastní čísla matice \( \matice A \). | ||
\begin{proof} | \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{proof} | ||
\end{remark} | \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ě. | 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} | \subsection{Konvergence LR algoritmu} | ||
− | + | ||
\setcounter{define}{23} | \setcounter{define}{23} | ||
\begin{theorem} | \begin{theorem} | ||
Řádka 215: | Řádka 435: | ||
\end{proof} | \end{proof} | ||
\end{theorem} | \end{theorem} | ||
− | + | ||
\setcounter{define}{26} | \setcounter{define}{26} | ||
\begin{theorem} | \begin{theorem} | ||
\label{LREigenvalues} | \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ě. | + | Nechť je matice \( \matice A \in \mathbbm C^{n, n} \) regulární a diagonalizovatelná, tj. \(\nu_a(\lambda)=\nu_g(\lambda)\). 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} | \begin{proof} | ||
− | \ | + | Protože musí být oba rozklady stejné, platí \(\matice R_k=\hat{\matice R}_k\) a \(\matice L_k=\prod_{i = 1}^k \hat{\matice L}_i \). Z toho plyne |
+ | \[\matice A_k=\hat{\matice L}_k \hat{\matice R}_k= (\matice L_{k-1})^{-1}\matice L_k \matice R_k \to \matice L^{-1}\matice L \matice R=\matice R\] | ||
+ | Z toho plyne, že \(\matice A_k \) z LR algoritmu konverguje k horní trojúhelníkové matici. | ||
+ | Výskyt vlastních čísel plyne z podobnosti (viz \ref{LREigenvaluesTriv}). | ||
\end{proof} | \end{proof} | ||
\end{theorem} | \end{theorem} | ||
− | + | ||
\subsection{QR algoritmus} | \subsection{QR algoritmus} | ||
− | + | ||
\setcounter{define}{28} | \setcounter{define}{28} | ||
\begin{theorem} | \begin{theorem} | ||
Řádka 233: | Řádka 456: | ||
\begin{proof} | \begin{proof} | ||
\begin{enumerate}[(1)] | \begin{enumerate}[(1)] | ||
− | \item existence | + | \item (\textit{existence}) |
− | \ | + | Zajišťuje ji např. Gramm–Schmidtův ON proces (viz \ref{GramSchmidt}). |
− | \item jednoznačnost | + | \item (\textit{jednoznačnost}) |
\\Důkaz indukcí podle n | \\Důkaz indukcí podle n | ||
\begin{itemize} | \begin{itemize} | ||
Řádka 284: | Řádka 507: | ||
\end{pmatrix} | \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' \). \ | + | 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'\) (musí být rovnoběžné) 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 (z ortogonality matic \(\matice Q\) a \(\matice Q'\)) a \(\vec u + \vec v = \vec 0\), musí být \(\vec u = \vec 0\) a \(\vec v = \vec 0\) (jinak by nebyly OG). | ||
+ | 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 z požadavku na kladnost diagonálních prvků \(\matice R\)) implikuje \(\gamma = \gamma'\). Z toho již snadno plyne \(\vec q_1 = \pvec q_1'\). \qedhere | ||
\end{itemize} | \end{itemize} | ||
\end{enumerate} | \end{enumerate} | ||
\end{proof} | \end{proof} | ||
\end{theorem} | \end{theorem} | ||
− | + | ||
\begin{remark*} | \begin{remark*} | ||
Pokud je matice \( \matice A \) reálná, je matice \( \matice Q \) orthogonální a matice \( \matice R \) reálná. | Pokud je matice \( \matice A \) reálná, je matice \( \matice Q \) orthogonální a matice \( \matice R \) reálná. | ||
\end{remark*} | \end{remark*} | ||
− | + | ||
Existují tři způsoby, jak najít QR rozklad: | Existují tři způsoby, jak najít QR rozklad: | ||
\begin{itemize} | \begin{itemize} | ||
Řádka 300: | Řádka 552: | ||
\item Givensovy rotace | \item Givensovy rotace | ||
\end{itemize} | \end{itemize} | ||
− | + | ||
\subsection{Gramův-Schmidtův ortonormalizační proces} | \subsection{Gramův-Schmidtův ortonormalizační proces} | ||
Budeme hledat matici \( \matice Q \) po sloupcích jako soubor vektorů. Označíme | Budeme hledat matici \( \matice Q \) po sloupcích jako soubor vektorů. Označíme | ||
\[ \vec a^{( k )} = \matice A_{\bullet k} \] | \[ \vec a^{( k )} = \matice A_{\bullet k} \] | ||
− | |||
− | |||
Nejprve provedeme ortogonalizaci: | Nejprve provedeme ortogonalizaci: | ||
\[ \vec p^{( 1 )} = \vec a^{( 1 )} \] | \[ \vec p^{( 1 )} = \vec a^{( 1 )} \] | ||
− | \[ \vec p^{( k )} = \vec a^{( k )} - \sum_{ | + | \[ \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 | a následně normalizujeme | ||
\[ \vec q^{( k )} = \frac{\vec p^{( k )}}{\left\lVert \vec p^{( k )} \right\rVert_2} \] | \[ \vec q^{( k )} = \frac{\vec p^{( k )}}{\left\lVert \vec p^{( k )} \right\rVert_2} \] | ||
− | + | 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 pro počítání průmětů už napočítané vektory, tj. | |
− | + | \[ \vec p^{( k )}_1 = \vec a^{( k )} \] | |
− | 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 )}_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}, m=1,\ldots,k-1 \] |
− | + | \[\vec p^{( k )}=\vec p^{( k )}_{k-1}\] | |
− | \[ \vec | + | |
− | \[ \vec | + | |
− | \[ \vec p^{( k )} = \vec | + | |
− | + | ||
\begin{theorem} | \begin{theorem} | ||
\label{GramSchmidt} | \label{GramSchmidt} | ||
Řádka 328: | Řádka 575: | ||
\] | \] | ||
\begin{proof} | \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 )} \] |
+ | Definujeme matici \( \matice R \): | ||
+ | \[ \matice R_{ij} = \begin{cases} | ||
+ | \braket{\vec a^{( j )} | \vec q^{( i )}} & i<j \\ | ||
+ | \left\lVert \vec p^{( k )} \right\rVert_2 & i = j \\ | ||
+ | 0 & i > j \\ | ||
+ | \end{cases}\] | ||
+ | Z toho plyne, že vznikne QR rozklad matice \(\matice A\): | ||
+ | \[ | ||
+ | \begin{pmatrix} | ||
+ | \vec a^{( 1 )} & \vec a^{( 2 )} & \cdots & \vec a^{( n )}\\ | ||
+ | \end{pmatrix}= | ||
+ | \begin{pmatrix} | ||
+ | \vec q^{( 1 )} & \vec q^{( 2 )} & \cdots & \vec q^{( n )} \\ | ||
+ | \end{pmatrix} | ||
+ | \begin{pmatrix} | ||
+ | r_{11}& \ldots & r_{1n} \\ | ||
+ | & \ddots & \vdots\\ | ||
+ | & & r_{nn}\\ | ||
+ | \end{pmatrix} | ||
+ | \] | ||
\end{proof} | \end{proof} | ||
\end{theorem} | \end{theorem} | ||
− | + | ||
\subsection{Householderovy transformace} | \subsection{Householderovy transformace} | ||
− | + | ||
\setcounter{define}{31} | \setcounter{define}{31} | ||
\begin{theorem} | \begin{theorem} | ||
Viz \ref{HouseholderReflekcni} | Viz \ref{HouseholderReflekcni} | ||
+ | Kvůli numerické stabilitě není dobré, pokud je rozdíl \(\vec e^{(1)}-\vec x\) malý (dělení malým číslem), volíme tedy | ||
+ | \[\vec x=-\sgn(x_1)\left\lVert \vec x^{( k )} \right\rVert_2 \vec e^{(1)}\] | ||
\end{theorem} | \end{theorem} | ||
− | + | ||
\subsection{QR algoritmus} Je stejný jako LR algoritmus, pouze místo LU rozkladu počítáme QR rozklad. | \subsection{QR algoritmus} Je stejný jako LR algoritmus, pouze místo LU rozkladu počítáme QR rozklad. | ||
− | + | ||
\subsection{Konvergence QR algoritmu} | \subsection{Konvergence QR algoritmu} | ||
− | + | ||
\setcounter{define}{35} | \setcounter{define}{35} | ||
\begin{lemma} | \begin{lemma} | ||
Řádka 356: | Řádka 625: | ||
\end{proof} | \end{proof} | ||
\end{lemma} | \end{lemma} | ||
− | + | ||
\begin{theorem} | \begin{theorem} | ||
\label{QREigenvalues} | \label{QREigenvalues} | ||
Řádka 363: | Řádka 632: | ||
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í. | 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} | \begin{proof} | ||
− | \todo{ | + | \[\matice A^k=\matice X \matice D^k \matice X^{-1}=\matice Q_X\matice R_X\matice D^k\matice L_Y\matice R_Y=\matice Q_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 QR rozklad \(\matice X=\matice Q_X\matice R_X\) a \textbf{LU rozklad} \(\matice X^{-1}=\matice Y=\matice L_Y\matice R_Y\). V posledním jsme vložili identitu, protože potřebujeme dostat matici \(\matice D^k\) za \(\matice L_Y\). | ||
+ | |||
+ | Nyní dokážeme (stejně jako u trojúhelníkové metody), ž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 \matice L_{ii}\lambda_i^{-k} = 1 & i = j \\ | ||
+ | \lambda_i^k \matice L_{ij}\lambda_j^{-k}=\matice L_{ij}\left(\frac{\lambda_i}{\lambda_j}\right)^k & i > j \\ | ||
+ | \end{cases}\] | ||
+ | Z uspořádání vlastních čísel 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 \). (Používáme Doolittlovu faktorizaci, platí tedy \(\matice L_{ii}=1\)) | ||
+ | |||
+ | 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 Q_X\matice R_X (\matice I + \matice F_k) \matice D^k \matice R_Y=\matice Q_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 Q_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 Q_X \left(\matice I+\matice G_k \right)\matice R_X\matice D^k \matice R_Y=\matice Q_X\matice Q_G^{(k)}\matice R_G^{(k)}\matice R_X\matice D^k \matice R_Y\] | ||
+ | kde jsme si v prvním rovnítku 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\). | ||
+ | V druhém rovnítku jsme použili QR rozklad: \((\matice I +\matice G_k)=\matice Q_G^{(k)}\matice R_G^{(k)}\). | ||
+ | Označíme–li si \(\matice R_G^{(k)}\matice R_X\matice D^k \matice R_Y\) jako \(\mathcal R_k\) a \(\mathcal Q_k=\matice Q_X\matice Q_G^{(k)}\), dokázali jsme, | ||
+ | že \(\matice A^k=\mathcal Q_k\mathcal R_k\). Dále jsme dokázali, že \(\mathcal Q_k \to \matice Q_X\) a \(\mathcal R_k \to \matice R_X\matice D^k \matice R_Y\), protože jde \(\matice G_k \to \Theta\), | ||
+ | jdou \(\matice Q_G^{(k)} \to \matice I\) a \(\matice R_G^{(k)} \to \matice I\). | ||
+ | Dále platí: | ||
+ | \[\matice T_k=(\matice Q_X\matice Q_G^{(k)})^T \matice A \matice Q_X\matice Q_G^{(k)}= | ||
+ | (\matice Q_G^{(k)})^T \matice Q_x^T \matice X\matice D\matice X^{-1}\matice Q_X\matice Q_G^{(k)} \rightarrow \matice R_X\matice D\matice R_X^{-1},\] | ||
+ | \todo{Opsáno ze sePlatnost} | ||
+ | Využili jsme, že platí | ||
+ | \[(\matice X=\matice Q_X\matice R_X)\implies(\matice Q_X^{-1}\matice X=\matice R_X).\] | ||
+ | Z věty \ref{SoucinTrojuhelniku} plyne, že \(\matice R_X\matice D\matice R_X^{-1}\) je horní trojúhelníková a \(\text{diag}~\matice R =\text{diag}~\matice D\). | ||
+ | Pro diagonální matici \(\matice A\) plyne diagonalita matice \(\matice T_k\), resp. \(\matice T\) ze Schurovy věty \ref{Schur}. | ||
\end{proof} | \end{proof} | ||
\end{theorem} | \end{theorem} | ||
− | + | ||
\subsection{Hessenbergovy QR iterace} | \subsection{Hessenbergovy QR iterace} | ||
− | + | ||
\begin{lemma} | \begin{lemma} | ||
\label{Hessenberg} | \label{Hessenberg} | ||
Matice \( \matice H^{( k )} \) v Hessenbergových QR iteracích je v Hessenberegově tvaru. | Matice \( \matice H^{( k )} \) v Hessenbergových QR iteracích je v Hessenberegově tvaru. | ||
\begin{proof} | \begin{proof} | ||
− | \ | + | \[ \matice H^{( k )}=\matice R^{(k)}\matice Q^{(k)}=\matice R^{(k)}\left(\matice G^{(k)}_{1,2}\right)^T\ldots\left(\matice G^{(k)}_{n-1,n}\right)^T\] |
+ | kde matice \(\left(\matice G^{(k)}_{n-1,n}\right)^T\) je Givensova matice, která rotuje \((n-1)\)–ní a \(n\)–tý řádek. Díky tomu nemohou při násobení horní trojúhelníkové matice \(\matice R\) | ||
+ | vzniknout nenulové prvky jinde, než těsně pod diagonálou, což je Hessenbergův tvar matice. | ||
\end{proof} | \end{proof} | ||
\end{lemma} | \end{lemma} |
Aktuální verze z 3. 6. 2024, 17:07
[ 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_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 alespoň jedna z 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 \) (může to být libovolná lineární kombinace vektorů \( \vec y^{( 1 )}, \dots, \vec y^{( r )} \)). \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{align} \label{momeiks} \vec x^{(k+1)}=\frac{1}{\vec e_1^T \matice A \vec x^{(k)}} \matice A \vec x^{(k)} \end{align} 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^{(k)}=\frac{\vec e_1^T \matice A \vec x^{(k)}}{\vec e_1^T\vec x^{(k)}}=\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 (dostaneme tam členy \(\frac{\lambda_m}{\lambda_1}, m \in \hat n\), které jsou menší než jedna, tudíž konvergují k 0), 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 \eqref{momeiks} a \ref{MocninnaMetodaVektor} platí \[ \vec x^{(k)}=\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\\ & \matice J_2^k\\ & & \ddots \end{matrix} \right) \matice T\vec x^{(0)}}=\frac{ \matice T^{-1}\left( \begin{matrix} 1\\ & (\frac{1}{\lambda_1}\matice 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^{(k)}\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^{(k)}\)) 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^{(k)}\) a přechodem k limitě 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ť \(\matice T \) převádí \(\matice A \) do Jordanova tvaru, tj. \(\matice A = \matice T^{-1} \matice J_{\matice A} \matice T\). Nechť je \( x^{( 0 )} \) takový, že alespoň jedna z prvních dvou složek vektoru\(\matice T x^{(0)}\) nenulová. 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á, tj. \(\nu_a(\lambda)=\nu_g(\lambda)\). 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} \begin{enumerate} \item (\textit{konvergence})\[\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_Y\matice R_Y\). 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 \matice L_{ii}\lambda_i^{-k} = 1 & i = j \\ \lambda_i^k \matice L_{ij}\lambda_j^{-k}=\matice L_{ij}\left(\frac{\lambda_i}{\lambda_j}\right)^k & i > j \\ \end{cases}\] Z uspořádání vlastních čísel 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 \). (Používáme Doolittlovu faktorizaci, platí tedy \(\matice L_{ii}=1\)) 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\), čímž je dokázána konvergence metody. \item (\textit{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 L_X=\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í \[\text{diag}~\matice R =\text{diag}~\matice D,\] z čehož plyne dokazované tvrzení. \qedhere \end{enumerate} \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á, tj. \(\nu_a(\lambda)=\nu_g(\lambda)\). 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} Protože musí být oba rozklady stejné, platí \(\matice R_k=\hat{\matice R}_k\) a \(\matice L_k=\prod_{i = 1}^k \hat{\matice L}_i \). Z toho plyne \[\matice A_k=\hat{\matice L}_k \hat{\matice R}_k= (\matice L_{k-1})^{-1}\matice L_k \matice R_k \to \matice L^{-1}\matice L \matice R=\matice R\] Z toho plyne, že \(\matice A_k \) z LR algoritmu konverguje k horní trojúhelníkové matici. Výskyt vlastních čísel plyne z podobnosti (viz \ref{LREigenvaluesTriv}). \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'\) (musí být rovnoběžné) 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 (z ortogonality matic \(\matice Q\) a \(\matice Q'\)) a \(\vec u + \vec v = \vec 0\), musí být \(\vec u = \vec 0\) a \(\vec v = \vec 0\) (jinak by nebyly OG). 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 z požadavku na kladnost diagonálních prvků \(\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} \] 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 pro počítání průmětů 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}, m=1,\ldots,k-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 )} \] Definujeme matici \( \matice R \): \[ \matice R_{ij} = \begin{cases} \braket{\vec a^{( j )} | \vec q^{( i )}} & i<j \\ \left\lVert \vec p^{( k )} \right\rVert_2 & i = j \\ 0 & i > j \\ \end{cases}\] Z toho plyne, že vznikne QR rozklad matice \(\matice A\): \[ \begin{pmatrix} \vec a^{( 1 )} & \vec a^{( 2 )} & \cdots & \vec a^{( n )}\\ \end{pmatrix}= \begin{pmatrix} \vec q^{( 1 )} & \vec q^{( 2 )} & \cdots & \vec q^{( n )} \\ \end{pmatrix} \begin{pmatrix} r_{11}& \ldots & r_{1n} \\ & \ddots & \vdots\\ & & r_{nn}\\ \end{pmatrix} \] \end{proof} \end{theorem} \subsection{Householderovy transformace} \setcounter{define}{31} \begin{theorem} Viz \ref{HouseholderReflekcni} Kvůli numerické stabilitě není dobré, pokud je rozdíl \(\vec e^{(1)}-\vec x\) malý (dělení malým číslem), volíme tedy \[\vec x=-\sgn(x_1)\left\lVert \vec x^{( k )} \right\rVert_2 \vec e^{(1)}\] \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} \[\matice A^k=\matice X \matice D^k \matice X^{-1}=\matice Q_X\matice R_X\matice D^k\matice L_Y\matice R_Y=\matice Q_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 QR rozklad \(\matice X=\matice Q_X\matice R_X\) a \textbf{LU rozklad} \(\matice X^{-1}=\matice Y=\matice L_Y\matice R_Y\). V posledním jsme vložili identitu, protože potřebujeme dostat matici \(\matice D^k\) za \(\matice L_Y\). Nyní dokážeme (stejně jako u trojúhelníkové metody), ž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 \matice L_{ii}\lambda_i^{-k} = 1 & i = j \\ \lambda_i^k \matice L_{ij}\lambda_j^{-k}=\matice L_{ij}\left(\frac{\lambda_i}{\lambda_j}\right)^k & i > j \\ \end{cases}\] Z uspořádání vlastních čísel 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 \). (Používáme Doolittlovu faktorizaci, platí tedy \(\matice L_{ii}=1\)) 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 Q_X\matice R_X (\matice I + \matice F_k) \matice D^k \matice R_Y=\matice Q_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 Q_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 Q_X \left(\matice I+\matice G_k \right)\matice R_X\matice D^k \matice R_Y=\matice Q_X\matice Q_G^{(k)}\matice R_G^{(k)}\matice R_X\matice D^k \matice R_Y\] kde jsme si v prvním rovnítku 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\). V druhém rovnítku jsme použili QR rozklad: \((\matice I +\matice G_k)=\matice Q_G^{(k)}\matice R_G^{(k)}\). Označíme–li si \(\matice R_G^{(k)}\matice R_X\matice D^k \matice R_Y\) jako \(\mathcal R_k\) a \(\mathcal Q_k=\matice Q_X\matice Q_G^{(k)}\), dokázali jsme, že \(\matice A^k=\mathcal Q_k\mathcal R_k\). Dále jsme dokázali, že \(\mathcal Q_k \to \matice Q_X\) a \(\mathcal R_k \to \matice R_X\matice D^k \matice R_Y\), protože jde \(\matice G_k \to \Theta\), jdou \(\matice Q_G^{(k)} \to \matice I\) a \(\matice R_G^{(k)} \to \matice I\). Dále platí: \[\matice T_k=(\matice Q_X\matice Q_G^{(k)})^T \matice A \matice Q_X\matice Q_G^{(k)}= (\matice Q_G^{(k)})^T \matice Q_x^T \matice X\matice D\matice X^{-1}\matice Q_X\matice Q_G^{(k)} \rightarrow \matice R_X\matice D\matice R_X^{-1},\] \todo{Opsáno ze sePlatnost} Využili jsme, že platí \[(\matice X=\matice Q_X\matice R_X)\implies(\matice Q_X^{-1}\matice X=\matice R_X).\] Z věty \ref{SoucinTrojuhelniku} plyne, že \(\matice R_X\matice D\matice R_X^{-1}\) je horní trojúhelníková a \(\text{diag}~\matice R =\text{diag}~\matice D\). Pro diagonální matici \(\matice A\) plyne diagonalita matice \(\matice T_k\), resp. \(\matice T\) ze Schurovy věty \ref{Schur}. \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} \[ \matice H^{( k )}=\matice R^{(k)}\matice Q^{(k)}=\matice R^{(k)}\left(\matice G^{(k)}_{1,2}\right)^T\ldots\left(\matice G^{(k)}_{n-1,n}\right)^T\] kde matice \(\left(\matice G^{(k)}_{n-1,n}\right)^T\) je Givensova matice, která rotuje \((n-1)\)–ní a \(n\)–tý řádek. Díky tomu nemohou při násobení horní trojúhelníkové matice \(\matice R\) vzniknout nenulové prvky jinde, než těsně pod diagonálou, což je Hessenbergův tvar matice. \end{proof} \end{lemma}