I am reading about Lemma 5.2.1 form here. Bellow the lemma is attached from the link. 
According to this lemma, i.e., $(5.2.2)$, $q_{k+1}$ must lie in the span of $q_i$ and $Hq_k$, Next, in order to compute $q_{k+1}$, it suffices to find a vector
$$y_{k+1} = \sum_{i=0}^{k} \theta_{ki} q_i + Hq_k\tag{1}$$
that is orthogonal to $q_i$ for $0 \leq j \leq k$ and then normalize $y_{k+1}$ to get $q_{k+1} = y_{k+1}/\gamma_{k+1}$, where $\gamma_{k+1} = ||y_{k+1}||_2$. Then, using the orthogonality of the $y_{k+1}$ with the $q_i$, $i=0,\dots,k$ we derive
$$0 = \langle q_j, y_{k+1} \rangle = \sum_{i=0}^k \theta_{ki} \langle q_j, q_i\rangle + \langle q_j, Hq_k \rangle = \theta_{kj} + \langle q_j, Hq_k \rangle.$$
As $q_i$ are orthonormal, from $(5.2.2)$, it is implied that
$$Hq_j \in span \{ q_0, q_1, \dots, q_j, q_{j+1}\},\quad j=0,\dots,k\tag{2}$$
and hence $$\langle q_i, Hq_k\rangle=0\tag{3}$$ for $j \leq k-2$. This way, $y_{k+1}$ can be writen as alinear combination of $Hq_k$ and the previous two orthonormal vectors, i.e.,
$$y_{k+1} = Hq_k – \langle q_k, Hq_k \rangle q_k – \langle q_{k-1}, Hq_k \rangle q_{k-1}$$
My questions are:
- Why in $(1)$ we do not use a $\theta$ coefficien for the $Hq_k$ term as we did for $q_i$?
- Why in $(3)$ the terms are zero for $j \leq k-2$? For this question, if we use $(2)$, i.e., for some $\lambda_i \in \mathbb{R}$ we may write
$$Hq_k = \sum_{i=0}^k \lambda_i q_{i+1}$$ and
$$\langle q_j, Hq_k\rangle = \sum_{i=0}^k \lambda_i \langle q_j ,q_{i+1}\rangle$$ but I could not reach the result in $(3)$ for $j \leq k-2$.
Could you please provide some explanations?
Best Answer
Why does $Hq_k$ not have a coefficient in $(1)$?
What we're doing in (1) is providing a general form for $y_{k+1}$ in which we'll later be able to solve for the coefficients $\theta_{k0}, \dots, \theta_{kk}$ to get the properties we want: that $y_{k+1} \in \operatorname{span}\{q_0, q_1, \dots, q_k, H q_k\}$ and that $\langle q_j, y_{k+1}\rangle = 0$ for $j=0, 1, \dots, k$.
The set of all such $y_{k+1}$ is a $1$-dimensional vector space, and it doesn't matter which element of that space we pick, because we're going to normalize and set $q_{k+1} = \frac{y_{k+1}}{\|y_{k+1}\|}$ anyway. So we're going to pick a specific $y_{k+1}$ to find: the one with a coefficient of $1$ on $Hq_k$. This makes our algebra easier.
If we put an unknown coefficient on $Hq_k$, we'd be able to solve for $\theta_{k0}, \dots, \theta_{kk}$ in terms of that coefficient, getting a family of solutions proportional to the $y_{k+1}$ we actually do find. Since we normalize anyway, that doesn't gain us anything.
How do we know that $\langle q_j, H q_k \rangle = 0$ for $j \le k-2$?
Because $H$ is symmetric, we have $\langle q_j, Hq_k \rangle = \langle Hq_j, q_k\rangle$, so it's enough to check that $Hq_j$ is orthogonal to $q_k$ for $j \le k-2$.
By the lemma, $$Hq_j \in \operatorname{span}\{q_0, q_1, \dots, q_{j+1}\},$$ so when $j \le k-2$, we have $$Hq_j \in \operatorname{span}\{q_0, q_1, \dots, q_{j+1}\} \subseteq \operatorname{span}\{q_0, q_1, \dots, q_{k-1}\}.$$ All of $q_0, q_1, \dots, q_{k-1}$ are orthogonal to $q_k$; therefore $Hq_j$ is also orthogonal to $q_k$.