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

  • $\begingroup$ 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. $\endgroup$ – Patrick Da Silva May 27 '11 at 5:23
  • $\begingroup$ 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/… $\endgroup$ – leonbloy May 27 '11 at 14:45
  • $\begingroup$ 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. $\endgroup$ – Did May 27 '11 at 17:59
  • $\begingroup$ @Didier: you are right. I was assuming $\mathbf{x}[0]$ is, say, random, so it's not aligned with any eigenvector w.h.p. $\endgroup$ – ACAC May 27 '11 at 23:08

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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