Calcolo numerico/Sistemi lineari su un calcolatore

Casi semplici

Vogliamo risolvere un sistema lineare $A𝒙=𝒃$ con $A$ matrice quadrata di dimensione $n$ supposta non singolare, e $𝒙,𝒃\in {ℝ}^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}}\mathrm{\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}},i=n:1$

(risoluzione backward)

Nota: le formule risolutive, e la divisione per $a_i$ è ben posta perché siccome $detA\ne 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𝒙=𝒚$

$B𝒚=𝒃$

siano facilmente risolubili.

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

$BC𝒙=𝒃$

e ponendo $C𝒙=𝒚$ ottengo

$B𝒚=𝒃$

e lo risolvo. Una volta ottenuto $𝒚$, per trovare $𝒙$ risolvo quindi

$C𝒙=𝒚$

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=L{L}^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 ($Q{Q}^h=Q^{h}Q=1$) e $R$ è una triangolare superiore.