2
$\begingroup$

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

  • 0
    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 breakdown2012-11-26

1 Answers 1

0

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.