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)?
convergence rate of matrix product
0
$\begingroup$
linear-algebra
convergence
dynamical-systems
-
0It 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. – 2011-05-27
-
0The last sentence might seem to imply that multiple eigenvalues is equivalent to non-diagonalizable : it's necessary but not sufficient condition http://mathoverflow.net/questions/23478/examples-of-common-false-beliefs-in-mathematics/27218#27218 – 2011-05-27
-
0The 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. – 2011-05-27
-
0@Didier: you are right. I was assuming $\mathbf{x}[0]$ is, say, random, so it's not aligned with any eigenvector w.h.p. – 2011-05-27
1 Answers
2
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$.