Il metodo del gradiente coniugato (CG) è il solutore iterativo di riferimento per sistemi lineari A\vec{x} = \vec{b} con A simmetrica definita positiva. Converge in al massimo n passi in aritmetica esatta, e in pochi passi nella pratica per matrici con spettro favorevole.
Vedi anche: Numero di Condizionamento, Fattorizzazione di Cholesky, Spazio Quoziente.
Idea Geometrica
Risolvere A\vec{x} = \vec{b} con A simmetrica definita positiva equivale a minimizzare la forma quadratica:
\phi(\vec{x}) = \frac{1}{2}\vec{x}^T A \vec{x} - \vec{b}^T \vec{x}
Il gradiente di \phi è il residuo \vec{r} = \vec{b} - A\vec{x}.
Algoritmo
Dato \vec{x}_0 iniziale, \vec{r}_0 = \vec{b} - A\vec{x}_0, \vec{p}_0 = \vec{r}_0:
Per k = 0, 1, 2, \ldots:
\alpha_k = \frac{\vec{r}_k^T \vec{r}_k}{\vec{p}_k^T A \vec{p}_k}
\vec{x}_{k+1} = \vec{x}_k + \alpha_k \vec{p}_k
\vec{r}_{k+1} = \vec{r}_k - \alpha_k A \vec{p}_k
\beta_k = \frac{\vec{r}_{k+1}^T \vec{r}_{k+1}}{\vec{r}_k^T \vec{r}_k}
\vec{p}_{k+1} = \vec{r}_{k+1} + \beta_k \vec{p}_k
Le direzioni \vec{p}_k sono A-coniugate: \vec{p}_i^T A \vec{p}_j = 0 per i \neq j.
Spazi di Krylov
Dopo k iterazioni, la soluzione \vec{x}_k appartiene allo spazio di Krylov:
\mathcal{K}_k(A, \vec{r}_0) = \operatorname{span}\{\vec{r}_0, A\vec{r}_0, A^2\vec{r}_0, \ldots, A^{k-1}\vec{r}_0\}
Il CG trova la migliore approssimazione a \vec{x}^* in \mathcal{K}_k rispetto alla norma A-indotta.
Convergenza: \|\vec{x}_k - \vec{x}^*\|_A \leq 2\left(\frac{\sqrt{\kappa} - 1}{\sqrt{\kappa} + 1}\right)^k \|\vec{x}_0 - \vec{x}^*\|_A dove \kappa = \kappa_2(A). Vedi: Numero di Condizionamento.
Metodi di Krylov Generalizzati
Per matrici non simmetriche si usano varianti:
- GMRES (Generalized Minimal Residual): minimizza il residuo nello spazio di Krylov; robusto ma richiede più memoria.
- BiCGSTAB: variante stabilizzata per matrici non simmetriche; richiede meno memoria di GMRES.
- MINRES: per matrici simmetriche indefinite.
Precondizionamento
Il precondizionatore P \approx A trasforma il sistema in P^{-1}A\vec{x} = P^{-1}\vec{b}, riducendo \kappa(P^{-1}A) \ll \kappa(A). Precondizionatori comuni:
- Jacobi (diagonale): P = D. Semplice, parallelo.
- ILU (incomplete LU): più efficace per sistemi da PDE.
- Cholesky incompleta (IC): per sistemi simmetrici definiti positivi. Vedi: Fattorizzazione di Cholesky.
- Multigrid: il precondizionatore più efficace per sistemi da equazioni alle derivate parziali ellittiche.
Applicazioni ingegneristiche
- FEM su larga scala: sistemi con 10^6–10^9 gradi di libertà si risolvono con CG precondizionato; i metodi diretti sono inapplicabili per dimensione e costo.
- Fluidodinamica computazionale: la soluzione delle equazioni di Poisson per la pressione in schemi per Navier-Stokes usa CG o GMRES con precondizionatori ILU.
- Reti neurali e ottimizzazione: L-BFGS e il CG non lineare (Polak-Ribière, Fletcher-Reeves) sono le versioni per ottimizzazione non convessa dei metodi di Krylov.