0
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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$.)

$\endgroup$
  • $\begingroup$ It is still not clear to me why $\rho(G) < 1$ in order to gurantee convergence. The proof does not make much sense to me. Also, I do not know the right basis to choose $\endgroup$ – Wolfy Jun 16 '16 at 2:35
  • $\begingroup$ 1) A stationary iterative method written in the form you wrote is basically a fixed point iteration, and Banach's fixed point theorem guarantees convergence if $\|G\|<1$. A slightly more involved argument gives the tighter bound $\rho(G)<1$, which is also necessary (since there is a counterexample, and I urge you again to try to construct one). 2) Well, the problem mentions eigenvalues -- can you find a basis related to those? $\endgroup$ – Christian Clason Jun 16 '16 at 7:06
  • $\begingroup$ I can find a basis. It would be great if you could just provide a full answer to this question so that I can understand what to do. $\endgroup$ – Wolfy Jun 17 '16 at 0:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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