In questo capitolo verranno introdotti alcuni concetti fondamentali per la risoluzione di sistemi lineari in ambito numerico. Dopo una prima sezione di carattere prettamente tecnico su come viene gestita la struttura di matrici dai più comuni software, verranno spiegate alcune problematiche comuni nell’implementazione di algoritmi per la risoluzione di un sistema lineare e l’importante concetto di numero di condizionamento. Il capitolo si concluderà con una panoramica sui modi di risolvere un sistema lineare.
Le matrici e vettori sono salvate in aree contigue di memorie, i.e., in array. Supponiamo di avere un vettore $x \in \R^n$
$$ \texttt x = \begin{bmatrix} x_1\\x_2 \\ x_3\\...\\x_n \end{bmatrix} $$
esso verrà salvato in aree contigue di memoria indipendentemente dal fatto che sia un vettore riga o colonna.
L’area di memoria viene indicizzata con $n$ numeri interi.
Con le matrici la situazione si complica. Esse vengono in un certo senso “srotolate” e messe in aree contigue di memoria. Consideriamo una matrice $A\in \R^{nxn}$
Essa può essere srotolata in $n\times m$ celle di memoria secondo due diversi criteri
per colonne, “Column-major”, tipico di linguaggi di programmazione come Fortran
per righe, “Row-major”, tipico di linguaggi di programmazione come c++
Questi due modi di salvare la matrice in memoria sono completamente equivalenti. Uno non risulta essere più veloce dell’altro, sono semplicemente delle convenzioni che si sono scelte. Per accedere all’area di memoria relativa a un coefficiente della matrice $A$, è necessaria una coppia di indici che identificano la riga e colonna di $A$ come il gioco di battaglia navale. Anche in questo caso, proprio come i vettori, esistono le due convenzioni su quale sia l’indice iniziale.
Come è facile intuire la memoria richiesta per salvare una matrice è più grande rispetto a quella richiesta per un vettore. Supponiamo che il costo per salvare un numero sia 8 bytes. Fissato $n > 0$ la memoria richiesta per salvare tutte le componenti di un vettore $x ∈ \R^n$ e una matrice quadrata $A ∈ \R^{n×n}$ saranno rispettivamente $8 n$ e $8 n^2$ bytes. Per valori di $n$ piccoli la differenza fra le due richieste rimane bassa, ma nel momento in cui facciamo crescere $n$ il divario fra le due diventa sempre più grande.
In tabella riportiamo lo sforzo richiesto in termini di memoria per salvare una matrice e un vettore delle medesime dimensioni.
Supponiamo che la matrice $A$ sia sparsa, ossia che abbia “poche” entrate diverse da zero. In questo caso si decide di salvare la matrice come una serie di terne, ossia salvare
$$ (i,j,a_{i,j}) $$
dove $i$ e $j$ sono rispettivamente l’indice di riga e colonna della matrice in cui l’entrata assume il valore $a_{i,j}$. Questo modo di salvare in memoria la matrice si chiama formato sparso. Prendiamo ora una matrice $A ∈ \R^{n×n}$ e vediamo al variare della dimensione come cambia lo sforzo in termini di memoria per salvare la matrice.
I dati sono raccolti in Tabella 2. Nell’ultima colonna riportiamo la percentuale di memoria che non viene utilizzata rispetto alla rappresentazione piena.