2

Let $M \in \mathbb{R}^{n \times n}$. In a lecture on numerical linear algebra we had a theorem which states that the iteration $\phi(x) = Mx+b$ converges for all $b \in \mathbb{C}^n$ and initial values $x_0 \in \mathbb{C}^n$ if and only if $\rho(M) < 1$ where $\rho$ is the spectral radius. So the question "When does $x_{k+1} = Mx_k + b$ converge for all $b \in \mathbb{C}^n$ and $x_0 \in \mathbb{C}^n$?" has the answer "if and only if $\rho(M) < 1$".

My question is now

"When does $x_{k+1} = Mx_k + b$ converge for all $b \in \mathbb{R}^n$ and $x_0 \in \mathbb{R}^n$?"

Of course it is still sufficient that $\rho(M)<1$ but is it also necessary? If yes, I would appreciate a hint on how to prove this.

EDIT: Proof of theorem mentioned above:

Let $\rho(M) < 1$. Then there is some matrix norm $||\cdot ||$ such that $||M|| < 1$. Apply Banach fixed point theorem on $\phi$. Now, suppose that $\rho(M) \geq 1$. Then pick an eigenvalue $\lambda$ such that $|\lambda|\geq 1$ and let $v$ be some eigenvector to $\lambda$ (it may be complex). Then pick $b = x_0 = v$. It is easy to see, that this fixed point iteration does not converge.

Andrei Kh
  • 2,569
  • If I recall correctly, the proof uses Banach fixed point theorem, so no difference. – Cauchy Aug 11 '17 at 17:05
  • To prove one implication yes, I ask about the other one – Andrei Kh Aug 11 '17 at 17:06
  • Doesn't this answer your question? https://math.stackexchange.com/questions/879626/spectral-radius-and-iterative-method-convergence?rq=1 – Cauchy Aug 11 '17 at 17:10
  • No, since the answers there provide examples for $b$ and $x_0$ which lie in $\mathbb{C}^n$. I want to know if there are necessary $b, x_0 \in \mathbb{R}^n$ such that the iteration does not converge if $\rho(M) \geq 1$. – Andrei Kh Aug 11 '17 at 17:14

1 Answers1

1

If $v$ is an eigenvector for $\lambda$, then $\text{Re}(M^n v) = M^n \text{Re}(v)$ and $\text{Im}(M^n v) = M^n \text{Im}(v)$. If $\|M^n v\| > N$, then at least one of these has norm $> N/2$. Thus for $b = 0$ and at least one of $x_0 = \text{Re}(v)$ and $x_0 = \text{Im}(v)$, the iteration doesn't converge.

Robert Israel
  • 448,999