Soluzione numerica di sistemi lineari

Analisi numerica > Soluzione numerica di sistemi lineari

• Indice delle lezioni di:
  • Analisi numerica
• Torna al corso:
  • Matematica
  • Ingegneria meccanica

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

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

$A\mathbf {x} =\mathbf {b}$

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:

${\begin{bmatrix}a_{11}&a_{12}&\cdots &a_{1n}\\a_{21}&a_{22}&\cdots &a_{2n}\\\vdots &\vdots &\ddots &\vdots \\a_{m1}&a_{m2}&\cdots &a_{mn}\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\\\vdots \\x_{n}\end{bmatrix}}={\begin{bmatrix}b_{1}\\b_{2}\\\vdots \\b_{m}\end{bmatrix}}$

e scritto come sistema di equazioni lineari:

$\left\{{\begin{matrix}a_{1,1}x_{1}+a_{1,2}x_{2}+\cdots +a_{1,n}x_{n}=b_{1}\\a_{2,1}x_{1}+a_{2,2}x_{2}+\cdots +a_{2,n}x_{n}=b_{2}\\\vdots \\a_{m,1}x_{1}+a_{m,2}x_{2}+\cdots +a_{m,n}x_{n}=b_{m}\\\end{matrix}}\right.$

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:

• il metodo di Cramer (calcolando il determinante con la regola dello sviluppo di Laplace):

$x_{i}={\det(A_{i}) \over \det(A)}{\mbox{per i=1, ... ,n}}$

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

$\mathbf {x} =A^{-1}\cdot \mathbf {b}$

Risoluzione numerica di sistemi lineari

Per la risoluzione numerica dello stesso problema $A\mathbf {x} =\mathbf {b}$ entrambi i metodi algebrici sono computazionalemnte costosi e scomodi.

Difatti, nel caso in cui si utilizzi la regola di Cramer, è necessario calcolare il determinante della matrice A e di tutte le matrici A_i, 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)! 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

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

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.

Bibliografia

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