Mètode del gradient conjugat

En matemàtiques, el mètode del gradient conjugat és un algorisme per a la solució numèrica de sistemes particulars d'equacions lineals, és a dir, aquells la matriu dels quals és positiva-semidefinida. El mètode del gradient conjugat sovint s'implementa com un algorisme iteratiu, aplicable a sistemes dispersos que són massa grans per ser manejats per una implementació directa o altres mètodes directes com la descomposició de Cholesky. Sovint sorgeixen grans sistemes dispersos quan es resol numèricament equacions en derivades parcials o problemes d'optimització.

Una comparació de la convergència del descens del gradient amb la mida òptima del pas (en verd) i el vector conjugat (en vermell) per minimitzar una funció quadràtica associada a un sistema lineal donat. El gradient conjugat, assumint l'aritmètica exacta, convergeix en com a màxim n passos, on n és la mida de la matriu del sistema (aquí n = 2).

El mètode del gradient conjugat també es pot utilitzar per resoldre problemes d'optimització sense restriccions com la minimització d'energia. S'atribueix comunament a Magnus Hestenes i Eduard Stiefel, ^[1][2] que el van programar a la Z4, ^[3] i el van investigar àmpliament.^[4][5]

El mètode del gradient biconjugat proporciona una generalització a matrius no simètriques. Diversos mètodes de gradient conjugat no lineal busquen mínims de problemes d'optimització no lineal.

Descripció del problema abordat pels gradients conjugats

Suposem que volem resoldre el sistema d'equacions lineals

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

per al vector ${\displaystyle \mathbf {x} }$, on el conegut ${\displaystyle n\times n}$ matriu ${\displaystyle \mathbf {A} }$ és simètric (és a dir, A^T = A), positiu definit (és a dir, x^TAx > 0 per a tots els vectors diferents de zero ${\displaystyle \mathbf {x} }$ en Rⁿ), i real, i ${\displaystyle \mathbf {b} }$ també es coneix. Denotem la solució única d'aquest sistema per ${\displaystyle \mathbf {x} _{*}}$.

La derivació com a mètode directe

El mètode del gradient conjugat es pot derivar des de diverses perspectives diferents, inclosa l'especialització del mètode de direcció conjugada per a l'optimització i la variació de la iteració d'Arnoldi/Lanczos per a problemes de valors propis. Malgrat les diferències en els seus enfocaments, aquestes derivacions comparteixen un tema comú: demostrar l'ortogonalitat dels residus i la conjugació de les direccions de cerca. Aquestes dues propietats són crucials per desenvolupar la coneguda formulació sucinta del mètode.

Com a mètode iteratiu

Si triem els vectors conjugats ${\displaystyle \mathbf {p} _{k}}$ amb cura, llavors potser no els necessitem tots per obtenir una bona aproximació a la solució ${\displaystyle \mathbf {x} _{*}}$. Per tant, volem considerar el mètode del gradient conjugat com un mètode iteratiu. Això també ens permet resoldre aproximadament sistemes on n és tan gran que el mètode directe trigaria massa temps.

Denotem la conjectura inicial de x_∗ per x₀ (podem suposar sense pèrdua de generalitat que x₀ = 0, en cas contrari considerem el sistema Az = b − Ax₀). Començant per x ₀ busquem la solució i en cada iteració necessitem una mètrica que ens indiqui si estem més a prop de la solució x_∗ (que ens és desconeguda). Aquesta mètrica prové del fet que la solució x_∗ també és l'únic minimitzador de la següent funció quadràtica

${\displaystyle f(\mathbf {x} )={\tfrac {1}{2}}\mathbf {x} ^{\mathsf {T}}\mathbf {A} \mathbf {x} -\mathbf {x} ^{\mathsf {T}}\mathbf {b} ,\qquad \mathbf {x} \in \mathbf {R} ^{n}\,.}$