# 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ó.
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, que el van programar a la Z4, i el van investigar àmpliament.
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
$\mathbf {A} \mathbf {x} =\mathbf {b}$
per al vector $\mathbf {x}$, on el conegut $n\times n$ matriu $\mathbf {A}$ és simètric (és a dir, A$^T$ = A), positiu definit (és a dir, x$^T$Ax > 0 per a tots els vectors diferents de zero $\mathbf {x}$ en R$^n$), i real, i $\mathbf {b}$ també es coneix. Denotem la solució única d'aquest sistema per $\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 $\mathbf {p} _{k}$ amb cura, llavors potser no els necessitem tots per obtenir una bona aproximació a la solució $\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$_0$ (podem suposar sense pèrdua de generalitat que x$_0$ = 0, en cas contrari considerem el sistema Az = b − Ax$_0$). Començant per x $_0$ 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
$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}\,.$

## Referències

* ↑ Hestenes, Magnus R.; Stiefel, Eduard Journal of Research of the National Bureau of Standards, 49, 6, December 1952, pàg. 409. DOI: 10.6028/jres.049.044 [Consulta: free].
* ↑ On the Extension of the Davidon–Broyden Class of Rank One, Quasi-Newton Minimization Methods to an Infinite Dimensional Hilbert Space with Applications to Optimal Control Problems (PhD thesis) (tesi) (en anglès). PhD, 1971.
* ↑ Speiser, Ambros. «Konrad Zuse und die ERMETH: Ein weltweiter Architektur-Vergleich». A: Hellige. Geschichten der Informatik. Visionen, Paradigmen, Leitmotive (en alemany). Berlin: Springer, 2004, p. 185. ISBN 3-540-00217-0.
* ↑ Polyak, Boris. Introduction to Optimization (en anglès), 1987.
* ↑ Greenbaum, Anne. Iterative Methods for Solving Linear Systems (en anglès), 1997. DOI 10.1137/1.9781611970937. ISBN 978-0-89871-396-1.