In questo capitolo ci occuperemo di un altro modo per risolvere sistemi lineari: i metodi iterativi. Come abbiamo fatto nel capitolo precedente daremo per ognuno dei metodi analizzati, una descrizione dettagliata ed esaustiva in modo tale da rendere l’implementazione più agevole nel linguaggio di programmazione scelto.

Consideriamo un sistema lineare

$$ Ax= b $$

con $A \in \R^{n \times n}$ non singolare, $b \in \R^n$ è termine noto e $x \in \R^n$ è il vettore delle incognite.

I metodi iterativi partendo da un vettore iniziale $x^{(0)}\in \R^n$ creano una sequenza di vetttori $x^{(k)}\in \R^n$ che si avvicinano sempre di più alla soluzione esatta $\tilde x \in \R^n$.

L’idea alla base è chiara si però aprono i seguenti quesiti:

• Perchè introdurre questo tipo di metodi?
• Come è possibile stabilire se si è arrivati vicini alla soluzione dato che non si conosce la soluzione esatta $\tilde x$?
• E’ sempre possibile arrivare alla soluzione indipendentemente dal punto di partenza?
• Come si può creare una tale successione di vettori?

Fill-in

Nella maggior parte delle applicazioni la matrice $A$ ha dimensione molto elevata dell’ordine di $10^6$. Abbiamo già visto che salvare l’intera matrice con un formato standard “Column-major” o “Row-major” richiederebbe l’utilizzo di molta memoria.

Se considerassimo per esempio una matrice quadrata di dimensione $10^6$ e se per ogni sua entrata ci servissero 8 bit, avremmo bisogno di $8e + 10^{12}$ bit e software come Matlab non permettono nemmeno di creare matrici così grandi.

Dato che nella maggior parte delle applicazioni matrici di così grande dimensione sono sparse, si può ovviare al problema del salvataggio tramite la rappresentazione sparsa delle matrici.

Consideriamo per esempio la matrice $A ∈ \R^{100×100}$, le cui entrate non nulle sono rappresentate in Figura 1.

Figura 1. Rappresentazione tramite il comando spy di Matlab della matrice sparsa $A$ presa in esame. Vengono anche riportate le sue entrate non nulle 1036 (circa il 10% delle ntrate totali della matrice).

Quando viene fatta la decomposizione PALU o quella di Cholesky è possibile che le matrici risultanti perdano la loro natura sparsa. Questo fenomeno è noto come fill-in.

Figura 2. Rappresentazione tramite il comando spy di Matlab delle matrici $L$ e $U$ risultanti dalla decomposizione PALU. Vengono anche riportate le sue entrate non nulle di L 3600, e quelle di $U$ 3606 (circa il 36% delle entrate totali della matrice sia per L che per U).

In Figura 2 riportiamo lo schema della sparsità delle matrici L, U ∈ R100×100, mentre in Figura 3 riportiamo quello associato alla matrice R ∈ R100×100 della decomposizione di Cholesky. Il numero di entrate non nulle aumenta notevolmente, diventa più del triplo, quindi possiamo dire che la matrice $A$ è soggetta al fenomeno di fill-in per entrambe le decomposizioni.