12.4. The Solution to the Eigenvalue Problem

We will focus on two orthogonal iterative algorithms that are fairly simple, yet quickly find accurate eigenvalues. John Francis, introduced in History of the Eigenvalue Problem, developed these algorithms. The second algorithm, called the Francis algorithm, establishes the foundation for eigensystem solutions in modern software such as MATLAB. The eig function in MATLAB uses the QZ algorithm for dense matrices. QZ finds the generalized eigendecomposition, which is the factorization \(\mathbf{A\,X} = \mathbf{B\,X\,\Lambda}\). If matrix \(\bf{B}\) is an identity matrix, then we have the more common eigenvalue problem. Indeed, the QZ algorithm is an extension of the Francis algorithm. Although not as closely related, the Krylov algorithm used with sparse matrices, [1] is also derived from the Francis algorithm [WATKINS11].

Before describing Francis’s two algorithms, we will discuss the similarity requirement for diagonalization algorithms and introduce two foundational algorithms to eigendecomposition—the Hessenberg and Schur decompositions.

Footnote

Contents