Jacobi rotation

In numerical linear algebra, a Jacobi rotation is a rotation, "Q"_"k"ℓ, of a 2-dimensional linear subspace of an "n-"dimensional inner product space, chosen to zero a symmetric pair of off-diagonal entries of an "n"×"n" real symmetric matrix, "A", when applied as a similarity transformation:

: $A\; mapsto\; Q\_\{kell\}^T\; A\; Q\_\{kell\}\; =\; A\text{'}\; .\; ,!$

:

It is the core operation in the Jacobi eigenvalue algorithm, which is numerically stable and well-suited to implementation on parallel processors.

It is important to note that only rows "k" and ℓ and columns "k" and ℓ of "A" will be affected, and that "A"′ will remain symmetric. Also, an explicit matrix for "Q"_"k"ℓ is rarely computed; instead, auxiliary values are computed and "A" is updated in an efficient and numerically stable way. However, for reference, we may write the matrix as

:

That is, "Q"_"k"ℓ is an identity matrix except for four entries, two on the diagonal ("q"_"kk" and "q"_ℓℓ, both equal to "c") and two symmetrically placed off the diagonal ("q"_"k"ℓ and "Q"_ℓ"k", equal to "s" and −"s", respectively). Here "c" = cos ϑ and "s" = sin ϑ for some angle ϑ; but to apply the rotation, the angle itself is not required. Using Kronecker delta notation, the matrix entries can be written

: $q\_\{ij\}\; =\; delta\_\{ij\}\; +\; (delta\_\{ik\}delta\_\{jk\}\; +\; delta\_\{iell\}delta\_\{jell\})(c-1)\; +\; (delta\_\{ik\}delta\_\{jell\}\; -\; delta\_\{iell\}delta\_\{jk\})s\; .\; ,!$

Suppose "h" is an index other than "k" or ℓ (which must themselves be distinct). Then the similarity update produces, algebraically,

: $a\text{'}\_\{hk\}\; =\; a\text{'}\_\{kh\}\; =\; c\; a\_\{hk\}\; -\; s\; a\_\{hell\}\; ,!$: $a\text{'}\_\{hell\}\; =\; a\text{'}\_\{ell\; h\}\; =\; c\; a\_\{hell\}\; +\; s\; a\_\{hk\}\; ,!$

: $a\text{'}\_\{kell\}\; =\; a\text{'}\_\{ell\; k\}\; =\; (c^2-s^2)a\_\{kell\}\; +\; sc\; (a\_\{kk\}\; -\; a\_\{ellell\})\; =\; 0\; ,!$

: $a\text{'}\_\{kk\}\; =\; c^2\; a\_\{kk\}\; +\; s^2\; a\_\{ellell\}\; -\; 2\; s\; c\; a\_\{kell\}\; ,!$: $a\text{'}\_\{ellell\}\; =\; c^2\; a\_\{kk\}\; +\; s^2\; a\_\{ellell\}\; +\; 2\; s\; c\; a\_\{kell\}\; ,!$

Numerically stable computation

To determine the quantities needed for the update, we must solve the off-diagonal equation for zero Harv|Golub|Van Loan|1996|loc=§8.4. This implies that

: $frac\{c^2-s^2\}\{sc\}\; =\; frac\{a\_\{ellell\}\; -\; a\_\{kk\{a\_\{kell\; .$

Set β to half this quantity,

:

If "a"_"k"ℓ is zero we can stop without performing an update, thus we never divide by zero. Let "t" be tan ϑ. Then with a few trigonometric identities we reduce the equation to

:

For stability we choose the solution

:

From this we may obtain "c" and "s" as

: $c\; =\; frac\{1\}\{sqrt\{t^2+1\; ,!$: $s\; =\; c\; t\; ,!$

Although we now could use the algebraic update equations given previously, it may be preferable to rewrite them. Let

: $ho=\; frac\{s\}\{1+c\}\; ,$

so that ρ = tan(ϑ/2). Then the revised update equations are

: $a\text{'}\_\{hk\}\; =\; a\text{'}\_\{kh\}\; =\; a\_\{hk\}\; -\; s\; (a\_\{hell\}\; +\; ho\; a\_\{hk\})\; ,!$: $a\text{'}\_\{hell\}\; =\; a\text{'}\_\{ell\; h\}\; =\; a\_\{hell\}\; +\; s\; (a\_\{hk\}\; -\; ho\; a\_\{hell\})\; ,!$

: $a\text{'}\_\{kell\}\; =\; a\text{'}\_\{ell\; k\}\; =\; 0\; ,!$

: $a\text{'}\_\{kk\}\; =\; a\_\{kk\}\; -\; t\; a\_\{k\; ell\}\; ,!$: $a\text{'}\_\{ellell\}\; =\; a\_\{ellell\}\; +\; t\; a\_\{k\; ell\}\; ,!$

As previously remarked, we need never explicitly compute the rotation angle ϑ. In fact, we can reproduce the symmetric update determined by "Q"_"k"ℓ by retaining only the three values "k", ℓ, and "t", with "t" set to zero for a null rotation.

See also

* Givens rotation

References

* citation
last1 = Golub
first1 = Gene H.
author1-link = Gene H. Golub
last2 = Van Loan
first2 = Charles F.
author2-link = Charles F. Van Loan
title = Matrix Computations
edition = 3rd
publisher = Johns Hopkins University Press
date = 1996
location = Baltimore
isbn = 978-0-8018-5414-9