Introduzione

Ci sono molti algoritmi per risolvere i sistemi lineari. Essi si dividono in:

1. Metodi diretti
2. Metodi iterativi

La differenza è che i metodi diretti calcolano la soluzione del sistema fattorizzando $A$ (ovvero scrivo $A$ come prodotto di altre matrici) e sono più costosi (computazionalmente) dei metodi iterativi, che calcolano la soluzione costruendo successioni di vettori $x_k$ che convergono a $x^*$ (la soluzione esatta) per $k$ che tende ad infinito.

Con i metodi diretti posso avere solo l'errore algoritmico e quello inerente, mentre nel metodi iterativi posso avere anche un errore di troncamento, dato che realizzo un procedimento che nemmeno in $\R$ mi darebbe una soluzione esatta (me la darebbe solo con infiniti termini, che è impossibile). Il vantaggio è appunto che sono meno onerosi computazionalmente, quindi sono usati per i sistemi grandi.

Metodi diretti

Sistema Triangolare Superiore $Ax=b$

$$ \begin{pmatrix} a_{1,1} & a_{1,2} & ... & a_{1,n}\\ 0 & a_{2,2} & ... & a_{2,n}\\ 0 & 0 & \ddots & \vdots \\ 0 & 0 & 0 & a_{n,n} \\ \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \\ \vdots \\ x_n \end{pmatrix}

\begin{pmatrix} b_1 \\ b_2 \\ \vdots \\ b_n \end{pmatrix} $$

Partendo dall'incognita $x_n$ posso procedere per sostituzione a cascata all'indietro e ottengo:

$$ x_i = \cfrac{b_i - \sum_{j=i+1}^n a_{i,j}\cdot x_j}{a_{i,i}} \quad \text{con} \quad i=n-1, ..., 1 $$

Si noti che l'algoritmo ha complessità computazionale $O(n^2/2)$.

• Serie di passaggi

• Un esempio dell'algoritmo scritto in Matlab.

Sistema Triangolare Inferiore $Ax=b$

$$ \begin{pmatrix} a_{1,1} & 0 & 0 & 0\\ a_{2,1} & a_{2,2} & 0 & 0\\ \vdots & \ddots & 0 & 0 \\ a_{n-1,1} & a_{n-1,2} & \ddots & 0 \\ a_{n,1} & a_{n,2} & \dots & a_{n,n} \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \\ \vdots \\ x_n \end{pmatrix}

\begin{pmatrix} b_1 \\ b_2 \\ \vdots \\ b_n \end{pmatrix} $$

Partendo dall'incognita $x_1$ posso procedere per sostituzione a cascata in avanti e ottengo:

$$ x_i = \cfrac{b_i - \sum_{j=1}^{i-1} a_{i,j}\cdot x_j}{a_{i,i}} \quad \text{con} \quad i=2, ..., n $$

Si noti che l'algoritmo ha complessità computazionale $O(n^2/2)$.

• Serie di passaggi

• Un esempio dell'algoritmo scritto in Matlab.

Fattorizzazione LR

Questo algoritmo ci permette di scrivere una matrice $A$ come prodotto di due matrici, $L$ e $R$ per l'appunto, di cui in particolare $L$ è una matrice triangolare inferiore con gli elementi sulla diagonale tutti di valore 1, mentre $R$ è una matrice triangolare superiore (con la diagonale con valori qualsiasi).

<aside> ❗ Questo algoritmo può essere applicato solo su matrici quadrate $A\in\R^{n\times n}$ non singolari, ovvero con $det(A)\neq0$

</aside>

Di seguito i passaggi dell'algoritmo:

• 1. Costruisco la matrice $L_1$
• 2. Moltiplico la matrice $L_1$ per $A$ e ottengo la matrice $A_2$

Reitero questi passaggi usando come input le matrici $A_k$ che ottengo e spostandomi ogni volta sulla colonna successiva.

Regola generale