01NUM1:Kapitola2: Porovnání verzí

Z WikiSkripta FJFI ČVUT v Praze
Přejít na: navigace, hledání
m (TODO k dk2.46 (obhájit D > 0))
(label pro lemma v konvergence geometrické posloupnosti.)
 
(Není zobrazeno 45 mezilehlých verzí od 6 dalších uživatelů.)
Řádka 1: Řádka 1:
 
%\wikiskriptum{01NUM1}
 
%\wikiskriptum{01NUM1}
 
\section{Opakování a doplnění znalostí z lineární algebry}
 
\section{Opakování a doplnění znalostí z lineární algebry}
 
+
 
\subsection{Trojúhelníkové matice}
 
\subsection{Trojúhelníkové matice}
 
+
 
\setcounter{define}{21}
 
\setcounter{define}{21}
 
\begin{theorem}
 
\begin{theorem}
Řádka 41: Řádka 41:
 
\end{proof}
 
\end{proof}
 
\end{theorem}
 
\end{theorem}
 
+
 
\subsection{Rozklad matice na horní a dolní trojúhelníkovou}
 
\subsection{Rozklad matice na horní a dolní trojúhelníkovou}
 
   
 
   
Řádka 94: Řádka 94:
 
   \begin{pmatrix}
 
   \begin{pmatrix}
 
   \matice {L' D' R'} & \matice {L' D'} \vec r \\
 
   \matice {L' D' R'} & \matice {L' D'} \vec r \\
   \vec l^T \matice {D' R'} & \vec r \vec l^T \matice D' + d \\
+
   \vec l^T \matice {D' R'} & \vec l^T \matice D' \vec r + d \\
 
   \end{pmatrix} =
 
   \end{pmatrix} =
 
   \begin{pmatrix}
 
   \begin{pmatrix}
Řádka 103: Řádka 103:
 
Chceme tedy určit \( \vec l \), \( \vec r \) a \( d \). Protože je \( \matice A \) silně regulární, je \( \matice A' \) v každém kroku regulární a tedy i \( \matice L' \), \( \matice D' \) a \( \matice R' \) jsou regulární. Upravíme \( \matice {L' D'} \vec r = \vec v \) a tím určíme \( \vec r = \left( \matice {L' D'} \right)^{-1} \vec v \). Obdobně
 
Chceme tedy určit \( \vec l \), \( \vec r \) a \( d \). Protože je \( \matice A \) silně regulární, je \( \matice A' \) v každém kroku regulární a tedy i \( \matice L' \), \( \matice D' \) a \( \matice R' \) jsou regulární. Upravíme \( \matice {L' D'} \vec r = \vec v \) a tím určíme \( \vec r = \left( \matice {L' D'} \right)^{-1} \vec v \). Obdobně
 
\[ \vec l^T \matice {D' R'} = \vec u^T \Rightarrow \vec l = ((\matice {D' R'})^T)^{-1} \vec u \]
 
\[ \vec l^T \matice {D' R'} = \vec u^T \Rightarrow \vec l = ((\matice {D' R'})^T)^{-1} \vec u \]
\[ d = \alpha - \vec r \vec l^T \matice D' \]
+
\[ d = \alpha - \vec l^T \matice D' \vec r \]
 
\end{itemize}
 
\end{itemize}
 
\item jednoznačnost
 
\item jednoznačnost
Řádka 120: Řádka 120:
 
   
 
   
 
\begin{remark*}
 
\begin{remark*}
Čísla na diagonále matice \( \matice D \) z \ref{LDR} \textbf{nejsou} vlastními čísly matice \( \matice A \)
+
Čísla na diagonále matice \( \matice D \) z \ref{LDR} \textbf{nejsou} vlastními čísly matice \( \matice A \) (jsou to pivoty GEM, viz \ref{GEMRegularni}).
 
\end{remark*}
 
\end{remark*}
 
+
 
+
 
\subsection{Rozklady matic}
 
\subsection{Rozklady matic}
 
   
 
   
Řádka 133: Řádka 133:
 
\begin{enumerate}[(1)]
 
\begin{enumerate}[(1)]
 
  \item Hermitovskost (\( \matice H^*( \vec w ) = \matice H( \vec w ) \))
 
  \item Hermitovskost (\( \matice H^*( \vec w ) = \matice H( \vec w ) \))
   \[ \matice H^*( \vec w ) = ( \matice I - 2 \vec w \vec w^*) = \matice I^* - 2 ( \vec w \vec w^* )^* = \matice I - 2 \vec w \vec w^* = \matice H ( \vec w ) \]
+
   \[ \matice H^*( \vec w ) = ( \matice I - 2 \vec w \vec w^* )^* = \matice I^* - 2 ( \vec w \vec w^* )^* = \matice I - 2 \vec w \vec w^* = \matice H ( \vec w ) \]
 
  \item Unitarita (\( \matice H^*( \vec w ) = \matice H^{-1}( \vec w ) \))
 
  \item Unitarita (\( \matice H^*( \vec w ) = \matice H^{-1}( \vec w ) \))
 
   \\ Díky hermitovskosti matice a vztahu \( \vec w^* \vec w = \braket{\vec w | \vec w } = {\lVert \vec w \rVert}^2 = 1 \) platí:
 
   \\ Díky hermitovskosti matice a vztahu \( \vec w^* \vec w = \braket{\vec w | \vec w } = {\lVert \vec w \rVert}^2 = 1 \) platí:
Řádka 140: Řádka 140:
 
\end{proof}
 
\end{proof}
 
\end{theorem}
 
\end{theorem}
 
+
 +
\begin{theorem}[Unitární matice zachovává normu]
 +
\label{UnitarniZachovavaNormu}
 +
Nechť \( \matice U \) je unitární matice. Pak platí:
 +
\[ \lVert \matice U \vec x \rVert_2 = \lVert \vec x \rVert_2 \]
 +
Pro libovolný vektor \( \vec x \).
 +
\begin{proof}
 +
\[ \lVert \matice U \vec x \rVert_2^2 = \braket{\matice U \vec x | \matice U \vec x} = ( \matice U \vec x )^* \matice U \vec x = \vec x^* \matice U^* \matice U \vec x = \vec x^* \matice U^{-1} \matice U \vec x = \vec x^* \vec x = \braket{\vec x | \vec x} = \lVert \vec x \rVert_2^2 \]
 +
\end{proof}
 +
\end{theorem}
 +
 
\begin{theorem}
 
\begin{theorem}
 
\label{HouseholderReflekcni}
 
\label{HouseholderReflekcni}
\( \matice H( \vec w )\) je Householderova reflekční matice a \( \vec w \) je libovolný vektor z \( \mathbbm C^n \).  
+
\( \matice H( \vec w )\) je Householderova reflekční matice a \( \vec v \) je libovolný vektor z \( \mathbbm C^n \).  
 
\\ Pak vektor \( \matice H( \vec w ) \vec v \) je zrcadlový obraz vektoru \( \vec v \) podle nadroviny \[ L = \{ \vec x \in \mathbbm C^n \; | \; \vec w^* \vec x = \braket{ \vec x | \vec w } = 0 \} \] v tom smyslu, že splňuje
 
\\ Pak vektor \( \matice H( \vec w ) \vec v \) je zrcadlový obraz vektoru \( \vec v \) podle nadroviny \[ L = \{ \vec x \in \mathbbm C^n \; | \; \vec w^* \vec x = \braket{ \vec x | \vec w } = 0 \} \] v tom smyslu, že splňuje
 
\begin{itemize}
 
\begin{itemize}
Řádka 159: Řádka 169:
 
\end{proof}
 
\end{proof}
 
\end{theorem}
 
\end{theorem}
 
+
\begin{theorem}
+
\label{UnitarniZachovavaNormu}
+
Nechť \( \matice U \) je unitární matice. Pak platí:
+
\[ \lVert \matice U \vec x \rVert_2 = \lVert \vec x \rVert_2 \]
+
Pro libovolný vektor \( \vec x \). (tj. Unitární matice zachovává normu. )
+
\begin{proof}
+
\[ \lVert \matice U \vec x \rVert_2^2 = \braket{\matice U \vec x | \matice U \vec x} = ( \matice U \vec x )^* \matice U \vec x = \vec x^* \matice U^* \matice U \vec x = \vec x^* \matice U^{-1} \matice U \vec x = \vec x^* \vec x = \braket{\vec x | \vec x} = \lVert \vec x \rVert_2^2 \]
+
\end{proof}
+
\end{theorem}
+
 
+
 
\begin{theorem}
 
\begin{theorem}
 
\label{HouseholderEigenvalue}
 
\label{HouseholderEigenvalue}
 
Nechť \(\lambda\) je vlastní číslo matice \(\matice A\), pak existuje Householderova matice \(\matice H(\vec w)\) taková, že  
 
Nechť \(\lambda\) je vlastní číslo matice \(\matice A\), pak existuje Householderova matice \(\matice H(\vec w)\) taková, že  
\[\underbrace{\matice H(\vec w)\matice A\matice H(\vec w)}_{\matice M}\vec e^{(1)}=\lambda\vec e^{(1)}\] kde \( \vec e^{(1)} \) je prvním bazickým vektorem a je vlastní vektor matice \(\matice M\).  
+
\[\matice H(\vec w)\matice A\matice H(\vec w)\vec e^{(1)}=\lambda\vec e^{(1)}\] kde \( \vec e^{(1)} \) je prvním bazickým vektorem.
 
\begin{proof}
 
\begin{proof}
Nechť \( \lambda \in \sigma ( \matice A ) \) a \(\vec x\) příslušný vlastní vektor. Chceme určit \(\matice H (\vec w)\) tak, že \(\matice H (\vec w)\vec x = \lVert \vec x \rVert \vec e^{(1)}\).
+
Nechť \( \lambda \in \sigma ( \matice A ) \) a \(\vec x\) příslušný vlastní vektor. Volíme \(\vec w\) tak, aby zobrazil vektor \(\vec x\) do směru vektoru \(\vec e^{(1)}\). Podle \ref{HouseholderReflekcni} musí platit:
% jak to říct?: (Jen když bude \(\vec x\) normovaný, promítne se přímo na \(\vec e^{(1)}\), neboť \(\matice H (\vec w)\) zachovává normu.)
+
\[\matice H (\vec w)\vec e^{(1)} = \vec x \Rightarrow (\vec x + \vec e^{(1)} ) \in L\]
 
+
\[\vec w=(\vec x - \vec e^{(1)} ) \perp L\]
Volíme \[ \vec w = \frac{\vec e^{(1)}-\frac{\vec x}{\lVert \vec x \rVert_2}}{\lVert \vec e^{(1)}-\frac{\vec x}{\lVert \vec x \rVert_2}\rVert_2} \]
+
Zvolíme tedy \( \vec w \) takto:
 +
\[ \vec w = \frac{\vec e^{(1)}-\frac{\vec x}{\lVert \vec x \rVert_2}}{\lVert \vec e^{(1)}-\frac{\vec x}{\lVert \vec x \rVert_2}\rVert_2} \]
 
a pokud vezmeme \(\vec x\) jako normovaný:
 
a pokud vezmeme \(\vec x\) jako normovaný:
 
\[ \vec w = \frac{\vec e^{(1)}-\vec x}{\lVert \vec e^{(1)} - \vec x \rVert_2} \]
 
\[ \vec w = \frac{\vec e^{(1)}-\vec x}{\lVert \vec e^{(1)} - \vec x \rVert_2} \]
protože z \ref{HouseholderHermUnit} platí \(\matice H (\vec w) = \matice H^* (\vec w) = \matice H^{-1} (\vec w)\) a volbě \(\vec w\)
+
Protože je Householedora matice unitární, musíme vektor \(\vec x\) normovat, jinak by totiž \(\matice H(\vec w)\vec x\) nemohl být jednotkový vektor.
\[\matice H (\vec w)\vec x = \vec e^{(1)} \Leftrightarrow \matice H (\vec w)\vec e^{(1)} = \vec x\]
+
Z volby \( \vec w \) pak plyne:
% \[\matice A \matice H (\vec w)\vec e^{(1)} = \matice A \vec x = \lambda \vec x\]
+
\[\matice A \matice H (\vec w)\vec e^{(1)} = \matice A \vec x = \lambda \vec x\]
% \[\matice H (\vec w)\matice A \matice H (\vec w)\vec e^{(1)} = \lambda \matice H(\vec w)\vec x \todo{Proč?} = \lambda \vec e^{(1)}\]
+
\[\matice H (\vec w)\matice A \matice H (\vec w)\vec e^{(1)} = \lambda \matice H(\vec w)\vec x = \lambda \vec e^{(1)},\]
\[\matice H (\vec w)\matice A \underbrace{\matice H (\vec w)\vec e^{(1)}}_{\vec x} = \matice H (\vec w)\matice A \vec x = \matice H (\vec w)\lambda\vec x = \lambda \matice H(\vec w)\vec x = \lambda \vec e^{(1)}\]
+
což dokazuje větu.
 
\end{proof}
 
\end{proof}
 
\end{theorem}
 
\end{theorem}
 +
 +
\begin{remark*}
 +
Je jedno, jestli bude vektor \(\vec w\) mířit na jednu, nebo na druhou stranu. zásadní je pouze kolmost na L.
 +
\end{remark*}
  
 
\begin{remark*}
 
\begin{remark*}
Řádka 197: Řádka 202:
 
\end{pmatrix}\)
 
\end{pmatrix}\)
 
\end{remark*}
 
\end{remark*}
 
+
 
\begin{remark*}
 
\begin{remark*}
 
\(\matice M = \matice H (\vec w)\matice A \matice H (\vec w)\) je podobnostní transformace.
 
\(\matice M = \matice H (\vec w)\matice A \matice H (\vec w)\) je podobnostní transformace.
 
\end{remark*}
 
\end{remark*}
 
+
\begin{theorem}[Schurova Věta]  
+
\begin{theorem}[Schurova věta]  
 
\label{Schur}
 
\label{Schur}
 
Libovolná matice \(\matice A \in \matice C^{n,n} \) se dá zapsat jako \[\matice A = \matice U^* \matice R \matice U \]
 
Libovolná matice \(\matice A \in \matice C^{n,n} \) se dá zapsat jako \[\matice A = \matice U^* \matice R \matice U \]
Řádka 248: Řádka 253:
 
\end{pmatrix}\]\[=
 
\end{pmatrix}\]\[=
 
\begin{pmatrix}  
 
\begin{pmatrix}  
\lambda_1 & 0 & \cdots \\
+
\lambda_1 & r_1 & \cdots \\
 
0 & \lambda_2 & \cdots \\
 
0 & \lambda_2 & \cdots \\
 
\vdots & 0 & \multirow{3}{*}{ \huge {\( \matice A'' \)} }\\
 
\vdots & 0 & \multirow{3}{*}{ \huge {\( \matice A'' \)} }\\
Řádka 254: Řádka 259:
 
0 & 0 & \\
 
0 & 0 & \\
 
\end{pmatrix}\]
 
\end{pmatrix}\]
Naprosto stejným postupem pokračujeme dále, až dojdeme k matici obsahující pouze vlastní čísla matice \(\matice A\). Tu označíme jako matici \(\matice R\). Dále označíme
+
Naprosto stejným postupem pokračujeme dále, až dojdeme k matici obsahující na diagonále vlastní čísla matice \(\matice A\) a případné další nenulové prvky nad diagonálou (ty tam kvůli jedničkám v maticích \(\matice H_2\) a dalších zůstanou). Tu označíme jako matici \(\matice R\). Dále označíme
 
\[ \matice U = \prod_{i = 0}^{n - 1} \matice H_{n - i} \]
 
\[ \matice U = \prod_{i = 0}^{n - 1} \matice H_{n - i} \]
 
Protože jsou všechny matice \(\matice H(\vec w_k)\) Householderovy reflekční matice, jsou podle \ref{HouseholderHermUnit} unitární. Součin unitárních matic je unitární matice (důkaz na dva řádky je trivální), tedy celá matice \(\matice U\) je unitární. Matice \(\matice U^{-1}\) bude mít tvar \(\matice H_1 \matice H_2 ... \matice H_n \). To už je ekvivalentní s tvrzením věty: \[\matice U^* \matice A \matice U = \matice R \Leftrightarrow \matice A = \matice U^* \matice R \matice U\]
 
Protože jsou všechny matice \(\matice H(\vec w_k)\) Householderovy reflekční matice, jsou podle \ref{HouseholderHermUnit} unitární. Součin unitárních matic je unitární matice (důkaz na dva řádky je trivální), tedy celá matice \(\matice U\) je unitární. Matice \(\matice U^{-1}\) bude mít tvar \(\matice H_1 \matice H_2 ... \matice H_n \). To už je ekvivalentní s tvrzením věty: \[\matice U^* \matice A \matice U = \matice R \Leftrightarrow \matice A = \matice U^* \matice R \matice U\]
 
\end{proof}
 
\end{proof}
 
\end{theorem}
 
\end{theorem}
 
+
\begin{theorem} % V2.40
+
\begin{theorem}
 
\label{NormalniTrojuhelnikDiagonalni}
 
\label{NormalniTrojuhelnikDiagonalni}
 
Normální trojúhelníková matice je diagonální.
 
Normální trojúhelníková matice je diagonální.
%\begin{proof} % To musi byt dukaz k necemu jinemu. (PS umim to snadno ukazat na unitarni i na hermitovske z 2.22 a 2.23, ale ne na normalni.)
+
\begin{proof}
%Ukážeme, že \( \matice R \) z \ref{Schur} je normální:
+
Nechť je matice \( \matice A \in \mathbbm C^{n, n} \) normální dolní trojúhelníková. Pak platí \( \matice A^* \matice A = \matice A \matice A^* \) a \( \matice A_{ik} = 0,\; \forall i < k \) a dále:
%\[ \matice A = \matice U^* \matice R \matice U \Rightarrow \matice R = \matice U \matice A \matice U^* \]
+
\[ (\matice A ^* \matice A)_{ii} = \sum_{k = 1}^n (\matice A^*)_{ik} \matice A_{ki} = \sum_{k = i}^n (\matice A^*)_{ik} \matice A_{ki} = \sum_{k = i}^n \overline{\matice A_{ki}} \matice A_{ki} = \sum_{k = i}^n \lvert \matice A_{ki} \rvert^2 \]
%\[ \matice R^* = ( \matice U \matice A \matice U^* )^* = \matice U \matice A^* \matice U^* \]
+
\[ (\matice A \matice A^*)_{ii} = \sum_{k = 1}^n \matice A_{ik} (\matice A^*)_{ki} = \sum_{k = 1}^i \matice A_{ik} (\matice A^*)_{ki} = \sum_{k = 1}^i \matice A_{ik} \overline{ \matice A_{ik}} = \sum_{k = 1}^i \lvert \matice A_{ik} \rvert^2 \]
%\[ \matice{R R^*} = \matice{R^* R} \]
+
\[ (\matice A^* \matice A)_{ii} = (\matice A^* \matice A)_{ii} \Leftrightarrow \sum_{k = i}^n \lvert \matice A_{ki} \rvert^2 = \sum_{k = 1}^i \lvert \matice A_{ik} \rvert^2, \; \forall i \in \hat n \]
%Oberhuberův důkaz nic nedokazuje.
+
%\end{proof}
+
\begin{proof} % takovy dukaz je ve Dvořákové jako Lemma 6 v 6.1 Vlastnosti normálních matic @ s. 41
+
Mlhův důkaz: Nechť je matice \( \matice A \in \mathbbm C^{n, n} \) normální dolní trojúhelníková. Pak platí \( \matice A^* \matice A = \matice A \matice A^* \) a \( \matice A_{ik} = 0,\; \forall i < k \) a dále:
+
\[ (\matice A^* \matice A)_{ii} = \sum_{k = 1}^n \matice (A^*)_{ik} \matice A_{ki} = \sum_{k = 1}^i \matice (A^*)_{ik} \matice A_{ki} = \sum_{k = 1}^i \overline{\matice A_{ki}} \matice A_{ki} = \sum_{k = 1}^i \lvert \matice A_{ki} \rvert^2 \]
+
\[ (\matice A \matice A^*)_{ii} = \sum_{k = 1}^n \matice A_{ik} \matice (A^*)_{ki} = \sum_{k = i}^n \matice A_{ik} \matice (A^*)_{ki} = \sum_{k = i}^n \matice A_{ik} \overline{ \matice A_{ik}} = \sum_{k = i}^n \lvert \matice A_{ik} \rvert^2 \]
+
\[ (\matice A^* \matice A)_{ii} = (\matice A^* \matice A)_{ii} \Leftrightarrow \sum_{k = 1}^i \lvert \matice A_{ki} \rvert^2 = \sum_{k = i}^n \lvert \matice A_{ik} \rvert^2, \; \forall i \in \hat n \]
+
 
Důkaz provedeme indukcí podle \( i \)
 
Důkaz provedeme indukcí podle \( i \)
 
\begin{itemize}
 
\begin{itemize}
Řádka 288: Řádka 286:
 
\end{proof}
 
\end{proof}
 
\end{theorem}
 
\end{theorem}
 
+
\begin{theorem} % Schurova V pro normalni matice
+
\begin{theorem}
 
\label{RozklNormMatice}
 
\label{RozklNormMatice}
 
Pro libovolnou normální matici \(\matice A\) existuje unitární matice \(\matice U\) tak, že  
 
Pro libovolnou normální matici \(\matice A\) existuje unitární matice \(\matice U\) tak, že  
Řádka 298: Řádka 296:
 
\item Ukážeme, že \(\matice R\) je normální, pak podle \ref{NormalniTrojuhelnikDiagonalni} bude také diagonální.
 
\item Ukážeme, že \(\matice R\) je normální, pak podle \ref{NormalniTrojuhelnikDiagonalni} bude také diagonální.
 
\[\matice A = \matice {U^*RU} \Rightarrow \matice {UA} = \matice {RU} \Rightarrow \matice {UAU^*} = \matice R\]
 
\[\matice A = \matice {U^*RU} \Rightarrow \matice {UA} = \matice {RU} \Rightarrow \matice {UAU^*} = \matice R\]
\[\matice R^* = \matice {(UAU^*)^*} = \matice {(AU^*)^*U^*} \matice {UA^*U^*} \]
+
\[\matice R^* = \matice {(UAU^*)^*} = \matice {(AU^*)^*U^*} = \matice {UA^*U^*} \]
 
\[\matice {RR^*} = \matice {UA}\underbrace{\matice{U^*U}}_{\matice I}\matice {A^*U^*} = \matice {UAA^*U^*} = \matice {UA^*AU^*} = \matice {UA^*U^*UAU^*} = \matice{R^*R}\]
 
\[\matice {RR^*} = \matice {UA}\underbrace{\matice{U^*U}}_{\matice I}\matice {A^*U^*} = \matice {UAA^*U^*} = \matice {UA^*AU^*} = \matice {UA^*U^*UAU^*} = \matice{R^*R}\]
 
\(\Rightarrow \matice R \) je normální \(\Rightarrow \matice R\) je diagonální.
 
\(\Rightarrow \matice R \) je normální \(\Rightarrow \matice R\) je diagonální.
Řádka 304: Řádka 302:
 
\[\matice A = \matice {U^*DU} \Rightarrow \matice D = \matice {UAU^*}\]
 
\[\matice A = \matice {U^*DU} \Rightarrow \matice D = \matice {UAU^*}\]
 
kde \(\matice D\) je diagonální matice.
 
kde \(\matice D\) je diagonální matice.
\[\matice D^* = \matice {(UAU^*)^*} = \matice {UA^*U^*} \underbrace{\Rightarrow}_{\matice A = \matice A^*} \matice {UAU^*} = D\]
+
\[\matice D^* = \matice {(UAU^*)^*} = \matice {UA^*U^*} \underbrace{\Rightarrow}_{\matice A = \matice A^*} \matice {UAU^*} = \matice {D} \]
 
\[\matice D^* = \matice D \Rightarrow \matice D \in \matice R^{n,n}\] protože transpozicí se diagonálních prvků nedotkneme a rovnost hermitovsky sdružených prvků nastává pokud jsou prvky reálná čísla. \qedhere
 
\[\matice D^* = \matice D \Rightarrow \matice D \in \matice R^{n,n}\] protože transpozicí se diagonálních prvků nedotkneme a rovnost hermitovsky sdružených prvků nastává pokud jsou prvky reálná čísla. \qedhere
 
\end{enumerate}
 
\end{enumerate}
 
\end{proof}
 
\end{proof}
 
\end{theorem}
 
\end{theorem}
 
+
 
\subsection{Rozklady matic - Jordanova Věta}
 
\subsection{Rozklady matic - Jordanova Věta}
 
+
 
\begin{theorem}[Jordan]
 
\begin{theorem}[Jordan]
 
\label{Jordan}
 
\label{Jordan}
Řádka 331: Řádka 329:
 
\end{pmatrix}, \;
 
\end{pmatrix}, \;
 
\forall k \in \hat p \]
 
\forall k \in \hat p \]
 +
Počet bloků příslušejících k \(\lambda\) je roven \(\nu_g(\lambda)\) a součet řádů těchto bloků je \(\nu_a(\lambda)\).
 
Matice \( \matice J \) je až na pořadí bloků dána jednoznačně.
 
Matice \( \matice J \) je až na pořadí bloků dána jednoznačně.
 
\begin{proof}\renewcommand{\qedsymbol}{}
 
\begin{proof}\renewcommand{\qedsymbol}{}
Řádka 336: Řádka 335:
 
\end{proof}
 
\end{proof}
 
\end{theorem}
 
\end{theorem}
 
+
 
\begin{theorem*}[Věta navíc]
 
\begin{theorem*}[Věta navíc]
 
\label{DefiniceMocninyMatice}
 
\label{DefiniceMocninyMatice}
\todo{Předělat neceločíselně}
+
\todo{Předělat neceločíselně, nebo vymazat, tuhle větu si Mlha vycucal z prstu, protože při psaní skript zápasil s tím, že jsme tu mocninu vůbec nedefinovali. Na zkoušce mi Oberhuber řekl, že by to definoval Schurovsky, ale on každý přístup má něco.}
 
Nechť \( \matice A \in \mathbbm C^{n, n} \). Definujeme pro \( p \in \mathbbm N \) mocninu matice \( \matice A^p \) takto:
 
Nechť \( \matice A \in \mathbbm C^{n, n} \). Definujeme pro \( p \in \mathbbm N \) mocninu matice \( \matice A^p \) takto:
 
\[ \matice A^p = \prod_{k = 1}^p \matice A \]
 
\[ \matice A^p = \prod_{k = 1}^p \matice A \]
Řádka 358: Řádka 357:
 
\end{proof}
 
\end{proof}
 
\end{theorem*}
 
\end{theorem*}
 
+
 
\begin{remark*}
 
\begin{remark*}
 
V prezentaci je mocnina matice definována pomocí Schurovy věty, kde je navíc přidán požadavek, aby matice \( \matice A \) byla hermitovská a pozitivně definitní, díky čemuž je matice \( \matice R \) diagonální s kladnými členy a tím pádem se Schurova věta stává speciálním případem věty Jordanovy. Tato definice umožní jednoduše definovat i neceločíselné mocniny. Předešlá věta v prezentaci chybí, přestože je občas používána.
 
V prezentaci je mocnina matice definována pomocí Schurovy věty, kde je navíc přidán požadavek, aby matice \( \matice A \) byla hermitovská a pozitivně definitní, díky čemuž je matice \( \matice R \) diagonální s kladnými členy a tím pádem se Schurova věta stává speciálním případem věty Jordanovy. Tato definice umožní jednoduše definovat i neceločíselné mocniny. Předešlá věta v prezentaci chybí, přestože je občas používána.
 
\end{remark*}
 
\end{remark*}
 
+
 
\subsection{Vlastní čísla matice}
 
\subsection{Vlastní čísla matice}
 
+
 
\setcounter{define}{43}
 
\setcounter{define}{43}
 
\begin{theorem}
 
\begin{theorem}
Řádka 375: Řádka 374:
 
\end{proof}
 
\end{proof}
 
\end{theorem}
 
\end{theorem}
 
+
 
\subsection{Pozitivně definitní matice}
 
\subsection{Pozitivně definitní matice}
 
+
 
\begin{define}
 
\begin{define}
 
Matice \(\matice A \in \mathbbm T^{n, n}\) je pozitivně definitní \(\Leftrightarrow\) \[ \forall \vec x \neq \vec 0, \; \vec x^*\matice A \vec x \in \matice R^+\]
 
Matice \(\matice A \in \mathbbm T^{n, n}\) je pozitivně definitní \(\Leftrightarrow\) \[ \forall \vec x \neq \vec 0, \; \vec x^*\matice A \vec x \in \matice R^+\]
Řádka 383: Řádka 382:
 
Platí-li pro \(\matice B \in \matice T^{n, n} \) vztah \( \matice A - \matice B > 0 \), pak píšeme \(\matice A > \matice B \).
 
Platí-li pro \(\matice B \in \matice T^{n, n} \) vztah \( \matice A - \matice B > 0 \), pak píšeme \(\matice A > \matice B \).
 
\end{define}
 
\end{define}
 
+
\begin{theorem} % V2.46
+
\begin{theorem}
 +
\label{PDEigenvalues}
 
Všechna vlastní čísla pozitivně definitní matice \(\matice A\) jsou kladná. Je-li \(\matice A\) hermitovská matice s kladnými vlastními čísly, pak \(\matice A\) je pozitivně definitní.
 
Všechna vlastní čísla pozitivně definitní matice \(\matice A\) jsou kladná. Je-li \(\matice A\) hermitovská matice s kladnými vlastními čísly, pak \(\matice A\) je pozitivně definitní.
 
\begin{proof}
 
\begin{proof}
 
\begin{itemize}
 
\begin{itemize}
 
\item Nechť \(\lambda\) vlastní číslo \(\matice A\) a \(\vec x\) příslušný vlastní vektor.
 
\item Nechť \(\lambda\) vlastní číslo \(\matice A\) a \(\vec x\) příslušný vlastní vektor.
\[\braket{\matice A \vec x| \vec x} = \braket{\lambda \vec x|\vec x} = \lambda \lVert \vec x \rVert ^2_2 > 0 \Rightarrow \lambda > 0\]
+
\[ 0 < \braket{\matice A \vec x| \vec x} = \braket{\lambda \vec x|\vec x} = \lambda \lVert \vec x \rVert ^2_2 \Rightarrow \lambda > 0\]
\item Podle \ref{Schur} \(\matice A = \matice{U^* D U}\) kde \(\matice D > 0 \)\todo{Proč? (sice triviální, ale \ldots) Na diagonále jsou kladná real. čísla z \ref{RozklNormMatice} a \ref{PodobneEigenvalue}, ale nikde neříkám, že to stačí. }. Vezmu tedy libovolný vektor \(\vec x \neq \vec 0\) a z něj určíme vektor \(\vec y = \matice U \vec x \Rightarrow \vec y \neq \vec 0\)
+
\item Podle \ref{RozklNormMatice} \(\matice A = \matice{U^* D U}\) kde \( \matice D \) je diagonální, a tedy kladná. Vezmu tedy libovolný vektor \(\vec x \neq \vec 0\) a vektor \(\vec y = \matice U \vec x \Rightarrow \vec y \neq \vec 0\)
\[\braket{\matice A \vec x|\vec x} = \braket{\matice{U^*DU}\vec x|\vec x} = \braket{\matice {DU}\vec x|\matice U\vec x} = \braket{\matice D \vec y|\vec y}=\underbrace{\vec y^*\matice D\vec y > 0}_{\matice D > 0} \Rightarrow \]
+
\[\braket{\matice A \vec x|\vec x} = \braket{\matice{U^*DU}\vec x|\vec x} = \braket{\matice {DU}\vec x|\matice U\vec x} = \braket{\matice D \vec y|\vec y}=\vec y^*\matice D\vec y > 0 \]
\[\braket{\matice A \vec x|\vec x} > 0 \forall \vec x \Leftright \matice A >0\]
+
 
\end{itemize}
 
\end{itemize}
 
\end{proof}
 
\end{proof}
 
\end{theorem}
 
\end{theorem}
 
+
 
\subsection{Normy}
 
\subsection{Normy}
 
+
 
\setcounter{define}{52}
 
\setcounter{define}{52}
 
\begin{theorem}
 
\begin{theorem}
Řádka 408: Řádka 407:
 
\end{proof}
 
\end{proof}
 
\end{theorem}
 
\end{theorem}
 
+
 
\begin{theorem}
 
\begin{theorem}
 
\label{KonvergenceVNorme}
 
\label{KonvergenceVNorme}
Řádka 419: Řádka 418:
 
\end{proof}
 
\end{proof}
 
\end{theorem}
 
\end{theorem}
 
+
 
\setcounter{define}{59}
 
\setcounter{define}{59}
 
\begin{theorem}
 
\begin{theorem}
Řádka 427: Řádka 426:
 
\[ \lVert \matice A \rVert_1 = \max\limits_{\lVert \vec x \rVert _1 = 1} \lVert \matice A \vec x \rVert_1 \]
 
\[ \lVert \matice A \rVert_1 = \max\limits_{\lVert \vec x \rVert _1 = 1} \lVert \matice A \vec x \rVert_1 \]
 
\[ \lVert \matice A \rVert_2 = \max\limits_{\lVert \vec x \rVert _2 = 1} \lVert \matice A \vec x \rVert_2 \]
 
\[ \lVert \matice A \rVert_2 = \max\limits_{\lVert \vec x \rVert _2 = 1} \lVert \matice A \vec x \rVert_2 \]
 
+
 
pro každou matici \( \matice A \in \mathbbm C^{n, n} \) platí vztahy:
 
pro každou matici \( \matice A \in \mathbbm C^{n, n} \) platí vztahy:
 
\[ \lVert \matice A \rVert_\infty = \max\limits_{i \in \hat n} \sum_{j = 1}^n \lvert \matice A_{ij} \rvert \]
 
\[ \lVert \matice A \rVert_\infty = \max\limits_{i \in \hat n} \sum_{j = 1}^n \lvert \matice A_{ij} \rvert \]
Řádka 450: Řádka 449:
 
Označíme  \(\vec y = \matice U \vec x\) a díky \ref{UnitarniZachovavaNormu} platí \(\lVert \vec y \rVert = \lVert \vec x \rVert\). Dále označíme \( \lambda_i = \matice D_{ii} \) vlastní čísla matice \( \matice A^* \matice A \)
 
Označíme  \(\vec y = \matice U \vec x\) a díky \ref{UnitarniZachovavaNormu} platí \(\lVert \vec y \rVert = \lVert \vec x \rVert\). Dále označíme \( \lambda_i = \matice D_{ii} \) vlastní čísla matice \( \matice A^* \matice A \)
 
\[ \max\limits_{\vec x \neq \vec 0} \frac{\braket{\matice U \vec x | \matice {D U} \vec x}}{\lVert \vec x \rVert_2^2} = \max\limits_{\vec y \neq \vec 0} \frac{\braket{\vec y | \matice D \vec y}}{\lVert \vec y \rVert_2^2} = \max\limits_{\vec y \neq \vec 0} \frac{\sum_{i = 1}^n \lvert \lambda_i \rvert \lvert y_i \rvert^2}{\sum_{i = 1}^n \lvert y_i \rvert^2} = \max\limits_{\lVert \vec y \rVert_2 = 1} \sum_{i = 1}^n \lvert \lambda_i \rvert \lvert y_i \rvert^2 \]
 
\[ \max\limits_{\vec x \neq \vec 0} \frac{\braket{\matice U \vec x | \matice {D U} \vec x}}{\lVert \vec x \rVert_2^2} = \max\limits_{\vec y \neq \vec 0} \frac{\braket{\vec y | \matice D \vec y}}{\lVert \vec y \rVert_2^2} = \max\limits_{\vec y \neq \vec 0} \frac{\sum_{i = 1}^n \lvert \lambda_i \rvert \lvert y_i \rvert^2}{\sum_{i = 1}^n \lvert y_i \rvert^2} = \max\limits_{\lVert \vec y \rVert_2 = 1} \sum_{i = 1}^n \lvert \lambda_i \rvert \lvert y_i \rvert^2 \]
Toto maximum nastává pro takový vektor \( \vec y_k = 1 \), kde \( \lambda_k \) je největší vlastní číslo matice \( \matice A^* \matice A \). Tedy
+
Toto maximum nastává pro takový vektor \(\vec y\), že jehož složka  \( y_k = 1 \) pro takové \(k\), pro které je \( \lambda_k \) největší vlastní číslo matice \( \matice A^* \matice A \). Tedy
 
\[ \max\limits_{\lVert \vec y \rVert_2 = 1} \sum_{i = 1}^n \lvert \lambda_i \rvert \lvert y_i \rvert^2 = \lambda_k = \rho ( \matice {A^* A} ) = \lVert \matice A \rVert_2^2 \]
 
\[ \max\limits_{\lVert \vec y \rVert_2 = 1} \sum_{i = 1}^n \lvert \lambda_i \rvert \lvert y_i \rvert^2 = \lambda_k = \rho ( \matice {A^* A} ) = \lVert \matice A \rVert_2^2 \]
 
\begin{remark*}
 
\begin{remark*}
Je-li \(\matice A\) hermitovská, platí \(\matice {A^*A} = \matice A^2\) a \(\lVert \matice A \rVert _2 = \sqrt{\rho(\matice A^2)} = \rho(\matice A)\).  
+
Je-li \(\matice A\) hermitovská, platí \(\matice {A^*A} = \matice A^2\) a \(\lVert \matice A \rVert _2 = \sqrt{\rho(\matice A^2)} = \rho(\matice A)\). (Rovnost plyne z \ref{MocninaJordan})
 
\\ Je-li \(\matice A\) unitární, pak \(\lVert \matice A \rVert _2 = 1\) \qedhere
 
\\ Je-li \(\matice A\) unitární, pak \(\lVert \matice A \rVert _2 = 1\) \qedhere
 
\end{remark*}
 
\end{remark*}
Řádka 459: Řádka 458:
 
\end{proof}
 
\end{proof}
 
\end{theorem}
 
\end{theorem}
 
+
 
\subsection{Konvergence geometrické posloupnosti matic}
 
\subsection{Konvergence geometrické posloupnosti matic}
 
+
 
\begin{lemma*}
 
\begin{lemma*}
 +
\label{MocninaJordan}
 
Nechť \( \matice J \in \mathbbm C^{n, n} \) je Jordanovou maticí z rozkladu \ref{Jordan}. Potom platí
 
Nechť \( \matice J \in \mathbbm C^{n, n} \) je Jordanovou maticí z rozkladu \ref{Jordan}. Potom platí
 
\[ (\matice J^k)_{ij} =
 
\[ (\matice J^k)_{ij} =
Řádka 499: Řádka 499:
 
\end{proof}
 
\end{proof}
 
\end{lemma*}
 
\end{lemma*}
 
+
 
\setcounter{define}{62}
 
\setcounter{define}{62}
 
\begin{theorem}
 
\begin{theorem}
Řádka 509: Řádka 509:
 
\end{proof}
 
\end{proof}
 
\end{theorem}
 
\end{theorem}
 
+
 
\begin{theorem}
 
\begin{theorem}
 
\label{GeomKNorma}
 
\label{GeomKNorma}
Řádka 519: Řádka 519:
 
\end{proof}
 
\end{proof}
 
\end{theorem}
 
\end{theorem}
 
+
 
\begin{theorem}
 
\begin{theorem}
 
\label{AbsEigenvalueVSNorma}
 
\label{AbsEigenvalueVSNorma}
Řádka 536: Řádka 536:
 
\end{proof}
 
\end{proof}
 
\end{theorem}
 
\end{theorem}
 
+
 
\begin{theorem}
 
\begin{theorem}
 
\label{NutPostK}
 
\label{NutPostK}
Řádka 555: Řádka 555:
 
\end{proof}
 
\end{proof}
 
\end{theorem}
 
\end{theorem}
 
+
 
\begin{theorem}
 
\begin{theorem}
 
\label{GeomRozvoj}
 
\label{GeomRozvoj}

Aktuální verze z 30. 1. 2017, 17:14

PDF [ 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.
ZIPKompletní zdrojový kód včetně obrázků.

Součásti dokumentu 01NUM1

součástakcepopisposlední editacesoubor
Hlavní dokument editovatHlavní stránka dokumentu 01NUM1Kubuondr 26. 11. 201616:56
Řídící stránka editovatDefiniční stránka dokumentu a vložených obrázkůDedicma2 23. 5. 201721:31
Header editovatHlavičkový souborDedicma2 17. 1. 201616:20 header.tex
Kapitola0 editovatZnačeníDedicma2 23. 5. 201721:32 preamble.tex
Kapitola2 editovatOpakování a doplnění znalostí z lineární algebryKubuondr 30. 1. 201717:14 prezentace2.tex
Kapitola3 editovatÚvod do numerické matematikyKubuondr 10. 12. 201614:17 prezentace3.tex
Kapitola4 editovatPřímé metody pro lineární soustavyKubuondr 30. 1. 201711:27 prezentace4.tex
Kapitola5 editovatIterativní metodyKubuondr 31. 1. 201710:41 prezentace5.tex
Kapitola6 editovatVlastní čísla a vektory maticKubuondr 31. 1. 201713:13 prezentace6.tex
Kapitola7 editovatNelineární rovniceKubuondr 31. 1. 201714:27 prezentace7.tex
Kapitola8 editovatInterpolaceKubuondr 31. 1. 201715:43 prezentace8.tex
Kapitola9 editovatDerivace a integraceKubuondr 31. 1. 201717:33 prezentace9.tex

Zdrojový kód

%\wikiskriptum{01NUM1}
\section{Opakování a doplnění znalostí z lineární algebry}
 
\subsection{Trojúhelníkové matice}
 
\setcounter{define}{21}
\begin{theorem}
\label{SoucinTrojuhelniku}
Nechť jsou \( \matice A \) a \( \matice B \in \mathbbm C^{n, n} \) dolní (resp. horní) trojúhelníkové matice. Pak matice \( \matice C = \matice {AB} \) je dolní (resp. horní) trojúhelníková. Dále pak platí:
\[ \forall i \in \hat n, \matice C_{ii} = \matice A_{ii} \matice B_{ii} \]
\begin{proof}
Protože jsou matice \( \matice A \) a \( \matice B \) dolní trojúhelníkové, platí \( \matice A_{ik} = 0,\; \forall i < k \) a \( \matice B_{kj} = 0, \; \forall k < j \). 
Tudíž:
\[ \matice C_{ij} = \sum_{k = 1}^n \matice A_{ik} \matice B_{kj} = \sum_{k = 1}^i \matice A_{ik} \matice B_{kj} = \sum_{k = j}^i \matice A_{ik} \matice B_{kj} \]
což je rovno 0 pro \( i < j \) a \( \matice A_{ii} \matice B_{ii} \) pro \( i = j \). Důkaz pro horní trojúhelníkové matice je obdobný.
\end{proof}
\end{theorem}
 
\begin{theorem}
\label{InverzeTrojuhelniku}
Nechť je \( \matice A \in \mathbbm C^{n, n} \) regulární dolní (resp. horní) trojúhelníková matice. Pak matice \( \matice A^{-1} \) je dolní (resp. horní) trojúhelníková. Dále pak platí:
\[ \forall i \in \hat n, \; (\matice A^{-1})_{ii} = (\matice A_{ii})^{-1} = \frac{1}{\matice A_{ii} } \]
\begin{proof}
Označíme \( \matice B = \matice A^{-1} \) a vyjdeme ze vztahu \( \matice A \matice B = \matice I \). Protože je matice \( \matice A \) dolní trojúhelníková a regulární, platí \( \matice A_{ik} = 0,\; \forall i < k \) a \( \matice A_{ii} \neq 0, \; \forall i \in \hat n \). Proto:
\[ \matice I_{ij} = \sum_{k = 1}^n \matice A_{ik} \matice B_{kj} = \sum_{k = 1}^i \matice A_{ik} \matice B_{kj} \]
\begin{enumerate}[(1)]
\item \( \matice B \) dolní trojúhelníková
\\ indukcí podle \( i \) při pevném j
\begin{itemize}
 \item \( i = 1 \), \( 1 < j \)
  \[ \matice I_{ij} = 0 = \sum_{k=1}^i \matice A_{ik} \matice B_{kj} = \sum_{k = 1}^1 \matice A_{1k} \matice B_{kj} = \underbrace{\matice A_{11}}_{\neq 0} \matice B_{1j} \Rightarrow \matice B_{1j} = 0, \; \forall j > 1 \]
\item \( i \rightarrow i + 1 \), \( i + 1 < j \)
 \\Indukční předpoklad: \( \matice B_{kj} = 0, \; \forall k \leq i \)
  \[ \matice I_{i + 1, j} = 0 = \sum_{k = 1}^{i + 1} \matice A_{i + 1, k} \matice B_{kj} = \sum_{k = i + 1}^{i + 1} \matice A_{i + 1, k} \matice B_{kj} = \underbrace{\matice A_{i + 1, i + 1}}_{\neq 0} \matice B_{i + 1, j} \Rightarrow \matice B_{i +1, j} = 0, \; \forall j > i + 1 \]
\end{itemize}
\item Prvky na diagonále \( \matice B \)
 \\ Jelikož je matice \( \matice B \) dolní trojúhelníková, plyne přímo z \ref{SoucinTrojuhelniku}:
 \[ \matice I_{ii} = 1 = \matice A_{ii} \matice B_{ii} \Rightarrow \matice B_{ii} = \frac{1}{\matice A_{ii}} \]
\end{enumerate}
Důkaz pro horní trojúhelníkové matice je obdobný.
\end{proof}
\end{theorem}
 
\subsection{Rozklad matice na horní a dolní trojúhelníkovou}
 
\begin{theorem}
\label{LDR}
Každou silně regulární matici \( \matice A \in \mathbbm C^{n, n} \) lze jednoznačně vyjádřit ve tvaru součinu:
\[ \matice A = \matice {LDR} \]
kde:
\begin{itemize}
 \item \( \matice L \) je dolní trojúhelníková matice s jedničkami na diagonále
 \item \( \matice D \) je diagonální matice
 \item \( \matice R \) je horní trojúhelníková matice s jedničkami na diagonále
\end{itemize}
\begin{proof}
\begin{enumerate}[(1)]
\item existence
 \\Důkaz indukcí podle \( n \)
\begin{itemize}
\item \( n=1 \)
\\ \( \matice A = ( \matice A_{11} ) = \matice I (\matice A_{11} ) \matice I, \text{tedy} \; \matice L = \matice I \) a \( \matice R = \matice I \)
\item \( n \rightarrow n + 1 \)
\\ Označíme 
\[ \matice A = 
\begin{pmatrix}
\matice A' & \vec v \\
\vec u^T & \alpha \\
\end{pmatrix}
\]
kde \( \matice A' \in \mathbbm C^{n, n} \) a díky indukčnímu předpokladu můžeme rozložit \( \matice A' = \matice {L' D' R'} \)
  \\ Obdobně označíme i matice \( \matice L \), \( \matice D \) a \( \matice R \) a chceme dokázat
  \[ \begin{pmatrix}
   \matice L' & \vec 0 \\
   \vec l^T & 1 \\
  \end{pmatrix}
  \begin{pmatrix}
   \matice D' & \vec 0 \\
   \vec 0^T & d \\
  \end{pmatrix}
  \begin{pmatrix}
   \matice R' & \vec r \\
   \vec 0^T & 1 \\
  \end{pmatrix} =
  \begin{pmatrix}
   \matice {L' D'} & \vec 0 \\
   \vec l^T \matice D' & d \\
  \end{pmatrix}
  \begin{pmatrix}
   \matice R' & \vec r \\
   \vec 0^T & 1 \\
  \end{pmatrix} =\]
  \[=
  \begin{pmatrix}
   \matice {L' D' R'} & \matice {L' D'} \vec r \\
   \vec l^T \matice {D' R'} & \vec l^T \matice D' \vec r + d \\
  \end{pmatrix} =
  \begin{pmatrix}
   \matice A' & \vec v \\
   \vec u^T & \alpha \\
  \end{pmatrix}
\]
Chceme tedy určit \( \vec l \), \( \vec r \) a \( d \). Protože je \( \matice A \) silně regulární, je \( \matice A' \) v každém kroku regulární a tedy i \( \matice L' \), \( \matice D' \) a \( \matice R' \) jsou regulární. Upravíme \( \matice {L' D'} \vec r = \vec v \) a tím určíme \( \vec r = \left( \matice {L' D'} \right)^{-1} \vec v \). Obdobně
\[ \vec l^T \matice {D' R'} = \vec u^T \Rightarrow \vec l = ((\matice {D' R'})^T)^{-1} \vec u \]
\[ d = \alpha - \vec l^T \matice D' \vec r \]
\end{itemize}
\item jednoznačnost
\\ Důkaz sporem, předpokládáme, že existují 2 různé rozklady \( \matice A =\matice L_1 \matice D_1 \matice R_1 = \matice L_2 \matice D_2 \matice R_2 \). Úpravou dostaneme
\[ \matice D_1 \matice R_1 = (\matice L_1)^{-1} \matice L_2 \matice D_2 \matice R_2 \]
\[ \matice D_1 \matice R_1 (\matice R_2)^{-1} = (\matice L_1)^{-1} \matice L_2 \matice D_2 \]
kde \( \matice D_1 \matice R_1 (\matice R_2)^{-1} \) je horní trojúhelníková matice a \( (\matice L_1)^{-1} \matice L_2 \matice D_2 \) je dolní trojúhelníková matice podle \ref{SoucinTrojuhelniku} a \ref{InverzeTrojuhelniku}. Z toho plyne, že \( (\matice L_1)^{-1} \matice L_2 \) je diagonální s jedničkami na diagonále, tedy upravujeme
\[ (\matice L_1)^{-1} \matice L_2 = \matice I \]
\[ (\matice L_1)^{-1} \matice L_2 = \matice I \Rightarrow \matice L_1 = \matice L_2 \]
A obdobně
\[ \matice R_1 (\matice R_2)^{-1} = \matice I \Rightarrow \matice R_1 = \matice R_2 \]
\[ \matice D_1 = \matice D_2 \]
\end{enumerate}
\end{proof}
\end{theorem}
 
\begin{remark*}
Čísla na diagonále matice \( \matice D \) z \ref{LDR} \textbf{nejsou} vlastními čísly matice \( \matice A \) (jsou to pivoty GEM, viz \ref{GEMRegularni}).
\end{remark*}
 
 
\subsection{Rozklady matic}
 
\setcounter{define}{33}
\begin{theorem}
\label{HouseholderHermUnit}
Householderova reflekční matice je hermitovská a unitární.
\begin{proof}
\begin{enumerate}[(1)]
 \item Hermitovskost (\( \matice H^*( \vec w ) = \matice H( \vec w ) \))
  \[ \matice H^*( \vec w ) = ( \matice I - 2 \vec w \vec w^* )^* = \matice I^* - 2 ( \vec w \vec w^* )^* = \matice I - 2 \vec w \vec w^* = \matice H ( \vec w ) \]
 \item Unitarita (\( \matice H^*( \vec w ) = \matice H^{-1}( \vec w ) \))
  \\ Díky hermitovskosti matice a vztahu \( \vec w^* \vec w = \braket{\vec w | \vec w } = {\lVert \vec w \rVert}^2 = 1 \) platí:
  \[ \matice H( \vec w ) \matice H^*( \vec w ) = \matice H( \vec w ) \matice H( \vec w ) = \matice I - 4 \vec w \vec w^* + 4 \vec w \vec w^* \vec w \vec w^* = \matice I \]
\end{enumerate}
\end{proof}
\end{theorem}
 
\begin{theorem}[Unitární matice zachovává normu]
\label{UnitarniZachovavaNormu}
Nechť \( \matice U \) je unitární matice. Pak platí:
\[ \lVert \matice U \vec x \rVert_2 = \lVert \vec x \rVert_2 \]
Pro libovolný vektor \( \vec x \).
\begin{proof}
\[ \lVert \matice U \vec x \rVert_2^2 = \braket{\matice U \vec x | \matice U \vec x} = ( \matice U \vec x )^* \matice U \vec x = \vec x^* \matice U^* \matice U \vec x = \vec x^* \matice U^{-1} \matice U \vec x = \vec x^* \vec x = \braket{\vec x | \vec x} = \lVert \vec x \rVert_2^2 \]
\end{proof}
\end{theorem}
 
\begin{theorem}
\label{HouseholderReflekcni}
\( \matice H( \vec w )\) je Householderova reflekční matice a \( \vec v \) je libovolný vektor z \( \mathbbm C^n \). 
\\ Pak vektor \( \matice H( \vec w ) \vec v \) je zrcadlový obraz vektoru \( \vec v \) podle nadroviny \[ L = \{ \vec x \in \mathbbm C^n \; | \; \vec w^* \vec x = \braket{ \vec x | \vec w } = 0 \} \] v tom smyslu, že splňuje
\begin{itemize}
\item \(\lVert \matice H( \vec w )\vec v \rVert = \lVert \vec v \rVert\)
\item \(\matice H( \vec w )\vec v + \vec v \in L\)
\item \((\matice H( \vec w )\vec v - \vec v) \perp L\)
\end{itemize}
\begin {proof}
\begin{enumerate}[(1)]
 \item \(\lVert \matice H( \vec w )\vec v \rVert = \lVert \vec v \rVert\) plyne z faktu, ze \(\matice H( \vec w )\) je unitární a z \ref{UnitarniZachovavaNormu}.
 \item \(\matice H( \vec w )\vec v + \vec v \in L \Leftrightarrow \braket{\matice H( \vec w )\vec v + \vec v | \vec w} = 0 \) \[ \braket{\matice H( \vec w )\vec v + \vec v | \vec w} = 0 \Leftrightarrow \braket{(\matice I - 2\vec w \vec w^*)\vec v + \vec v| \vec w} = \braket{(2\vec v - 2\vec w \vec w^* \vec v | \vec w )} = \] \[ = 2\braket{\vec v|\vec w} - 2\braket{\vec w \vec w^* \vec v|\vec w} = 2\braket{\vec v|\vec w} - 2\underbrace{\vec w^* \vec w}_{\lVert \vec w \rVert = 1} \vec w^* \vec v = 2\braket{\vec v| \vec w} - 2\underbrace{\vec w^* \vec v}_{2\braket{\vec v| \vec w}} = 0 \]
 \item \( (\matice H( \vec w )\vec v - \vec v) \perp L \Leftrightarrow \forall \vec x \in L, \braket{\matice H( \vec w )\vec v - \vec v | \vec x} = 0 \)
 \[ \braket{\matice H( \vec w )\vec v - \vec v | \vec x} = \braket{ ( \matice I - 2 \vec w \vec w^* )\vec v - \vec v | \vec x} = -2 \braket{ \vec w \vec w^* \vec v | \vec x} = -2 \underbrace{\vec x^* \vec w}_{ = 0} \vec w^* \vec v = 0 \]
\end{enumerate}
\end{proof}
\end{theorem}
 
\begin{theorem}
\label{HouseholderEigenvalue}
Nechť \(\lambda\) je vlastní číslo matice \(\matice A\), pak existuje Householderova matice \(\matice H(\vec w)\) taková, že 
\[\matice H(\vec w)\matice A\matice H(\vec w)\vec e^{(1)}=\lambda\vec e^{(1)}\] kde \( \vec e^{(1)} \) je prvním bazickým vektorem.
\begin{proof}
Nechť \( \lambda \in \sigma ( \matice A ) \) a \(\vec x\) příslušný vlastní vektor. Volíme \(\vec w\) tak, aby zobrazil vektor \(\vec x\) do směru vektoru \(\vec e^{(1)}\). Podle \ref{HouseholderReflekcni} musí platit: 
\[\matice H (\vec w)\vec e^{(1)} = \vec x \Rightarrow (\vec x + \vec e^{(1)} ) \in L\]
\[\vec w=(\vec x - \vec e^{(1)} ) \perp L\]
Zvolíme tedy \( \vec w \) takto:
 \[ \vec w = \frac{\vec e^{(1)}-\frac{\vec x}{\lVert \vec x \rVert_2}}{\lVert \vec e^{(1)}-\frac{\vec x}{\lVert \vec x \rVert_2}\rVert_2} \]
a pokud vezmeme \(\vec x\) jako normovaný:
\[ \vec w = \frac{\vec e^{(1)}-\vec x}{\lVert \vec e^{(1)} - \vec x \rVert_2} \]
Protože je Householedora matice unitární, musíme vektor \(\vec x\) normovat, jinak by totiž \(\matice H(\vec w)\vec x\) nemohl být jednotkový vektor.
Z volby \( \vec w \) pak plyne:
\[\matice A \matice H (\vec w)\vec e^{(1)} = \matice A \vec x = \lambda \vec x\]
\[\matice H (\vec w)\matice A \matice H (\vec w)\vec e^{(1)} = \lambda \matice H(\vec w)\vec x  = \lambda \vec e^{(1)},\]
což dokazuje větu.
\end{proof}
\end{theorem}
 
\begin{remark*}
Je jedno, jestli bude vektor \(\vec w\) mířit na jednu, nebo na druhou stranu. zásadní je pouze kolmost na L.
\end{remark*}
 
\begin{remark*}
\(\matice M \vec e^{(1)} = \lambda \vec e^{(1)} \Rightarrow \matice M = \begin{pmatrix} 
\lambda & \multirow{4}{*}{\text{\Huge ?}} \\
0 & \\
\vdots & \\
0 & \\
\end{pmatrix}\)
\end{remark*}
 
\begin{remark*}
\(\matice M = \matice H (\vec w)\matice A \matice H (\vec w)\) je podobnostní transformace.
\end{remark*}
 
\begin{theorem}[Schurova věta] 
\label{Schur}
Libovolná matice \(\matice A \in \matice C^{n,n} \) se dá zapsat jako \[\matice A = \matice U^* \matice R \matice U \]
kde \(\matice U \) je unitární matice a \(\matice R\) je horní trojúhelníková matice.
\begin{remark}
Vlastní čísla matice \(\matice A \) jsou na diagonále \(\matice R\) díky \ref{PodobneEigenvalue}.
\end{remark}
\begin{proof}
Podle \ref{HouseholderEigenvalue} existuje \(\vec w_1 \in \matice C^{n}\) který při splňuje 
\[ \matice H (\vec w_1)\matice A \matice H (\vec w_1) =
\begin{pmatrix} 
\lambda_1 & \cdots \\
0 & \multirow{3}{*}{ \huge {\( \matice A' \)} } \\
\vdots & \\
0 & \\
\end{pmatrix}
= \matice H_1 \matice A \matice H_1 \]
Máme tedy další matici \(\matice A' \in \matice C^{n-1,n-1}\), ke které opět můžeme podle \(\ref{HouseholderEigenvalue}\) najít vektor \(\vec w'_2 \in \matice C^{n-1}\). Definujeme matici
\[ \matice H_2 = \begin{pmatrix} 
1 & \cdots \\
0 & \multirow{3}{*}{ \huge{\( \matice H'(\vec w'_2) \)} } \\
\vdots & \\
0 & \\
\end{pmatrix}
\]
která splňuje rovnici
\[\matice H'(\vec w'_2)\matice A'\matice H'(\vec w'_2) = \matice H_2\matice H_1\matice A\matice H_1\matice H_2=
\begin{pmatrix} 
1 & \cdots \\
0 & \multirow{3}{*}{ \huge{\( \matice H'(\vec w'_2) \)} } \\
\vdots & \\
0 & \\
\end{pmatrix}
\begin{pmatrix} 
\lambda_1 & \cdots \\
0 & \multirow{3}{*}{ \huge {\( \matice A' \)} } \\
\vdots & \\
0 & \\
\end{pmatrix}
\begin{pmatrix} 
1 & \cdots \\
0 & \multirow{3}{*}{ \huge{\( \matice H'(\vec w'_2) \)} } \\
\vdots & \\
0 & \\
\end{pmatrix}\]\[=
\begin{pmatrix} 
\lambda_1 & r_1 & \cdots \\
0 & \lambda_2 & \cdots \\
\vdots & 0 & \multirow{3}{*}{ \huge {\( \matice A'' \)} }\\
\vdots & \vdots && \\
0 & 0 & \\
\end{pmatrix}\]
Naprosto stejným postupem pokračujeme dále, až dojdeme k matici obsahující na diagonále vlastní čísla matice \(\matice A\) a případné další nenulové prvky nad diagonálou (ty tam kvůli jedničkám v maticích \(\matice H_2\) a dalších zůstanou). Tu označíme jako matici \(\matice R\). Dále označíme
\[ \matice U = \prod_{i = 0}^{n - 1} \matice H_{n - i} \]
Protože jsou všechny matice \(\matice H(\vec w_k)\) Householderovy reflekční matice, jsou podle \ref{HouseholderHermUnit} unitární. Součin unitárních matic je unitární matice (důkaz na dva řádky je trivální), tedy celá matice \(\matice U\) je unitární. Matice \(\matice U^{-1}\) bude mít tvar \(\matice H_1 \matice H_2 ... \matice H_n \). To už je ekvivalentní s tvrzením věty: \[\matice U^* \matice A \matice U = \matice R \Leftrightarrow \matice A = \matice U^* \matice R \matice U\]
\end{proof}
\end{theorem}
 
\begin{theorem}
\label{NormalniTrojuhelnikDiagonalni}
Normální trojúhelníková matice je diagonální.
\begin{proof}
Nechť je matice \( \matice A \in \mathbbm C^{n, n} \) normální dolní trojúhelníková. Pak platí \( \matice A^* \matice A = \matice A \matice A^* \) a \( \matice A_{ik} = 0,\; \forall i < k \) a dále:
\[ (\matice A ^* \matice A)_{ii} = \sum_{k = 1}^n (\matice A^*)_{ik} \matice A_{ki} = \sum_{k = i}^n (\matice A^*)_{ik} \matice A_{ki} = \sum_{k = i}^n \overline{\matice A_{ki}} \matice A_{ki} = \sum_{k = i}^n \lvert \matice A_{ki} \rvert^2 \]
\[ (\matice A \matice A^*)_{ii} = \sum_{k = 1}^n \matice A_{ik} (\matice A^*)_{ki} = \sum_{k = 1}^i \matice A_{ik} (\matice A^*)_{ki} = \sum_{k = 1}^i \matice A_{ik} \overline{ \matice A_{ik}} = \sum_{k = 1}^i \lvert \matice A_{ik} \rvert^2 \]
\[ (\matice A^* \matice A)_{ii} = (\matice A^* \matice A)_{ii} \Leftrightarrow \sum_{k = i}^n \lvert \matice A_{ki} \rvert^2 = \sum_{k = 1}^i \lvert \matice A_{ik} \rvert^2, \; \forall i \in \hat n \]
Důkaz provedeme indukcí podle \( i \)
\begin{itemize}
\item \( i = 1 \)
\[ \lvert \matice A_{11} \rvert^2 = \sum_{k = 1}^i \lvert \matice A_{ki} \rvert^2 = \sum_{k = i}^n \lvert \matice A_{1k} \rvert^2 = \lvert \matice A_{11} \rvert^2 + \sum_{k = 2}^n \lvert \matice A_{1k} \rvert^2 \Rightarrow \sum_{k = 2}^n \lvert \matice A_{1k} \rvert^2 = 0 \]
Jelikož jsou všechny členy pravé sumy nezáporné, musí být rovny 0, tedy \( \matice A_{1k} = 0, \; \forall k > 1 \)
\item \( i \rightarrow i + 1 \)
 \\ Indukční předpoklad: \( \matice A_{k, i + 1} = 0, \; \forall k < i + 1 \)
 \[ \lvert \matice A_{i + 1, i + 1} \rvert^2 = \sum_{k = i + 1}^{i + 1} \lvert \matice A_{k, i + 1} \rvert^2 = \sum_{k = 1}^{i + 1} \lvert \matice A_{k, i + 1} \rvert^2 = \sum_{k = i + 1}^n \lvert \matice A_{i + 1, k} \rvert^2 = \lvert \matice A_{i + 1, i + 1} \rvert^2 + \sum_{k = i + 2}^n \lvert \matice A_{i + 1, k} \rvert^2 \]
 Z čehož plyne díky nezápornosti členů pravé sumy \( \matice A_{i + 1, k} = 0, \; \forall k > i + 1 \)
\end{itemize}
Důkaz pro horní trojúhelníkové matice je obdobný.
\end{proof}
\end{theorem}
 
\begin{theorem}
\label{RozklNormMatice}
Pro libovolnou normální matici \(\matice A\) existuje unitární matice \(\matice U\) tak, že 
\[\matice A = \matice {U^*RU}\]
kde \(\matice R\) je diagonální. Je-li \(\matice A\) hermitovská, pak \(\matice R\) má na diagonále reálná čísla.
\begin{proof}
\begin{enumerate}
\item Ukážeme, že \(\matice R\) je normální, pak podle \ref{NormalniTrojuhelnikDiagonalni} bude také diagonální.
\[\matice A = \matice {U^*RU} \Rightarrow \matice {UA} = \matice {RU} \Rightarrow \matice {UAU^*} = \matice R\]
\[\matice R^* = \matice {(UAU^*)^*} = \matice {(AU^*)^*U^*} = \matice {UA^*U^*} \]
\[\matice {RR^*} = \matice {UA}\underbrace{\matice{U^*U}}_{\matice I}\matice {A^*U^*} = \matice {UAA^*U^*} = \matice {UA^*AU^*} = \matice {UA^*U^*UAU^*} = \matice{R^*R}\]
\(\Rightarrow \matice R \) je normální \(\Rightarrow \matice R\) je diagonální.
\item \(\matice A\) je hermitovská \(\Rightarrow \matice A\) je normální. 
\[\matice A = \matice {U^*DU} \Rightarrow \matice D = \matice {UAU^*}\]
kde \(\matice D\) je diagonální matice.
\[\matice D^* = \matice {(UAU^*)^*} = \matice {UA^*U^*} \underbrace{\Rightarrow}_{\matice A = \matice A^*} \matice {UAU^*} = \matice {D} \]
\[\matice D^* = \matice D \Rightarrow \matice D \in \matice R^{n,n}\] protože transpozicí se diagonálních prvků nedotkneme a rovnost hermitovsky sdružených prvků nastává pokud jsou prvky reálná čísla. \qedhere
\end{enumerate}
\end{proof}
\end{theorem}
 
\subsection{Rozklady matic - Jordanova Věta}
 
\begin{theorem}[Jordan]
\label{Jordan}
Nechť \( \matice A \in \mathbbm C^{n, n} \) a \( \lambda_1, \lambda_2, ... , \lambda_p \) jsou všechna její navzájem různá vlastní čísla. Pak je matice \( \matice A \) podobná blokově diagonální (Jordanově) matici \( \matice J \) tvaru:
\[ \matice J =
\begin{pmatrix}
\matice J_1 && \multicolumn{3}{c}{\multirow{3}{*}{\Huge { \( \Theta \) }}} & \\
& \matice J_2 && \\
\multicolumn{2}{c}{\multirow{2}{*}{\Huge { \( \Theta \) }}} & \ddots & \\
&&& \matice J_p \\
\end{pmatrix} \]
kde:
\[ \matice J_k =
\begin{pmatrix}
\lambda_k && \multicolumn{3}{c}{\multirow{3}{*}{\Huge { \( 0 \) }}} & \\
1 & \lambda_k && \\
\multirow{2}{*}{\Huge { \( 0 \) }} & \ddots & \ddots & \\
&& 1 & \lambda_k \\
\end{pmatrix}, \;
\forall k \in \hat p \]
Počet bloků příslušejících k \(\lambda\) je roven \(\nu_g(\lambda)\) a součet řádů těchto bloků je \(\nu_a(\lambda)\).
Matice \( \matice J \) je až na pořadí bloků dána jednoznačně.
\begin{proof}\renewcommand{\qedsymbol}{}
Bez důkazu.
\end{proof}
\end{theorem}
 
\begin{theorem*}[Věta navíc]
\label{DefiniceMocninyMatice}
\todo{Předělat neceločíselně, nebo vymazat, tuhle větu si Mlha vycucal z prstu, protože při psaní skript zápasil s tím, že jsme tu mocninu vůbec nedefinovali. Na zkoušce mi Oberhuber řekl, že by to definoval Schurovsky, ale on každý přístup má něco.}
Nechť \( \matice A \in \mathbbm C^{n, n} \). Definujeme pro \( p \in \mathbbm N \) mocninu matice \( \matice A^p \) takto:
\[ \matice A^p = \prod_{k = 1}^p \matice A \]
Potom platí:
\begin{enumerate}[(1)]
\item Pokud rozložíme matici \( \matice A \) podle \ref{Jordan} tak, že \( \matice A = \matice T^{-1} \matice{J T} \), pak platí
\[ \matice A^p = \matice T^{-1} \matice J^p \matice T \]
\item Pokud rozložíme matici \( \matice A \) podle \ref{Schur} tak, že \( \matice A = \matice U^* \matice{R U} \), pak platí
\[ \matice A^p = \matice U^* \matice R^p \matice U\]
\end{enumerate}
\begin{proof}
\begin{enumerate}[(1)]
\item Využijeme rozkladu:
\[ \matice A^p = \matice A \matice A \dots \matice A = \matice T^{-1} \matice{J T} \matice T^{-1} \matice{J T} \dots \matice T^{-1} \matice{J T} = \matice T^{-1} ( \matice J \matice J \dots \matice J ) \matice T = \matice T^{-1} \matice J^p \matice T \]
\item Využijeme rozkladu a faktu, že matice \( \matice U \) je unitární, tj. \( \matice U^* = \matice U^{-1} \):
\[ \matice A^p = \matice A \matice A \dots \matice A = \matice U^* \matice{R U} \matice U^* \matice{R U} \dots \matice U^* \matice{R U} =  \matice U^{-1} \matice{R U} \matice U^{-1} \matice{R U} \dots \matice U^{-1} \matice{R U} = \matice U^{-1} ( \matice R \matice R \dots \matice R ) \matice U = \matice U^{-1} \matice R^p \matice U \]
\end{enumerate}
\end{proof}
\end{theorem*}
 
\begin{remark*}
V prezentaci je mocnina matice definována pomocí Schurovy věty, kde je navíc přidán požadavek, aby matice \( \matice A \) byla hermitovská a pozitivně definitní, díky čemuž je matice \( \matice R \) diagonální s kladnými členy a tím pádem se Schurova věta stává speciálním případem věty Jordanovy. Tato definice umožní jednoduše definovat i neceločíselné mocniny. Předešlá věta v prezentaci chybí, přestože je občas používána.
\end{remark*}
 
\subsection{Vlastní čísla matice}
 
\setcounter{define}{43}
\begin{theorem}
\label{PodobneEigenvalue}
Podobné matice \( \matice A \) a \( \matice B \) mají stejná vlastní čísla se stejnou geometrickou násobností.
\begin{proof}
Díky podobnosti existuje taková matice \( \matice T \), že \( \matice A = \matice T^{-1} \matice{B T} \). Dále rozložíme \( \matice B \) podle \ref{Jordan} a označíme \( \matice B = \matice K^{-1} \matice{JK} \), kde \( \matice J \) je Jordanova matice. Pak platí:
\[ \matice A = \matice T^{-1} \matice{B T} = \matice T^{-1} \matice K^{-1} \matice{J K T} = ( \matice{K T} )^{-1} \matice J ( \matice{K T} ) \]
což je podobnostní transformace a z čehož díky podmínce jednoznačnosti v \ref{Jordan} plyne, že matice \( \matice J \) je Jordanovou maticí k matici \( \matice A \). Z definice Jordanovy matice pak plyne tvrzení věty.
\end{proof}
\end{theorem}
 
\subsection{Pozitivně definitní matice}
 
\begin{define}
Matice \(\matice A \in \mathbbm T^{n, n}\) je pozitivně definitní \(\Leftrightarrow\) \[ \forall \vec x \neq \vec 0, \; \vec x^*\matice A \vec x \in \matice R^+\]
značíme \(\matice A > 0\).
Platí-li pro \(\matice B \in \matice T^{n, n} \) vztah \( \matice A - \matice B > 0 \), pak píšeme \(\matice A > \matice B \).
\end{define}
 
\begin{theorem}
\label{PDEigenvalues}
Všechna vlastní čísla pozitivně definitní matice \(\matice A\) jsou kladná. Je-li \(\matice A\) hermitovská matice s kladnými vlastními čísly, pak \(\matice A\) je pozitivně definitní.
\begin{proof}
\begin{itemize}
\item Nechť \(\lambda\) vlastní číslo \(\matice A\) a \(\vec x\) příslušný vlastní vektor.
\[ 0 < \braket{\matice A \vec x| \vec x} = \braket{\lambda \vec x|\vec x} = \lambda \lVert \vec x \rVert ^2_2 \Rightarrow \lambda > 0\]
\item Podle \ref{RozklNormMatice} \(\matice A = \matice{U^* D U}\) kde \( \matice D \) je diagonální, a tedy kladná. Vezmu tedy libovolný vektor \(\vec x \neq \vec 0\) a vektor \(\vec y = \matice U \vec x \Rightarrow \vec y \neq \vec 0\)
\[\braket{\matice A \vec x|\vec x} = \braket{\matice{U^*DU}\vec x|\vec x} = \braket{\matice {DU}\vec x|\matice U\vec x} = \braket{\matice D \vec y|\vec y}=\vec y^*\matice D\vec y > 0 \]
\end{itemize}
\end{proof}
\end{theorem}
 
\subsection{Normy}
 
\setcounter{define}{52}
\begin{theorem}
\label{NormySendvic}
Pro libovolné dvě normy \( \lVert \, \cdot \, \rVert_1 \) a \( \lVert \, \cdot \, \rVert_2 \) na množině vektorů z \( \mathbbm C^n \) existují kladné konstanty \( \gamma_1 \) a \( \gamma_2 \) takové, že \( \forall \vec x \in \mathbbm C^n \) platí:
\[ \gamma_1 \lVert \vec x \rVert_1 \leq \lVert \vec x \rVert_2 \leq \gamma_2 \lVert \vec x \rVert_1 \]
\begin{proof}\renewcommand{\qedsymbol}{}
Bez důkazu, pro zájemce viz Turistický průvodce matematickou analýzou 3, Věta {\color{red} 6.7}
\end{proof}
\end{theorem}
 
\begin{theorem}
\label{KonvergenceVNorme}
Nechť \( \left\{ \vec x^{(k)} \right\}_{k = 1}^\infty \) je posloupnost vektorů z \( \mathbbm C^{n} \) a \( \lVert \, \cdot \, \rVert \) libovolná norma. Potom
\[ \vec x^{(k)} \rightarrow \vec x \Leftrightarrow \lVert \vec x^{(k)} - \vec x \rVert \rightarrow 0 \]
\begin{proof}
(\( \Rightarrow \)) Pokud \( \vec x^{(k)} \rightarrow \vec x \), pak \( \lVert \vec x^{(k)} - \vec x \rVert_\infty \rightarrow 0 \) a tento vztah pak díky \ref{NormySendvic} platí pro libovolnou normu.
\\ (\( \Leftarrow \))
Díky \ref{NormySendvic} platí \( \lVert \vec x^{(k)} - \vec x \rVert_\infty \rightarrow 0 \), tedy \( \max\limits_{i \in \hat n} \lvert \vec x_i^{(k)} - \vec x_i \rvert \rightarrow 0 \) a proto \( \forall i \in \hat n, \; \lvert \vec x_i^{(k)} - \vec x_i \rvert \rightarrow 0 \), což je jinak zapsáno \( \vec x^{(k)} \rightarrow \vec x \)
\end{proof}
\end{theorem}
 
\setcounter{define}{59}
\begin{theorem}
\label{NormaMatice}
Při značení:
\[ \lVert \matice A \rVert_\infty = \max\limits_{\lVert \vec x \rVert_\infty = 1} \lVert \matice A \vec x \rVert_\infty \]
\[ \lVert \matice A \rVert_1 = \max\limits_{\lVert \vec x \rVert _1 = 1} \lVert \matice A \vec x \rVert_1 \]
\[ \lVert \matice A \rVert_2 = \max\limits_{\lVert \vec x \rVert _2 = 1} \lVert \matice A \vec x \rVert_2 \]
 
pro každou matici \( \matice A \in \mathbbm C^{n, n} \) platí vztahy:
\[ \lVert \matice A \rVert_\infty = \max\limits_{i \in \hat n} \sum_{j = 1}^n \lvert \matice A_{ij} \rvert \]
\[ \lVert \matice A \rVert_1 = \max\limits_{j \in \hat n} \sum_{i = 1}^n \lvert \matice A_{ij} \rvert \]
\[ \lVert \matice A \rVert _2 = \sqrt{\rho ( \matice {A^* A} ) } \]
\begin{proof}
\begin{enumerate}[(1)]
\item \( \lVert \matice A \rVert_\infty = \max\limits_{\lVert \vec x \rVert_\infty = 1} \lVert \matice A \vec x \rVert_\infty = \max\limits_{i \in \hat n} \sum_{j = 1}^n \lvert \matice A_{ij} \rvert \)
\\ Pro každé pevné \( i \in \hat n \) volíme \( \vec x_j = \sgn \matice A_{ij} \) a potom \( ( \matice A \vec x )_i = \sum_{j = 1}^n \lvert \matice A_{ij} \rvert \). Platí \( \lVert \vec x \rVert_\infty = 1 \) a tvrzení plyne z definice \( \lVert \, \cdot \, \rVert_\infty \).
\begin{remark*}
Hledáme maxima přes řádky, maximové normě pro matice se tedy říká také řádková norma.
\end{remark*}
\item \( \lVert \matice A \rVert_1 = \max\limits_{\lVert \vec x \rVert _1 = 1} \lVert \matice A \vec x \rVert_1 = \max\limits_{j \in \hat n} \sum_{i = 1}^n \lvert \matice A_{ij} \rvert \)
\\ Volím \( k \) aby \( \matice A_{\cdot k} \) byl maximální (\( \forall l \neq k, \; \sum_{i = 1}^n \lvert \matice A_{il} \rvert \leq \sum_{i = 1}^n \lvert \matice A_{ik} \rvert \)). Poté volím \( \vec x \) tak, že \( \forall i \neq k, \; \vec x_i = 0 \) a \( \vec x_k = 1 \). Tento vektor splňuje \( \lVert \vec x \rVert _1 = 1 \) a zároveň tím maximalizuji \( \lVert \matice A \vec x \rVert_1 \). Z \( \max\limits_{j \in \hat n} \sum_{i = 1}^n \lvert \matice A_{ij} \rvert = \sum_{i = 1}^n \lvert \matice A_{ik} \rvert \) potom plyne tvrzení věty.
\begin{remark*}
Hledáme maxima přes sloupce, normě se tedy říká sloupcová. 
\end{remark*}
\item \( \lVert \matice A \rVert _2 = \max\limits_{\lVert \vec x \rVert_2 = 1} \lVert \matice A \vec x \rVert_2 = \sqrt{\rho ( \matice {A^* A} )} \)
\[ \lVert \matice A \rVert_2^2 = \max\limits_{\lVert \vec x \rVert_2 = 1} \lVert \matice A \vec x \rVert_2^2 = \max\limits_{\vec x \neq \vec 0} \frac{\lVert \matice A \vec x \rVert_2^2}{\lVert \vec x \rVert_2^2} = \max\limits_{\vec x \neq \vec 0} \frac{\braket{\matice A \vec x | \matice A \vec x}}{\lVert \vec x \rVert_2^2} = \max\limits_{\vec x \neq \vec 0} \frac{\braket{\vec x | \matice {A^* A} \vec x}}{\lVert \vec x \rVert_2^2} \]
Dále využijeme toho, že matice \( \matice {A^* A} \) je normální (ověření na řádek práce s hvězdičkováním), tedy lze ji napsat ve tvaru \( \matice {U^* D U} \)
\[\max\limits_{\vec x \neq \vec 0} \frac{\braket{\vec x | \matice {A^* A} \vec x}}{\lVert \vec x \rVert_2^2} = \max\limits_{\vec x \neq \vec 0} \frac{\braket{\vec x | \matice {U^* D U} \vec x}}{\lVert \vec x \rVert_2^2} = \max\limits_{\vec x \neq \vec 0} \frac{\braket{\matice U \vec x | \matice {D U} \vec x}}{\lVert \vec x \rVert_2^2} \]
Označíme  \(\vec y = \matice U \vec x\) a díky \ref{UnitarniZachovavaNormu} platí \(\lVert \vec y \rVert = \lVert \vec x \rVert\). Dále označíme \( \lambda_i = \matice D_{ii} \) vlastní čísla matice \( \matice A^* \matice A \)
\[ \max\limits_{\vec x \neq \vec 0} \frac{\braket{\matice U \vec x | \matice {D U} \vec x}}{\lVert \vec x \rVert_2^2} = \max\limits_{\vec y \neq \vec 0} \frac{\braket{\vec y | \matice D \vec y}}{\lVert \vec y \rVert_2^2} = \max\limits_{\vec y \neq \vec 0} \frac{\sum_{i = 1}^n \lvert \lambda_i \rvert \lvert y_i \rvert^2}{\sum_{i = 1}^n \lvert y_i \rvert^2} = \max\limits_{\lVert \vec y \rVert_2 = 1} \sum_{i = 1}^n \lvert \lambda_i \rvert \lvert y_i \rvert^2 \]
Toto maximum nastává pro takový vektor \(\vec y\), že jehož složka  \( y_k = 1 \) pro takové \(k\), pro které je \( \lambda_k \) největší vlastní číslo matice \( \matice A^* \matice A \). Tedy
\[ \max\limits_{\lVert \vec y \rVert_2 = 1} \sum_{i = 1}^n \lvert \lambda_i \rvert \lvert y_i \rvert^2 = \lambda_k = \rho ( \matice {A^* A} ) = \lVert \matice A \rVert_2^2 \]
\begin{remark*}
Je-li \(\matice A\) hermitovská, platí \(\matice {A^*A} = \matice A^2\) a \(\lVert \matice A \rVert _2 = \sqrt{\rho(\matice A^2)} = \rho(\matice A)\). (Rovnost plyne z \ref{MocninaJordan})
\\ Je-li \(\matice A\) unitární, pak \(\lVert \matice A \rVert _2 = 1\) \qedhere
\end{remark*}
\end{enumerate}
\end{proof}
\end{theorem}
 
\subsection{Konvergence geometrické posloupnosti matic}
 
\begin{lemma*}
\label{MocninaJordan}
Nechť \( \matice J \in \mathbbm C^{n, n} \) je Jordanovou maticí z rozkladu \ref{Jordan}. Potom platí
\[ (\matice J^k)_{ij} =
\begin{cases}
0, & i < j \\
\binom{k}{i - j} \lambda^{k - (i - j)}, & i \geq j \\
\end{cases}
\]
\begin{proof}
Indukcí podle \( k \)
\begin{itemize}
\item \( k = 1 \)
\\ Plyne přímo z \ref{Jordan}.
\item \( k \rightarrow k + 1 \)
\[ (\matice J^{k + 1})_{ij} = (\matice J \matice J^k)_{ij} = \sum_{l = 1}^n \matice J_{il} ( \matice J^k )_{lj} \]
Z definice Jordanovy matice platí, že
\[ \matice J_{il} = 
\begin{cases}
1, & l = i - 1 \\
\lambda, & l = i \\
0, & \text{jinak} \\
\end{cases}
\]
a tedy
\[ \sum_{l = 1}^n \matice J_{il} ( \matice J^k )_{lj} = (\matice J^k)_{i - 1, j} + \lambda (\matice J^k)_{i, j} \]
Použijeme indukční předpoklad
\[ (\matice J^k)_{i - 1, j} + \lambda (\matice J^k)_{i, j} =
\begin{cases}
0, & i < j \\
0 + \lambda \binom{k}{i -j} \lambda^{k - (i - j)} = \lambda^{k + 1}, & i = j \\
\binom{k}{i - j -1}\lambda^{k - (i - 1 - j)} + \lambda \binom{k}{i - j} \lambda^{k - (i - j)} = \binom{k + 1}{i - j} \lambda^{k + 1 - (i - j)}, & i > j \\ 
\end{cases}
\]
kde poslední rovnost plyne ze vztahu \( \binom{n}{k - 1} + \binom{n}{k} = \binom{n + 1}{k} \) \qedhere
\end{itemize}
\end{proof}
\end{lemma*}
 
\setcounter{define}{62}
\begin{theorem}
\label{GeomKSpektrum}
Nechť \( \matice A \in \mathbbm C^{n, n} \). Potom platí
\[ \lim_{k \rightarrow \infty} \matice A^k = \Theta \Leftrightarrow \rho ( \matice A ) < 1 \]
\begin{proof}
Podle \ref{Jordan} rozložíme \( \matice A = \matice T^{-1} \matice{J T} \) a díky \nameref{DefiniceMocninyMatice} platí \( \matice A^k = \matice T^{-1} \matice J^k \matice T \). Díky lemmatu je zřejmé, že \( \lim\limits_{k \rightarrow \infty} (\matice J^k)_{ij} = 0 \) právě tehdy, pokud pro všechna vlastní čísla \( \lambda \) platí \( \lvert \lambda \rvert < 1 \).
\end{proof}
\end{theorem}
 
\begin{theorem}
\label{GeomKNorma}
Nechť \( \matice A \in \mathbbm C^{n, n} \). Potom platí
\[ \exists \; \text{maticová norma} \; \lVert \, \cdot \, \rVert, \lVert \matice A \rVert < 1 \Rightarrow \lim_{k \rightarrow \infty} \matice A^k = \Theta \]
\begin{proof}
Z \( \lVert \matice A \rVert < 1 \) plyne:
\[ \lVert \matice A^k \rVert \leq \lVert \matice A \rVert^k < 1^k \Rightarrow \lim_{k \rightarrow \infty} \lVert \matice A^k \rVert = 0 \Rightarrow \lim_{k \rightarrow \infty} \matice A^k = \Theta \]
\end{proof}
\end{theorem}
 
\begin{theorem}
\label{AbsEigenvalueVSNorma}
Nechť \( \matice A \in \mathbbm C^{n, n} \). Potom platí
\[ \forall \; \text{maticové normy} \; \lVert \, \cdot \, \rVert, \rho ( \matice A ) \leq \lVert \matice A \rVert \]
\begin{proof}
Označíme \( \lambda^{\matice A} \in \sigma ( \matice A ) \) a \( \forall \varepsilon > 0 \) označíme
\[ \matice B = \frac{1}{\lVert \matice A \rVert + \varepsilon} \matice A \]
a potom
\[ \lVert \matice B \rVert = \frac{\lVert \matice A \rVert}{\lVert \matice A \rVert + \varepsilon} < 1 \Rightarrow \matice B^k \rightarrow \Theta \]
díky \ref{GeomKNorma}. Pro nějaký \( \vec x \) vlastní vektor matice \( \matice A\) platí
\[ \matice B \vec x =  \frac{1}{\lVert \matice A \rVert + \varepsilon} \matice A \vec x =  \frac{\lambda^{\matice A}}{\lVert \matice A \rVert + \varepsilon} \vec x = \lambda^{\matice B} \vec x \]
Kde platí \( \lambda^{\matice B} \in \sigma ( \matice B ) \) a \( \lambda^{\matice B} < 1 \) díky \ref{GeomKSpektrum}. Pak platí
\[ \lvert \lambda^{\matice A} \rvert = ( \lVert \matice A \rVert + \varepsilon ) \lambda^{\matice B} < \lVert \matice A \rVert + \varepsilon, \; \forall \varepsilon > 0 \]
a tedy \( \lvert \lambda^{\matice A} \rvert \leq \lVert \matice A \rVert \)
\end{proof}
\end{theorem}
 
\begin{theorem}
\label{NutPostK}
Nechť \( \matice A \in \mathbbm C^{n, n} \). Potom platí
\[ \sum_{i = 0}^\infty \matice A^i < \infty \Leftrightarrow \lim_{k \rightarrow \infty} \matice A^k = \Theta \]
a
\[ \sum_{i = 0}^\infty \matice A^i < \infty \Rightarrow \sum_{i = 0}^\infty \matice A^i = ( \matice I - \matice A )^{-1} \]
\begin{proof}
\begin{enumerate}
\item[( \( \Rightarrow \) )] Důsledek nutné podmínky konvergence řady.
\item[( \( \Leftarrow \) )]
Označíme \( \matice S_k = \sum_{i = 0}^k \matice A^i \) a platí
\[ ( \matice I - \matice A ) \matice S_k = \matice I - \matice A^{k + 1} \]
Díky \ref{GeomKSpektrum} \( \rho ( \matice A ) < 1 \), a tedy \( 0 \notin \sigma ( \matice I - \matice A ) \), tedy \( ( \matice I - \matice A ) \) je regulární, díky čemuž můžeme upravit
\[ \matice S_k = ( \matice I - \matice A )^{-1} ( \matice I - \matice A^{k + 1} ) \]
\[ \lim_{k \rightarrow \infty} \matice S_k = ( \matice I - \matice A )^{-1} \]
\end{enumerate}
\end{proof}
\end{theorem}
 
\begin{theorem}
\label{GeomRozvoj}
Nechť \( \matice A \in \mathbbm C^{n, n} \) a \( \lVert \matice A \rVert < 1 \). Potom platí
\[ \left\lVert ( \matice I - \matice A )^{-1} - \sum_{i = 0}^k \matice A^i \right\rVert \leq \frac{\lVert \matice A \rVert^{k + 1}}{1 - \lVert \matice A \rVert}, \; \forall k \in \mathbbm N \]
\begin{proof}
Díky \ref{GeomKNorma} a \ref{NutPostK} víme \( ( \matice I - \matice A )^{-1} = \sum_{i = 0}^\infty \matice A^i \) a tedy při využití trojúhelníkové nerovnosti \( ( \lVert \matice{A B} \rVert \leq \lVert \matice A \rVert \lVert \matice B \rVert ) \) platí
\[ \left\lVert ( \matice I - \matice A )^{-1} - \sum_{i = 0}^k \matice A^i \right\rVert = \left\lVert \sum_{i = 0}^\infty \matice A^i - \sum_{i = 0}^k \matice A^i \right\rVert = \left\lVert \sum_{i = k + 1}^\infty \matice A^i \right\rVert = \left\lVert \matice A^{k + 1} \sum_{i = 0}^\infty \matice A^i \right\rVert \leq \lVert \matice A^{k + 1} \rVert \sum_{i = 0}^\infty \lVert \matice A \rVert^i = \frac{\lVert \matice A \rVert^{k + 1}}{1 - \lVert \matice A \rVert} \]
kde poslední rovnost plyne ze vzorce pro součet geometrické řady.
\end{proof}
\end{theorem}