01NM:Kapitola2: Porovnání verzí

Z WikiSkripta FJFI ČVUT v Praze
Přejít na: navigace, hledání
(odkaz na hlavičkovou stránku dokumentu)
(korekce u normy)
Řádka 50: Řádka 50:
 
Normou na prostoru čtvercových matic $n$-tého řádu $\mathbbm C^{n, n}$ nazýváme zobrazení $\nor{\text{ }}: \mathbbm C^{n, n} \rightarrow \mathbbm{R}^{+}$, které splňuje tyto vlastnosti:
 
Normou na prostoru čtvercových matic $n$-tého řádu $\mathbbm C^{n, n}$ nazýváme zobrazení $\nor{\text{ }}: \mathbbm C^{n, n} \rightarrow \mathbbm{R}^{+}$, které splňuje tyto vlastnosti:
 
\begin{enumerate}
 
\begin{enumerate}
\item $\nor{A} \ge 0 \Leftrightarrow A=0$,
+
\item $(\forall A\in\mathbbm C^{n, n})(\nor{A} \ge 0) \land \nor{A} = 0 \Leftrightarrow A=\vec{0}$,
 
\item $(\forall\lambda\in\mathbbm C)(\forall A\in\mathbbm C^{n, n})(\nor{\lambda A} = \abs{\lambda} \nor{A}$),
 
\item $(\forall\lambda\in\mathbbm C)(\forall A\in\mathbbm C^{n, n})(\nor{\lambda A} = \abs{\lambda} \nor{A}$),
 
\item $(\forall A\, B\in\mathbbm C^{n, n})(\nor{A+B}\le \nor{A}+\nor{B})$,
 
\item $(\forall A\, B\in\mathbbm C^{n, n})(\nor{A+B}\le \nor{A}+\nor{B})$,

Verze z 20. 4. 2010, 17:59

\section{Iterační metody řešení soustav lineárních algebraických rovnic} \subsection{Úvod} \subsubsection{Pojem limity v lineární algebře} \begin{define} \label{poslvek} Řekneme, že posloupnost vektorů $\{\vk x\}_{k=1}^{\infty}$, $\vk x = (x_1^{(k)}\,\hdots\,x_n^{(k)})^T$, konverguje k vektoru $\vec x = (x_1\,\hdots\,x_n)^T$ a píšeme $\vk x\rightarrow\vec x$ nebo $\lim_{k\rightarrow\infty} x^{(k)}=\vec x$, platí-li \[ (\forall i\in\hat n)(\lim_{k\rightarrow\infty} x_i^{(k)} = x_i). \] Řekneme, že posloupnost matic $\{A^{(k)}\}_{k=1}^{\infty}$ typu $(m\,n)$, $A^{(k)}=(a_{ij}^{(k)})$, konverguje k matici $A=(a_{ij})$ typu $(m\,n)$ a píšeme $A^{(k)}\rightarrow A$ nebo $\lim_{k\rightarrow\infty} A^{(k)}=A$, platí-li \[ (\forall i\in\hat n)(\forall j\in\hat m)(\lim_{k\rightarrow\infty} a_{ij}^{(k)} = a_{ij}). \] \end{define} \begin{remark} Přestože tato definice vypadá na první pohled jinak než definice limity posloupnosti v metrickém prostoru z matematické analýzy, jsou obě definice v daném případě ekvivalentní, jak za chvíli dokážeme. Nejprve však zavedeme následující značení norem na $\mathbbm C^{n, 1}$: %\begin{array}{lcll} %\end{array} \[ \norm{\vec x}=\max_{i\in\hat n} \abs{x_i} \;\;\; \text{(maximová norma)}, \] \[ \nor{\vec x}_{\text{II}}=\sum_{i=1}^n \abs{x_i} \;\;\; \text{(součtová norma)}, \] \[ \nor{\vec x}_{\text{III}}=\sqrt{\sum_{i=1}^n \abs{x_i}^2} \;\;\; \text{(eukleidovská norma)}. \] \end{remark} \begin{theorem} Buďte $\{\vk x\}$ posloupnost vektorů v $\mathbbm C^{n, 1}$, $\vec x\in\mathbbm C^{n, 1}$. \begin{enumerate} \item Je-li $\vk x\rightarrow\vec x$, potom v každé normě platí $\nor{\vk x - \vec x}\rightarrow 0$. \item Platí-li v některé normě $\nor{\vk x - \vec x}\rightarrow 0$, potom $\vk x\rightarrow\vec x$. \end{enumerate} \begin{proof} \begin{enumerate} \item Z definice \ref{poslvek} je zřejmé, že platí \[ \left ( \vk x\rightarrow\vec x \right ) \Rightarrow \left ( \norm{\vk x - \vec x}\rightarrow 0 \right ). \] Protože jsou všechny normy $\mathbbm C^{n, 1}$ ekvivalentní, platí pro libovolnou normu $\nor{\vk x- \vec x}\le K \norm{\vk x - \vec x}\rightarrow 0$. \item Z ekvivalence norem $\mathbbm C^{n, 1}$ a z definice maximové normy plyne \[ (\forall i\in\hat n)\left ( \abs{x_i^{(k)} - x_i} \le \norm{\vk x- \vec x}\le K \nor{\vk x - \vec x}\rightarrow 0\right ). \] \end{enumerate} \end{proof} \end{theorem} \begin{define} Normou na prostoru čtvercových matic $n$-tého řádu $\mathbbm C^{n, n}$ nazýváme zobrazení $\nor{\text{ }}: \mathbbm C^{n, n} \rightarrow \mathbbm{R}^{+}$, které splňuje tyto vlastnosti: \begin{enumerate} \item $(\forall A\in\mathbbm C^{n, n})(\nor{A} \ge 0) \land \nor{A} = 0 \Leftrightarrow A=\vec{0}$, \item $(\forall\lambda\in\mathbbm C)(\forall A\in\mathbbm C^{n, n})(\nor{\lambda A} = \abs{\lambda} \nor{A}$), \item $(\forall A\, B\in\mathbbm C^{n, n})(\nor{A+B}\le \nor{A}+\nor{B})$, \item $(\forall A\, B\in\mathbbm C^{n, n})(\nor{AB}\le \nor{A}.\nor{B})$. \end{enumerate} \end{define} \begin{define} Norma $\nor{\text{ }}_M$ na $\mathbbm C^{n, n}$ se nazývá souhlasná s normou $\nor{\text{ }}_V$ na $\mathbbm C^{n, 1}$, jestliže platí \[ (\forall A\in\mathbbm C^{n, n})(\forall \vec x\in\mathbbm C^{n, 1})(\nor{A\vec x}_V \le \nor{A}_M . \nor{\vec x}_V). \] \end{define} \begin{define} Normu $\nor{\text{ }}_M$ na $\mathbbm C^{n, n}$ nazýváme normou generovanou (přidruženou) normou (normě) $\nor{\text{ }}_V$ na $\mathbbm C^{n, 1}$, jestliže platí \[ (\forall A\in\mathbbm C^{n, n})(\forall \vec x\in\mathbbm C^{n, 1})(\nor{A}_M = \max_{\nor{\vec x}=1} \nor{A\vec x}_V). \] \end{define} \begin{remark} Norma generovaná je normou souhlasnou. Definice generované normy je v souhlase s definicí normy spojitého lineárního zobrazení z matematické analýzy, pouze zde vystupuje maximum místo suprema. Je tomu tak proto, že jde o supremum spojité funkce na kompaktní množině. \begin{proof} \begin{enumerate} \item Kompaktnost: Množina $\{\;\vec x\in\mathbbm C^{n, 1}\; | \;\nor{\vec x}=1\;\}$ je uzavřená a omezená, neboť je hranicí koule $B(\vec o\, 1)$ a hranice každé množiny je uzavřená. Množina v lineárním prostoru konečné dimenze je kompaktní, právě když je omezená a uzavřená. \item Spojitost: Zobrazení $\vec x\mapsto\nor{A\vec x}$ je kompozicí dvou zobrazení $A:\vec x\mapsto A\vec x$ a $\nor{\text{ }}:\vec y\mapsto\nor{\vec y}$. Spojitost zobrazení $A$ byla dokázána v matematické analýze. Dokážeme, že zobrazení $\nor{\text{ }}$ je spojité, a to dokonce stejnoměrně: \newline Chceme dokázat, že \[ (\forall \epsilon\in\mathbbm{R}^{+})(\exists\delta\in\mathbbm{R}^{+})(\forall \vec x\, \vec y\in\mathbbm C^{n, 1})(\nor {\vec x-\vec y}<\delta \Rightarrow \abs{\;\nor{\vec x}-\nor{\vec y}\;}<\epsilon). \] Pro každé dva vektory $\vec x\, \vec y\in\mathbbm C^{n, 1}$ můžeme bez újmy na obecnosti předpokládat, že $\nor{\vec x}\ge\nor{\vec y}$. Platí-li $\nor {\vec x-\vec y}<\delta$, můžeme tedy psát $\abs{\;\nor{\vec x}-\nor{\vec y}\;}=$ $=\nor{\vec x}-\nor{\vec y}=\nor{\vec x-\vec y+\vec y}-\nor{\vec y}\le \nor{\vec x-\vec y}+\nor{\vec y}-\nor{\vec y}=\nor{\vec x-\vec y}<\delta.$ \linebreak[4]Nyní stačí položit $\delta=\epsilon$. \end{enumerate} \end{proof} \end{remark} \subsubsection{Princip iteračních metod} Je dána soustava $A\vec x=\vec f$, kde $A$ je regulární. V iteračních metodách konstruujeme iterační posloupnost vektorů $\{\vk x\}_{k=0}^{\infty}$. Má-li matice $A$ příznivé vlastnosti, konverguje tato posloupnost k řešení soustavy $\vec x^*$. Výchozí vektor $\vec x^{(0)}$ této posloupnosti se volí libovolně (nejvýhodnější ovšem je zvolit za $\vec x^{(0)}$ nějakou aproximaxi $\vec x^*$). Další členy posloupnosti se vypočítávají ze vztahu \begin{equation} \label{iter} \vec x^{(k+1)}=\vk x+H^{(k+1)} (\vec f-A \vk x), \end{equation} kde $\{H^{(k)}\}_{k=1}^{\infty}$ je vhodně zvolená posloupnost matic. Vektor $\vec f-A \vk x$ nazýváme reziduum. Navíc chceme, aby platilo \[ (\forall k\in\N)(\vec x^*=\vec x^* + H^{(k)} (\vec f-A \vec x^*)). \] Odečtením této rovnice od (\ref{iter}) získáme výraz pro chybu $k$-té aproximace \[ \vk x-\vec x^*=\vec x^{(k-1)} - \vec x^* + H^{(k)} A(\vec x^*-\vec x^{(k-1)})=(I-H^{(k)} A)(\vec x^{(k-1)}-\vec x^*)= \] \[

(I-H^{(k)} A)(I-H^{(k-1)} A)(\vec x^{(k-2)}-\vec x^*)=\hdots

\] \[ =\underbrace{(I-H^{(k)} A)(I-H^{(k-1)} A)\hdots(I-H^{(1)} A)}_{\text{ozn. }T^{(k)}}(\vec x^{(0)}-\vec x^*). \] Právě jsme dokázali následující větu: \begin{theorem} \label{kritkonv} Iterační posloupnost $\{\vk x\}_{k=0}^{\infty}$ konverguje k řešení soustavy $A\vec x=\vec f$ při libovolné volbě $\vec x^{(0)}$ právě tehdy, když platí \[ \lim_{k\rightarrow\infty} T^{(k)}=O. \] \end{theorem} \begin{remark} Iterační metody se vyznačují odolností vůči chybám vzniklým zaokrouhlováním. Tato samoopravná schopnost je dána tím, že dojde-li v při výpočtu jistého vektoru $\vec x^{(k)}$ iterační posloupnosti k chybě, můžeme na tento vektor pohlížet jako na výchozí člen $\vec x^{(0)}$ nové iterační posloupnosti. \end{remark} \subsubsection{Nestacionární metody} Iterační metody se dělí na stacionární, kde je posloupnost matic $\{H^{(k)}\}_{k=1}^{\infty}$ konstantní, a nestacionární. Příkladem metody nestacionární budiž metoda řízené relaxace (nevyžaduje se, následující věta však bude užitečná i dále). \begin{theorem} U soustavy lineárních alebraických rovnic s regulární maticí lze rovnice vždy přerovnat tak, aby diagonální prvky byly nenulové. \begin{proof} Plyne z definice determinantu \begin{equation} \label{defdet} \det A=\sum_{\pi\in S_n}\text{ sgn }\pi .\; a_{\pi(1)1}\hdots a_{\pi(n)n} \end{equation} a z toho, že determinant regulární matice je různý od nuly. Potom totiž musí být alespoň jeden sčítanec v (\ref{defdet}) nenulový, tj. $(\exists \pi\in S_n)(a_{\pi(1)1}\hdots a_{\pi(n)n}\ne 0)$. Proto stačí dát na první místo $\pi(1)$-tou rovnici, na druhé $\pi(2)$-tou atd. \end{proof} \end{theorem} Předpokládejme, že matice soustavy $A\vec x=\vec f$ má na diagonále jedničky. Z definice rezidua je zřejmé, že je-li $j$-tá složka rezidua nulová, je splněna $j$-tá rovnice soustavy. Označme $i$ index v absolutní hodnotě největší složky rezidua $\vec f-A\vk x$. (Je-li jich více, je jedno, kterou zvolíme.) Chceme, aby reziduum v následující iteraci $\vec f-A\vec x^{(k+1)}$ mělo $i$-tou složku rovnou nule, tj. aby platilo \[ f_i-(a_{i1} x_1^{(k+1)} + \hdots + a_{ii-1} x_{i-1}^{(k+1)} + x_i^{(k+1)} + a_{ii+1} x_{i+1}^{(k+1)} + \hdots + a_{in} x_n^{(k+1)})=0, \] a proto klademe \[ x_i^{(k+1)}=f_i-(a_{i1} \K x_1 + \hdots + a_{ii-1} \K x_{i-1} + a_{ii+1} \K x_{i+1}+\hdots+a_{in} \K x_n)= \] \[ =\K x_i + [f_i-(a_{i1} \K x_1 + \hdots + a_{ii-1} \K x_{i-1} + \K x_i + a_{ii+1} \K x_{i+1} + \hdots + a_{in} \K x_n)], \] \[ x_j^{(k+1)}=\K x_j\text{ pro }j\ne i. \] Porovnáním první z těchto dvou rovnic s (\ref{iter}) zjistíme, že příslušná matice $H^{(k+1)}$ má v $i$-tém řádku na $i$-tém místě jedničku a na ostatních místech nuly. Z druhé rovnice pak vyplývá, že všechny ostatní řádky matice $H^{(k+1)}$ jsou nulové. Z toho je zřejmé, že pro $k\ne l$ budou matice $H^{(k)}\, H^{(l)}$ obecně různé. \subsection{Stacionární metody} Dále se budeme zabývat pouze stacionárními metodami, neboť jsou algoritmicky výhodnější a jejich chování lze snáze analyzovat. \subsubsection{Konvergence iterační posloupnosti} Protože ve stacionárních metodách platí $(\forall k\in\N)(H^{(k)}=H)$, znamená to, že $(\forall k\in\N)(T^{(k)}=(I-HA)^k)$ a kritérium konvergence z věty \ref{kritkonv} přechází ve tvar \[ \lim_{k\rightarrow\infty} (I-HA)^k=O. \] \begin{theorem} \label{nppkgpm} Buď $A\in\mathbbm C^{n, n}$. Potom platí \[ \lim_{k\rightarrow\infty} A^k=O \Leftrightarrow \rho(A)<1, \] kde $\rho(A)$ je spektrální poloměr matice $A$. \begin{proof} Podle Jordanovy věty existuje regulární matice $C$ a blokově diagonální matice \[ J=\left( \begin{matrix} J_1\\ & \ddots\\ & & J_s \end{matrix} \right)\, J_i=\left( \begin{matrix} \lambda\\ 1 & \ddots\\ & \ddots & \ddots\\ & & 1& \lambda \end{matrix} \right), \] tak, že $A=C^{-1}JC$. Odtud $A^k=C^{-1}J^kC$, takže $A^k\rightarrow O\Leftrightarrow J^k\rightarrow O$. Zřejmě platí \[ J^k=\left( \begin{matrix} J_1^k\\ & \ddots\\ & & J_s^k \end{matrix} \right). \] Na cvičení se matematickou indukcí dokazovalo, že \[ J_i^k=\left( \begin{matrix} \lambda^k\\ \kcislo{k}{1}\lambda^{k-1} & \lambda^k\\ \kcislo{k}{2}\lambda^{k-2} & \kcislo{k}{1}\lambda^{k-1}& \lambda^k\\ \vdots & \vdots & \vdots & \ddots\\ \kcislo{k}{p-1}\lambda^{k-p+1} & \kcislo{k}{p-2}\lambda^{k-p+2} & \kcislo{k}{p-3}\lambda^{k-p+3} & \hdots & \lambda^k \end{matrix} \right), \] kde $p$ je rozměr bloku $J_i$ a pro $i>k$ klademe $\kcislo{k}{i}=0$. Odtud je zřejmé, že platí $J_i^k\rightarrow 0\Leftrightarrow\abs\lambda<1$. \end{proof} \end{theorem} \begin{dusl} Iterační posloupnost (\ref{iter}) konverguje při libovolné volbě $\vec x^{(0)}$ právě tehdy, je-li $\rho(I-HA)<1$. \end{dusl} \begin{theorem} Buď $A\in\mathbbm C^{n, n}$ a nechť alespoň v jedné normě $\mathbbm C^{n, n}$ platí $\nor{A}<1$. Potom $A^k\rightarrow O$. \begin{proof} Ze čtvrté vlastnosti maticové normy vyplývá $\nor{A^k}\le\nor{A}^k$. \end{proof} \end{theorem} \begin{dusl} Nechť v některé maticové normě platí $\nor{I-HA}<1$. Potom iterační posloupnost (\ref{iter}) konverguje při libovolné volbě $\vec x^{(0)}$. \end{dusl} \begin{theorem} Absolutní hodnota každého vlastního čísla matice (spektrální poloměr) je nejvýše rovna její libovolné normě. \end{theorem} \subsubsection{Metoda postupných aproximací} Rovnici $A\vec x=\vec f$ přepíšeme do tvaru \[ \vec o=\vec f - A\vec x \] a k oběma stranám rovnosti přičteme $\vec x$. Vzniklou rovnost oindexujeme takto: \begin{equation} \label{mpa} \vec x^{(k+1)}=\vk x+I(\vec f-A\vk x). \end{equation} Porovnáním s (\ref{iter}) zjistíme, že při metodě postupných aproximací je $H=I$. \begin{kriterkonv} Posloupnost (\ref{mpa}) konverguje pro každou volbu $\vec x^{(0)}$ $\Leftrightarrow \rho(I-A)<1$, postačující podmínka je $\nor{I-A}<1$. \end{kriterkonv} \begin{lemma} Je-li $\rho(B)<1$, potom je matice $I-B$ regulární. \begin{proof} Buď $\rho(B)<1$. Na cvičení se dokazovalo, že k libovolné čtvercové matici $B$ existují unitární matice $\Omega$ a horní trojúhelníková matice $R$ tak, že $B=\Omega^HR\;\Omega$. Matice $B$ je tedy podobná trojúhelníkové matici $R$, takže diagonální prvky matice $R$ jsou vlastními čísly matice $B$. Podle předpokladu jsou všechny tyto prvky v absolutní hodnotě menší než 1. Z toho vyplývá, že $I-R$ je horní trojúhelníková matice, jejíž všechny diagonální prvky jsou nenulové. Protože ale platí $I-B=$ $=\Omega^H\Omega-\Omega^HR\;\Omega=\Omega^H(I-R)\;\Omega$, musí být matice $I-B$ regulární. \end{proof} \end{lemma} \begin{remark} Předchozí lemma zjednodušeně řečeno říká, že matice, která ,,se příliš neliší" od jednotkov\' e matice, je regulární. \end{remark} \begin{lemma}[,,geometrická řada matic"] Buď $\rho(B)<1$. Potom platí \[ (I-B)^{-1}=I+B+B^2+\hdots+B^k+\hdots, \] tj. označíme-li $S_m=I+B+B^2+\hdots+B^m$, potom $S_m\stackrel{m\rightarrow\infty}{\longrightarrow}(I-B)^{-1}$. \begin{proof} Zřejmě platí $S_m(I-B)=I-B^{m+1}$. Matice $I-B$ je podle předchozí lemmy regulární, a tak můžeme tento vztah zprava vynásobit maticí $(I-B)^{-1}$. Dostaneme $S_m=(I-B)^{-1}-B^{m+1}(I-B)^{-1}$. Zlimicením získáme tvrzení. \end{proof} \end{lemma} \begin{theorem} Buď $\nor{\text{ }}$ libovolná norma $\mathbbm C^{n, 1}$ a nechť $\nor{\text{ }}$ značí i touto normou generovanou normu $\mathbbm C^{n, n}$. Je-li $\nor{I-A}<1$, potom platí \[ \nor{\vk x-\vec x^{*}}\le \nor{I-A}^k\left ( \nor{\vec x^{(0)}}+\frac{\nor{\vec f}}{1-\nor{I-A}}\right ) . \] \begin{proof} Označme $B=I-A$. Potom podle (\ref{mpa}) platí $\vk x=B\vec x^{(k-1)}+\vec f=$\linebreak[4]$=B(B\vec x^{(k-2)}+\vec f)+\vec f=B^2\vec x^{(k-2)}+B\vec f+\vec f=B^2\vec x^{(k-2)}+(B+I)\vec f=$\linebreak[4]$=B^3\vec x^{(k-3)}+(B^2+B+I)\vec f=\hdots=B^k\vec x^{(0)}+(B^{k-1}+B^{k-2}+\hdots+B+I)\vec f$.

Pro přesné řešení platí $A\vec x^*=\vec f$, takže \[ \vec x^*=A^{-1}\vec f=(I-B)^{-1}\vec f=(I+B+B^2+\hdots)\vec f. \] Z předchozích dvou vztahů plyne \[ \nor{\vk x-\vec x^*}=\nor{B^k\vec x^{(0)}-(B^k+B^{k+1}+B^{k+2}+\hdots)\vec f}\le \] \[ \le\nor{B^k}\left(\nor{\vec x^{(0)}}+\nor{I+B+B^2+\hdots}\nor{\vec f}\right)\le \] \[ \le\nor{B^k}\left(\nor{\vec x^{(0)}}+(\nor I+\nor B+\nor{B^2}+\hdots)\nor{\vec f}\right)\le \] \[ \le\nor B^k\left(\nor{\vec x^{(0)}}+(1+\nor B+\nor B^2+\hdots)\nor{\vec f}\right)=\nor B^k\left(\nor{\vec x^{(0)}}+\frac{\nor{\vec f}}{1-\nor B}\right). \] \end{proof} \end{theorem} \begin{remark} Na každou stacionární iterační metodu lze pohlížet jako na metodu postupných aproximací aplikovanou na soustavu $HA\vec x=H\vec f$. \begin{proof} Postupujme stejně jako na začátku: $\vec o=H\vec f-HA\vec x$ a odtud \[ \vec x^{(k+1)}=\vk x + I(H\vec f-HA\vec x)=\vk x + H(\vec f-A\vec x). \] \end{proof} \end{remark} \begin{remark} V následujících dvou odstavcích budeme symbolem $(\vec x\, \vec y)$ označovat standardní skalární součin na $\mathbbm C^{n, 1}$. Připomeňme, že pro tento skalární součin platí $(\vec x\, \vec y)=\vec y^H\vec x$. \end{remark} \subsubsection{Jacobiho metoda (prosté iterace)} Jednotlivé rovnice soustavy $A\vec x=\vec f$ přepíšeme tak, že z první vyjádříme $x_1$, ze druhé $x_2$ atd. Získané rovnice oindexujeme takto: \[ \begin{matrix} x_1^{(k+1)} & = & & -\frac{a_{12}}{a_{11}} \K{x_2} & -\frac{a_{13}}{a_{11}} \K{x_3} & - & \hdots & -\frac{a_{1n}}{a_{11}} \K{x_n} & +\frac{f_1}{a_{11}}\\ x_2^{(k+1)} & = & -\frac{a_{21}}{a_{22}} \K{x_1} & & -\frac{a_{23}}{a_{22}} \K{x_3} & - & \hdots & -\frac{a_{2n}}{a_{22}} \K{x_n} & +\frac{f_2}{a_{22}}\\ \vdots & & \vdots & \vdots & \vdots & & & \vdots & \vdots\\ x_n^{(k+1)} & = & -\frac{a_{n1}}{a_{nn}} \K{x_1} & -\frac{a_{n2}}{a_{nn}} \K{x_2} & -\frac{a_{n3}}{a_{nn}} \K{x_3} & - & \hdots & & +\frac{f_n}{a_{nn}} \end{matrix} \] To je ovšem po složkách rozepsaný vztah $\vec x^{(k+1)}=(I-D^{-1}A)\vk x+D^{-1}\vec f$, kde \[ D= \left ( \begin{matrix} a_{11}\\ & \ddots\\ & & a_{nn} \end{matrix} \right ). \] Odtud vyplývá $\vec x^{(k+1)}=\vk x+D^{-1}(\vec f-A\vec x)$, takže $H=D^{-1}$. \begin{kriterkonv} Jacobiho metoda konverguje při každé volbě $\vec x^{(0)}$ $\Leftrightarrow \rho(I-D^{-1}A)<1$, postačující podmínka je $\nor{I-D^{-1}A}<1$. Vezmeme-li maximovou normu, přejde poslední vztah ve \[ \max_{i\in\hat n} \sum_{j=1\, j\ne i}^n \abs{\frac{a_{ij}}{a_{ii}}} < 1 \Leftrightarrow (\forall i\in\hat n)\left ( \sum_{j=1\, j\ne i}^n \abs{\frac{a_{ij}}{a_{ii}}} < 1 \right ) \Leftrightarrow (\forall i\in\hat n) \left ( \sum_{j=1\, j\ne i}^n \abs{a_{ij}} < \abs{a_{ii}}\right ) . \] Matice, pro které platí poslední nerovnost, nazýváme maticemi s převládající diagonálou. Jacobiho metoda tedy konverguje pro všechny matice s převládající diagonálou. \end{kriterkonv} \begin{define} \label{pozdef} Hermitovská, resp. symetrická matice $A$ se nazývá pozitivně definitní, jestliže pro každý vektor, resp. každý reálný vektor $\vec x\ne\vec o$ platí $(A\vec x\, \vec x)>0$. \end{define} \begin{theorem} \begin{enumerate} \item Všechna vlastní čísla pozitivně definitní matice jsou kladná. \item Má-li hermitovská matice všechna vlastní čísla kladná, potom je pozitivně definitní. \end{enumerate} \begin{proof} \begin{enumerate} \item Buďte $A$ pozitivně definitní matice, $\lambda$ její libovolné vlastní číslo a $\vec x$ libovolný k němu příslušející vlastní vektor. Vztah $A\vec x=\lambda\vec x$ vynásobíme skalárně vektorem $\vec x$ a dostaneme \[ \underbrace{(A\vec x\, \vec x)}_{>0}=\lambda\underbrace{(\vec x\, \vec x)}_{>0}\Rightarrow\lambda >0. \] \item Buď $A$ hermitovská matice, jejíž všechna vlastní čísla jsou kladná. Na cvičeních se dokazovalo, že pro každou normální (a tím spíše hermitovskou) matici $A$ existuje unitární matice $\Omega$ a diagonální matice $D$ tak, že $A=\Omega^HD\;\Omega$. Označíme-li $\lambda_1\, \hdots\, \lambda_n$ vlastní čísla matice $A$, potom \[ D= \left ( \begin{matrix} \lambda_1\\ & \ddots\\ & & \lambda_n \end{matrix} \right ). \] Buď $\vec x\ne\vec o$. Potom $(A\vec x\, \vec x)=\vec x^HA\vec x=\vec x^H\Omega^HD\;\Omega\vec x$. Označme $\vec y=\Omega\vec x$. Je $\vec y\ne\vec o$, protože jinak by byl vektor $\vec x$ netriviálním řešením homogenní soustavy s regulární maticí, a platí \[ (A\vec x\, \vec x)=\vec y^HD\vec y=\sum_{i=1}^n\lambda_i\abs{y_i}^2>0, \] neboť všechny sčítance v sumě jsou nezáporné a alespoň jeden z nich je jistě kladný. \end{enumerate} \end{proof} \end{theorem} \begin{theorem} Buď $A$ hermitovská matice s kladnými diagonálními prvky. Potom Jacobiho metoda pro soustavu $A\vec x=\vec f$ konverguje při každé volbě $\vec x^{(0)}$ právě tehdy, jsou-li obě matice $A\, 2D-A$ pozitivně definitní. \begin{proof} Dokážeme pouze nutnost podmínky. Důkaz opačné implikace se provede stejně, ale v opačném pořadí. Označme \[ P=\left( \begin{matrix} \sqrt{a_{11}}\\ &\ddots\\ &&\sqrt{a_{nn}}\\ \end{matrix} \right). \] Je tedy $P^2=D$. Dále platí $I-D^{-1}A=P^{-1}(I-P^{-1}AP^{-1})P$, tedy matice $I-D^{-1}A$ je podobná matici $I-P^{-1}AP^{-1}$. Tato matice je zřejmě hermitovská, a má proto všechna vlastní čísla reálná. Podle předpokladu je $\rho(I-D^{-1}A)<1$, a tak jsou tato čísla z intervalu $(-1\, 1)$.

Buď $\lambda$ vlastní číslo matice $I-D^{-1}A$. Potom existuje vektor $\vec x\ne\vec o$ takový, že $(I-D^{-1}A)\vec x=\lambda\vec x$, takže $D^{-1}A\vec x=(1-\lambda)\vec x$. Vlastní čísla matice $D^{-1}A$ jsou tedy z intervalu $(0\, 2)$. Protože platí $D^{-1}A=P^{-1}(P^{-1}AP^{-1})P$, znamená to, že matice $P^{-1}AP^{-1}$ je pozitivně definitní.

Buď $\vec x\ne\vec o$. Potom \[ (A\vec x\, \vec x)=\vec x^HA\vec x=\vec x^HPP^{-1}AP^{-1}\underbrace{P\vec x}_{\text{ozn. }\vec y}=\vec y^HP^{-1}AP^{-1}\vec y=((P^{-1}AP^{-1})\vec y\, \vec y). \] Stejně jako v důkaze předchozí věty dostaneme $\vec y\ne\vec o$. Podle definice \ref{pozdef} je tedy poslední výraz kladný a matice $A$ je pozitivně definitní.

Obdobně postupujeme i při důkazu pozitivní definitnosti matice $2D-A$:

Buďte opět $\lambda$ vlastní číslo matice $I-D^{-1}A$ a $\vec x$ příslušný vlastní vektor. Potom $(2I-D^{-1}A)\vec x=(1+\lambda)$, a tak jsou všechna vlastní čísla matice $2I-D^{-1}A$ z intervalu $(0\, 2)$. Protože platí $2I-D^{-1}A=P^{-1}(2I-P^{-1}AP^{-1})P$, znamená to, že matice $2I-P^{-1}AP^{-1}$ je pozitivně definitní.

Buď $\vec x\ne\vec o$. Potom \[ ((2D-A)\vec x\, \vec x)=\vec x^H(2D-A)\vec x=\vec x^HPP^{-1}(2D-A)P^{-1}\underbrace{P\vec x}_{\text{ozn. }\vec y}= \] \[ =\vec y^H(2P^{-1}P^2P^{-1}-P^{-1}AP^{-1})\vec y=((2I-P^{-1}AP^{-1})\vec y\, \vec y). \] Přitom opět $\vec y\ne\vec o$, takže podle definice \ref{pozdef} je poslední výraz kladný. Matice $2D-A$ je tedy pozitivně definitní. \end{proof} \end{theorem} \subsubsection{Gaussova-Seidelova metoda} V Jacobiho metodě se všechny složky vektoru $\vec x^{(k+1)}$ počítají ze složek vektoru $\vk x$. Vzniká přirozená otázka, zda by se (alespoň v některých případech) nedosáhlo zlepšení, kdyby se při tomto výpočtu použily již známé složky vektoru $\vec x^{(k+1)}$. Touto úvahou dospějeme ke vzorcům \[ \begin{array}{ccc} a_{11}x_1^{(k+1)}+a_{12}\K{x_2}+\hdots+a_{1n}\K{x_n} & = & f_1\\ a_{21}x_1^{(k+1)}+a_{22}x_2^{(k+1)}+\hdots+a_{1n}\K{x_n} & = & f_2\\ \vdots & & \vdots\\ a_{n1}x_1^{(k+1)}+a_{n2}x_2^{(k+1)}+\hdots+a_{nn}x_n^{(k+1)} & = & f_n\\ \end{array} \] Jak tyto vztahy zapsat vektorově? Ponechme si matici $D$ z předchozího odstavce a navíc definujme \[ L= \left( \begin{matrix} 0\\ -a_{21} & 0\\ \vdots & \vdots & \ddots\\ -a_{n1} & -a_{n2} & \hdots & 0\\ \end{matrix} \right) \, R= \left( \begin{matrix} 0 & \hdots & -a_{1n-1} & -a_{1n}\\ & \ddots & \vdots & \vdots\\ & & 0 & -a_{n-1n}\\ & & & 0 \end{matrix} \right). \] Potom zřejmě platí $A=-L+D-R$ a $(-L+D)\vec x^{(k+1)}-R\vk x=\vec f$, takže \[ \vec x^{(k+1)}=(D-L)^{-1} R \vk x+(D-L)^{-1}\vec f. \] Do této rovnice dosadíme $R=D-L-A$ a dostaneme \[ \vec x^{(k+1)}=\vk x+(D-L)^{-1}(\vec f-A\vk x), \] odkud porovnáním s (\ref{iter}) plyne $H=(D-L)^{-1}$. \begin{kriterkonv} Platí $I-(D-L)^{-1}A=I-(D-L)^{-1}[(D-L)-R]=(D-L)^{-1}R$. Metoda tedy konverguje při libovolné volbě $\vec x^{(0)}$ $\Leftrightarrow \rho((D-L)^{-1}R)<1$, postačující podmínkou je $\nor{(D-L)^{-1}R}<1$. \end{kriterkonv} \begin{tvrz} Gaussova-Seidelova metoda konverguje pro matice s převládající diagonálou. \end{tvrz} \begin{theorem} Je-li matice soustavy pozitivně definitní, pak Gaussova-Seidelova metoda konverguje při libovolné volbě $\vec x^{(0)}$. \begin{proof} Buď $A$ pozitivně definitní matice a nechť $A=-L+D-R$. Podle definice je matice $A$ hermitovská, takže $(-L+D-R)^H=-L+D-R$. Protože $A^H=\overline A^T$, musí nutně platit $L=R^H$. Chceme dokázat, že $\rho((D-R^H)^{-1}R)<1$. Buďte $\lambda$ vlastní číslo matice $(D-R^H)^{-1}R$, $\vec x$ k němu příslušející vlastní vektor. Vztah $(D-R^H)^{-1}R\vec x=\lambda\vec x$ vynásobíme zleva maticí $D-R^H$ a dostaneme \[ R\vec x=\lambda(D-R^H)\vec x=\lambda (A+R)\vec x=\lambda A\vec x+\lambda R\vec x. \] Odtud po skalárním vynásobení vektorem $\vec x$ plyne \[ (R\vec x\, \vec x)=\lambda\underbrace{(A\vec x\, \vec x)}_{\text{ozn. }p}+\lambda(R\vec x\, \vec x). \] Podle definice \ref{pozdef} je $p>0$. Položme $(R\vec x\, \vec x)=a+\text{i}b$, kde $a\, b\in\mathbbm R$. Potom \[ \lambda=\frac{a+\text{i}b}{p+a+\text{i}b}\, \abs{\lambda}^2=\frac{a^2+b^2}{(p+a)^2+b^2}. \] Dále platí $p=(A\vec x\, \vec x)=((-R^H+D-R)\vec x\, \vec x)=-(R^H\vec x\, \vec x)+\underbrace{(D\vec x\, \vec x)}_{\text{ozn. }d}-(R\vec x\, \vec x)=$ $=d-(\vec x\, R\vec x)-(a+\text{i}b)=d-\overline{(R\vec x\, \vec x)}-(a+\text{i}b)=d-(a-\text{i}b)-(a+\text{i}b)=d-2a$.

Máme dokázat, že $\abs{\lambda}^2<1$. Pozitivně definitní matice má všechny diagonální prvky kladné, neboť $[A]_{ii}=(A\vec e^{(i)}\, \vec e^{(i)})>0$. Odtud plyne $d>0$, protože \[ d=(D\vec x\, \vec x)=\sum_{i=1}^n a_{ii}\abs{x_i}^2. \] Je tedy $(p+a)^2=p^2+2pa+a^2=p(p+2a)+a^2=pd+a^2$\, a tak $\abs{\lambda}^2<1$. \end{proof} \end{theorem} \begin{remark} Gaussova-Seidelova metoda je stejně časově náročná jako Jacobiho metoda. Paměťové nároky jsou menší: Nově vypočítanými složkami vektoru $\vec x^{(k+1)}$ můžeme ihned přepisovat složky původní, takže je nemusíme ukládat do zvláštního pole. Obecně Gaussova-Seidelova metoda nekonverguje rychleji než Jacobiho metoda. \end{remark} \subsubsection{Superrelaxační metoda (Succesive OverRelaxation method)} Výpočet vektoru $\vec x^{(k+1)}$ v Gaussově-Seidelově metodě můžeme chápat jako složený z $n$ dílčích kroků, přičemž v $i$-tém kroku se $i$-tá složka vektoru $\vk x$ opraví o tolik, aby byla splněna $i$-tá rovnice soustavy, tj. $x_i^{(k+1)}=x_i^{(k)}+\Delta x_i^{(k)}$, kde \[ \Delta x_i^{(k)}=\frac{1}{a_{ii}} (f_i-a_{i1}x_1^{(k+1)}-\hdots-a_{ii-1}x_{i-1}^{(k+1)}-a_{ii}x_i^{(k)}-\hdots-a_{in}x_n^{(k)}). \] Položme si otázku, zda bychom nedostali lepší metodu, kdybychom ke každé složce připočítávali jen konstantní násobek tohoto výrazu, tj. $x_i^{(k+1)}=x_i^{(k)}+\omega\Delta x_i^{(k)}$, \linebreak[4]kde $\omega\in\mathbbm{R}$. Potom $\forall i\in\hat n$ platí \[ x_i^{(k+1)}=x_i^{(k)}+\frac{\omega}{a_{ii}} (f_i-a_{i1}x_1^{(k+1)}-\hdots-a_{ii-1}x_{i-1}^{(k+1)}-a_{ii}x_i^{(k)}-\hdots-a_{in}x_n^{(k)}), \] \[ a_{ii}x_i^{(k+1)}=a_{ii}x_i^{(k)}+\omega (f_i-a_{i1}x_1^{(k+1)}-\hdots-a_{ii-1}x_{i-1}^{(k+1)}-a_{ii}x_i^{(k)}-\hdots-a_{in}x_n^{(k)}), \] \[ \omega a_{i1}x_1^{(k+1)}+\hdots+\omega a_{ii-1}x_{i-1}^{(k+1)}+a_{ii}x_i^{(k+1)}= \] \[ =(1-\omega)a_{ii}x_i^{(k)}-\omega a_{ii+1}x_{i+1}^{(k)}-\hdots-\omega a_{in}x_n^{(k)}+\omega f_i. \] To je ale po složkách rozepsaný vektorový vztah \[ -\omega L\vec x^{(k+1)}+D\vec x^{(k+1)}=(1-\omega)D\vk x+\omega R\vk x+\omega \vec f, \] kde matice $L\, D$ a $R$ mají stejný význam jako v předchozím odstavci. Vynásobíme-li tento vztah zleva maticí $(D-\omega L)^{-1}$, dostaneme \[ \vec x^{(k+1)}=\underbrace{(D-\omega L)^{-1}[(1-\omega)D+\omega R]}_{\text{ozn. }\mathcal L_{\omega}} \vk x+\omega (D-\omega L)^{-1} \vec f, \] odkud po dosazení $R=D-L-A$ plyne \[ \vec x^{(k+1)}=[I-\omega (D-\omega L)^{-1} A] \vk x + \omega (D-\omega L)^{-1} \vec f= \] \[ =\vk x+\omega(D-\omega L)^{-1} (\vec f-A\vk x). \] Je tedy $H=\omega (D-\omega L)^{-1}$. Při $\omega=1$ přechází SOR v metodu Gaussovu-Seidelovu. \begin{kriterkonv} Platí $I-HA=I-\omega (D-\omega L)^{-1} (-L+D-R)=$ \linebreak[4]$=I-(D-\omega L)^{-1} [D-\omega L+(\omega - 1)D-\omega R]=(D-\omega L)^{-1}[(1-\omega)D+\omega R]=\mathcal L_{\omega}$.

Označme $\rho_{\omega}$ spektrální poloměr matice $\mathcal L_{\omega}$. Superrelaxační metoda konverguje pro libovolnou volbu $\vec x^{(0)}$ $\Leftrightarrow \rho_{\omega}<1$, postačující podmínka je $\nor{\mathcal L_{\omega}}<1$. \end{kriterkonv} \begin{remark} Je třeba nalézt nejvýhodnější hodnotu parametru $\omega$, potřebujeme tedy nějaké kritérium, abychom mohli rozhodnout, která ze dvou iteračních metod je lepší a která horší.

Za lepší ze dvou metod považujeme tu, jejíž matice $I-HA$ má menší spektrální poloměr. Důvod je následující: Nechť je dána iterační metoda \linebreak[4]$\vec x^{(k+1)}=B\vk x+\vec g$. Pro přesné řešení musí platit $\vec x^*=B\vec x^*+\vec g$. Odečtením těchto dvou vztahů dostaneme \[ \vec x^{(k+1)}-\vec x^*=B(\vk x-\vec x^*)=B^2(\vec x^{(k-1)}-\vec x^*)=\hdots=B^{k+1}(\vec x^{(0)}-\vec x^*). \] Protože platí $B^{k+1}=T^{-1}J^{k+1}T$, kde $J$ a $T$ jsou příslušné matice z Jordanovy věty, je zřejmé (viz též důkaz věty \ref{nppkgpm}), že $B^{k}$ konverguje k nulové matici stejně rychle jako $(\rho(B))^k\rightarrow 0$. \end{remark} \begin{define} \begin{enumerate} \item Elementární permutační maticí $I_{ij}\in\mathbbm C^{n,n}$ nazýváme matici, která vznikne z jednotkové matice $I\in\mathbbm C^{n,n}$ záměnou $i$-tého a $j$-tého řádku (sloupce). \item Permutační maticí nazveme matici, která je součinem libovolného počtu elementárních permutačních matic. \end{enumerate} \end{define} \begin{remark} \begin{enumerate} \item Elementární permutační matice je symetrická a ortogonální: \[ I_{ij}=I_{ij}^T=I_{ij}^{-1}. \] Z toho plyne, že každá permutační matice je ortogonální. \item Násobení libovolné matice $A$ zleva, resp. zprava maticí $I_{ij}$ odpovídajícího rozměru je ekvivalentní prohození $i$-tého a $j$-tého řádku, resp. sloupce matice $A$. Indukcí získáme toto tvrzení:

Provedeme-li libovolnou permutaci řádků, resp. sloupců matice $A$, je výsledek ekvivalentní násobení matice $A$ zleva, resp. zprava permutační maticí odpovídajícího rozměru, která vznikne z $I$ stejnou permutací řádků, resp. sloupců. \item Předchozí definice permutační matice je sice snadno zapamatovatelná, není z ní však na první pohled zřejmé, odkud se vzalo pojmenování této matice. Uveďme si proto jinou, s předchozí zřejmě ekvivalentní definici:

Permutační maticí nazveme takovou matici $P=(p_{ij})$, pro kterou existuje permutace $\pi\in S_n$ tak, že \[ p_{ij}= \begin{cases} 1 & \text{když }\pi(i)=j,\\ 0 & \text{jinak}.\\ \end{cases} \] \end{enumerate} \end{remark} \begin{define} Čtvercová matice $A$ se nazývá slabě cyklická s indexem 2, existuje-li permutační matice $P$ taková, že matice $PAP^T$ je blokového tvaru \begin{equation} \label{sci2} \left( \begin{matrix} O & M_1\\ M_2 & O \end{matrix} \right), \end{equation} kde diagonální bloky jsou čtvercové matice. \end{define} \begin{remark} Matice je slabě cyklická s indexem 2, lze-li ji simultánní (tj. stejnou) permutací řádků a sloupců převést na blokový tvar (\ref{sci2}). \end{remark} \begin{define} Buď $A=-L+D-R$. Matice $A$ se nazývá dvoucyklická, je-li matice $D^{-1}(L+R)$ slabě cyklická s indexem 2. Dvoucyklická matice se nazývá shodně uspořádaná, jestliže vlastní čísla matice $\alpha D^{-1}L+\frac{1}{\alpha}D^{-1}R$ nezávisejí na volbě čísla $\alpha\ne 0$. \end{define} \begin{remark} Matice je shodně uspořádaná, jestliže se spektrum (Jacobiho) matice $D^{-1}(L+R)$ nezmění po vynásobení prvků pod diagonálou číslem $\alpha$ a prvků nad diagonálou číslem $\alpha^{-1}$. \end{remark} \begin{theorem} Má-li matice slabě cyklická s indexem 2 vlastní číslo $\mu$, potom má i vlastní číslo $-\mu$. \begin{proof} Matice slabě cyklická s indexem 2 je podle definice podobná blokové matici (\ref{sci2}). Má tedy i stejný charakteristický polynom \[ \left | \begin{matrix} \lambda I_1 & -M_1\\ -M_2 & \lambda I_2 \end{matrix} \right |= \left | \begin{matrix} I_1 & O\\ \frac{1}{\lambda}M_2 & I_2 \end{matrix} \right | \left | \begin{matrix} \lambda I_1 & -M_1\\ -M_2 & \lambda I_2 \end{matrix} \right |= \left | \begin{matrix} \lambda I_1 & -M_1\\ O & -\frac{1}{\lambda}M_2 M_1+\lambda I_2 \end{matrix} \right |= \] $=\lambda^{s_1-s_2} |\lambda^2I_2-M_2M_1|$, kde $I_1$ je jednotková matice typu $(s_1\, s_1)$ a $I_2$ jednotková matice typu $(s_2\, s_2)$. Poslední výraz má ovšem tu vlastnost, že když je nulován pro $\lambda=\mu$, je nulován i pro $\lambda=-\mu$. \end{proof} \end{theorem} \begin{theorem} Buď $A$ dvoucyklická shodně uspořádaná a nechť $\omega \ne 0$. \begin{enumerate} \item Buď $\lambda\ne 0$ vlastní číslo matice $\mathcal L_{\omega}$ a nechť číslo $\mu$ splňuje rovnici \begin{equation} \label{graf} (\lambda+\omega-1)^2=\omega^2\mu^2\lambda. \end{equation} Potom $\mu$ je vlastní číslo (Jacobiho) matice $D^{-1}(L+R)$. \item Buď $\mu$ vlastní číslo (Jacobiho) matice $D^{-1}(L+R)$ a nechť $\lambda$ splňuje rovnici (\ref{graf}). Potom $\lambda$ je vlastní číslo matice $\mathcal L_{\omega}$. \end{enumerate} Je-li navíc $A$ pozitivně definitní, potom jsou všechna vlastní čísla $\mu$ Jacobiho matice reálná, $\abs{\mu}<1$ (tj. $\rho(D^{-1}(L+R))<1$) a SOR konverguje pro libovolnou volbu $\vec x^{(0)} \Leftrightarrow \omega\in(0\, 2)$.

Definujme \[ \omega_0=\frac{2}{1+\sqrt{1-\mu_0^2}}, \] kde $\mu_0=\rho(D^{-1}(L-R))$. Pak $1\le \omega_0<2$, $\rho_{\omega}$ je klesající funkcí $\omega$ v intervalu $(0\, \omega_0\rangle$ a pro $\omega\in\langle\omega_0\, 2)$ platí $\rho_{\omega}=\omega-1$. \begin{proof} \begin{enumerate} \item Buďte $\lambda\ne 0$ vlastní číslo matice $\mathcal L_{\omega}$, $\vec x$ k němu příslušející vlastní vektor. Potom platí $(D-\omega L)^{-1}[(1-\omega)D+\omega R]\vec x=\lambda\vec x$. Tuto rovnici vynásobíme zleva maticí $D-\omega L$ a dostaneme $[(1-\omega)D+\omega R]\vec x=\lambda(D-\omega L)\vec x$, odkud $\omega(R+\lambda L)\vec x=(\lambda+\omega-1)D\vec x$. Tento vztah vynásobíme zleva maticí $\frac{1}{\sqrt\lambda\omega}D^{-1}$, kde $\sqrt\lambda$ značí libovolnou komplexní druhou odmocninu z $\lambda$. Potom \[ \left(\frac{1}{\sqrt\lambda}D^{-1}R+\sqrt\lambda D^{-1}L\right)\vec x=\underbrace{\frac{\lambda+\omega-1}{\sqrt\lambda\omega}}_{\text{ozn. }\mu}\;\vec x. \] Číslo $\mu$ je tedy vlastním číslem matice $\sqrt\lambda D^{-1}L+\frac{1}{\sqrt\lambda}D^{-1}R$. Protože je matice $A$ shodně uspořádaná, musí být $\mu$ též vlastním číslem matice $D^{-1}L+D^{-1}R$. Tato matice je ovšem slabě cyklická s indexem 2 (matice $A$ je dvoucyklická), a tak je jejím vlastním číslem i $-\mu$. \item Pro $\lambda\ne 0\, \omega\ne 0$ se bod 2 dokáže analogicky. Pro $\lambda=0$ připadá podle (\ref{graf}) v úvahu jen $\omega=1$ a tehdy SOR přechází v Gaussovu-Seidelovu metodu, tj. $\mathcal L_{\omega}=(D-L)^{-1}R$. Máme dokázat, že $(\exists\vec x\ne\vec o)((D-L)^{-1}R\:\vec x=\vec o)$, tedy že matice $(D-L)^{-1}R$ je singulární. Z definice matice $R$ je zřejmé, že $R$ je singulární, a tak musí být singulární i $(D-L)^{-1}R$. \end{enumerate} Položme $\omega=1$. Potom (\ref{graf}) přejde v $\lambda^2=\mu^2\lambda$, pro $\lambda\ne 0$ je tedy $\lambda=\mu^2$. Odtud $\rho((D-L)^{-1}R)=(\rho(D^{-1}(L+R)))^2$, takže Gaussova-Seidelova metoda konverguje, právě když konverguje Jacobiho metoda. Buď nyní $A$ pozitivně difinitní. Potom Gaussova-Seidelova metoda konverguje při libovolné volbě $\vec x^{(0)}$. To ovšem --- jak jsme právě dokázali --- znamená, že pro libovolné $\vec x^{(0)}$ konverguje i Jacobiho metoda, takže musí být $\rho(D^{-1}(L+R))<1$.

Platí \[ D^{-1}(L+R)=D^{-\frac{1}{2}}[D^{-\frac{1}{2}}(L+R)D^{-\frac{1}{2}}]D^{\frac{1}{2}}, \] tj. matice $D^{-1}(L+R)$ je podobná matici $D^{-\frac{1}{2}}(L+R)D^{-\frac{1}{2}}$. Protože je matice $A$ pozitivně definitní, musí být podle definice \ref{pozdef} hermitovská. Z definice hermitovské matice je zřejmé, že hermitovská je potom i matice $L+R$ a tím pádem i matice $D^{-\frac{1}{2}}(L+R)D^{-\frac{1}{2}}$. Každá hermitovská matice má všechna vlastní čísla reálná, a tak má všechna vlastní čísla reálná i matice $D^{-1}(L+R)$.

Přepišme (\ref{graf}) do tvaru \begin{equation} \label{diskr} \lambda^2+[2(\omega-1)-\omega^2\mu^2]\lambda+(\omega-1)^2=0. \end{equation} Každé vlastní číslo $\lambda$ matice $\mathcal L_{\omega}$ je tedy kořenem kvadratické rovnice s reálnými koeficienty. Odtud ihned vyplývá: \begin{enumerate} \item Je-li $\lambda$ imaginární vlastní číslo $\mathcal L_{\omega}$, je jím i $\overline\lambda$ a platí $\lambda\overline\lambda=(\omega-1)^2$, takže $\abs\lambda=\sqrt{\lambda\overline\lambda}=\abs{\omega-1}$. \item Je-li $\lambda_1$ reálné vlastní číslo $\mathcal L_{\omega}$, je jím i $\lambda_2$ takové, že $\lambda_1\lambda_2=(\omega-1)^2$. Bez újmy na obecnosti potom platí např. $\lambda_2\le\abs{\omega-1}\le\lambda_1$. \end{enumerate} Nutnou podmínkou pro konvergenci metody při libovolné volbě $\vec x^{(0)}$ je tedy \linebreak[4]$\omega\in(0\, 2)$, neboť jinak by některé vlastní číslo matice $\mathcal L_{\omega}$ muselo mít absolutní hodnotu větší nebo rovnu jedné. Z bodu 1 plyne, že jsou-li všechna vlastní čísla matice $\mathcal L_{\omega}$ imaginární, potom $\rho_{\omega}=\abs{\omega-1}$. Z bodu 2 plyne, že má-li matice $\mathcal L_{\omega}$ alespoň jedno vlastní číslo reálné, potom platí $\rho_{\omega}=\max\{\abs{\lambda}\;|\;\lambda\in\sigma(\mathcal L_{\omega})\cap\mathbbm R\}$. Naším cílem je vhodně vyjádřit $\rho_{\omega}$ v tomto druhém případě. Omezíme se tedy na reálné kořeny rovnice (\ref{graf}) a $\omega\in(0\, 2)$.

Vztah (\ref{graf}) tentokrát přepíšeme takto: \[ \frac{\lambda+\omega-1}{\omega}=\pm\mu\sqrt\lambda. \] Tuto rovnici řešme graficky. Jejími reálnými kořeny jsou $\lambda$-ové souřadnice průsečíků přímky $y=\frac{1}{\omega}(\lambda+\omega-1)$ s parabolou $y=\pm\mu\sqrt\lambda$. Přímka prochází bodem $[1\, 1]$, parabola prochází počátkem a je tím otevřenější, čím je $\abs\mu$ větší. Pro pevné $\omega$ získáme $\rho_{\omega}$ jako větší z $\lambda$-ových souřadnic průsečíků přímky s parabolou při volbě $\mu_0=\rho(D^{-1}(L+R))$, tj. v případě, kdy je parabola nejotevřenější.

S rostoucím $\omega$ se bude $\rho_{\omega}$ zmenšovat --- přímka se bude naklánět v záporném smyslu až do chvíle, kdy se stane tečnou paraboly; tehdy položme $\omega=\omega_0$. Pro $\omega>\omega_0$ přímka s parabolou žádné průsečíky nemá a všechna vlastní čísla matice $\mathcal L_{\omega}$ jsou imaginární, tj. platí $\rho_{\omega}=\abs{\omega-1}$; ovšem jen do meze $\omega=\omega_1$, kdy se přímka dotkne paraboly ,,vpravo" od bodu $[1\, 1]$. Potom ale zřejmě $\rho_{\omega}>1$, takže metoda nemůže konvergovat při každé volbě $\vec x^{(0)}$.

Nyní určíme $\omega_0$ tak, že položíme diskriminant rovnice (\ref{diskr}) roven nule: \[ 4(\omega-1)^2-4(\omega-1)\omega^2\mu_0^2+\omega^4\mu_0^4-4(\omega-1)^2=0\,\;\;\;\;\omega^2\mu_0^2-4\omega+4=0, \] \[ \omega_{1\, 2}=\frac{4\pm\sqrt{16-16\mu_0^2}}{2\mu_0^2}=2\cdot\frac{1\pm\sqrt{1-\mu_0^2}}{\mu_0^2}=\frac{2\mu_0^2}{\mu_0^2(1\mp\sqrt{1-\mu_0^2})}. \] Protože musí $\omega_0\in(0\, 2)$, dostáváme \[ \omega_0=\frac{2}{1+\sqrt{1-\mu_0^2}}. \] \end{proof} \end{theorem}


% následující řádky upravují pouze zobrazení stránky na wiki na obsah dokumentu nemají vliv - prosím neměnit ! %\parentlatexfile{01NMskriptum} %\usewikiobsah{01NM:Obsah} %\parentlatexpreamble{01NM:Preamble} .................................. odkaz na hlavičkovou stránku dokumentu, jehož vložení umožní překlad částečného pdf, tj. pdf, které vznikne pouze z této stránky