1
$\begingroup$

What is the easiest or most clear way to derive or discover the conjugate gradient method for solving $Ax = b$, where $A$ is a symmetric positive definite matrix?

I think the answer might be something like this: At iteration $k$, find the vector in the $k$th Krylov subspace for $A$ which minimizes $\frac12 x^T A x - x^T b$. But I would like to understand the details. And maybe there is a completely different point of view which is even easier or more clear.

I realize that much has been written about the conjugate gradient method, but I think that after all this time it is still usually explained poorly. For example, Trefethen's book Numerical Linear Algebra presents the conjugate gradient method without motivation, then proves it has certain properties (and later interprets it as minimizing a functional using special search directions, but does not explain how we would discover the search directions). There is a famous document titled "An introduction to the conjugate gradient method without the agonizing pain", but this document is 58 pages long. I want an explanation that is short and sweet for people who are strong in linear algebra and have plenty of mathematical maturity, but do not yet know the conjugate gradient method.

Also, I have not found a math.stackexchange question which explains how the conjugate gradient method is derived. And I often find that the most clear explanations for any topic tend to appear on math.stackexchange.

$\endgroup$
  • $\begingroup$ Golub & Van Loan's description in Matrix Computations was the first exposition I read that provided some Krylov subspace motivation. (I'm not saying that it was the first such description, just the first that I read, it was a bit of an 'ah hah' moment.) $\endgroup$ – copper.hat Feb 20 '17 at 23:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.