Metodi iterativi per sistemi lineari

Prerequisiti

Definizione.

Una matrice $A$ di ordine $n, n \geq 2$, si dice riducibile se $\exists$ una matrice di permutazione $P$ e un intero $k, 0<k<n$ tale che:

$ B=PAP^T = \left( \begin{array}{cc} A_{11} & A_{12} \\ 0 & A_{22} \end{array} \right)$ in cui $A_{11} \in \mathbb{R}^{kxk}$ e $A_{22} \in \mathbb{R}^{(n-k)x(n-k)}$
Se la matrice A non è riducibile allora si dice irriducibile.
N.B.: Se A è riducibile, possono esistere differenti matrici di permutazione $P$ che consentono di trasformare $A$ nella forma $B$.
$A = \left( \begin{array}{ccc} 1 & 3 & 0 \\ 0 & 2 & -1 \\ -1 & 0 & 2 \end{array} \right) n=3 \Rightarrow$ avremo un grafo con 3 nodi $P_1,P_2,P_3$. Se $a_{ij} \neq 0 \Rightarrow \exists$ un arco uscente da $P_i$ entrante in $P_j$. [! Aggiungere immagine grafo] [P1 .> P1; P1 .> P2; P2 .> P2; P2 .> P3; P3 .> P3; P3 .> P1] Per determinare se $A$ di ordine $n$ è riducibile si può usare il grafo orientato associato ad $A$, cioè un grafo che ha $n$ nodi $p_i , i=1,...,n$ e un arco orientato uscente da $P_i$ ed entrante in $P_j$ se $a_{ij} \neq 0, \forall i,k$
Se il nodo di arrivo di un arco è il nodo di partenza di un altro arco $\Rightarrow$ questi sono contigui.

Definizione.

Due archi di un grafo si dicono contigui se il nodo di arrivo del primo arco è anche il nodo di partenza del secondo arco.

Definizione. 

Una successione di archi contigui si dice cammino orientato

Definizione.

Un grafo orientato si dice fortemente connesso se per ogni coppia di indici $(i,j), 1 \leq i,j \leq n, i \neq j$, esiste un cammino orientato che parte da $P_i$ e arriva in $P_j$

Teorema
(CNS)

 Una matrice $A$ è riducibile $\Leftrightarrow$ il suo grafo orientato NON è fortemente connesso.

Segue che C.N.: 

se $A$ è irriducibile $\Rightarrow \exists$ un cammino orientato chiuso che tocca tutti i nodi