% Davor Menon, matematika-informatika, Odjel za matematiku, Osijek
% MBS: 8735
% Seminarski rad iz RP2
% Zadnja izmjena: 12.08.2005.
% 
% Successive overrelaxation method
% {\v{C}}lanak
% 
\documentclass[a4paper,12pt]{article}
    \usepackage[croatian]{babel}
    \usepackage{graphicx}
    \usepackage{graphics}
    \usepackage{amsmath, amssymb}

    \title{\textbf{Metoda sukcesivne nadrelaksacije (SOR)}
        \footnote{Seminarski rad iz kolegija \emph{Ra\v cunarski praktikum 2}}}
    \author{\textsc{Davor Menon}\footnote{\textsl{dmenon@mathos.hr; 
        www.mathos.hr/$^\sim$dmenon}}
        \\\emph{\normalsize Odjel za matematiku, Osijek}}
    \date{\textsl{8. srpnja 2005.}}

    \newtheorem{teo}{Teorem}[section]
    \newtheorem{naziv}{Definicija}[section]
    \newtheorem{kor}{Korolar}[section]
    \newtheorem{pokaz}{Primjer}[section]

    % \theequation
    %\newcounter{equation}[section]
    %\renewcommand{\theequation}{\arabic{section}.\arabic{equation}}

\begin{document}

\maketitle
\thispagestyle{empty}

\begin{tabular}{l}
\hline
\begin{minipage}{1.1\textwidth}\small
    {\ }\subsection*{Sa\v{z}etak}
    Pro\v slo je preko pedeset godina od D. M. Youngova rada o metodi sukcesivne
    nadrelaksacije (eng. \emph{successive overrelaxation method}). Ova metoda se danas
    pojavljuje u svim ud\v zbenicima u kojima se obra\dj uju iterativne metode.

    U ovom radu se naglasak stavlja na SOR metodu, ali obra\dj ene su i srodne iterativne
    metode poput Jacobijeve metode i Gauss-Seidelove metode. Iterativne metode se koriste
    pri rje\v savanju velikih rijetkih sustava linearnih jednad\v zbi.
    \begin{description}
        \item[AMS:] 65R10; 65N22; 65F10
        \item[Klju\v cne rije\v ci:] stacionarne iterativne metode, Jacobijeva metoda,
        Gauss-Seidelova metoda, SOR metoda
    \end{description}
    \subsection*{Abstract}
    It has been over fifty years since D.M. Young's original work on the successive
    overrelaxation (SOR)methods. This fundamental method now appears in all textbooks
    containing an introductory discussion of iterative solution methods.

    In this survey, the accent is at SOR method, but we considered some other related methods.
    Iterative methods are used for solving large sparse linear systems.
    \begin{description}
        \item[AMS:] 65R10; 65N22; 65F10
        \item[Key words:] stationary iterative methods, Jacobi method,
        Gauss-Seidel method, SOR method
    \end{description}
    {\ }
\end{minipage}
\end{tabular}

\section{Uvod}
U svojem dosada\v snjem radu smo vjerojatno mnogo puta nai\v sli na problem rje\v savanja
sustava linearnih jednad\v zbi
\begin{equation}
    \mathbf{A}x=\mathbf{b}\mbox{.}
    \label{jed}
\end{equation}
Svi smo upoznati s direktnim metodama rje\v savanja sustava (\ref{jed}). 
U slu\v cajevima kada je broj jednad\v zbi i nepoznanica malen, ovaj problem smo u 
stanju rije\v siti vrlo brzo i pouzdano. U slu\v caju da je rije\v c o vrlo velikim 
sustavima linearnih jednad\v zbi dolazi do vrlo velikih problema, \v cak i uz 
dana\v snja ra\v cunala ovaj problem mo\v ze postati vrlo te\v zak.

Stoga su se vremenom razvile mnoge razli\v cite metode za rje\v savanje sustava 
(\ref{jed}), a u ovom radu \' cemo se osvrnuti na grupu metoda koje se nazivaju 
\emph{stacionarne iterativne metode}. Kao \v sto samo ime ka\v ze, iterativnim 
metodama poku\v savamo pobolj\v sati neku po\v cetnu aproksimaciju, tako da u svakoj 
iteraciji gre\v ska bude \v sto manja. Primjenom odgovaraju\' ceg kriterija 
zaustavljanja, nakon odre\dj enog broja iteracija, dobiveni vektor smatrati \' cemo 
dovoljno dobrom aproksimacijom.

Postavlja se pitanje za\v sto se pored prili\v cno djelotvorne metode Gaussovih 
eliminacija (vidi \cite{sci}) za rje\v savanje linearnih sustava razvio i veliki 
broj iterativnih metoda? Op\' ce je poznato da rje\v savanje linearnog sustava pomo\' cu 
Gaussovih eliminacija, u op\'  cenitom slu\v caju, zahtijeva zalihu u memoriji za 
skladi\v stenje svih $n^2$ elemenata matrice $\mathbf{A}$ i broj potrebnih operacija 
reda $n^3$. Matrice koje se pojavljuju u praksi \v cesto imaju posebna svojstva. Naj\v 
ce\v s\' ce se to svodi na veliki broj elemenata koji su jednaki nuli, pa govorimo o 
\emph{rijetko popunjenim} matricama. Tako\dj er je \v cesto raspored netrivijalnih 
elemenata pravilno raspore\dj en, pa govorimo o\emph{ vrp\v castim} matricama. 
Gaussove eliminacije obi\v cno su u stanju samo djelomi\v cno iskoristiti ta svojstva. 
Ako primijenimo Gaussove eliminacije na takve matrice, u rezultiraju\' cim trokutastim 
faktorima pojaviti \' ce se mnogi netrivijalni elementi na mjestima gdje je originalna 
matrica imala nule. Nadalje, vrlo \v cesto se rijetka popunjenost matrice mo\v ze 
iskoristiti pri mno\v zenju matrice s vektorom.

Zato su se razvile iterativne metode za rje\v savanje sustava (\ref{jed}) koje koriste 
samo mno\v zenje matrice i vektora, uz mali broj jo\v s dodatnih operacija. Takve 
metode mogu prili\v cno nadma\v siti Gaussove eliminacije i u memoriji i po broju 
izvr\v senih operacija.

Osnovni nedostatak iterativnih metoda je u tome \v sto je klasa sustava linearnih 
jednad\v zbi za koje pojedine metode konvergiraju dosta uska. No, s druge strane, 
sre\' ca je sto u praksi mnogi sustavi linearnih jednad\v zbi spadaju u klasu za koju 
iterativne metode konvergiraju.

\section{Spektralni radijus}
Spektralni radijus, ili najve\' ca apsolutna vrijednost svojstvenih vrijednosti matrice, 
je od velike va\v znosti u analizi odre\dj enih iterativnih metoda. Sa $\sigma 
(\mathbf{A})$ ozna\v cavamo skup svojstvenih vrijednosti od $\mathbf{A}$.

\begin{naziv}
    \textsf{Spektralni radijus} matrice $\mathbf{A}\in\mathbb{R}^{n\times n}$ je
    $$
        \rho (\mathbf{A})=\max_{\lambda\in\sigma (\mathbf{A})}|\lambda |\mbox{.}
    $$
\end{naziv}

\begin{teo}
    Ako je $\|\cdot\|$ bilo koja matri\v cna norma i
    $\mathbf{A}\in\mathbb{R}^{n\times n}$, tada je
    $$
        \rho (\mathbf{A})\leq\|\mathbf{A}\|\mbox{.}
    $$
    \label{tm_prvi}
\end{teo}

\noindent\textbf{\emph{Dokaz:}}
Neka je $\lambda$ svojstvena vrijednost od $\mathbf{A}$, za koju je $|\lambda |=\rho 
(\mathbf{A})$ i neka je $\mathbf{v}\neq 0$ odgovaraju\' ci svojstveni vektor. Neka je 
$\mathbf{V}\in\mathbb{R}^{n\times n}$ matrica kojoj je svaki stupac jednak $\mathbf{v}$. 
Tada je $\mathbf{AV}=\lambda\mathbf{V}$ i vrijedi
$$
    |\lambda |\cdot\|\mathbf{V}\| =\|\lambda\mathbf{V}\|
    =\|\mathbf{AV}\|\leq\|\mathbf{A}\|\cdot\|\mathbf{V}\|\mbox{.}
$$
Budu\' ci da je $\mathbf{V}\neq 0$, imamo da je $\|\mathbf{V}\| >0$, odakle slijedi da
je \linebreak $\rho (\mathbf{A})\leq\|\mathbf{A}\|\mbox{.}
$\hfill $\square$

\begin{teo}
    Neka je $\mathbf{A}\in\mathbb{R}^{n\times n}$ i $\varepsilon >0$ dani broj.
    Tada postoji matri\v cna norma $\|\cdot\|$ inducirana nekom vektorskom
    normom takva da je
    $$
        \|\mathbf{A}\|_{\varepsilon ,\mathbf{A}}\leq\rho (\mathbf{A})+\varepsilon\mbox{.}
    $$
    \label{spektar12}
\end{teo}

\noindent\textbf{\emph{Dokaz:}}
Neka je $\mathbf{S}^{-1}\mathbf{AS}=\mathbf{J}$ Jordanova forma matrice $\mathbf{A}$. 
Definirajmo
$$
    \mathbf{D}_\varepsilon =\mathop{\mathrm{diag}}(1,\varepsilon
    ,\ldots ,\varepsilon^{n-1})\mbox{,}
$$
i
$$
    \mathbf{J}_\varepsilon =\mathbf{D}_\varepsilon ^{-1}\mathbf{JD}_\varepsilon\mbox{,}
$$
tako da vrijedi
\begin{eqnarray*}
    (\mathbf{J}_\varepsilon )_{i,i} & = &
    \varepsilon^{-(i-1)}\mathbf{J}_{i,i}\varepsilon^{i-1} =\mathbf{J}_{i,i}\\
    (\mathbf{J}_\varepsilon )_{i,i+1} & = &
    \varepsilon^{-(i-1)}\cdot 1\cdot\varepsilon^{i} =\varepsilon\mbox{.}
\end{eqnarray*}
Matri\v cnu normu, za proizvoljnu matricu $\mathbf{B}\in\mathbb{R}^{n\times n}$, 
definirati \' cemo na sljede\' ci na\v cin.
$$
    \|\mathbf{B}\|_{\varepsilon ,\mathbf{A}}=\|\mathbf{D}_{\varepsilon}^{-1}
    \mathbf{S}^{-1}\mathbf{BSD}_{\varepsilon }\|_{1}\mbox{,}
$$
pri \v cemu  je odgovaraju\' ca vektorska norma koja ju inducira za proizvoljan vektor 
$\mathbf{v}$, oblika
$$
    \|\mathbf{v}\|_{\varepsilon ,\mathbf{A}}=
    \|\mathbf{D}_{\varepsilon }^{-1}\mathbf{S}^{-1}\mathbf{v}\|_{1}\mbox{,}
$$
\v sto se lako mo\v ze provjeriti iz niza jednakosti
\begin{eqnarray*}
    \max_{\mathbf{v}\neq 0}
    \frac{\|\mathbf{D}_{\varepsilon}^{-1}\mathbf{S}^{-1}\mathbf{Bv}\|_1}
    {\|\mathbf{D}_{\varepsilon}^{-1}\mathbf{S}^{-1}\mathbf{v}\|_1} & = &
    \max_{\mathbf{w}\neq 0}
    \frac{\|\mathbf{D}_{\varepsilon}^{-1}\mathbf{S}^{-1}
    \mathbf{BSD}_{\varepsilon}\mathbf{w}\|_1}{\|\mathbf{w}\|_1}\\
    & = & \|\mathbf{D}_{\varepsilon}^{-1}\mathbf{S}^{-1}
    \mathbf{BSD}_{\varepsilon}\|_1 \\
    & = & \|\mathbf{B}\|_{\varepsilon ,\mathbf{A}}\mbox{,}
\end{eqnarray*}
pri \v cemu je $\mathbf{w} = \mathbf{D}_{\varepsilon}^{-1}\mathbf{S}^{-1}\mathbf{v}$. 
Napokon, vrijedi
$$
\|\mathbf{A}\|_{\varepsilon ,\mathbf{A}}=\|\mathbf{J}_{\varepsilon}\|_1\leq\rho ( \mathbf{A} )+\varepsilon\mbox{.}
$$
{\ }\hfill $\square$

\begin{teo}
    Neka je $\mathbf{A}\in\mathbb{R}^{n\times n}$. Tada je
    $\displaystyle\lim_{k\rightarrow\infty}\mathbf{A}^k=0$
    ako i samo ako je $\rho (\mathbf{A})<1$.
    \label{prije_kora}
\end{teo}

\noindent\textbf{\emph{Dokaz:}}
Prvo pretpostavimo da je $\displaystyle\lim_{k\rightarrow\infty}\mathbf{A}^k=0$. Neka je 
$\lambda$ svojstvena vrijednost od $\mathbf{A}$ sa svojstvenim vektorom $\mathbf{v}\neq 
0$. Budu\' ci da je $\mathbf{A}^k\mathbf{v}=\lambda ^k\mathbf{v}$, za proizvoljnu normu 
$\|\cdot\|$ slijedi
$$
    0=\lim_{k\rightarrow\infty}\|\lambda ^k\mathbf{v}\|=
    \|\mathbf{v}\|\lim_{k\rightarrow\infty}|\lambda ^k|\mbox{.}
$$
Kako je $\|\mathbf{v}\|>0$, vrijedi da je
$\displaystyle\lim_{k\rightarrow\infty}|\lambda ^k|=0$, odakle slijedi da mora biti
$|\lambda |<1$ i to za proizvoljnu svojstvenu vrijednost od $\mathbf{A}$. Dakle, vrijedi 
i $\rho(\mathbf{A})<1$.

Obrnuto, pretpostavimo da je $\rho(\mathbf{A})<1$ i tada prema Teoremu \ref{spektar12} 
postoji matri\v cna norma $\|\cdot\|$, takva da je za
$0<\varepsilon <1-\rho (\mathbf{A})$
$$
    \|\mathbf{A}\|\leq\rho (\mathbf{A})+\varepsilon <1\mbox{.}
$$
Odatle slijedi da je
$$
    \lim_{k\rightarrow\infty}\|
    \mathbf{A}^k\|\leq\lim_{k\rightarrow\infty}\|\mathbf{A}\|^k=0\mbox{.}
$$
Budu\' ci da su na $\mathbb{R}^{n\times n}$ sve matri\v cne norme ekvivalentne, 
zna\v ci da je i $\displaystyle\lim_{k\rightarrow\infty}\|\mathbf{A}^k\|_F=0$, odakle 
slijedi da svi elementi od $\mathbf{A}^k$ moraju te\v ziti k nuli.
{\ }\hfill $\square$

\begin{kor}
    Neka je $\|\cdot\|$ matri\v cna norma na $\mathbb{R}^{n\times n}$. Tada je
    $$
        \rho (\mathbf{A})=\lim_{k\rightarrow\infty}\|\mathbf{A}^k\|^{1/k}
    $$
    za svaki $\mathbf{A}\in\mathbb{R}^{n\times n}$.
\end{kor}

\noindent\textbf{\emph{Dokaz:}}
Budu\' ci da je prema definiciji i Teoremu \ref{tm_prvi}
$\rho(\mathbf{A})^k=\rho(\mathbf{A}^k)\leq\|\mathbf{A}^k\|$, imamo da je 
$\rho(\mathbf{A})\leq\|\mathbf{A}^k\|^{1/k}$ za sve $k=1,2,\ldots$ Za proizvoljni 
$\varepsilon >0$, matrica $\mathbf{\tilde{A}}=[\rho 
(\mathbf{A})+\varepsilon]^{-1}\mathbf{A}$ ima spektralni radijus strogo manji od jedan, 
pa je prema Teoremu \ref{prije_kora} 
$\displaystyle\lim_{k\rightarrow\infty}\|\mathbf{\tilde{A}}^k\|=0$. Dakle, postoji broj 
$K$ koji ovisi o $\varepsilon$, takav da je za svaki $k\geq K$, 
$\|\mathbf{\tilde{A}}^k\|<1$. \v sto je ekvivalentno tvrdnji $\|\mathbf{A}^k\|\leq [\rho 
(\mathbf{A})+\varepsilon ]^k$ ili $\|\mathbf{A}^k\|^{1/k}\leq \rho 
(\mathbf{A})+\varepsilon $ za sve $k\leq K$. Prema tome imamo
$$
    \rho (\mathbf{A})\leq\|\mathbf{A}^k\|^{1/k}\leq \rho (\mathbf{A})+\varepsilon
$$
za sve $k\leq K$, a budu\' ci da to vrijedi za sve $\varepsilon >0$, slijedi da 
$\displaystyle\lim_{k\rightarrow\infty}\|\mathbf{A}^k\|^{1/k}$ postoji i da je 
jedak $\rho (\mathbf{A})$.
{\ }\hfill $\square$

\section{Op\' ci iterativni postupak}
Neka je dana regularna matrica $\mathbf{A}\in\mathbb{R}^{n\times n}$ i neka su 
$\mathbf{N},\mathbf{P}\in\mathbb{R}^{n\times n}$ takve da je
$$
    \mathbf{A=N+P}\mbox{.}
$$
Tada dani sustav $\mathbf{Ax}=\mathbf{b}$ mo\v zemo zapisati u obliku
$$
    \mathbf{Nx}=\mathbf{-Px}+\mathbf{b}\mbox{,}
$$
pri \v cemu je matrica $\mathbf{N}$ regularna. Ako nam je dana aproksimacija 
$\mathbf{x}^{(k)}$, novu aproksimaciju $\mathbf{x}^{(k+1)}$ mo\v zemo dobiti kao rje\v 
senje jednad\v zbe
\begin{equation}
    \mathbf{Nx}^{(k+1)}=-\mathbf{Px}^{(k)}+\mathbf{b},\quad k=0,1,2,\ldots
    \label{ite_formula}
\end{equation}
U tom slu\v caju imamo iteracije oblika
$$
    \mathbf{x}^{(k+1)}=-\mathbf{N}^{-1}\mathbf{Px}^{(k)}+\mathbf{N}^{-1}\mathbf{b}
$$
kod kojih se tra\v zi fiksna to\v cka (vidi \cite{sci}). Ovako dobiveni iterativni 
postupak mo\v zemo op\' cenito zapisati kao
$$
    \mathbf{x}^{(k+1)}=\mathbf{Mx}^{(k)}+\mathbf{d}\mbox{,}
$$
gdje je $\mathbf{M}=\mathbf{N}^{-1}\mathbf{P}$ i $\mathbf{d}=\mathbf{N}^{-1}\mathbf{b}$.

\begin{teo}
    Neka je $\mathbf{M}\in\mathbb{R}^{n\times n}$ matrica takva da za neku matri\v cnu
    i s njom kompatibilnu vektorsku normu vrijedi
    $$
        \|\mathbf{My-Mz}\|\leq\alpha\|\mathbf{y-z}\|,\quad
        \mbox{ za svaki } \mathbf{y,z}\in\mathbb{R}^{n}\mbox{,}
    $$
    pri \v cemu je $\alpha\in[0,1)$. Tada sustav $\mathbf{x}=\mathbf{Mx}+\mathbf{d},
    \quad \mathbf{d}\in\mathbb{R}^{n}$, ima jedinstveno rje\v senje $\mathbf{x}^*\in
    \mathbb{R}^{n}$ i to rje\v senje je grani\v cna vrijednost niza vektora
    $\mathbf{x}^{(0)}$, $\mathbf{x}^{(1)}$, $\mathbf{x}^{(2)}$,\ldots odre\dj enog prema
    \begin{equation}
        \mathbf{x}^{(k+1)}=\mathbf{Mx}^{(k)}+\mathbf{d},\quad k=0,1,2,\ldots
        \label{iter}
    \end{equation}
    za proizvoljan $\mathbf{x}^{(0)}\in\mathbb{R}^{n}$.
    \label{banach}
\end{teo}

Kako za kompatibilne vektorske i matri\v cne norme vrijedi
$$
    \|\mathbf{My-Mz}\|\leq\|\mathbf{M}\| \|\mathbf{y-z}\|,\quad
    \mathbf{y,z}\in\mathbb{R}^{n}\mbox{,}
$$
slijedi
\begin{teo}
    Neka je za neku matri\v cnu normu $\|\mathbf{M}\|\geq 1$. Tada sustav\linebreak
    $\mathbf{x}=\mathbf{Mx}+\mathbf{d}$ ima jedinstveno rje\v senje koje je
    grani\v cna vrijednost iterativnog niza (\ref{iter}), za proizvoljan
    $\mathbf{x}^{(0)}$.
    \label{norma}
\end{teo}

\noindent\textbf{\emph{Dokaz:}}
Uzmemo $\alpha=\|\mathbf{M}\|$ i tvrdnja teorema slijedi direktno iz\linebreak Teorema \ref{banach}.
{\ }\hfill $\square$

Uvjet $\|\mathbf{M}\|<1$ je samo dovoljan za konvergenciju iterativnog postupka 
(\ref{iter}) za proizvoljni $\mathbf{x}^{(0)}$, tj. ako za neku normu vrijedi 
$\|\mathbf{M}\|\geq 1$ to ne zna\v ci da iterativni postupak ne konvergira.

\begin{teo}
    Neka je niz vektora $\mathbf{x}^{(0)}$, $\mathbf{x}^{(1)}$, $\mathbf{x}^{(2)}$,
    \ldots generiran s
    $$
        \mathbf{x}^{(k+1)}=\mathbf{Mx}^{(k)}+\mathbf{d},\quad k=0,1,2,\ldots,
    $$
    gdje je $\mathbf{M}\in\mathbb{R}^{n\times n}$, $\mathbf{x}\in\mathbb{R}^{n}$.
    Dani niz konvergira prema jedinstvenom rje\v senju $\mathbf{x}^*$sustava
    $\mathbf{x}=\mathbf{Mx}+\mathbf{d}$ za svaki po\v cetni vektor $\mathbf{x}^{(0)}$
    ako i samo ako je\linebreak $\rho (\mathbf{M})<1$.
    \label{opca_kon}
\end{teo}

\noindent\textbf{\emph{Dokaz:}}
Najprije pretpostavimo da je $\rho (\mathbf{M})<1$. Tada postoji $\varepsilon >0$ takav 
da je $\rho (\mathbf{M})+\varepsilon <1$. Prema Teoremu \ref{spektar12} postoji matri\v 
cna norma $\|\cdot\|$ takva da je
$$
    \|\mathbf{M}\| <\rho (\mathbf{M})+\varepsilon <1\mbox{,}
$$
pa prema Teoremu \ref{norma} slijedi da metoda konvergira.

Pretpostavimo sada obrat, to jest, da niz $\mathbf{x}^{(k)}$ konvergira za svako 
$\mathbf{x}^{(0)}$ i $\mathbf{d}$. Sljede\' ce, pretpostavimo da je u tom slu\v caju 
$\rho (\mathbf{M})\geq 1$. To zna\v ci da postoji svojstvena vrijednost $\lambda$ od 
$\mathbf{M}$, takva da je $|\lambda |\geq 1$. Neka je $\mathbf{d}\neq 0$ svojstveni 
vektor od $\mathbf{M}$, koji pripada $\lambda$ i $\mathbf{x}^{(0)}=0$. Tada imamo
\begin{eqnarray*}
    \mathbf{x}^{(1)} & = & \mathbf{Mx}^{(0)}+\mathbf{d} =
    \mathbf{M}\cdot \mathbf{0} + \mathbf{d} = \mathbf{d} \\
    \mathbf{x}^{(2)} & = & \mathbf{Mx}^{(1)}+\mathbf{d} =
    \mathbf{M d} + \mathbf{d} = (\lambda +1) \mathbf{d} \\
    \mathbf{x}^{(3)} & = & \mathbf{Mx}^{(2)}+\mathbf{d} =
    (\lambda +1)\mathbf{Md}+\mathbf{d}=(\lambda ^2+\lambda +1)\mathbf{d} \\
    & \vdots & \\
    \mathbf{x}^{(k)} & = & \mathbf{Mx}^{(k-1)}+\mathbf{d} =
    (\lambda ^{k-1}+\cdots +\lambda +1)\mathbf{d}\mbox{.}
\end{eqnarray*}
Prema tome za iteraciju u $k$-tom koraku vrijedi
$$
    \mathbf{x}^{(k)}=\left\{ \begin{array}{ll}\frac{\lambda ^k-1}{\lambda -1}
    \mathbf{d},\quad\lambda\neq 1 \\ k\mathbf{d},\quad\lambda =1 \end{array} \right.
$$
\v sto u oba slu\v caja divergira kada $k$ te\v zi ka beskona\v cnosti. Dakle, na\v sli 
smo niz koji za odre\dj ene $\mathbf{x}^{(0)}$ i $\mathbf{d}$ divergira, \v sto je u 
kontradikciji sa pretpostavkom. Zna\v ci, da mora biti $\rho (\mathbf{M})<1$.
{\ }\hfill $\square$

\section{Jacobijeva metoda}
Neka je dan sustav linearnih jednad\v zbi
\begin{equation}
    \mathbf{Ax}=\mathbf{b}\mbox{,}
    \label{sustav}
\end{equation}
gdje je matrica $\mathbf{A}\in\mathbb{R}^{n\times n}$ regularna i
$$
    a_{ii}\neq 0,\quad i=1,2,\ldots ,n\mbox{.}
$$
Jacobijev iterativni postupak za rje\v savanje sustava (\ref{sustav}) definiran je sa
$$
    \mathbf{x}^{(k+1)}=-(\mathbf{L+U})\mathbf{x}^{(k)}+
    \mathbf{D}^{-1}\mathbf{b},\quad k=0,1,2,\ldots\mbox{,}
$$
odnosno
$$
    \mathbf{x}^{(k+1)}=\mathbf{B}_J\mathbf{x}^{(k)}+
    \mathbf{d},\quad k=0,1,2,\ldots\mbox{,}
$$
gdje je
\begin{eqnarray}
    \mathbf{D} & = & \mathop{\mathrm{diag}}
    (a_{11},a_{22},\ldots ,a_{nn})\mbox{,}\nonumber\\
    \mathbf{B}_J & = & -(\mathbf{L+U})\mbox{,}\label{matrica_jacobi}\\
    \mathbf{d} & = & \mathbf{D}^{-1}\mathbf{b}\mbox{.}\nonumber
\end{eqnarray}
kako je $\mathbf{D}^{-1}=\mathop{\mathrm{diag}}(a_{11}^{-1},a_{22}^{-1},\ldots , a_{nn}^{-1})$, to je
$$
    \mathbf{B}_J=\left[
        \begin{array}{cccc}
        0 & -\frac{a_{12}}{a_{11}} & \cdots & -\frac{a_{1n}}{11}\\
        -\frac{21}{22} & 0 & \ddots & \vdots \\
        \vdots & \ddots & \ddots & -\frac{a_{n-1,n}}{a_{n-1,n-1}} \\
        -\frac{a_{n1}}{a_{nn}} & \cdots & -\frac{a_{n,n-1}}{a_{nn}} & 0
        \end{array}
    \right], \quad \mathbf{d}=\left[ \begin{array}{c}
    \frac{b_1}{a_{11}}\\ \frac{b_2}{a_{22}}\\ \vdots \\ \frac{b_n}{a_{nn}}
    \end{array} \right] \mbox{.}
$$

Prema tome, komponente vektora $\mathbf{x}^{(k+1)}$ izra\v cunavaju se prema 
sljede\' coj formuli
\begin{equation}
    x_i^{(k+1)}=\frac{1}{a_{ii}}\left( b_i - \sum_{{j=1 \atop j\neq i}}^{n}a_{ij}x_j^{(k)}
    \right) , \quad i=1,\ldots ,n\mbox{.}
    \label{formula_jacobi}
\end{equation}

Primijetimo da kod skladi\v stenja vektora u memoriji, novi vektor $\mathbf{x}^{(k+1)}$ 
ne mo\v ze se prepisati preko starog vektora $\mathbf{x}^{(k)}$ sve dok sve komponente 
vektora $\mathbf{x}^{(k+1)}$ nisu izra\v cunate. Dakle, prije kraja jedne iteracije, oba 
vektora moramo posebno skladi\v stiti.

U nastavku \' ce nas zanimati konvergencija Jacobijeve metode, me\dj utim, samo za 
matrice s posebnim svojstvima postoje rezultati koji govore o tome. Stoga definirajmo 
pojam \emph{strogo dijagonalne dominantnosti}.

\begin{naziv}
    Ka\v zemo da je matrica $\mathbf{A}$ \textsf{strogo dijagonalno dominantna}
    ako vrijedi
    $$
        |a_{ii}|>\sum_{j\neq i}|a_{ij}|,\quad i=1,\ldots ,n\mbox{.}
    $$
    \label{dominantno}
\end{naziv}

Za takve matrice vrijedi sljede\' ci teorem.

\begin{teo}
    Neka je $\mathbf{A}$ strogo dijagonalno dominantna matrica. Tada Jacobijeva
    metoda konvergira za svaku po\v cetnu aproksimaciju $\mathbf{x}^{(0)}$.
\end{teo}

\noindent\textbf{\emph{Dokaz:}}
Prema Definiciji \ref{dominantno} i (\ref{matrica_jacobi}) vrijedi
$$
    \|\mathbf{B}_J\|_\infty =\max_{i=1,\ldots ,n}\sum_{j=1}^{n}|(\mathbf{B}_J)_{ij}|
    =\max_{i=1,\ldots ,n}\frac{1}{|a_{ii}|}\sum_{j\neq i}|a_{ij}|<1\mbox{,}
$$
pa prema Teoremu \ref{opca_kon}, Jacobijeva metoda konvergira za svaku po\v cetnu 
aproksimaciju $\mathbf{x}^{(0)}$.
{\ }\hfill $\square$

\section{Gauss-Seidelova metoda}
Jacobijevu metodu mo\v zemo modificirati tako da teku\' ce aproksimacije pre\-thodnih 
komponenti od $\mathbf{x}^{(k+1)}$ koristimo da bi se izra\v cunala njegova sljede\' ca 
komponenta. Time se omogu\' cava da komponente od $\mathbf{x}^{(k+1)}$ prebri\v su 
stare vrijednosti komponenata od $\mathbf{x}^{(k)}$, \v cim se izra\v cunaju. Stoga nam 
nije potreban dodatni pomo\' cni vektor za pam\' cenje komponenti prethodne iteracije. S 
takvim modifikacijama Jacobijeve metode, dobivamo Gauss-Seidelovu metodu.

Dakle, dan je sustav jednad\v zbi
\begin{equation}
    \mathbf{Ax}=\mathbf{b}\mbox{,}
    \label{sustav2}
\end{equation}
gdje je matrica $\mathbf{A}\in\mathbb{R}^{n\times n}$ regularna i
$$
    a_{ii}\neq 0,\quad i=1,2,\ldots ,n\mbox{.}
$$
Gauss-Seidelov iterativni postupak za rje\v savanje sustava (\ref{sustav2}) definiran 
je sa
$$
    \mathbf{x}^{(k+1)}=-\mathbf{Lx}^{(k+1)}-
    \mathbf{Ux}^{(k)}+\mathbf{D}^{-1}\mathbf{b},\quad k=,0,1,2,\ldots ,
$$
odnosno sa
$$
    \mathbf{x}^{(k+1)}=\mathbf{B}_{GS}\mathbf{x}^{(k)}+\mathbf{d},\quad k=,0,1,2,\ldots ,
$$
gdje je
\begin{eqnarray*}
    \mathbf{B}_{GS} & = & -(\mathbf{I+L})^{-1}\mathbf{U} \\
    \mathbf{d} & = & \mathbf{D}^{-1}(\mathbf{I+L})^{-1}\mathbf{b}\mbox{.}
\end{eqnarray*}
Prema tome komponente vektora $\mathbf{x}^{(k+1)}$ izra\v cunavaju se na 
sljede\' ci na\v cin
$$
    x_i^{(k+1)}=\frac{1}{a_{ii}}\left( b_i - \sum_{j=1}^{i-1}a_{ij}x_j^{(k+1)} -
    \sum_{j=i+1}^{n}a_{ij}x_j^{(k)} \right) ,\quad i=1,2,\ldots ,n\mbox{.}
$$

Stoga ka\v zemo da je Jacobijeva metoda \emph{totalno kora\v cna}, dok 
se za Gauss-Seidelovu metodu ka\v ze da je \emph{jednokora\v cna}.

Uzev\v si u obzir navedene razlike izme\dj u Jacobijeve i Gauss-Seidelove meto\-de, 
razumno je o\v cekivati da Gauss-Seidelova metoda konvergira br\v ze od Jacobijeve. 
U ve{\'{c}}ini slu\v cajeva to je to\v cno, ali ne uvijek.

\begin{pokaz}
    Neka je
    $$
        \mathbf{A}=\left[ \begin{array}{rrr} 1 & -2 & 2 \\ -1 & 1 & -1  \\
        -2 & -2 & 1 \end{array} \right]
    $$
    dana matrica. Tada matrice $\mathbf{B}_J$ i $\mathbf{B}_{GS}$ glase
    $$
        \mathbf{B}_J=\left[ \begin{array}{rrr} 0 & 2 & -2 \\ 1 & 0 & 1  \\
        2 & 2 & 0 \end{array} \right]\mbox{i}\quad
        \mathbf{B}_{GS}=\left[ \begin{array}{rrr} 0 & 2 & -2 \\ 0 & 2 & -1  \\
        0 & 8 & -6 \end{array} \right]\mbox{.}
    $$
    Slijedi
    $$
        \rho (\mathbf{B}_J)=0\mbox{,}\quad\rho (\mathbf{B}_{GS})=2(1+\sqrt{2})\mbox{,}
    $$
    \v sto zna\v ci da Jacobijeva metoda konvergira, a Gauss-Seidelova divergira 
    (vidi \cite{diplomski}).
\end{pokaz}

\begin{pokaz}
    Neka je
    $$
        \mathbf{A}=\left[ \begin{array}{rrr} 1 & \frac{1}{2} & -\frac{1}{2} \\
        -1 & 1 & -1  \\ -\frac{1}{2} & \frac{1}{2} & 1 \end{array} \right]
    $$
    dana matrica. Tada za matrice $\mathbf{B}_J$ i $\mathbf{B}_{GS}$ vrijedi
    $$
        \rho (\mathbf{B}_J)=1\mbox{,}\quad\rho (\mathbf{B}_{GS})=\frac{1}{2}\mbox{,}
    $$
    pa se sada lako vidi da Gauss-Seidelova metoda konvergira, a Jacobijeva
    metoda divergira.
\end{pokaz}

O konvergenciji Gauss-Seidelove metode govore sljede\' ci teoremi.

\begin{teo}
    Neka je $\mathbf{A}$ strogo dijagonalno dominantna matrica ili ireducibilna
    dijagonalno dominantna matrica. Tada Gauss-Seidelova metoda konvergira za
    proizvoljan po\v cetni vektor $\mathbf{x}^{(0)}$.
\end{teo}

\begin{teo}
    Ako je matrica $\mathbf{A}\in\mathbb{R}^{n\times n}$ simetri\v cna i pozitivno
    definitna, onda Gauss-Seidelova metoda za rje\v savanje sustava (\ref{sustav2})
    konvergira za svaki po\v cetni vektor $\mathbf{x}^{(0)}$.
\end{teo}

\begin{teo}
    Neka je $\mathbf{A}$ trodijagonalna matrica. Tada ili i Jacobijeva i Gauss-Seidelova
    metoda za rje\v savanje sustava (\ref{sustav2}) konvergiraju ili obje divergiraju.
    Ako obje konvergiraju, Gauss-Seidelova metoda konvergira br\v ze.
\end{teo}

\section{SOR metoda}
Za\v cetnik metode sukcesivne nadrelaksacije (engl. \emph{successive overrelaxation 
method}), skra\' ceno SOR, je svakako D. M. Young koji je 1950. u svojoj doktorskoj 
disertaciji ukazao na prednosti dobivene u nekim slu\v cajevima kori\v stenjem 
fiksnog relaksacijskog parametra $\omega $ (vidi \cite{DMY}). Svakako treba naglasiti 
da se pojam relaksacijskog parametra mogao na\' ci i u ranijim radovima.

Od svih stacionarnih iterativnih metoda, SOR metoda se naj\v ce\v s\' ce koristi. 
U dana\v snje vrijeme su stacionarne iterativne metode ve\' cinom zamijenjene 
\emph{nestacionarnim iterativnim metodama}. No, mnoge stacionarne iterativne metode se 
koriste kod prekondicioniranja. Prekondicioniranje je bilo kakvo modificiranje 
originalnog linearnog sustava, koje na neki na\v cin olak\v sava rje\v savanje danog 
sustava. Odnosno, \v zeli se postoje\' ci sustav transformirati u ekvivalentan sustav 
koji ima npr. bolja spektralna svojstva. I do sada smo vidjeli kako je spektralni 
radijus kod stacionarnih iterativnih metoda vrlo va\v zan. Njegova va\v znost je vrlo 
velika i kod nestacionarnih iterativnih metoda.

SOR metoda je modifikacija Gauss-Seidelove metoda sa svrhom pobolj\v sanja 
konvergencije. Cilj tih modifikacija nije u tome da pro\v siri klasu matrica za koje 
iterativna metoda konvergira, ve\' c da ubrza konvergenciju. Kasnije \' cemo na 
primjerima vidjeti koliko se zna\v cajno konvergencija mo\v ze ubrzati.

Ponovno promatramo sustav
\begin{equation}
    \mathbf{Ax}=\mathbf{b}\mbox{,}
    \label{sustav_sor}
\end{equation}
gdje je $\mathbf{A}\in\mathbb{R}^{n\times n}$ uz pretpostavku
$$
    a_{ii}\neq 0\mbox{,}\quad i=1,2,\ldots ,n\mbox{.}
$$

Matricu $\mathbf{A}$ rastavimo na
$$
    \mathbf{A}=\mathbf{N+P}
$$
gdje je
\begin{eqnarray*}
    \mathbf{N} & = & \frac{1}{\omega }\mathbf{D}+\mathbf{\tilde{L}}\mbox{,}\\
    \mathbf{P} & = & \frac{\omega -1}{\omega}\mathbf{D}+\mathbf{\tilde{U}}\mbox{.}
\end{eqnarray*}
Pri tome su matrice $\mathbf{D}$, $\mathbf{\tilde{L}}$ i $\mathbf{\tilde{U}}$ definirane 
kao $\mathbf{D}=\mathop{\mathrm{diag}}(a_{11},a_{22},\ldots ,a_{nn})$, 
$\mathbf{\mbox{\~{L}}}$ je strogo donji trokutasti dio, a $\mathbf{\mbox{\~{U}}}$ 
strogo gornji trokutasti dio. Dok je $\omega$  realan broj razli\v cit od nule koji 
zovemo \textsf{relaksacijski parametar}.

Sada iz (\ref{sustav_sor}) dobivamo
$$
    \mathbf{Nx}=-\mathbf{Px}+\mathbf{b}
$$
odnosno
\begin{eqnarray*}
    \mathbf{D}\left( \frac{1}{\omega}\mathbf{I} + \mathbf{L} \right) \mathbf{x}^{(k+1)}
    & = & -\mathbf{D}\left( \frac{\omega -1}{\omega }\mathbf{I}+\mathbf{U} \right)
    \mathbf{x}^{(k)}+\mathbf{b}\\
    \left( \mathbf{I}+\omega \mathbf{L} \right) \mathbf{x}^{(k+1)} & = &
    \left( \left( 1-\omega \right) \mathbf{I} -\omega\mathbf{U} \right) \mathbf{x}^{(k)}
    +\mathbf{D}^{-1}\omega\mathbf{b}\mbox{,}
\end{eqnarray*}
pa je
$$
    \mathbf{x}^{(k+1)}=(\mathbf{I}+\omega \mathbf{L})^{-1}((1-\omega )\mathbf{I}
    -\omega\mathbf{U})\mathbf{x}^{(k)} + (\mathbf{I}+\omega \mathbf{L})^{-1}
    \mathbf{D}^{-1}\omega\mathbf{b}\mbox{,}\quad k=0,1,2,\ldots
$$
Uvedimo oznake
\begin{eqnarray*}
    \mathbf{B}_\omega & = &(\mathbf{I}+\omega \mathbf{L})^{-1}((1-\omega )\mathbf{I}
    -\omega\mathbf{U}) \\
    \mathbf{d} & = & (\mathbf{I}+\omega \mathbf{L})^{-1}
    \mathbf{D}^{-1}\omega\mathbf{b}\mbox{,}
\end{eqnarray*}
te slijedi
$$
    \mathbf{x}^{(k+1)}=\mathbf{B}_\omega \mathbf{x}^{(k)} + \mathbf{d}\mbox{,}\quad
    k=0,1,2,\ldots
$$
Slijedi
$$
    x_i^{(k+1)}=(1-\omega )x_i^{(k)}-\frac{\omega}{a_{ii}}\left( \sum_{j=1}^{i-1}
    a_{ij}x_j^{(k+1)}+\sum_{j=i+1}^{n}a_{ij}x_j^{(k)} \right) + \omega\frac{b_i}{a_{ii}}
    \mbox{,}\quad i=1,2,\ldots ,n\mbox{.}
    \label{sor_formula}
$$

Razlikujemo tri slu\v caja koja ovise o broju $\omega $. Izbor $\omega =1$ daje 
Gauss-Seidelovu metodu, $\omega <1$ se zove podrelaksacijski parametar (engl. 
\emph{underrelaxation}), a $\omega >1$ nadrelaksacijski parametar (engl. 
\emph{overrelaxation}).

\begin{teo}[Kahan]
    Za proizvoljnu matricu $\mathbf{A}$ vrijedi
    $$
        \rho (\mathbf{B}_\omega )\geq|\omega -1|
    $$
    za svaki $\omega$.
    \label{kahan}
\end{teo}

\noindent\textbf{\emph{Dokaz:}}
Po\v sto su  svojstvene vrijednosti $\lambda_1,\ldots ,\lambda_n$ od $\mathbf{B}_\omega$
nulto\v cke karakteristi\v cnog polinoma, vrijedi
$$
    \prod_{j=1}^{n}\lambda_j=\mathop{\mathrm{det}}\mathbf{B}_\omega\mbox{.}
$$
Odavde, zbog pravila za mno\v zenje determinanti i po\v sto su 
$\mathbf{I}+\omega\mathbf{L}$ i \linebreak $(1-\omega )\mathbf{I}-\omega\mathbf{U}$ 
trokutaste matrice, slijedi
$$
    \prod_{j=1}^{n}\lambda_j=\mathop{\mathrm{det}}(\mathbf{I}+\omega\mathbf{L})^{-1}
    \mathop{\mathrm{det}}((1-\omega )\mathbf{I}-\omega\mathbf{U})=(1-\omega )^n\mbox{.}
$$
Nadalje slijedi
$$
    \rho (\mathbf{B}_\omega )\geq|\omega -1|\mbox{.}
$$
{\ }\hfill $\square$

\begin{teo}[Ostrowski]
    Neka je $\mathbf{A}\in\mathbb{R}^{n\times n}$ simetri\v cna pozitivno definitna 
    matrica i pretpostavimo da je $0<\omega <2$. Tada SOR metoda konvergira prema 
    jedinstvenom rje\v senju od (\ref{sustav_sor}).
\end{teo}

\noindent\textbf{\emph{Dokaz:}}
Neka je $\lambda $ proizvoljna svojstvena vrijednost matrice $\mathbf{B}_\omega $ i 
neka je $\mathbf{y}\neq 0$ odgovaraju\' ci svojstveni vektor. Tada vrijedi
\begin{equation}
    \left( (1-\omega )\mathbf{I}-\omega\mathbf{U} \right)\mathbf{y}=
    \lambda(\mathbf{I}+\omega\mathbf{L})\mathbf{y}\mbox{.}
    \label{ostro_dok}
\end{equation}
Za lijevu stranu jednakosti (\ref{ostro_dok}), direktnim ra\v cunom dobivamo
$$
    (2-\omega )\mathbf{I}-\omega\mathbf{A}-\omega (\mathbf{U-L})=
    2\left( (1-\omega )\mathbf{I}-\omega\mathbf{U} \right)\mbox{,}
$$
a za desnu stranu vrijedi
$$
    (2-\omega)\mathbf{I}-\omega\mathbf{A}-\omega (\mathbf{U-L})=
    2\left( \mathbf{I}+\omega\mathbf{L} \right)\mbox{.}
$$
Poslije skalarnog mno\v zenja sa $\mathbf{y}$, iz (\ref{ostro_dok}) dobivamo
$$
    \lambda =\frac{(2-\omega )d-\omega a + \imath\omega s}
    {(2-\omega )d+\omega a + \imath\omega s}
$$
gdje je
$$
    a:=(\mathbf{Ay,y})\mbox{,}\quad d:=(\mathbf{Dy,y})\mbox{,}\quad
    s:=\imath (\mathbf{Uy-Ly,y})\mbox{.}
$$
Po\v sto je $\mathbf{A}$ pozitivno definitna, imamo $a>0$ i $d>0$ i po\v sto je 
$\mathbf{A}$ simetri\v cna, $s\in\mathbb{R}$. Iz
$$
    |(2-\omega)d-\omega a|<|(2-\omega )d+\omega a|
$$
za $0<\omega <2$ sada mo\v zemo zaklju\v citi da je $|\lambda <1|$. Stoga 
konvergencija SOR metode za $0<\omega <2$ slijedi iz Teorema \ref{opca_kon}.
{\ }\hfill $\square$

\begin{teo}
    SOR metoda ne konvergira za $\omega\leq 0$ i $\omega\geq 2$.
\end{teo}

\noindent\textbf{\emph{Dokaz:}}
O\v cito je da za matricu koraka
$$
    \mathbf{B}_\omega =(\mathbf{I}+\omega\mathbf{L})^{-1}((1-\omega
    )\mathbf{I}-\omega\mathbf{U})
$$
SOR metode vrijedi
\begin{eqnarray*}
    \det \mathbf{B}_\omega & = & (\det (\mathbf{I}+\omega\mathbf{L}))^{-1}
    \det ((1-\omega )\mathbf{I}-\omega\mathbf{U}) \\
    & = & (\det\mathbf{I})^{-1}(1-\omega)^n\det\mathbf{I} \\
    & = & (1-\omega )^n\mbox{,}
\end{eqnarray*}
jer su $\mathbf{I}+\omega\mathbf{L}$ i $(1-\omega )\mathbf{I}-\omega\mathbf{U}$ 
donja i gornja trokutasta matrica, a $\mathbf{L}$ i $\mathbf{U}$ strogo donja 
odnosno strogo gornja trokutasta matrica. Kako je
$$
    \rho (\mathbf{B}_\omega)^n\geq\prod_{j=1}^{n}|\lambda_i|=|\det\mathbf{B}_\omega |=
    |1-\omega |^n\mbox{,}
$$
gdje su $\lambda_j$ svojstvene vrijednosti matrice $\mathbf{B}_\omega$, slijedi
$$
    \rho (\mathbf{B}_\omega )\geq |1-\omega|\mbox{.}
$$
Prema Teoremu \ref{opca_kon} SOR metoda \' ce konvergirati ako i samo ako je
$\rho (\mathbf{B}_\omega )<1$, pa ako imamo da je $|1-\omega |\geq 1$, tada SOR 
metoda ne\' ce konvergirati. Ovaj uvjet biti \' ce ispunjen ako i samo ako je 
$\omega\leq 0$ i $\omega\geq 2$.
{\ }\hfill $\square$

\subsection{Odre\dj ivanje relaksacijskog parametra}
Odre\dj ivanje optimalnog relaksacijskog parametra $\omega_{opt}$ je u pravilu dosta 
komplicirano. U mnogim prakti\v cnim slu\v cajevima odre\dj ivanje optimalnog 
relaksacijskog parametra bi zahtijevao vi\v se rada ra\v cunala nego provo\dj enje 
iterativnog postupka. Sre\' com, pokazalo se da je i relativno dobra procjena 
vrijednosti relaksacijskog parametra i vi\v se nego dovoljna da se konvergencija 
iterativne metode zna\v cajno ubrza. Nadalje, za neke klase matrica se zna vrijednost 
optimalnog relaksiraju\' ceg parametra, dok se za neke druge klase matrica 
eksperimentalno utvrdila vrijednost relaksiraju\' ceg parametra koja zna\v cajno 
ubrzava konvergenciju.

Pokazati \' cemo kako se relaksacijski parametar $\omega $ ra\v cuna za klasu 
konzistentno ure\dj enih matrica (engl. \emph{consistently ordered matrices}).

\begin{naziv}
    Matrica $\mathbf{T}$ ima ``\textsf{svojstvo $\mathcal{A}$}" ako postoji 
    matrica permutacija $\mathbf{P}$ takva da je
    \begin{equation}
        \mathbf{PTP}^T=\left[ \begin{array}{cc}\mathbf{D}_1&\mathbf{M}_1 \\
        \mathbf{M}_2 & \mathbf{D}_2\end{array} \right]\mbox{,}
        \label{matr_svojstvo}
    \end{equation}
    gdje su $\mathbf{D}_1$ i $\mathbf{D}_2$ dijagonalne matrice.
    \label{def_svojstvo}
\end{naziv}

Mnoge matrice dobivene diskretizacijom parcijalnih diferencijalnih jednad\v zbi 
zadovoljavaju ``svojstvo $\mathcal{A}$". Na primjer, takva matrica je matrica koja 
dolazi iz aproksimacije s pet to\v caka Poissonove jednad\v zbe na kvadratu, pomo\' 
cu kona\v cnih diferencija. Ako \v cvorove na mre\v zi numeriramo na crveno-crni na\v 
cin (vidi \cite{DMY}), poput polja na \v sahovskoj plo\v ci, tada dobivamo matricu 
oblika (\ref{matr_svojstvo}). Dakle, isplati se posebno promatrati matrice sa 
``svojstvom $\mathcal{A}$" i njihovo pona\v sanje u SOR procesu.

\begin{naziv}
    Neka je $\mathbf{B}_J(\alpha )=-\alpha\mathbf{L}-\alpha^{-1}\mathbf{U}$. Tada je
    $\mathbf{B}_J(1)=\mathbf{B}_J$ matrica koraka za Jacobijevu metodu.
\end{naziv}

Najva{\v{z}}nija \v cinjenica o matricama sa ``svojstvom $\mathcal{A}$" dana je sljede\' 
cim teoremom.

\begin{teo}
    Za svaku $n\times n$ matricu sa ``svojstvom $\mathcal{A}$", za koju je $a_{ii}\neq
    0,\quad i=1,2,\ldots ,n$, postoji matrica permutacija $\mathbf{P}$ takva da je
    dekompozicija $\mathbf{\tilde{A}}=\mathbf{D}(\mathbf{I+L+U})$, permutirane
    matrice $\mathbf{\tilde{A}}=\mathbf{PAP}^T$ ima sljede\' ce svojstvo:

    Svojstvene vrijednosti matrice
    $$
        \mathbf{B}_J(\alpha )=-\alpha\mathbf{L}-\alpha^{-1}\mathbf{U}\mbox{,}\quad\alpha
        \in\mathbb{C}\mbox{,}\quad\alpha\neq 0\mbox{,}
    $$
    ne ovise o $\alpha $.
\end{teo}

\noindent\textbf{\emph{Dokaz:}}
Po Definiciji \ref{def_svojstvo} postoji matrica permutacija $\mathbf{P}$ takva da je
$$
    \mathbf{PAP}^T=\left[ \begin{array}{cc}\mathbf{D}_1 & \mathbf{M}_1 \\
    \mathbf{M}_2 & \mathbf{D}_2\end{array}\right]
    =\mathbf{D}(\mathbf{I}+\mathbf{L}+\mathbf{U})
    \mbox{,}
$$
$$
    \mathbf{D}=\left[ \begin{array}{cc}\mathbf{D}_1 & \mathbf{0} \\
    \mathbf{0} & \mathbf{D}_2\end{array}\right]\mbox{,}\quad
    \mathbf{L}=\left[ \begin{array}{cc}\mathbf{0} & \mathbf{0} \\
    \mathbf{D}_2^{-1}\mathbf{M}_2 & \mathbf{0}\end{array}\right]\mbox{,}\quad
    \mathbf{U}=\left[ \begin{array}{cc}\mathbf{0} & \mathbf{D}_1^{-1}\mathbf{M}_1 \\
    \mathbf{0} & \mathbf{0}\end{array}\right]\mbox{.}
$$
Ovdje su $\mathbf{D}_1$ i $\mathbf{D}_2$ regularne dijagonalne matrice. Za $\alpha\neq 0$
sada imamo
$$
    \mathbf{B}_J(\alpha )=-\left[ \begin{array}{cc}\mathbf{0} & 
    \alpha^{-1}\mathbf{D}_1^{-1}
    \mathbf{M}_1 \\ \alpha\mathbf{D}_2^{-1}\mathbf{M}_2 & \mathbf{0}\end{array}\right]
    =-\mathbf{S}_\alpha\left[ \begin{array}{cc}\mathbf{0} & 
    \mathbf{D}_1^{-1}\mathbf{M}_1 \\
    \mathbf{D}_2^{-1}\mathbf{M}_2 & \mathbf{0}\end{array}\right]\mathbf{S}_\alpha^{-1}=
    \mathbf{S}_\alpha\mathbf{B}_J(1)\mathbf{S}_\alpha^{-1}\mbox{,}
$$
gdje je $\mathbf{S}_\alpha $ regularna dijagonalna matrica
$$
    \mathbf{S}_\alpha =\left[ \begin{array}{cc}\mathbf{I}_1 & \mathbf{0} \\
    \mathbf{0} & \alpha\mathbf{I}_2\end{array}\right]\mbox{,}
$$
a $\mathbf{I}_1$ i $\mathbf{I}_2$ jedini\v cne matrice. Matrice $\mathbf{B}_J(\alpha )$
i $\mathbf{B}_J(1)$ su sli\v cne, pa slijedi da imaju jednake svojstvene vrijednosti.
{\ }\hfill $\square$

\begin{naziv}
    Neka je $\mathbf{A}$ bilo koja matrica takva da je
    $\mathbf{A}=\mathbf{D+\tilde{L}+\tilde{U}}$ i
    $$
        \mathbf{B}_J(\alpha )=-\alpha\mathbf{D}^{-1}\mathbf{\tilde{L}}-\alpha^{-1}
        \mathbf{D}^{-1}\mathbf{\tilde{U}}=-\alpha\mathbf{L}-\alpha^{-1}\mathbf{U}\mbox{.}
    $$
    Ako svojstvene vrijednosti matrice $\mathbf{B}_J(\alpha )$ ne ovise o $\alpha $,
    tada matricu $\mathbf{A}$ zovemo \textsf{konzistentno ure\dj ena matrica}.
\end{naziv}

\begin{teo}[Young, Varga]
    Neka je $\mathbf{A}$ konzistentno ure\dj ena matrica i $\omega\neq 0$. Tada vrijedi:
    \begin{itemize}
        \item[(a)] Svojstvene vrijednosti matrice $\mathbf{B}_J=-\mathbf{L}-\mathbf{U}$
        pojavljuju se u $\pm$ parovima.
        \item[(b)] Ako je $\mu$ svojstvena vrijednost matrice $\mathbf{B}_J$ i
        \begin{equation}
            (\lambda + \omega - 1)^2=\lambda\omega^2\mu^2\mbox{,}
            \label{trostruki}
        \end{equation}
        tada je $\lambda$ svojstvena vrijednost matrice $\mathbf{B}_\omega $.
        \item[(c)] Obratno, ako je $\lambda\neq 0$ svojstvena vrijednost matrice
        $\mathbf{B}_\omega $ i vrijedi (\ref{trostruki}), tada je $\mu $ 
        svojstvena vrijednost matrice $\mathbf{B}_J$.
    \end{itemize}
\end{teo}

\noindent\textbf{\emph{Dokaz:}}
\begin{itemize}
    \item[\emph{(a)}]
    Konzistentna ure\dj enost povla\v ci da svojstvene vrijednosti matrice
    $\mathbf{B}_J(\alpha )$ ne ovise o $\alpha $, pa matrice 
    $\mathbf{B}_J=\mathbf{B}_J(1)$ i
    $\mathbf{B}_J(-1)=\mathbf{B}_J(1)$ imaju iste svojstvene vrijednosti. Stoga se one
    pojavljuju u $\pm$ parovima.
    \item[\emph{(b)}]
    Jer je $\det (\mathbf{I}+\omega\mathbf{L})=1$ za svaki $\omega$, slijedi
    \begin{eqnarray}
        \det (\lambda \mathbf{I}-\mathbf{B}_\omega ) & = &
        \det\left( (\mathbf{I}+\omega\mathbf{L})(\lambda\mathbf{I}-
        \mathbf{B}_\omega)\right)\nonumber \\
        & = & \det \left( \lambda\mathbf{I}+\lambda\omega\mathbf{L}-(1-\omega)\mathbf{I}
        +\omega\mathbf{U} \right)\label{bekan}\\
        & = & \det \left( (\lambda +\omega -1)\mathbf{I}+\lambda\omega\mathbf{L}+
        \omega\mathbf{U} \right)\mbox{.}\nonumber
    \end{eqnarray}
    Neka je $\mu $ svojstvena vrijednost matrice $\mathbf{B}_J=-\mathbf{L}-\mathbf{U}$
    i $\lambda $ rje\v senje jednakosti (\ref{trostruki}). Tada je
    $$
        \lambda +\omega -1=\sqrt{\lambda}\omega\mu\quad\mathrm{ili}\quad\lambda
        +\omega -1=-\sqrt{\lambda}\omega\mu\mbox{.}
    $$
    Zbog \emph{(a)}, a bez smanjenja op\' cenitosti mo\v zemo pretpostaviti da je
    $$
        \lambda +\omega -1=\sqrt{\lambda }\omega\mu
        \mbox{.}
    $$
    Ako je $\lambda =0$, tada je $\omega =1$, pa iz (\ref{bekan}) slijedi
    $$
        \det (0\cdot\mathbf{I}-\mathbf{B}_1))\det (\mathbf{U})=0\mbox{,}
    $$
    tj. $\lambda $ je svojstvena vrijednost matrice $\mathbf{B}_\omega$. Ako je
    $\lambda\neq 0$ iz (\ref{bekan}) slijedi da je
    \begin{eqnarray}
        \det (\lambda\mathbf{I}-\mathbf{B}_\omega ) & = &
        \det \left( (\lambda +\omega -1)\mathbf{I}+\sqrt{\lambda}\omega
        \left( \sqrt{\lambda}\mathbf{L}+\frac{1}{\sqrt{\lambda}}\mathbf{U}
        \right) \right) \nonumber \\
        & = & (\sqrt{\lambda}\omega)^n\det\left( \mu\mathbf{I}+\left(
        \sqrt{\lambda}\mathbf{L}
        +\frac{1}{\sqrt{\lambda}}\mathbf{U} \right) \right) \label{nakraj} \\
        & = & (\sqrt{\lambda}\omega)^n\det (\mu\mathbf{I}+(\mathbf{L+U}))\nonumber \\
        & = & 0\mbox{,}\nonumber
    \end{eqnarray}
    jer matrica $\mathbf{B}_J(\sqrt{\lambda})=-\sqrt{\lambda}\mathbf{L}-
    (1/\sqrt{\lambda})\mathbf{U}$ ima iste svojstvene vrijednosti kao matrica
    $\mathbf{B}_J=-\mathbf{L}-\mathbf{U}$ i $\mu $ je svojstvena vrijednost
    matrice $\mathbf{B}_J$.
    \item[\emph{(c)}]
    Neka je $\lambda\neq 0$ svojstvena vrijednost matrice $\mathbf{B}_\omega$, i $\mu $
    broj koji zadovoljava (\ref{trostruki}), odnosno $ \lambda +\omega -1=
    \pm\omega\sqrt{\lambda}\mu $. Zbog \emph{(a)}, dovoljno je dokazati da je broj $\mu $
    uz $\lambda +\omega -1=\omega\sqrt{\lambda}\mu $ svojstvena vrijednost matrice
    $\mathbf{B}_J$. Ovo, me\dj utim, slijedi odmah iz (\ref{nakraj}).
\end{itemize}
{\ }\hfill $\square$

\begin{kor}
    Neka je $\mathbf{A}$ konzistentno ure\dj ena matrica. Tada za matricu koraka
    $\mathbf{B}_{GS}=\mathbf{B}_1=-(\mathbf{I}+\mathbf{L})^{-1}\mathbf{U}$
    Gauss-Seidelove metode imamo
    $$
        \rho (\mathbf{B}_{GS})=\left( \rho(\mathbf{B}_J) \right)^2\mbox{.}
    $$
    Ovo zna\v ci da je Gauss-Seidelova metoda dva puta br\v za od Jacobijeve.
\end{kor}

\noindent\textbf{\emph{Dokaz:}}
Izbor $\omega =1$ je ekvivalentan Gauss-Seidelovoj metodi, pa je $\lambda^2=\lambda\mu^2$
ili $\lambda =\mu^2$.
{\ }\hfill $\square$

Sljede\' ci teorem nam daje $\omega_{opt}$ koji minimizira $\rho (\mathbf{B}_\omega)$.

\begin{teo}
    Neka je $\mathbf{A}$ konzistentno ure\dj ena matrica, neka matrica $\mathbf{B}_J$
    ima realne svojstvene vrijednosti, i neka je $\mu =\rho (\mathbf{B}_J)<1$. Tada je
    \begin{eqnarray*}
        \omega_{opt} & = & \frac{2}{1+\sqrt{1-\mu^2}}\mbox{,} \\
        \rho (\mathbf{B}_{\omega_{opt}}) & = & \omega_{opt}-1=\frac{\mu^2}{\left(
        1+\sqrt{1-\mu^2}\right) ^2}\mbox{,} \\
        \rho (\mathbf{B}_\omega )&=&\left\{ \begin{array}{ll} \omega -1\mbox{,} &
        \omega_{opt}\leq\omega\leq 2 \\ 1-\omega +\frac{1}{2}\omega^2\mu^2
        +\omega\mu\sqrt{1-\omega +\frac{1}{4}\omega^2\mu^2}\mbox{,}&0<\omega\leq
        \omega_{opt}\ \end{array} \right. \mbox{,}
    \end{eqnarray*}
    (vidi sliku \ref{slika}).
    \begin{figure}[h]
        \resizebox*{\textwidth}{!}{\includegraphics*[3cm,19cm][16cm,28cm]{omega_sl2.eps}}
        \caption{Spektralni radijus matrice $\mathbf{B}_\omega$}
        \label{slika}
    \end{figure}
\end{teo}

\noindent\textbf{\emph{Dokaz:}}
(vidi \cite{nela})
{\ }\hfill $\square$

\section{Ocjena gre\v ske}
Ra\v cunala su strojevi koji \' ce ponavljati jednu te istu radnju proizvoljno puta, 
a dana\v snja su ra\v cunala vrlo brza i mo\' cna. No, u praksi se mo\v ze obaviti samo 
kona\v can broj iteracija, pa je vrlo va\v zno znati kada je aproksimacija dovoljno 
dobra.

Proces se zaustavlja poslije kona\v cnog broja koraka $k$, pa je vektor 
$\mathbf{x}^{(k)}$ tada pribli\v zno rje\v senje danog sustava. Pitanje koje se 
prirodno name\' ce je ocjena veli\v cine tako nastale pogre\v ske $\|\mathbf{x}^* 
-\mathbf{x}^{(k)}\|$. U tu svrhu promatrati \' cemo sustav
\begin{equation}
    \mathbf{x}=\mathbf{Mx}+\mathbf{d}\mbox{,}
    \label{gr_sustav}
\end{equation}
odnosno iterativni postupak
\begin{equation}
    \mathbf{x}^{(k+1)}=\mathbf{Mx}^{(k)}+\mathbf{d}\mbox{,}\quad k=0,1,2,\ldots
    \label{gr_iterativni}
\end{equation}

\begin{teo}
    Neka za matricu $\mathbf{M}\in\mathbb{R}^{n\times n}$ vrijedi
    $$
        \|\mathbf{My}-\mathbf{Mz}\|\leq\alpha\|\mathbf{y-z}\|\mbox{,}\quad
        \mbox{za svaki }\mathbf{y,z}\in\mathbb{R}^{n\times n}\mbox{,}
    $$
    za neki $\alpha\in[0,1)$. Ako je (\ref{gr_iterativni}) za proizvoljni
    $\mathbf{x}^{(0)}\in\mathbb{R}^{n}$, onda je
    \begin{equation}
        \|\mathbf{x}^{*}-\mathbf{x}^{(k)}\|\leq\frac{\alpha }{1-\alpha }
        \|\mathbf{x}^{(k)}-\mathbf{x}^{(k-1)}\|\mbox{,}\quad k=1,2,\ldots\mbox{,}
        \label{gr_prvitm}
    \end{equation}
    gdje je $\mathbf{x}^{*}$ to\v cno rje\v senje sustava (\ref{gr_sustav}).
    \label{gr_teoremprvi}
\end{teo}

\noindent\textbf{\emph{Dokaz:}}
Rje\v senje $\mathbf{x}^{*}$ sustava (\ref{gr_sustav}) postoji i jedinstveno je i 
$\displaystyle\lim_{k\rightarrow\infty}\mathbf{x}^{(k)}=\mathbf{x}^{*}$ (Teorem 
\ref{banach}). Za svaki prirodan broj $m$ i $k$ vrijedi
\begin{eqnarray*}
    \|\mathbf{x}^{(k+m)}-\mathbf{x}^{(k+m-1)}\| & = &
    \|\mathbf{Mx}^{(k+m-1)}-\mathbf{Mx}^{(k+m-2)}\| \\
    & \leq & \alpha\|\mathbf{x}^{(k+m-1)}-\mathbf{x}^{(k+m-2)}\| \\
    & \vdots & \\
    & \leq & \alpha^m\|\mathbf{x}^{(k)}-\mathbf{x}^{(k-1)}\|\mbox{.}
\end{eqnarray*}
Nadalje imamo
\begin{eqnarray*}
    \|\mathbf{x}^{(k)}-\mathbf{x}^{(k+m)}\|
    & \leq & \|\mathbf{x}^{(k)}-\mathbf{x}^{(k+1)}\|+ \|\mathbf{x}^{(k+1)}
    -\mathbf{x}^{(k+2)}\|+\cdots + \|\mathbf{x}^{(k+m-1)}-\mathbf{x}^{(k+m)}\| \\
    & \leq & \alpha\|\mathbf{x}^{(k)}-\mathbf{x}^{(k-1)}\|+\alpha^2
    \|\mathbf{x}^{(k)}-\mathbf{x}^{(k-1)}\|+\cdots +\alpha^m\|\mathbf{x}^{(k)}-
    \mathbf{x}^{(k+1)}\| \\ & \leq &
    \alpha\frac{1-\alpha^m}{1-\alpha }\|\mathbf{x}^{(k)}-\mathbf{x}^{(k-1)}\|\mbox{.}
\end{eqnarray*}
Kako je $\displaystyle\lim_{k\rightarrow\infty}\mathbf{x}^{(k+m)}=\mathbf{x}^{*}$ i 
$\alpha <1$ slijedi
$$
    \|\mathbf{x}^{(k)}-\mathbf{x}^{*}\|\leq\frac{\alpha }{1-\alpha }\|\mathbf{x}^{(k)}
    -\mathbf{x}^{(k-1)}\|\mbox{,}\quad k=1,2,\ldots
$$
{\ }\hfill $\square$

\begin{teo}
    Neka je
    $$\|M\|<1\mbox{,}$$
    $$
        \mathbf{x}^{(k+1)}=\mathbf{Mx}^{(k)}+\mathbf{d}\mbox{,}\quad k=0,1,2,\ldots
    $$
    i
    $$
        \lim_{k\rightarrow\infty}\mathbf{x}^{(k)}=\mathbf{x}^{*}\mbox{.}
    $$

    Tada je
    $$
        \|\mathbf{x}^{*}-\mathbf{x}^{(k)}\|\leq\frac{\|\mathbf{M}\|}{1-\|\mathbf{M}\|}
        \|\mathbf{x}^{(k)}-\mathbf{x}^{(k-1)}\|\mbox{,}\quad k=1,2,\ldots
    $$
\end{teo}

\noindent\textbf{\emph{Dokaz:}}
Dokaz slijedi neposredno iz Teorema \ref{gr_teoremprvi} i
$$
    \|\mathbf{Mx-My}\|\leq\|\mathbf{M}\|\|\mathbf{x-y}\|\
$$
sa $\alpha =\|\mathbf{M}\|$.
{\ }\hfill $\square$

Dobivene ocjene pogre\v ske $\|\mathbf{x}^{*}-\mathbf{x}^{(k)}\|$ mogu se koristiti za 
svaki iterativni postupak oblika (\ref{gr_iterativni}) bez obzira na na\v cin na koji 
smo iz sustava $\mathbf{Ax}=\mathbf{b}$ dobili ekvivalentan sustav oblika 
(\ref{gr_sustav}).

Do sada smo pretpostavljali da se sva ra\v cunanja izvode to\v cno, odnosno da nema 
pogre\v saka pri zaokru\v zivanju. U praksi uvijek dolazi do pogre\v ske zaokru\v 
zivanja, jer ra\v cunala imaju svoja ograni\v cenja. Vrlo va\v zna stvar kod 
iterativnih metoda je da gre\v ska zaokru\v zivanja ne utje\v ce mnogo na njih. Razlog 
tome je \v sto iterativne metode u svakoj iteraciji nastoje pobolj\v sati trenutnu 
aproksimaciju i nije va\v zno koliko je to\v cna ta aproksimacija. Problem se javlja 
kada iterativna metoda konvergira previ\v se sporo, \v sto ima za posljedicu da zbog 
pogre\v ske zaokru\v zivanja aproksimacija $\mathbf{x}^{(k)}$ bude jednaka sljede\' coj 
aproksimaciji $\mathbf{x}^{(k)}$.

\begin{pokaz}
    Neka je dan sustav
    \begin{eqnarray*}
        1.00000x_1+0.70710x_2 & = & 0.29290 \\
        0.70710x_1+0.50000x_2 & = & 0.20711\mbox{.}
    \end{eqnarray*}
    Matrica koraka $\mathbf{B}_{GS}$ Gauss-Seidelovog iterativnog postupka ima
    spektralni radijus $\rho (\mathbf{B}_{GS})=0.99998$. Polaze\' ci od
    $\mathbf{x}^{(0)}=[0.00000,0.00000]^T$ i ra\v cunaju\' ci s pet mjesta iza
    decimalne to\v cke dobivamo
    $$
        \lim_{k\rightarrow\infty}=\mathbf{x}^{(0)}\mbox{,}
    $$
    \v sto nije to\v cno, jer rje\v senje danog sustava glasi
    $\mathbf{x}^{*}=[0.26267\ldots ,0.04275\ldots ]^T$. O\v cito, spora
    konvergencija Gauss-Seidelovog iterativnog procesa i pogre\v ske zaokru\v
    zivanja su uzrok tome.
\end{pokaz}

Sljede\' ci teorem govori o iterativnom postupku kod kojeg se u svakom koraku 
pojavljuje pogre\v ska koja je posljedica pogre\v ske zaokru\v zivanja.

\begin{teo}
    Neka se vektori niza $\mathbf{x}^{(0)}$, $\mathbf{x}^{(1)}$,
    $\mathbf{x}^{(2)}\ldots $,  koji zadovoljavaju uvjet
    $$
       \mathbf{x}^{(k+1)}=\mathbf{Mx}^{(k)}+\mathbf{d}\mbox{,}\quad k=0,1,2,\ldots
    $$
    gdje je $\|\mathbf{M}\|<1$, izra\v cunavaju s pogre\v skama zaokru\v zivanja tako
    da se dobiva niz $\mathbf{\bar{x}}^{(0)}$, $\mathbf{\bar{x}}^{(1)}$,
    $\mathbf{\bar{x}}^{(2)}\ldots $

    Ako je
    $$
        \mathbf{\bar{x}}^{(k+1)}=\mathbf{M}\mathbf{\bar{x}}^{(k)}+\mathbf{d}
        +\mathbf{r}^{k}\mbox{,}\quad k=0,1,2,\ldots
    $$
    $$
        \|\mathbf{r}^{(k)}\|\leq\varepsilon\mbox{,}\quad k=0,1,2,\ldots
    $$
    i
    $$
        \mathbf{x}^{(0)}=\mathbf{\bar{x}}^{(0)}\mbox{,}
    $$
    onda je
    $$
        \|\mathbf{\bar{x}}^{(k)}-\mathbf{x}^{(k)}\|\leq\frac{\varepsilon}
        {1-\|\mathbf{M}\|}\mbox{,}\quad k=0,1,2,\ldots\
    $$
    i
    $$
        \|\mathbf{x}^{*}-\mathbf{\bar{x}}^{(k)}\|\leq\frac{1}{1-\|\mathbf{M}\|}
        \left( \varepsilon\frac{1+\|\mathbf{M}\|}{1-\|\mathbf{M}\|}+\|\mathbf{M}\|
        \| \mathbf{\bar{x}}^{(k)}-\mathbf{\bar{x}}^{(k-1)} \|\right)
    $$
    gdje je $\displaystyle\mathbf{x}^{*}=\lim_{k\rightarrow\infty}\mathbf{x}^{(k)}$ 
    to\v cno rje\v senje sustava (\ref{gr_sustav}).
\end{teo}

\section{Jacobijeva, Gauss-Seidelova i SOR metoda u programskom paketu \textsc{Mathematica}}

\subsection*{Jacobijeva metoda}
\begin{verbatim}
Jac[a_, b_, n_, it_, gr_] :=
  Module[
    {i, k, xs, xn},
    xs = Table[0, {i, n}];
    xn = xs;
    k = 1;
    r = -b;
    PNormaVektora[r, n, 2];
    While[
      (No > gr) && (k <= it),
      Do[
        xn[[i]] = (b[[i]] - Sum[a[[i, j]] xs[[j]], {j, i - 1}] -
                Sum[a[[i, j]] xs[[j]], {j, i + 1, n}])/a[[i, i]],
        {i, n}
        ];
      r = a.xn - b;
      PNormaVektora[r, n, 2];
      xs = xn;
      pr = k;
      k = k + 1;
      ];
    Print["It_", pr, "=", N[xn]];
    ]
\end{verbatim}

\subsection*{Gauss-Seidelova metoda}
\begin{verbatim}
GS[a_, b_, n_, it_, gr_] :=
  Module[
    {i, k, xs, xn},
    xn = Table[0, {i, n}];
    k = 1;
    r = -b;
    PNormaVektora[r, n, 2];
    While[
      (No > gr) && (k <= it),
      Do[
        xn[[i]] = (b[[i]] - Sum[a[[i, j]] xn[[j]], {j, i - 1}] -
                Sum[a[[i, j]] xn[[j]], {j, i + 1, n}])/a[[i, i]],
        {i, n}
        ];
      r = a.xn - b;
      PNormaVektora[r, n, 2];
      pr = k;
      k = k + 1;
      ];
    Print["It_", pr, "=", N[xn]];
    ]
\end{verbatim}

\subsection*{SOR metoda}
\begin{verbatim}
SOR[a_, b_, n_, it_, gr_, om_] :=
  Module[
    {i, k, xs, xn},
    xs = Table[0, {i, n}];
    xn = xs;
    k = 1;
    r = -b;
    PNormaVektora[r, n, 2];
    While[
      (No > gr) && (k <= it),
      Do[
        xn[[i]] = (1 - om)xs[[i]] + (b[[i]] -
                  Sum[a[[i, j]] xn[[j]], {j, i - 1}] -
                  Sum[a[[i, j]] xs[[j]], {j, i + 1, n}])(om/a[[i, i]]),
        {i, n}
        ];
      r = a.xn - b;
      PNormaVektora[r, n, 2];
      xs = xn;
      pr = k;
      k = k + 1;
      ];
    Print["It_", pr, "=", N[xn]];
    ]
\end{verbatim}

\subsection*{Ostali moduli}

\subsubsection*{P-norma vektora}
\begin{verbatim}
PNormaVektora[x_, n_, p_] :=
  Module[
    {i},
    Clear[No];
    If[
      (IntegerQ[p]) && (p > 0),
      No = N[(Sum[Abs[x[[i]]]^p, {i, n}])^(1/p)]
      ];
    ]
\end{verbatim}

\subsubsection*{Generiranje podataka}
\begin{verbatim}
GenPod[n_] :=
    Module[
      {a},
      a = Table[-1, {i, 1, n - 2}];
      a = Insert[a, 0, n/2];
      A =
        Table[Switch[i - j, n/2, -1, 1, a[[i - 1]], 0, 4, -1,
            a[[i]], -n/2, -1, _, 0], {i, n}, {j, n}];
      bo = Table[1, {i, n}];
      ];
\end{verbatim}

\subsubsection*{$\mathbf{B}_J$ matrica}
\begin{verbatim}
MatricaBJ[a_, n_] :=
  Module[
    {i, j},
    BJ = Table[0, {i, n}, {j, n}];
    Do[
      Do[
        BJ[[i, j]] = -a[[i, j]]/a[[i, i]], {j, i - 1}
        ];
      Do[
        BJ[[i, j]] = -a[[i, j]]/a[[i, i]], {j, i + 1, n}
        ],
      {i, n}
      ];
    ]
\end{verbatim}

\subsubsection*{Spektralni radijus}
\begin{verbatim}
SpecRad[a_, n_] :=
  Module[
    {i},
    Sv = Eigenvalues[a];
    Ro = N[Abs[Sv[[1]]]];
    Do[
      If[
        Ro < Abs[Sv[[i]]], Ro = N[Abs[Sv[[i]]]], Ro = Ro
        ],
      {i, n}
      ];
    ]
\end{verbatim}

\subsubsection*{Testiranje}
\begin{verbatim}
velicina = 50;
GenPod[velicina];
Timing[Jac[A, bo, velicina, 200, 0.0001]]
Timing[GS[A, bo, velicina, 200, 0.0001]]
MatricaBJ[A, velicina];
Timing[SpecRad[BJ, velicina];]
om = N[2/(1 + Sqrt[1 - (Ro^2)])]
Timing[SOR[A, bo, velicina, 200, 0.0001, om]]
\end{verbatim}

\subsubsection*{Testiranje}
\begin{verbatim}
velicina = 50;
GenPod[velicina];
Timing[SOR[A, bo, velicina, 200, 0.0001, 0.5]]
Timing[SOR[A, bo, velicina, 200, 0.0001, 0.8]]
Timing[SOR[A, bo, velicina, 200, 0.0001, 1.2]]
Timing[SOR[A, bo, velicina, 200, 0.0001, 1.5]]
Timing[SOR[A, bo, velicina, 200, 0.0001, 1.8]]
MatricaBJ[A, velicina];
Timing[SpecRad[BJ, velicina];]
om = N[2/(1 + Sqrt[1 - (Ro^2)])]
Timing[SOR[A, bo, velicina, 200, 0.0001, om]]
\end{verbatim}

%
% Literatura
%

\begin{thebibliography}{123}

\bibitem{nela}
\textsc{N.Bosner}, \emph{Iterativne metode za rje\v savanje linearnih sustava}, diplomski rad, Matemati\v cki odjel, PMF, Zagreb, \textsf{2001.}

\bibitem{diplomski}
\textsc{M.Vrzi\' c}, \emph{Veliki rijetki sustavi}, diplomski rad, Odjel za matematiku, Osijek, \textsf{2000.}

\bibitem{sci}
\textsc{R.Scitovski}, \emph{Numeri\v cka matematika}, Elektrotehni\v cki fakultet, Osijek, \textsf{1999.}

\bibitem{DMY}
\textsc{D.M.Young}, \emph{Iterative Solution of Large Linear Systems}, Academic Press, New York, \textsf{1972.}

\bibitem{Kress}
\textsc{R.Kress}, \emph{Numerical Analysis}, Springer-Verlag, Berlin, \textsf{1998.}

\bibitem{Ortega}
\textsc{J.M.Ortega}, \emph{Numerical Analysis}, SIAM, Philadelphia, \textsf{1990.}

\bibitem{nenegativne}
\textsc{A. Berman,R.J.Plemmons}, \emph{Nonnegative Matrices in the Mathematical Sciences}, SIAM, Philadelphia, \textsf{1994.}

\bibitem{templates}
\textsc{R.Barrett,M.Berry,T.F.Chan,J.Demmel,J.Donato,J.Dongarra, V.Eijkhont,R.Pozo,
C.Rpmine,H.Von der Vorst}, \emph{Templates for the Solution of Linear Systems: Bilding Blocks for Iterative Methods}, SIAM, Philadelphia, \textsf{1994.}

\end{thebibliography}

\end{document}



\noindent\textbf{\emph{Dokaz:}}
{\ }\hfill $\square$
