Spectral radius and iterative method convergence

Question

I'm trying to show that if the spectral radius of $R$, $\rho(R)\geq 1$, then there exist iterations of the form, given $\mathbf{x}_0$,

$\mathbf{x}_{n+1}=R\mathbf{x}_n+\mathbf{c}$

Which do not converge. Let $(\lambda, \mathbf{x}_\lambda)$ be the eigenpair corresponding to the spectral radius. Then choosing $\mathbf{x}_0=\mathbf{x}_\lambda$ results in,

$\mathbf{x}_n=R^n\mathbf{x}_\lambda + \left(\sum_{i=0}^{n-1}R^i\right)\mathbf{c}$

Then,

$\begin{align}\lVert\mathbf{x}_{n+1}-\mathbf{x}_n\rVert &= \lVert R^n(R-\mathbb{I})\mathbf{x}_\lambda+R^n\mathbf{c}\rVert\\ &=\lVert \lambda^n(\lambda-1)\mathbf{x}_\lambda+R^n\mathbf{c}\rVert \end{align} $

I'm not sure how to proceed from here, as I can only show this norm is less than or equal to $\infty$ with the triangle and sub-multiplicative properties of a norm.

Thanks!

Answer 1

I guess you are considering the finite dimensional Euclidean space $\mathbb{C}^N$ which means that any norm can be used to investigate convergence of a sequence, say, the $1$-norm, $\|\mathbf{x}\|_1 \triangleq \sum_{i=1}^N|x_i|$, where $x_i$ is the $i$-th element of $\mathbf{x}$. A necessary condition for $\{\mathbf{x}_n\}$ to converge is that $\|\mathbf{x}_n\|_1$ is bounded for all $n$. For $\mathbf{x}_0 = \mathbf{u}$ where $ \mathbf{u}$ is the eigenvector or $\mathbf{R}$ corresponding to its spectral radius $\rho$, it follows that \begin{align} \|\mathbf{x}_n\|_1&= \|\mathbf{R} \mathbf{x}_{n-1} + \mathbf{c} \|_1\\ &= \|\rho^{n} \mathbf{u} + \tilde{\mathbf{c}}_n \|_1 \; \left(\text{with }\tilde{\mathbf{c}}_n\triangleq\sum_{i=0}^{n-1} \mathbf{R}^i\mathbf{c}\right)\\ &= \sum_{i=1}^N|\rho^{n}u_i+\tilde{c}_{n,i}| \\ &=|\rho|^{n} \sum_{i=1}^N\left|u_i+\frac{\tilde{c}_{n,i}}{\rho^{n}}\right| \\ \end{align} which grows unbounded for $|\rho|>1$ as $n$ increases.

Answer 2

To complement the other answer, it is worth to realize that if the sequence $\{x_n\}$ converge to "something" that something is the fixed point, that is, an $x$ such that $x=Bx+c$. For the question of convergence to make sense it is required that there exists such a something (a fixed point), that is, the equation $(I-B)x=c$ must be solvable. Then you can subtract $x_{n+1}=Bx_n+c$ from $x=Bx+c$ to get $e_{n+1}=Be_n$, where $e_n:=x-x_n$ is the error associated with $x_n$. Therefore $e_n=B^ne_0$ and if the initial error $e_0$ corresponds to an eigenvector associated with an eigenvalue $\lambda$ of $B$ such that $|\lambda|\geq 1$ the iteration does not converge (either it "stagnates" if $|\lambda|=1$ or diverge if $|\lambda|>1$).