In numerical linear algebra, a Jacobi rotation is a rotation, Qkℓ, 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: It is the core operation in the Jacobi eigenvalue algorithm, which is numerically stable and well-suited to implementation on parallel processors [citation needed].
Also, an explicit matrix for Qkℓ 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, Qkℓ is an identity matrix except for four entries, two on the diagonal (qkk and qℓℓ, both equal to c) and two symmetrically placed off the diagonal (qkℓ and qℓk, equal to s and −s, respectively), where c = cos θ and s = sin θ for some angle θ.
This is the same matrix as defines a Givens rotation, but for Jacobi rotations the choice of angle is different (very roughly half as large), since the rotation is applied on both sides simultaneously.
It is not necessary to calculate the angle itself to apply the rotation.
Using Kronecker delta notation, the matrix entries can be written: Suppose h is an index other than k or ℓ (which must themselves be distinct).
Then the similarity update produces, algebraically: To determine the quantities needed for the update, we must solve the off-diagonal equation for zero (Golub & Van Loan 1996, §8.4).
This implies that: Set β to twice this quantity:
Then with a few trigonometric identities we reduce the equation to: For stability we choose the solution with
From this we may obtain c and s as: Although we now could use the algebraic update equations given previously, it may be preferable[how?]
Then the revised update equations are: As previously remarked, we need never explicitly compute the rotation angle
In fact, we can reproduce the symmetric update determined by Qkℓ by retaining only the three values k, ℓ, and t, with t set to zero for a null rotation.
Some applications may require multiple zero entries in a similarity matrix, possibly in the form of a tridiagonal matrix.
[1] Since Jacobian rotations may remove zeros from other cells that were previously zeroed, it is usually not possible to achieve tridiagonalization by simply zeroing each off-tridiagonal cell individually in a medium to large matrix.
However, if Jacobian rotations are repeatedly performed on the above-tridiagonal cell with the highest absolute value using an adjacent cell just below or to the left to rotate on, then all of the off-triangular cells are expected to converge on zero after several iterations.
, the off-tridiagonal cells [1,3], [1,4], [1,5], [2,4], [2,5], and [3,5], must continue to be iteratively zeroed until the maximum absolute value of those cells is below an acceptable convergence threshold.
The cells below the diagonal will be zeroed automatically, due to the symmetric nature of the matrix.
The first Jacobian rotation will be on the off-tridiagonal cell with the highest absolute value, which by inspection is [1,4] with a value of 11.
To make this entry zero, the condition specified in the above equations must be met for the cell coordinates to be zeroed (
, produces a matrix with cells [1,4] and [4,1] zeroed, as expected.
and T1 is also symmetric, confirming that the Jacobian rotation was performed correctly.
Assuming this convergence criteria is acceptably low for the application it is being performed for, the similar triangularized
Jacobian rotation can be used to extract the eigenvalues in a similar manner as the triangulation example above, but by zeroing all of the cells above the diagonal, instead of the tridiagonal, and performing the Jacobian rotation directly in the cells to be zeroed, instead of an adjacent cell.
The first Jacobian rotation will be on the off-diagonal cell with the highest absolute value, which by inspection is [1,4] with a value of 11, and the rotation cell will also be [1,4],
The rotation angle is the result of a quadratic solution, but it can be seen in the equation that if the matrix is symmetric, then a real solution is assured.
, produces a matrix with cells [1,4] and [4,1] zeroed, as expected.
and T1 is also symmetric, confirming that the Jacobian rotation was performed correctly.
will select cell [3,4] which contains the highest absolute value, 8.5794421, of all the cells to be zeroed.. After 25 iterations of zeroing the cell with the maximum absolute value using Jacobian rotations on the cell just below it, the maximum absolute value of all off-diagonal cells is 9.0233029E-11.
Assuming this convergence criteria is acceptably low for the application it is being performed for, the similar diagonalized
The eigenvalues are now displayed across the diagonal, and may be directly extracted for use elsewhere.