Método do gradiente conjugado

Uma comparação da convergência do método de descida do gradiente com tamanho de passo ótimo (em verde) e o método do gradiente conjugado (em vermelho) para a minimização da forma quadrática com um sistema linear dado. O gradiente conjugado, assumindo aritimética exata, converge em no máximo n passos onde n é o tamnho da matriz do sistema (no exemplo, n=2).

Em matemática, o método do gradiente conjugado é um algoritmo para a solução numérica de sistemas particulares de equações lineares, aqueles cuja matriz é simétrica e positiva definida. O método do gradiente conjugado é um método iterativo, então ele pode ser aplicado a sistemas esparsos que são grandes demais para ser tratados por métodos diretos como a decomposição de Cholesky. Tais sistemas surgem frequentemente quando se resolve numericamente equações diferenciais parciais.

Referências

O método do gradiente conjugado foi originalmente proposto em

• Hestenes, Magnus R.; Stiefel, Eduard. (dezembro, 1952). "Methods of Conjugate Gradients for Solving Linear Systems". Journal of Research of the National Bureau of Standards 49 (6).

Descrições do método podem ser encontradas nos seguintes livros texto:

• Kendell A. Atkinson (1988), An introduction to numerical analysis (2nd ed.), Section 8.9, John Wiley and Sons. ISBN 0-471-50023-2.
• Mordecai Avriel (2003). Nonlinear Programming: Analysis and Methods. Dover Publishing. ISBN 0-486-43227-0.
• Gene H. Golub and Charles F. Van Loan, Matrix computations (3rd ed.), Chapter 10, Johns Hopkins University Press. ISBN 0-8018-5414-8.

Ligações externas

• Método do gradiente conjugado por Nadir Soualem.
• Método do gradiente conjugado com precondicionamento por Nadir Soualem.
• An Introduction to the Conjugate Gradient Method Without the Agonizing Pain por Jonathan Richard Shewchuk.
• Métodos iterativos para sistemas lineares esparsos por Yousef Saad
• LSQR: Equações esparsas e mínimos quadrados por Christopher Paige e Michael Saunders.