# Convergence of iterative method and spectral radius

1. Aug 12, 2014

### IniquiTrance

1. The problem statement, all variables and given/known data
Show that if given $\mathbf{x}_0$, and a matrix $R$ with spectral radius $\rho(R)\geq 1$, there exist iterations of the form,
$$\mathbf{x}_{n+1}=R\mathbf{x}_0+\mathbf{c}$$
which do not converge.

3. The attempt at a solution

Let $\mathbf{x}_0$ be given, and let $(\lambda_0,\mathbf{v}_0)$ be the eigenpair corresponding to $\rho(R)$. Then choose $\mathbf{c}=\mathbf{v}_0$ so that,
$$\mathbf{x}_n = R^n\mathbf{x}_0+\left(\sum_{i = 0}^{n - 1}\lambda_0^i\right)\mathbf{v}_0$$

I'm not sure how to proceed from here. Thanks!

2. Aug 12, 2014

### Zondrina

The supremum of the absolute values in the spectrum of $R$ is some $\rho(R) \geq 1$.

I think you need to show that $(1 + \lambda_0 + \lambda_0^2 + \lambda_0^3 + \space...)$ somehow diverges. So the iteration would diverge.

3. Aug 12, 2014

### IniquiTrance

Right, that sum diverges, but how do I show that $\Vert \mathbf{x}_n\Vert$ diverges as $n\rightarrow\infty$? I can only show the norm is not greater than $\Vert R^n\mathbf{x}_0\Vert + \infty$ with the triangle inequality.

4. Aug 12, 2014

### Zondrina

Can you show that:

$\displaystyle \lim_{n → ∞} R^n = 0 \iff \rho(R) < 1$?

Since $\rho(R) ≥ 1$, it would be clear as to why $||R^n||$ is not bounded.

5. Aug 13, 2014

### pasmith

As it stands the statement is false, since $\mathbf{x}_{n+1} = R\mathbf{x}_0 + \mathbf{c}$ is a constant map. Perhaps the $\mathbf{x}_0$ is supposed to be an $\mathbf{x}_n$.

You need only consider the case where $\mathbf{x}_0 = z_0\mathbf{v}_0$ and $\mathbf{c} = c\mathbf{v}_0$. You are justified in making this assumption since you're asked to show that divergent iterations exist, so you only need to find one such iteration.

Thus your problem is to show that the complex sequence $$z_{n+1} = \lambda z_n + c$$ diverges if $|\lambda| > 1$. Fortunately this linear recurrence can be solved analytically to obtain $z_n$ in closed form.

6. Aug 13, 2014

### IniquiTrance

Yep, thank you for noticing my error, I meant to say,

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

I'm just still unclear why I am allowed to assume $\mathbf{x}_0$ is a scalar multiple of the eigenvector corresponding to the spectral radius. Doesn't the question read, "If I am provided with some $\mathbf{x}_0$ I can choose a $\mathbf{c}$ that will result in a nonconvergent sequence"?

7. Aug 13, 2014

### pasmith

You're right, I missed that. You are stuck with the given $\mathbf{x}_0$.

However, I can still achieve my goal (reducing the problem to finding a sequence of scalars $z_n$ with $|z_n| \to \infty$) by suitable choice of $\mathbf{c}$. I'm stuck with $\mathbf{x}_0$, so it may be that the best I can do is $\mathbf{x}_n = \mathbf{x}_0 + z_n\mathbf{v}_0$. But that would suffice, since
$$\|\mathbf{x}_n\| = \|\mathbf{x}_0 + z_n \mathbf{v}_0\| = |z_n|\left\| \frac{\mathbf{x}_0}{z_n} + \mathbf{v}_0\right\| \to \infty$$
since by definition $\mathbf{v}_0 \neq 0$.