CG -- The Method of Conjugate Directions

High-level idea

CG -- The Method of Steepest Descent often finds itself taking steps in the same direction as earlier steps. So we have an idea to make it converge faster:

Let’s pick a set of orthogonal search directions $d_{(0)},d_{(1)},...,d_{(n-1)}$. In each search direction, we'll take exactly one step and that step will be just the right length to line up with $x$. After $n$ steps, we'l be done.

Update procedure

Compute \alpha

In order not to step in the previous directions ($d_{(i)}$) again, $e_{(i+1)}$ should be orthogonal to $d_{(i)}$. So,

But we cannot do anything without knowing $e_{(i)}$. But if we know $e_{(i)}$, we can solve the problem.

A-orthogonal instead of orthogonal

Thus, $\alpha$ becomes from #Compute alpha to

Prove we can compute $x$ in $n$ steps

From the above formula, we concludes that ${\alpha }_{(i)}=-{\delta }_{(i)}$

Construct $d_{(i)}$ using Gram-Schmidt Conjugation

CG -- Gram-Schmidt Conjugation

Properties if using the Method of Conjugate Directions

1. The error term is evermore A-orthogonal to all the old search directions since we never step back in the previous directions (Also from equation 35).
2. From 1, since $r_{(i)}=-A{e}_{(i)}$, the residual is evermore orthogonal to all the old search directions, that is
3. From 2, because the search directions ({$d_{(i)}$}) are constructed from the $u$ vectors, the residual $r_{(i)}$ is orthogonal to these previous $u$ vectors, that is
4. From 2 and 3, we have

New updates formula