01NUM1:Kapitola2: Porovnání verzí
Z WikiSkripta FJFI ČVUT v Praze
m (typo) |
m (změna multirow matice) |
||
Řádka 165: | Řádka 165: | ||
\begin{remark} | \begin{remark} | ||
\(\matice M \vec e^{(1)} = \lambda \vec e^{(1)} \Rightarrow \matice M = \begin{pmatrix} | \(\matice M \vec e^{(1)} = \lambda \vec e^{(1)} \Rightarrow \matice M = \begin{pmatrix} | ||
− | \lambda | + | \lambda & \multirow{4}{*}{\text{\Huge ?}} \\ |
− | 0 | + | 0 & \\ |
− | \vdots | + | \vdots & \\ |
− | 0 & \ | + | 0 & \\ |
\end{pmatrix}\) | \end{pmatrix}\) | ||
− | \\\(\matice M = \matice H (\vec w)\matice A \matice H (\vec w)\) je podobnostní transformace. | + | \end{remark} |
+ | \begin{remark} | ||
+ | \(\matice M = \matice H (\vec w)\matice A \matice H (\vec w)\) je podobnostní transformace. | ||
\end{remark} | \end{remark} |
Verze z 15. 11. 2015, 13:40
[ 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} \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í přes \( 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} \( \matice H( \vec w )\) je Householderova reflexč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 w \) 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í. \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} Nechť \(\lambda\) je vlastní číslo matice \(\matice A\), pak existuje Houholderova 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 \(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}