In questo capitolo ci occuperemo di metodi diretti per la risoluzione di un sistema lineare. Vedremo che per particolari casi, il sistema lineare è facilmente risolubile e poi analizzeremo in dettaglio l’algoritmo di Gauß e le decomposizioni PALU e Cholesky. In questa analisi daremo spazio anche all’aspetto implementativo dando le idee generali, cosicché questi algoritmi possano essere implementati in diversi linguaggi di programmazione o librerie.
Supponiamo di voler risolvere il seguente sistema lineare
Quando si risolve questo sistema con carta e penna si osservano i coefficienti e si attuano delle strategie per eliminare un’incognita o un’equazione. Queste scelte sono essenzialmente dettate dalla nostra fantasia e dalla nostra capacità di calcolo e si adattano ogni volta che ci troviamo di fronte a un sistema differente. Capite bene che risulterebbe oneroso e difficile programmare un calcolatore per imitare le decisioni che “noi umani” facciamo per risolvere un sistema lineare.
Come abbiamo visto in precedenza, un sistema lineare può essere riscritto in termini di prodotti matrice e vettore. Definiamo $A \in \R^{n\times n}$, $\texttt x \in \R^n$ e $b \in \R^n$
allora il sistema sopra si traduce nella forma più compatta
$$ A\texttt x = b $$
Un computer “vede” un sistema lineare come una matrice e utilizza le operazioni base fra matrici e vettori per trovare la soluzione $\texttt x$.
Nel caso in cui la matrice $A$ ha “forme” particolari la risoluzione di un sistema lineare è molto semplice. Questo è il caso in cui le matrici sono triangolari superiori o inferiori. Analizziamo il primo caso (il secondo è del tutto analogo).
Per rendere più chiara la procedura supponiamo che la dimensione della matrice $U$ sia 4 e che il sistema sia risolvibile ossia che $\det(U)\neq 0$. Consideriamo allora la matrice $U \in \R^{4\times 4}$ triangolare superiore
ad essa è associato il sistema lineare
Questo sistema lineare è facile da risolvere, dato che si può risolvere a cascata partendo dall’ultima equazione e ottenere quindi tutte le incognite $x_1,x_2,x_3$ e $x_4$. Vediamo in dettaglio questa procedura. Partiamo ricavando l’incognita $x_4$ dall’ultima equazione
$$ x_4 = \frac{b_4}{u_{4,4}} $$
D’ora in poi la variabile $x_4$ è nota, quindi può essere sostituita nella terza equazione per ottenere $x_3$, i.e.,
