Why are we choosing the Krylov projection method like this? I am attending a course on numerical linear algebra, where we talk about Krylov-Methods right now. We want to construct a sequence which converges to a solution of a system of linear equations $Ax = b$.
Lets say that $x_0$ is our starting point. In an iterative manner we want to construct $x_k$ such that $x_k \in x_0 + \mathcal{K}^k(A,r_0)$. Here we just say that $x_0 = 0$ and with that $r_0 = b$. Here is now the thing I don't understand:
We construct the $x_k$ in such a way that $r_k \perp \mathcal{K}^k(A,r_0)$ so that we get the constraints $$B_k^T(b - Ax_k) = 0$$
where $B_k$ is a Basis of the k-th Krylov subsapce. How is this orthogonality constraint helpful in finding a good sequence $\{x_k\}$?
 A: In general, there is no guarantee that the sequence $x_0, x_1, x_2 \dotsc$ will converge rapidly towards the solution $x$ of $Ax=b$. In that sense, the orthogonality condition is not useful at all.
However, there are practical considerations that are important when the sequence converges so fast that it is actually useful.
If you generate the basis $V_k = [v_1, v_2, \dots v_k ]$ of $K_k(A,b)$ using the celebrated Arnoldi method, then you achieve a factorization of the form
$$A V_k = V_{k+1} \bar{H}_k$$
where $\bar{H}_{k+1} \in \mathbb{R}^{(k+1) \times k}$ is an upper Hessenberg matrix. Now if we seek $x_k = V_k y_k$, then the orthogonality condition reduces to
$$ V_k^T A V_k y_k = H_k y_k = V_k^T b = \|b\|_2 e_1^{(k)}$$
where $H_k \in \mathbb{R}^{k \times k}$ consists of the first $k$ rows of $\bar{H}_k$ and $e_1^{(k)}$ is the first column of the $k$-by-$k$ identity matrix. It is now straight forward to solve the linear system
$$H_k y_k = \|b\|_2 e_1^{(k)}$$ because it is almost upper triangular. The standard procedure is to use Givens rotations to reduce it to upper triangular form. The beauty of this procedure is that the work can be recycled if we decided that we need to increase $k$.
In summary, the orthogonality condition is not useful for choosing a good sequence, but it simplifies the problem of computing the sequence.
Good sequences can be often be obtained by preconditioning, i.e., by effectively replacing the linear system $Ax=b$ with another linear system, often of the form $M^{-1} Ax = M^{-1} b$, which has the same solution, but a sequence that converges rapidly.
A: So im going to Argument this for any Subspace $U_k$ you can substitute it with the Krylow-Subspaces its equivalent:
We are trying to solve $$||x_k-x||_A=\min_{y\in U_k}||y-x||_A.$$
Because we are in Spaces with a dotproduct with the Projection-Theorem this is equivalent to:
$$\langle x-x_k,u\rangle_A \forall u\in U_k$$
Since we are using the dot-product given my the Matrix $A$ we can rewrite it as:
$$\langle x-x_k,u\rangle_A=\langle A(x-x_k),u\rangle=\langle b-Ax_k,u\rangle.$$
So basically we are using the Projection-Theorem in Spaces with dot-Products to find our Approximation, which naturally gives us the orthogonality constraint.
