Metodo del gradiente coniugato

Da Wikipedia, l'enciclopedia libera.

In analisi numerica, il metodo del gradiente coniugato (spesso abbreviato in CG, dall'inglese conjugate gradient) è un algoritmo per la risoluzione numerica di un sistema lineare la cui matrice sia simmetrica e definita positiva.

Il metodo è stato inizialmente proposto nel 1952 dai matematici Magnus Hestenes e Eduard Stiefel[1] e costituisce una variante del metodo del gradiente in cui la direzione di discesa a ogni passo è scelta in modo tale da garantire la convergenza del metodo (in aritmetica esatta) in un numero di iterazioni pari al più alla dimensione del sistema da risolvere.

Il metodo del gradiente biconiugato ne fornisce una generalizzazione al caso di matrici non simmetriche.

Descrizione del metodo[modifica | modifica wikitesto]

Si voglia calcolare la soluzione del sistema lineare

dove è una matrice simmetrica e definita positiva a coefficienti reali e è il termine noto.

La matrice , grazie alle sue proprietà, induce un prodotto scalare definito da

Una coppia di vettori che soddisfa , cioè ortogonale rispetto a questo prodotto scalare, si dice -coniugata.

Inoltre la soluzione del sistema lineare precedente corrisponde al punto di minimo della forma quadratica

Infatti:

da cui

Confronto tra il metodo del gradiente classico (in bianco) e metodo del gradiente con direzioni coniugate (in rosso) per la risoluzione di un sistema lineare di dimensione La soluzione iniziale è, per entrambi i metodi, e la soluzione esatta del sistema è

Questo suggerisce di procedere iterativamente, partendo da una data soluzione iniziale e muovendosi lungo direzioni che minimizzano la forma quadratica A differenza del metodo del gradiente, in cui la direzione di discesa al -esimo passo è scelta pari a , nel caso del gradiente coniugato essa viene scelta in modo che risulti -ortogonale alle direzioni precedenti, cioè Il significato geometrico di tale scelta è mostrato nella figura a lato, da cui emerge in particolare il vantaggio di scegliere direzioni -ortogonali e non semplicemente ortogonali alle linee di livello della funzione .

Alla -esima iterazione la soluzione viene dunque aggiornata nel modo seguente:

dove corrisponde alla lunghezza del passo di discesa. È possibile dimostrare (si veda ad esempio Soluzione di sistemi lineari) che la scelta ottimale per , che porta cioè al minimo di , è

dove

è il residuo del sistema.

Un metodo per calcolare direzioni di discesa -ortogonali alle precedenti è il seguente[2]:

con ; la scelta ottimale per è

Algoritmo risolutivo[modifica | modifica wikitesto]

Lo schema generale per la soluzione mediante metodo del gradiente coniugato è il seguente:

L'eventuale implementazione dell'algoritmo in aritmetica floating point, in cui la convergenza in al più passi non è garantita, il ciclo for può essere sostituito da un ciclo while che verrà eseguito finché la norma del residuo non sia più piccola di una tolleranza impostata dall'utente.

Metodo del gradiente coniugato precondizionato[modifica | modifica wikitesto]

In molti casi è possibile accelerare ulteriormente la velocità di convergenza dell'algoritmo migliorando le proprietà di condizionamento della matrice . Si introduca a tal fine una matrice di precondizionamento simmetrica e definita positiva. L'algoritmo corrispondente al metodo del gradiente coniugato precondizionato (spesso abbreviato in PCG, dall'inglese preconditioned conjugate gradient) si ottiene applicando la versione senza precondizionamento per trovare la soluzione del seguente sistema:

,

dove è la radice quadrata di e .

Lo schema risolutivo in questo caso diventa[2]:

Analisi dell'errore[modifica | modifica wikitesto]

È possibile dimostrare che l'errore commesso alla -esima iterazione del metodo del gradiente coniugato soddisfa la seguente stima[2]:

dove

il numero di condizionamento in norma di e è la norma indotta da .

Nel caso precondizionato vale la stessa stima con

Esempio di implementazione[modifica | modifica wikitesto]

Si riporta un esempio di possibile implementazione del metodo del gradiente coniugato non precondizionato compatibile con i linguaggi di programmazione Octave e MATLAB.

function [xk] = conj_grad(A, b, x0, nmax, toll)
    xk = x0;        
    rk = b - A * xk;
    pk = rk;
    iter = 1;
    while ((norm(rk) >= toll) && (iter <= nmax))
        alphak = (pk' * rk) / (pk' * A * pk);
        xk = xk + alphak * pk;
        rk = b - A * xk;
        betak = (pk' * A * rk) / (pk' * A * pk);
        pk = rk - betak * pk;
    end
    if iter == nmax
        warning('Convergenza non raggiunta in nmax iterazioni!');
    end
end

Note[modifica | modifica wikitesto]

  1. ^ Hestenes, M. e Stiefel, E., Methods of Conjugate Gradients for Solving Linear Systems (PDF), in Journal of Research of the National Bureau of Standards, vol. 49, nº 6, 1952, pp. 409-436. URL consultato il 17 giugno 2016.
  2. ^ a b c Quarteroni, Sacco, Saleri

Bibliografia[modifica | modifica wikitesto]

  • A. Quarteroni, R. Sacco e F. Saleri, Matematica numerica, 4ª ed., Milano, Springer Verlag, 13 marzo 2014, ISBN 978-88-470-5643-5.

Voci correlate[modifica | modifica wikitesto]

Collegamenti esterni[modifica | modifica wikitesto]

Matematica Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica