Linear stationary iteration method

Question

Suppose you are attempting to solve $Ax = b$ using linear stationary iteration method defined by $$x_k = G x_{k-1} + f$$ that is consistent with $Ax = b$, i.e., for which $f = (I - G)A^{-1}b$. Suppose the eigenvalues of $G$ are real and such that $|\lambda_1| > 1$ and $|\lambda_i| < 1$ for $2\leq i \leq n$. Also, suppose that $G$ has $n$ linearly independent eigenvectors, $z_i$, $1\leq i \leq n$.

a.) Show that there exists an initial condition $x_0$ such that $x_k\rightarrow x = A^{-1}b$

b.) Does your answer give a characterization of selecting $x_0$ that could be used in practice to create an algorithm that would ensure convergence?

Solution - Let $e^{(k)} = x_k - x$ be the error on step $k$. We know that $$e^{(0)} = \sum_{i=1}^{n}\alpha_i z_i, \ \ \|z_i\| = 1$$ Since $|\lambda_i| < 1$ then we can conclude that $$\lim_{k\rightarrow \infty} e^{(k)} = 0$$ which implies that there is a fixed point $x^* = A^{-1} b$. Thus there exists an $x_0$ such that $x_k\rightarrow x^* = A^{-1}b$.

I am not really sure if this is correct. Any suggestions are greatly appreciated. This is not homework. I am preparing for a qualifier exam at the end of August in Computational Mathematics.

Answer 1

This is not correct. To conclude that the error converges, you need that all eigenvalues (and thus the spectral radius) of the iteration matrix are less than $1$; but the problem states that $\lambda_1>1$. So the standard theory is not applicable. (In fact, since you don't use any property of $x_0$, you have "shown" convergence of the iteration. This should have made you suspicious.)

I'm not giving the full answer, but here's a hint: Your approach of writing the initial error as a linear combination of basis vectors $z_i$ is right, but you have to choose the right basis -- if you look at the statement again (and the standard counterexample for why $\rho(G)<1$ is necessary for convergence), you should see that there's an obvious choice.

EDIT Since you insist:

As the statement of the problem suggests, expand the error $e_0$ in the basis $z_i$ of eigenvectors of $G$. Then any $x_0$ such that $\alpha_1=0$ will do. (Naturally, to actually find such an $x_0$, you'd have to already know $x$.)