Convergence of iterative method and spectral radius

[IniquiTrance]

Homework Statement

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.

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!

 

[STEMucator]

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.

 

[IniquiTrance]

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.

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.

 

[STEMucator]

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.

 

[pasmith]

Homework Statement

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.

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$.

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!

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.

 

[IniquiTrance]

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.

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"?

 

[pasmith]

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"?

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$.