Conjugate Gradient

vs Gradient Descent on SPD matrix

Solving $Ax = b$ where $A$ is SPD is equivalent to minimizing the quadratic form:

f(x) = \frac{1}{2}x^T A x - b^T x

Iteration 0

Use Left/Right arrow keys to navigate steps

Gradient Descent (Blue)

Moves strictly in the direction of the local negative gradient. Because the "bowl" is skewed (ill-conditioned $A$ ), the path zig-zags back and forth, taking many steps to reach the bottom.

Conjugate Gradient (Red)

Chooses search directions that are $A$ -orthogonal (conjugate) to all previous directions. For an $n \times n$ matrix, it perfectly reaches the minimum in exactly $n$ steps. Here ( $n=2$ ), it reaches the center in exactly 2 steps!

Gradient Descent (Zig-Zag)

Conjugate Gradient (A-orthogonal)