Jacobi Eigenvalue Algorithm - Convergence

Convergence

If is a pivot element, then by definition for . Since S has exactly 2 N := n ( n - 1) off-diag elements, we have or . This implies or, i.e. the sequence of Jacobi rotations converges at least linearly by a factor to a diagonal matrix.

A number of N Jacobi rotations is called a sweep; let denote the result. The previous estimate yields

,

i.e. the sequence of sweeps converges at least linearly with a factor ≈ .

However the following result of Schönhage yields locally quadratic convergence. To this end let S have m distinct eigenvalues with multiplicities and let d > 0 be the smallest distance of two different eigenvalues. Let us call a number of

Jacobi rotations a Schönhage-sweep. If denotes the result then

.

Thus convergence becomes quadratic as soon as .