

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer

I am working on a homework, where we have to proof that GMRES finds an exact solution of $Ax = b$ in at most m steps (with A being an $m \times m$-matrix). The proof is split up into several steps, and I have already solved all but one. The remaining one is:

Under the assumption in (c - see below), show that the solution x to the system of equations $Ax = b$ lies in $\mathcal{K}_n$. Conclude that GMRES has found the solution to $Ax = b$ in step n.

Here is part c (I already proved that one): Assume that at some n, $h_{n+1,n} = 0$ in the Arnoldi iteration (Arnoldi breakdown). Show that $\mathcal{K}_n$ is an invariant subspace of A, i.e. $Av \in \mathcal{K}_n$, for every $v \in \mathcal{K}_n$.

Note: The question here is such that the solution is already found in $n < m$ steps if there happens to be an Arnoldi breakdown, i.e., $h_{n+1,n} = 0$.

My idea so far was to say that if $x$ (the real solution) were not in $\mathcal{K}_n$, than there has to exist a vector $v \in \mathcal{K}_n$ such that $A^{k}v = \alpha x$ - i.e. subsequent Arnoldi iterations will transform $v$ into $x$ (apart from the length - that's why there is the factor $\alpha$). That would be proof by contradiction.

But I don't feel like my assumption that this vector exists is necessarily true. So any advice for me?


share|cite|improve this question
Hint After $m$ iterations, you have $m$ orthogonal search directions to find the minimum in $\mathbb{R}^m$. – Daryl Nov 26 '12 at 19:15
Sorry, my question was maybe a bit unclear, I updated it. After m iterations it is obvious, but we have the case that we have $n < m$ iterations with an Arnoldi breakdown – disaster Nov 26 '12 at 19:22
up vote 0 down vote accepted

Recall that if $Q$ contains the orthonormal basis vector for the Krylov subspace, with $x=Qy+x_0$ as the solution, $y$ can be found by solving the linear system $$\widetilde{H}y=\beta e_1$$ depending on your notation. With $h_{n+1,n}=0$, this system is consistent.

You should be able to take it from here.

share|cite|improve this answer

Your Answer


