01NUM1:Kapitola2: Porovnání verzí
Z WikiSkripta FJFI ČVUT v Praze
(Přidána Věta navíc) |
(label pro lemma v konvergence geometrické posloupnosti.) |
||
(Není zobrazeno 57 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 \) | |
− | + | \\ \( \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} | \[ \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 & | + | \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' & | + | \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 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} |
− | + | \] | |
− | + | 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} | \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 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{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 | + | \( \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 158: | Řádka 169: | ||
\end{proof} | \end{proof} | ||
\end{theorem} | \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 | + | \[\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} \] | ||
− | \ | + | 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 | + | \begin{theorem}[Schurova věta] |
\label{Schur} | \label{Schur} | ||
Libovolná matice \(\matice A \in \matice C^{n,n} \) se dá zapsat jako \[\matice A = \matice U^* \matice R \matice U \] | Libovolná matice \(\matice A \in \matice C^{n,n} \) se dá zapsat jako \[\matice A = \matice U^* \matice R \matice U \] | ||
Řádka 204: | Řádka 215: | ||
\end{remark} | \end{remark} | ||
\begin{proof} | \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 \\ | \lambda_1 & \cdots \\ | ||
− | 0 & \multirow{3}{*}{ \ | + | 0 & \multirow{3}{*}{ \huge {\( \matice A' \)} } \\ |
\vdots & \\ | \vdots & \\ | ||
0 & \\ | 0 & \\ | ||
− | \end{pmatrix} = \matice H_1 \matice A \matice H_1\ | + | \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 \\ | 1 & \cdots \\ | ||
− | 0 & \multirow{3}{*}{ \ | + | 0 & \multirow{3}{*}{ \huge{\( \matice H'(\vec w'_2) \)} } \\ |
\vdots & \\ | \vdots & \\ | ||
0 & \\ | 0 & \\ | ||
− | \end{pmatrix} | + | \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} | \begin{pmatrix} | ||
1 & \cdots \\ | 1 & \cdots \\ | ||
− | 0 & \multirow{3}{*}{ \ | + | 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}{*}{ \ | + | 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}{*}{ \ | + | 0 & \multirow{3}{*}{ \huge{\( \matice H'(\vec w'_2) \)} } \\ |
\vdots & \\ | \vdots & \\ | ||
0 & \\ | 0 & \\ | ||
\end{pmatrix}\]\[= | \end{pmatrix}\]\[= | ||
\begin{pmatrix} | \begin{pmatrix} | ||
− | \lambda_1 & | + | \lambda_1 & r_1 & \cdots \\ |
0 & \lambda_2 & \cdots \\ | 0 & \lambda_2 & \cdots \\ | ||
− | \vdots & 0 & \multirow{3}{*}{ \ | + | \vdots & 0 & \multirow{3}{*}{ \huge {\( \matice A'' \)} }\\ |
\vdots & \vdots && \\ | \vdots & \vdots && \\ | ||
0 & 0 & \\ | 0 & 0 & \\ | ||
\end{pmatrix}\] | \end{pmatrix}\] | ||
− | Naprosto stejným postupem | + | 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} | ||
− | + | 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 \] | |
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | \[ (\matice A^* \matice A)_{ii} = \sum_{k = 1}^n \matice | + | |
− | \[ (\matice A \matice A^*)_{ii} = \sum_{k = 1}^n \matice A_{ik} \matice | + | |
− | \[ (\matice A^* \matice A)_{ii} = (\matice A^* \matice A)_{ii} \Leftrightarrow \sum_{k = | + | |
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. \qedhere | \[\matice D^* = \matice D \Rightarrow \matice D \in \matice R^{n,n}\] protože transpozicí se diagonálních prvků nedotkneme a rovnost hermitovsky sdružených prvků nastává pokud jsou prvky reálná čísla. \qedhere | ||
\end{enumerate} | \end{enumerate} | ||
\end{proof} | \end{proof} | ||
\end{theorem} | \end{theorem} | ||
− | + | ||
\subsection{Rozklady matic - Jordanova Věta} | \subsection{Rozklady matic - Jordanova Věta} | ||
− | + | ||
\begin{theorem}[Jordan] | \begin{theorem}[Jordan] | ||
\label{Jordan} | \label{Jordan} | ||
Řádka 304: | Řádka 315: | ||
\[ \matice J = | \[ \matice J = | ||
\begin{pmatrix} | \begin{pmatrix} | ||
− | \matice J_1 &&&\\ | + | \matice J_1 && \multicolumn{3}{c}{\multirow{3}{*}{\Huge { \( \Theta \) }}} & \\ |
− | & \matice J_2 &&\\ | + | & \matice J_2 && \\ |
− | + | \multicolumn{2}{c}{\multirow{2}{*}{\Huge { \( \Theta \) }}} & \ddots & \\ | |
&&& \matice J_p \\ | &&& \matice J_p \\ | ||
\end{pmatrix} \] | \end{pmatrix} \] | ||
Řádka 312: | Řádka 323: | ||
\[ \matice J_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 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 323: | Řádka 335: | ||
\end{proof} | \end{proof} | ||
\end{theorem} | \end{theorem} | ||
− | + | ||
\begin{theorem*}[Věta navíc] | \begin{theorem*}[Věta navíc] | ||
\label{DefiniceMocninyMatice} | \label{DefiniceMocninyMatice} | ||
− | Nechť \( \matice A \in \mathbbm C^{n, n} \). Definujeme mocninu matice \( \matice A^p \) takto: | + | \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 \] | \[ \matice A^p = \prod_{k = 1}^p \matice A \] | ||
Potom platí: | Potom platí: | ||
Řádka 344: | Řádka 357: | ||
\end{proof} | \end{proof} | ||
\end{theorem*} | \end{theorem*} | ||
− | + | ||
\begin{remark*} | \begin{remark*} | ||
− | V prezentaci je mocnina matice definována pomocí Schurovy věty, kde je navíc přidán požadavek, aby matice \( \matice A \) byla hermitovská a pozitivně definitní, díky čemuž je matice \( \matice R \) diagonální s kladnými členy a tím pádem se Schurova věta stává speciálním případem věty Jordanovy. Předešlá věta v prezentaci chybí, přestože je občas používána. | + | V prezentaci je mocnina matice definována pomocí Schurovy věty, kde je navíc přidán požadavek, aby matice \( \matice A \) byla hermitovská a pozitivně definitní, díky čemuž je matice \( \matice R \) diagonální s kladnými členy a tím pádem se Schurova věta stává speciálním případem věty Jordanovy. Tato definice umožní jednoduše definovat i neceločíselné mocniny. Předešlá věta v prezentaci chybí, přestože je občas používána. |
\end{remark*} | \end{remark*} | ||
− | + | ||
\subsection{Vlastní čísla matice} | \subsection{Vlastní čísla matice} | ||
− | + | ||
\setcounter{define}{43} | \setcounter{define}{43} | ||
\begin{theorem} | \begin{theorem} | ||
Řádka 361: | Řádka 374: | ||
\end{proof} | \end{proof} | ||
\end{theorem} | \end{theorem} | ||
− | + | ||
\subsection{Pozitivně definitní matice} | \subsection{Pozitivně definitní matice} | ||
− | + | ||
\begin{define} | \begin{define} | ||
Matice \(\matice A \in \mathbbm T^{n, n}\) je pozitivně definitní \(\Leftrightarrow\) \[ \forall \vec x \neq \vec 0, \; \vec x^*\matice A \vec x \in \matice R^+\] | Matice \(\matice A \in \mathbbm T^{n, n}\) je pozitivně definitní \(\Leftrightarrow\) \[ \forall \vec x \neq \vec 0, \; \vec x^*\matice A \vec x \in \matice R^+\] | ||
Řádka 369: | Řá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 < \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{ | + | \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 | + | \[\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 393: | Řádka 407: | ||
\end{proof} | \end{proof} | ||
\end{theorem} | \end{theorem} | ||
− | + | ||
\begin{theorem} | \begin{theorem} | ||
\label{KonvergenceVNorme} | \label{KonvergenceVNorme} | ||
Řádka 404: | Řádka 418: | ||
\end{proof} | \end{proof} | ||
\end{theorem} | \end{theorem} | ||
− | + | ||
\setcounter{define}{59} | \setcounter{define}{59} | ||
\begin{theorem} | \begin{theorem} | ||
Řádka 412: | Řádka 426: | ||
\[ \lVert \matice A \rVert_1 = \max\limits_{\lVert \vec x \rVert _1 = 1} \lVert \matice A \vec x \rVert_1 \] | \[ \lVert \matice A \rVert_1 = \max\limits_{\lVert \vec x \rVert _1 = 1} \lVert \matice A \vec x \rVert_1 \] | ||
\[ \lVert \matice A \rVert_2 = \max\limits_{\lVert \vec x \rVert _2 = 1} \lVert \matice A \vec x \rVert_2 \] | \[ \lVert \matice A \rVert_2 = \max\limits_{\lVert \vec x \rVert _2 = 1} \lVert \matice A \vec x \rVert_2 \] | ||
− | + | ||
pro každou matici \( \matice A \in \mathbbm C^{n, n} \) platí vztahy: | pro každou matici \( \matice A \in \mathbbm C^{n, n} \) platí vztahy: | ||
\[ \lVert \matice A \rVert_\infty = \max\limits_{i \in \hat n} \sum_{j = 1}^n \lvert \matice A_{ij} \rvert \] | \[ \lVert \matice A \rVert_\infty = \max\limits_{i \in \hat n} \sum_{j = 1}^n \lvert \matice A_{ij} \rvert \] | ||
Řádka 433: | Řádka 447: | ||
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} \) | 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} \] | \[\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} \) | + | Označíme \(\vec y = \matice U \vec x\) a díky \ref{UnitarniZachovavaNormu} platí \(\lVert \vec y \rVert = \lVert \vec x \rVert\). Dále označíme \( \lambda_i = \matice D_{ii} \) vlastní čísla matice \( \matice A^* \matice A \) |
− | \[ \max\limits_{\vec x \neq \vec 0} \frac{\braket{\matice U \vec x | \matice {D U} \vec x}}{\lVert \vec x \rVert_2^2} = \max\limits_{\vec y \neq \vec 0} \frac{\braket{\vec y | \matice D \vec y}}{\lVert \vec y \rVert_2^2} = \max\limits_{\vec y \neq \vec 0} \frac{\sum_{i = 1}^n \lvert \lambda_i \rvert \lvert y_i \rvert^2}{\sum_{i = 1}^n \lvert y_i \rvert^2} = \max\limits_{\lVert \vec y \rVert_2 = 1} \sum_{i = 1}^n \lvert \lambda_i \rvert \lvert y_i \rvert^2\] | + | \[ \max\limits_{\vec x \neq \vec 0} \frac{\braket{\matice U \vec x | \matice {D U} \vec x}}{\lVert \vec x \rVert_2^2} = \max\limits_{\vec y \neq \vec 0} \frac{\braket{\vec y | \matice D \vec y}}{\lVert \vec y \rVert_2^2} = \max\limits_{\vec y \neq \vec 0} \frac{\sum_{i = 1}^n \lvert \lambda_i \rvert \lvert y_i \rvert^2}{\sum_{i = 1}^n \lvert y_i \rvert^2} = \max\limits_{\lVert \vec y \rVert_2 = 1} \sum_{i = 1}^n \lvert \lambda_i \rvert \lvert y_i \rvert^2 \] |
+ | Toto maximum nastává pro takový vektor \(\vec y\), ž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*} | \begin{remark*} | ||
− | Je-li \(\matice A\) hermitovská, platí \(\matice {A^*A} = \matice A^2\) a \(\lVert \matice A \rVert _2 = \sqrt{\rho(\matice A^2)} = \rho(\matice A)\). | + | Je-li \(\matice A\) hermitovská, platí \(\matice {A^*A} = \matice A^2\) a \(\lVert \matice A \rVert _2 = \sqrt{\rho(\matice A^2)} = \rho(\matice A)\). (Rovnost plyne z \ref{MocninaJordan}) |
\\ Je-li \(\matice A\) unitární, pak \(\lVert \matice A \rVert _2 = 1\) \qedhere | \\ Je-li \(\matice A\) unitární, pak \(\lVert \matice A \rVert _2 = 1\) \qedhere | ||
\end{remark*} | \end{remark*} | ||
Řádka 442: | Řádka 458: | ||
\end{proof} | \end{proof} | ||
\end{theorem} | \end{theorem} | ||
− | + | ||
\subsection{Konvergence geometrické posloupnosti matic} | \subsection{Konvergence geometrické posloupnosti matic} | ||
− | + | ||
\begin{lemma*} | \begin{lemma*} | ||
+ | \label{MocninaJordan} | ||
Nechť \( \matice J \in \mathbbm C^{n, n} \) je Jordanovou maticí z rozkladu \ref{Jordan}. Potom platí | Nechť \( \matice J \in \mathbbm C^{n, n} \) je Jordanovou maticí z rozkladu \ref{Jordan}. Potom platí | ||
\[ (\matice J^k)_{ij} = | \[ (\matice J^k)_{ij} = | ||
Řádka 482: | Řádka 499: | ||
\end{proof} | \end{proof} | ||
\end{lemma*} | \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 | + | \[ \lim_{k \rightarrow \infty} \matice A^k = \Theta \Leftrightarrow \rho ( \matice A ) < 1 \] |
\begin{proof} | \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 \). | 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 | + | \[ \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} | ||
Z \( \lVert \matice A \rVert < 1 \) plyne: | Z \( \lVert \matice A \rVert < 1 \) plyne: | ||
− | \[ \lVert \matice A^k \rVert \leq \lVert \matice A \rVert^k < 1^k \Rightarrow \lVert \matice A^k \rVert | + | \[ \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 519: | Řádka 536: | ||
\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 = 0}^\infty \matice A^i < \infty \Leftrightarrow \matice A^k | + | \[ \sum_{i = 0}^\infty \matice A^i < \infty \Leftrightarrow \lim_{k \rightarrow \infty} \matice A^k = \Theta \] |
a | a | ||
\[ \sum_{i = 0}^\infty \matice A^i < \infty \Rightarrow \sum_{i = 0}^\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} | ||
+ | \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í | 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} \] | \[ ( \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} ) \] | \[ \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} |
Verze z 30. 1. 2017, 17:14
[ znovu generovat, | výstup z překladu ] | Kompletní WikiSkriptum včetně všech podkapitol. | |
PDF Této kapitoly | [ znovu generovat, | výstup z překladu ] | Přeložení pouze této kaptioly. |
ZIP | Kompletní zdrojový kód včetně obrázků. |
Součásti dokumentu 01NUM1
součást | akce | popis | poslední editace | soubor | |||
---|---|---|---|---|---|---|---|
Hlavní dokument | editovat | Hlavní stránka dokumentu 01NUM1 | Dedicma2 | 3. 6. 2024 | 19:49 | ||
Řídící stránka | editovat | Definiční stránka dokumentu a vložených obrázků | Dedicma2 | 3. 6. 2024 | 19:48 | ||
Header | editovat | Hlavičkový soubor | Dedicma2 | 17. 1. 2016 | 16:20 | header.tex | |
Kapitola0 | editovat | Značení | Dedicma2 | 23. 5. 2017 | 21:32 | znaceni.tex | |
Kapitola2 | editovat | Opakování a doplnění znalostí z lineární algebry | Dedicma2 | 3. 6. 2024 | 15:41 | prezentace2.tex | |
Kapitola3 | editovat | Úvod do numerické matematiky | Dedicma2 | 3. 6. 2024 | 15:51 | prezentace3.tex | |
Kapitola4 | editovat | Přímé metody pro lineární soustavy | Dedicma2 | 3. 6. 2024 | 16:47 | prezentace4.tex | |
Kapitola5 | editovat | Iterativní metody | Dedicma2 | 3. 6. 2024 | 16:59 | prezentace5.tex | |
Kapitola6 | editovat | Vlastní čísla a vektory matic | Dedicma2 | 3. 6. 2024 | 17:07 | prezentace6.tex | |
Kapitola7 | editovat | Nelineární rovnice | Kubuondr | 31. 1. 2017 | 14:27 | prezentace7.tex | |
Kapitola8 | editovat | Interpolace | Kubuondr | 31. 1. 2017 | 15:43 | prezentace8.tex | |
Kapitola9 | editovat | Derivace a integrace | Kubuondr | 31. 1. 2017 | 17:33 | prezentace9.tex |
Zdrojový kód
%\wikiskriptum{01NUM1} \section{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}