Metodo del Gradiente Coniugato

Voci di Glossario Algebra LineareAnalisi Matematica
Indice dei contenuti

    Il metodo del gradiente coniugato (CG) è il solutore iterativo di riferimento per sistemi lineari Ax⃗=b⃗A\vec{x} = \vec{b} con AA simmetrica definita positiva. Converge in al massimo nn 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 Ax⃗=b⃗A\vec{x} = \vec{b} con AA simmetrica definita positiva equivale a minimizzare la forma quadratica:

    ϕ(x⃗)=12x⃗TAx⃗−b⃗Tx⃗\phi(\vec{x}) = \frac{1}{2}\vec{x}^T A \vec{x} - \vec{b}^T \vec{x}

    Il gradiente di ϕ\phi è il residuo r⃗=b⃗−Ax⃗\vec{r} = \vec{b} - A\vec{x}.

    Algoritmo

    Dato x⃗0\vec{x}_0 iniziale, r⃗0=b⃗−Ax⃗0\vec{r}_0 = \vec{b} - A\vec{x}_0, p⃗0=r⃗0\vec{p}_0 = \vec{r}_0:

    Per k=0,1,2,…k = 0, 1, 2, \ldots:

    αk=r⃗kTr⃗kp⃗kTAp⃗k\alpha_k = \frac{\vec{r}_k^T \vec{r}_k}{\vec{p}_k^T A \vec{p}_k}

    x⃗k+1=x⃗k+αkp⃗k\vec{x}_{k+1} = \vec{x}_k + \alpha_k \vec{p}_k

    r⃗k+1=r⃗k−αkAp⃗k\vec{r}_{k+1} = \vec{r}_k - \alpha_k A \vec{p}_k

    βk=r⃗k+1Tr⃗k+1r⃗kTr⃗k\beta_k = \frac{\vec{r}_{k+1}^T \vec{r}_{k+1}}{\vec{r}_k^T \vec{r}_k}

    p⃗k+1=r⃗k+1+βkp⃗k\vec{p}_{k+1} = \vec{r}_{k+1} + \beta_k \vec{p}_k

    Le direzioni p⃗k\vec{p}_k sono AA-coniugate: p⃗iTAp⃗j=0\vec{p}_i^T A \vec{p}_j = 0 per i≠ji \neq j.

    Spazi di Krylov

    Dopo kk iterazioni, la soluzione x⃗k\vec{x}_k appartiene allo spazio di Krylov:

    Kk(A,r⃗0)=span⁡{r⃗0,Ar⃗0,A2r⃗0,…,Ak−1r⃗0}\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 x⃗∗\vec{x}^* in Kk\mathcal{K}_k rispetto alla norma AA-indotta.

    Convergenza: ∥x⃗k−x⃗∗∥A≤2(κ−1κ+1)k∥x⃗0−x⃗∗∥A\|\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 κ=κ2(A)\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≈AP \approx A trasforma il sistema in P−1Ax⃗=P−1b⃗P^{-1}A\vec{x} = P^{-1}\vec{b}, riducendo κ(P−1A)≪κ(A)\kappa(P^{-1}A) \ll \kappa(A). Precondizionatori comuni:

    • Jacobi (diagonale): P=DP = 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 10610^6–10910^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.

    Ultimo aggiornamento: