Sunday, May 4, 2014

Expanding Subspace, basis for induction

The original articles are here, conjugate gradient is discussed in the second one. Math notes and technical stuff: Introduction to steepest gradient descent and conjugate gradient

The theorem is stated here:

(i) is proved by induction, but the base step was not provided, it is done here as an exercise.

We need to verify that the $\alpha_k$ calculated from this theorem is in agreement with equation (4).

That is to say $$-g_0^T d_0 = d_0^T Q (x^* - x_0)$$

\begin{align*} -(Qx_0 + b)^T d_0 &= d_0^T Q (x^* - x_0) \\ -(x_0^T Q + b^T) d_0 &= d_0^T Q x^* - d_0^T Q x_0 \\ - b^T d_0 &= d_0^T Q x^* \\ - d_0^T b &= d_0^T Q x^* \\ - b &= Q x^* \\ \end{align*}

So we need to prove $- b = Q x^*$, since $x^*$ is the solution, this is something we already know!