Método do gradiente conjugado

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.

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 aritmética exata, converge em no máximo n passos onde n é o tamanho da matriz do sistema (no exemplo, n=2).

Referências

O método do gradiente conjugado foi originalmente proposto em

• Hestenes, Magnus R.; Stiefel, Eduard (dezembro de 1952). «Methods of Conjugate Gradients for Solving Linear Systems» (PDF). 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» (PDF). 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.