01NUM1:Kapitola2: Porovnání verzí

Z WikiSkripta FJFI ČVUT v Praze
Přejít na: navigace, hledání
Řádka 301: Řádka 301:
 
\item Podle Schurovy věty: \(\matice A = \matice{U^*D^*U}\) kde \(\matice D > 0 \). Vezmu tedy libovolný vektor \(\vec c \neq 0\) a vektor \(\vec y = \matice U \vec x \Rightarrow \vec y \neq \vec 0\)
 
\item Podle Schurovy věty: \(\matice A = \matice{U^*D^*U}\) kde \(\matice D > 0 \). Vezmu tedy libovolný vektor \(\vec c \neq 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^*D^*U}\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^*D^*U}\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\]
 +
\end{itemize}
 +
\end{proof}
 +
\end{theorem}
 +
 +
 +
 +
\begin{theorem}
 +
\label{NormaMatice}
 +
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_{1} = \underset {\lVert \vec x \rVert _1 = 1}{max} \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} \]
 +
 +
pro každou matici \(\matice A \in \matice 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_{1} = \underset {j \in \hat n}{max} \sum_{i=1}^n \lvert \matice A_{ij} \rvert \]
 +
\[\lVert \matice A \rVert _2 = \sqrt{\rho(\matice {A^*A})} \]
 +
\\ \begin{proof}
 +
\begin{itemize}
 +
\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 \)
 +
\\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 \)
 +
\[(\matice A \vec x)_i = \sum_{j=1}^n a_{ij}x_j\]
 +
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\).
 +
\[\Rightarrow (\matice A \vec x)_i = \sum_{j=1}^n  \lvert a_{ij} \rvert \]
 +
Poznámka: Hledám maxima přes řádky, maximové normě pro matice se tedy říká také řádková norma.
 +
\\ \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\)
 +
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, Oberhuba skáče trochu moc./
 +
Tentokrát hledám maxima přes sloupečky, normě se tedy říká sloupcová.
 +
Platí také \[\lVert \matice A \rVert _{\infty} = \lVert \matice A \rVert _1\]
 +
\\ \item \(\lVert \matice A \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}}  \]
 +
Dále využijee toho, že matice \(\matice {A^*A}\) je normální (což tvrdí Oberhuber, ale Hanele nevidí), tedy lze ji napsat ve tvaru \(\matice {U^*DU}\)
 +
\[\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}} \]
 +
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\)
 +
\[\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\]
 +
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)\).
 +
\\ Je-li \(\matice A\) unitární, pak \(\lVert \matice A \rVert _2 = 1\)
 
\end{itemize}
 
\end{itemize}
 
\end{proof}
 
\end{proof}
 
\end{theorem}
 
\end{theorem}

Verze z 23. 11. 2015, 21:08

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}
 
\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}
 
\begin{theorem}
\label{LDR}
Každou 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 \in \mathbbm C^{1, 1} \Rightarrow \matice A = ( \matice A_{11} ) = \matice I (\matice A_{11} ) \matice I \)
  kde \( \matice L = \matice I \) a \( \matice R = \matice I \)
 \item \( n \rightarrow n + 1 \)
  \\ \( \matice A \in \mathbbm C^{n+1, n+1} \matice A = 
  \begin{pmatrix}
   \matice A' & \vec v \\
   \vec u^T & \alpha \\
  \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:
  \[ \begin{pmatrix}
   \matice L' & \vec 0 \\
   \vec l^T & 1 \\
  \end{pmatrix}
  \begin{pmatrix}
   \matice D' & \vec 0 \\
   \vec 0^T & d_{n+1} \\
  \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_{n+1} \\
  \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 r \vec l^T \matice D' + d_{n+1} \\
  \end{pmatrix} =
  \begin{pmatrix}
   \matice A' & \vec v \\
   \vec u^T & \alpha \\
  \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
  \\ d_{n+1} = \alpha - \vec r \vec l^T \matice D'
\)
\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
 \\ \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}.
 \\ \( \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 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 \)
\end{remark*}
 
\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}
\label{HouseholderReflekcni}
\( \matice H( \vec w )\) je Householderova reflekční matice a \( \vec w \) 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 =  \]
\end{enumerate}
\end{proof}
\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}
\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 vlastní vektor matice \(\matice A\).
\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} \]
a vezmeme \(\vec x\) jako normovaný:
\[ \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\]
\[\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)}\]
\end{proof}
\end{theorem}
 
\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}
\label{SchurovaVeta}
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\).
\end{remark}
\begin{proof}
Mějme matici \(\matice A\) a předpokládejme podle \(\ref{HouseholderEigenvalue}\), že existuje \(\vec w_1 \in \matice C^{n}\). 
\\\( \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}\). 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} 
1 & \cdots \\
0 & \multirow{3}{*}{ \Huge{\( \matice H'(\vec w'_2) \)} } \\
\vdots & \\
0 & \\
\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=
\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 & 0 & \cdots \\
0 & \lambda_2 & \cdots \\
\vdots & 0 & \multirow{3}{*}{ \Huge {\( \matice A'' \)} }\\
\vdots & \vdots && \\
0 & 0 & \\
\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 triviá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\]
\end{proof}
\end{theorem}
 
\begin{theorem}
\label{NormalniTrojuhelnikDiagonalni}
Normální trojúhelníková matice je diagonální.
\begin{proof}
Ukážeme, že \( \matice R \) z \ref{SchurovaVeta} je normální:
\[ \matice A = \matice U^* \matice R \matice U \Rightarrow \matice R = \matice U \matice A \matice U^* \]
\[ \matice R^* = ( \matice U \matice A \matice U^* )^* = \matice U \matice A^* \matice U^* \]
\[ \matice{R R^*} = \matice{R^* R} \]
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 \)
\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^*} = 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.
\end{enumerate}
\end{proof}
\end{theorem}
\begin{define}
Matice \(\matice A \in \matice 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\).
Je-li \(\matice B \in \matice T^{n,n} \matice A - \matice B > 0 \), pak píšeme \(\matice A > \matice B \)
\end{define}
\begin{theorem}
Všechna vlastní čísla pozitivně definitní matice \(\matice A\) jsou kladná. Je-li matice \(\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.
\[\braket{\matice A \vec x| \vec x} = \braket{\lambda \vec x|\vec x} = \lambda \lVert \vec x \rVert ^2_2 > 0 \Rightarrow \lambda > 0\]
\item Podle Schurovy věty: \(\matice A = \matice{U^*D^*U}\) kde \(\matice D > 0 \). Vezmu tedy libovolný vektor \(\vec c \neq 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^*D^*U}\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\]
\end{itemize}
\end{proof}
\end{theorem}
 
 
 
\begin{theorem}
\label{NormaMatice}
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_{1} = \underset {\lVert \vec x \rVert _1 = 1}{max} \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} \]
 
pro každou matici \(\matice A \in \matice 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_{1} = \underset {j \in \hat n}{max} \sum_{i=1}^n \lvert \matice A_{ij} \rvert \]
\[\lVert \matice A \rVert _2 = \sqrt{\rho(\matice {A^*A})} \]
\\ \begin{proof}
\begin{itemize}
\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 \)
\\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 \)
\[(\matice A \vec x)_i = \sum_{j=1}^n a_{ij}x_j\]
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\).
\[\Rightarrow (\matice A \vec x)_i = \sum_{j=1}^n  \lvert a_{ij} \rvert \]
Poznámka: Hledám maxima přes řádky, maximové normě pro matice se tedy říká také řádková norma.
\\ \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\)
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, Oberhuba skáče trochu moc./
Tentokrát hledám maxima přes sloupečky, normě se tedy říká sloupcová. 
Platí také \[\lVert \matice A \rVert _{\infty} = \lVert \matice A \rVert _1\]
\\ \item \(\lVert \matice A \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}}  \]
Dále využijee toho, že matice \(\matice {A^*A}\) je normální (což tvrdí Oberhuber, ale Hanele nevidí), tedy lze ji napsat ve tvaru \(\matice {U^*DU}\)
\[\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}} \]
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\)
\[\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\]
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)\). 
\\ Je-li \(\matice A\) unitární, pak \(\lVert \matice A \rVert _2 = 1\)
\end{itemize}
\end{proof}
\end{theorem}