Soluzione numerica di sistemi lineari

Analisi numerica > Soluzione numerica di sistemi lineari

lezione
lezione
Soluzione numerica di sistemi lineari
Tipo di risorsa Tipo: lezione
Materia di appartenenza Materia: Analisi numerica
Avanzamento Avanzamento: lezione completa al 75%

Questa lezione è solo un introduzione al genere di problema che andremo a risolvere con l'analisi numerica e i suoi metodi risolutivi.

Risoluzione analitica di sistemi lineari modifica

Un sistema lineare (sistema di equazioni lineari) in algebra lineare viene scritto sinteticamente come:

 

ovvero il prodotto della matrice A (n × m) per il vettore di incognite x è uguale al vettore soluzione b, che esplicitato con matrici e vettori generici vale:

 

e scritto come sistema di equazioni lineari:

 

La sua soluzione (ovvero il valore del vettore incognito x) secondo l'algebra lineare esiste certamente solo se la matrice A è invertibile, e la si può ottenere principalmente in due modi:

 
  • pre-moltiplicando entrambi i termini dell'equazione Ax=b per l'inversa della matrice A (ovvero A-1)[1]:
 

Risoluzione numerica di sistemi lineari modifica

Per la risoluzione numerica dello stesso problema   entrambi i metodi algebrici sono computazionalemnte costosi e scomodi[2].

Difatti, nel caso in cui si utilizzi la regola di Cramer, è necessario calcolare il determinante della matrice A e di tutte le matrici Ai, che se sono grandi (ovvero hanno un numero di righe e colonne molto alto), è difficile da calcolare rapidamente (con lo sviluppo di Laplace bisognerebbe effettuare 2(n+1)![3] operazioni semplici) e può produrre significativi errori di approssimazione dovuti all'utilizzo di numeri finiti, fino all'impossibilità di essere risolte (ciò avviene se per esempio, per approssimazione, il calcolatore considera un det(A)≅0 al denominatore come un det(A)=0, rendendo la divisione impossibile).

Nel caso invece in cui si intendesse calcolare l'inversa della matrice A, si incorrerebbe in problematiche simili al caso precedente poiché il calcolo dell'inversa richiede il calcolo di numerosi determinanti e può portare ad eccessive approssimazioni oppure al fallimento del metodo nel caso in cui una matrice A invertibile risulti - solo a causa dell'approssimazione in numeri finiti - come non invertibile.

Per i motivi sopra esposti si utilizzano due altre classi di soluzioni tipicamente numeriche, tra le quali distinguiamo i metodi diretti e i metodi iterativi.

Metodi diretti modifica

I metodi diretti sono caratterizzati da un numero di passaggi di calcolo definito dalla logica di soluzione. Tra questi metodi esamineremo il metodo di eliminazione di Gauss, la fattorizzazione LU e la fattorizzazione di Cholesky.

Metodi iterativi modifica

I metodi iterativi, a differenza dei diretti, sono caratterizzati da un numero di passaggi possibili potenzialmente infinito che si ripetono in sequenze e permettono generalmente di approssimare sempre meglio la soluzione con un numero sempre più alto di passaggi. Tuttavia per il calcolo su calcolatori il numero di passaggi sarà sempre finito, perciò è necessario ogni volta stabilire un criterio di arresto che decida quando terminare l'iterazione.

Tra questi metodi esamineremo il metodo di Jacobi, il metodo di Richardson e il caso del metodo del gradiente.

Note modifica

  1. Ricordiamo la proprietà delle matrici per cui  , ovvero: il prodotto di una qualunque matrice per la propria inversa è uguale alla matrice identità, che è l'elemento neutro del prodotto tra matrici, ovvero  
  2. pag.121-164, Introduzione al corso di calcolo scientifico, Quarteroni, Saleri, Ed. Springer, 2006
  3. pag.124, Introduzione al corso di calcolo scientifico, Quarteroni, Saleri, Ed. Springer, 2006

Bibliografia modifica

  • Introduzione al corso di calcolo scientifico, Quarteroni, Saleri, Ed. Springer, 2006