01NM:Kapitola2: Porovnání verzí

Z WikiSkripta FJFI ČVUT v Praze
Přejít na: navigace, hledání
m
m (zpřehledněn důkaz poznámky)
 
(Nejsou zobrazeny 4 mezilehlé verze od 3 dalších uživatelů.)
Řádka 1: Řádka 1:
 +
%\wikiskriptum{01NM}
 +
 
\section{Iterační metody řešení soustav lineárních algebraických rovnic}
 
\section{Iterační metody řešení soustav lineárních algebraických rovnic}
 
\subsection{Úvod}
 
\subsection{Úvod}
Řádka 50: Řádka 52:
 
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})$,
Řádka 80: Řádka 82:
 
\]
 
\]
 
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}$.
 
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}\;}=$
+
Platí-li $\nor {\vec x-\vec y}<\delta$, můžeme tedy psát
$=\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$.
+
\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.
 +
\]
 +
Nyní stačí položit $\delta=\epsilon$.
 
\end{enumerate}
 
\end{enumerate}
 
\end{proof}
 
\end{proof}
Řádka 669: Řádka 673:
 
\end{proof}
 
\end{proof}
 
\end{theorem}
 
\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}
 

Aktuální verze z 3. 9. 2015, 19:49

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 01NM

součástakcepopisposlední editacesoubor
Hlavní dokument editovatHlavní stránka dokumentu 01NMAdmin 1. 8. 201010:22
Řídící stránka editovatDefiniční stránka dokumentu a vložených obrázkůAdmin 7. 9. 201513:47
Header editovatHlavičkový souborKlinkjak 1. 9. 201522:49 header.tex
Kapitola1 editovatFinitní metodyAdmin 1. 8. 201010:24 kapitola1.tex
Kapitola2 editovatIterační metody řešení soustav lineárních algebraických rovnicKlinkjak 3. 9. 201519:49 kapitola2.tex
Kapitola3 editovatČástečný problém vlastních číselAdmin 1. 8. 201010:25 kapitola3.tex
Kapitola4 editovatÚplný problém vlastních číselAdmin 1. 8. 201010:25 kapitola4.tex
Kapitola5 editovatIterační metody řešení rovnice tvaru f(x)=0Admin 1. 8. 201010:25 kapitola5.tex
Kapitola6 editovatIterační metody pro řešení systémů nelineárních algebraických a transcendentních rovnicAdmin 1. 8. 201010:25 kapitola6.tex
Kapitola7 editovatLagrangeova interpolaceAdmin 1. 8. 201010:25 kapitola7.tex
Kapitola8 editovatNumerický výpočet derivaceAdmin 1. 8. 201010:25 kapitola8.tex
Kapitola9 editovatNumerický výpočet integrálu Admin 1. 8. 201010:25 kapitola9.tex

Zdrojový kód

%\wikiskriptum{01NM}
 
\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.
\]
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}