Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

Thanks

share|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

1 Answer 1

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|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.