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_^T A Q_ = A' . \,\!$

: $\begin & & & \cdots & & & * \\ & \ddots & & & & & \\ & & a_ & \cdots & a_ & & \\ \vdots & & \vdots & \ddots & \vdots & & \vdots \\ & & a_ & \cdots & a_ & & \\ & & & & & \ddots & \\ & & & \cdots & & & * \end \to \begin & & & \cdots & & & * \\ & \ddots & & & & & \\ & & a'_ & \cdots & 0 & & \\ \vdots & & \vdots & \ddots & \vdots & & \vdots \\ & & 0 & \cdots & a'_ & & \\ & & & & & \ddots & \\ & & & \cdots & & & * \end.$

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

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

: $Q_ = \begin 1 & & & & & & \\ & \ddots & & & & 0 & \\ & & c & \cdots & s & & \\ & & \vdots & \ddots & \vdots & & \\ & & -s & \cdots & c & & \\ & 0 & & & & \ddots & \\ & & & & & & 1 \end .$

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_ = \delta_ + (\delta_\delta_ + \delta_\delta_)(c-1) + (\delta_\delta_ - \delta_\delta_)s . \,\!$

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

: $a'_ = a'_ = c a_ - s a_ \,\!$
: $a'_ = a'_ = c a_ + s a_ \,\!$

: $a'_ = a'_ = (c^2-s^2)a_ + sc (a_ - a_) = 0 \,\!$

: $a'_ = c^2 a_ + s^2 a_ - 2 s c a_ \,\!$
: $a'_ = s^2 a_ + c^2 a_ + 2 s c a_. \,\!$

Numerically stable computation

To determine the quantities needed for the update, we must solve the off-diagonal equation for zero . This implies that

: $\frac = \frac .$

Set β to half of this quantity,

: $\beta = \frac .$

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

: $t^2 + 2\beta t - 1 = 0 . \,\!$

For stability we choose the solution

: $t = \frac .$

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

: $c = \frac \,\!$
: $s = c t \,\!$

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

: $\rho= \frac ,$

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

: $a'_ = a'_ = a_ - s (a_ + \rho a_) \,\!$
: $a'_ = a'_ = a_ + s (a_ - \rho a_) \,\!$

: $a'_ = a'_ = 0 \,\!$

: $a'_ = a_ - t a_ \,\!$
: $a'_ = a_ + t a_ \,\!$

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
* Householder transformation

References

*

{{DEFAULTSORT:Jacobi Rotation
Numerical linear algebra