     Next: Conditioning Up: Generalized Non-Hermitian Eigenproblems   Previous: Equivalences   Contents   Index

## Eigendecompositions

We discuss four eigendecompositions, or four pencils that are equivalent to and for which it is simpler to solve eigenproblems. This section is analogous to §2.5.4.

The first eigendecomposition, diagonal form, exists only when there are independent eigenvectors. The second one, Weierstrass form, generalizes diagonal form to all pencils where the characteristic polynomial is not identically 0. We can also describe the Weierstrass form as the generalization of the Jordan form matrices to pencils. The Weierstrass form, like the Jordan form, can be very ill-conditioned (indeed, it can change discontinuously), so for numerical purposes we typically use the third one, generalized Schur form, which is cheaper and more stable to compute. We briefly mention a fourth one, which we call the Weierstrass-Schur form, that is as stable as the Schur form but computes some of the detailed information about deflating subspaces provided by the Weierstrass form.

Define . If there are independent right eigenvectors , we define . is called a (right) eigenvector matrix of . Similarly let be a left eigenvector matrix. The equalities and for may also be written and . and may furthermore be chosen so that and are both diagonal, and . The factorization is called the diagonal form of . In this case we call diagonalizable.

If we take a subset of columns of and of (say = columns 2, 3, and 5 and ) then these columns span a pair of deflating subspaces of . If we take the corresponding submatrices and , then we can write the corresponding partial diagonal form as and . If the columns in and are replaced by different vectors spanning the same deflating subspaces, then we get a different partial eigendecomposition and , where is a by pencil whose eigenvalues are those of , though may not be diagonal. Similar procedures for producing partial eigendecompositions work for the other eigendecompositions discussed below.

If all the are distinct, then there are independent eigenvectors, and the diagonal form exists. This is the simplest and most common case. For example, if one picks and at random,'' the probability is 1 that the eigenvalues are distinct.

A diagonal form of the pencil in (2.3) in §2.5.4 does not exist, since it has just one independent eigenvector. Instead, we can compute its Weierstrass form, which is a decomposition where is a block-diagonal pencil, with one or more upper triangular diagonal blocks for each eigenvalue. When there are no infinite eigenvalues, this is identical to the Jordan form discussed in §2.5.4. When there are infinite eigenvalues, there are blocks quite similar to Jordan blocks with a single infinite eigenvalue and one right and left eigenvector. It can be shown that the Weierstrass form explicitly describes all possible deflating subspaces of as being spanned by certain subsets of the columns of and .

Unfortunately, the Weierstrass form is generally not suitable for numerical computation, for the same reason that the Jordan form is not suitable. See §2.5.4 for discussion.

So instead we use eigendecompositions of the form where and are unitary (or orthogonal) matrices and is triangular (or quasi-triangular). This is called the generalized Schur form of . When is complex, or real with all real or infinite eigenvalues, then is triangular with the eigenvalues of on its diagonal. When is real with complex eigenvalues and is real and orthogonal, then cannot be real and triangular. Instead, we allow 2 by 2 blocks with complex eigenvalues to appear on the diagonal of , which we call quasi-triangular form. For simplicity of presentation, we will consider the complex case, so that is triangular. Let be the eigenvalues in the order they appear on the diagonal of ; there is a (different) generalized Schur form for every order. The columns of and are called generalized Schur vectors. The generalized Schur form does not give explicit eigenvectors and bases for all deflating subspaces the way diagonal form and Weierstrass form do, but it can be computed quite stably. The leading columns of and of do span the right and left deflating subspaces for eigenvalues through , but all other eigenspaces require a computation. For example, right eigenvectors can be computed simply by solving a triangular system of equations taken from and multiplying by .

Finally, we consider the Weierstrass-Schur form. It is quite complicated, so we only summarize its properties here. Like the Schur form, it only uses unitary (orthogonal) transformation and so can be computed stably. Like the Weierstrass form, it explicitly shows what the sizes of the (Jordan) blocks are and gives explicit bases for many more invariant subspaces than the Schur form.

Many textbooks give explicit solutions for problems such as solving ordinary differential equations in terms of the Weierstrass form of . These methods are to be avoided numerically, because of the difficulty of computing the Weierstrass form. Nearly all these problems have alternative solutions in terms of the generalized Schur form, or in some cases the Weierstrass-Schur form.     Next: Conditioning Up: Generalized Non-Hermitian Eigenproblems   Previous: Equivalences   Contents   Index
Susan Blackford 2000-11-20