Chapter 7
Eigensystems
AbstractWe present here two methods for solving directly eigenvalueproblems using sim-
ilarity transformations. One is the familiar Jacobi rotation method while the second method
is based on transforming the matrix to tridiagonal form using Householder’s algorithm. We
discuss also so-called power methods and conclude with a discussion of iterative algorithms.
These are particularly interesting for eigenvalue problems of large dimnesionality.
7.1 Introduction
Together with linear equations and least squares, the thirdmajor problem in matrix com-
putations deals with the algebraic eigenvalue problem. Here we limit our attention to the
symmetric case. We focus in particular on two similarity transformations, the Jacobi method,
the famous QR algoritm with Householder’s method for obtaining a triangular matrix and
Francis’ algorithm for the final eigenvalues. Our presentation follows closely that of Golub
and Van Loan, see Ref. [28].
7.2 Eigenvalue problems
Let us consider the matrixAof dimension n. The eigenvalues ofAare defined through the
matrix equation
Ax(ν)=λ(ν)x(ν), (7.1)
whereλ(ν)are the eigenvalues andx(ν)the corresponding eigenvectors. Unless otherwise
stated, when we use the wording eigenvector we mean the righteigenvector. The left eigen-
vector is defined as
x(ν)LA=λ(ν)x(ν)L
The above right eigenvector problem is equivalent to a set ofnequations withnunknownsxi
a 11 x 1 +a 12 x 2 +···+a 1 nxn=λx 1
a 21 x 1 +a 22 x 2 +···+a 2 nxn=λx 2
... ...
an 1 x 1 +an 2 x 2 +···+annxn=λxn.We can rewrite Eq. (7.1) as
213