\documentclass[xcolor=svgnames]{beamer}
\usepackage{multimedia}
\mode<presentation>
{
  \usetheme{Berlin}
  \setbeamercovered{transparent}
}
\useoutertheme{shadow}

\setbeamercolor{normal text}{fg=DarkSlateBlue,bg=white}
\usepackage[slovene]{babel}
\usepackage[latin1]{inputenc}
%\usepackage{times}
%usepackage[T1]{fontenc}
\newtheorem{primer}[theorem]{Primer} 
\setbeamertemplate{blocks}[rounded][shadow=true]

\title[Iterativno re\v{s}evanje sistemov linearnih ena\v{c}b]
{Iterativno re\v{s}evanje sistemov linearnih ena\v{c}b}

\subtitle{Numeri\v{c}ne metode, sistemi linearnih ena\v{c}b}

\author[Borut] % 
{B.~Jur\v{c}i\v{c}~Zlobec\inst{1}}

\institute[Univerza v Ljubljani Slovenia] % 
{
  \inst{1}%
    Univerza v Ljubljani,\\Fakulteta za Elektrotehniko\\ 
    1000 Ljubljana, Tr\v{z}a\v{s}ka 25, Slovenija
}


\date[BF 2012] % 
{Numeri\v{c}ne metode FE, Ljubljana, Slovenija \today}

\subject{Numeri\v{c}ne metode}


\AtBeginSubsection[]
{
  \begin{frame}<beamer>{Vsebina}
    \tableofcontents[currentsection,currentsubsection]
  \end{frame}
}


\begin{document}

\begin{frame}
 \titlepage
\end{frame}

\begin{frame}{}
  \tableofcontents
\end{frame}


\section{Iterativno re"sevanje sistemov linearnih ena"cb}

\subsection{Sistem linearnih ena"cb}

\begin{frame}{}
  \begin{itemize}
  \item Sistem linearnih ena"cb z $n$ neznankami.
	$$
		a_{i1}x_1+a_{i2}x_2+\cdots+a_{in}=b_i\quad i=1,\dots,n
	$$
  \item V matri"cni obliki zapi"semo: $$ \mathbf{A}\,\mathbf{x}=\mathbf{b} $$
  \item Matrika $\mathbf{A}=(a_{ij})_{n\times n}$ je matrika sistema,\\ 
	(koeficieti pred nezanakami).
  \item Vektor $\mathbf{x}=(x_{i})_n$ je vektor neznank in 
  \item vector $\mathbf{b}=(b_i)_n$ je vektor svobodnih "clenov na desni strani.  
  \end{itemize}
\end{frame}

\subsection{Razcep matrike sistema}
\begin{frame}{Splo"sno}
\begin{itemize}
  \item Razcepimo matriko $\mathbf{A}$ na razliko matrik $\mathbf{A}=\mathbf{M}-\mathbf{N}$.
  \item Razcep je smiselen, "ce lahko na preprost na"cin izra"cunamo inverzno matrtiko $\mathbf{M}^{-1}$.
  \item Zapi"semo sistem 
	\begin{eqnarray*}
		(\mathbf{M}-\mathbf{N})\,\mathbf{x}&=&\mathbf{b}\\
		\mathbf{M}\,\mathbf{x}&=&\mathbf{N}\,\mathbf{x}+\mathbf{b}\\
		\mathbf{x}&=&\mathbf{M}^{-1}\mathbf{N}\,\mathbf{x}+\mathbf{M}^{-1}\mathbf{b}		
	\end{eqnarray*}  
\end{itemize}
\end{frame}

\begin{frame}{Iteracija}
\begin{itemize}
  \item Ozna"cimo matriko $\mathbf{S}=\mathbf{M}^{-1}\mathbf{N}$,\\ 
	ki ji re"cemo iteracijska matrika in vektor 
	$\mathbf{c}=\mathbf{M}^{-1}\mathbf{b}$.
  \item Sistem zapi"semo z novimi oznakami: 
	$$\mathbf{x}=\mathbf{S}\,\mathbf{x}+\mathbf{c}.$$
  \item Izberemo za"cetni pribli"zek $\mathbf{x}^{(0)}$ in spro"zimo iteracijo 
	$$\mathbf{x}^{(k+1)}=\mathbf{S}\,\mathbf{x}^{(k)}+\mathbf{c},\quad k=0,1,\dots$$ 
\end{itemize}
\end{frame}

\subsection{Konvergenca}

\begin{frame}{Spektralni radij}
\begin{itemize}
	\item  \textit{Spektralni radij matrike} je enak absolutno najve"cji lastni vrednosti matrike.  
	\item  Spektralni radij matrike $\mathbf{S}$ ozna"cimo z $\rho(\mathbf{S})$.
        \item  Spektralni radij matrike je manj"si ali enak normi matrike,
		$\rho(\mathbf{S})\le\|\mathbf{S}\|$.
	\item  Zaporedje $\mathbf{x}^{(k)}$ je konvergentno, ko je $\rho(\mathbf{S})<1$.
\end{itemize}
\end{frame}


\subsection{Jacobieva in Gauss-Sidlova iteracija}

\begin{frame}{}
Razcepimo matriko $\mathbf{A}$ na vsoto $\mathbf{A}=\mathbf{L}+\mathbf{D}+\mathbf{U}$.\\
Sumandi so spodnjetrikotna, diagonalna in zgornjetrikotna matrika matrike $\mathbf{A}$.
\begin{block}{Jacobijeva iteracija}
	$\mathbf{M}=\mathbf{D}$ in $\mathbf{N}=-\mathbf{L}-\mathbf{U}$
\end{block}

\begin{block}{Gauss-Seidlova iteracija}
        $\mathbf{M}=\mathbf{D}+\mathbf{L}$ in $\mathbf{N}=-\mathbf{U}$
\end{block}
\end{frame}

\begin{frame}{}
\begin{block}{Diagonalno dominantne matrike}
	Matrika je diagonalno dominantna, "se je absolutna vsota izvediagonalnih 
	"clenov matrike maj"sa od absolutne vrednosti diagonalnega "clena. 
\end{block}
$$
	|a_{ii}|>\sum_{j\ne i}|a_{ij}|,\quad i=1,\dots,n
$$
\end{frame}
\begin{frame}{}
\begin{block}{Norma matrike}
$$ \|\mathbf{S}\|=
\sup\frac{\|\mathbf{S}\mathbf{x}\|}{\|\mathbf{x}\|}$$
\end{block}
\begin{block}{Neskon"cna norma je 
maksimalna absolutna vrsti"cna vsota.}
$$
	\|\mathbf{S}\|_\infty=\max_i\left(\sum_j|s_{ij}|\right)
$$
\end{block}
\end{frame}

\begin{frame}{}

\begin{block}{"Ce je matrika $\mathbf{A}$ diagonalno dominantna, 
potem je iteracijska matrika $\mathbf{S}$
Jacobijeve iteracije konvergentna. 
Njena neskon"cna norma je pod 1, $\|\mathbf{S}\|_\infty<1$.}
Elementi iteracijske matrike so 
$$
	s_{ij}=
	\begin{cases}
		0,& i=j\\
		-\frac{a_{ij}}{a_{ii}},& i\ne j
	\end{cases},\quad i,j=1,\dots,n
$$
Velja, \textit{(zaradi diagonalne dominantnosti matrike} $\mathbf{A}$): 
$$
	\sum_{j}|s_{ij}|<1,\quad i=1,\dots,n
$$
\end{block}
\end{frame}

\subsection{Jacobijeva in Gauss-Seidlova iteracija v akciji}
\begin{frame}{}
\begin{block}{Jacobijeva iteracija}
	$$a_{ii}x_i=-\sum_{j\ne i}a_{ij}x_j+b_i,\quad i=1,\dots,n$$
	$$  x_i^{(k+1)}=-\sum_{j\ne i}\frac{a_{ij}}{a_{ii}}x_j^{(k)}+\frac{b_i}{a_{ii}}$$
	$$  x_i^{(k+1)}=\sum_{j}s_{ij}x_j^{(k)}+c_i$$
\end{block}
\end{frame}
\begin{frame}{}
\begin{block}{Gauss-Seidlova iteracija}
 $$a_{ii}x_i+\sum_{j<i}a_{ij}x_j=-
\sum_{j>i}a_{ij}x_j+b_i,\quad i=1,\dots,n$$
  
$$a_{ii}x_i^{(k+1)}+\sum_{j<i}a_{ij}x_j^{(k+1)}=
-\sum_{j>i}a_{ij}x_j^{(k)}+b_i,\quad i=1,\dots,n$$
$$  x_i^{(k+1)}=-\sum_{j<i}\frac{a_{ij}}{a_{ii}}x_j^{(k+1)}-
\sum_{j>i}\frac{a_{ij}}{a_{ii}}x_j^{(k)}+\frac{b_i}{a_{ii}}$$
\end{block}
\end{frame}

\subsection{Tridiagonalni sistemi}
\begin{frame}
\begin{block}{Razcep po Jacobiju}
	\vskip-5mm
        \begin{eqnarray*} 
		d_1x_1&=&-u_1\,x_2+b_1\\
        	d_ix_i&=&-l_i\,x_{i-1}-u_i\,x_{i+1}+b_i\quad i=2,\dots n-1\\
		d_nx_n&=&-l_n\,x_{n-1}+b_n
	\end{eqnarray*}
\end{block}

\begin{block}{Jacobijeva iteracija}
        \vskip-5mm
        \begin{eqnarray*} 
                x_1^{(k+1)}&=&-{u_1}/{d_1}\,x_2^{(k)}+{b_1}/{d_1}\\
                x_i^{(k+1)}&=&-{l_i}/{d_i}\,x_{i-1}^{(k)}-{u_i}/{d_i}\,x_{i+1}^{(k)}+{b_i}/{d_i}\quad i=2,\dots n-1\\
                x_n^{(k+1)}&=&-{l_n}/{d_n}\,x_{n-1}^{(k)}+{b_n}/{d_n}
        \end{eqnarray*}
\end{block}

\end{frame}

\begin{frame}

\begin{block}{Razcep po Gauss-Seidlu}
       \vskip-5mm
       \begin{eqnarray*} 
                d_1x_1&=&-u_1 x_2+b_1\\
                d_ix_i+l_i x_{i-1}&=&-u_ix_{i+1}+b_i\quad i=2,\dots n-1\\
                d_nx_n+l_nx_{n-1}&=&b_n
        \end{eqnarray*}
\end{block}

\begin{block}{Gaus-Seidlova iteracija}
        \vskip-5mm
        \begin{eqnarray*} 
                x_1^{(k+1)}&=&-{u_1}/{d_1}\,x_2^{(k)}+{b_1}/{d_1}\\
                x_i^{(k+1)}&=&-{l_i}/{d_i}\,x_{i-1}^{(k+1)}-{u_i}/{d_i}\,x_{i+1}^{(k)}+{b_i}/{d_i}\quad i=2,\dots n-1\\
                x_n^{(k+1)}&=&-{l_n}/{d_n}\,x_{n-1}^{(k+1)}+{b_n}/{d_n}
        \end{eqnarray*}
\end{block}

\end{frame}

\end{document}


