Let $A \in \Bbb K^{n \times n}$ be invertible, $\ A = M + N$ a decomposition and $T = M^{-1}N$ with $\rho(T) \ge 1$ (spectral radius). Show that the fixed-point iteration for systems of linear equations doesn't converge against the solution $x = A^{-1}b$ for every start vector $x_0 \in \Bbb K^n$.

For $\rho(T) < 1$, we can choose the start vector arbitrary, and then, the fixed point iteration $x_{n+1} = \phi(x_n) = Tx_n + b$ would converge against the fixed point of $\phi$. Furthermore, we know that this fixed point is the solution $x = A^{-1}b$.

In this case, we have to work with $\rho(T) \ge 1$. This means that, in general, we can't assume that, for every start vector, the fixed point iteration converges against the fixed point. I would go as far to say that we don't even know whether there is a certain fixed point or not.

In order to receive such a situation, we would have to choose $x_0$ as an eigenvector to an eigenvalue $\lambda \ge 1$, which exists by the given premises. Then, $\phi$ isn't a contraction anymore, hence, it doesn't converge against the fixed point anymore (at least not in any case).

But this doesn't answer the whole question though. As I said, it is also possible that there isn't even such a fixed point anymore. So, even though $\phi$ doesn't converge against that fixed point, it can still be possible that it converges against another vector that represents the solution of the system of linear equations, isn't it?

For $\rho(T) < 1$, we knew that the fixed point is the only given solution, but in this case, it should also be possible that there is another vector that is the solution of the system, right? Now, my task would be to show that this actually can't be true, I believe.

Does anyone have a hint how I could proceed further?

  • $\begingroup$ What is $b$ and what does it mean to "converge against the solution"? $\endgroup$ – Mark May 7 '17 at 10:53
  • $\begingroup$ When you have a system of linear equations $Ax = b$, and you know that there is one specific vector $x$ that solves this system, and you have a sequence $x_n$ that converges against $x$, then the sequence $x_n$ converges against the solution of $Ax = b$. I don't understand your question about $b$ though. $\endgroup$ – Julian May 7 '17 at 11:07
  • $\begingroup$ So you have a system $Ax = b$ that you're trying to solve and you are trying to do this by repeatedly taking some vector and multiplying by $T$ and adding $b$. (And you are trying to prove that won't always work?) $\endgroup$ – Mark May 7 '17 at 11:15
  • 1
    $\begingroup$ Basically, yes. Do you know about what a fixed-point iteration is? en.wikipedia.org/wiki/Fixed-point_iteration $\endgroup$ – Julian May 7 '17 at 11:34
  • $\begingroup$ It should be $x_{k+1}=-M^{-1}Nx_k + M^{-1}b$ if you want the fixed point to be a solution of $Ax=(M+N)x=b$. If the system has a unique solution, then there is only one fixed point. $\endgroup$ – LutzL May 7 '17 at 15:23

Your Answer

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

Browse other questions tagged or ask your own question.