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}_{\left(0\right)},{d}_{\left(1\right)},...,{d}_{\left(n-1\right)}$. 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.

Example

Update procedure

${x}_{\left(i+1\right)}={x}_{\left(i\right)}+{\alpha }_{\left(i\right)}{d}_{\left(i\right)}$

Compute \alpha

In order not to step in the previous directions (${d}_{\left(i\right)}$) again, ${e}_{\left(i+1\right)}$ should be orthogonal to ${d}_{\left(i\right)}$. So,

But we cannot do anything without knowing ${e}_{\left(i\right)}$. But if we know ${e}_{\left(i\right)}$, we can solve the problem.

Definition

Two vectors ${d}_{\left(i\right)}$ and ${d}_{\left(j\right)}$ are A-orthogonal, or conjugate if

${d}_{\left(i\right)}^{T}A{d}_{\left(j\right)}=0$

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

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

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

Construct ${d}_{\left(i\right)}$ 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}_{\left(i\right)}=-A{e}_{\left(i\right)}$, the residual is evermore orthogonal to all the old search directions, that is
3. From 2, because the search directions ({${d}_{\left(i\right)}$}) are constructed from the $u$ vectors, the residual ${r}_{\left(i\right)}$ is orthogonal to these previous $u$ vectors, that is
4. From 2 and 3, we have
Info