In questo capitolo sarà considerato il seguente problema:
Dato un vettore bÎ Rm e una matrice A=(aij), i=1,2,…,n ad elementi reali, si cerca un vettore xÎ Rn tale che:
La risoluzione di un sistema lineare riveste un ruolo fondamentale nella matematica applicata. Diversi modelli matematici significativi, sono di tipo lineare, ma anche i modelli non lineari, in generale più idonei alla descrizione della realtà, sono spesso linearizzati, nel senso che la loro risoluzione è ricondotta alla risoluzione iterata di problemi lineari.
Essendo il sistema lineare uno strumento di base della modellistica matematica, ne scaturisce la necessità di avere a disposizione una varietà di algoritmi dai quali poter scegliere il più adatto, per stabilità, occupazione di memoria, velocità di esecuzione, a risolvere su un determinato calcolatore un particolare sistema.
I metodi di risoluzione per i sistemi lineari sono divisi in due categorie:
- Metodi diretti: sono i metodi che in assenza di errori di arrotondamento danno la soluzione in un numero finito di operazioni. Si tratta sostanzialmente si metodi basati sull'idea della eliminazione Gaussiana.
- Metodi iterativi: la soluzione è ottenuta come limite di una successione di problemi lineari più semplici. Diversamente dal caso precedente, la matrice dei coefficienti non è modificata durante il calcolo e quindi è più agevole sfruttarne la sparsità.
L'idea che sta alla base dei metodi diretti, comunemente attribuita a Gauss, consiste nel ricavare (eliminare) da una fissata equazione, una particolare incognita e nella sua sostituzione nelle equazioni rimanenti. La sostituzione diminuisce la dimensione del problema. Iterando il procedimento, si riduce il problema originario ad un problema ad una dimensione, in una sola incognita. Determinata tale incognita, le altre componenti della soluzione sono successivamente ottenute mediante una procedura di sostituzione (substitution).
Dal punto di vista numerico, si tratta, da una parte di organizzare la procedura in maniera conveniente per essere implementata su un calcolatore e dall’'altra di analizzare i limiti di applicazione del metodo, cioè di individuare per quali matrici il metodo può essere utilizzato e in quale forma il metodo si presenta più stabile.
I metodi iterativi, sono generalmente utilizzati come alternativa a quelli diretti, per risolvere sistemi con matrice sparsa o di ordine elevato. Rispetto ai metodi diretti, quelli iterativi hanno il vantaggio di preservare la struttura della matrice, sfruttandone quindi meglio l'’eventuale sparsità, e di essere, in generale, di più semplice implementazione.