Calcolo numerico/Sistemi lineari su un calcolatore

Casi semplici

Vogliamo risolvere un sistema lineare $A{\boldsymbol {x}}={\boldsymbol {b}}$ con $A$ matrice quadrata di dimensione $n$ supposta non singolare, e ${\boldsymbol {x}},{\boldsymbol {b}}\in \mathbb {R} ^{n}$.

1. Se $A$ è una matrice diagonale, ci sono equazioni disaccoppiate, e, per i coefficienti della soluzione, vale la formula:

$x_{i}={\frac {b_{i}}{a_{i}}}$

2. Nel caso di una matrice triangolare inferiore $A=L$, nell'equazione $i$-esima esplicito l'incognita $x_{i}$:

$x_{i}={\frac {b_{i}-\sum _{j=1}^{i-1}a_{j}x_{j}}{a_{ii}}}\forall i=1,\dots ,n$

infatti risolvendo l'$i$-esima equazione, conosciamo già tutte le $i-1$ incognite precedenti, ricavate nelle equazioni sopra esplicitando le incognite precedenti (risoluzione forward).

3. Nel caso in cui $A=U$ triangolare superiore, si applica lo stesso procedimento ma partendo dall'ultima incognita.

$x_{i}={\frac {(b_{i}-\sum _{j=i+1}^{n}a_{j}x_{j})}{a_{ii}}},\quad i=n:1$

(risoluzione backward)

Nota: le formule risolutive, e la divisione per $a_{i}$ è ben posta perché siccome $\det A\neq 0$, i coefficienti sulla diagonale di una matrice triangolare sono diversi da 0.

I metodi per la risoluzione di sistemi lineari si distinguono in

1. metodi diretti (di fattorizzazione)
2. metodi iterativi, usati per matrici di grosse dimensioni.

Metodi di fattorizzazione

Una matrice $A$ può essere scritta come prodotto $BC$, con $B,C$ facilmente invertibili, in modo che i sistemi

$C{\boldsymbol {x}}={\boldsymbol {y}}$

$B{\boldsymbol {y}}={\boldsymbol {b}}$

siano facilmente risolubili.

Siccome $A=BC$, sostituendo nel sistema originario ottengo

$BC{\boldsymbol {x}}={\boldsymbol {b}}$

e ponendo $C{\boldsymbol {x}}={\boldsymbol {y}}$ ottengo

$B{\boldsymbol {y}}={\boldsymbol {b}}$

e lo risolvo. Una volta ottenuto ${\boldsymbol {y}}$, per trovare ${\boldsymbol {x}}$ risolvo quindi

$C{\boldsymbol {x}}={\boldsymbol {y}}$

Fattorizzazioni classiche

Esistono tre possibili fattorizzazioni della matrice $A$:

1. fattorizzazione $PA=LU$, con la richiesta che la diagonale principale di $L$ sia composta da 1, e dove $P$ è una matrice di permutazione.
2. se $A$ è simmetrica definita positiva, si può considerare la fattorizzazione $A=LL^{H}=U^{h}U$, con $L^{h}$ coniugata trasposta di $L$, con la richiesta che gli elementi della diagonale principale siano positivi.
3. $A=QR$, dove $Q$ è una matrice unitaria ($QQ^{h}=Q^{h}Q=1$) e $R$ è una triangolare superiore.