Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Let $H$ be an $n\times n$ Hermitian matrix. The Jacobi method is an iterative method for finding the spectrum of $H$. It is described in every book on numerical linear algebra.

Principle: At step $k$, the matrix has become $H^k$. You choose a pair $(i,j)$ with $1\le i,j\le n$ and $i\ne j $. Then you conjugate $H^k$ by a rotation in the plane of coordinates $(x_i,x_j)$, in such a way that the new matrix $H^{k+1}$ has a zero entry in position $(i,j)$. Of course, after several other steps, this entry will be again nonzero.

Let us recall that the Frobenius norm is $\|M\|:=\sqrt{\sum_{i,j}|m_{ij}|^2}$. The norm $e_k$ of the off-diagonal part of $H^k$ is called the error. It is non-increasing. This question is about the order at which $e_k\rightarrow0$.

There are at least three strategies for the choice of $(i,j)$ at each step, and I shall concentrate on the optimal one, in which we choose the entry that has the largest modulus among the off-diagonal ones. Every book presents and proves the first-order convergence, thanks to the inequality $$e_{k+1}\le\rho e_k, \qquad \rho:=\sqrt{1-\frac{2}{n(n-1)}}.$$ When the eigenvalues of $H$ are simple, advanced books (see [1,2]) give also a quadratic convergence result. However, it is not really quadratic, because it is based upon an inequality of the form $$e_{k+N}\le c\cdot e_k^2,\qquad N:=\frac{n(n-1)}{2}$$ where it requires $N$ step to square the error. We should better call this a result of convergence of order $2^{1/N}$.

Question. Of course the result mentionned above gives only an upper bound of the order of the method. If $n=3$, I can prove that the exact order is the root $\omega>1$ of the polynomial $X^3-X-1$. What is the exact order for larger sizes ? Even an upper bound of the order, better than $2^{1/N}$, is welcome.

[1] J. H. Wilkinson. The algebraic eigenvalue problem. Oxford University Press, 1965.

[2] D. Serre. Matrices; Theory and applications. GTM 216, Springer-Verlag, 2000.

share|improve this question
add comment

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.