01NUM1:Kapitola5: Porovnání verzí

Z WikiSkripta FJFI ČVUT v Praze
Přejít na: navigace, hledání
(Všechny věty)
m
 
(Není zobrazeno 50 mezilehlých verzí od 5 dalších uživatelů.)
Řádka 1: Řádka 1:
 
%\wikiskriptum{01NUM1}
 
%\wikiskriptum{01NUM1}
−
\section{Opakování a doplnění znalostí z lineární algebry}
+
\section{Iterativní metody – úvod a soustavy lineárních rovnic}
  
−
\subsection{Trojúhelníkové matice}
+
\subsection{Iterativní metody obecně}
  
−
\setcounter{define}{21}
 
 
\begin{theorem}
 
\begin{theorem}
−
\label{SoucinTrojuhelniku}
+
\label{KIterativniMetody}
−
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í:
+
Iterativní metoda tvaru
−
\[ \forall i \in \hat n, \matice C_{ii} = \matice A_{ii} \matice B_{ii} \]
+
\[ \vec x^{( k + 1 )} = \matice B^{( k )} \vec x^{( k )} + \vec c^{( k )} \]
 +
splňující
 +
\[ \vec x = \matice B^{( k )} \vec x + \vec c^{( k )} \]
 +
konverguje pro libovolné \( \vec x^{( 0 )} \) k \( \vec x \) právě tehdy, když
 +
\[ \lim_{k \rightarrow \infty} \prod_{i = 0}^k \matice B^{( k - i )} = \Theta \]
 
\begin{proof}
 
\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 \).
+
\[ \lim_{k \rightarrow \infty} \vec x^{( k )} - \vec x = \lim_{k \rightarrow \infty} \matice B^{( k - 1)} \vec x^{( k -1 )} + \vec c^{( k - 1 )} - \matice B^{( k - 1 )} \vec x - \vec c^{( k - 1 )} = \]
−
Tudíž:
+
\[ = \lim_{k \rightarrow \infty} \matice B^{( k - 1 )} ( \vec x^{( k -1 )} - \vec x ) = \dots = \lim_{k \rightarrow \infty} \prod_{i = 0}^{k - 1} \matice B^{( k - i - 1 )} ( \vec x^{( 0 )} - \vec x ) \]
−
\[ \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 nule pro libovolné \( \vec x^{( 0 )} \) právě tehdy, je-li splněna podmínka z věty.
−
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{proof}
 
\end{theorem}
 
\end{theorem}
−
+
 
 +
\begin{remark*}
 +
Vzhledem k tomu, že je výběr \( \vec x^{( 0 )} \) libovolný, bude tato metoda konvergovat i přes numerické chyby. Iterativní metody pro řešení soustav lineárních algebraických rovnic mají \textbf{samoopravující} vlastnost
 +
a jsou tudíž stabilní vzhledem k numerickým chybám.
 +
\end{remark*}
 +
 
 +
\subsection{Stacionární iterativní metody}
 +
 
 
\begin{theorem}
 
\begin{theorem}
−
\label{InverzeTrojuhelniku}
+
\label{KStacionarniIterativniMetody}
−
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í:
+
Stacionární iterativní metoda, tj. metoda tvaru
−
\[ \forall i \in \hat n, \; (\matice A^{-1})_{ii} = (\matice A_{ii})^{-1} = \frac{1}{\matice A_{ii} } \]
+
\[ \vec x^{( k + 1 )} = \matice B \vec x^{( k )} + \vec c \]
 +
splňující
 +
\[ \vec x = \matice B \vec x + \vec c \]
 +
konverguje pro libovolné \( \vec x^{( 0 )} \) k \( \vec x \) právě tehdy, když
 +
\[ \lim_{k \rightarrow \infty } \matice B^k = \Theta \]
 
\begin{proof}
 
\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 B^k = \prod_{i = 0}^k \matice B \) a tedy platnost této věty plyne přímo z \ref{KIterativniMetody}.
−
\[ \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{proof}
 
\end{theorem}
 
\end{theorem}
  
−
\subsection{Rozklad matice na horní a dolní trojúhelníkovou}
 
−
 
 
\begin{theorem}
 
\begin{theorem}
−
\label{LDR}
+
\label{KStacionarniIterativniMetodySpektrum}
−
Každou regulární matici \( \matice A \in \mathbbm C^{n, n} \) lze jednoznačně vyjádřit ve tvaru součinu:
+
Stacionární iterativní metoda, tj. metoda tvaru
−
\[ \matice A = \matice {LDR} \]
+
\[ \vec x^{( k + 1 )} = \matice B \vec x^{( k )} + \vec c \]
−
kde:
+
splňující
−
\begin{itemize}
+
\[ \vec x = \matice B \vec x + \vec c \]
−
\item \( \matice L \) je dolní trojúhelníková matice s jedničkami na diagonále
+
konverguje pro libovolné \( \vec x^{( 0 )} \) k \( \vec x \) právě tehdy, když
−
\item \( \matice D \) je diagonální matice
+
\[ \rho ( \matice B ) < 1 \]
−
\item \( \matice R \) je horní trojúhelníková matice s jedničkami na diagonále
+
−
\end{itemize}
+
 
\begin{proof}
 
\begin{proof}
−
\begin{enumerate}[(1)]
+
Plyne z \ref{GeomKSpektrum} a \ref{KStacionarniIterativniMetody}.
−
\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 \) \qedhere
+
−
\end{enumerate}
+
 
\end{proof}
 
\end{proof}
 
\end{theorem}
 
\end{theorem}
−
 
−
\begin{remark*}
 
−
Čísla na diagonále matice \( \matice D \) z \ref{LDR} \textbf{nejsou} vlastními čísly matice \( \matice A \)
 
−
\end{remark*}
 
  
−
 
−
\subsection{Rozklady matic}
 
−
 
−
\setcounter{define}{33}
 
 
\begin{theorem}
 
\begin{theorem}
−
\label{HouseholderHermUnit}
+
\label{KStacionarniIterativniMetodyNorma}
−
Householderova reflekční matice je hermitovská a unitární.
+
Postačující podmínkou pro to, aby stacionární iterativní metoda, tj. metoda tvaru
 +
\[ \vec x^{( k + 1 )} = \matice B \vec x^{( k )} + \vec c \]
 +
splňující
 +
\[ \vec x = \matice B \vec x + \vec c \]
 +
konvergovala pro libovolné \( \vec x^{( 0 )} \) k \( \vec x \) je
 +
\[ \exists \; \text{maticová norma} \; \lVert \, \cdot \, \rVert, \lVert \matice B \rVert < 1 \]
 
\begin{proof}
 
\begin{proof}
−
\begin{enumerate}[(1)]
+
Plyne z \ref{GeomKNorma} a \ref{KStacionarniIterativniMetody}.
−
\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{proof}
 
\end{theorem}
 
\end{theorem}
  
−
\begin{theorem}
+
\begin{theorem}[Aposteriorní odhad chyby pro stacionární iterativní metody]
−
\label{HouseholderReflekcni}
+
\label{AposteriorniOdhad}
−
\( \matice H( \vec w )\) je Householderova reflekční matice a \( \vec w \) je libovolný vektor z \( \mathbbm C^n \).  
+
Pro stacionární iterativní metodu, tj. metodu tvaru
−
\\ 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
+
\[ \vec x^{( k + 1 )} = \matice B \vec x^{( k )} + \vec c \]
−
\begin{itemize}
+
splňující
−
\item \(\lVert \matice H( \vec w )\vec v \rVert = \lVert \vec v \rVert\)
+
\[ \vec x = \matice B \vec x + \vec c \]
−
\item \(\matice H( \vec w )\vec v + \vec v \in L\)
+
kde \( \vec x \) je řešením soustavy lineárních rovnic \( \matice A \vec x = \vec b \), platí při použití \textbf{souhlasné normy} tyto odhady chyby aproximace řešení:
−
\item \((\matice H( \vec w )\vec v - \vec v) \perp L\)
+
−
\end{itemize}
+
−
\begin {proof}
+
 
\begin{enumerate}[(1)]
 
\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 \( \displaystyle \left\lVert \vec x^{( k )} - \vec x \right\rVert \leq \left\lVert \matice A^{-1} \right\rVert \left\rVert \matice A \vec x^{( k )} - \vec b \right\rVert \)
−
\item \(\matice H( \vec w )\vec v + \vec v \in L \Leftrightarrow \braket{\matice H( \vec w )\vec v + \vec v | \vec w} = 0 \) \[ \braket{\matice H( \vec w )\vec v + \vec v | \vec w} = 0 \Leftrightarrow \braket{(\matice I - 2\vec w \vec w^*)\vec v + \vec v| \vec w} = \braket{(2\vec v - 2\vec w \vec w^* \vec v | \vec w )} = \] \[ = 2\braket{\vec v|\vec w} - 2\braket{\vec w \vec w^* \vec v|\vec w} = 2\braket{\vec v|\vec w} - 2\underbrace{\vec w^* \vec w}_{\lVert \vec w \rVert = 1} \vec w^* \vec v = 2\braket{\vec v| \vec w} - 2\underbrace{\vec w^* \vec v}_{2\braket{\vec v| \vec w}} = 0 \]
+
\\
−
\item \( (\matice H( \vec w )\vec v - \vec v) \perp L \Leftrightarrow \forall \vec x \in L, \braket{\matice H( \vec w )\vec v - \vec v | \vec x} = 0 \)
+
\item \( \displaystyle \left\lVert \vec x^{( k )} - \vec x \right\rVert \leq \left\lVert ( \matice I - \matice B )^{-1} \right\rVert \lVert \matice B \rVert \left\lVert \vec x^{( k - 1)} - \vec x^{( k )} \right\rVert \)
−
\[ \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}
 +
\begin{proof}
 +
\begin{enumerate}[(1)]
 +
\item
 +
Nahrazujeme vektor \( \vec x\) pomocí \( \vec x =\matice A^{-1} \vec b \).
 +
\[ \left\lVert \vec x^{( k )} - \vec x \right\rVert = \left\lVert \matice A^{-1} ( \matice A \vec x^{( k )} - \vec b ) \right\rVert \leq \left\lVert \matice A^{-1} \right\rVert \left\rVert \matice A \vec x^{( k )} - \vec b \right\rVert \]
 +
kde poslední nerovnost plyne z trojúhelníkové nerovnosti.
 +
\item
 +
Nahrazujeme vektor \( \vec x\) pomocí \( \vec x =( \matice I - \matice B )^{-1} \vec c \), což je inverze podmínky pro řešení.
 +
\[ \left\lVert \vec x^{( k )} - \vec x \right\rVert = \left\lVert ( \matice I - \matice B )^{-1} ( ( \matice I - \matice B ) \vec x^{( k )} - \vec c ) \right\rVert \leq \left\lVert ( \matice I - \matice B )^{-1} \right\rVert \left\lVert ( \matice I - \matice B ) \vec x^{( k )} - \vec c \right\rVert \]
 +
kde poslední nerovnost je opět aplikací trojúhleníkové nerovnosti.
 +
\[ \left\lVert ( \matice I - \matice B )^{-1} \right\rVert \left\lVert ( \matice I - \matice B ) \vec x^{( k )} - \vec c \right\rVert = \left\lVert ( \matice I - \matice B )^{-1} \right\rVert \left\lVert \vec x^{(k)} - \matice B \vec x^{( k )} - \vec c \right\rVert = \left\lVert ( \matice I - \matice B )^{-1} \right\rVert \left\lVert \matice B \vec x^{(k - 1)} + \vec c - \matice B \vec x^{( k )} - \vec c \right\rVert = \]
 +
\[ = \left\lVert ( \matice I - \matice B )^{-1} \right\rVert \left\lVert \matice B ( \vec x^{(k - 1)} - \vec x^{( k )} ) \right\rVert \leq \left\lVert ( \matice I - \matice B )^{-1} \right\rVert \left\lVert \matice B \right\rVert \left\lVert \vec x^{(k - 1)} - \vec x^{( k )} \right\rVert \]
 +
kde poslední nerovnost je znovu pouze aplikací trojúhelníkové nerovnosti. \qedhere
 
\end{enumerate}
 
\end{enumerate}
 
\end{proof}
 
\end{proof}
 
\end{theorem}
 
\end{theorem}
  
−
\begin{theorem}
+
\begin{define}[V prezentaci poznámka]
−
\label{UnitarniZachovavaNormu}
+
Nechť \( \vec x^{( k )} \) je \( k \)-tá aproximace řešení soustavy lineárních rovnic \( \matice A \vec x = \vec b \). Potom definujeme reziduum v \( k \)-té iteraci
−
Nechť \( \matice U \) je unitární matice. Pak platí:
+
\[ \vec r^{( k )} = \matice A \vec x^{( k )} - \vec b \]
−
\[ \lVert \matice U \vec x \rVert_2 = \lVert \vec x \rVert_2 \]
+
\end{define}
−
Pro libovolný vektor \( \vec x \).
+
 
 +
\setcounter{define}{7}
 +
\begin{theorem}[Apriorní odhad chyby pro stacionární iterativní metody]
 +
\label{ApriorniOdhad}
 +
Pro stacionární iterativní metodu, tj. metodu tvaru
 +
\[ \vec x^{( k + 1 )} = \matice B \vec x^{( k )} + \vec c \]
 +
splňující
 +
\[ \vec x = \matice B \vec x + \vec c \]
 +
a dále splňující pro nějakou maticovou normu
 +
\[ \lVert \matice B \rVert < 1 \]
 +
platí
 +
\[ \left\lVert \vec x^{(k)} - \vec x \right\rVert \leq \lVert \matice B \rVert^k \left( \left\lVert \vec x^{(0)} \right\rVert + \frac{\lVert \vec c \rVert}{1 - \lVert \matice B \rVert} \right) \]
 +
kde používaná vektorová norma je \textbf{souhlasná} s normou maticovou.
 
\begin{proof}
 
\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 \]
+
\[ \vec x^{(k)} = \matice B \vec x^{(k - 1)} + \vec c = \dots = \matice B^k \vec x^{(0)} + \sum_{i = 0}^{k - 1} \matice B^i \vec c \]
 +
Protože \( \lVert \matice B \rVert < 1 \), tak díky \ref{AbsEigenvalueVSNorma} \( \rho ( \matice B ) < 1 \), a tedy \( 0 \notin \sigma ( \matice I - \matice B ) \), tedy \( ( \matice I - \matice B ) \) je regulární a můžeme upravovat
 +
\[ \vec c = ( \matice I - \matice B) \vec x \Rightarrow \vec x = ( \matice I - \matice B )^{-1} \vec c = \sum_{i = 0}^\infty \matice B^i \vec c \]
 +
kde poslední rovnost platí, protože \( \lVert \matice B \rVert < 1 \), a tedy díky \ref{GeomKNorma} řada konverguje.
 +
S pomocí těchto dvou rozvojů můžeme za použití trojúhelníkové nerovnosti a vzorce pro součet geometrické řady odhadovat
 +
\[ \left\lVert \vec x^{(k)} - \vec x \right\rVert = \left\lVert \matice B^k \vec x^{(0)} + \sum_{i = 0}^{k - 1} \matice B^i \vec c - \sum_{i = 0}^\infty \matice B^i \vec c \right\rVert = \left\lVert \matice B^k \vec x^{(0)} - \sum_{i = k}^\infty \matice B^i \vec c \right\rVert = \left\lVert \matice B^k \left( \vec x^{(0)} - \sum_{i = 0}^\infty \matice B^i \vec c \right) \right\rVert \leq \]
 +
\[ \leq \lVert \matice B \rVert^k \left\lVert \vec x^{(0)} - \sum_{i = 0}^\infty \matice B^i \vec c \right\rVert \leq \lVert \matice B \rVert^k \left( \left\lVert \vec x^{(0)} \right\rVert + \sum_{i = 0}^\infty \lVert \matice B \rVert^i \lVert \vec c \rVert \right) = \lVert \matice B \rVert^k \left( \left\lVert \vec x^{(0)} \right\rVert + \frac{\lVert \vec c \rVert}{1 - \lVert \matice B \rVert} \right) \]
 
\end{proof}
 
\end{proof}
 
\end{theorem}
 
\end{theorem}
 +
 +
\subsection{Metoda postupných aproximací}
 +
Využijeme znalosti rezidua v \( k \)-té iteraci a definujeme
 +
\[ \vec x^{( k + 1 )} = \vec x^{( k )} - \vec r^{( k )} = \vec x^{( k )} - \matice A \vec x^{( k )} + \vec b = ( \matice I - \matice A ) \vec x^{( k )} + \vec b \]
 +
Vidíme, že tato metoda obecně splňuje podmínku
 +
\[ \vec x = ( \matice I - \matice A ) \vec x + \vec b \]
  
 
\begin{theorem}
 
\begin{theorem}
−
\label{HouseholderEigenvalue}
+
\label{KPostupneAproximace}
−
Nechť \(\lambda\) je vlastní číslo matice \(\matice A\), pak existuje Householderova matice \(\matice H(\vec w)\) taková, že
+
Metoda postupných aproximací pro soustavu lineárních rovnic \( \matice A \vec x = \vec b \), kde matice \( \matice A \) je regulární, tj. metoda tvaru
−
\[\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\).
+
\[ \vec x^{(k + 1)} = ( \matice I - \matice A ) \vec x^{(k)} + \vec b \]
 +
konverguje pro libovolné \( \vec x^{(0)} \) k \( \vec x \) právě tehdy, když
 +
\[ \rho ( \matice I - \matice A ) < 1 \]
 
\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} \]
+
Plyne z \ref{KStacionarniIterativniMetodySpektrum}.
−
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{proof}
 
\end{theorem}
 
\end{theorem}
  
 
\begin{remark*}
 
\begin{remark*}
−
\(\matice M \vec e^{(1)} = \lambda \vec e^{(1)} \Rightarrow \matice M = \begin{pmatrix}
+
Díky \ref{AbsEigenvalueVSNorma} je postačující podmínkou konvergence metody postupných aproximací existence nějaké normy, pro kterou
−
\lambda & \multirow{4}{*}{\text{\Huge ?}} \\
+
\[ \lVert \matice I - \matice A \rVert < 1 \]
−
0 & \\
+
−
\vdots & \\
+
−
0 & \\
+
−
\end{pmatrix}\)
+
 
\end{remark*}
 
\end{remark*}
  
−
\begin{remark*}
+
\begin{theorem}
−
\(\matice M = \matice H (\vec w)\matice A \matice H (\vec w)\) je podobnostní transformace.
+
\label{PolynomEigenvalues}
 +
Nechť \( p(t) \) je polynom, \( \matice A \in \mathbbm C^{n, n} \) a \( \lambda \in \sigma ( \matice A ) \). Potom \( p( \lambda ) \in \sigma ( p( \matice A ) ) \).
 +
\begin{proof}
 +
Využijeme vztahu \( \lambda \in \sigma ( \matice A ) \Leftrightarrow ( \matice A - \lambda \matice I ) \) je singulární. Rozepíšeme \( p ( t ) \) do tvaru
 +
\[ p ( t ) = \sum_{i = 0}^n a_i t^i, \; a_n \neq 0 \]
 +
Potom můžeme upravit
 +
\[ p ( \matice A ) - p ( \lambda ) \matice I = \sum_{i = 0}^n a_i \matice A^i - \sum_{i = 0}^n a_i \lambda^i = \sum_{i = 1}^n a_i ( \matice A - \lambda \matice I )^i = ( \matice A - \lambda \matice I ) \sum_{i = 1}^n a_i ( \matice A - \lambda \matice I )^{i - 1} \]
 +
Z čehož plyne, že \( p ( \matice A ) - p ( \lambda ) \matice I \) je sigulární a tedy \( p ( \lambda ) \in \sigma ( p ( \matice A ) ) \).
 +
\end{proof}
 +
\end{theorem}
 +
\begin{remark*}\textit{(Důkaz z přednášky)}
 +
Z \ref{MocninaJordan} víme, že se při mocnění umocňuje spektrum. 
 +
S pomocí Jordanovy věty dále zjistíme, že pro násobení platí:
 +
\[a^k\matice A^k=a^k \matice X^-1\matice J^k \matice X=\matice X^-1 (a\matice J)^k \matice X\]
 +
Obdobně pro sčítání. Z toho je vidět, spektrum součtu matice obsahuje součet vlastních čísel. Složením těchto operací definuje polynom.
 +
Platí tedy \(p(\matice A)=matice X^-1 p(\matice J) \matice X\), což dokazuje větu.
 
\end{remark*}
 
\end{remark*}
  
−
\begin{theorem}[Schurova Věta]
+
\begin{theorem}
−
\label{SchurovaVeta}
+
\label{KHermPDPostupneAproximace}
−
Libovolná matice \(\matice A \in \matice C^{n,n} \) se dá zapsat jako \[\matice A = \matice U^* \matice R \matice U \]
+
Nechť matice \( \matice A \) je hermitovská a pozitivně definitní. Pak metoda postupných aproximací pro soustavu lineárních rovnic \( \matice A \vec x = \vec b \) konverguje pro libovolné \( \vec x^{( 0 )} \) k \( \vec x \) právě tehdy, když
−
kde \(\matice U \) je unitární matice a \(\matice R\) je horní trojúhelníková matice.
+
\[ \Theta < \matice A < 2 \matice I \]
−
\begin{remark}
+
−
Vlastní čísla matice \(\matice A \) jsou na diagonále \(\matice R\) díky \ref{PodobneEigenvalue}.
+
−
\end{remark}
+
 
\begin{proof}
 
\begin{proof}
−
Mějme matici \(\matice A\) a předpokládejme podle \(\ref{HouseholderEigenvalue}\), že existuje \(\vec w_1 \in \matice C^{n}\).
+
Díky \ref{KPostupneAproximace} metoda postupných aproximací konverguje právě tehdy, když \( \sigma ( \matice I - \matice A ) \subset \left( -1, 1 \right) \). Hermitovskost matice \( \matice A \) nám zaručuje reálnost vlastních čísel. Vezmeme polynom \( p ( t ) = 1 - t \), tedy \( p ( \matice I - \matice A ) = \matice A \) a užitím \ref{PolynomEigenvalues} dostáváme \( \sigma ( \matice A ) \subset p ( \left( -1 , 1 \right) ) = \left( 0, 2 \right) \), tedy \( \matice A \) je pozitivně definitní.
−
\\\( \matice H (\vec w_1)\matice A \matice H (\vec w_1) = \begin{pmatrix}
+
\\ Vezmeme polynom \( q ( t ) = 1 + t \), tedy \( q ( \matice I - \matice A ) = 2 \matice I - \matice A \) a užitím \ref{PolynomEigenvalues} dostáváme \( \sigma ( 2 \matice I - \matice A ) \subset q ( \left( -1 , 1 \right) ) = \left( 0, 2 \right) \), tedy \( 2 \matice I - \matice A \) je pozitivně definitní. To je jinak zapsáno \( \matice A < 2 \matice I \).
−
\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 trivální), tedy celá matice \(\matice U\) je unitární. Matice \(\matice U^{-1}\) bude mít tvar \(\matice H_1 \matice H_2 ... \matice H_n \) (zřejmé). To už je ekvivalentní s tvrzením věty: \[\matice U^* \matice A \matice U = \matice R \Leftrightarrow \matice A = \matice U^* \matice R \matice U\]
+
 
\end{proof}
 
\end{proof}
 
\end{theorem}
 
\end{theorem}
 +
\begin{remark*}
 +
Nejspíše platí i pro nehermitovské matice. Všechny věty, které jsou v důkazu použité, platí bez ohledu na to, zda jsou vlastní čísla reálná či komplexní, pokud se nahradí interval kruhem v \(\matice C\) obsahujícím daný interval.
 +
\end{remark*}
 +
 +
\subsection{Předpodmíněná metoda postupných aproximací}
 +
Abychom zlepšili konvergenci metody postupných aproximací, vynásobíme soustavu regulární maticí \( \matice H \) a dostáváme
 +
\[ \matice{H A} \vec x = \matice H \vec b \]
 +
Použitím metody postupných aproximací pro tuto soustavu dostáváme
 +
\[ \vec x^{( k + 1 )} = ( \matice I - \matice{H A} ) \vec x^{( k )} + \matice H \vec b \]
 +
Podmínka
 +
\[ \vec x = ( \matice I - \matice{H A} ) \vec x + \matice H \vec b \]
 +
je splněna díky tomu, že je obecně splněná pro metodu postupných aproximací.
  
 +
\setcounter{define}{12}
 
\begin{theorem}
 
\begin{theorem}
−
\label{NormalniTrojuhelnikDiagonalni}
+
\label{KPredpodmineneAproximace}
−
Normální trojúhelníková matice je diagonální.
+
Předpodmíněná metoda postupných aproximací s předpodmíněním \( \matice H \) pro soustavu lineárních rovnic \( \matice A \vec x = \vec b \), kde matice \( \matice A \) je regulární, tj. metoda tvaru
 +
\[ \vec x^{( k + 1 )} = ( \matice I - \matice{H A} ) \vec x^{( k )} + \matice H \vec b \]
 +
konverguje pro libovolné \( \vec x^{( 0 )} \) k \( \vec x \) právě tehdy, když
 +
\[ \rho ( \matice I - \matice{H A} ) < 1 \]
 
\begin{proof}
 
\begin{proof}
−
Ukážeme, že \( \matice R \) z \ref{SchurovaVeta} je normální:
+
Plyne z \ref{KStacionarniIterativniMetodySpektrum}.
−
\[ \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 = i}^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{proof}
 +
 
\end{theorem}
 
\end{theorem}
 +
 +
\begin{remark*}
 +
Díky \ref{AbsEigenvalueVSNorma} je postačující podmínkou konvergence předpodmíněné metody postupných aproximací existence nějaké normy, pro kterou
 +
\[ \lVert \matice I - \matice{H A} \rVert < 1 \]
 +
\end{remark*}
  
 
\begin{theorem}
 
\begin{theorem}
−
\label{RozklNormMatice}
+
\label{KHermPDPredpodmineneAproximace}
−
Pro libovolnou normální matici \(\matice A\) existuje unitární matice \(\matice U\) tak, že
+
Nechť matice \( \matice A \) je hermitovská a pozitivně definitní. Pak předpodmíněná metoda postupných aproximací pro soustavu lineárních rovnic \( \matice A \vec x = \vec b \) konverguje pro libovolné \( \vec x^{( 0 )} \) k \( \vec x \) když platí \textbf{postačující podmínka}
−
\[\matice A = \matice {U^*RU}\]
+
\[ \Theta < \matice A <\matice H^{-1} + \left( \matice H^{-1} \right)^* \]
−
kde \(\matice R\) je diagonální. Je-li \(\matice A\) hermitovská, pak \(\matice R\) má na diagonále reálná čísla.
+
Konvergence je navíc monotónní vzhledem k normě \( \lVert \, \cdot \, \rVert_{\matice A} \)
 
\begin{proof}
 
\begin{proof}
−
\begin{enumerate}
+
Chceme dokázat \( \lVert \matice I - \matice{H A} \rVert_{\matice A} < 1 \) a tím splnit předpoklady \ref{KPredpodmineneAproximace} (Energetická norma existuje, protože je \( \matice A \) hermitovská a pozitivně definitní).
−
\item Ukážeme, že \(\matice R\) je normální, pak podle \ref{NormalniTrojuhelnikDiagonalni} bude také diagonální.
+
\[ \lVert \matice I - \matice{H A} \rVert_{\matice A} = \left\lVert \matice A^{\frac{1}{2}} ( \matice I - \matice{H A} ) \matice A^{-\frac{1}{2}} \right\rVert_2 = \left\lVert \matice I - \matice A^{\frac{1}{2}} \matice H \matice A^{\frac{1}{2}} \right\rVert_2 = \lVert \matice B \rVert_2 \]
−
\[\matice A = \matice {U^*RU} \Rightarrow \matice {UA} = \matice {RU} \Rightarrow \matice {UAU^*} = \matice R\]
+
když označíme \( \matice B = \matice I - \matice A^{\frac{1}{2}} \matice H \matice A^{\frac{1}{2}} \). Dále
−
\[\matice R^* = \matice {(UAU^*)^*} = \matice {(AU^*)^*U^*} \matice {UA^*U^*} \]
+
\[ \lVert \matice B \rVert_2 < 1 \Leftrightarrow \lVert \matice B \rVert_2^2 < 1 \]
−
\[\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}\]
+
Využijeme \ref{NormaMatice} a \ref{AbsEigenvalueVSNorma}
−
\(\Rightarrow \matice R \) je normální \(\Rightarrow \matice R\) je diagonální.
+
\[ \lVert \matice B \rVert_2^2 = \rho ( \matice B^* \matice B ) \leq \left\lVert \matice B^* \matice B \right\rVert \]
−
\item \(\matice A\) je hermitovská \(\Rightarrow \matice A\) je normální.
+
pro nějakou normu. Budeme tedy odhadovat ze shora matici \( \matice B^* \matice B \).
−
\[\matice A = \matice {U^*DU} \Rightarrow \matice D = \matice {UAU^*}\]
+
\[ \matice B^* \matice B = ( \matice I - \matice A^{\frac{1}{2}} \matice H \matice A^{\frac{1}{2}} )^* ( \matice I - \matice A^{\frac{1}{2}} \matice H \matice A^{\frac{1}{2}} ) = ( \matice I - \matice A^{\frac{1}{2}} \matice H^* \matice A^{\frac{1}{2}} ) ( \matice I - \matice A^{\frac{1}{2}} \matice H \matice A^{\frac{1}{2}} ) \]
−
kde \(\matice D\) je diagonální matice.
+
kde poslední rovnost plyne z hermitovskosti matice \( \matice A \).
−
\[\matice D^* = \matice {(UAU^*)^*} = \matice {UA^*U^*} \underbrace{\Rightarrow}_{\matice A = \matice A^*} \matice {UAU^*} = D\]
+
\[ ( \matice I - \matice A^{\frac{1}{2}} \matice H^* \matice A^{\frac{1}{2}} ) ( \matice I - \matice A^{\frac{1}{2}} \matice H \matice A^{\frac{1}{2}} ) = \matice I - \matice A^{\frac{1}{2}} ( \matice H^* + \matice H ) \matice A^{\frac{1}{2}} + \matice A^{\frac{1}{2}} \matice H^* \matice A \matice H \matice A^{\frac{1}{2}} \]
−
\[\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
+
Využijeme snadno ověřitelné rovnosti \( \matice H^* ( \matice H^{-1} + \left( \matice H^{-1} \right)^* ) \matice H = \matice H^* + \matice H \) a dostáváme
−
\end{enumerate}
+
\[ \matice I - \matice A^{\frac{1}{2}} ( \matice H^* + \matice H ) \matice A^{\frac{1}{2}} + \matice A^{\frac{1}{2}} \matice H^* \matice A \matice H \matice A^{\frac{1}{2}} = \matice I - \matice A^{\frac{1}{2}} \matice H^* ( \matice H^{-1} + \left( \matice H^{-1} \right)^* ) \matice H \matice A^{\frac{1}{2}} + \matice A^{\frac{1}{2}} \matice H^* \matice A \matice H \matice A^{\frac{1}{2}} =  \]
 +
\[ = \matice I - \matice A^{\frac{1}{2}} \matice H^* ( \underbrace{\matice H^{-1} + \left( \matice H^{-1} \right)^* - \matice A}_{> \Theta} ) \matice H \matice A^{\frac{1}{2}} \]
 +
kde jsme k odhadu využili předpokladů věty. Dále víme, že \( \matice H^* \matice H \) je pozitivně definitní (Ověření: \( \braket{\matice H^* \matice H \vec x | \vec x} = \braket{\matice H \vec x | \matice H \vec x} = \lVert \matice H \vec x \rVert > 0 \)). Protože i \( \matice A \) je pozitivně definitní, můžeme odhadnout
 +
\[ \matice A^{\frac{1}{2}} \matice H^* ( \matice H^{-1} + \left( \matice H^{-1} \right)^* - \matice A ) \matice H \matice A^{\frac{1}{2}} > \Theta \]
 +
A protože i \( \matice B^* \matice B \) je pozitivně definitní, konečně můžeme odhadnout
 +
\[ \matice I - \matice A^{\frac{1}{2}} \matice H^* ( \matice H^{-1} + \left( \matice H^{-1} \right)^* - \matice A ) \matice H \matice A^{\frac{1}{2}} < \matice I \]
 +
Tím jsme naplnili předpoklady \ref{KPredpodmineneAproximace}, a tedy dokázali platnost věty.
 
\end{proof}
 
\end{proof}
 
\end{theorem}
 
\end{theorem}
  
−
\subsection{Rozklady matic - Jordanova Věta}
+
Jak tedy volit matici \( \matice H \)? Pokud bychom volili \( \matice H = \matice A^{-1} \) dostáváme
 +
\[ \vec x^{( k + 1 )} = \left( \matice I - \matice A^{-1} \matice A \right) \vec x^{( k )} + \matice A^{-1} \vec b = \vec x \]
 +
Tedy předpodmíněná metoda postupných aproximací by konvergovala v první iteraci. Avšak výpočet \( \matice A^{-1} \) provádíme Gaussovou eliminační metodou, čemuž jsme se chtěli vyhnout.
 +
\\ Oblíbenou metodou je tzv. \textbf{neúplný LU rozklad}, kde malé prvky zanedbáváme, čímž můžeme zlepšit časovou náročnost.
  
−
\begin{theorem}[Jordan]
+
\subsection{Richardsonovy iterace}
−
\label{JordanovaVeta}
+
Zavedeme tzv. \textbf{relaxační parametr} \( \theta \in \mathbbm C \). Metoda Richardsonových iterací je předpodmíněnou metodou postupných iterací, kde volíme
−
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 H = \theta \matice I \]
−
\[ \matice J =
+
a dostáváme
−
\begin{pmatrix}
+
\[ \vec x^{( k + 1 )} = ( \matice I - \theta \matice A ) + \theta \vec b \]
−
\matice J_1^1 &&&&&&&&&&&&& \\
+
 
−
& \matice J_2^1 &&&&&&&&&&&& \\
+
\setcounter{define}{15}
−
&& \ddots &&&&&&&&&&& \\
+
\begin{theorem}
−
&&& \matice J_{s_1}^1 &&&&&&&&&& \\
+
\label{KHermPDRichardson}
−
&&&& \matice J_1^2 &&&&&&&&& \\
+
Nechť matice \( \matice A \) je hermitovská a pozitivně definitní. Nechť \( \theta \in \mathbbm R \). Pak metoda Richardsonových iterací konverguje pro libovolné \( \vec x^{( 0 )} \) k \( \vec x \) právě tehdy, když
−
&&&&& \matice J_2^2 &&&&&&&& \\
+
\[ \Theta < \matice A < \frac{2}{\theta} \matice I \]
−
&&&&&& \ddots &&&&&&& \\
+
Konvergence je navíc monotónní vzhledem k normě \( \lVert \, \cdot \, \rVert_{\matice A} \)
−
&&&&&&& \matice J_{s_2}^2 &&&&&& \\
+
 
−
&&&&&&&& \matice J_1^3 &&&&& \\
+
\begin{proof}
−
&&&&&&&&& \ddots &&&& \\
+
Pomocí \ref{KHermPDPredpodmineneAproximace} dokážeme, že se jedná o \textbf{postačující podmínku}:
−
&&&&&&&&&& \matice J_1^p &&& \\
+
\todo{Důkaz nutnosti podmínky od doc. Humhala}
−
&&&&&&&&&&& \matice J_2^p && \\
+
\[ \matice H^{-1} + \left( \matice H^{-1} \right)^* = \frac{1}{\theta} \matice I + \left( \frac{1}{\theta} \matice I \right)^* = \frac{2}{\theta} \matice I \]
−
&&&&&&&&&&&& \ddots & \\
+
−
&&&&&&&&&&&&& \matice J_{s_p}^p \\
+
−
\end{pmatrix} \]
+
−
kde:
+
−
\[ \matice J_i^k =
+
−
\begin{pmatrix}
+
−
\lambda_k &&& \\
+
−
1 & \lambda_k && \\
+
−
& \ddots & \ddots & \\
+
−
&& 1 & \lambda_k \\
+
−
\end{pmatrix}, \;
+
−
\forall k \in \hat p, \forall i \in \hat{s_k} \]
+
−
Matice \( \matice J \) je až na pořadí bloků dána jednoznačně.
+
−
\begin{proof}\renewcommand{\qedsymbol}{}
+
−
Bez důkazu.
+
 
\end{proof}
 
\end{proof}
 
\end{theorem}
 
\end{theorem}
  
−
\subsection{Vlastní čísla matice}
+
\subsection{Jacobiho metoda}
 +
Vyjdeme ze vzorce pro výpočet složek násobku matice a vektoru, tj.
 +
\[ \left( \matice A \vec y \right)_i = \sum_{j = 1}^n \matice A_{ij} \vec y_j \]
 +
Budeme chtít, aby když z vektoru \( \vec x^{( k )} \) nahradíme \( i \)-tou složku \( i \)-tou složkou vektoru \( \vec x^{( k + 1 )} \), byla splněna \( i \)-tá rovnice soustavy, tj.
 +
\[ \sum_{\substack{j = 1 \\ j \neq i}}^n \matice A_{ij} \vec x_j^{( k )} + \matice A_{ii} \vec x_i^{( k + 1 )} = \vec b_i \]
 +
Tedy dostáváme
 +
\[ \vec x_i^{( k + 1 )} = \frac{\vec b_i - \sum_{j = 1, j \neq i}^n \matice A_{ij} \vec x_j^{( k )}}{\matice A_{ii}} \]
 +
Z posledního předpisu je vidět, že musíme předpokládat nenulovou diagonálu. Toho však lze u regulární matice dosáhnout přerovnáním.
  
−
\setcounter{define}{43}
+
\subsection{Jacobiho metoda - numerická analýza}
 +
Rozepíšeme matici \( \matice A \) do tvaru
 +
\[ \matice A = \matice D - \matice L - \matice R \]
 +
kde
 +
\begin{itemize}
 +
\item \( \matice D \) je diagonální matice s diagonálou matice \( \matice A \)
 +
\item \( \matice L \) je dolní trojúhelníková matice s prvky pod diagonálou \( \matice A \), vynásobenými \( ( - 1 ) \)
 +
\item \( \matice R \) je horní trojúhelníková matice s prvky nad diagonálou \( \matice A \), vynásobenými \( ( - 1 ) \)
 +
\end{itemize}
 +
Můžeme tedy shrnout předpis pro prvky \( \vec x^{( k + 1 )} \) do jednoho vztahu
 +
\[ \vec x^{( k + 1 )} = \matice D^{-1} \left( \vec b + ( \matice L + \matice R ) \vec x^{( k )} \right) = \matice D^{-1} \vec b + \matice D^{-1} ( \matice D - \matice A ) \vec x^{( k )} = \left( \matice I - \matice D^{-1} \matice A \right) \vec x^{( k )} + \matice D^{-1} \vec b \]
 +
Zjišťujeme, že Jacobiho metoda je vlastně předpodmíněnou metodou postupných aproximací, kde volíme
 +
\[ \matice H = \matice D^{-1}\]
 +
\[\vec c = \matice D^{-1} \vec b \]
 +
 
 +
\setcounter{define}{17}
 
\begin{theorem}
 
\begin{theorem}
−
\label{PodobneEigenvalue}
+
\label{KJacobi}
−
Podobné matice \( \matice A \) a \( \matice B \) mají stejná vlastní čísla se stejnou geometrickou násobností.
+
Jacobiho metoda pro soustavu lineárních rovnic \( \matice A \vec x = \vec b \) konverguje pro libovolné \( \vec x^{( 0 )} \) k \( \vec x \) právě tehdy, když
 +
\[ \rho \left( \matice D^{-1} ( \matice L + \matice R ) \right) < 1 \]
 
\begin{proof}
 
\begin{proof}
−
Díky podobnosti existuje taková matice \( \matice T \), že \( \matice A = \matice T^{-1} \matice{B T} \). Dále rozložíme \( \matice B \) podle \ref{JordanovaVeta} a označíme \( \matice B = \matice K^{-1} \matice{JK} \), kde \( \matice J \) je Jordanova matice. Pak platí:
+
Díky vztahu \( \matice A = \matice D - \matice L - \matice R \) můžeme upravit
−
\[ \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} ) \]
+
\[ \rho \left( \matice D^{-1} ( \matice L + \matice R ) \right) = \rho \left( \matice D^{-1} ( \matice D - \matice A ) \right) = \rho \left( \matice I - \matice D^{-1} \matice A \right) < 1 \]
−
což je podobnostní transformace a z čehož díky podmínce jednoznačnosti v \ref{JordanovaVeta} plyne, že matice \( \matice J \) je Jordanovou maticí k matici \( \matice A \). Z definice Jordanovy matice pak plyne tvrzení věty.
+
čímž jsou splněny předpoklady \ref{KPredpodmineneAproximace}.
 
\end{proof}
 
\end{proof}
 
\end{theorem}
 
\end{theorem}
  
−
\subsection{Pozitivně definitní matice}
+
\begin{remark*}
 +
Díky \ref{AbsEigenvalueVSNorma} je postačující podmínkou konvergence Jacobiho metody existence nějaké normy, pro kterou
 +
\[ \left\lVert \matice D^{-1} ( \matice L + \matice R ) \right\rVert < 1 \]
 +
\end{remark*}
  
 
\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^+\]
+
\label{PrevladajiciDiagonala}
−
značíme \(\matice A > 0\).
+
Pokud pro matici \( \matice A \in \mathbbm C^{n, n} \) platí
−
Platí-li pro \(\matice B \in \matice T^{n, n} \) vztah \( \matice A - \matice B > 0 \), pak píšeme \(\matice A > \matice B \).
+
\[ \sum_{\substack{j = 1 \\ j \neq i}}^n \lvert \matice A_{ij} \rvert < \lvert \matice A_{ii} \rvert \]
 +
Nazýváme ji maticí s převládající diagonálou.
 
\end{define}
 
\end{define}
  
 
\begin{theorem}
 
\begin{theorem}
−
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í.
+
\label{KDiagJacobi}
 +
Nechť má matice \( \matice A \) převládající diagonálu. Pak Jacobiho metoda pro soustavu lineárních rovnic \( \matice A \vec x = \vec b \) konverguje pro libovolné \( \vec x^{( 0 )} \) k \( \vec x \).
 
\begin{proof}
 
\begin{proof}
−
\begin{itemize}
+
Chceme ukázat \( \lVert \matice D^{-1} ( \matice L + \matice R ) \rVert_\infty = \lVert \matice D^{-1} ( \matice D - \matice A ) \rVert_\infty = \lVert \matice I - \matice D^{-1} \matice A \rVert_\infty < 1 \) a využít \ref{KJacobi}. Matice \( \matice D \) je diagonální a na její diagonále jsou prvky diagonály matice \( \matice A \). Proto pro prvky matice \( \matice D^{-1} \matice A \) platí
−
\item Nechť \(\lambda\) vlastní číslo \(\matice A\) a \(\vec x\) příslušný vlastní vektor.
+
\[ \left( \matice D^{-1} \matice A \right)_{ij} = \frac{\matice A_{ij}}{\matice A_{ii}} \]
−
\[\braket{\matice A \vec x| \vec x} = \braket{\lambda \vec x|\vec x} = \lambda \lVert \vec x \rVert ^2_2 > 0 \Rightarrow \lambda > 0\]
+
A tedy na diagonále \( \matice D^{-1} \matice A \) jsou jedničky. Proto
−
\item Podle \ref{SchurovaVeta} \(\matice A = \matice{U^* D U}\) kde \(\matice D > 0 \). Vezmu tedy libovolný vektor \(\vec c \neq \vec 0\) a vektor \(\vec y = \matice U \vec x \Rightarrow \vec y \neq \vec 0\)
+
\[ \left( \matice I - \matice D^{-1} \matice A \right)_{ij} =
−
\[\braket{\matice A \vec x|\vec x} = \braket{\matice{U^*DU}\vec x|\vec x} = \braket{\matice {DU}\vec x|\matice U\vec x} = \braket{\matice D \vec y|\vec y}=\vec y^*\matice D\vec y > 0 \Rightarrow \matice D > 0\]
+
\begin{cases}
−
\end{itemize}
+
0, & i =j \\
 +
\frac{\matice A_{ij}}{\matice A_{ii}}, & i \neq j
 +
\end{cases}
 +
\]
 +
Díky \ref{NormaMatice} platí
 +
\[ \lVert \matice I - \matice D^{-1} \matice A \rVert_\infty = \max_{i \in \hat n} \sum_{j = 1}^n \left\lvert \left( \matice I - \matice D^{-1} \matice A \right)_{ij} \right\rvert = \max_{i \in \hat n} \frac{1}{\matice A_{ii}} \sum_{\substack{j = 1 \\ j \neq i}}^n \lvert \matice A_{ij} \rvert < 1 \]
 +
kde poslední nerovnost je důsledkem toho, že matice \( \matice A \) má převládající diagonálu.
 
\end{proof}
 
\end{proof}
 
\end{theorem}
 
\end{theorem}
  
−
\subsection{Normy}
 
−
 
−
\setcounter{define}{52}
 
 
\begin{theorem}
 
\begin{theorem}
−
\label{NormySendvic}
+
\label{KHermPDJacobi}
−
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í:
+
Nechť je matice \( \matice A \) hermitovská a pozivně definitní. Pak Jacobiho metoda pro soustavu lineárních rovnic \( \matice A \vec x = \vec b \) konverguje pro libovolné \( \vec x^{( 0 )} \) k \( \vec x \) právě tehdy, když
−
\[ \gamma_1 \lVert \vec x \rVert_1 \leq \lVert \vec x \rVert_2 \leq \gamma_2 \lVert \vec x \rVert_1 \]
+
\[ \Theta < \matice A < 2 \matice D \]
−
\begin{proof}\renewcommand{\qedsymbol}{}
+
Konvergence je navíc monotónní vzhledem k normě \( \lVert \, \cdot \, \rVert_{\matice A} \)
−
Bez důkazu, pro zájemce viz Turistický průvodce matematickou analýzou 3, Věta {\color{red} 6.7}
+
\begin{proof}
 +
Protože je matice \( \matice A \) hermitovská, jsou diagonální prvky \( \matice A_{ii} \in \mathbbm R \) (musí platit \( \matice A_{ii} = \overline{\matice A_{ii}} \)), tudíž \( \matice D = \matice D^* \). Protože je navíc pozitivné definitní, platí \( \vec x^* \matice A \vec x > 0 \). Zvolíme–li \(\vec x = \vec e_{(i)} \), kde \( \vec e_{(i)} \) jsou vektory ze standardní báze, dostaneme \( \matice A_{ii} = \matice D_{ii} = \vec e_{(i)}^* \matice A \vec e_{(i)} > 0 \), tj. \(\matice D \) je pozitivně definitní.
 +
\begin{enumerate}
 +
\item[( \( \Leftarrow \) )] Upravíme předpis Jacobiho metody do tvaru
 +
\[ \vec x^{( k + 1 )} = ( \matice I - \matice D^{-1} \matice A ) \vec x^{( k + 1 )} + \matice D^{-1} \vec b \]
 +
což je předpis předpodmíněné metody postupných aproximací s předpodmíněním \( \matice H = \matice D^{-1} \). Dále tedy platí
 +
\[ \matice H^{-1} + \left( \matice H^{-1} \right)^* = \matice D + \matice D^* = 2 \matice D \]
 +
čímž jsou splněny předpoklady \ref{KHermPDPredpodmineneAproximace}.
 +
\item[( \( \Rightarrow \) )] Díky \ref{KStacionarniIterativniMetodySpektrum} víme, že \( \sigma ( \matice I - \matice D^{-1} \matice A ) \subset \left( -1, 1 \right) \). Užitím \ref{PolynomEigenvalues} s \( p ( t ) = 1 + t \) dostáváme \( \sigma ( 2 \matice I - \matice D^{-1} \matice A ) \subset \left( 0, 2 \right) \). Můžeme upravit
 +
\[ 2 \matice I - \matice D^{-1} \matice A = \matice D^{-\frac{1}{2}} ( 2 \matice I - \matice D^{-\frac{1}{2}} \matice A \matice D^{-\frac{1}{2}} ) \matice D^{\frac{1}{2}} \]
 +
Z čehož plyne, že je matice \( 2 \matice I - \matice D^{-\frac{1}{2}} \matice A \matice D^{-\frac{1}{2}} \) pozitivně definitní. Toho využijeme při odhadu
 +
\[ \braket{( 2 \matice D - \matice A ) \vec x | \vec x} = \vec x ( 2 \matice D - \matice A ) \vec x = \vec x \matice D^{\frac{1}{2}} \matice D^{-\frac{1}{2}} ( 2 \matice D - \matice A ) \matice D^{-\frac{1}{2}} \matice D^{\frac{1}{2}} \vec x = \left( \matice D^{\frac{1}{2}} \vec x \right)^* \left( 2 \matice I - \matice D^{-\frac{1}{2}} \matice A \matice D^{-\frac{1}{2}} \right) \left( \matice D^{\frac{1}{2}} \vec x \right) = \]
 +
\[ = \braket{\left( 2 \matice I - \matice D^{-\frac{1}{2}} \matice A \matice D^{-\frac{1}{2}} \right) \matice D^{\frac{1}{2}} \vec x | \matice D^{\frac{1}{2}} \vec x} > 0 \]
 +
Tedy \( 2 \matice D - \matice A > \Theta \), což je jinak zapsáno \( 2 \matice D > \matice A \).
 +
\end{enumerate}
 
\end{proof}
 
\end{proof}
 
\end{theorem}
 
\end{theorem}
  
 +
\subsection{Gaussova-Seidelova metoda}
 +
Vyjdeme ze stejného vztahu jako v případě Jacobiho metody, avšak použijeme již napočítané složky vektoru \( \vec x^{( k + 1 )} \), tedy
 +
\[ \sum_{j = 1}^i \matice A_{ij} \vec x_j^{( k + 1 )} + \sum_{j = i + 1}^n \matice A_{ij} \vec x_j^{( k )} = \vec b_i \]
 +
Tedy dostáváme
 +
\[ \vec x_i^{( k + 1 )} = \frac{\vec b_i - \sum_{j = 1}^{i - 1} \matice A_{ij} \vec x_j^{( k + 1 )} - \sum_{j = i + 1}^n \matice A_{ij} \vec x_j^{( k )}}{\matice A_{ii}} \]
 +
Znovu musíme předpokládat nenulovou diagonálu.
 +
 +
\subsection{Gaussova-Seidelova metoda - numerická analýza}
 +
Použijeme stejného přepisu matice \( \matice A \) jako v případě Jacobiho metody a shrneme předpis pro prvky \( \vec x^{( k + 1 )} \) do jednoho vztahu
 +
\[ \vec x^{( k + 1 )} = \matice D^{-1} \left( \vec b + \matice L \vec x^{( k + 1 )} + \matice R \vec x^{( k )} \right) \]
 +
který upravujeme
 +
\[ \matice D \vec x^{( k + 1 )} - \matice L \vec x^{( k + 1 )} = \vec b + \matice R \vec x^{( k )} \]
 +
\[ \vec x^{( k + 1 )} = ( \matice D - \matice L )^{-1} ( \matice D - \matice L - \matice A ) \vec x^{( k )} + ( \matice D - \matice L )^{-1} \vec b \]
 +
\[ \vec x^{( k + 1 )} = \left( \matice I - ( \matice D - \matice L )^{-1} \matice A \right) \vec x^{( k )} + ( \matice D - \matice L )^{-1} \vec b \]
 +
Zjišťujeme, že Gaussova-Seidelova metoda je vlastně předpodmíněnou metodou postupných aproximací, kde volíme
 +
\[ \matice H = ( \matice D - \matice L )^{-1} \]
 +
 +
\setcounter{define}{22}
 
\begin{theorem}
 
\begin{theorem}
−
\label{KonvergenceVNorme}
+
\label{KGaussSeidel}
−
Nechť \( \left\{ \vec x^{(k)} \right\}_{k = 1}^\infty \) je posloupnost vektorů z \( \mathbbm C^{n} \) a \( \lVert \, \cdot \, \rVert \) libovolná norma. Potom
+
Gaussova-Seidelova metoda pro soustavu lineárních rovnic \( \matice A \vec x = \vec b \) konverguje pro libovolné \( \vec x^{( 0 )} \) k \( \vec x \) právě tehdy, když
−
\[ \vec x^{(k)} \rightarrow \vec x \Leftrightarrow \lVert \vec x^{(k)} - \vec x \rVert \rightarrow 0 \]
+
\[ \rho \left( ( \matice D - \matice L )^{-1} \matice R \right) < 1 \]
 
\begin{proof}
 
\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.
+
Upravíme předpis Gaussovy-Seidelovy metody do tvaru
−
\\ (\( \Leftarrow \))
+
\[ \vec x^{( k + 1 )} = ( \matice I - \left( \matice D - \matice L \right)^{-1} \matice A ) \vec x^{( k )} + \left( \matice D - \matice L \right)^{-1} \vec b \]
−
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 \)
+
což je předpis předpodmíněné metody postupných aproximací s předpodmíněním \( \matice H = \left( \matice D - \matice L \right)^{-1} \). Díky vztahu \( \matice A = \matice D - \matice L - \matice R \) můžeme upravit
 +
\[ \rho \left( \left( \matice D - \matice L \right)^{-1} \matice R \right) = \rho \left( \left( \matice D - \matice L \right)^{-1} ( \matice D - \matice L - \matice A ) \right) = \rho \left( \matice I - \left( \matice D - \matice L \right)^{-1} \matice A \right) < 1 \]
 +
čímž jsou splněny předpoklady \ref{KPredpodmineneAproximace}.
 
\end{proof}
 
\end{proof}
 
\end{theorem}
 
\end{theorem}
  
−
\setcounter{define}{59}
+
\begin{remark*}
 +
Díky \ref{AbsEigenvalueVSNorma} je postačující podmínkou konvergence Gaussovy-Seidelovy metody existence nějaké normy, pro kterou
 +
\[ \left\lVert ( \matice D - \matice L )^{-1} \matice R \right\rVert < 1 \]
 +
\end{remark*}
 +
 
 
\begin{theorem}
 
\begin{theorem}
−
\label{NormaMatice}
+
\label{KDiagGaussSeidel}
−
Při značení:
+
Nechť má matice \( \matice A \) převládající diagonálu. Pak Gaussova-Seidelova metoda pro soustavu lineárních rovnic \( \matice A \vec x = \vec b \) konverguje pro libovolné \( \vec x^{( 0 )} \) k \( \vec x \).
−
\[ \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{proof}
−
\begin{enumerate}[(1)]
+
Označíme \( \matice B = \left( \matice D - \matice L \right)^{-1} \matice R \). Chceme ukázat \( \lVert \matice B \rVert_\infty < 1 \) a využít \ref{KGaussSeidel}. Díky \ref{NormaMatice} platí
−
\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 \)
+
\[ \lVert \matice B \rVert_\infty = \max_{\lVert \vec x \rVert_\infty = 1} \lVert \matice B \vec x \rVert_\infty \]
−
\\ 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 \).
+
Označíme tento maximální vektor \( \vec u \) ( \( \lVert \vec u \rVert_\infty = 1 \) ) a dále označíme \( \vec v = \matice B \vec u \). Potom platí
−
\begin{remark*}
+
\[ \lVert \matice B \rVert_\infty = \lVert \matice B \vec u \rVert_\infty = \lVert \vec v \rVert_\infty = \max_{k \in \hat n} \lvert \vec v_k \rvert \]
−
Hledáme maxima přes řádky, maximové normě pro matice se tedy říká také řádková norma.
+
Označíme takovouto maximální složku indexem \( i \). Upravíme rovnici \( \matice B \vec u = \vec v \) do tvaru
−
\end{remark*}
+
\[ \left( \matice D - \matice L \right)^{-1} \matice R \vec u = \vec v \]
−
\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 \)
+
\[ \matice R \vec u = ( \matice D - \matice L ) \vec v \]
−
\\ 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.
+
a budeme upravovat její \( i \)-tou (maximální) složku:
−
\begin{remark*}
+
\[ \sum_{j = i + 1}^n -\matice A_{ij} \vec u_j = \sum_{j = 1}^i \matice A_{ij} \vec v_j \]
−
Hledáme maxima přes sloupce, normě se tedy říká sloupcová.
+
Upravíme a díky trojúhelníkové nerovnosti odhadujeme
−
\end{remark*}
+
\[ \lvert \vec v_i \rvert = \left\lvert \frac{1}{\matice A_{ii}} \left( \sum_{j = i + 1}^n - \matice A_{ij} \vec u_j - \sum_{j = 1}^{i - 1} \matice A_{ij} \vec v_j \right) \right\rvert \leq \frac{1}{\lvert \matice A_{ii} \rvert} \left( \sum_{j = i + 1}^n \lvert \matice A_{ij} \rvert \lvert \vec u_j \rvert + \sum_{j = 1}^{i - 1} \lvert \matice A_{ij} \rvert \lvert \vec v_j \rvert \right) \]
−
\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} )} \)
+
Využijeme vlastností \( \lvert \vec u_j \rvert \leq 1 \) a \( \lvert \vec v_j \rvert \leq \lvert \vec v_i \rvert \):
−
\[ \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} \]
+
\[ \frac{1}{\lvert \matice A_{ii} \rvert} \left( \sum_{j = i + 1}^n \lvert \matice A_{ij} \rvert \lvert \vec u_j \rvert + \sum_{j = 1}^{i - 1} \lvert \matice A_{ij} \rvert \lvert \vec v_j \rvert \right) \leq \frac{1}{\lvert \matice A_{ii} \rvert} \left( \sum_{j = i + 1}^n \lvert \matice A_{ij} \rvert + \lvert \vec v_i \rvert \sum_{j = 1}^{i - 1} \lvert \matice A_{ij} \rvert \right) = \sum_{j = i + 1}^n \frac{\lvert \matice A_{ij} \rvert}{\lvert \matice A_{ii} \rvert} + \lvert \vec v_i \rvert \sum_{j = 1}^{i - 1} \frac{\lvert \matice A_{ij} \rvert}{\lvert \matice A_{ii} \rvert} \]
−
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} \)
+
Označíme \( a = \sum_{j = i + 1}^n \frac{\lvert \matice A_{ij} \rvert}{\lvert \matice A_{ii} \rvert} \) a \( b = \sum_{j = 1}^{i - 1} \frac{\lvert \matice A_{ij} \rvert}{\lvert \matice A_{ii} \rvert} \) a máme nerovnost
−
\[\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} \]
+
\[ \lvert \vec v_i \rvert \leq a + b \lvert \vec v_i \rvert \]
−
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} \)
+
Zároveň ale díky tomu, že matice \( \matice A \) má převládající diagonálu, platí \( a + b < 1 \) a konečně můžeme odhadovat
−
\[ \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\]
+
\[ \lvert \vec v_i \rvert \leq \frac{a}{1 - b} < \frac{a}{a + b - b} = 1 \]
−
\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\) unitární, pak \(\lVert \matice A \rVert _2 = 1\) \qedhere
+
−
\end{remark*}
+
−
\end{enumerate}
+
 
\end{proof}
 
\end{proof}
 
\end{theorem}
 
\end{theorem}
  
−
\subsection{Konvergence geometrické posloupnosti matic}
+
\begin{theorem}
−
 
+
\label{KHermPDGaussSeidel}
−
\begin{lemma*}
+
Nechť je matice \( \matice A \) hermitovská a pozivně definitní. Pak Gaussova-Seidelova metoda pro soustavu lineárních rovnic \( \matice A \vec x = \vec b \) konverguje pro libovolné \( \vec x^{( 0 )} \) k \( \vec x \). Konvergence je navíc monotónní vzhledem k normě \( \lVert \, \cdot \, \rVert_{\matice A} \)
−
Nechť \( \matice J \in \mathbbm C^{n, n} \) je Jordanovou maticí z rozkladu \ref{JordanovaVeta}. 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}
 
\begin{proof}
−
Indukcí podle \( k \)
+
Upravíme předpis Gaussovy-Seidelovy metody do tvaru
−
\begin{itemize}
+
\[ \vec x^{( k + 1 )} = ( \matice I - \left( \matice D - \matice L \right)^{-1} \matice A ) \vec x^{( k )} + \left( \matice D - \matice L \right)^{-1} \vec b \]
−
\item \( k = 1 \)
+
což je předpis předpodmíněné metody postupných aproximací s předpodmíněním \( \matice H = \left( \matice D - \matice L \right)^{-1} \). Díky hermitovskosti matice \( \matice A \) platí \( \matice L^* = \matice R \) a \( \matice D^* = \matice D \).  Potom můžeme využít \ref{KHermPDPredpodmineneAproximace} protože platí
−
\\ Plyne přímo z \ref{JordanovaVeta}.
+
\[ \matice H^{-1} + \left( \matice H^{-1} \right)^* = \matice D - \matice L + ( \matice D - \matice L )^* = \matice D - \matice L + \matice D - \matice R = \matice D + \matice A > \matice A \]
−
\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{proof}
−
\end{lemma*}
+
\end{theorem}
 +
 
 +
\subsection{Super-relaxační metoda (SOR – Succesive Over Relaxation)}
 +
Upravíme předpis pro Gaussovu-Seidelovu metodu do tvaru
 +
\[ \vec x_i^{( k + 1 )} = \vec x_i^{( k )} + \Delta \vec x_i^{( k )} \]
 +
Zavedeme tzv. \textbf{relaxační parametr} \( \omega \) a pozměníme předpis pro Gaussovu-Seidelovu metodu na
 +
\[ \vec x_i^{( k + 1 )} = \vec x_i^{( k )} + \omega \Delta \vec x_i^{( k )} \]
 +
Vidíme, že pro \( \omega = 1 \) super-relaxační metoda přechází v metodu Gaussovu-Seidelovu.
 +
 
 +
\begin{remark*}
 +
Obdobnou modifikaci můžeme provést i pro Jacobiho metodu i pro Richardsonovy iterace.
 +
\end{remark*}
 +
 
 +
\subsection{Super-relaxační metoda - numerická analýza}
 +
Vyjádříme po složky vektoru \( \Delta \vec x^{( k )} \) z Gaussovy-Seidelovy metody jako
 +
\[ \Delta \vec x_i^{( k )} = \vec x_i^{( k + 1 )} - \vec x_i^{( k )} = \frac{\vec b_i - \sum_{j = 1}^{i - 1} \matice A_{ij} \vec x_j^{( k + 1 )} - \sum_{j = i + 1}^n \matice A_{ij} \vec x_j^{( k )}}{\matice A_{ii}} - \vec x_i^{( k )} = \frac{\vec b_i - \sum_{j = 1}^{i - 1} \matice A_{ij} \vec x_j^{( k + 1 )} - \sum_{j = i}^n \matice A_{ij} \vec x_j^{( k )}}{\matice A_{ii}} \]
 +
Nyní tento vztah použijeme pro super-relaxační metodu
 +
\[ \vec x_i^{( k + 1 )} = \vec x_i^{( k )} + \frac{\omega}{\matice A_{ii}} \left( \vec b_i - \sum_{j = 1}^{i - 1} \matice A_{ij} \vec x_j^{( k + 1 )} - \sum_{j = i}^n \matice A_{ij} \vec x_j^{( k )} \right) \]
 +
Použijeme stejného přepisu matice \( \matice A \) jako v případě Jacobiho metody a shrneme předpis pro prvky \( \vec x^{( k + 1 )} \) do jednoho vztahu
 +
\[ \vec x^{( k + 1 )} = \vec x^{( k )} + \omega \matice D^{-1} \left( \vec b + \matice L \vec x^{( k + 1 )} + ( \matice R - \matice D ) \vec x^{( k )} \right) \]
 +
který upravujeme
 +
\[ \matice D \vec x^{( k + 1 )} - \omega \matice L \vec x^{( k + 1 )} = ( \matice D - \omega ( \matice D - \matice R ) ) \vec x^{( k )} + \omega \vec b \]
 +
\[ \vec x^{( k+1 )} = ( \matice D - \omega \matice L )^{-1} ( \matice D - \omega ( \matice A + \matice L ) ) \vec x^{( k )} + \omega ( \matice D - \omega \matice L )^{-1} \vec b \]
 +
\[ \vec x^{( k+1 )} = \left( \matice I - \omega ( \matice D - \omega \matice L )^{-1} \matice A \right) \vec x^{( k )} + \omega ( \matice D - \omega \matice L )^{-1} \vec b \]
 +
Zjišťujeme, že super-relaxační metoda je vlastně předpodmíněnou metodou postupných aproximací, kde volíme
 +
\[ \matice H = \omega ( \matice D - \omega \matice L )^{-1} \]
  
−
\setcounter{define}{62}
+
\setcounter{define}{27}
 
\begin{theorem}
 
\begin{theorem}
−
\label{GeomKSpektrum}
+
\label{KSOR}
−
Nechť \( \matice A \in \mathbbm C^{n, n} \). Potom platí
+
Super-relaxační metoda pro soustavu lineárních rovnic \( \matice A \vec x = \vec b \) konverguje pro libovolné \( \vec x^{( 0 )} \) k \( \vec x \) právě tehdy, když
−
\[ \matice A^k \rightarrow \Theta \Leftrightarrow \rho ( \matice A ) < 1 \]
+
\[ \rho \left( \matice B_\omega \right) < 1 \]
 +
kde jsem označili \[B_\omega = \matice I - \omega ( \matice D - \omega \matice L )^{-1} \matice A \]
 
\begin{proof}
 
\begin{proof}
−
Podle \ref{JordanovaVeta} rozložíme \( \matice A = \matice T^{-1} \matice{J T} \) a 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 \).
+
Plyne z \ref{KStacionarniIterativniMetodySpektrum}.
 
\end{proof}
 
\end{proof}
 
\end{theorem}
 
\end{theorem}
 +
 +
\begin{remark*}
 +
Díky \ref{AbsEigenvalueVSNorma} je postačující podmínkou konvergence super-relaxační metody existence nějaké normy, pro kterou
 +
\[ \left\lVert \matice B_\omega \right\rVert < 1 \]
 +
\end{remark*}
  
 
\begin{theorem}
 
\begin{theorem}
−
\label{GeomKNorma}
+
\label{NKSOR}
−
Nechť \( \matice A \in \mathbbm C^{n, n} \). Potom platí
+
Pro každé \( \omega \in \mathbbm R \) platí
−
\[ \exists \; \text{maticová norma} \; \lVert \, \cdot \, \rVert, \lVert \matice A \rVert < 1 \Rightarrow \matice A^k \rightarrow \Theta \]
+
\[ \lvert \omega - 1 \rvert \leq \rho \left( \matice B_\omega \right) \]
 +
a tedy super-relaxační metoda nemůže konvergovat pro \( \omega \in \mathbbm R \setminus \langle 0 , 2 \rangle  \)
 
\begin{proof}
 
\begin{proof}
−
Z \( \lVert \matice A \rVert < 1 \) plyne:
+
Pro důkaz využijeme toho, že determinant nezávisí na volbě báze. Podle označení je \[\matice B_\omega = (\matice D - \omega \matice L)^{-1}\big[(1-\omega)\matice D + \omega \matice R\big] \]
−
\[ \lVert \matice A^k \rVert \leq \lVert \matice A \rVert^k < 1^k \Rightarrow \lVert \matice A^k \rVert \rightarrow 0 \Rightarrow \matice A^k \rightarrow \Theta \]
+
Z Jordanovy věty zároveň víme: \[\matice A = (\matice T)^{-1} \matice {JT} \Rightarrow \det(\matice A) = \det(\matice J) = \prod_{i=1}^n \lambda_i\]
 +
Aplikujeme tuto znalost na naši matici (členy determinantu za \(\matice L\) a \(\matice R\) vypadnou, neboť jsou to singulární matice:
 +
\[\det(\matice B_{\omega}) = \frac{1}{\prod_{i=1}^n \matice A_{ii}} \prod_{i=1}^n (1-\omega) \matice A_{ii}} = (1-\omega)^n = \prod_{i=1}^n \lambda_i\]
 +
Kde poslední rovnost plyne z Jordanovy věty a rozpisu nahoře. V absolutních hodnotách tedy máme: \[\lvert 1-\omega\rvert^n = \prod_{i=1}^n \lvert \lambda_i \rvert\]
 +
Pak je splněno buď I) všechna \( \lambda_i \) jsou stejná, tj, \(\lvert 1-\omega\rvert^n = \lvert \lambda_i \rvert^n \) a tedy nastává rovnost \(\rho (\matice B_{\omega}) = \lvert \lambda_i \rvert \)
 +
anebo II) existuje takové \(\lambda_{i_1} \), že \(\lvert \lambda_{i_1} \rvert < \lvert 1-\omega \rvert\), pak ale musí zároveň existovat takové \(\lambda_{i_2}\), že \(\lvert \lambda_{i_2} \rvert > \lvert 1-\omega \rvert\) a nastává tudíž \(\rho (\matice B_{\omega}) \geq \lvert \lambda_{i_2} \rvert>\lvert \lambda_i \rvert \). Z věty \ref{KSOR} pak plyne divergence metody pro \( \omega \in \mathbbm R \setminus \langle 0 , 2 \rangle  \).
 
\end{proof}
 
\end{proof}
 
\end{theorem}
 
\end{theorem}
  
 
\begin{theorem}
 
\begin{theorem}
−
\label{AbsEigenvalueVSNorma}
+
\label{KDiagSOR}
−
Nechť \( \matice A \in \mathbbm C^{n, n} \). Potom platí
+
Nechť má matice \( \matice A \) převládající diagonálu a platí \( 0 < \omega \leq 1 \). Pak super-relaxační metoda pro soustavu lineárních rovnic \( \matice A \vec x = \vec b \) konverguje pro libovolné \( \vec x^{( 0 )} \) k \( \vec x \).
−
\[ \forall \; \text{maticové normy} \; \lVert \, \cdot \, \rVert, \rho ( \matice A ) \leq \lVert \matice A \rVert \]
+
 
\begin{proof}
 
\begin{proof}
−
Označíme \( \lambda^{\matice A} \in \sigma ( \matice A ) \) a \( \forall \varepsilon > 0 \) označíme
+
Oberhuber nezná.
−
\[ \matice B = \frac{1}{\lVert \matice A \rVert + \varepsilon} \matice A \]
+
−
a potom
+
−
\[ \lVert \matice B \rVert = \frac{\lVert \matice A \rVert}{\lVert \matice A \rVert + \varepsilon} < 1 \Rightarrow \matice B^k \rightarrow \Theta \]
+
−
díky \ref{GeomKNorma}. Pro nějaký \( \vec x \) vlastní vektor matice \( \matice A\) platí
+
−
\[ \matice B \vec x =  \frac{1}{\lVert \matice A \rVert + \varepsilon} \matice A \vec x =  \frac{\lambda^{\matice A}}{\lVert \matice A \rVert + \varepsilon} \vec x = \lambda^{\matice B} \vec x \]
+
−
Kde platí \( \lambda^{\matice B} \in \sigma ( \matice B ) \) a \( \lambda^{\matice B} < 1 \) díky \ref{GeomKSpektrum}. Pak platí
+
−
\[ \lvert \lambda^{\matice A} \rvert = ( \lVert \matice A \rVert + \varepsilon ) \lambda^{\matice B} < \lVert \matice A \rVert + \varepsilon, \; \forall \varepsilon > 0 \]
+
−
a tedy \( \lvert \lambda^{\matice A} \rvert \leq \lVert \matice A \rVert \)
+
 
\end{proof}
 
\end{proof}
 
\end{theorem}
 
\end{theorem}
  
−
\begin{theorem}
+
\begin{theorem}[Ostrowski]
−
\label{NutPostK}
+
\label{Ostrowski}
−
Nechť \( \matice A \in \mathbbm C^{n, n} \). Potom platí
+
Nechť je matice \( \matice A \) hermitovská a pozivně definitní. Pak super-relaxační metoda pro soustavu lineárních rovnic \( \matice A \vec x = \vec b \) konverguje pro libovolné \( \vec x^{( 0 )} \) k \( \vec x \) právě tehdy, když
−
\[ \sum_{i = 0}^\infty \matice A^i < \infty \Leftrightarrow \matice A^k \rightarrow \Theta \]
+
\[ 0 < \omega < 2 \]
−
a
+
Konvergence je navíc monotónní vzhledem k normě \( \lVert \, \cdot \, \rVert_{\matice 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{proof}
−
Označíme \( \matice S_k = \sum_{i = 0}^k \matice A^i \) a platí
+
Upravíme předpis super-relaxační metody do tvaru
−
\[ ( \matice I - \matice A ) \matice S_k = \matice I - \matice A^{k + 1} \]
+
\[ \vec x^{( k + 1 )} = ( \matice I - \omega \left( \matice D - \omega \matice L \right)^{-1} \matice A ) \vec x^{( k )} + \omega \left( \matice D - \omega \matice L \right)^{-1} \vec b \]
−
Matici \( \matice A \) rozložíme podle \ref{JordanovaVeta}: \( \matice A = \matice{T J} \matice T^{-1} \) a platí
+
což je předpis předpodmíněné metody postupných aproximací s předpodmíněním \( \matice H = \omega \left( \matice D - \omega \matice L \right)^{-1} \). Díky podmínce věty platí
−
\[ \matice I - \matice A = \matice{T I} \matice T^{-1} - \matice{T J} \matice T^{-1} = \matice T ( \matice I - \matice J ) \matice T^{-1} \]
+
\[ \frac{2}{\omega} - 1 > 0 \]
−
a jelikož díky \ref{GeomKSpektrum} jsou prvky na diagonále matice \( ( \matice I - \matice J ) \) nenulové, je tato matice regulární, pak je i \( ( \matice I - \matice A ) \) regulární a tedy
+
Díky hermitovskosti matice \( \matice A \) platí \( \matice L^* = \matice R \) a \( \matice D^* = \matice D \). Potom můžeme s využitím \ref{KHermPDPredpodmineneAproximace} dokázat \textbf{postačující podmínku}, protože platí
−
\[ \matice S_k = ( \matice I - \matice A )^{-1} ( \matice I - \matice A^{k + 1} ) \]
+
\[ \matice H^{-1} + \left( \matice H^{-1} \right)^* = \frac{1}{\omega} ( \matice D - \omega \matice L) + \frac{1}{\omega} ( \matice D - \omega \matice L )^* = \frac{1}{\omega} \matice D - \matice L + \frac{1}{\omega} \matice D - \matice R = \left( \frac{2}{\omega} - 1 \right) \matice D + \matice A > \matice A \]
−
což má konečnou limitu právě pro \( \matice A^k \rightarrow \Theta \) rovnu \( ( \matice I - \matice A )^{-1} \)
+
 
\end{proof}
 
\end{proof}
 
\end{theorem}
 
\end{theorem}
  
 +
\setcounter{define}{37}
 
\begin{theorem}
 
\begin{theorem}
−
\label{GeomRozvoj}
+
\label{SORJacobiEigenvalue}
−
Nechť \( \matice A \in \mathbbm C^{n, n} \) a \( \lVert \matice A \rVert < 1 \). Potom platí
+
Nechť je matice \( \matice A \) dvoucyklická a shodně uspořádaná. Nechť dále \( \omega \neq 0 \) a \( \lambda \neq 0 \) a \( \matice B_\omega \in \mathbbm C^{n, n} \) je maticí super-relaxační metody a \( \matice B_J \in \mathbbm C^{n, n} \) je maticí Jacobiho metody. Nechť čísla \( \lambda \) a \( \mu \) splňují
−
\[ \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 \]
+
\[ ( \lambda + \omega - 1 )^2 = \omega^2 \mu^2 \lambda \]
−
\begin{proof}
+
Pak \( \lambda \in \sigma ( \matice B_\omega ) \Leftrightarrow \mu \in \sigma ( \matice B_J ) \). Navíc platí, že pro
−
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í
+
\[ \omega_{opt} = \frac{2}{1 + \sqrt{1 - \rho^2 ( \matice B_J ) }} \]
−
\[ \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} \]
+
nabývá \( \rho( \matice B_\omega ) \) svého minima a super-relaxační metoda tedy konverguje nejrychleji.
−
kde poslední rovnost plyne ze vzorce pro součet geometrické řady.
+
\begin{proof}\renewcommand{\qedsymbol}{}
 +
Bez důkazu.
 
\end{proof}
 
\end{proof}
 
\end{theorem}
 
\end{theorem}
 +
 +
\subsection{Shrnutí podmínek konvergence}
 +
~\\ ~\\
 +
\begin{tabular}{c | c | c}
 +
\textbf{Podmínka na matici} \( \matice A \) & Převládající diagonála & Hermitovská a pozitivně definitní \\ \hline
 +
\textbf{Jacobiho metoda} & vždy & \( \matice A < 2 \matice D \) \\ \hline
 +
\textbf{Gaussova-Seidelova metoda} & vždy & vždy \\ \hline
 +
\textbf{Super-relaxační metoda} & \( 0 < \omega \leq 1 \) & \( 0 < \omega < 2 \) \\
 +
\end{tabular}

Aktuální verze z 31. 1. 2017, 11:41

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. 201617:56
Řídící stránka editovatDefiniční stránka dokumentu a vložených obrázkůDedicma2 23. 5. 201722:31
Header editovatHlavičkový souborDedicma2 17. 1. 201617:20 header.tex
Kapitola0 editovatZnačeníDedicma2 23. 5. 201722:32 preamble.tex
Kapitola2 editovatOpakování a doplnění znalostí z lineární algebryKubuondr 30. 1. 201718:14 prezentace2.tex
Kapitola3 editovatÚvod do numerické matematikyKubuondr 10. 12. 201615:17 prezentace3.tex
Kapitola4 editovatPřímé metody pro lineární soustavyKubuondr 30. 1. 201712:27 prezentace4.tex
Kapitola5 editovatIterativní metodyKubuondr 31. 1. 201711:41 prezentace5.tex
Kapitola6 editovatVlastní čísla a vektory maticKubuondr 31. 1. 201714:13 prezentace6.tex
Kapitola7 editovatNelineární rovniceKubuondr 31. 1. 201715:27 prezentace7.tex
Kapitola8 editovatInterpolaceKubuondr 31. 1. 201716:43 prezentace8.tex
Kapitola9 editovatDerivace a integraceKubuondr 31. 1. 201718:33 prezentace9.tex

Zdrojový kód

%\wikiskriptum{01NUM1}
\section{Iterativní metody – úvod a soustavy lineárních rovnic}
 
\subsection{Iterativní metody obecně}
 
\begin{theorem}
\label{KIterativniMetody}
Iterativní metoda tvaru
\[ \vec x^{( k + 1 )} = \matice B^{( k )} \vec x^{( k )} + \vec c^{( k )} \]
splňující
\[ \vec x = \matice B^{( k )} \vec x + \vec c^{( k )} \]
konverguje pro libovolné \( \vec x^{( 0 )} \) k \( \vec x \) právě tehdy, když
\[ \lim_{k \rightarrow \infty} \prod_{i = 0}^k \matice B^{( k - i )} = \Theta \]
\begin{proof}
\[ \lim_{k \rightarrow \infty} \vec x^{( k )} - \vec x = \lim_{k \rightarrow \infty} \matice B^{( k - 1)} \vec x^{( k -1 )} + \vec c^{( k - 1 )} - \matice B^{( k - 1 )} \vec x - \vec c^{( k - 1 )} = \]
\[ = \lim_{k \rightarrow \infty} \matice B^{( k - 1 )} ( \vec x^{( k -1 )} - \vec x ) = \dots = \lim_{k \rightarrow \infty} \prod_{i = 0}^{k - 1} \matice B^{( k - i - 1 )} ( \vec x^{( 0 )} - \vec x ) \]
což je rovno nule pro libovolné \( \vec x^{( 0 )} \) právě tehdy, je-li splněna podmínka z věty.
\end{proof}
\end{theorem}
 
\begin{remark*}
Vzhledem k tomu, že je výběr \( \vec x^{( 0 )} \) libovolný, bude tato metoda konvergovat i přes numerické chyby. Iterativní metody pro řešení soustav lineárních algebraických rovnic mají \textbf{samoopravující} vlastnost
a jsou tudíž stabilní vzhledem k numerickým chybám.
\end{remark*}
 
\subsection{Stacionární iterativní metody}
 
\begin{theorem}
\label{KStacionarniIterativniMetody}
Stacionární iterativní metoda, tj. metoda tvaru
\[ \vec x^{( k + 1 )} = \matice B \vec x^{( k )} + \vec c \]
splňující
\[ \vec x = \matice B \vec x + \vec c \]
konverguje pro libovolné \( \vec x^{( 0 )} \) k \( \vec x \) právě tehdy, když
\[ \lim_{k \rightarrow \infty } \matice B^k = \Theta \]
\begin{proof}
\( \matice B^k = \prod_{i = 0}^k \matice B \) a tedy platnost této věty plyne přímo z \ref{KIterativniMetody}.
\end{proof}
\end{theorem}
 
\begin{theorem}
\label{KStacionarniIterativniMetodySpektrum}
Stacionární iterativní metoda, tj. metoda tvaru
\[ \vec x^{( k + 1 )} = \matice B \vec x^{( k )} + \vec c \]
splňující
\[ \vec x = \matice B \vec x + \vec c \]
konverguje pro libovolné \( \vec x^{( 0 )} \) k \( \vec x \) právě tehdy, když
\[ \rho ( \matice B ) < 1 \]
\begin{proof}
Plyne z \ref{GeomKSpektrum} a \ref{KStacionarniIterativniMetody}.
\end{proof}
\end{theorem}
 
\begin{theorem}
\label{KStacionarniIterativniMetodyNorma}
Postačující podmínkou pro to, aby stacionární iterativní metoda, tj. metoda tvaru
\[ \vec x^{( k + 1 )} = \matice B \vec x^{( k )} + \vec c \]
splňující
\[ \vec x = \matice B \vec x + \vec c \]
konvergovala pro libovolné \( \vec x^{( 0 )} \) k \( \vec x \) je
\[ \exists \; \text{maticová norma} \; \lVert \, \cdot \, \rVert, \lVert \matice B \rVert < 1 \]
\begin{proof}
Plyne z \ref{GeomKNorma} a \ref{KStacionarniIterativniMetody}.
\end{proof}
\end{theorem}
 
\begin{theorem}[Aposteriorní odhad chyby pro stacionární iterativní metody]
\label{AposteriorniOdhad}
Pro stacionární iterativní metodu, tj. metodu tvaru
\[ \vec x^{( k + 1 )} = \matice B \vec x^{( k )} + \vec c \]
splňující
\[ \vec x = \matice B \vec x + \vec c \]
kde \( \vec x \) je řešením soustavy lineárních rovnic \( \matice A \vec x = \vec b \), platí při použití \textbf{souhlasné normy} tyto odhady chyby aproximace řešení:
\begin{enumerate}[(1)]
\item \( \displaystyle \left\lVert \vec x^{( k )} - \vec x \right\rVert \leq \left\lVert \matice A^{-1} \right\rVert \left\rVert \matice A \vec x^{( k )} - \vec b \right\rVert \)
\\
\item \( \displaystyle \left\lVert \vec x^{( k )} - \vec x \right\rVert \leq \left\lVert ( \matice I - \matice B )^{-1} \right\rVert \lVert \matice B \rVert \left\lVert \vec x^{( k - 1)} - \vec x^{( k )} \right\rVert \)
\end{enumerate}
\begin{proof}
\begin{enumerate}[(1)]
\item
Nahrazujeme vektor \( \vec x\) pomocí \( \vec x =\matice A^{-1} \vec b \).
\[ \left\lVert \vec x^{( k )} - \vec x \right\rVert = \left\lVert \matice A^{-1} ( \matice A \vec x^{( k )} - \vec b ) \right\rVert \leq \left\lVert \matice A^{-1} \right\rVert \left\rVert \matice A \vec x^{( k )} - \vec b \right\rVert \]
kde poslední nerovnost plyne z trojúhelníkové nerovnosti.
\item
Nahrazujeme vektor \( \vec x\) pomocí \( \vec x =( \matice I - \matice B )^{-1} \vec c \), což je inverze podmínky pro řešení.
\[ \left\lVert \vec x^{( k )} - \vec x \right\rVert = \left\lVert ( \matice I - \matice B )^{-1} ( ( \matice I - \matice B ) \vec x^{( k )} - \vec c ) \right\rVert \leq \left\lVert ( \matice I - \matice B )^{-1} \right\rVert \left\lVert ( \matice I - \matice B ) \vec x^{( k )} - \vec c \right\rVert \]
kde poslední nerovnost je opět aplikací trojúhleníkové nerovnosti.
\[ \left\lVert ( \matice I - \matice B )^{-1} \right\rVert \left\lVert ( \matice I - \matice B ) \vec x^{( k )} - \vec c \right\rVert = \left\lVert ( \matice I - \matice B )^{-1} \right\rVert \left\lVert \vec x^{(k)} - \matice B \vec x^{( k )} - \vec c \right\rVert = \left\lVert ( \matice I - \matice B )^{-1} \right\rVert \left\lVert \matice B \vec x^{(k - 1)} + \vec c - \matice B \vec x^{( k )} - \vec c \right\rVert =  \]
\[ = \left\lVert ( \matice I - \matice B )^{-1} \right\rVert \left\lVert \matice B ( \vec x^{(k - 1)} - \vec x^{( k )} ) \right\rVert \leq \left\lVert ( \matice I - \matice B )^{-1} \right\rVert \left\lVert \matice B \right\rVert \left\lVert \vec x^{(k - 1)} - \vec x^{( k )} \right\rVert \]
kde poslední nerovnost je znovu pouze aplikací trojúhelníkové nerovnosti. \qedhere
\end{enumerate}
\end{proof}
\end{theorem}
 
\begin{define}[V prezentaci poznámka]
Nechť \( \vec x^{( k )} \) je \( k \)-tá aproximace řešení soustavy lineárních rovnic \( \matice A \vec x = \vec b \). Potom definujeme reziduum v \( k \)-té iteraci
\[ \vec r^{( k )} = \matice A \vec x^{( k )} - \vec b \]
\end{define}
 
\setcounter{define}{7}
\begin{theorem}[Apriorní odhad chyby pro stacionární iterativní metody]
\label{ApriorniOdhad}
Pro stacionární iterativní metodu, tj. metodu tvaru
\[ \vec x^{( k + 1 )} = \matice B \vec x^{( k )} + \vec c \]
splňující
\[ \vec x = \matice B \vec x + \vec c \]
a dále splňující pro nějakou maticovou normu
\[ \lVert \matice B \rVert < 1 \]
platí
\[ \left\lVert \vec x^{(k)} - \vec x \right\rVert \leq \lVert \matice B \rVert^k \left( \left\lVert \vec x^{(0)} \right\rVert + \frac{\lVert \vec c \rVert}{1 - \lVert \matice B \rVert} \right) \]
kde používaná vektorová norma je \textbf{souhlasná} s normou maticovou.
\begin{proof}
\[ \vec x^{(k)} = \matice B \vec x^{(k - 1)} + \vec c = \dots = \matice B^k \vec x^{(0)} + \sum_{i = 0}^{k - 1} \matice B^i \vec c \]
Protože \( \lVert \matice B \rVert < 1 \), tak díky \ref{AbsEigenvalueVSNorma} \( \rho ( \matice B ) < 1 \), a tedy \( 0 \notin \sigma ( \matice I - \matice B ) \), tedy \( ( \matice I - \matice B ) \) je regulární a můžeme upravovat
\[ \vec c = ( \matice I - \matice B) \vec x \Rightarrow \vec x = ( \matice I - \matice B )^{-1} \vec c = \sum_{i = 0}^\infty \matice B^i \vec c \]
kde poslední rovnost platí, protože \( \lVert \matice B \rVert < 1 \), a tedy díky \ref{GeomKNorma} řada konverguje.
S pomocí těchto dvou rozvojů můžeme za použití trojúhelníkové nerovnosti a vzorce pro součet geometrické řady odhadovat
\[ \left\lVert \vec x^{(k)} - \vec x \right\rVert = \left\lVert \matice B^k \vec x^{(0)} + \sum_{i = 0}^{k - 1} \matice B^i \vec c - \sum_{i = 0}^\infty \matice B^i \vec c \right\rVert = \left\lVert \matice B^k \vec x^{(0)} - \sum_{i = k}^\infty \matice B^i \vec c \right\rVert = \left\lVert \matice B^k \left( \vec x^{(0)} - \sum_{i = 0}^\infty \matice B^i \vec c \right) \right\rVert \leq \]
\[ \leq \lVert \matice B \rVert^k \left\lVert \vec x^{(0)} - \sum_{i = 0}^\infty \matice B^i \vec c \right\rVert \leq \lVert \matice B \rVert^k \left( \left\lVert \vec x^{(0)} \right\rVert + \sum_{i = 0}^\infty \lVert \matice B \rVert^i \lVert \vec c \rVert \right) = \lVert \matice B \rVert^k \left( \left\lVert \vec x^{(0)} \right\rVert + \frac{\lVert \vec c \rVert}{1 - \lVert \matice B \rVert} \right) \]
\end{proof}
\end{theorem}
 
\subsection{Metoda postupných aproximací}
Využijeme znalosti rezidua v \( k \)-té iteraci a definujeme
\[ \vec x^{( k + 1 )} = \vec x^{( k )} - \vec r^{( k )} = \vec x^{( k )} - \matice A \vec x^{( k )} + \vec b = ( \matice I - \matice A ) \vec x^{( k )} + \vec b \]
Vidíme, že tato metoda obecně splňuje podmínku
\[ \vec x = ( \matice I - \matice A ) \vec x + \vec b \]
 
\begin{theorem}
\label{KPostupneAproximace}
Metoda postupných aproximací pro soustavu lineárních rovnic \( \matice A \vec x = \vec b \), kde matice \( \matice A \) je regulární, tj. metoda tvaru
\[ \vec x^{(k + 1)} = ( \matice I - \matice A ) \vec x^{(k)} + \vec b \]
konverguje pro libovolné \( \vec x^{(0)} \) k \( \vec x \) právě tehdy, když
\[ \rho ( \matice I - \matice A ) < 1 \]
\begin{proof}
Plyne z \ref{KStacionarniIterativniMetodySpektrum}.
\end{proof}
\end{theorem}
 
\begin{remark*}
Díky \ref{AbsEigenvalueVSNorma} je postačující podmínkou konvergence metody postupných aproximací existence nějaké normy, pro kterou
\[ \lVert \matice I - \matice A \rVert < 1 \]
\end{remark*}
 
\begin{theorem}
\label{PolynomEigenvalues}
Nechť \( p(t) \) je polynom, \( \matice A \in \mathbbm C^{n, n} \) a \( \lambda \in \sigma ( \matice A ) \). Potom \( p( \lambda ) \in \sigma ( p( \matice A ) ) \).
\begin{proof}
Využijeme vztahu \( \lambda \in \sigma ( \matice A ) \Leftrightarrow ( \matice A - \lambda \matice I ) \) je singulární. Rozepíšeme \( p ( t ) \) do tvaru
\[ p ( t ) = \sum_{i = 0}^n a_i t^i, \; a_n \neq 0 \]
Potom můžeme upravit
\[ p ( \matice A ) - p ( \lambda ) \matice I = \sum_{i = 0}^n a_i \matice A^i - \sum_{i = 0}^n a_i \lambda^i = \sum_{i = 1}^n a_i ( \matice A - \lambda \matice I )^i = ( \matice A - \lambda \matice I ) \sum_{i = 1}^n a_i ( \matice A - \lambda \matice I )^{i - 1} \]
Z čehož plyne, že \( p ( \matice A ) - p ( \lambda ) \matice I \) je sigulární a tedy \( p ( \lambda ) \in \sigma ( p ( \matice A ) ) \).
\end{proof}
\end{theorem}
\begin{remark*}\textit{(Důkaz z přednášky)}
Z \ref{MocninaJordan} víme, že se při mocnění umocňuje spektrum.  
S pomocí Jordanovy věty dále zjistíme, že pro násobení platí:
\[a^k\matice A^k=a^k \matice X^-1\matice J^k \matice X=\matice X^-1 (a\matice J)^k \matice X\]
Obdobně pro sčítání. Z toho je vidět, spektrum součtu matice obsahuje součet vlastních čísel. Složením těchto operací definuje polynom.
Platí tedy \(p(\matice A)=matice X^-1 p(\matice J) \matice X\), což dokazuje větu.
\end{remark*}
 
\begin{theorem}
\label{KHermPDPostupneAproximace}
Nechť matice \( \matice A \) je hermitovská a pozitivně definitní. Pak metoda postupných aproximací pro soustavu lineárních rovnic \( \matice A \vec x = \vec b \) konverguje pro libovolné \( \vec x^{( 0 )} \) k \( \vec x \) právě tehdy, když
\[ \Theta < \matice A < 2 \matice I \]
\begin{proof}
Díky \ref{KPostupneAproximace} metoda postupných aproximací konverguje právě tehdy, když \( \sigma ( \matice I - \matice A ) \subset \left( -1, 1 \right) \). Hermitovskost matice \( \matice A \) nám zaručuje reálnost vlastních čísel. Vezmeme polynom \( p ( t ) = 1 - t \), tedy \( p ( \matice I - \matice A ) = \matice A \) a užitím \ref{PolynomEigenvalues} dostáváme \( \sigma ( \matice A ) \subset p ( \left( -1 , 1 \right) ) = \left( 0, 2 \right) \), tedy \( \matice A \) je pozitivně definitní.
\\ Vezmeme polynom \( q ( t ) = 1 + t \), tedy \( q ( \matice I - \matice A ) = 2 \matice I - \matice A \) a užitím \ref{PolynomEigenvalues} dostáváme \( \sigma ( 2 \matice I - \matice A ) \subset q ( \left( -1 , 1 \right) ) = \left( 0, 2 \right) \), tedy \( 2 \matice I - \matice A \) je pozitivně definitní. To je jinak zapsáno \( \matice A < 2 \matice I \).
\end{proof}
\end{theorem}
\begin{remark*}
Nejspíše platí i pro nehermitovské matice. Všechny věty, které jsou v důkazu použité, platí bez ohledu na to, zda jsou vlastní čísla reálná či komplexní, pokud se nahradí interval kruhem v \(\matice C\) obsahujícím daný interval.
\end{remark*}
 
\subsection{Předpodmíněná metoda postupných aproximací}
Abychom zlepšili konvergenci metody postupných aproximací, vynásobíme soustavu regulární maticí \( \matice H \) a dostáváme
\[ \matice{H A} \vec x = \matice H \vec b \]
Použitím metody postupných aproximací pro tuto soustavu dostáváme
\[ \vec x^{( k + 1 )} = ( \matice I - \matice{H A} ) \vec x^{( k )} + \matice H \vec b \]
Podmínka
\[ \vec x = ( \matice I - \matice{H A} ) \vec x + \matice H \vec b \]
je splněna díky tomu, že je obecně splněná pro metodu postupných aproximací.
 
\setcounter{define}{12}
\begin{theorem}
\label{KPredpodmineneAproximace}
Předpodmíněná metoda postupných aproximací s předpodmíněním \( \matice H \) pro soustavu lineárních rovnic \( \matice A \vec x = \vec b \), kde matice \( \matice A \) je regulární, tj. metoda tvaru
\[ \vec x^{( k + 1 )} = ( \matice I - \matice{H A} ) \vec x^{( k )} + \matice H \vec b \]
konverguje pro libovolné \( \vec x^{( 0 )} \) k \( \vec x \) právě tehdy, když
\[ \rho ( \matice I - \matice{H A} ) < 1 \]
\begin{proof}
Plyne z \ref{KStacionarniIterativniMetodySpektrum}.
\end{proof}
 
\end{theorem}
 
\begin{remark*}
Díky \ref{AbsEigenvalueVSNorma} je postačující podmínkou konvergence předpodmíněné metody postupných aproximací existence nějaké normy, pro kterou
\[ \lVert \matice I - \matice{H A} \rVert < 1 \]
\end{remark*}
 
\begin{theorem}
\label{KHermPDPredpodmineneAproximace}
Nechť matice \( \matice A \) je hermitovská a pozitivně definitní. Pak předpodmíněná metoda postupných aproximací pro soustavu lineárních rovnic \( \matice A \vec x = \vec b \) konverguje pro libovolné \( \vec x^{( 0 )} \) k \( \vec x \) když platí \textbf{postačující podmínka}
\[ \Theta < \matice A <\matice H^{-1} + \left( \matice H^{-1} \right)^* \]
Konvergence je navíc monotónní vzhledem k normě \( \lVert \, \cdot \, \rVert_{\matice A} \)
\begin{proof}
Chceme dokázat \( \lVert \matice I - \matice{H A} \rVert_{\matice A} < 1 \) a tím splnit předpoklady \ref{KPredpodmineneAproximace} (Energetická norma existuje, protože je \( \matice A \) hermitovská a pozitivně definitní).
\[ \lVert \matice I - \matice{H A} \rVert_{\matice A} = \left\lVert \matice A^{\frac{1}{2}} ( \matice I - \matice{H A} ) \matice A^{-\frac{1}{2}} \right\rVert_2 = \left\lVert \matice I - \matice A^{\frac{1}{2}} \matice H \matice A^{\frac{1}{2}} \right\rVert_2 = \lVert \matice B \rVert_2 \]
když označíme \( \matice B = \matice I - \matice A^{\frac{1}{2}} \matice H \matice A^{\frac{1}{2}} \). Dále
\[ \lVert \matice B \rVert_2 < 1 \Leftrightarrow \lVert \matice B \rVert_2^2 < 1 \]
Využijeme \ref{NormaMatice} a \ref{AbsEigenvalueVSNorma}
\[ \lVert \matice B \rVert_2^2 = \rho ( \matice B^* \matice B ) \leq \left\lVert \matice B^* \matice B \right\rVert \]
pro nějakou normu. Budeme tedy odhadovat ze shora matici \( \matice B^* \matice B \).
\[ \matice B^* \matice B = ( \matice I - \matice A^{\frac{1}{2}} \matice H \matice A^{\frac{1}{2}} )^* ( \matice I - \matice A^{\frac{1}{2}} \matice H \matice A^{\frac{1}{2}} ) = ( \matice I - \matice A^{\frac{1}{2}} \matice H^* \matice A^{\frac{1}{2}} ) ( \matice I - \matice A^{\frac{1}{2}} \matice H \matice A^{\frac{1}{2}} ) \]
kde poslední rovnost plyne z hermitovskosti matice \( \matice A \).
\[ ( \matice I - \matice A^{\frac{1}{2}} \matice H^* \matice A^{\frac{1}{2}} ) ( \matice I - \matice A^{\frac{1}{2}} \matice H \matice A^{\frac{1}{2}} ) = \matice I - \matice A^{\frac{1}{2}} ( \matice H^* + \matice H ) \matice A^{\frac{1}{2}} + \matice A^{\frac{1}{2}} \matice H^* \matice A \matice H \matice A^{\frac{1}{2}} \]
Využijeme snadno ověřitelné rovnosti \( \matice H^* ( \matice H^{-1} + \left( \matice H^{-1} \right)^* ) \matice H = \matice H^* + \matice H \) a dostáváme
\[ \matice I - \matice A^{\frac{1}{2}} ( \matice H^* + \matice H ) \matice A^{\frac{1}{2}} + \matice A^{\frac{1}{2}} \matice H^* \matice A \matice H \matice A^{\frac{1}{2}} = \matice I - \matice A^{\frac{1}{2}} \matice H^* ( \matice H^{-1} + \left( \matice H^{-1} \right)^* ) \matice H \matice A^{\frac{1}{2}} + \matice A^{\frac{1}{2}} \matice H^* \matice A \matice H \matice A^{\frac{1}{2}} =  \]
\[ = \matice I - \matice A^{\frac{1}{2}} \matice H^* ( \underbrace{\matice H^{-1} + \left( \matice H^{-1} \right)^* - \matice A}_{> \Theta} ) \matice H \matice A^{\frac{1}{2}} \]
kde jsme k odhadu využili předpokladů věty. Dále víme, že \( \matice H^* \matice H \) je pozitivně definitní (Ověření: \( \braket{\matice H^* \matice H \vec x | \vec x} = \braket{\matice H \vec x | \matice H \vec x} = \lVert \matice H \vec x \rVert > 0 \)). Protože i \( \matice A \) je pozitivně definitní, můžeme odhadnout
\[ \matice A^{\frac{1}{2}} \matice H^* ( \matice H^{-1} + \left( \matice H^{-1} \right)^* - \matice A ) \matice H \matice A^{\frac{1}{2}} > \Theta \]
A protože i \( \matice B^* \matice B \) je pozitivně definitní, konečně můžeme odhadnout
\[ \matice I - \matice A^{\frac{1}{2}} \matice H^* ( \matice H^{-1} + \left( \matice H^{-1} \right)^* - \matice A ) \matice H \matice A^{\frac{1}{2}} < \matice I \]
Tím jsme naplnili předpoklady \ref{KPredpodmineneAproximace}, a tedy dokázali platnost věty.
\end{proof}
\end{theorem}
 
Jak tedy volit matici \( \matice H \)? Pokud bychom volili \( \matice H = \matice A^{-1} \) dostáváme
\[ \vec x^{( k + 1 )} = \left( \matice I - \matice A^{-1} \matice A \right) \vec x^{( k )} + \matice A^{-1} \vec b = \vec x \]
Tedy předpodmíněná metoda postupných aproximací by konvergovala v první iteraci. Avšak výpočet \( \matice A^{-1} \) provádíme Gaussovou eliminační metodou, čemuž jsme se chtěli vyhnout.
\\ Oblíbenou metodou je tzv. \textbf{neúplný LU rozklad}, kde malé prvky zanedbáváme, čímž můžeme zlepšit časovou náročnost.
 
\subsection{Richardsonovy iterace}
Zavedeme tzv. \textbf{relaxační parametr} \( \theta \in \mathbbm C \). Metoda Richardsonových iterací je předpodmíněnou metodou postupných iterací, kde volíme
\[ \matice H = \theta \matice I \]
a dostáváme
\[ \vec x^{( k + 1 )} = ( \matice I - \theta \matice A ) + \theta \vec b \]
 
\setcounter{define}{15}
\begin{theorem}
\label{KHermPDRichardson}
Nechť matice \( \matice A \) je hermitovská a pozitivně definitní. Nechť \( \theta \in \mathbbm R \). Pak metoda Richardsonových iterací konverguje pro libovolné \( \vec x^{( 0 )} \) k \( \vec x \) právě tehdy, když
\[ \Theta < \matice A < \frac{2}{\theta} \matice I \]
Konvergence je navíc monotónní vzhledem k normě \( \lVert \, \cdot \, \rVert_{\matice A} \)
 
\begin{proof}
Pomocí \ref{KHermPDPredpodmineneAproximace} dokážeme, že se jedná o \textbf{postačující podmínku}:
\todo{Důkaz nutnosti podmínky od doc. Humhala}
\[ \matice H^{-1} + \left( \matice H^{-1} \right)^* = \frac{1}{\theta} \matice I + \left( \frac{1}{\theta} \matice I \right)^* = \frac{2}{\theta} \matice I \]
\end{proof}
\end{theorem}
 
\subsection{Jacobiho metoda}
Vyjdeme ze vzorce pro výpočet složek násobku matice a vektoru, tj.
\[ \left( \matice A \vec y \right)_i = \sum_{j = 1}^n \matice A_{ij} \vec y_j \]
Budeme chtít, aby když z vektoru \( \vec x^{( k )} \) nahradíme \( i \)-tou složku \( i \)-tou složkou vektoru \( \vec x^{( k + 1 )} \), byla splněna \( i \)-tá rovnice soustavy, tj.
\[ \sum_{\substack{j = 1 \\ j \neq i}}^n \matice A_{ij} \vec x_j^{( k )} + \matice A_{ii} \vec x_i^{( k + 1 )} = \vec b_i \]
Tedy dostáváme
\[ \vec x_i^{( k + 1 )} = \frac{\vec b_i - \sum_{j = 1, j \neq i}^n \matice A_{ij} \vec x_j^{( k )}}{\matice A_{ii}} \]
Z posledního předpisu je vidět, že musíme předpokládat nenulovou diagonálu. Toho však lze u regulární matice dosáhnout přerovnáním.
 
\subsection{Jacobiho metoda - numerická analýza}
Rozepíšeme matici \( \matice A \) do tvaru
\[ \matice A = \matice D - \matice L - \matice R \]
kde
\begin{itemize}
\item \( \matice D \) je diagonální matice s diagonálou matice \( \matice A \)
\item \( \matice L \) je dolní trojúhelníková matice s prvky pod diagonálou \( \matice A \), vynásobenými \( ( - 1 ) \)
\item \( \matice R \) je horní trojúhelníková matice s prvky nad diagonálou \( \matice A \), vynásobenými \( ( - 1 ) \)
\end{itemize}
Můžeme tedy shrnout předpis pro prvky \( \vec x^{( k + 1 )} \) do jednoho vztahu
\[ \vec x^{( k + 1 )} = \matice D^{-1} \left( \vec b + ( \matice L + \matice R ) \vec x^{( k )} \right) = \matice D^{-1} \vec b + \matice D^{-1} ( \matice D - \matice A ) \vec x^{( k )} = \left( \matice I - \matice D^{-1} \matice A \right) \vec x^{( k )} + \matice D^{-1} \vec b \]
Zjišťujeme, že Jacobiho metoda je vlastně předpodmíněnou metodou postupných aproximací, kde volíme
\[ \matice H = \matice D^{-1}\]
\[\vec c = \matice D^{-1} \vec b \]
 
\setcounter{define}{17}
\begin{theorem}
\label{KJacobi}
Jacobiho metoda pro soustavu lineárních rovnic \( \matice A \vec x = \vec b \) konverguje pro libovolné \( \vec x^{( 0 )} \) k \( \vec x \) právě tehdy, když
\[ \rho \left( \matice D^{-1} ( \matice L + \matice R ) \right) < 1 \]
\begin{proof}
Díky vztahu \( \matice A = \matice D - \matice L - \matice R \) můžeme upravit
\[ \rho \left( \matice D^{-1} ( \matice L + \matice R ) \right) = \rho \left( \matice D^{-1} ( \matice D - \matice A ) \right) = \rho \left( \matice I - \matice D^{-1} \matice A \right) < 1 \]
čímž jsou splněny předpoklady \ref{KPredpodmineneAproximace}.
\end{proof}
\end{theorem}
 
\begin{remark*}
Díky \ref{AbsEigenvalueVSNorma} je postačující podmínkou konvergence Jacobiho metody existence nějaké normy, pro kterou
\[ \left\lVert \matice D^{-1} ( \matice L + \matice R ) \right\rVert < 1 \]
\end{remark*}
 
\begin{define}
\label{PrevladajiciDiagonala}
Pokud pro matici \( \matice A \in \mathbbm C^{n, n} \) platí
\[ \sum_{\substack{j = 1 \\ j \neq i}}^n \lvert \matice A_{ij} \rvert < \lvert \matice A_{ii} \rvert \]
Nazýváme ji maticí s převládající diagonálou.
\end{define}
 
\begin{theorem}
\label{KDiagJacobi}
Nechť má matice \( \matice A \) převládající diagonálu. Pak Jacobiho metoda pro soustavu lineárních rovnic \( \matice A \vec x = \vec b \) konverguje pro libovolné \( \vec x^{( 0 )} \) k \( \vec x \).
\begin{proof}
Chceme ukázat \( \lVert \matice D^{-1} ( \matice L + \matice R ) \rVert_\infty = \lVert \matice D^{-1} ( \matice D - \matice A ) \rVert_\infty = \lVert \matice I - \matice D^{-1} \matice A \rVert_\infty < 1 \) a využít \ref{KJacobi}. Matice \( \matice D \) je diagonální a na její diagonále jsou prvky diagonály matice \( \matice A \). Proto pro prvky matice \( \matice D^{-1} \matice A \) platí
\[ \left( \matice D^{-1} \matice A \right)_{ij} = \frac{\matice A_{ij}}{\matice A_{ii}} \]
A tedy na diagonále \( \matice D^{-1} \matice A \) jsou jedničky. Proto
\[ \left( \matice I - \matice D^{-1} \matice A \right)_{ij} =
\begin{cases}
0, & i =j \\
\frac{\matice A_{ij}}{\matice A_{ii}}, & i \neq j
\end{cases}
\]
Díky \ref{NormaMatice} platí
\[ \lVert \matice I - \matice D^{-1} \matice A \rVert_\infty = \max_{i \in \hat n} \sum_{j = 1}^n \left\lvert \left( \matice I - \matice D^{-1} \matice A \right)_{ij} \right\rvert = \max_{i \in \hat n} \frac{1}{\matice A_{ii}} \sum_{\substack{j = 1 \\ j \neq i}}^n \lvert \matice A_{ij} \rvert < 1 \]
kde poslední nerovnost je důsledkem toho, že matice \( \matice A \) má převládající diagonálu.
\end{proof}
\end{theorem}
 
\begin{theorem}
\label{KHermPDJacobi}
Nechť je matice \( \matice A \) hermitovská a pozivně definitní. Pak Jacobiho metoda pro soustavu lineárních rovnic \( \matice A \vec x = \vec b \) konverguje pro libovolné \( \vec x^{( 0 )} \) k \( \vec x \) právě tehdy, když
\[ \Theta < \matice A < 2 \matice D \]
Konvergence je navíc monotónní vzhledem k normě \( \lVert \, \cdot \, \rVert_{\matice A} \)
\begin{proof}
Protože je matice \( \matice A \) hermitovská, jsou diagonální prvky \( \matice A_{ii} \in \mathbbm R \) (musí platit \( \matice A_{ii} = \overline{\matice A_{ii}} \)), tudíž \( \matice D = \matice D^* \). Protože je navíc pozitivné definitní, platí \( \vec x^* \matice A \vec x > 0 \). Zvolíme–li \(\vec x = \vec e_{(i)} \), kde \( \vec e_{(i)} \) jsou vektory ze standardní báze, dostaneme \( \matice A_{ii} = \matice D_{ii} = \vec e_{(i)}^* \matice A \vec e_{(i)} > 0 \), tj. \(\matice D \) je pozitivně definitní.
\begin{enumerate}
\item[( \( \Leftarrow \) )] Upravíme předpis Jacobiho metody do tvaru
\[ \vec x^{( k + 1 )} = ( \matice I - \matice D^{-1} \matice A ) \vec x^{( k + 1 )} + \matice D^{-1} \vec b \]
což je předpis předpodmíněné metody postupných aproximací s předpodmíněním \( \matice H = \matice D^{-1} \). Dále tedy platí
\[ \matice H^{-1} + \left( \matice H^{-1} \right)^* = \matice D + \matice D^* = 2 \matice D \]
čímž jsou splněny předpoklady \ref{KHermPDPredpodmineneAproximace}.
\item[( \( \Rightarrow \) )] Díky \ref{KStacionarniIterativniMetodySpektrum} víme, že \( \sigma ( \matice I - \matice D^{-1} \matice A ) \subset \left( -1, 1 \right) \). Užitím \ref{PolynomEigenvalues} s \( p ( t ) = 1 + t \) dostáváme \( \sigma ( 2 \matice I - \matice D^{-1} \matice A ) \subset \left( 0, 2 \right) \). Můžeme upravit
\[ 2 \matice I - \matice D^{-1} \matice A = \matice D^{-\frac{1}{2}} ( 2 \matice I - \matice D^{-\frac{1}{2}} \matice A \matice D^{-\frac{1}{2}} ) \matice D^{\frac{1}{2}} \]
Z čehož plyne, že je matice \( 2 \matice I - \matice D^{-\frac{1}{2}} \matice A \matice D^{-\frac{1}{2}} \) pozitivně definitní. Toho využijeme při odhadu
\[ \braket{( 2 \matice D - \matice A ) \vec x | \vec x} = \vec x ( 2 \matice D - \matice A ) \vec x = \vec x \matice D^{\frac{1}{2}} \matice D^{-\frac{1}{2}} ( 2 \matice D - \matice A ) \matice D^{-\frac{1}{2}} \matice D^{\frac{1}{2}} \vec x = \left( \matice D^{\frac{1}{2}} \vec x \right)^* \left( 2 \matice I - \matice D^{-\frac{1}{2}} \matice A \matice D^{-\frac{1}{2}} \right) \left( \matice D^{\frac{1}{2}} \vec x \right) = \]
\[ = \braket{\left( 2 \matice I - \matice D^{-\frac{1}{2}} \matice A \matice D^{-\frac{1}{2}} \right) \matice D^{\frac{1}{2}} \vec x | \matice D^{\frac{1}{2}} \vec x} > 0 \]
Tedy \( 2 \matice D - \matice A > \Theta \), což je jinak zapsáno \( 2 \matice D > \matice A \).
\end{enumerate}
\end{proof}
\end{theorem}
 
\subsection{Gaussova-Seidelova metoda}
Vyjdeme ze stejného vztahu jako v případě Jacobiho metody, avšak použijeme již napočítané složky vektoru \( \vec x^{( k + 1 )} \), tedy
\[ \sum_{j = 1}^i \matice A_{ij} \vec x_j^{( k + 1 )} + \sum_{j = i + 1}^n \matice A_{ij} \vec x_j^{( k )} = \vec b_i \]
Tedy dostáváme
\[ \vec x_i^{( k + 1 )} = \frac{\vec b_i - \sum_{j = 1}^{i - 1} \matice A_{ij} \vec x_j^{( k + 1 )} - \sum_{j = i + 1}^n \matice A_{ij} \vec x_j^{( k )}}{\matice A_{ii}} \]
Znovu musíme předpokládat nenulovou diagonálu.
 
\subsection{Gaussova-Seidelova metoda - numerická analýza}
Použijeme stejného přepisu matice \( \matice A \) jako v případě Jacobiho metody a shrneme předpis pro prvky \( \vec x^{( k + 1 )} \) do jednoho vztahu
\[ \vec x^{( k + 1 )} = \matice D^{-1} \left( \vec b + \matice L \vec x^{( k + 1 )} + \matice R \vec x^{( k )} \right) \]
který upravujeme
\[ \matice D \vec x^{( k + 1 )} - \matice L \vec x^{( k + 1 )} = \vec b + \matice R \vec x^{( k )} \]
\[ \vec x^{( k + 1 )} = ( \matice D - \matice L )^{-1} ( \matice D - \matice L - \matice A ) \vec x^{( k )} + ( \matice D - \matice L )^{-1} \vec b \]
\[ \vec x^{( k + 1 )} = \left( \matice I - ( \matice D - \matice L )^{-1} \matice A \right) \vec x^{( k )} + ( \matice D - \matice L )^{-1} \vec b \]
Zjišťujeme, že Gaussova-Seidelova metoda je vlastně předpodmíněnou metodou postupných aproximací, kde volíme
\[ \matice H = ( \matice D - \matice L )^{-1} \]
 
\setcounter{define}{22}
\begin{theorem}
\label{KGaussSeidel}
Gaussova-Seidelova metoda pro soustavu lineárních rovnic \( \matice A \vec x = \vec b \) konverguje pro libovolné \( \vec x^{( 0 )} \) k \( \vec x \) právě tehdy, když
\[ \rho \left( ( \matice D - \matice L )^{-1} \matice R \right) < 1 \]
\begin{proof}
Upravíme předpis Gaussovy-Seidelovy metody do tvaru
\[ \vec x^{( k + 1 )} = ( \matice I - \left( \matice D - \matice L \right)^{-1} \matice A ) \vec x^{( k )} + \left( \matice D - \matice L \right)^{-1} \vec b \]
což je předpis předpodmíněné metody postupných aproximací s předpodmíněním \( \matice H = \left( \matice D - \matice L \right)^{-1} \). Díky vztahu \( \matice A = \matice D - \matice L - \matice R \) můžeme upravit
\[ \rho \left( \left( \matice D - \matice L \right)^{-1} \matice R \right) = \rho \left( \left( \matice D - \matice L \right)^{-1} ( \matice D - \matice L - \matice A ) \right) = \rho \left( \matice I - \left( \matice D - \matice L \right)^{-1} \matice A \right) < 1 \]
čímž jsou splněny předpoklady \ref{KPredpodmineneAproximace}.
\end{proof}
\end{theorem}
 
\begin{remark*}
Díky \ref{AbsEigenvalueVSNorma} je postačující podmínkou konvergence Gaussovy-Seidelovy metody existence nějaké normy, pro kterou
\[ \left\lVert ( \matice D - \matice L )^{-1} \matice R \right\rVert < 1 \]
\end{remark*}
 
\begin{theorem}
\label{KDiagGaussSeidel}
Nechť má matice \( \matice A \) převládající diagonálu. Pak Gaussova-Seidelova metoda pro soustavu lineárních rovnic \( \matice A \vec x = \vec b \) konverguje pro libovolné \( \vec x^{( 0 )} \) k \( \vec x \).
\begin{proof}
Označíme \( \matice B = \left( \matice D - \matice L \right)^{-1} \matice R \). Chceme ukázat \( \lVert \matice B \rVert_\infty < 1 \) a využít \ref{KGaussSeidel}. Díky \ref{NormaMatice} platí
\[ \lVert \matice B \rVert_\infty = \max_{\lVert \vec x \rVert_\infty = 1} \lVert \matice B \vec x \rVert_\infty \]
Označíme tento maximální vektor \( \vec u \) ( \( \lVert \vec u \rVert_\infty = 1 \) ) a dále označíme \( \vec v = \matice B \vec u \). Potom platí
\[ \lVert \matice B \rVert_\infty = \lVert \matice B \vec u \rVert_\infty = \lVert \vec v \rVert_\infty = \max_{k \in \hat n} \lvert \vec v_k \rvert \]
Označíme takovouto maximální složku indexem \( i \). Upravíme rovnici \( \matice B \vec u = \vec v \) do tvaru
\[ \left( \matice D - \matice L \right)^{-1} \matice R \vec u = \vec v \]
\[ \matice R \vec u = ( \matice D - \matice L ) \vec v \]
a budeme upravovat její \( i \)-tou (maximální) složku:
\[ \sum_{j = i + 1}^n -\matice A_{ij} \vec u_j = \sum_{j = 1}^i \matice A_{ij} \vec v_j \]
Upravíme a díky trojúhelníkové nerovnosti odhadujeme
\[ \lvert \vec v_i \rvert = \left\lvert \frac{1}{\matice A_{ii}} \left( \sum_{j = i + 1}^n - \matice A_{ij} \vec u_j - \sum_{j = 1}^{i - 1} \matice A_{ij} \vec v_j \right) \right\rvert \leq \frac{1}{\lvert \matice A_{ii} \rvert} \left( \sum_{j = i + 1}^n \lvert \matice A_{ij} \rvert \lvert \vec u_j \rvert + \sum_{j = 1}^{i - 1} \lvert \matice A_{ij} \rvert \lvert \vec v_j \rvert \right) \]
Využijeme vlastností \( \lvert \vec u_j \rvert \leq 1 \) a \( \lvert \vec v_j \rvert \leq \lvert \vec v_i \rvert \):
\[ \frac{1}{\lvert \matice A_{ii} \rvert} \left( \sum_{j = i + 1}^n \lvert \matice A_{ij} \rvert \lvert \vec u_j \rvert + \sum_{j = 1}^{i - 1} \lvert \matice A_{ij} \rvert \lvert \vec v_j \rvert \right) \leq \frac{1}{\lvert \matice A_{ii} \rvert} \left( \sum_{j = i + 1}^n \lvert \matice A_{ij} \rvert + \lvert \vec v_i \rvert \sum_{j = 1}^{i - 1} \lvert \matice A_{ij} \rvert \right) = \sum_{j = i + 1}^n \frac{\lvert \matice A_{ij} \rvert}{\lvert \matice A_{ii} \rvert} + \lvert \vec v_i \rvert \sum_{j = 1}^{i - 1} \frac{\lvert \matice A_{ij} \rvert}{\lvert \matice A_{ii} \rvert} \]
Označíme \( a = \sum_{j = i + 1}^n \frac{\lvert \matice A_{ij} \rvert}{\lvert \matice A_{ii} \rvert} \) a \( b = \sum_{j = 1}^{i - 1} \frac{\lvert \matice A_{ij} \rvert}{\lvert \matice A_{ii} \rvert} \) a máme nerovnost
\[ \lvert \vec v_i \rvert \leq a + b \lvert \vec v_i \rvert \]
Zároveň ale díky tomu, že matice \( \matice A \) má převládající diagonálu, platí \( a + b < 1 \) a konečně můžeme odhadovat
\[ \lvert \vec v_i \rvert \leq \frac{a}{1 - b} < \frac{a}{a + b - b} = 1 \]
\end{proof}
\end{theorem}
 
\begin{theorem}
\label{KHermPDGaussSeidel}
Nechť je matice \( \matice A \) hermitovská a pozivně definitní. Pak Gaussova-Seidelova metoda pro soustavu lineárních rovnic \( \matice A \vec x = \vec b \) konverguje pro libovolné \( \vec x^{( 0 )} \) k \( \vec x \). Konvergence je navíc monotónní vzhledem k normě \( \lVert \, \cdot \, \rVert_{\matice A} \)
\begin{proof}
Upravíme předpis Gaussovy-Seidelovy metody do tvaru
\[ \vec x^{( k + 1 )} = ( \matice I - \left( \matice D - \matice L \right)^{-1} \matice A ) \vec x^{( k )} + \left( \matice D - \matice L \right)^{-1} \vec b \]
což je předpis předpodmíněné metody postupných aproximací s předpodmíněním \( \matice H = \left( \matice D - \matice L \right)^{-1} \). Díky hermitovskosti matice \( \matice A \) platí \( \matice L^* = \matice R \) a \( \matice D^* = \matice D \).  Potom můžeme využít \ref{KHermPDPredpodmineneAproximace} protože platí
\[ \matice H^{-1} + \left( \matice H^{-1} \right)^* = \matice D - \matice L + ( \matice D - \matice L )^* = \matice D - \matice L + \matice D - \matice R = \matice D + \matice A > \matice A \]
\end{proof}
\end{theorem}
 
\subsection{Super-relaxační metoda (SOR – Succesive Over Relaxation)}
Upravíme předpis pro Gaussovu-Seidelovu metodu do tvaru
\[ \vec x_i^{( k + 1 )} = \vec x_i^{( k )} + \Delta \vec x_i^{( k )} \]
Zavedeme tzv. \textbf{relaxační parametr} \( \omega \) a pozměníme předpis pro Gaussovu-Seidelovu metodu na
\[ \vec x_i^{( k + 1 )} = \vec x_i^{( k )} + \omega \Delta \vec x_i^{( k )} \]
Vidíme, že pro \( \omega = 1 \) super-relaxační metoda přechází v metodu Gaussovu-Seidelovu.
 
\begin{remark*}
Obdobnou modifikaci můžeme provést i pro Jacobiho metodu i pro Richardsonovy iterace.
\end{remark*}
 
\subsection{Super-relaxační metoda - numerická analýza}
Vyjádříme po složky vektoru \( \Delta \vec x^{( k )} \) z Gaussovy-Seidelovy metody jako
\[ \Delta \vec x_i^{( k )} = \vec x_i^{( k + 1 )} - \vec x_i^{( k )} = \frac{\vec b_i - \sum_{j = 1}^{i - 1} \matice A_{ij} \vec x_j^{( k + 1 )} - \sum_{j = i + 1}^n \matice A_{ij} \vec x_j^{( k )}}{\matice A_{ii}} - \vec x_i^{( k )} = \frac{\vec b_i - \sum_{j = 1}^{i - 1} \matice A_{ij} \vec x_j^{( k + 1 )} - \sum_{j = i}^n \matice A_{ij} \vec x_j^{( k )}}{\matice A_{ii}} \]
Nyní tento vztah použijeme pro super-relaxační metodu
\[ \vec x_i^{( k + 1 )} = \vec x_i^{( k )} + \frac{\omega}{\matice A_{ii}} \left( \vec b_i - \sum_{j = 1}^{i - 1} \matice A_{ij} \vec x_j^{( k + 1 )} - \sum_{j = i}^n \matice A_{ij} \vec x_j^{( k )} \right) \]
Použijeme stejného přepisu matice \( \matice A \) jako v případě Jacobiho metody a shrneme předpis pro prvky \( \vec x^{( k + 1 )} \) do jednoho vztahu
\[ \vec x^{( k + 1 )} = \vec x^{( k )} + \omega \matice D^{-1} \left( \vec b + \matice L \vec x^{( k + 1 )} + ( \matice R - \matice D ) \vec x^{( k )} \right) \]
který upravujeme
\[ \matice D \vec x^{( k + 1 )} - \omega \matice L \vec x^{( k + 1 )} = ( \matice D - \omega ( \matice D - \matice R ) ) \vec x^{( k )} + \omega \vec b \]
\[ \vec x^{( k+1 )} = ( \matice D - \omega \matice L )^{-1} ( \matice D - \omega ( \matice A + \matice L ) ) \vec x^{( k )} + \omega ( \matice D - \omega \matice L )^{-1} \vec b \]
\[ \vec x^{( k+1 )} = \left( \matice I - \omega ( \matice D - \omega \matice L )^{-1} \matice A \right) \vec x^{( k )} + \omega ( \matice D - \omega \matice L )^{-1} \vec b \]
Zjišťujeme, že super-relaxační metoda je vlastně předpodmíněnou metodou postupných aproximací, kde volíme
\[ \matice H = \omega ( \matice D - \omega \matice L )^{-1} \]
 
\setcounter{define}{27}
\begin{theorem}
\label{KSOR}
Super-relaxační metoda pro soustavu lineárních rovnic \( \matice A \vec x = \vec b \) konverguje pro libovolné \( \vec x^{( 0 )} \) k \( \vec x \) právě tehdy, když
\[ \rho \left( \matice B_\omega \right) < 1 \] 
kde jsem označili \[B_\omega = \matice I - \omega ( \matice D - \omega \matice L )^{-1} \matice A \]
\begin{proof}
Plyne z \ref{KStacionarniIterativniMetodySpektrum}.
\end{proof}
\end{theorem}
 
\begin{remark*}
Díky \ref{AbsEigenvalueVSNorma} je postačující podmínkou konvergence super-relaxační metody existence nějaké normy, pro kterou
\[ \left\lVert \matice B_\omega \right\rVert < 1 \]
\end{remark*}
 
\begin{theorem}
\label{NKSOR}
Pro každé \( \omega \in \mathbbm R \) platí
\[ \lvert \omega - 1 \rvert \leq \rho \left( \matice B_\omega \right) \]
a tedy super-relaxační metoda nemůže konvergovat pro \( \omega \in \mathbbm R \setminus \langle 0 , 2 \rangle  \)
\begin{proof}
Pro důkaz využijeme toho, že determinant nezávisí na volbě báze. Podle označení je \[\matice B_\omega = (\matice D - \omega \matice L)^{-1}\big[(1-\omega)\matice D + \omega \matice R\big] \]
Z Jordanovy věty zároveň víme: \[\matice A = (\matice T)^{-1} \matice {JT} \Rightarrow \det(\matice A) = \det(\matice J) = \prod_{i=1}^n \lambda_i\]
Aplikujeme tuto znalost na naši matici (členy determinantu za \(\matice L\) a \(\matice R\) vypadnou, neboť jsou to singulární matice:
\[\det(\matice B_{\omega}) = \frac{1}{\prod_{i=1}^n \matice A_{ii}} \prod_{i=1}^n (1-\omega) \matice A_{ii}} = (1-\omega)^n = \prod_{i=1}^n \lambda_i\]
Kde poslední rovnost plyne z Jordanovy věty a rozpisu nahoře. V absolutních hodnotách tedy máme: \[\lvert 1-\omega\rvert^n = \prod_{i=1}^n \lvert \lambda_i \rvert\]
Pak je splněno buď I) všechna \( \lambda_i \) jsou stejná, tj, \(\lvert 1-\omega\rvert^n = \lvert \lambda_i \rvert^n \) a tedy nastává rovnost \(\rho (\matice B_{\omega}) = \lvert \lambda_i \rvert \) 
anebo II) existuje takové \(\lambda_{i_1} \), že \(\lvert \lambda_{i_1} \rvert < \lvert 1-\omega \rvert\), pak ale musí zároveň existovat takové \(\lambda_{i_2}\), že \(\lvert \lambda_{i_2} \rvert > \lvert 1-\omega \rvert\) a nastává tudíž \(\rho (\matice B_{\omega}) \geq \lvert \lambda_{i_2} \rvert>\lvert \lambda_i \rvert \). Z věty \ref{KSOR} pak plyne divergence metody pro \( \omega \in \mathbbm R \setminus \langle 0 , 2 \rangle  \).
\end{proof}
\end{theorem}
 
\begin{theorem}
\label{KDiagSOR}
Nechť má matice \( \matice A \) převládající diagonálu a platí \( 0 < \omega \leq 1 \). Pak super-relaxační metoda pro soustavu lineárních rovnic \( \matice A \vec x = \vec b \) konverguje pro libovolné \( \vec x^{( 0 )} \) k \( \vec x \).
\begin{proof}
Oberhuber nezná.
\end{proof}
\end{theorem}
 
\begin{theorem}[Ostrowski]
\label{Ostrowski}
Nechť je matice \( \matice A \) hermitovská a pozivně definitní. Pak super-relaxační metoda pro soustavu lineárních rovnic \( \matice A \vec x = \vec b \) konverguje pro libovolné \( \vec x^{( 0 )} \) k \( \vec x \) právě tehdy, když
\[ 0 < \omega < 2 \]
Konvergence je navíc monotónní vzhledem k normě \( \lVert \, \cdot \, \rVert_{\matice A} \)
\begin{proof}
Upravíme předpis super-relaxační metody do tvaru
\[ \vec x^{( k + 1 )} = ( \matice I - \omega \left( \matice D - \omega \matice L \right)^{-1} \matice A ) \vec x^{( k )} + \omega \left( \matice D - \omega \matice L \right)^{-1} \vec b \]
což je předpis předpodmíněné metody postupných aproximací s předpodmíněním \( \matice H = \omega \left( \matice D - \omega \matice L \right)^{-1} \). Díky podmínce věty platí
\[ \frac{2}{\omega} - 1 > 0 \]
Díky hermitovskosti matice \( \matice A \) platí \( \matice L^* = \matice R \) a \( \matice D^* = \matice D \). Potom můžeme s využitím \ref{KHermPDPredpodmineneAproximace} dokázat \textbf{postačující podmínku}, protože platí
\[ \matice H^{-1} + \left( \matice H^{-1} \right)^* = \frac{1}{\omega} ( \matice D - \omega \matice L) + \frac{1}{\omega} ( \matice D - \omega \matice L )^* = \frac{1}{\omega} \matice D - \matice L + \frac{1}{\omega} \matice D - \matice R = \left( \frac{2}{\omega} - 1 \right) \matice D + \matice A > \matice A \]
\end{proof}
\end{theorem}
 
\setcounter{define}{37}
\begin{theorem}
\label{SORJacobiEigenvalue}
Nechť je matice \( \matice A \) dvoucyklická a shodně uspořádaná. Nechť dále \( \omega \neq 0 \) a \( \lambda \neq 0 \) a \( \matice B_\omega \in \mathbbm C^{n, n} \) je maticí super-relaxační metody a \( \matice B_J \in \mathbbm C^{n, n} \) je maticí Jacobiho metody. Nechť čísla \( \lambda \) a \( \mu \) splňují
\[ ( \lambda + \omega - 1 )^2 = \omega^2 \mu^2 \lambda \]
Pak \( \lambda \in \sigma ( \matice B_\omega ) \Leftrightarrow \mu \in \sigma ( \matice B_J ) \). Navíc platí, že pro
\[ \omega_{opt} = \frac{2}{1 + \sqrt{1 - \rho^2 ( \matice B_J ) }} \]
nabývá \( \rho( \matice B_\omega ) \) svého minima a super-relaxační metoda tedy konverguje nejrychleji.
\begin{proof}\renewcommand{\qedsymbol}{}
Bez důkazu.
\end{proof}
\end{theorem}
 
\subsection{Shrnutí podmínek konvergence}
~\\ ~\\
\begin{tabular}{c | c | c}
\textbf{Podmínka na matici} \( \matice A \) & Převládající diagonála & Hermitovská a pozitivně definitní \\ \hline
\textbf{Jacobiho metoda} & vždy & \( \matice A < 2 \matice D \) \\ \hline
\textbf{Gaussova-Seidelova metoda} & vždy & vždy \\ \hline
\textbf{Super-relaxační metoda} & \( 0 < \omega \leq 1 \) & \( 0 < \omega < 2 \) \\
\end{tabular}

Citováno z „https://wikiskripta.fjfi.cvut.cz/wiki/index.php?title=01NUM1:Kapitola5&oldid=7545“