01NUM1:Kapitola2: Porovnání verzí

Z WikiSkripta FJFI ČVUT v Praze
Přejít na: navigace, hledání
(Všechny věty)
(label pro lemma v konvergence geometrické posloupnosti.)
(Není zobrazeno 71 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}
 
   
 
   
 
\begin{theorem}
 
\begin{theorem}
 
\label{LDR}
 
\label{LDR}
Každou regulární matici \( \matice A \in \mathbbm C^{n, n} \) lze jednoznačně vyjádřit ve tvaru součinu:
+
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} \]
 
\[ \matice A = \matice {LDR} \]
 
kde:
 
kde:
Řádka 59: Řádka 59:
 
  \\Důkaz indukcí podle \( n \)
 
  \\Důkaz indukcí podle \( n \)
 
\begin{itemize}
 
\begin{itemize}
\item \( n=1 \)
+
\item \( n=1 \)
  \\ \( \matice A \in \mathbbm C^{1, 1} \Rightarrow \matice A = ( \matice A_{11} ) = \matice I (\matice A_{11} ) \matice I \)
+
\\ \( \matice A = ( \matice A_{11} ) = \matice I (\matice A_{11} ) \matice I, \text{tedy} \; \matice L = \matice I \) a \( \matice R = \matice I \)
  kde \( \matice L = \matice I \) a \( \matice R = \matice I \)
+
\item \( n \rightarrow n + 1 \)
\item \( n \rightarrow n + 1 \)
+
\\ Označíme
  \\ \( \matice A \in \mathbbm C^{n+1, n+1} \matice A =  
+
\[ \matice A =  
  \begin{pmatrix}
+
\begin{pmatrix}
  \matice A' & \vec v \\
+
\matice A' & \vec v \\
  \vec u^T & \alpha \\
+
\vec u^T & \alpha \\
  \end{pmatrix}
+
\end{pmatrix}
  \Rightarrow \matice A' \in \mathbbm C^{n, n} \Rightarrow \matice A' = \matice {L' D' R'}
+
\]
   \\ \matice A = \matice {LDR} \) a hledám \( \vec l \), \( \vec r \) a \( d_{n+1} \) tak, aby platil rozklad:
+
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}
 
   \[ \begin{pmatrix}
 
   \matice L' & \vec 0 \\
 
   \matice L' & \vec 0 \\
Řádka 76: Řádka 77:
 
   \begin{pmatrix}
 
   \begin{pmatrix}
 
   \matice D' & \vec 0 \\
 
   \matice D' & \vec 0 \\
   \vec 0^T & d_{n+1} \\
+
   \vec 0^T & d \\
 
   \end{pmatrix}
 
   \end{pmatrix}
 
   \begin{pmatrix}
 
   \begin{pmatrix}
Řádka 84: Řádka 85:
 
   \begin{pmatrix}
 
   \begin{pmatrix}
 
   \matice {L' D'} & \vec 0 \\
 
   \matice {L' D'} & \vec 0 \\
   \vec l^T \matice D' & d_{n+1} \\
+
   \vec l^T \matice D' & d \\
 
   \end{pmatrix}
 
   \end{pmatrix}
 
   \begin{pmatrix}
 
   \begin{pmatrix}
Řádka 93: Řá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_{n+1} \\
+
   \vec l^T \matice {D' R'} & \vec l^T \matice D' \vec r + d \\
 
   \end{pmatrix} =
 
   \end{pmatrix} =
 
   \begin{pmatrix}
 
   \begin{pmatrix}
 
   \matice A' & \vec v \\
 
   \matice A' & \vec v \\
 
   \vec u^T & \alpha \\
 
   \vec u^T & \alpha \\
   \end{pmatrix}\]\(
+
   \end{pmatrix}
  \\ \matice {L' D'} \vec r = \vec v \Rightarrow \vec r = (\matice {L' D'})^{-1} \vec v
+
\]
  \\ \vec l^T \matice {D' R'} = \vec u^T \Rightarrow \vec u = (\matice {D' R'})^T = \vec l \Rightarrow \vec l = ((\matice {D' R'})^T)^{-1} \vec u
+
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ě
  \\ d_{n+1} = \alpha - \vec r \vec l^T \matice D'
+
\[ \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}
 
\end{itemize}
 
\item jednoznačnost
 
\item jednoznačnost
\\ Důkaz sporem, předpokládáme, že existují 2 různé rozklady
+
\\ 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 A =\matice L_1 \matice D_1 \matice R_1 = \matice L_2 \matice D_2 \matice R_2
+
\[ \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 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 \]
\\ \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
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}.
+
\[ (\matice L_1)^{-1} \matice L_2 = \matice I \]
\\ \( \Rightarrow (\matice L_1)^{-1} \matice L_2 \) je diagonální a má jedničky na diagonále, tzn. \( (\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 \]
\\ (\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 R_1 (\matice R_2)^{-1} = \matice I \Rightarrow \matice R_1 = \matice R_2 \]
\\ \matice D_1 = \matice D_2 \)
+
\[ \matice D_1 = \matice D_2 \]
 
\end{enumerate}
 
\end{enumerate}
 
\end{proof}
 
\end{proof}
Řádka 119: Řá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 132: Řá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 139: Řá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 154: Řádka 165:
 
  \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 \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 \)
 
  \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 = \]
+
  \[ \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{enumerate}
 
\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 \).
+
\begin{proof}
+
\[ \lVert \matice U \vec x \rVert_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 \]
+
\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  
\[\matice H(\vec w)\matice A\matice H(\vec w)\vec e^{(1)}=\lambda\vec e^{(1)}\] kde \( \vec e^{(1)} \) je vlastní vektor matice \(\matice A\).
+
\[\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}
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} \]
+
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:
a vezmeme \(\vec x\) jako normovaný:
+
\[\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} \]
 
\[ \vec w = \frac{\vec e^{(1)}-\vec x}{\lVert \vec e^{(1)} - \vec x \rVert_2} \]
\[\matice H (\vec w)\vec e^{(1)} = \vec x\]
+
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 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)}\]
+
\[\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{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 191: Řá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{SchurovaVeta}
+
\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 \]
 
kde \(\matice U \) je unitární matice a \(\matice R\) je horní trojúhelníková matice.
 
kde \(\matice U \) je unitární matice a \(\matice R\) je horní trojúhelníková matice.
Řádka 204: Řádka 215:
 
\end{remark}
 
\end{remark}
 
\begin{proof}
 
\begin{proof}
Mějme matici \(\matice A\) a předpokládejme podle \(\ref{HouseholderEigenvalue}\), že existuje \(\vec w_1 \in \matice C^{n}\).
+
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}  
+
\[ \matice H (\vec w_1)\matice A \matice H (\vec w_1) =
 +
\begin{pmatrix}  
 
\lambda_1 & \cdots \\
 
\lambda_1 & \cdots \\
0 & \multirow{3}{*}{ \Huge {\( \matice A' \)} } \\
+
0 & \multirow{3}{*}{ \huge {\( \matice A' \)} } \\
 
\vdots & \\
 
\vdots & \\
 
0 & \\
 
0 & \\
\end{pmatrix} = \matice H_1 \matice A \matice H_1\)
+
\end{pmatrix}
\\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}\). Mějme také matici \(\matice H'(\vec w'_2) \in \matice C^{n-1,n-1} \) a matici \(\matice H_2\), definovanou jako \(\matice H_2 = \begin{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 \\
 
1 & \cdots \\
0 & \multirow{3}{*}{ \Huge{\( \matice H'(\vec w'_2) \)} } \\
+
0 & \multirow{3}{*}{ \huge{\( \matice H'(\vec w'_2) \)} } \\
 
\vdots & \\
 
\vdots & \\
 
0 & \\
 
0 & \\
\end{pmatrix}\)
+
\end{pmatrix}
\newpage \[\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=
+
\]
 +
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}  
 
\begin{pmatrix}  
 
1 & \cdots \\
 
1 & \cdots \\
0 & \multirow{3}{*}{ \Huge{\( \matice H'(\vec w'_2) \)} } \\
+
0 & \multirow{3}{*}{ \huge{\( \matice H'(\vec w'_2) \)} } \\
 
\vdots & \\
 
\vdots & \\
 
0 & \\
 
0 & \\
Řádka 226: Řádka 242:
 
\begin{pmatrix}  
 
\begin{pmatrix}  
 
\lambda_1 & \cdots \\
 
\lambda_1 & \cdots \\
0 & \multirow{3}{*}{ \Huge {\( \matice A' \)} } \\
+
0 & \multirow{3}{*}{ \huge {\( \matice A' \)} } \\
 
\vdots & \\
 
\vdots & \\
 
0 & \\
 
0 & \\
Řádka 232: Řádka 248:
 
\begin{pmatrix}  
 
\begin{pmatrix}  
 
1 & \cdots \\
 
1 & \cdots \\
0 & \multirow{3}{*}{ \Huge{\( \matice H'(\vec w'_2) \)} } \\
+
0 & \multirow{3}{*}{ \huge{\( \matice H'(\vec w'_2) \)} } \\
 
\vdots & \\
 
\vdots & \\
 
0 & \\
 
0 & \\
 
\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'' \)} }\\
 
\vdots & \vdots && \\
 
\vdots & \vdots && \\
 
0 & 0 & \\
 
0 & 0 & \\
 
\end{pmatrix}\]
 
\end{pmatrix}\]
Naprosto stejným postupem bychom pokračovali dále, až dojdeme k matici obsahující pouze vlastní čísla matice \(\matice A\). Tu označíme jako matici \(\matice R\). Matici \(\matice H_n \matice H_{n-1} ... \matice H_1\) označíme jako \(\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 \) (zřejmé). 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\]
+
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{proof}
 
\end{theorem}
 
\end{theorem}
 
+
 
\begin{theorem}
 
\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}
 
\begin{proof}
Ukážeme, že \( \matice R \) z \ref{SchurovaVeta} 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}
+
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 = 1}^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 275: Řádka 286:
 
\end{proof}
 
\end{proof}
 
\end{theorem}
 
\end{theorem}
 
+
 
\begin{theorem}
 
\begin{theorem}
 
\label{RozklNormMatice}
 
\label{RozklNormMatice}
Řádka 285: Řá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 291: Řá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.
+
\[\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}[Jordanova Věta]
+
\begin{theorem}[Jordan]
\label{JordanovaVeta}
+
\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í matici \( \matice J \) tvaru:
+
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 =
 
\[ \matice J =
 
\begin{pmatrix}
 
\begin{pmatrix}
\matice J_1^1 &&&&&&&&&&&&& \\
+
\matice J_1 && \multicolumn{3}{c}{\multirow{3}{*}{\Huge { \( \Theta \) }}} & \\
& \matice J_2^1 &&&&&&&&&&&& \\
+
& \matice J_2 && \\
&& \ddots &&&&&&&&&&& \\
+
\multicolumn{2}{c}{\multirow{2}{*}{\Huge { \( \Theta \) }}} & \ddots & \\
&&& \matice J_{s_1}^1 &&&&&&&&&& \\
+
&&& \matice J_p \\
&&&& \matice J_1^2 &&&&&&&&& \\
+
&&&&& \matice J_2^2 &&&&&&&& \\
+
&&&&&& \ddots &&&&&&& \\
+
&&&&&&& \matice J_{s_2}^2 &&&&&& \\
+
&&&&&&&& \matice J_1^3 &&&&& \\
+
&&&&&&&&& \ddots &&&& \\
+
&&&&&&&&&& \matice J_1^p &&& \\
+
&&&&&&&&&&& \matice J_2^p && \\
+
&&&&&&&&&&&& \ddots & \\
+
&&&&&&&&&&&&& \matice J_{s_p}^p \\
+
 
\end{pmatrix} \]
 
\end{pmatrix} \]
 
kde:
 
kde:
\[ \matice J_i^k =
+
\[ \matice J_k =
 
\begin{pmatrix}
 
\begin{pmatrix}
\lambda_k &&& \\
+
\lambda_k && \multicolumn{3}{c}{\multirow{3}{*}{\Huge { \( 0 \) }}} & \\
 
1 & \lambda_k && \\
 
1 & \lambda_k && \\
& \ddots & \ddots & \\
+
\multirow{2}{*}{\Huge { \( 0 \) }} & \ddots & \ddots & \\
 
&& 1 & \lambda_k \\
 
&& 1 & \lambda_k \\
 
\end{pmatrix}, \;
 
\end{pmatrix}, \;
\forall k \in \hat p, \forall i \in \hat{s_k} \]
+
\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 333: Řádka 335:
 
\end{proof}
 
\end{proof}
 
\end{theorem}
 
\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}
 
\subsection{Vlastní čísla matice}
 
+
 
\setcounter{define}{43}
 
\setcounter{define}{43}
 
\begin{theorem}
 
\begin{theorem}
Řádka 341: Řádka 369:
 
Podobné matice \( \matice A \) a \( \matice B \) mají stejná vlastní čísla se stejnou geometrickou násobností.
 
Podobné matice \( \matice A \) a \( \matice B \) mají stejná vlastní čísla se stejnou geometrickou násobností.
 
\begin{proof}
 
\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{JordanovaVeta} a označíme \( \matice B = \matice K^{-1} \matice{JK} \), kde \( \matice J \) je Jordanova matice. Pak platí:
+
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} ) \]
 
\[ \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{JordanovaVeta} plyne, že matice \( \matice J \) je Jordanovou maticí k matici \( \matice A \). Z definice Jordanovy matice pak plyne tvrzení věty.
+
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{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 354: Řá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}
 
\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{SchurovaVeta} \(\matice A = \matice{U^* D U}\) kde \(\matice D > 0 \). Vezmu tedy libovolný vektor \(\vec c \neq \vec 0\) a 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}=\vec y^*\matice D\vec y > 0 \Rightarrow \matice D > 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{itemize}
 
\end{proof}
 
\end{proof}
 
\end{theorem}
 
\end{theorem}
 
+
 
\subsection{Normy}
 
\subsection{Normy}
 
+
 
\setcounter{define}{52}
 
\setcounter{define}{52}
 
\begin{theorem}
 
\begin{theorem}
Řádka 378: Řádka 407:
 
\end{proof}
 
\end{proof}
 
\end{theorem}
 
\end{theorem}
 
+
 
\begin{theorem}
 
\begin{theorem}
 
\label{KonvergenceVNorme}
 
\label{KonvergenceVNorme}
Řádka 389: Řádka 418:
 
\end{proof}
 
\end{proof}
 
\end{theorem}
 
\end{theorem}
 
+
 
\setcounter{define}{59}
 
\setcounter{define}{59}
 
\begin{theorem}
 
\begin{theorem}
 
\label{NormaMatice}
 
\label{NormaMatice}
 
Při značení:
 
Při značení:
\[\lVert \matice A \rVert_{\infty} = \underset {\lVert \vec x \rVert _\infty = 1}{max} \lVert \matice A \vec x \rVert_{\infty} \]
+
\[ \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} = \underset {\lVert \vec x \rVert _1 = 1}{max} \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} = \underset {\lVert \vec x \rVert _2 = 1}{max} \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 \matice C^{n,n}\) platí vztahy:
+
pro každou matici \( \matice A \in \mathbbm C^{n, n} \) platí vztahy:
\[\lVert \matice A \rVert_{\infty} = \underset {i \in \hat n}{max} \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 \]
\[\lVert \matice A \rVert_{1} = \underset {j \in \hat n}{max} \sum_{i=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})} \]
+
\[ \lVert \matice A \rVert _2 = \sqrt{\rho ( \matice {A^* A} ) } \]
\begin{proof} OPRAVIT
+
\begin{proof}
 
\begin{enumerate}[(1)]
 
\begin{enumerate}[(1)]
\item \(\lVert \matice A \rVert_{\infty} = \underset {i \in \hat n}{max} \sum_{j=1}^n \lvert \matice A_{ij} \rvert = \underset {i \in \hat n}{max} \sum_{j=1}^n \lvert \matice A_{ij} \rvert \)
+
\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 \)
\\Hledáme \(\vec x\) tak, aby nějaká složka \(\matice A \vec x\) byla maximální a zároveň \(\vec x_i \in \braket {-1,+1}\), \( i \in \hat n \)
+
\\ 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 \).
\[(\matice A \vec x)_i = \sum_{j=1}^n a_{ij}x_j\]
+
\begin{remark*}
Hledám maximální hodnotu, volím tedy \(x_i = 1\) pro \(\matice A_{ij} > 0\) a \(x_i = -1\) pro \(\matice A_{ij} < 0\).
+
Hledáme maxima přes řádky, maximové normě pro matice se tedy říká také řádková norma.
\[\Rightarrow (\matice A \vec x)_i = \sum_{j=1}^n  \lvert a_{ij} \rvert \]
+
\end{remark*}
Poznámka: Hledám maxima přes řádky, maximové normě pro matice se tedy říká také řádková norma.
+
\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 \)
\\ \item \(\lVert \matice A \rVert_{1} = \underset {\lVert \vec x \rVert _1 = 1}{max} \lVert \matice A \vec x \rVert_{1} = \underset {j \in \hat n}{max} \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.
Opět hledáme takové \(\vec x\), aby byly složky \(\matice A \vec x\) byly v absolutní hodnotě maximální. Je výhodné zvolit si jednu složku jako \(\pm 1\). /Hanele důkaz moc nechápe, Oberhuber skáče trochu moc./
+
\begin{remark*}
Tentokrát hledám maxima přes sloupečky, normě se tedy říká sloupcová.  
+
Hledáme maxima přes sloupce, normě se tedy říká sloupcová.  
Platí také \[\lVert \matice A \rVert _{\infty} = \lVert \matice A \rVert _1\]
+
\end{remark*}
\\ \item \(\lVert \matice A \rVert _2 = \sqrt{\rho(\matice {A^*A})}\)
+
\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} = \underset {\lVert \vec x \rVert _2 = 1}{max} \lVert \matice A \vec x \rVert_{2} = \underset {\vec x \neq \vec 0}{max} \frac{\lVert \matice A \vec x \rVert_{2}}{\lVert \vec x \rVert_{2}} = \underset {\vec x \neq \vec 0}{max} \frac{\braket{\matice A \vec x| \matice A \vec x}}{\braket{\vec x|\vec x}} = \underset {\vec x \neq \vec 0}{max}\frac{\braket{\vec x| \matice {A^*A} \vec x}}{\braket{\vec x|\vec x}\]
+
\[ \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^*DU}\)
+
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} \)
\[\underset {\vec x \neq \vec 0}{max}\frac{\braket{\vec x| \matice {A^*A} \vec x}}{\braket{\vec x|\vec x}} = \underset {\vec x \neq \vec 0}{max}\frac{\braket{\vec x| \matice {U^*DU} \vec x}}{\braket{\vec x|\vec x}} = \underset {\vec x \neq \vec 0}{max}\frac{\braket{\matice U \vec x| \matice {DU} \vec x}}{\braket{\vec x|\vec x}} \]
+
\[\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} \]
Mějme vektor \(\vec y\) tak, že \(\vec y = \matice U \vec x\) a \(\lVert \vec y \rVert = \lVert \vec x \rVert\). Prvky na diagonále \(\matice D\) označme \(\matice D_{ii} = \lambda_i\)
+
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 \)
\[\underset {\vec x \neq \vec 0}{max}\frac{\braket{\matice U \vec x| \matice {DU} \vec x}}{\braket{\vec x|\vec x}} = \underset {\vec y \neq \vec 0}{max}\frac{\braket{\vec y| \matice D \vec y}}{\lVert \vec y \rVert _2^2} = \underset {\vec y \neq \vec 0}{max} \frac{\sum_{i=1}^n \lvert \lambda_i \rvert \lvert y_i \rvert ^2}{\sum_{i=1}^n \lvert y_i \rvert ^2} = \underset {\lVert \vec x \rVert _2 = 1}{max}\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 \]
Poznámka: 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)\).  
+
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
\\ Je-li \(\matice A\) unitární, pak \(\lVert \matice A \rVert _2 = 1\)
+
\[ \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{enumerate}
 
\end{proof}
 
\end{proof}
 
\end{theorem}
 
\end{theorem}
 
+
 
\subsection{Konvergence geometrické posloupnosti matic}
 
\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}
 
\setcounter{define}{62}
 
\begin{theorem}
 
\begin{theorem}
 
\label{GeomKSpektrum}
 
\label{GeomKSpektrum}
 
Nechť \( \matice A \in \mathbbm C^{n, n} \). Potom platí
 
Nechť \( \matice A \in \mathbbm C^{n, n} \). Potom platí
\[ \matice A^k \rightarrow \Theta \Leftrightarrow \rho ( \matice A ) < 1 \]
+
\[ \lim_{k \rightarrow \infty} \matice A^k = \Theta \Leftrightarrow \rho ( \matice A ) < 1 \]
 
\begin{proof}
 
\begin{proof}
TODO
+
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{proof}
 
\end{theorem}
 
\end{theorem}
 
+
 
\begin{theorem}
 
\begin{theorem}
 
\label{GeomKNorma}
 
\label{GeomKNorma}
 
Nechť \( \matice A \in \mathbbm C^{n, n} \). Potom platí
 
Nechť \( \matice A \in \mathbbm C^{n, n} \). Potom platí
\[ \exists \; \text{maticová norma} \; \lVert \, \cdot \, \rVert, \lVert \matice A \rVert < 1 \Rightarrow \matice A^k \rightarrow \Theta \]
+
\[ \exists \; \text{maticová norma} \; \lVert \, \cdot \, \rVert, \lVert \matice A \rVert < 1 \Rightarrow \lim_{k \rightarrow \infty} \matice A^k = \Theta \]
 
\begin{proof}
 
\begin{proof}
TODO
+
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{proof}
 
\end{theorem}
 
\end{theorem}
 
+
 
\begin{theorem}
 
\begin{theorem}
 
\label{AbsEigenvalueVSNorma}
 
\label{AbsEigenvalueVSNorma}
Řádka 451: Řádka 525:
 
\[ \forall \; \text{maticové normy} \; \lVert \, \cdot \, \rVert, \rho ( \matice A ) \leq \lVert \matice A \rVert \]
 
\[ \forall \; \text{maticové normy} \; \lVert \, \cdot \, \rVert, \rho ( \matice A ) \leq \lVert \matice A \rVert \]
 
\begin{proof}
 
\begin{proof}
TODO
+
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{proof}
 
\end{theorem}
 
\end{theorem}
 
+
 
\begin{theorem}
 
\begin{theorem}
 
\label{NutPostK}
 
\label{NutPostK}
 
Nechť \( \matice A \in \mathbbm C^{n, n} \). Potom platí
 
Nechť \( \matice A \in \mathbbm C^{n, n} \). Potom platí
\[ \sum_{i = 1}^\infty \matice A^i < \infty \Leftrightarrow \matice A^k \rightarrow \Theta \]
+
\[ \sum_{i = 0}^\infty \matice A^i < \infty \Leftrightarrow \lim_{k \rightarrow \infty} \matice A^k = \Theta \]
 
a
 
a
\[ \sum_{i = 1}^\infty \matice A^i < \infty \Rightarrow \sum_{i = 1}^\infty \matice A^i = ( \matice I - \matice A )^{-1} \]
+
\[ \sum_{i = 0}^\infty \matice A^i < \infty \Rightarrow \sum_{i = 0}^\infty \matice A^i = ( \matice I - \matice A )^{-1} \]
 
\begin{proof}
 
\begin{proof}
TODO
+
\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{proof}
 
\end{theorem}
 
\end{theorem}
 
+
 
\begin{theorem}
 
\begin{theorem}
 
\label{GeomRozvoj}
 
\label{GeomRozvoj}
 
Nechť \( \matice A \in \mathbbm C^{n, n} \) a \( \lVert \matice A \rVert < 1 \). Potom platí
 
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 = 1}^k \matice A^i \right\rVert \leq \frac{\lVert \matice A \rVert^{k + 1}}{1 - \lVert \matice A \rVert}, \; \forall k \in \mathbbm N \]
+
\[ \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}
 
\begin{proof}
TODO
+
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{proof}
 
\end{theorem}
 
\end{theorem}

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 01NUM1Dedicma2 3. 6. 202419:49
Řídící stránka editovatDefiniční stránka dokumentu a vložených obrázkůDedicma2 3. 6. 202419:48
Header editovatHlavičkový souborDedicma2 17. 1. 201616:20 header.tex
Kapitola0 editovatZnačeníDedicma2 23. 5. 201721:32 znaceni.tex
Kapitola2 editovatOpakování a doplnění znalostí z lineární algebryDedicma2 3. 6. 202415:41 prezentace2.tex
Kapitola3 editovatÚvod do numerické matematikyDedicma2 3. 6. 202415:51 prezentace3.tex
Kapitola4 editovatPřímé metody pro lineární soustavyDedicma2 3. 6. 202416:47 prezentace4.tex
Kapitola5 editovatIterativní metodyDedicma2 3. 6. 202416:59 prezentace5.tex
Kapitola6 editovatVlastní čísla a vektory maticDedicma2 3. 6. 202417:07 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}