% Copyright (C) 2007 Alvise Sommariva. This is a free document; you can redistribute it and/or modify
% it under the terms of the GNU General Public License as published by
% the Free Software Foundation; either version 2 of the License, or
% at your option) any later version. This document is distributed in the hope that it will be useful,
% but WITHOUT ANY WARRANTY; without even the implied warranty of
% MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
% GNU General Public License for more details. You should have received a copy of the GNU General Public License
% along with this program; if not, write to the Free Software
% Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA}

\documentclass[9pt]{beamer}
\input{hal_prefs}
\setlength{\tabcolsep}{2.5pt}
\setbeamertemplate{navigation symbols}{} %no nav symbols
\title[Algebra lineare numerica \hspace{2em}\insertframenumber/
\inserttotalframenumber]{Algebra lineare numerica}
\author{Alvise Sommariva}
\institute{Universit\`a degli Studi di Padova}
\date{\today}
\begin{document}
\frame{\titlepage}



\begin{frame}[fragile]
\frametitle{Cenni di algebra lineare}

\smnsp

\small{
\begin{definizione}[Norma vettoriale (spazio vettoriale sopra $\mathbb{R}$)]
Dato uno spazio vettoriale $V$ (sopra il campo $\mathbb{R}$), la funzione $\|\cdot\|: V \rightarrow \mathbb{R}$ \mye una {\reds{norma vettoriale}} se
\begin{enumerate}
\item $\|x\| \geq 0$ per ogni $x \in V$ e $\|x\| = 0$ se e solo se $x=0_V$,
\item $\|\alpha x\| = |\alpha|_{\mathbb{R}} \| x\|$ per ogni $x \in V$ e scalare $\alpha \in \mathbb{R}$,
\item vale la cosidetta disuguaglianza triangolare $$\|x+y\| \leq \|x\|+\|y\|$$ per ogni $x,y \in V$.
\end{enumerate}
\end{definizione}

\smnsp

\begin{definizione}[Norma vettoriale (spazio vettoriale sopra $\mathbb{C}$)]
Dato uno spazio vettoriale $V$ (sopra il campo $\mathbb{C}$), la funzione $\|\cdot\|: V \rightarrow \mathbb{R}$ \mye una {\reds{norma vettoriale}} se
\begin{enumerate}
\item $\|x\| \geq 0$ per ogni $x \in V$ e $\|x\| = 0$ se e solo se $x=0_V$,
\item $\|\alpha x\| = |\alpha|_{\mathbb{C}} \| x\|$ per ogni $x \in V$ e scalare $\alpha \in \mathbb{C}$,
\item vale la cosidetta disuguaglianza triangolare $$\|x+y\| \leq \|x\|+\|y\|$$ per ogni $x,y \in V$.
\end{enumerate}
\end{definizione}

\smnsp

\begin{nota}[Norma in $\mathbb C$]
Si ricorda che se $z=a+i \cdot b$ allora $|z|_{\mathbb{C}}=\sqrt{a^2+b^2}$.
\end{nota}

}

\end{frame}




\begin{frame}[fragile]
\frametitle{Cenni di algebra lineare}

\smnsp

\begin{esempio}[Alcune norme vettoriali]
Se $V=\C^n$ o $V=\R^n$ e $x=(x_1,x_2,\ldots,x_n) \in V$ alcuni esempi di norme sono
\begin{itemize}
\item per $p \in [1,+\infty)$, la {\reds{norma}} $p$ \mye definita come 
\bc
\btc[width=8cm]
$${ \|x\|_p=\left( \sum_{j=1}^n |x_j|^p \right)^{1/p} }$$ 
\etc
\ec
\item la {\reds{norma del massimo}} \mye definita per $p=\infty$ come \bc
\btc[width=8cm]$${\|x\|_{\infty}=\max_{j=1,\ldots,n} |x_j| }$$ 
\etc
\ec
\end{itemize}
\end{esempio}

\smnsp

\begin{nota}
Di seguito, non distingueremo se lo spazio vettoriale $V$, sia uguale $\C^n$ o $V=\R^n$. Qualora necessario, per semplicit\myash, si ponga $V=\R^n$.
\end{nota}

\end{frame}




\begin{frame}[fragile]
\frametitle{Cenni di algebra lineare}

\smnsp

\begin{nota}[Alcuni casi notevoli della norma $p$]
Si osservi che essendo ${ \|x\|_p=( \sum_{j=1}^n |x_j|^p )^{1/p} }$
\begin{itemize}
\item per $p=1$, si definisce la importante {\reds{norma}} $1$
\bc
\btc[width=6cm]
$${\|x\|_1=\sum_{j=1}^n |x_j|}$$ 
\etc
\ec
\item per $p=2$, si definisce la importante {\reds{norma}} $2$, detta anche  {\reds{euclidea}}
\bc
\btc[width=6cm]
$${\|x\|_2=\left( \sum_{j=1}^n |x_j|^2 \right)^{1/2}}$$ 
\etc
\ec
\end{itemize}
\end{nota}

\end{frame}




\begin{frame}[fragile]
\frametitle{Cenni di algebra lineare}

\smnsp
\small{
\begin{esempio}
Si consideri il vettore $v=(4,-3) \in \R^{2}$.
Allora
\begin{itemize}
\item $\|v\|_1=|4|+|-3|=7$,
\item $\|v\|_2=\sqrt{|4|^2+|-3|^2}=5$,
\item $\|v\|_{\infty}=\max{(|4|,|-3|)}=4$.
\end{itemize}
\end{esempio}

\begin{esempio}
Si considerino i vettori $u=(4,-3), v=(4.001,-2.999) \in \R^{2}$.

I due vettori sono numericamente {\reds{vicini}}. Per verificarlo calcoliamo la loro distanza in termine di norme ovvero
$$
{\mbox{dist}}(u,v):=\|u-v\|_p, \,\,\, p=[1,\infty].
$$

Allora, visto che $u-v=[-0.001 ,  -0.001]$
\begin{itemize}
\item $\|u-v\|_1=0.002$,
\item $\|u-v\|_2=0.0014$,
\item $\|u-v\|_{\infty}=\max{(|-0.001|,|-0.001|)}=0.001$,
\end{itemize}
risultati che sottolineano che $u$ e $v$ sono vicini rispetto alle distanze definite dalle norme.
 \end{esempio}
}
\end{frame}




\begin{frame}[fragile]
\frametitle{Cenni di algebra lineare}

\smnsp

{{
\begin{definizione}
Sia $\| \cdot \|$ una norma vettoriale. Si definisce {\reds{norma vettoriale indotta}} di una matrice in $\C^{n \times n}$ la funzione che mappa ogni matrice $A \in \C^{n \times n}$ nel valore
\bc
\btc[width=6cm]
$$
\|A\|=\sup_{x \neq 0} \frac{\|Ax\|}{\|x\|}
$$
\etc
\ec
\end{definizione}

\smnsp

\begin{nota}
Tali norme si definiscono anche nel caso particolare che $A \in \R^{n \times n}$.
\end{nota}

\smnsp

\begin{definizione}[Raggio spettrale]
Si definisce {\reds{raggio spettrale}} di $A $ la quantit\mya 
\bc
\btc[width=6cm]
$${\rho(A)=\max_{k=1,\ldots,n} (|\lambda_k|)}$$
\etc
\ec
dove $\lambda_k$ \mye un {\reds{autovalore}} di $A$, ovvero esiste $x_k \neq 0$ detto {\reds{autovettore}} di $A$, tale che $Ax_k=\lambda_k x_k$.
\end{definizione}
}}
\end{frame}




\begin{frame}[fragile]
\frametitle{Cenni di algebra lineare}

\smnsp

{\fns{
\begin{esempio}[Alcune norme matriciali]
Posto $A=(a_{i,j})$, alcuni esempi di norme matriciali risultano:
\begin{itemize}
\item per $p=1$, partendo dalla norma vettoriale $\|\cdot\|_1$, si dimostra che la {\reds{norma}} $1$ matriciale risulta uguale al massimo della somma dei moduli delle componenti di ogni {\purples{colonna}} ovvero

\smnsp

\bc
\btc[width=6cm]
\smnsp
$${\|A\|_1=\max_{1 \leq j \leq n} \sum_{i=1}^n |a_{i,j}|};$$
\etc
\ec
\item per $p=2$, partendo dalla norma vettoriale $\|\cdot\|_2$, si dimostra che la {\reds{norma}} $2$ matriciale risulta uguale a 

\smnsp

\bc
\btc[width=6cm]
$${\|A\|_2=\sqrt{\rho(A^* A)}};$$
\etc
\ec  

\smnsp

dove 
\begin{itemize}
\item se $A=(a_{i,j}) \in \R^{n \times n}$ allora $A^*$ \mye la trasposta $A^T$ di $A$, ovvero $a^*_{i,j}=a_{j,i}$,
\item se $A \in \C^{n \times n}$ allora $A^*$ \mye la trasposta coniugata $A^H$ di $A$ ovvero $a^*_{i,j}={\overline{a_{j,i}}}$;
\end{itemize}
\item per $p=\infty$, partendo dalla norma vettoriale $\|\cdot\|_{\infty}$, si dimostra che la {\reds{norma}} $\infty$ matriciale risulta uguale al massimo della somma dei moduli delle componenti di ogni {\purples{riga}} ovvero

\smnsp

\bc
\btc[width=6cm]
\smnsp
$${\|A\|_{\infty}=\max_{1 \leq i \leq n} \sum_{j=1}^n |a_{i,j}|}$$
\smnsp
\etc
\ec
\end{itemize}
\end{esempio}
}}
\end{frame}



\begin{frame}[fragile]
\frametitle{Cenni di algebra lineare}

\smnsp

{{
\begin{esempio}[1]
Si consideri la matrice $A \in \R^{2 \times 2}$

$$
A=\left[
\begin{array}{cc}
$1$ & $-2$ \\
$-3$ & $4$ \\
\end{array}
\right]
$$
Allora 
\begin{itemize}
\item $\|A\|_1=\max(|1|+|-3|,|-2|+|4|)=6$;
\item osservato che $A^*=A^T$ abbiamo

$$
A^T A=\left[
\begin{array}{cc}
$1$ & $-3$ \\
$-2$ & $4$ \\
\end{array} 
\right]
\left[
\begin{array}{cc}
$1$ & $-2$ \\
$-3$ & $4$ \\
\end{array}
\right]
=
\left[
\begin{array}{cc}
$10$ & $-14$ \\
$-14$ & $20$ \\
\end{array}
\right]
$$


i cui autovalori valgono rispettivamente 


$$
\lambda_1 \approx 0.1339312526814949, \,\,\,\, \lambda_2 \approx 29.86606874731851
$$
e di conseguenza 
$$
\|A\|_2=\sqrt{\max(|\lambda_1|,|\lambda_2|)} \approx 5.464985704219044;
$$
\item $\|A\|_{\infty}=\max(|1|+|-2|,|-3|+|4|)=7$.
\end{itemize}
\end{esempio}
}}
\end{frame}




\begin{frame}[fragile]
\frametitle{Cenni di algebra lineare}

{{
\begin{esempio}[2]
Si considerino le matrici 
$$
A=\left[
\begin{array}{cc}
$1.001$ & $-2.999$ \\
$-2.002$ & $4.005$ \\
\end{array} 
\right]
{\hspace{0.5cm}}
B=\left[
\begin{array}{cc}
$1$ & $-3$ \\
$-2$ & $4$ \\
\end{array} 
\right]
$$

Le due matrici sono numericamente {\reds{vicine}}. Per verificarlo calcoliamo la loro distanza in termine di norme ovvero {\reds{$
{\mbox{dist}}(A,B):=\|A-B\|_p, \,\,\, p=[1,\infty].
$}}

Allora, visto che 
$$
A-B=\left[
\begin{array}{cc}
$0.0010$&$0.0010$ \\
$-0.0020$&$0.0050$\\
\end{array} 
\right]
$$
ricaviamo
\begin{itemize}
\item $\|A-B\|_1=\max(0.003,0.006)=0.006$,
\item $\|A-B\|_2=0.005415654779058332$,
\item $\|A-B\|_{\infty}=\max(0.002,0.007)=0.007$,
\end{itemize}
risultati che sottolineano che $A$ e $B$ sono matrici vicine rispetto alle distanze definite dalle norme.
 \end{esempio}
}}
\end{frame}





\begin{frame}[fragile]
\frametitle{Cenni di algebra lineare}

\smnsp

\begin{teorema}[Disuguaglianze norme indotte]
Per le norme matriciali indotte, se $A,B \in \C^{n \times n}$, $x \in \C^{n \times 1}$,

\bc
\btc[width=6cm]
\begin{equation}\label{dis1}
\|Ax\| \leq \|A\|\|x\|,
\end{equation}
\etc
\ec

\smnsp

\bc
\btc[width=6cm]
\begin{equation}\label{dis2}
\|AB\| \leq \|A\|\|B\|.
\end{equation}
\etc
\ec


\end{teorema}


\end{frame}





\begin{frame}[fragile]
\frametitle{Cenni di algebra lineare: Indice di condizionamento}

\smnsp



\begin{definizione}[Indice di condizionamento]
Sia $A \in \C^{n \times n}$ una matrice invertibile ossia tale che $\det(A) \neq 0$. Si dice {\reds{indice di condizionamento}} della matrice $A$, relativamente alla norma indotta $\|\cdot\|$,
\bc
\btc[width=6cm]
$${
k(A):=\|A\|\|A^{-1}\|.
}
$$
\etc
\ec
\end{definizione}

\begin{nota}
Si osservi che dalla definizione, se $I $ \mye la matrice identica di $\C^{n \times n}$
$$
\|I\|=\sup_{x \neq 0} \frac{\|Ix\|}{\|x\|}=\sup_{x \neq 0} \frac{\|x\|}{\|x\|}=1
$$
e quindi, se la norma $\|\cdot\|$ \mye indotta, essendo $\|ST\| \leq \|S\|\|T\| $ per ogni $S,T \in \C^{n \times n}$, ricaviamo
$$
1=\|I\|=\|A A^{-1}\|\leq \|A\| \|A^{-1}\|=k(A)
$$
ovvero {\reds{$k(A) \geq 1$}}.
\end{nota}

\end{frame}




\begin{frame}[fragile]
\frametitle{Cenni di algebra lineare}

\smnsp

Valgono i seguenti risultati

\begin{teorema}[Stime dal basso dell'indice di condizionamento]
\begin{enumerate}
\item Qualsiasi sia la norma matriciale indotta, e $A$ invertibile,
\bc
\btc[width=6cm]
$$
1 \leq \frac{|\lambda_{\mbox{max}}|}{|\lambda_{\mbox{min}}|} \leq k(A)
$$
\etc
\ec
dove $\lambda_{\mbox{min}}$ e $\lambda_{\mbox{max}}$ sono rispettivamente gli autovalori di $A$ di minimo e massimo modulo.

\item Se $A$ \mye {\purples{simmetrica}}, ovvero $A=A^T$, 

\bc
\btc[width=6cm]
$$
k_2(A)=\frac{|\lambda_{\mbox{max}}|}{|\lambda_{\mbox{min}}|}.
$$
\etc
\ec
\end{enumerate}
\end{teorema}

\end{frame}






\begin{frame}[fragile]
\frametitle{Cenni di algebra lineare}

\smnsp

\begin{esempio}[Matrice di Hilbert]
La matrice $H=(h_{i,j})_{i,j=1,\ldots,n}$ con $$h_{i,j}=\frac{1}{i+j-1}$$ \mye nota come matrice di Hilbert di ordine $n$. Per queste matrici gli indici di condizionamento crescono molto rapidamente, come si pu\myo vedere dalla tabella.

 \begin{table}[!ht]
\begin{center}
\begin{tabular}{| c c  | c c | c c |}
\hline
$n$&   $c_n$ & $n$ &   $c_n$ & $n$ &   $c_n$   \\
\hline
 	 $ 1$ & $1.00e+00$ & $ 5$ & $4.77e+05$ & $ 9$ & $4.93e+11$ \\
 	 $ 2$ & $1.93e+01$ & $ 6$ & $1.50e+07$ & $10$ & $1.60e+13$ \\
 	 $ 3$ & $5.24e+02$ & $ 7$ & $4.75e+08$ & $11$ & $5.22e+14$ \\
 	 $ 4$ & $1.55e+04$ & $ 8$ & $1.53e+10$ & $12$ & $1.62e+16$ \\
  \hline
\end{tabular}
\caption{Indice di condizionamento $c_n={\mbox{cond}}_2(H_n)$ della matrici di Hilbert $H_n$ di ordine $n$}
\end{center}
\end{table}


\end{esempio}


\end{frame}




\begin{frame}[fragile]
\frametitle{Cenni di algebra lineare}

\smnsp

Vale la seguente risposta della soluzione di un sistema lineare agli errori del vettore termine noto.

\begin{teorema}[Condizionamento ed errore nel termine noto]
Se 
\begin{enumerate}
\item $A \in \C^{n \times n}$ \mye una matrice invertibile, 
\item $b \in \C^{n}$, $b \neq 0$,
\item $Ax=b$,
\item $A(x+\delta x)={\reds{b+\delta b}}$,
\item $\|\cdot\|$ \mye una norma indotta,
\end{enumerate}
allora vale la stima
\bc
\btc[width=6cm]
$$
{
\frac {\|\delta x\|}  {\|x\|} \leq k(A) \frac {\|\delta b\|}  {\|b\|}
}
$$
\etc
\ec
dove $k(A)=\|A\|\|A^{-1}\|$.
\end{teorema}

\end{frame}








\begin{frame}[fragile]
\frametitle{Cenni di algebra lineare}

\smnsp

\begin{commento}[Relazione tra $\|\delta x\|/\|x\|$ e $\|\delta b\|/\|b\|$]
\begin{itemize}
\item Questo teorema mostra che si fa un errore relativo sul termine noto pari a $\frac{\|\delta b\|}{\|b\|}$ allora si compie un errore relativo tra soluzione $x$ e soluzione $x+\delta x$ del problema perturbato 
$$\frac {\|x-(x+\delta x) \|}{\|x\|}=\frac {\|\delta x\|}{\|x\|}$$
 tale che
$$
\frac {\|\delta x\|}{\|x\|}\leq k(A) \frac{\|\delta b\|}{\|b\|}.
$$

\item Quindi, se $k(A) \gg 1$, pu\myo accadere che la soluzione  $x+\delta x$  del problema perturbato sia molto distante da $x$ e di conseguenza la soluzione del sistema lineare $Ax=b$ molto suscettibile a piccoli errori sul termine noto.

\item In altri termini {\reds{pi\myu grande \mye $k(A)$}} pi\myu i sistemi lineari $Ax=b$ sono {\reds{difficili da trattare}} nel senso che piccoli errori sui dati $b$ possono portare a grossi errori sulla soluzione $x$.
\end{itemize}
\end{commento}

\smsp

\end{frame}



\begin{frame}[fragile]
\frametitle{Cenni di algebra lineare}

\smnsp
{\small{
\begin{esempio}
Siano
$$
A=\left[
\begin{array}{cc}
$7$&$10$ \\
$5$&$7$\\
\end{array} 
\right],
\hspace{0.25cm}
b=\left[
\begin{array}{c}
$1$ \\
$0.7$\\
\end{array} 
\right],
\hspace{0.25cm}
b+\delta b=\left[
\begin{array}{c}
$1.01$ \\
$0.69$\\
\end{array} 
\right].
$$
Il sistema $Ax=b$ ha soluzione
$$
x=\left[
\begin{array}{c}
$0$ \\
$0.1$\\
\end{array} 
\right]
$$
mentre $A(x+\delta x)=b+\delta b$ ha soluzione
$$
x+\delta x=\left[
\begin{array}{c}
$-0.17$ \\
$0.22$\\
\end{array} 
\right].
$$

Di conseguenza seppure $\frac{\|\delta b\|_{\infty}}{\|b\|_{\infty}}=0.01$ abbiamo $\frac{\|\delta x\|_{\infty}}{\|x\|_{\infty}}=1.7$. 

\smsp

Questo significa che a un piccolo errore relativo sui dati abbiamo riscontrato un eccessivo errore relativo sulla soluzione.

\smsp

Osserviamo che in questo caso $k(A)=\|A\|_{\infty}\|A^{-1}\|_{\infty}=289$ e quindi non troppo vicino a $1$.
\end{esempio}
}}
\end{frame}



\begin{frame}[fragile]
\frametitle{Cenni di algebra lineare}

\smnsp


\begin{teorema}[Condizionamento e errore sui dati della matrice]
Se 
\begin{enumerate}
\item $A \in \C^{n \times n}$ \mye una matrice invertibile, 
\item $b \in \C^{n}$, $b \neq 0$,
\item $Ax=b$,
\item ${\reds{(A+\delta A)}}(x+\delta x)=b$, con $\det(A+\delta A) \neq 0$,
\end{enumerate}
allora per una qualsiasi norma indotta $\|\cdot\|$ vale la stima
\bc
\btc[width=7cm]
$$
\frac {\|\delta x\|}  {\|x+\delta x\|} \leq k(A) \frac {\|\delta A\|}  {\|A\|}.
$$
\etc
\ec
dove $k(A)=\|A\| \|A^{-1}\|$.
\end{teorema}

\begin{commento}
Il precedente teorema dice che in presenza di un forte indice di condizionamento, piccoli errori relativi sulla matrice possono indurre grandi errori relativi nella soluzione.  Si noti che usualmente $\|x\| \approx \|x+\delta x\|$.
\end{commento}

\end{frame}













\begin{frame}[fragile]
\frametitle{Cenni di algebra lineare}

\smnsp
{\small{

\begin{esempio}
Siano
$$
A=\left[
\begin{array}{ccc}
$1.0000 $&$   0.5000 $&$   0.3333$ \\
$0.5000 $&$   0.3333  $&$  0.2500$ \\
$0.3333 $&$   0.2500  $&$  0.2000$ 
\end{array} 
\right],
A+\delta A=\left[
\begin{array}{ccc}
$1.0010 $&$   0.5030  $&$  0.3403$ \\
 $   0.5040  $&$  0.3383  $&$  0.2520$ \\
 $   0.3423  $&$  0.2520 $&$   0.2050$ 
\end{array} 
\right],
$$
Il sistema $Ax=b$, per $b=[1, \, 2, \, 3]^T$ ha soluzione approssimativamente
$$
x\approx \left[
\begin{array}{c}
$27.3232$ \\  $-193.6572$ \\ $211.5374$
\end{array} 
\right]
$$
mentre $(A+\delta A)(x+\delta x)=b$ ha soluzione
$$
x+\delta x\approx \left[
\begin{array}{c}
$5.5489 $ \\  $ -75.3599  $ \\  $ 98.0063$ \\ 
\end{array} 
\right].
$$

Di conseguenza seppure $\frac{\|\delta A\|_{2}}{\|A\|_{2}}=9.35310e-03$ abbiamo $\frac{\|\delta x\|_{2}}{\|x+\delta x\|_{2}}=1.33653e+00$. Questo significa che a un piccolo errore relativo sui dati abbiamo riscontrato un eccessivo errore relativo sulla soluzione.

\smsp

Osserviamo che in questo caso $k(A)=\|A\|_{\infty}\|A^{-1}\|_{\infty} \approx 528.5409$ e quindi non troppo vicino a $1$.

\end{esempio}
}}
\end{frame}





















\begin{frame}[fragile]
\frametitle{Metodo di eliminazione di Gauss (esempio)}

\smnsp
{\small{

\begin{proposito}
Il proposito di questa sezione \mye di introdurre il metodo dell'eliminazione gaussiana per risolvere sistemi lineari $Ax=b$ dove supponiamo $A$ invertibile, cio\mye tale che $\det(A) \neq 0$.
\end{proposito}

Per semplificare l'esposizione cominciamo con un esempio.

\begin{esempio}
Si risolva il sistema lineare
$$
\left\{
\begin{array}{l}
3x_1-2x_2-x_3=0 \\
6x_1-2x_2+2x_3=6 \\
-9x_1+7x_2+x_3=-1 \\
\end{array}
\right.
$$
mediante eliminazione gaussiana.
\end{esempio}
Sappiamo che 
\begin{itemize}
\item se moltiplichiamo ambo i membri di una stessa equazione per una costante non nulla, il nuovo problema ha le stesse soluzioni del precedente;
\item se  scambiamo due equazioni,  il nuovo problema ha le stesse soluzioni del precedente;
\item in generale {\reds{se moltiplichiamo la $i$-sima equazione per una costante non nulla e sottraiamo il risultato membro a membro alla $j$-sima}}, ricaviamo una equazione che sostituita alla $j$-sima, propone un nuovo problema lineare che ha le stesse soluzioni del precedente.
\end{itemize}
}}
\end{frame}




\begin{frame}[fragile]
\frametitle{Metodo di eliminazione di Gauss (esempio)}
{\footnotesize{
\begin{svolgimento}
Diremo che due sistemi sono equivalenti, se hanno le stesse soluzioni. Da:
$$
\left\{
\begin{array}{l}
3x_1-2x_2-x_3=0 \\
6x_1-2x_2+2x_3=6 \\
-9x_1+7x_2+x_3=-1 \\
\end{array}
\right.
$$

\begin{itemize}
\item moltiplichiamo la {\purples{prima equazione}} per {\blues{$m_{2,1}=6/3=2$}} e la sottraiamo alla seconda, sostituendo il risultato a quest'ultima, ottenendo il sistema lineare equivalente
 $$
\left\{
\begin{array}{l}
3x_1-2x_2-x_3=0 \\
{\reds{{0}}} \cdot x_1+2x_2+4x_3=6 \\
-9x_1+7x_2+x_3=-1 \\
\end{array}
\right.
$$
\item moltiplichiamo la {\purples{prima equazione}} per {\blues{$m_{3,1}=-9/3=-3$}} e la sottraiamo alla terza, sostituendo il risultato a quest'ultima,  ottenendo il sistema lineare equivalente
 $$
\left\{
\begin{array}{l}
3x_1-2x_2-x_3=0 \\
{\magentas{0}} x_1+2 x_2+4x_3=6 \\
{\reds{{0}}} x_1+1 x_2-2x_3=-1 \\
\end{array}
\right.
$$
in cui le componenti nulle della prima {\it{colonna}}, precedentemente ottenute, non vengono modificate.
\item moltiplichiamo la {\purples{seconda equazione}} per {\blues{$m_{3,2}=1/2$}} e la sottraiamo alla terza, sostituendo il risultato a quest'ultima,  ottenendo il sistema lineare equivalente
 $$
\left\{
\begin{array}{l}
3x_1-2x_2-x_3=0 \\
{\magentas{0}} x_1+2 x_2+4x_3=6 \\
{\magentas{0}} x_1+{\reds{{0}}} x_2-4x_3=-4 \\
\end{array}
\right.
$$
in cui le componenti nulle della {\it{colonna}} precedente non vengono modificate.
\end{itemize}
\end{svolgimento}
}}
\end{frame}




\begin{frame}[fragile]
\frametitle{Metodo di eliminazione di Gauss (esempio)}
{\small{
\begin{vuoto}
Il sistema finale
 $$
\left\{
\begin{array}{l}
3x_1-2x_2-x_3=0 \\
0 x_1+2 x_2+4x_3=6 \\
0 x_1+0 x_2-4x_3=-4 \\
\end{array}
\right.
$$
 \mye facile da risolvere. 

\begin{itemize}
\item L'ultima equazione {\purples{$-4x_3=-4$}} ha una sola variabile e una sola incognita e comporta che $$x_3=1.$$
\item Inseriamo {\purples{$x_3=1$}} nella penultima equazione {\purples{$2 x_2+4x_3=6$}} e otteniamo 
$$ 
2 x_2+4\cdot 1=6
$$
da cui $2x_2=2$ e quindi $x_2=1$.
\item Inseriamo {\purples{$x_2=x_3=1$}}  nella prima equazione {\purples{$3x_1-2x_2-x_3=0 $}} e otteniamo 
$$
3x_1-2 \cdot 1-1=0
$$
da cui $$x_1=1.$$
\end{itemize}
Quindi il sistema ha soluzioni $x_1=1$, $x_2=1$, $x_3=1$.
\end{vuoto}
}}



\end{frame}




\begin{frame}[fragile]
\frametitle{Metodo di eliminazione di Gauss (esempio matriciale)}
{\small{
\begin{nota}[Sistema matriciale]
Il sistema pu\myo essere scritto matricialmente come $Ax=b$ dove
$$
A=\left[
\begin{array}{c c c}
3 & -2 & -1 \\
6 & -2 & 2 \\
-9 & 7 & 1 \\
\end{array}
\right],
\hspace{0.5cm}
b=\left[
\begin{array}{c}
0 \\
6 \\
-1 \\
\end{array}
\right],
$$
e abbiamo mostrato essere equivalente a $Ux=c$ dove
$$
U=\left[
\begin{array}{c c c}
3 & -2 & -1 \\
0 & 2 & 4 \\
0 & 0 & -4 \\
\end{array}
\right],
\hspace{0.5cm}
c=\left[
\begin{array}{c}
0 \\
6 \\
-4\\
\end{array}
\right].
$$
Dal punto di vista matriciale, abbiamo generato una sequenza di sistemi lineari equivalenti, ma via via pi\myu {\reds{semplici}}. 

\smsp

L'ultimo \mye un sistema $Ux=c$ con $U$ triangolare superiore, ovvero tale che $U_{i,j}=0$ qualora $i > j$, che abbiamo risolto facilmente mediante {\reds{sostituzione all'indietro}}.
% % \end{esempio}
\end{nota}
}}
\end{frame}




\begin{frame}[fragile]
\frametitle{Metodo di eliminazione di Gauss (esempio matriciale)}
Operativamente, al posto dello studio di 
$$
\left\{
\begin{array}{l}
3x_1-2x_2-x_3=0 \\
6x_1-2x_2+2x_3=6 \\
-9x_1+7x_2+x_3=-1 \\
\end{array}
\right.
$$
si considera quello di $A^{(1)}x=b^{(1)}$ dove 
$$
A^{(1)}=A=\left[
\begin{array}{c c c}
3 & -2 & -1 \\
6 & -2 & 2 \\
-9 & 7 & 1 \\
\end{array}
\right],
\hspace{0.5cm}
b^{(1)}=b=\left[
\begin{array}{c}
0 \\
6 \\
-1 \\
\end{array}
\right],
$$
I moltiplicatori sono {\purples{$m_{2,1}=a^{(1)}_{2,1}/a^{(1)}_{1,1}=2$}} e {\purples{$m_{3,1}=a^{(1)}_{3,1}/a^{(1)}_{1,1}=-3$}}. Definiamo ora
$$
L^{(1)}=\left[
\begin{array}{c c c}
1 & 0 & 0 \\
-m_{2,1} & 1 & 0 \\
-m_{3,1} & 0 & 1 \\
\end{array}
\right]
=\left[
\begin{array}{c c c}
1 & 0 & 0 \\
-3 & 1 & 0 \\
3 & 0 & 1 \\
\end{array}
\right],
$$
e poniamo {\purples{$A^{(2)}=L^{(1)} \cdot A^{(1)}$}},  {\purples{$b^{(2)}=L^{(1)} \cdot b^{(1)}$}}. Si ricavano quindi
$$
A^{(2)}=\left[
\begin{array}{c c c}
3 & -2 & -1 \\
0 & 2 & 4 \\
0 & 1 & -2 \\
\end{array}
\right],
\hspace{0.5cm}
b^{(2)}=\left[
\begin{array}{c}
0 \\
6 \\
-1 \\
\end{array}
\right],
$$

\end{frame}




\begin{frame}[fragile]
\frametitle{Metodo di eliminazione di Gauss (esempio matriciale)}
Dopo il primo passo si ottiene un sistema equivalente
$$
\left\{
\begin{array}{l}
3x_1-2x_2-x_3=0 \\
{{0}} x_1+2 x_2+4x_3=6 \\
{{{0}}} x_1+1 x_2-2x_3=-1 \\
\end{array}
\right.
$$
ovvero matricialmente si considera il problema equivalente $A^{(2)}x=b^{(2)}$
$$
A^{(2)}=\left[
\begin{array}{c c c}
3 & -2 & -1 \\
0 & 2 & 4 \\
0 & 1 & -2 \\
\end{array}
\right],
\hspace{0.5cm}
b^{(2)}=\left[
\begin{array}{c}
0 \\
6 \\
-1 \\
\end{array}
\right],
$$
in cui i termini della prima colonna di $A^{(1)}$, strettamente sotto la diagonale, sono nulli.

\begin{nota}[Importante]
Notiamo che matricialmente se $A^{(1)}x=b^{(1)}$, essendo $\det{(L^{(1)})}=1 \neq 0$ allora ${L^{(1)}} {A^{(1)}} x = {L^{(1)}} b$ ovvero $A^{(2)}x=b^{(2)}$.

\smsp

 In altri termini il vettore $x=(x_1,x_2,x_3)$ \'e soluzione tanto di  $A^{(1)}x=b^{(1)}$ quanto del pi\'u semplice sistema lineare $A^{(2)}x=b^{(2)}$.
\end{nota}
\end{frame}



\begin{frame}[fragile]
\frametitle{Metodo di eliminazione di Gauss (esempio matriciale)}
Consideriamo ora il sistema $A^{(2)}x=b^{(2)}$ con
$$
A^{(2)}=\left[
\begin{array}{c c c}
3 & -2 & -1 \\
0 & 2 & 4 \\
0 & 1 & -2 \\
\end{array}
\right],
\hspace{0.5cm}
b^{(2)}=\left[
\begin{array}{c}
0 \\
6 \\
-1 \\
\end{array}
\right],
$$
L'unico moltiplicatore utile a porre uguali a 0 le componenti della seconda colonna sotto $a^{(2)}_{2,2}$ ottenuto \'e {\purples{$m_{3,1}=a^{(2)}_{3,2}/a^{(2)}_{2,2}=1/2$}}. Definiamo ora
$$
L^{(2)}=\left[
\begin{array}{c c c}
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & -m_{3,1} & 1 \\
\end{array}
\right]
=\left[
\begin{array}{c c c}
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & -1/2 & 1 \\
\end{array}
\right],
$$
e poniamo {\purples{$A^{(3)}=L^{(2)} \cdot A^{(2)}$}},  {\purples{$b^{(3)}=L^{(2)} \cdot b^{(2)}$}}. Si ricavano quindi
$$
A^{(3)}=\left[
\begin{array}{c c c}
3 & -2 & -1 \\
0 & 2 & 4 \\
0 & 0 & -4 \\
\end{array}
\right],
\hspace{0.5cm}
b^{(3)}=c=\left[
\begin{array}{c}
0 \\
6 \\
-4\\
\end{array}
\right],
$$



{\small{
\begin{nota}[Importante]
Notiamo che matricialmente se $A^{(2)}x=b^{(2)}$, essendo $\det{(L^{(2)})}=1 \neq 0$ allora ${L^{(2)}} {A^{(2)}} x = {L^{(2)}} b$ ovvero $A^{(3)}x=b^{(3)}$.

\smsp

 In altri termini il vettore $x=(x_1,x_2,x_3)$ \'e soluzione tanto di  $A^{(1)}x=b^{(1)}$ quanto del pi\'u semplice sistema lineare $A^{(2)}x=b^{(2)}$, quanto del sistema triangolare $A^{(3)}x=b^{(3)}$.
\end{nota}
}}
\end{frame}






\begin{frame}[fragile]
\frametitle{Metodo di eliminazione di Gauss (esempio matriciale)}
Infine si studia il problema
$$
\left\{
\begin{array}{l}
3x_1-2x_2-x_3=0 \\
0 x_1+2 x_2+4x_3=6 \\
0 x_1+0 x_2-4x_3=-4 \\
\end{array}
\right.
$$
ovvero matricialmente si considera il problema equivalente $A^{(3)}x=b^{(3)}$ dove 
$$
A^{(3)}=U=\left[
\begin{array}{c c c}
3 & -2 & -1 \\
0 & 2 & 4 \\
0 & 0 & -4 \\
\end{array}
\right],
\hspace{0.5cm}
b^{(3)}=c=\left[
\begin{array}{c}
0 \\
6 \\
-4\\
\end{array}
\right],
$$

Notiamo in particolare che visto che $U=A^{(3)}$, $A=A^{(1)}$ e $b=b^{(1)}$
\begin{itemize}
\item $U=A^{(3)}=L^{(2)}\cdot A^{(2)}=L^{(2)}\cdot (L^{(1)}\cdot A^{(1)})=L^{(2)} \cdot L^{(1)} \cdot A$,
\item $b^{(3)}=L^{(2)}\cdot b^{(2)}=L^{(2)}\cdot (L^{(1)}\cdot b^{(1)})=L^{(2)} \cdot L^{(1)} \cdot b$.
\end{itemize}


Di seguito mostreremo 

\begin{enumerate}
\item come risolvere il sistema finale $Ux=c$;
\item come generare passo passo le matrici $A^{(1)}$, $A^{(2)}$, $\ldots$, $A^{(n)}$ e i corrispettivi termini noti $b^{(1)}$, $b^{(2)}$, $\ldots$, $b^{(n)}$.
\end{enumerate}

\end{frame}




\begin{frame}[fragile]
\frametitle{Metodo di eliminazione gaussiana (versione matriciale)}

\smnsp


In questa sezione mostriamo come si pu\'o effettuare matricialmente il processo di eliminazione gaussiana, per la risoluzione di sistemi lineari $Ax=b$ dove in generale si suppone 
\begin{itemize}
\item $A \in \C^{n \times n}$, invertibile e non triangolare, 
\item $b \in \C^{n}$.
\end{itemize}

\smsp

Poniamo
\begin{itemize}
\item $A=A^{(1)}=(a^{(1)}_{i,j})$, 
\item $b=b^{(1)}=(b^{(1)}_j)$, 
\end{itemize}

\smsp
Intendiamo quindi proporre quanto evidenziato in precedenza al caso pi\'u generale di matrici di dimensione maggiore di 3.


\end{frame}



\begin{frame}[fragile]
\frametitle{Metodo di eliminazione gaussiana (versione matriciale, generale)}

{\bf{Primo passo}}. 

\begin{itemize}
\item Supponiamo sia l'{\reds{elemento pivotale}} {\reds{$a^{(1)}_{1,1} \neq 0$}}.
\item  Per $i=2,\ldots,n$, calcoliamo i {\it{moltiplicatori}}
\bc
\btc[width=4cm]

{\vspace{-0.3cm}}

$$
m_{i,1}=\frac{a^{(1)}_{i,1}}{a^{(1)}_{1,1}},
$$

{\vspace{-0.3cm}}

\etc
\ec
\item Definiamo la matrice 
$$
L^{(1)}=\left[
\begin{array}{c c c c c}
1 & 0 & 0 & \ldots & 0\\
-m_{2,1} & 1 & 0  & \ldots & 0\\
-m_{3,1} & 0 & 1  & \ldots & 0\\
\ldots & \ldots & \ldots  & \ldots & \ldots\\
-m_{n,1} & 0 & 0 & \ldots & 1\\
\end{array}
\right]
$$

\noindent e poniamo


\bc
\btc[width=6cm]
{\vspace{-0.4cm}}
$$
A^{(2)}=L^{(1)} \cdot A^{(1)}, {\hspace{0.3cm}}
b^{(2)}=L^{(1)}\cdot b^{(1)}
$$
{\vspace{-0.4cm}}
\etc
\ec
\end{itemize}
\end{frame}



\begin{frame}[fragile]
\frametitle{Metodo di eliminazione gaussiana (versione matriciale, prima colonna)}
\begin{itemize}
\item Dopo questa prima fase, essendo $\det{(L^{(1)})}=1 \neq 0$, come detto in precedenza il sistema $A^{(2)} x = b^{(2)}$ \'e equivalente a $A^{(1)} x = b^{(1)}$ ma pi\'u semplice da risolvere;
\item la matrice a $A^{(2)}=L^{(1)}\cdot A^{(1)}$ risulta del tipo
$$
A^{(2)} =\left[
\begin{array}{c c c c }
a^{(2)}_{1,1} & a^{(2)}_{1,2} & \ldots & a^{(2)}_{1,n}    \\
0 & a^{(2)}_{2,2} & \ldots & a^{(2)}_{2,n}    \\
\ldots & \ldots & \ldots & \ldots    \\
0 & a^{(2)}_{n,2} & \ldots & a^{(2)}_{n,n}   \\
\end{array}
\right].
$$
ovvero le componenti $a^{(2)}_{j,1} $ della prima colonna, strettamente sotto $a^{(2)}_{1,1} $, risultano nulle.
\end{itemize}
\end{frame}



\begin{frame}[fragile]
\frametitle{Metodo di eliminazione gaussiana (versione matriciale, colonne successive)}

{\vspace{-0.1cm}}

{\bf{Passo k-simo}}. 

A questo livello si suppone di aver applicato la strategia pi\'u volte ottendo
\begin{itemize}
\item $A^{(k)}=L^{(k-1)}\cdot A^{(k-1)}=\ldots=L^{(k-1)}\cdot L^{(k-2)} A^{(k-2)}=\ldots=L^{(k-1)}\cdot \ldots \cdot L^{(1)} A^{(1)}$, con
$$
[A^{(k)} ]=\left[
\begin{array}{c c c c c c c }
a^{(k)}_{1,1} & a^{(k)}_{1,2} & \ldots & \ldots & \ldots & \ldots & a^{(k)}_{1,n}   \\
0 & a^{(k)}_{2,2} & \ldots & \ldots & \ldots & \ldots & a^{(k)}_{2,n}    \\
\ldots & \ddots & \ddots & \ldots & \ldots & \ldots & \ldots    \\
0 & \ldots &0 & a^{(k)}_{k,k} & \ldots & \ldots & a^{(k)}_{k,n}   \\
0 & \ldots &0 & a^{(k)}_{k+1,k} & \ldots & \ldots & a^{(k)}_{k+1,n}   \\
0 & \ldots & 0 & \ldots & \ldots & \ldots & \ldots    \\
0 & \ldots &0 & a^{(k)}_{n,k} & \ldots & \ldots & a^{(k)}_{n,n}    \\
\end{array}
\right].
$$
ovvero la matrice $A^{(k)}$ ha componenti nulle sotto la diagonale delle prime $k-1$ colonne.
\item $b^{(k)}=L^{(k-1)}\cdot b^{(k-1)}=\ldots=L^{(k-1)}\cdot L^{(k-2)} b^{(k-2)}=\ldots=L^{(k-1)}\cdot \ldots \cdot L^{(1)} b^{(1)}$.
\end{itemize}


\end{frame}



\begin{frame}[fragile]
\frametitle{Metodo di eliminazione gaussiana (versione matriciale, colonne successive)}

Supponiamo ora che l'{\reds{elemento pivotale}} {\purples{$a^{(k)}_{k,k} \neq 0$}}.

{\magentas{1.}} Definiamo i moltiplicatori

\bc
\btc[width=7cm]
\smnsp
$$
m_{i,k}=\frac {a^{(k)}_{i,k}} {a^{(k)}_{k,k}}, \,\,\, i=k+1,\ldots,n,
$$
\smnsp
\etc
\ec


{\magentas{k.}}  Definiamo la matrice 
$$
L^{(k)}=\left[
\begin{array}{c c c c c c c }
1 & 0 & \ldots & \ldots & \ldots & \ldots & 0  \\
0 & 1 & \ldots & \ldots & \ldots & \ldots & 0    \\
\ldots & \ddots & \ddots & \ldots & \ldots & \ldots & \ldots    \\
0 & \ldots &0 & 1 & 0 & \ldots & 0   \\
0 & \ldots &0 & m_{k+1,k} & 1 & \ldots & 0  \\
0 & \ldots & 0 & \ldots & \ldots & \ldots & \ldots    \\
0 & \ldots &0 & m_{n,k} & 0 & \ldots &1     \\
\end{array}
\right].
$$

\noindent e poniamo


\bc
\btc[width=6cm]
{\vspace{-0.4cm}}
$$
A^{(k+1)}=L^{(k)} \cdot A^{(k)}, {\hspace{0.3cm}}
b^{(k+1)}=L^{(k)}\cdot b^{(k)}
$$
{\vspace{-0.4cm}}
\etc
\ec
\end{frame}



\begin{frame}[fragile]
\frametitle{Metodo di eliminazione gaussiana (versione matriciale, colonne successive)}

Dopo questo ulteriore passo otteniamo un sistema lineare $A^{(k+1)}x= b^{(k+1)}$ avente quale soluzione la stessa di $A^{(1)}x= b^{(1)}$ ma in cui
$$
A^{(k+1)} =\left[
\begin{array}{c c c c c c c}
a^{(k+1)}_{1,1} & a^{(k+1)}_{1,2} & \ldots & \ldots & \ldots & \ldots & a^{(k+1)}_{1,n}  \\
0 & a^{(k+1)}_{2,2} & \ldots & \ldots & \ldots & \ldots & a^{(k+1)}_{2,n}    \\
\ldots & \ddots & \ddots & \ldots & \ldots & \ldots & \ldots    \\
0 & \ldots &0 & a^{(k+1)}_{k,k} & \ldots & \ldots & a^{(k+1)}_{k,n}   \\
0 & \ldots &0 & 0 & a^{(k+1)}_{k+1,k+1} & \ldots & a^{(k)}_{k+1,n}    \\
0 & \ldots & 0 & 0 &  \ldots  & \ldots  &  \ldots  \\
0 & \ldots &0 & 0 &a^{(k+1)}_{n,k+1}  & \ldots & a^{(k)}_{n,n}   \\
\end{array}
\right].
$$

\smsp

Con questo procedimento, dopo $n-1$ passi otteniamo un sistema $A^{(n)}x=b^{(n)}$ in cui la matrice $A^{(n)}$ \mye triangolare superiore con elementi diagonali $A^{(n)}_{k,k} \neq 0$, $k=1,\ldots,n$, problema che pu\myo essere facilmente risolto con l'algoritmo di sostituzione all'indietro.

\end{frame}


\begin{frame}[fragile]
\frametitle{Metodo di eliminazione gaussiana (pseudocodice)}

{\small{
\begin{pseudocodice}
Le seguenti righe di codice implementano la prima parte dell'algoritmo di eliminazione gaussiana senza pivoting, cui deve seguire la risoluzione di un sistema triangolare superiore mediante sostituzione all'indietro.

\begin{verbatim}
for k=1:n-1
  for i=k+1:n
       if a(k,k) == 0
         fprintf('Non posso completare il processo'); return;
       end
       m(i,k)=a(i,k)/a(k,k);
       for j=k+1:n
         a(i,j)=a(i,j)-m(i,k)*a(k,j);
       end
       b(i)=b(i)-m(i,k)*b(k);
  end 
end
\end{verbatim}

Notiamo che al termine del processo la matrice $A$ coincide con $L$ e che il codice produce errore se durante il processo qualche {\purples{\tt{a(k,k)}}} \'e nullo.
\end{pseudocodice}

\begin{nota}[Complessit\'a]
L'eliminazione gaussiana senza pivoting, relativamente ad $A \in {\R}^{n \times n}$, necessita al pi\'u $O(n^3/3)$ operazioni moltiplicative.
\end{nota}
}}
\end{frame}








\begin{frame}[fragile]
\frametitle{Metodo di eliminazione di Gauss (risoluzione sistemi lineari triangolari)}

\smnsp
\small{
\begin{definizione}
Una matrice $A=(a_{i,j}) \in \C^{n \times n}$ si dice 
\begin{itemize}
\item {\reds{triangolare inferiore}} se $a_{i,j}=0$ qualora $i < j$;
\item {\reds{triangolare superiore}} se $a_{i,j}=0$ qualora $i > j$.
\end{itemize}
\end{definizione}

\begin{esempio}
La matrice
$$
L=\left[
\begin{array}{c c c}
3 & 0 & 0\\
4 & 2 & 0 \\
1 & 0 & -4 \\
\end{array}
\right]
$$
\mye triangolare inferiore ($a_{i,j}=0$ se l'indice di riga strettamente minore di quello di colonna).
\end{esempio}


\begin{esempio}
La matrice
$$
U=\left[
\begin{array}{c c c}
3 & -2 & -1 \\
0 & 2 & 4 \\
0 & 0 & -4 \\
\end{array}
\right]
$$
\mye triangolare superiore ($a_{i,j}=0$ se l'indice di riga strettamente maggiore di quello di colonna).
\end{esempio}
}
\end{frame}

\begin{frame}[fragile]
\frametitle{Metodo di eliminazione di Gauss (risoluzione sistemi lineari triangolari)}
Supponiamo di dover risolvere un sistema lineare in forma triangolare superiore non singolare 
$$
\left\{
\begin{array}{l}
a_{1,1}x_1+a_{1,2}x_2+\ldots+a_{1,n}x_n=b_1 \\
a_{2,2}x_2+\ldots+a_{2,n}x_n=b_2 \\
\ldots+\ldots+\ldots=\ldots \\
a_{1,n}x_n=b_n \\
\end{array}
\right.
$$

Evidentemente dall'ultima equazione
$$x_n^*=\frac{b_n}{a_n}$$
Supposti noti $x^*_{k+1}$, $\ldots$, $x^*_{n}$, inserendoli nella $k$-sima equazione, per $k=1,\ldots,n-1$,
$$
a_{k,k}x_k+a_{k,k+1}x^*_{k+1}+a_{k,k+2}x^*_{k+2}+\ldots+a_{k,n}x^*_{n}=b_k
$$
ricaviamo, essendo $a_{k,k} \neq 0$ in quanto $A$ \'e non singolare,
\bc
\btc[width=9cm]
\smnsp
{{
$$
x_k^{*}=\frac{b_k-(a_{k,k+1} \, x^*_{k+1}+a_{k,k+2} \, x^*_{k+2}+\ldots+a_{k,n}\, x^*_{n})}{a_{k,k}}.
$$
}}
\smnsp
\etc
\ec

\end{frame}

\begin{frame}[fragile]
\frametitle{Metodo di eliminazione di Gauss (risoluzione sistemi lineari triangolari)}

\smnsp

{\small{
\begin{algoritmo}[Sostituzione all'indietro e in avanti]
Sia $b=(b_j) \in \C^{n}$ e supponiamo di dover risolvere il sistema $Ax=b$, con {\purples{$A_{k,k} \neq 0$}} per $k=1,\ldots,n$. 

\smsp

In tal caso, 
\begin{itemize}
\item se $A$ \mye triangolare superiore e invertibile, si usa l'algoritmo della {\reds{sostituzione all'indietro}} ovvero
\begin{equation}\label{bs}
\left\{
\begin{array}{l}
x_n=\frac{b_n}{a_{n,n}}\\
x_k=\frac {b_k-(a_{k,k+1}x_{k+1} + \ldots +a_{k,n}x_{n})}  {a_{k,k}}, \,\,\,k=n-1,\ldots,1.
\end{array}
\right.
\end{equation}
\item se $A$ \mye triangolare inferiore e invertibile, si usa l'algoritmo della {\reds{sostituzione in avanti}} ovvero
\begin{equation}\label{fs}
\left\{
\begin{array}{l}
x_1=b_1/a_{1,1}, \\
x_k=\frac {b_k-(a_{k,1}x_{1} + \ldots +a_{k,k-1}x_{k-1})}  {a_{k,k}}, \,\,\,k=2,\ldots,n.
\end{array}
\right.
\end{equation}
\end{itemize}
\end{algoritmo}

\begin{nota}[Complessit\'a risoluzione sistemi triangolari con eliminazione gaussiana]
Si osservi che la {\reds{risoluzione di sistemi lineari triangolari}} necessita approssimativamente {\reds{$n^2/2$ operazioni moltiplicative}}, dove $n$ \mye l'ordine della matrice.

\smsp

Infatti il numero di operazioni moltiplicative, nel caso della sostituzione all'indietro risulta
$$
1+2+\ldots+n = n(n+1)/2 \approx {\reds{n^2/2}}.
$$

\end{nota}
}}
\end{frame}



\begin{frame}[fragile]
\frametitle{Fattorizzazione $A=LU$}

\smnsp
{\fns{
\begin{definizione}[Fattorizzazione LU]
Una matrice $A \in \C^{n \times n}$ \mye fattorizzabile $LU$ se esistono
\begin{itemize}
\item $L=(l_{i,j}) \in \C^{n \times n}$ triangolare inferiore con elementi diagonali $l_{i,i}=1$, 
\item $U=(u_{i,j}) \in \C^{n \times n}$ triangolare superiore, 
\end{itemize}
tali che $A=LU$ (cf. \cite{WIKILU}).
\end{definizione}

\begin{importante}[Pivot non nulli]
Dall'applicazione della procedura precedente per la risoluzione di un sistema lineare, qualora tutti i pivot $a^{(k)}_{k,k}$ siano non nulli, otteniamo un sistema $A^{(n)}x=b^{(n)}$ equivalente all'originario e durante il calcolo introduciamo i moltiplicatori $m_{i,k}$, $k=1,\ldots,n-1$, $i=k+1,\ldots,n$. 
Siano 
\begin{itemize}
\item $U=A^{(n)}$,
\item $L$ la matrice
$$
L=\left[
\begin{array}{c c c c c c}
1 & 0 & 0 & \ldots & 0 & 0 \\
m_{2,1} & 1 & 0 & \ldots & 0 & 0\\
\vdots & \vdots & \vdots & \ldots & \vdots & 0\\
m_{n,1} &m_{n,2} & \ldots & \ldots & m_{n,n-1} & 1 \\
\end{array}
\right].
$$
\end{itemize}
Allora $A=LU$ (cf. {\cite[p.511]{ATK}, \cite[p.143, p.158]{BINI}}).

\smsp

Questo risultato \mye rilevante, perch\mye tale fattorizzazione viene molto utilizzata, come vedremo in seguito con qualche esempio, indipendentemente dalla risoluzione di sistemi lineari.  
\end{importante}
}}
\end{frame}



\begin{frame}[fragile]
\frametitle{Fattorizzazione $A=LU$ (esempio)}

\smnsp
{\fns{
\begin{esempio}
Sia, come nell'esempio iniziale,
$$
A=\left[
\begin{array}{c c c}
3 & -2 & -1 \\
6 & -2 & 2 \\
-9 & 7 & 1 \\
\end{array}
\right],
\hspace{0.5cm}
$$
Alla fine dell'eliminazione gaussiana senza pivoting abbiamo determinato $U=A^{(n)}$  uguale a
$$
U=\left[
\begin{array}{c c c}
3 & -2 & -1 \\
0 & 2 & 4 \\
0 & 0 & -4 \\
\end{array}
\right].
$$
Tenendo conto dei moltiplicatori $m_{2,1}=2$, $m_{3,1}=-3$, $m_{2,2}=0.5$,
$$
L
=
\left[
\begin{array}{c c c}
1 & 0 & 0 \\
m_{2,1} & 1 & 0 \\
m_{3,1} & m_{3,2} & 1 \\
\end{array}
\right]
=
\left[
\begin{array}{c c c}
1 & 0 & 0 \\
2 & 1 & 0 \\
-3 & 0.5 & 1 \\
\end{array}
\right],
$$
e si verifica facilmente che $A=LU$, con $L,U$ triangolari e della forma richiesta. In Matlab:

\smnsp

\begin{verbatim}
>> A=[3 -2 -1; 6 -2 2; -9 7 1]; 
>> U=[3 -2 -1; 0 2 4; 0 0 -4]; L=[1 0 0; 2 1 0; -3 0.5 1];
>> L*U  % verifichiamo che A=L*U
ans =
     3    -2    -1
     6    -2     2
    -9     7     1
>> norm(A-L*U) % la norma di una matrice C nulla se e solo se C e' nulla
ans =
     0
>>
\end{verbatim}
\end{esempio}
}}
\end{frame}





\begin{frame}[fragile]
\frametitle{Matrici che sono sempre fattorizzabili $A=LU$}

\smnsp

{\small{

\begin{definizione}[{\white{\href{https://it.wikipedia.org/wiki/Matrice_a_diagonale_dominante}{Predominanza diagonale}}}]
La matrice $A \in \C^{n \times n}$, $A=(a_{i,j})$, \mye a {\blues{\href{https://it.wikipedia.org/wiki/Matrice\_a\_diagonale\_dominante}{predominanza diagonale per righe}}} se per ogni 
$i=1,\ldots,n$  

\smnsp

$${ { |a_{i,i}|  \geq \sum_{j=1,j \neq i}^n |a_{i,j}| }}$$
e per almeno un indice $s$ si abbia

\smnsp

$$|a_{s,s}| >\sum_{j=1,j \neq s}^n |a_{s,j}|.$$

La matrice $A \in \C^{n \times n}$ \mye a  {\blues{\href{https://it.wikipedia.org/wiki/Matrice\_a\_diagonale\_dominante}{predominanza diagonale stretta per righe}}}  se per ogni 
$i=1,\ldots,n$ risulta 

\smnsp

$${ { |a_{i,i}|  > \sum_{j=1,j \neq i}^n |a_{i,j}| }}.$$

La matrice $A \in \C^{n \times n}$ \mye a {\blues{\href{https://it.wikipedia.org/wiki/Matrice\_a\_diagonale\_dominante}{predominanza diagonale (stretta) per colonne}}}  se $A^T$  \mye a predominanza diagonale (stretta) per righe.
\end{definizione}

\smnsp

\begin{esempio}
Ad esempio la matrice 
$$A=\left( 
\begin{array}{c c c }
4   & -2      &  0         \\
-2  &  4      & -1          \\
0   & -0.5      &  5         
\end{array}
\right)$$
\mye a predominanza diagonale per righe e a predominanza diagonale stretta per colonne.
\end{esempio}

}}
\end{frame}



\begin{frame}[fragile]
\frametitle{Alcune note sulla eliminazione gaussiana e la fattorizzazione LU (predominanza diagonale)}

\smnsp
\begin{nota}[Matrici che hanno fattorizzazione $A=LU$]
Esistono classi di matrici come quelle 
\begin{enumerate}
\item a predominanza diagonale stretta per righe (cf. {\cite{WIKIDD}}), o
\item a predominanza diagonale stretta per colonne (cf. {\cite{WIKIDD}}), o
\item simmetriche e definite positive,
\end{enumerate}
per cui \mye sempre possibile la fattorizzazione $A=LU$.
\end{nota}


\begin{nota}[Fattorizzazione $PA=LU$ anche per matrici non invertibili]
Di seguito vedremo che una qualsiasi matrice invertibile possiede una fattorizzazione del tipo $PA=LU$, con $P$ matrice di permutazione. 

\bigskip

In realt\mya una matrice arbitraria possiede una fattorizzazione di questo tipo (cf. {\cite[p.145]{BINI}}).
\end{nota}

\end{frame}


\begin{frame}[fragile]
\frametitle{Alcune note sulla eliminazione gaussiana e la fattorizzazione LU (predominanza diagonale/simm.def.pos)}

\smnsp

\begin{esempio}
La matrice
$$
\left(
\begin{array}{c c c}
4 & -1 & 0 \\
-1 & 4 & -1 \\
0 & -1 & 4 \\
\end{array}
\right).
$$

\noindent \mye 
\begin{itemize}
\item a predominanza diagonale stretta sia per righe che per colonne.
\item  simmetrica in quanto $A=A^T$ e definita positiva avendo per autovalori 
$$
\lambda_1 \approx  5.4142,
\lambda_2 \approx 4.0000,
\lambda_3 \approx  2.5858
$$
A tal proposito ricordiamo che una matrice \'e {\blues{\href{https://it.wikipedia.org/wiki/Matrice\_definita\_positiva}{definita positiva}}} se e solo se ha tutti gli autovalori positivi.
\end{itemize}
\end{esempio}

\end{frame}










\begin{frame}[fragile]
\frametitle{Eliminazione gaussiana (tempi di calcolo)}

\smnsp

{\small{
\begin{table}[!ht]
\begin{center}
\begin{tabular}{| c c  | c c |}
\hline
$n$&   cputime  \\
\hline
 	 $    1$ & $2.28081e-04$ \\
 	 $    2$ & $1.14614e-03$\\
 	 $    4$ & $1.14304e-04$\\
 	 $    8$ & $4.85808e-05$\\
 	 $   16$ & $4.79512e-04$\\
 	 $   32$ & $1.15395e-04$\\
 	 $   64$ & $2.23282e-03$\\
 	 $  128$ & $2.85307e-03$\\
 	 $  256$ & $2.95903e-03$\\
 	 $  512$ & $1.71150e-02$\\
 	 $ 1024$ & $4.20015e-02$\\
 	 $ 2048$ & $2.45661e-01$\\
 	 $ 4096$ & $1.55579e+00$\\
 	 $ 8192$ & $9.08754e+00$\\
 	 $16384$ & $6.18414e+01$\\
  \hline
\end{tabular}
\caption{Secondi necessari per risolvere un sistema $Ax=b$, con una generica $A \in \R^{n \times n}$, mediante eliminazione gaussiana su un Mac Book Pro, con processore 2,7 GHz Intel Core i5 e 16 GB di memoria. Si ricordi che necessitano, al pi\'u', $O(n^3/3)$ operazioni moltiplicative.}
\end{center}
\end{table}
}}
\end{frame}





\begin{frame}[fragile]
\frametitle{Metodo di eliminazione gaussiana con pivoting parziale (esempio)}

\smnsp

\begin{commento}
Nella precedente sezione, uno dei punti cruciali \mye risultato che i pivot $a^{(k)}_{k,k}$  fossero non nulli. Questo ci ha permesso di calcolare i moltiplicatori 
\bc
\btc[width=8cm]
\smnsp
$$
m_{i,k}=\frac {a^{(k)}_{i,k}} {a^{(k)}_{k,k}}, \,\,\, k=1,\ldots,n-1, \,\,\, i=k+1,\ldots,n
$$
\etc
\ec
e di seguito ridurre il problema iniziale alla risoluzione di un sistema $A^{(n)}x=b^{(n)}$, con $A^{(n)}$ triangolare superiore.

\smsp

Possono sorgere i seguenti problemi: 
\begin{itemize}
\item qualche {\reds{${a^{(k)}_{k,k}}$ risulta nullo}} e quindi il processo precedente \mye  inapplicabile;
\item qualche {\reds{${a^{(k)}_{k,k}}$ risulta molto piccolo in modulo}}, questione che rende il metodo soggetto a una cattiva propagazione degli errori (cf. {\cite[p.516]{ATK}, \cite[p.174]{BINI}}).
\end{itemize}

La soluzione risulta la seguente, detta del {\reds{pivoting (parziale)}} o del {\reds{massimo pivot}}. 
\end{commento}
\end{frame}








\begin{frame}[fragile]
\frametitle{Metodo di eliminazione gaussiana con pivoting parziale (esempio)}

Mostriamo come utilizzare in un esempio l'eliminazione gaussiana con pivoting parziale (per colonne).

\smsp

Di seguito {\reds{colonna}} sar\mya sinonimo di variabile, mentre {\reds{riga}} sar\mya sinonimo di equazione.

\begin{esempio}
Si risolva  il sistema lineare
$$
\left\{
\begin{array}{l}
3x_1-2x_2-x_3=0 \\
6x_1-2x_2+2x_3=6 \\
-9x_1+7x_2+x_3=-1 \\
\end{array}
\right.
$$
mediante il metodo di eliminazione gaussiana con pivoting (parziale).
\end{esempio}
Il {\purples{termine maggiore in modulo della prima colonna}} \mye il terzo e vale $|-9|=9$. Scriviamo $\phi(1)=3$, intendendo che nella prima colonna, la componente di massimo modulo \'e la terza. Scambiamo la prima equazione, con la terza e ricaviamo il sistema equivalente

$$
\left\{
\begin{array}{l}
-9x_1+7x_2+x_3=-1 \\
6x_1-2x_2+2x_3=6 \\
3x_1-2x_2-x_3=0 \\
\end{array}
\right.
$$

\end{frame}



\begin{frame}[fragile]
\frametitle{Metodo di eliminazione gaussiana con pivoting parziale (esempio)}

Applichiamo ora i primi passi dell'eliminazione gaussiana relativamente a

$$
\left\{
\begin{array}{l}
-9x_1+7x_2+x_3=-1 \\
6x_1-2x_2+2x_3=6 \\
3x_1-2x_2-x_3=0 \\
\end{array}
\right.
$$


\begin{itemize}
\item Moltiplichiamo la  {\purples{prima riga}}, ovvero equazione, per {\blues{$m_{2,1}=(-6/9)=-2/3$}} e la sottraiamo alla seconda, ottenendo
 $$
\left\{
\begin{array}{l}
-9x_1+7x_2+x_3=-1 \\
0 x_1+(8/3)x_2+(8/3)x_3=16/3 \\
3x_1-2x_2-x_3=0  \\
\end{array}
\right.
$$
\item Moltiplichiamo la  {\purples{prima riga}}, ovvero equazione, per {\blues{$m_{3,1}=(-1/3)=-1/3$}} e la sottraiamo alla terza, ottenendo
 $$
\left\{
\begin{array}{l}
-9x_1+7x_2+x_3=-1 \\
0 x_1+(8/3)x_2+(8/3)x_3=16/3 \\
0 x_1+(1/3) x_2-(2/3)x_3=-1 /3\\
\end{array}
\right.
$$
\end{itemize}
\end{frame}


\begin{frame}[fragile]
\frametitle{Metodo di eliminazione gaussiana con pivoting parziale (esempio)}

\smnsp
Partiamo da
 $$
\left\{
\begin{array}{l}
-9x_1+7x_2+x_3=-1 \\
0 x_1+(8/3)x_2+(8/3)x_3=16/3 \\
0 x_1+(1/3) x_2-(2/3)x_3=-1 /3\\
\end{array}
\right.
$$

\begin{itemize}
\item Osserviamo che il {\purples{termine maggiore in modulo della seconda colonna}}, di indice di riga maggiore o uguale di quello di colonna,  \'e quello della seconda riga visto che $\max({8/3,1/3})=8/3$. 

\smsp

Con le notazioni introdotte, $\phi(2)=2$ e quindi non si richiedono scambi di equazioni (si dovrebbe scambiare la seconda equazione con la seconda equazione). 

\smsp

Moltiplichiamo la  {\purples{seconda riga}} per {\blues{$m_{3,2}=(1/3)/(8/3)=1/8$}} e la sottraiamo alla terza, ottenendo
 $$
\left\{
\begin{array}{l}
-9x_1+7x_2+x_3=-1 \\
0 x_1+(8/3)x_2+(8/3)x_3=16/3 \\
0 x_1+0 x_2- x_3=-1 \\
\end{array}
\right.
$$
\end{itemize}
\end{frame}


\begin{frame}[fragile]
\frametitle{Metodo di eliminazione gaussiana con pivoting parziale (esempio)}
Il sistema finale, \mye facile da risolvere mediante sostituzione all'indietro. 
\begin{itemize}
\item L'ultima equazione ha una sola variabile e una sola incognita e comporta che $x_3=1.$
\item Inseriamo questo risultato nella penultima equazione e otteniamo 
$$ 
(8/3)x_2+(8/3) \cdot 1=16/3
$$
da cui $x_2=1$.
\item Inseriamo questi risultati nella prima equazione e otteniamo 
$$
-9x_1+7 \cdot 1+1=-1
$$
da cui $x_1=1.$
\end{itemize}


\end{frame}



\begin{frame}[fragile]
\frametitle{Matrici di permutazione}
Il processo di eliminazione gaussiana con pivoting, \mye lo stesso dell'eliminazione gaussiana, per\'o in aggiunta dobbiamo scambiare ad ogni passo certe equazioni.

\smsp

Matricialmente questo corrisponde a scambiare (matematicamente si dice {\reds{permutare}}) certe righe della matrice, e per fare questo risulta fondamentale definire le matrice di permutazione.

\smsp

\begin{definizione}[Matrice di permutazione]
Una matrice $P=(p_{i,j})$ si dice di {\reds{\it{permutazione}}} se 
\begin{enumerate}
\item le sue componenti sono $0$ o $1$, 
\item ogni riga e colonna contengono una sola componente uguale a $1$.
\end{enumerate}
\end{definizione}

Supponiamo sia  $P \in \R^{n \times n}$ una matrice di permutazione.
\begin{itemize}
\item Sia $x \in \R^n$ un vettore colonna e $y=Px$. Allora
$$ P_{i,j} =1 \Rightarrow {\purples{y_i=x_j}}.$$
\item  Sia $A \in \R^n$ una matrice e $C=PA$. Allora
$$ P_{i,j} = 1 \Rightarrow {\purples{C_{i,:}=A_{j,:}}}$$
ovvero la i-sima riga di $C$ \'e la j-sima riga di $A$.
\end{itemize}
\end{frame}



\begin{frame}[fragile]
\frametitle{Matrici di permutazione (esempio)}
\begin{esempio}
Consideriamo la matrice di permutazione
$$
P=\left[
\begin{array}{c c c}
0 & 1 & 0 \\
1 & 0 & 0 \\
0 & 0 & 1 \\
\end{array}
\right]
$$
e il vettore $x=(x_1,x_2,x_3)^T$. Allora 
$$
\left[
\begin{array}{c c c}
0 & 1 & 0 \\
1 & 0 & 0 \\
0 & 0 & 1 \\
\end{array}
\right].
\left(
\begin{array}{c}
{\blues{x_1}}\\
{\purples{x_2 }}\\
x_3 \\
\end{array}
\right)
=
\left(
\begin{array}{c}
0\cdot x_1+1 \cdot x_2+0\cdot x_3\\
1\cdot x_1+0 \cdot x_2+0\cdot x_3\\
0\cdot x_1+0 \cdot x_2+1\cdot x_3\\
\end{array}
\right)
=
\left(
\begin{array}{c}
{\purples{x_2}}\\
{\blues{x_1}} \\
x_3 \\
\end{array}
\right).
$$
Pi\'u in generale, per $A=(a_{i,j})$, 
$$
PA=\left[
\begin{array}{c c c}
0 & 1 & 0 \\
1 & 0 & 0 \\
0 & 0 & 1 \\
\end{array}
\right].
\left(
\begin{array}{c c c}
{\blues{a_{1,1}}} & {\blues{a_{1,2}}} & {\blues{a_{1,3}}}\\
{\reds{a_{2,1}}} & {\reds{a_{2,2}}} & {\reds{a_{2,3}}}\\
{\cyans{a_{3,1}}} & {\cyans{a_{3,2}}} & {\cyans{a_{3,3}}}\\
\end{array}
\right)
=
\left(
\begin{array}{c c c}
{\reds{a_{2,1}}} & {\reds{a_{2,2}}} & {\reds{a_{2,3}}}\\
{\blues{a_{1,1}}} & {\blues{a_{1,2}}} & {\blues{a_{1,3}}}\\
{\cyans{a_{3,1}}} & {\cyans{a_{3,2}}} & {\cyans{a_{3,3}}}\\
\end{array}
\right).
$$
\end{esempio}



\end{frame}

\begin{frame}[fragile]
\frametitle{Matrici di permutazione (esempio)}

\begin{esempio}
La matrice $P_{i,j}$ che \'e come la matrice identica eccetto per le righe $i,j$ che sono tutte nulle eccetto per le componenti $P_{i,j}=P_{j,i}=1$, \'e tale che $C=PA$ coincide con la matrice $A$ eccetto per il fatto che le righe $i$, $j$ sono scambiate.

\smsp

Cos\'i

\begin{eqnarray}
P_{2,3}A&=&\left[
\begin{array}{c c c c}
1 & 0 & 0 & 0 \\
0 & 0 & {\purples{1}} & 0 \\
0 & {\purples{1}}  & 0 & 0 \\
0 & 0 & 0 & 1 \\
\end{array}
\right].
\left(
\begin{array}{c c c c}
{\blues{a_{1,1}}} & {\blues{a_{1,2}}} & {\blues{a_{1,3}}} & {\blues{a_{1,4}}}\\
{\reds{a_{2,1}}} & {\reds{a_{2,2}}} & {\reds{a_{2,3}}}\ & {\reds{a_{2,4}}}\\
{\cyans{a_{3,1}}} & {\cyans{a_{3,2}}} & {\cyans{a_{3,3}}} & {\cyans{a_{3,4}}}\\
{\dkgreens{a_{4,1}}} & {\dkgreens{a_{4,2}}} & {\dkgreens{a_{4,3}}} & {\dkgreens{a_{4,4}}}\\
\end{array}
\right) \nonumber \\
&=&
\left(
\begin{array}{c c c c}
{\blues{a_{1,1}}} & {\blues{a_{1,2}}} & {\blues{a_{1,3}}} & {\blues{a_{1,4}}}\\
{\cyans{a_{3,1}}} & {\cyans{a_{3,2}}} & {\cyans{a_{3,3}}} & {\cyans{a_{3,4}}}\\
{\reds{a_{2,1}}} & {\reds{a_{2,2}}} & {\reds{a_{2,3}}}\ & {\reds{a_{2,4}}}\\
{\dkgreens{a_{4,1}}} & {\dkgreens{a_{4,2}}} & {\dkgreens{a_{4,3}}} & {\dkgreens{a_{4,4}}}\\
\end{array}
\right) \nonumber
\end{eqnarray}

ha le stesse righe di $A$, ma con la seconda permutata con la terza.

\end{esempio}

\end{frame}


\begin{frame}[fragile]
\frametitle{Metodo di eliminazione gaussiana con pivoting parziale (esempio)}

\smnsp
Illustriamo l'importanza delle matrici di permutazione, nel processo di elimazione gaussiana con pivoting parziale (per colonne).

\smsp

Abbiamo visto che il precedente sistema lineare  
$$
\left\{
\begin{array}{l}
3x_1-2x_2-x_3=0 \\
6x_1-2x_2+2x_3=6 \\
-9x_1+7x_2+x_3=-1 \\
\end{array}
\right.
$$

 \mye equivalente al sistema lineare $A^{(1)}x=b^{(1)}$ con 
 $$
A^{(1)}=\left[
\begin{array}{c c c}
3 & -2 & -1 \\
6 & -2 & 2 \\
-9 & 7 & 1 \\
\end{array}
\right]
 \smhsp
b^{(1)}=\left[
\begin{array}{c}
0 \\
6 \\
-1 \\
\end{array}
\right]
$$
\end{frame}


\begin{frame}[fragile]
\frametitle{Metodo di eliminazione gaussiana con pivoting parziale (esempio)}
\begin{itemize}
\item Osserviamo che l'elemento di massimo modulo della prima colonna \'e $a^{(1)}_{3,1}$. 
\item Scambiamo quindi la prima riga con la terza.
\item La matrice di permutazione usata risulta quindi
$$
P^{(1)}=\left[
\begin{array}{c c c}
0 & 0 & 1 \\
0 & 1 & 0 \\
1 & 0 & 0 \\
\end{array}
\right]
$$
\item Consideriamo il sistema equivalente $P^{(1)}A^{(1)}x=P^{(1)}b^{(1)}$ in cui 
$$
P^{(1)}A^{(1)}=
\left[
\begin{array}{c c c}
0 & 0 & 1 \\
0 & 1 & 0 \\
1 & 0 & 0 \\
\end{array}
\right]
\left[
\begin{array}{c c c}
3 & -2 & -1 \\
6 & -2 & 2 \\
-9 & 7 & 1 \\
\end{array}
\right]
=
\left[
\begin{array}{c c c}
-9 & 7 & 1 \\
6 & -2 & 2 \\
3 & -2 & -1 \\
\end{array}
\right]
$$

$$
P^{(1)}b^{(1)}=
\left[
\begin{array}{c c c}
0 & 0 & 1 \\
0 & 1 & 0 \\
1 & 0 & 0 \\
\end{array}
\right]
\left[
\begin{array}{c}
0 \\
6 \\
-1 \\
\end{array}
\right]
=
\left[
\begin{array}{c}
-1 \\
6 \\
0 \\
\end{array}
\right]
$$
\item Osserviamo che i moltiplicatori in $P^{(1)}A^{(1)}$, relativamente alla prima colonna sono $m_{2,1}=6/(-9)=-2/3$ e $m_{3,1}=3/(-9)=-1/3$.
\end{itemize}
\end{frame}



\begin{frame}[fragile]
\frametitle{Metodo di eliminazione gaussiana con pivoting parziale (esempio)}
\begin{itemize}
\item Introduciamo la matrice $L^{(1)}$ basata sui moltiplicatori $m_{2,1}=6/(-9)=-2/3$ e $m_{3,1}=3/(-9)=-1/3$ ovvero
$$
L^{(1)}=
\left[
\begin{array}{c c c}
1 & 0 & 0 \\
-m_{2,1} & 1 & 0 \\
-m_{3,1} & 0 & 1 \\
\end{array}
\right]
=
\left[
\begin{array}{c c c}
1 & 0 & 0 \\
2/3 & 1 & 0 \\
1/3 & 0 & 1 \\
\end{array}
\right]
$$
\item Introduciamo il sistema $A^{(2)}x=b^{(2)}$ equivalente a $A^{(1)}x=b^{(1)}$ dove
\begin{eqnarray}
A^{(2)}&=&L^{(1)}P^{(1)}A^{(1)}=
\left[
\begin{array}{c c c}
1 & 0 & 0 \\
2/3 & 1 & 0 \\
1/3 & 0 & 1 \\
\end{array}
\right]
\left[
\begin{array}{c c c}
-9 & 7 & 1 \\
6 & -2 & 2 \\
3 & -2 & -1 \\
\end{array}
\right]
\nonumber \\
&=&
\left[
\begin{array}{c c c}
-9 & 7 & 1 \\
0 & 8/3 & 8/3 \\
0 & 1/3 & -2/3 \\
\end{array}
\right]
\nonumber
\end{eqnarray}
$$
b^{(2)}=L^{(1)}P^{(1)}b^{(1)}=
\left[
\begin{array}{c c c}
1 & 0 & 0 \\
2/3 & 1 & 0 \\
1/3 & 0 & 1 \\
\end{array}
\right]
\left[
\begin{array}{c}
-1 \\
6 \\
0 \\
\end{array}
\right]
=
\left[
\begin{array}{c}
-1 \\
16/3 \\
-1/3 \\
\end{array}
\right]
$$



\end{itemize}

\end{frame}



\begin{frame}[fragile]
\frametitle{Metodo di eliminazione gaussiana con pivoting parziale (esempio)}

\smnsp
Il sistema lineare precedente, dopo il primo passo di l'eliminazione gaussiana (con pivoting), \'e risultato equivalente a 
$$
\left\{
\begin{array}{l}
-9x_1+7x_2+x_3=-1 \\
0 x_1+(8/3)x_2+(8/3)x_3=16/3 \\
0 x_1+(1/3) x_2-(2/3)x_3=-1 /3\\
\end{array}
\right.
$$

Alternativamente, per i calcoli effettuati in versione matriciale, \'e equivalente al sistema lineare $A^{(2)}x=b^{(2)}$ definito come 
$$
A^{(2)}x:=\left[
\begin{array}{c c c}
-9 & 7 & 1 \\
0 & 8/3 & 8/3 \\
0 & 1/3 & -2/3 \\
\end{array}
\right]
 \smhsp
\left[
\begin{array}{c}
x_1 \\
x_2 \\
x_3 \\
\end{array}
\right]=\left[
\begin{array}{c}
-1 \\
16/3 \\
-1/3 \\
\end{array}
\right]
:=b^{(2)}
$$

Tanto la formulazione matriciale che quella per equazioni hanno portato quindi allo stesso sistema lineare.
\end{frame}




\begin{frame}[fragile]
\frametitle{Metodo di eliminazione gaussiana con pivoting parziale (esempio)}
\begin{itemize}
\item Osserviamo che l'elemento di massimo modulo della seconda colonna, sulla diagonale o al di sotto della stessa \'e $a^{(2)}_{2,2}$.  
\item In virt\'u di quanto visto, non serve fare scambi.
\item La matrice di permutazione usata risulta quindi
$$
P^{(2)}=\left[
\begin{array}{c c c}
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & 0 & 1 \\
\end{array}
\right]
$$
\item Consideriamo il sistema equivalente $P^{(2)}A^{(2)}x=P^{(2)}b^{(1)}$ in cui 
$$
P^{(2)}A^{(2)}=
\left[
\begin{array}{c c c}
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & 0 & 1 \\
\end{array}
\right]
\left[
\begin{array}{c c c}
-9 & 7 & 1 \\
0 & 8/3 & 8/3 \\
0 & 1/3 & -2/3 \\
\end{array}
\right]
=
\left[
\begin{array}{c c c}
-9 & 7 & 1 \\
0 & 8/3 & 8/3 \\
0 & 1/3 & -2/3 \\
\end{array}
\right]
$$

$$
P^{(2)}b^{(2)}=
\left[
\begin{array}{c c c}
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & 0 & 1 \\
\end{array}
\right]
\left[
\begin{array}{c}
-1 \\
16/3 \\
-1/3 \\
\end{array}
\right]
=
\left[
\begin{array}{c}
-1 \\
16/3 \\
-1/3 \\
\end{array}
\right]
$$
\item Osserviamo che il moltiplicatore in $P^{(2)}A^{(2)}$, relativamente alla seconda colonna \'e $m_{3,2}=(1/3)/(8/3)=1/8$.
\end{itemize}
\end{frame}






\begin{frame}[fragile]
\frametitle{Metodo di eliminazione gaussiana con pivoting parziale (esempio)}
\begin{itemize}
\item Introduciamo la matrice $L^{(2)}$ basata sul moltiplicatore $m_{3,2}=1/8$ ovvero
$$
L^{(2)}=
\left[
\begin{array}{c c c}
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & -m_{3,2} & 1 \\
\end{array}
\right]
=
\left[
\begin{array}{c c c}
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & -1/8 & 1 \\
\end{array}
\right]
$$
\item Definiamo il sistema $A^{(3)}x=b^{(3)}$ equivalente a $A^{(2)}x=b^{(2)}$ e quindi a $A^{(1)}x=b^{(1)}$ dove
\begin{eqnarray}
A^{(3)}&=&L^{(2)}P^{(2)}A^{(2)}=
\left[
\begin{array}{c c c}
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & -1/8 & 1 \\
\end{array}
\right]
\left[
\begin{array}{c c c}
-9 & 7 & 1 \\
0 & 8/3 & 8/3 \\
0 & 1/3 & -2/3 \\
\end{array}
\right]
\nonumber \\
&=&
\left[
\begin{array}{c c c}
-9 & 7 & 1 \\
0 & 8/3 & 8/3 \\
0 & 0 & -1 \\
\end{array}
\right]
\nonumber
\end{eqnarray}
$$
b^{(3)}=L^{(2)}P^{(2)}b^{(2)}=
\left[
\begin{array}{c c c}
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & -1/8 & 1 \\
\end{array}
\right]
\left[
\begin{array}{c}
-1 \\
16/3 \\
-1/3 \\
\end{array}
\right]
=
\left[
\begin{array}{c}
-1 \\
16/3 \\
-1 \\
\end{array}
\right]
$$



\end{itemize}

\end{frame}
















\begin{frame}[fragile]
\frametitle{Metodo di eliminazione gaussiana con pivoting parziale (esempio)}

\begin{itemize}
\item Utilizzando la metodologia per singole equazioni abbiamo ottenuto al termine del processo di eliminazione gaussiana lo studio del sistema triangolare 
\begin{equation}\label{001}
\left\{
\begin{array}{l}
-9x_1+7x_2+x_3=-1 \\
0 x_1+(8/3)x_2+(8/3)x_3=16/3 \\
0 x_1+0 x_2- x_3=-1 \\
\end{array}
\right.
\end{equation}
\noindent equivalente a quello iniziale.

\item Matricialmente, abbiamo ricavato similmente

$$
A^{(3)}x:=\left[
\begin{array}{c c c}
-9 & 7 & 1 \\
0 & 8/3 & 8/3 \\
0 & 0 & -1 \\
\end{array}
\right]
 \smhsp
\left[
\begin{array}{c}
x_1 \\
x_2 \\
x_3 \\
\end{array}
\right]=\left[
\begin{array}{c}
-1 \\
16/3 \\
-1 \\
\end{array}
\right]
:=b^{(3)}
$$

\noindent che ovviamente \'e equivalente al sistema ({\ref{001}}). 

\item Il sistema finale pu\'o essere risolto con la sostituzione all'indietro.
\end{itemize}
\end{frame}





\begin{frame}[fragile]
\frametitle{Metodo di eliminazione gaussiana con pivoting parziale (esempio)}

\smnsp
\begin{nota}
Il sistema lineare precedente pu\myo essere riscritto direttamente in forma matriciale, utilizzando le operazioni di moltiplicazione per matrici di permutazione nonch\'e l'utilizzo passo passo dell'eliminazione gaussiana dal punto di vista matriciale.
\end{nota}

Passiamo alla fattorizzazione LU della matrice 
 $$
A=\left[
\begin{array}{c c c}
3 & -2 & -1 \\
6 & -2 & 2 \\
-9 & 7 & 1 \\
\end{array}
\right]
$$
utilizzata nell'esempio precedente per risolvere $Ax=b$, con $b=(0,6,-1)^T$.
Per quanto visto, analizzando il sistema finale del processo, $U=A^{(3)}$ e dunque
$$
U=\left[
\begin{array}{c c c}
-9 & 7 & 1 \\
0 & 8/3 & 8/3 \\
0 & 0 & -1 \\
\end{array}
\right].
$$
\end{frame}



\begin{frame}[fragile]
\frametitle{Metodo di eliminazione gaussiana con pivoting parziale (esempio)}

\smnsp

\begin{enumerate}
\item Ricordando i moltiplicatori $m_{2,1}=-2/3$, $m_{3,1}=-1/3$, $m_{3,2}=1/8$, abbiamo
$$
L=\left[
\begin{array}{c c c}
1 & 0 & 0 \\
-2/3 & 1 & 0 \\
-1/3 & 1/8 & 1 \\
\end{array}
\right]
$$
\item visto che le matrici di permuazione sono risultate
$$
P^{(1)}=\left[
\begin{array}{c c c}
0 & 0 & 1 \\
0 & 1 & 0 \\
1 & 0 & 0 \\
\end{array}
\right],
$$
mentre nel passo relativo alla seconda colonna, visto che non abbiamo effettuato scambi $$P^{(2)}=\left[
\begin{array}{c c c}
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & 0 & 1 \\
\end{array}
\right]$$
 (ovvero la matrice identica),
\end{enumerate}

si pu\'o mostrare, con qualche ragionamento non banale, che per {\reds{$P=P^{(2)} \cdot P^{(1)}=I \cdot P_1=P_1$}} si ha $$PA=LU.$$

\end{frame}


\begin{frame}[fragile]
\frametitle{Metodo di eliminazione gaussiana con pivoting parziale (esempio fattorizzazione $PA=LU$.)}

\smnsp

Avendo calcolato la fattorizzazione $PA=LU$, verifichiamo i risultati in Matlab.

\begin{lstlisting}[basicstyle=\small]
>> P=[0 0 1; 0 1 0; 1 0 0];
>> A=[3 -2 -1; 6 -2 2; -9 7 1];
>> PA=P*A;
>> L=[1 0 0; -2/3 1 0; -1/3 1/8 1];
>> U=[-9 7 1; 0 8/3 8/3; 0 0 -1];
>> LU=L*U;
>> norm(PA-LU,2)
ans =
   4.9651e-16
>> 
\end{lstlisting}

\smnsp

\noindent Si afferma che $\|P*A-L*U\|_2 \approx 4.9651e-16$ ovvero che anche numericamente $P*A=L*U$ (la distanza euclidea matriciale tra $PA$ e $LU$ \'e molto piccola). 

\end{frame}






\begin{frame}[fragile]
\frametitle{Metodo di eliminazione gaussiana con pivoting parziale (fattorizzazione $PA=LU$)}

\smnsp
{\footnotesize{
\begin{importante}[Fattorizzazione PA=LU]
Dall'applicazione della procedura dell'eliminazione gaussiana con pivoting per la risoluzione di un sistema lineare, abbiamo ottenuto un sistema $A^{(n)}x=b^{(n)}$ equivalente all'originario.
Poniamo 
\begin{itemize}
\item $P$ matrice di {\purples{permutazione}} ottenuta come $P=P^{(n-1)}\cdot \ldots \cdot P^{(1)}$ dove $P^{(k)}$ \mye la matrice di permutazione che la scambia la riga $i_k$ con la $k$-sima, ovvero la matrice identica eccetto per le righe {\reds{$i_k$}}, {\reds{$k$}} in cui 
\bc
\btc[width=8cm]
$$
P_{i_k,i_k}=0, P_{i_k,k}=1, P_{k,i_k}=1, P_{k,k}=0;
$$
\etc
\ec

\smnsp

\item $U=A^{(n)}$ di forma {\purples{triangolare superiore}},
\item $L=(l_{i,j})$ la matrice
$$
L=\left[
\begin{array}{c c c c c c}
1 & 0 & 0 & \ldots & 0 & 0  \\
m_{2,1} & 1 & 0 & \ldots & 0 & 0 \\
\vdots & \vdots & \vdots & \ldots & \vdots & \vdots \\
m_{n,1} &m_{n,2} & \ldots & \ldots &m_{n,n-1} & 1 \ \\
\end{array}
\right].
$$
 di forma {\purples{triangolare inferiore}}, con componenti diagonali {\reds{$l_{k,k}=1$}}, $k=1,\ldots,n$.
\end{itemize}
Allora $PA=LU$ (cf. {\cite[p.511]{ATK}, \cite[p.143, p.158]{BINI}}).

\smsp

Questo risultato \mye rilevante, perch\mye tale fattorizzazione viene molto utilizzata indipendentemente dalla risoluzione di sistemi lineari.  
\end{importante}

\smnsp

\begin{nota}[storica]
L'algoritmo di eliminazione gaussiana \mye stato scoperto in Cina circa 2000 anni fa, con pi\myu recenti contributi in lavori di Lagrange e Jacobi. La descrizione moderna  \mye stata introdotta solo nel 1930. {\cite[p.607]{TREF}}.
\end{nota}


}}
\end{frame}








\begin{frame}[fragile]
\frametitle{Eliminazione gaussiana con pivoting parziale e la fattorizzazione LU}

\begin{nota}[Importante]
\small{
{\reds{1.}} Visto che risolvere ognuno dei sistemi triangolari  costa circa $n^2/2$ mentre la parte precedente necessita di circa $n^3/3$ operazioni moltiplicative, deduciamo che risolvere il sistema $Ax=b$ con l'eliminazione gaussiana necessita di circa $n^3/3$ operazioni moltiplicative, visto che
$$O(n^3/3)+2 \cdot O(n^2/2)=O(n^3/3).$$

\smsp
 
{\reds{2.}} La complessit\mya della fattorizzazione $PA=LU$ \mye essenzialmente la stessa della eliminazione gaussiana, ovvero $ \frac{n^3}{3}$.

\smsp

{\reds{3.}} In generale l'algoritmo di eliminazione gaussiana per la risoluzione di un sistema lineare $Ax=b$ con $A$ invertibile, pu\'o essere implementato come segue
\begin{enumerate}
\item {\purples{Calcola la fattorizzazione $PA=LU$}}. Osserviamo che  essendo $P$  invertibile (si dimostra che $|\det(P)|=1$)
$$Ax=b \Leftrightarrow PAx=Pb \Leftrightarrow LUx=Pb \Leftrightarrow {{Ly=\tilde{b} {\mbox{ con }} Ux=y, \tilde{b}=Pb}}.$$
\item {\purples{Calcola $\tilde{b}=Pb$}}.
\item Calcoli la soluzione $y^*$ {\purples{del sistema triangolare inferiore $Ly=\tilde{b}$}} con la sostituzione in avanti.
\item Calcoli la soluzione $x^*$ {\purples{del sistema triangolare superiore $Ux=y^*$}} con la sostituzione all'indietro. Tale $x^*$ \'e quindi soluzione di $Ax=b$.
\end{enumerate}
La complessit\mya dell'algoritmo cos\myi implementato \mye di $ \frac{n^3}{3}$ operazioni moltiplicative, ma offre il vantaggio di avere a disposizione la fattorizzazione $PA=LU$.
}
\end{nota}



\end{frame}




\begin{frame}[fragile]
\frametitle{Alcune note sulla eliminazione gaussiana e la fattorizzazione LU}

\smnsp






\begin{nota}[Decomposizione di Cholesky]
Se la $A$ matrice \mye {\reds{simmetrica e definita positiva}}, ovvero 
\begin{itemize}
\item $A=A^T$, 
\item tutti gli autovalori di $A$ sono positivi,
\end{itemize}
 \mye pi\myu conveniente utilizzare la {\blues{
\href
{https://it.wikipedia.org/wiki/Decomposizione\_di\_Cholesky}
{decomposizione di Cholesky}
}} \cite[p.524]{ATK}, in cui $${\reds{A=L L^T}}$$ con {\reds{$L=(l_{i,j})$ triangolare inferiore con elementi diagonali $l_{k,k} > 0$}}, $k=1,\ldots,n$. 

\smsp

La determinazione di questa fattorizzazione richiede approssimativamente $ \frac{n^3}{6}$ operazioni moltiplicative.

\smsp

Di conseguenza, per calcolare la soluzione di $Ax=b$, basta risolvere i due sistemi triangolari $Ly=b$, $L^Tx=y$. Quindi in generale la soluzione del sistema lineare si pu\myo ottenere in
$$
O \left( \frac{n^3}{6}  \right)+O \left( \frac{n^2}{2} \right)+O \left( \frac{n^2}{2} \right) = {\reds{O \left( \frac{n^3}{6} \right)}}
$$
operazioni moltiplicative.
\end{nota}
\end{frame}



\begin{frame}[fragile]
\frametitle{Alcune note sulla eliminazione gaussiana e la fattorizzazione LU}

\smnsp
{\fns{
\begin{esempio}
La matrice simmetrica
$$ 
A=\left[
\begin{array}{c c c c c}
     1   &  1 &    1  &   1  &   1 \\
     1    & 2  &   2  &   2  &   2\\
     1   &  2    & 3  &   3   &  3\\
     1   &  2   &  3  &   4  &   4\\
     1   &  2   &  3   &  4  &   5\\
\end{array}
\right]
$$
\mye definita positiva, in quanto l'autovalore minimo \mye $\lambda_{\mbox{min}} = 0.271\ldots >0$.

Di conseguenza possiede una decomposizione di Cholesky $A=L L^T$. In questo caso particolare risulta:
$$ 
L=\left[
\begin{array}{c c c c c}
     1   &  0 &    0  &   0  &   0 \\
     1    & 1  &   0  &   0  &   0\\
     1   &  1    & 1  &   0   &  0\\
     1   &  1   &  1  &   1  &   0\\
     1   &  1   &  1   &  1  &   1\\
\end{array}
\right].
$$

In Matlab la routine {\tt{chol}} calcola la trasposta di tale matrice $L$. Vediamo in effetti che i risultati sono corretti.
\begin{verbatim}
>> A=gallery('minij',5);
>> LT=chol(A); L=LT';
>> L
L =
     1     0     0     0     0
     1     1     0     0     0
     1     1     1     0     0
     1     1     1     1     0
     1     1     1     1     1
>> norm(A-L*L',inf)
ans =
     0
\end{verbatim}
\end{esempio}

}}
\end{frame}





\begin{frame}[fragile]
\frametitle{Metodi iterativi}

\smnsp

{{
\begin{motivazione}[Metodi diretti e iterativi] 

\begin{itemize}
\item I metodi come l'eliminazione gaussiana calcolano in aritmetica esatta la soluzione $x^*$ di $Ax=b$, $A \in \C^{n \times n}$ in un numero finito di passi, sono detti metodi {\reds{diretti}}.

\item Osserviamo che
\begin{itemize}
\item [(a)] la matrice {\reds{$n$ \mye di grandi dimensioni}} e quindi ci sono sia problemi di immagazzinamento dati che di complessit\mya computazionale (ovvero $n^3/3$ pu\myo essere proibitivo in termini di costo);
\item [(b)] la matrice $A$ pu\myo possedere {\reds{molti zeri}}, che si verifica spesso non aiutare a migliorare la performance del metodo diretto.
 \end{itemize}

\item Una alternativa consiste nei {\reds{metodi iterativi}} che tipicamente non \mye detto determinino la soluzione esatta, ma possono approssimarla {\reds{arbitrariamente bene}}.
Usualmente {\reds{ogni iterazione}} calcola un prodotto matrice-vettore, e quindi ha complessit\mya di circa {\reds{$n^2$ operazioni moltiplicative}}.
 
\item Se i metodi iterativi forniscono l'approssimazione della soluzione richiesta in un {\reds{$k \ll n/3$}} iterazione, essendo $k n^2 \ll n^3/3$ risultano {\reds{convenienti}} rispetto alla generale fattorizzazione LU.

\end{itemize}
\end{motivazione}
}}
\end{frame}










\begin{frame}[fragile]
\frametitle{Metodi iterativi}

{{

Sia $A \in \C^{n \times n}$ e definiamo lo {\it{splitting}} 
\bc
\btc[width=5cm]
$$A=D-E-F$$
\etc
\ec 
dove
\begin{itemize}
\item $D$ \mye una matrice diagonale, {{non singolare}},
\item $E$ \mye triangolare inferiore con elementi diagonali nulli,
\item $F$ \mye triangolare superiore con elementi diagonali nulli.
\end{itemize}

\begin{esempio}
Sia $A$ la matrice 
$$
\footnotesize{
A = \left[
  \begin{array}{c c c c}
     1   &  2   &  3   &  4 \\ 
     5   &  6  &   7  &   2 \\
     8    & 9  &   1  &   2 \\
     3    & 4  &   5 &    1 \\
         \end{array}
\right],}
$$
allora pu\'o essere descritta in termini di $D$, $E$, $F$ con
$$
\footnotesize{
D = \left[
  \begin{array}{c c c c}
     1   &  0   &  0   &  0 \\ 
     0   &  6  &   0  &   0 \\
     0    & 0  &   1  &   0 \\
     0    & 0  &   0 &    1 \\
         \end{array}
\right],
\,
E = \left[
  \begin{array}{c c c c}
     0   &  0   &  0   &  0 \\ 
     -5   &  0  &   0  &   0 \\
     -8    & -9  &   0  &   0 \\
     -3    & -4  &   -5 &    0 \\
         \end{array}
\right],
\,
F = \left[
  \begin{array}{c c c c}
     0   &  -2   &  -3   &  -4 \\ 
     0   &  0  &   -7  &   -2 \\
     0    & 0  &   0  &   -2 \\
     0    & 0  &   0 &    0 \\
         \end{array}
\right]
}
$$
\end{esempio}
}}
\end{frame}


\begin{frame}[fragile]
\frametitle{Metodi iterativi}

{\small{
Se $A \in \C^{n \times n}$ \mye una matrice quadrata, risulta importante anche lo {\it{splitting}}

\bc
\btc[width=6cm]
\begin{equation}\label{ispl}
A = P - N, {\mbox{      }}\det(P) \neq 0.
\end{equation}
\etc
\ec

Allora 
$$Ax = b \Leftrightarrow (P-N) x=b \Leftrightarrow Px-Nx=b \Leftrightarrow Px=Nx+b$$ 
da cui, per l'invertibilit\mya di $P$, moltiplicando ambo i membri per $P^{-1}$, ricaviamo
\begin{equation}\label{staz}
x=P^{-1}Px=P^{-1}(Nx+b)={\underbrace{P^{-1}N}_{B}}x+{\underbrace{P^{-1}b}_{c}}=Bx+c:=\phi(x).
\end{equation}
Quindi, posti $B:=P^{-1}N$,  $c:=P^{-1}b$, la soluzione $x^*$ di $Ax=b$ risolve pure $x=Bx+c$ (e viceversa).

\smsp

Conseguentemente, vista la struttura di punto fisso $x=\phi(x)$ con $\phi(x)=Bx+c$, si considera il {\purples{metodo iterativo (stazionario)}}  
\bc
\btc[width=6cm]
\begin{equation}\label{isucc}
x^{(k+1)}=\phi(x^{(k)})=Bx^{(k)}+c.
\end{equation}
\etc
\ec
}}
\end{frame}



\begin{frame}[fragile]
\frametitle{Metodi iterativi: alcuni esempi}

\smnsp

{\small{
\begin{vuoto}[Metodi di Jacobi e Gauss-Seidel]
Sia $A=D-E-F$ con
\begin{enumerate}
\item $D$ matrice diagonale,
\item $E$ triangolare inferiore,
\item $F$ triangolare superiore.
\end{enumerate}
Allora
\begin{itemize}
\item il {\reds{metodo di Jacobi}} corrisponde a scegliere, se $D$ \mye invertibile, 
\bc
\btc[width=5cm]
$$P=D, {\mbox{   }} N=E+F$$
\etc
\ec
\item il {\reds{metodo di Gauss-Seidel}} corrisponde a scegliere, se $D$ \mye invertibile,
\bc
\btc[width=5cm]
$$P=D-E, {\mbox{   }} N=F$$
\etc
\ec
\end{itemize}
\end{vuoto}
}}

\smnsp

\begin{nota}
{\fns{
Il metodo di Jacobi fu pubblicato dall'autore nel 1845 in un giornale di astronomia, mentre quello che conosciamo come metodo di Gauss-Seidel fu il risultato di una collaborazione di Seidel con Jacobi nel 1874. Gauss aveva gi\mya descritto un metodo analogo nel 1845 \cite[p.466]{EPS}. 
}}
\end{nota}
\end{frame}






\begin{frame}[fragile]
\frametitle{Metodi iterativi: alcuni esempi}

\smnsp
{\small{
\begin{commento}[Osservazioni sul metodo di Jacobi e Gauss-Seidel]
Se $A=(a_{i,j})_{i,j=1,\ldots,n} \in \C^{n \times n}$, $det(A) \neq 0$  ed $Ax=b$, visto che $(Ax)_i=\sum_{j=1}^n a_{i,j}x_{j}$, allora 
$$\sum_{j=1}^n a_{i,j}x_{j}=b_i, {\mbox{   }} i=1,\ldots,n$$
e quindi, per $i=1,\ldots,n$, evidenziando il termine $i$-simo,
$${\purples{\sum_{j=1}^{i-1} a_{i,j}x_{j}}}+a_{i,i}x_{i}+{\purples{\sum_{j=i+1}^{n} a_{i,j}x_{j}}}=\sum_{i=1}^n a_{i,j}x_{j}=b_i, $$ 
da cui portando a secondo membro $\sum_{j=1}^{i-1} a_{i,j}x_{j}+\sum_{j=i+1}^{n} a_{i,j}x_{j}$
$$a_{i,i}x_{i}=b_i-\sum_{j=1}^{i-1} a_{i,j}x_{j}-\sum_{j=i+1}^{n} a_{i,j}x_{j} ,$$ 
e quindi nel caso $a_{i,i} \neq 0$ per $i=1,\ldots,n$
\bc
\btc[width=10cm]
$${x_{i}=\frac{b_i-\sum_{j=1}^{i-1} a_{i,j}x_{j}-\sum_{j=i+1}^{n} a_{i,j}x_{j}} {a_{i,i}}, {\mbox{   }} i=1,\ldots,n.}$$ 
\etc
\ec
\end{commento}
}}
\end{frame}








\begin{frame}[fragile]
\frametitle{Metodi iterativi: metodo Jacobi}

\begin{vuoto}
Da
{\reds{
$${x_{i}=\frac{b_i-\sum_{j=1}^{i-1} a_{i,j}x_{j}-\sum_{j=i+1}^{n} a_{i,j}x_{j} } {a_{i,i}}, {\mbox{   }} i=1,\ldots,n.}$$ 
}}
il metodo di {\purples{Jacobi}} si ricava ponendo nelle occorrenze del membro di 
\begin{itemize}
\item {\it{sinistra}} {\purples{$x^{(k+1)}_{i}$}} al posto di $x_i$,
\item  {\it{destra}} {\purples{$x^{(k)}_{j}$}} al posto di ogni occorrenza di $x_j$ (con $j=1,\ldots,n$),
\end{itemize}

\noindent ricavando

\bc
\btc
\begin{equation}\label{Jac}
	x_{i}^{(k+1)}=(b_{i} - \sum_{j=1}^{i-1} a_{ij} x_{j}^{(k)}- 
	\sum_{j=i+1}^{n} a_{ij} x_{j}^{(k)} )/a_{ii}, \,\, i=1,\ldots,n,
\end{equation}	
\etc
\ec
\end{vuoto}

\begin{nota}
Il metodo ottenuto e' lo stesso descritto matricialmente come $$x^{(k+1)}=P^{-1}Nx^{(k)}+P^{-1}b$$ con $P=D$ e $N=E+F$.
\end{nota}
\end{frame}





\begin{frame}[fragile]
\frametitle{Metodo di Jacobi}

\smnsp

\begin{esempio}[Metodo di Jacobi]
{\small{
Applicando 

\smnsp

$$x^{(k+1)}_i={ \frac {1} {a_{i,i}} } \left(b_i-\left( \sum_{j<i} a_{i,j} x^{(k)}_j+\sum_{j>i} a_{i,j} x^{(k)}_j\right)\right), \,\,i=1,\ldots,n$$ al caso di $A \in {\mathbb{C}}^{3 \times 3}$, otteniamo, supponendo disponibile $x^{(k)}$:

\begin{enumerate}
\item $x^{(k+1)}_1=\frac {1} {a_{1,1}} (b_1- a_{1,2} x^{(k)}_2- a_{1,3} x^{(k)}_3)$;
\item $x^{(k+1)}_2=\frac {1} {a_{2,2}}  (b_2- a_{2,1} {\reds{x^{(k)}_1}}- a_{2,3} x^{(k)}_3)$;
\item $x^{(k+1)}_3=\frac {1} {a_{3,3}}  (b_3- a_{3,1} {\reds{x^{(k)}_1}}- a_{3,2} {\reds{x^{(k)}_2}})$.
\end{enumerate}

Si nota che 
\begin{itemize}
\item dopo aver calcolato $x^{(k+1)}_1$ tale nuova approssimazione della prima componente $x^*_1$ della soluzione $x^*$ non \'e sfruttata nel determinare $x^{(k+1)}_2$;
\item dopo aver calcolato $x^{(k+1)}_2$ tale nuova approssimazione della prima componente $x^*_2$ della soluzione $x^*$ non \'e sfruttata nel determinare $x^{(k+1)}_3$.
\end{itemize}
Ogni $x^{(k+1)}_j$, $j=1,2,3$ \'e calcolato direttamente dall'iterazione precedente $x^{(k)}=(x^{(k)}_i)_i$, senza richiedere la conoscenza di qualche $x^{(k+1)}_i$ con $i=1,\ldots,j-1$.

}}


\end{esempio}
\end{frame}








\begin{frame}[fragile]
\frametitle{Metodi iterativi: metodo di Gauss-Seidel}

\begin{vuoto}
Da
{\reds{
$${x_{i}=\frac{b_i-\sum_{j=1}^{i-1} a_{i,j}x_{j}-\sum_{j=i+1}^{n} a_{i,j}x_{j} } {a_{i,i}}, {\mbox{   }} i=1,\ldots,n.}$$ 
}}
il metodo di {\purples{Gauss-Seidel}} si ricava ponendo nelle occorrenze del membro di 
\begin{itemize}
\item {\it{sinistra}} {\purples{$x^{(k+1)}_{i}$}} al posto di $x_i$,
\item  {\it{destra}} nella prima sommatoria {\purples{$x^{(k+1)}_{i}$}} al posto di $x_i$ e nella seconda sommatoria {\purples{$x^{(k)}_{i}$}}
\end{itemize}

\noindent ricavando

\bc
\btc
\begin{equation}\label{GS}
	x_{i}^{(k+1)}=(b_{i} - \sum_{j=1}^{i-1} a_{ij} x_{j}^{(k+1)}- 
	\sum_{j=i+1}^{n} a_{ij} x_{j}^{(k)} )/a_{ii}, \,\, i=1,\ldots,n,
\end{equation}	
\etc
\ec
\end{vuoto}

\begin{nota}
{\fns{
Il metodo ottenuto e' lo stesso descritto matricialmente come $$x^{(k+1)}=P^{-1}Nx^{(k)}+P^{-1}b, \smhsp P=D-E, \smhsp N=F.$$ Una sua generalizzazione porta ai metodi SOR (cf. \cite{WIKISOR}).
}}
\end{nota}
\end{frame}











\begin{frame}[fragile]
\frametitle{Metodo di Gauss-Seidel}

\smnsp
\smnsp

\begin{esempio}[Metodo di Gauss-Seidel]
{{
Applicando $$x^{(k+1)}_i={ \frac {1} {a_{i,i}} } \left(b_i-\left( \sum_{j<i} a_{i,j} x^{(k+1)}_j+\sum_{j>i} a_{i,j} x^{(k)}_j\right)\right), \,\,i=1,\ldots,n$$ al caso di $A \in {\mathbb{C}}^{3 \times 3}$, otteniamo:

\begin{enumerate}
\item $x^{(k+1)}_1=\frac {1} {a_{1,1}} (b_1- a_{1,2} x^{(k)}_2- a_{1,3} x^{(k)}_3)$;
\item $x^{(k+1)}_2=\frac {1} {a_{2,2}}  (b_2- a_{2,1} {\reds{x^{(k+1)}_1}}- a_{2,3} x^{(k)}_3)$;
\item $x^{(k+1)}_3=\frac {1} {a_{3,3}}  (b_3- a_{3,1} {\reds{x^{(k+1)}_1}}- a_{3,2} {\reds{x^{(k+1)}_2}})$.
\end{enumerate}

Si nota che 
\begin{itemize}
\item dopo aver calcolato $x^{(k+1)}_1$ tale nuova approssimazione della prima componente $x^*_1$ della soluzione $x^*$ \'e sfruttata nel determinare $x^{(k+1)}_2$;
\item dopo aver calcolato $x^{(k+1)}_2$ tale nuova approssimazione della prima componente $x^*_2$ della soluzione $x^*$ \'e sfruttata nel determinare $x^{(k+1)}_3$.
\end{itemize}

}}

\smnsp

\end{esempio}

\smnsp


\end{frame}










\begin{frame}[fragile]
\frametitle{Metodi iterativi, convergenza}

\smnsp

\begin{teorema}[Convergenza globale dei metodi iterativi]\label{cnorm}
Siano
\begin{itemize}
\item $B \in \C^{n \times n}$,
\item si supponga che la soluzione $x^*$ di $Ax=b$ sia l'unica soluzione di $x = Bx + c$.
\item sia  $\rho(B)=\max_{k=1,\ldots,n}|\lambda_k|$ il raggio spettrale di $B$ (dove $\lambda_1,\ldots,\lambda_n$ sono gli autovalori di $B$).
\end{itemize}
Allora qualsiasi sia $x^{(0)} \in \C^n$, la successione $\{x^{(k)}\}$ definita da
$$
x^{(k+1)} = B x^{(k)} + c, \,\,\, k = 0, 1, 2, \ldots
$$
converge a $x^*$ {\reds{se e solo se}} $\rho(B) < 1$ .
\end{teorema}

\smnsp

\begin{nota}
\begin{enumerate}
\item Si noti che in questo asserto compare {\purples{un se e solo se}}.
\item Si noti compare il {\purples{raggio spettrale di $B$}} (e non di $A$).
\item Si noti che richiede il calcolo dell'autovalore di modulo massimo di $B$, un problema potenzialmente complicato. Di solito, noto la struttura della matrice $A$ ci sono dei teoremi che offrono risultati sul raggio spettrale di $B$.
\end{enumerate}
\end{nota}
\end{frame}







\begin{frame}[fragile]
\frametitle{Metodi iterativi, convergenza caso predominanza diagonale stretta}

A partire dai precedenti teoremi si \mye potuto dimostrare (non facile!)

\begin{teorema}[Convergenza Jacobi per matrici a predominanza diagonale stretta]
Se la matrice $A$ \mye a {\reds{predominanza diagonale (stretta) per righe}}, allora il metodo di {\purples{Jacobi}} converge.
\end{teorema}

\begin{teorema}[Convergenza Gauss-Seidel per matrici a predominanza diagonale stretta]
Se la matrice $A$ \mye a {\reds{predominanza diagonale (stretta) per righe}}, allora il metodo di {\purples{Gauss-Seidel}} converge.
\end{teorema}

\begin{teorema}[Convergenza G.-S. per matrici simmetriche e definite positive]
Se la matrice $A$ \mye {\reds{simmetrica e definita positiva}} allora il metodo di {\purples{Gauss-Seidel}} converge.
\end{teorema}

\begin{nota}[Grandezza raggio spettrale]
In generale, con stime quantitative, si vede che sono da preferire metodi con raggio spettrale $\rho(B)$ il pi\'u piccolo possibile.
\end{nota}

\end{frame}



\begin{frame}[fragile]
\frametitle{Alcuni esempi}

\smnsp
{{
\begin{esempio}[Matrice a predominanza diagonale stretta]
Consideriamo il sistema lineare $Ax=b$ dove
$$
\footnotesize{
A = \left[
  \begin{array}{c c c }
     11   & -5   &  -5 \\ 
     5   &  12  &   6 \\
     6    & -4  &   11 \\
         \end{array}
\right],
\,\,\,
b = \left[
  \begin{array}{c}
     1 \\ 
    23 \\
     13 \\
         \end{array}
\right],
}
$$
che ha soluzione $x^*=[1,1,1]^T$ (cf. {\cite[p.252]{BINI}}).
Si dica se convergono i metodi di Jacobi e Gauss-Seidel.
\end{esempio}


\begin{itemize}
\item La matrice $A$ \mye a predominanza diagonale in senso stretto e quindi tanto il metodo di Jacobi, quanto quello di Gauss-Seidel, risultano convergenti. In effetti $\rho(B_J) \approx 0.79$, $\rho(B_{GS}) \approx 0.83$ e questo si dimostra implicare che asintoticamente il metodo di Jacobi converge pi\'u rapidamente di quello di Gauss-Seidel.
\item Gli errori assoluti $\|x^{(k)}-x^*\|_{\infty}$ compiuti rispettivamente dal metodo di Jacobi e Gauss-Seidel sono esposti nella tabella che segue, da cui si evince la convergenza dei metodi.
\end{itemize}
}}
\end{frame}



\begin{frame}[fragile]
\frametitle{Alcuni esempi}

\smnsp
 \begin{table}[!ht]
\begin{center}
\begin{tabular}{| c c c |}
\hline
$n$&   $E_J$ & $E_{GS}$  \\
\hline
 	 $ 10$ & $1.6e-01$ & $2.2e-01$ \\
 	 $ 30$ & $1.5e-03$ & $6.2e-03$ \\
 	 $ 50$ & $1.4e-05$ & $1.7e-04$ \\
 	 $ 70$ & $1.3e-07$ & $4.8e-06$ \\
 	 $ 90$ & $1.2e-09$ & $1.3e-07$ \\
 	 $110$ & $1.1e-11$ & $3.8e-09$ \\
 	 $130$ & $1.0e-13$ & $1.1e-10$ \\
 	 $150$ & $1.1e-15$ & $2.9e-12$ \\
 	 $170$ & $-$ & $8.2e-14$ \\
 	 $190$ & $-$ & $2.2e-15$ \\
  \hline
\end{tabular}
\caption{Errori assoluti $\|x^{(k)}-x^*\|_{\infty}$ compiuti dalle $k$-sime iterazioni di Jacobi e Gauss-Seidel, nel risolvere un certo problema $Ax=b$ con $A$ a predominanza diagonale stretta, con vettore iniziale $x_0=(0,0,0)^T \in \R^3$.}
\end{center}
\end{table}

\end{frame}






\begin{frame}[fragile]
\frametitle{Alcuni esempi}

\smnsp

\begin{esempio}[Matrice definita positiva]
Si studi la convergenza dei metodi di Jacobi e Gauss-Seidel, relativamente al sistema lineare $Ax=b$ dove
$$
\footnotesize{
A = \left[
  \begin{array}{c c c | c c c | c c c}
 	 $4$ & $-1$ & $0$ & $-1$ & $0$ & $0$ & $0$ & $0$ & $0$ \\ 
 	 $-1$ & $4$ & $-1$ & $0$ & $-1$ & $0$ & $0$ & $0$ & $0$ \\ 
 	 $0$ & $-1$ & $4$ & $0$ & $0$ & $-1$ & $0$ & $0$ & $0$ \\ 
 	 \hline 
 	 $-1$ & $0$ & $0$ & $4$ & $-1$ & $0$ & $-1$ & $0$ & $0$ \\ 
 	 $0$ & $-1$ & $0$ & $-1$ & $4$ & $-1$ & $0$ & $-1$ & $0$ \\ 
 	 $0$ & $0$ & $-1$ & $0$ & $-1$ & $4$ & $0$ & $0$ & $-1$ \\ 
 	 \hline 
 	 $0$ & $0$ & $0$ & $-1$ & $0$ & $0$ & $4$ & $-1$ & $0$ \\ 
 	 $0$ & $0$ & $0$ & $0$ & $-1$ & $0$ & $-1$ & $4$ & $-1$ \\ 
 	 $0$ & $0$ & $0$ & $0$ & $0$ & $-1$ & $0$ & $-1$ & $4$ \\
         \end{array}
\right],
\,\,\,
b = \left[
  \begin{array}{c}
          2 \\
     1\\
     2\\
     1\\
     0\\
     1\\
     2\\
     1\\
     2\\
         \end{array}
\right],
}
$$
che ha soluzione $x^*=[1,\ldots,1]^T \in \R^9$. 
\end{esempio}

La matrice $A$ \mye un esempio di matrice di Poisson ed \mye definita positiva, in quanto il suo autovalore pi\myu piccolo vale $$\lambda_{\mbox{min}} \approx 1.171572875253810e+00 >0.$$

Le linee mostrano come $A \in \R^{9 \times 9}$ segua {\it{pattern}} particolari con {\sl{blocchi}} pari a 
$$
\footnotesize{
B = \left[
  \begin{array}{c c c}
 	 $4$ & $-1$ & $0$  \\ 
 	 $-1$ & $4$ & $-1$  \\ 
 	 $0$ & $-1$ & $4$ 
         \end{array}
\right],
\,\,\,
-I = \left[
  \begin{array}{c c c}
 	 $-1$ & $0$ & $0$  \\ 
 	 $0$ & $-1$ & $0$  \\ 
 	 $0$ & $0$ & $-1$ 
         \end{array}
\right],
\,\,\,
0_{3 \times 3} = \left[
  \begin{array}{c c c}
 	 $0$ & $0$ & $0$  \\ 
 	 $0$ & $0$ & $0$  \\ 
 	 $0$ & $0$ & $0$ 
         \end{array}
\right],
}
$$

\end{frame}



\begin{frame}[fragile]
\frametitle{Alcuni esempi}

\smnsp

\begin{itemize}
\item Gli errori assoluti $\|x^{(k)}-x^*\|_{\infty}$ compiuti rispettivamente dal metodo di Jacobi e Gauss-Seidel partendo da $x_0=[0,\ldots,0]^T \in \R^9$. Entrambi i metodi convergono, e per quanto concerne il metodo di Gauss-Seidel, ci\myo era garantito dal teorema di convergenza, in quanto $A$ \'e simmetrica e definita positiva.  

\item Si vede che $\rho(B_J) \approx 0.7071$, mentre $\rho(B_{GS}) \approx 0.5$ e quindi ci si aspetta che asintoticamente il metodo di Gauss-Seidel converga in meno iterazioni di quello di Jacobi.
\end{itemize}

 \begin{table}[!ht]
\begin{center}
\begin{tabular}{| c c c |}
\hline
$n$&   $E_J$ & $E_{GS}$  \\
\hline
 	 $ 10$ & $4.7e-02$ & $1.8e-03$ \\
 	 $ 30$ & $4.6e-05$ & $1.7e-09$ \\
 	 $ 50$ & $4.5e-08$ & $1.8e-15$ \\
 	 $ 70$ & $4.4e-11$ & $-$ \\
 	 $ 90$ & $4.3e-14$ & $-$ \\
 	   \hline
\end{tabular}
\caption{Errori assoluti $\|x^{(k)}-x^*\|_{\infty}$ compiuti dalle $k$-sime iterazioni di Jacobi e Gauss-Seidel, nel risolvere un certo problema $Ax=b$ con $A$ matrice di Poisson, con vettore iniziale $x_0=(0,0,0,0,0,0,0,0,0)^T \in \R^9$.}
\end{center}
\end{table}
 	 % % \end{esempio}
\end{frame}



\begin{frame}[fragile]
\frametitle{Alcuni esempi}

\smnsp
 	 
 	 
 	 
\begin{esempio}[Mancata convergenza dei metodi di Jacobi e Gauss-Seidel]
Consideriamo il sistema $Ax=b$ con
$$
A=\left[
\begin{array}{c c c}
3 & -2 & -1 \\
6 & -2 & 2 \\
-9 & 7 & 1 \\
\end{array}
\right],
\,\,
b=\left[
\begin{array}{c}
0 \\
6 \\
-1 \\
\end{array}
\right],
$$
avente soluzione $x^*=(1,1,1)^T$. Si verifichi la mancata convergenza globale dei metodi di Jacobi e Gauss-Seidel partendo da $x^{(0)}=(1-\epsilon,1-\epsilon,1-\epsilon)^T$ con $\epsilon=10^{-14}$.
\end{esempio}

\begin{itemize}
\item Utilizziamo i metodi di Jacobi e Gauss-Seidel con dato iniziale $$x^{(0)}=(1-10^{-14},1-10^{-14},1-10^{-14})^T$$
e quindi molto prossimo al vettore soluzione $x^*$ in quanto $\|x^*-x^{(0)}\|_{\infty}=10^{-14}$.

\item Entrambi i metodi citati, pur partendo da un tal $x^{(0)}$, non convergono, come si pu\myo vedere dalla relativa tabella. In effetti, si verifica che $1 < \rho(B_J) \approx 8.66$, $1 < \rho(B_{GS}) \approx 9.62$, e quindi entrambi i metodi iterativi non sono globalmente convergenti.
\end{itemize}
\end{frame}



\begin{frame}[fragile]
\frametitle{Alcuni esempi}

\smnsp
 \begin{table}[!ht]
\begin{center}
\begin{tabular}{| c c c |}
\hline
$n$&   $E_J$ & $E_{GS}$  \\
\hline
 	 $ 10$ & $2.6e-12$ & $1.4e-05$ \\
 	 $ 30$ & $6.7e-09$ & $6.3e+14$ \\
 	 $ 50$ & $1.8e-05$ & $2.9e+34$ \\
 	 $ 70$ & $4.5e-02$ & $1.4e+54$ \\
 	 $ 90$ & $1.2e+02$ & $6.3e+73$ \\
 	 $110$ & $2.9e+05$ & $2.9e+93$ \\
 	 $130$ & $7.3e+08$ & $1.4e+113$ \\
 	 $150$ & $1.8e+12$ & $6.3e+132$ \\
 	 $170$ & $4.4e+15$ & $2.9e+152$ \\
 	   \hline
\end{tabular}
\caption{Errori assoluti $\|x^{(k)}-x^*\|_{\infty}$ compiuti dalle $n$-sime iterazioni di Jacobi e Gauss-Seidel, nel risolvere un certo problema $Ax=b$ con $A$ matrice utilizzata come esempio per l'eliminazione gaussiana, con vettore iniziale $x^{(0)}=(1-10^{-14},1-10^{-14},1-10^{-14})^T  \in \R^3$.}
\end{center}
\end{table}

 	% % \end{esempio}
\end{frame}




\begin{frame}[fragile]
\frametitle{Test di arresto}

\smnsp

{\small{
\begin{vuoto}
Sia $\epsilon >0$ una tolleranza fissata dall'utente.
Il metodo iterativo
$$
x^{(k+1)}=Bx^{(k)}+c
$$
viene arrestato utilizzando 
\begin{itemize}
\item il {\reds{criterio dello step}}, ovvero si interrompe il processo quando
\bc
\btc[width=5cm]
$$
\|x^{(k+1)} - x^{(k)}\| \leq \epsilon,
$$
\etc
\ec
\item {\reds{criterio del residuo}}, ovvero si interrompe il processo quando
\bc
\btc[width=5cm]
$$
\|b-Ax^{(k)}\| \leq \epsilon,
$$
\etc
\ec
\item {\reds{criterio del residuo relativo}}, ovvero si interrompe il processo quando
\bc
\btc[width=5cm]
$$
{ \frac {\|b-Ax^{(k)}\|} {\|b\|} } \leq \epsilon, \smhsp b \neq 0_{{\mathbb{C}}^n}
$$
\etc
\ec
\end{itemize}
\end{vuoto}
}}
\end{frame}



















\begin{frame}[allowframebreaks] {Bibliografia}
\bibliographystyle{plain}
\bibliography{bibliography/bibliography} 
\usebibitemtemplate{\color{structure}\insertbiblabel}
\usebibliographyblocktemplate{\color{structure}}{\color{black}}{\color{structure!75}}{\color{structure!75}}


\begin{thebibliography}{99} 


\bibitem{ATK} K. Atkinson, {\it{Introduction to Numerical Analysis}}, Wiley, 1989.
\bibitem{ATKNEW} K. Atkinson, W. Han, {\it{Elementary Numerical Analysis}}, Wiley, 2003.
\bibitem{BINI} D. Bini, M. Capovani, O. Menchi, {\it{Metodi numerici per l'algebra lineare}}, Zanichelli, 1988.
%\bibitem{COM} V. Comincioli, {\reds{Analisi Numerica, metodi modelli applicazioni}}, Mc Graw-Hill, 1990.
% \bibitem{CON} S.D. Conte e C. de Boor, {\reds{Elementary Numerical Analysis, 3rd Edition}}, Mc Graw-Hill, 1980.
\bibitem{EPS} J.F. Epperson, {\it{Introduzione all'analisi numerica. Teoria, metodi, algoritmi.}}, Mc Graw-Hill, 2009.
\bibitem{GVL} G.H.Golub and C.F. Van Loan, {\em Matrix Computations\/}, 3rd edition, John Hopkins University Press, (1996).
\bibitem{KEL} C.T. Kelley, {\em Iterative Methods for Linear and Nonlinear Equations\/}, SIAM Frontiers in Applied Mathematics. SIAM, Philadelphia, (1995).
%\bibitem{QUASM} A. Quarteroni e F. Saleri, {\it{Elementi di calcolo numerico}}, Progetto Leonardo, 1999.
% \bibitem{QUA} A. Quarteroni e F. Saleri, {\reds{Introduzione al calcolo scientifico}}, Springer Verlag, 2006.
%\bibitem{QUALAR} A. Quarteroni, R. Sacco e F. Saleri, {\it{Matematica Numerica}}, Springer Verlag, 1998.
%\bibitem{SULI} A. Suli e D. Mayers, {\reds{An Introduction to Numerical Analysis}}, Cambridge University Press, 2003.
\bibitem{TREF} L.N. Trefethen, {\it{Numerical Analysis}}, Princeton Companion to Mathematics, 2008.
%\bibitem{WIKINC} Wikipedia, Formule di Newton-Cotes,\\   {\href{https://it.wikipedia.org/wiki/Formule\_di\_Newton-Cotes}{https://it.wikipedia.org/wiki/Formule\_di\_Newton-Cotes}}.

\bibitem{WIKICHOL} {\blues{\href{https://it.wikipedia.org/wiki/Decomposizione\_di\_Cholesky}{Wikipedia, Decomposizione di Cholesky}}}.
\bibitem{WIKILU} {\blues{\href{https://it.wikipedia.org/wiki/Decomposizione\_LU}{Wikipedia, Decomposizione LU}}}.
% \bibitem{WIKIQR} {\blues{\href{https://it.wikipedia.org/wiki/Decomposizione\_QR}{Wikipedia, Decomposizione QR}}}.
\bibitem{WIKIDD}  {\blues{\href{https://it.wikipedia.org/wiki/Matrice\_a\_diagonale\_dominante}{Wikipedia, Matrice a diagonale dominante}}}.
\bibitem{WIKIDP} {\blues{\href{https://it.wikipedia.org/wiki/Matrice\_definita\_positiva}{Wikipedia, Matrice definita positiva}}}.
%\bibitem{WIKICOF} {\blues{\href{Matrice\_invertibile\#Metodo\_della\_matrice\_dei\_cofattori}{Wikipedia, Matrice invertibile: Metodo della matrice dei cofattori}}}.
\bibitem{WIKISOR} {\blues{\href{http://it.wikipedia.org/wiki/Successive\_Over\_Relaxation}{Wikipedia, SuccessiveOverRelaxation}}}.
%\bibitem{WIKISUP}  {\blues{\href{https://it.wikipedia.org/wiki/Supercomputer}{Wikipedia, Supercomputer}}}.
\bibitem{WIKIBIN} {\blues{\href{https://it.wikipedia.org/wiki/Teorema\_di\_Binet}{Wikipedia, Teorema di Binet}}}.
\bibitem{WIKILAP}  {\blues{\href{https://it.wikipedia.org/wiki/Teorema\_di\_Laplace}{Wikipedia, Teorema di Laplace}}}.





\end{thebibliography}
\end{frame}






\end{document}



\begin{frame}[fragile]
\frametitle{Metodo di eliminazione gaussiana con pivoting (parziale)}

\smnsp
\begin{vuoto}
Supponiamo di voler {\it{azzerare}} le componenti sotto la diagonale della colonna k-sima e determiniamo
\bc
\btc[width=6cm]
$$
c_k=\max_{k \leq i \leq n} |a^{(k)}_{i,k}|.
$$
\etc
\ec

Certamente $c_k \neq 0$, altrimenti, dopo qualche conto, si vedrebbe che la matrice originaria $A$ di cui studiamo $Ax=b$ sarebbe non invertibile, diversamente da quanto richiesto (per accorgersene basta applicare la regola di Laplace relativamente alla k-sima colonna).

\smsp
\begin{itemize}
\item Sia {\reds{$i_k:=\phi(k) \geq k$}} il pi\myu piccolo indice di riga, per cui il massimo $c_k$ \mye ottenuto. 
\item Se $i_k > k$, {\reds{scambiamo la riga $i_k$-sima con la $k$-sima della matrice aumentata}}
$[A^{(k)} | b^{(k)}]$ ottenendo una nuova matrice aumentata, diciamo $[{{\hat{A}}}^{(k)} | {{\hat{b}}}^{(k)}]$, su cui possiamo applicare la tecnica introdotta al $k$-simo passo dell'eliminazione gaussiana senza pivoting. 

\smsp

Con questa tecnica, la nuova matrice aumentata avr\mya il pivot pi\myu grande possibile in modulo, con vantaggi per la propagazione degli errori.
\end{itemize}
\end{vuoto}
\end{frame}







