I am reading about conjugate directions from here (Algorithm 5.1.1). The algorithm is
Given $r_0$, set $p_0=-r_0$ and for $k=0,1,\dots,$ perform the
iteration $$a_k = ||r_k||^2 / \langle p_k, Hp_k \rangle\tag{1}$$ $$r_{k+1} =
r_k + a_k H p_k\tag{2}$$ $$\beta_k = ||r_{k+1}||^2/||r_{k}||^2\tag{3}$$ $$p_{k+1} = -r_{k+1} + \beta_k p_k\tag{4}$$
I the reference, it is stated that $$\mathcal{K}(H, r_0,j)=\text{span} \{ p_0, \dots, p_j\}=\text{span} \{ r_0, \dots, r_j\}\tag{5}$$ where $\mathcal{K}(H, r_0,j)$ is the Krylov subspace. Could you please someone explain how can be get the last equality using the update rules in the algorithm?
EDIT:
For the equivalence $\mathcal{K}(H, r_0,j)=\text{span} \{ r_0, \dots, r_j\}$ from $(2)$ and $p_0 = -r_0$ we have
$$r_1 = r_0 – a_0 H r_0 \in \text{span} \{ r_0, Hr_0\}.$$ Similarly, using this with $(2)$ $(3)$ ,and $p_0 = -r_0$
$$\begin{aligned}r_2 = &r_1 + a_1 Hp_1 = (r_0 -a_0 Hr_0) + a_1 H(-r_1 + \beta_0 p_0) \\ = & \dots = r_0 – (a_0 + a_1+a_1\beta_0)Hr_0 -a_1 a_0 H^2 r_0 \in \text{span} \{ r_0, Hr_0, H^2r_0\}\end{aligned} $$
Then recursively, we get $r_j \in \text{span} \{ r_0, Hr_0, H^2r_0, \dots, H^jr_0\} \in \mathcal{K}(H, r_0,j)$. Following a similar procedure, we can show that $p_j \in \text{span} \{ r_0, Hr_0, H^2r_0, \dots, H^jr_0\} \in \mathcal{K}(H, r_0,j)$. How do we proceed to prove $(5)$?
Best Answer
Let me just prove $span \{ p_0,...,p_j \} = span \{ r_0,...,r_j \}$. By (4) I have for any $k \in [0..j-1]$ that $$ r_{k+1} = \beta_k p_k - p_{k+1} \in span \{ p_0,...,p_j \} $$ and $$ r_0 = -p_0 \in span \{ p_0,...,p_j \} $$ which yields the inclusion in the opposite direction. For the direct direction, we have for any $k \in [0..j-1]$ $$ p_{k+1} = -r_{k+1} + \beta_k p_k\in span \{ r_{k+1},p_k \} $$ so by induction $$ p_{k+1} \in span \{ r_{k+1},p_k \} \subset span \{ r_{k+1},r_k, p_{k-1} \} \subset ... \subset span \{ r_{k+1},r_k, ..., r_0\}. $$ Re using $r_0 = -p_0$ we have the inclusion in the direct direction.