Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 0 down vote favorite

Suppose you have a linear system like this:
$$\mathbf{x}[k+1] = \mathbf{D} \mathbf{x}[k]$$
where matrix $\mathbf{D}$ is diagonal. Assume its diagonal entries are real, greater than zero and less than one, but not necessarily distinct. Is it still technically correct to say that the convergence rate is determined by the largest value in $\mathbf{D}$? And what about non-diagonalizable matrices (when eigenvalues have multiplicity greater than one)?

share|improve this question
It is technically correct to say that the convergence rate of $x[k]$ will be determined by the greatest eigenvalue of $D$ when $D$ is diagonal. I'm still suspicious about non-diagonal matrices. – Patrick Da Silva May 27 '11 at 5:23
The last sentence might seem to imply that multiple eigenvalues is equivalent to non-diagonalizable : it's necessary but not sufficient condition mathoverflow.net/questions/23478/… – leonbloy May 27 '11 at 14:45
The convergence rate depends on the starting point $x[0]$. If the component of $x[0]$ in the eigenspace of the largest eigenvalue is zero, one should look at the second largest eigenvalue, and so on. – Did May 27 '11 at 17:59
@Didier: you are right. I was assuming $\mathbf{x}[0]$ is, say, random, so it's not aligned with any eigenvector w.h.p. – Bob May 27 '11 at 23:08

1 Answer

up vote 1 down vote accepted

The diagonal case is trivial because the system decouples into one-dimensional ones.

If the matrix is not diagonalizable, and the largest block in the Jordan normal form for the largest eigenvalue $\lambda$ is $m \times m$, then you can have $\|x[n]\| \sim C n^{m-1} \lambda^n$ as $n \to \infty$. This is because if $B$ is a matrix with $(B-\lambda I)^m = 0$ and $(B - \lambda I)^{m-1} \ne 0$, $B^n = (B-\lambda I+ \lambda I)^n = \sum_{k=0}^{m-1} {n \choose k} \lambda^{n-k} (B-\lambda I)^k$, and ${n \choose k}$ is a polynomial in $n$ of degree $k$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.