Convergence of iterative methods to solve linear system

53 Views Asked by At

Let $A\in\mathrm{GL}_n(\mathbb{R})$ such that $A=M-N$ with $(M,N)\in\mathrm{GL}_n(\mathbb{R})\times\mathcal{M}_n(\mathbb{R})$. I don't understand the proof of the following statement :

If $\rho (M^{-1}N)\geq 1$ then there exist $u_0\in\mathbb{R}^n$ such $$ u_{k+1}=M^{-1}(Nu_k +b)$$ is not convergent.

The author of the book that I'm reading do the following : Let $\lambda$ an eigenvalue of $M^{-1}N$ such $|\lambda |\geq 1$, and $\tilde{u}=\tilde{u_1}+i\tilde{u_2}$ an eigenvectors of $\lambda$. Then $(u_k)_k$ is divergente for $u_0=u+\tilde{u_1}$ or $u_0=u+\tilde{u_2}$ (where $u=(M-N)^{-1}b$).

I understand that the problem is that we have to find $u_0$ in $\mathbb{R}^n$ and that the eigenvector as no reason to be real. First I assumed that $x\in\mathbb{R}^n$ and try to compute the definition of $(u_k)_k$ to find a geometric sequence, but it's not the case. Plus the case $\lambda =1$ is possible.

When we have $x\in\mathbb{C}^n$, another problem I have is that $\Re (\lambda )$ and $\Im (\lambda )$ can be $<1$ so trying to find a geometric relation is probably not a good idea.

Any help will be greatly appreciate.


Note : I found something interesting. Let $e_k=u_k-u$ it led to $$ e_k = M^{-1}Ne_{k-1}$$ hence $e_k=(M^{-1}N)^ke_0$. So if we consider $u_0=u+\tilde{u_i}$ as the author suggested, we find $$ u_k = (M^{-1}N)^k\tilde{u_i} +u .$$ I don't not yet why this is not convergente, but in the case where $x$ is real : $$ u_k = (M^{-1}N)^kx +u =\lambda^k +u$$ is clearly divergent if $\lambda >1$.