There are two preprocessing
steps one may perform
on a matrix A in order
to make its eigenproblem easier. The first is permutation, or
reordering the rows and columns to make A more nearly upper triangular
(closer to Schur form): , where P is a permutation matrix.
If
is permutable to upper triangular form (or close to it), then
no floating-point operations (or very few) are needed to reduce it to
Schur form.
The second is scaling by a diagonal matrix D to make the rows and
columns of
more nearly equal in norm:
. Scaling
can make the matrix norm smaller with respect to the eigenvalues, and so
possibly reduce the inaccuracy contributed by roundoff
[][Chap. II/11]wilkinson3. We refer to these two operations as
.
Balancing is performed by driver xGEEVX, which calls computational routine xGEBAL. The user may tell xGEEVX to optionally permute, scale, do both, or do neither; this is specified by input parameter BALANC. Permuting has no effect on the condition numbers or their interpretation as described in previous subsections. Scaling, however, does change their interpretation, as we now describe.
The output parameters of xGEEVX - SCALE (real array of length N),
ILO (integer), IHI (integer) and ABNRM (real) - describe
the result of
balancing a matrix A into , where N is the dimension of A.
The matrix
is block upper triangular, with at most three blocks:
from 1 to ILO - 1, from ILO to IHI, and from IHI + 1 to N.
The first and last blocks are upper triangular, and so already in Schur
form. These are not scaled; only the block from ILO to IHI is scaled.
Details of the scaling and permutation are described in SCALE (see the
specification of xGEEVX or xGEBAL for details) . The one-norm of
is returned in ABNRM.
The condition numbers
described in earlier subsections are computed for
the balanced matrix , and so some interpretation is needed to
apply them to the eigenvalues and eigenvectors of the original matrix A.
To use the bounds for eigenvalues in Tables 4.5 and
4.6,
we must replace
and
by
. To use the
bounds for eigenvectors, we also need to take into account that bounds
on rotations of eigenvectors are for the eigenvectors
of
, which are related to the eigenvectors x of A by
, or
. One coarse but simple way to do this is
as follows: let
be the bound on rotations of
from
Table 4.5 or Table 4.6
and let
be the desired bound on rotation of x. Let
be the condition number of D. Then
The numerical example in subsection 4.8 does no scaling, just permutation.