Sistemi lineari su un calcolatore

Casi semplici

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

1. Se $A$$A$ è una matrice diagonale, ci sono equazioni disaccoppiate, e, per i coefficienti della soluzione, vale la formula:
   $$x_{i}={\frac {b_{i}}{a_{i}}}$$

   $$x_{i}={\frac {b_{i}}{a_{i}}}$$
2. Nel caso di una matrice triangolare inferiore $A=L$$A=L$, nell'equazione i-esima esplicito l'incognita $x_{i}$$x_i$:
   $$x_{i}={\frac {b_{i}-\sum _{j=1}^{i-1}a_{j}x_{j}}{a_{ii}}}\forall i=1,\dots ,n$$

   $$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, conosco già tutte le $i-1$$i-1$ incognite precedenti, ricavate nelle equazioni sopra esplicitando le incognite precedenti (risoluzione forward).
3. Nel caso in cui $A=U$$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$$

   $$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}$$a_{i}$ è ben posta perché siccome $\det A\neq 0$$\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$$A$ può essere scritta come prodotto $BC$$BC$, con $B,C$$B,C$ facilmente invertibili, in modo che i sistemi

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

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

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

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

siano facilmente risolubili.

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

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

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

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

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

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

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

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

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

Fattorizzazioni classiche

Esistono tre possibili fattorizzazioni della matrice $A$$A$:

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