Publisher's Synopsis
"For the past 50 years the workhorse algorithm for solving eigenvalue problems has been Francis's implictly shifted QR algorithm. We present here a new formulation of Francis's algorithm that operates on the QR factors of a matrix A rather than A itself. This is not in any existing book. A popular way to compute the roots of a polynomial is to form the companion matrix and compute its eigenvalues (which are exactly the roots of the polynomial). This is what Matlab's roots command does. Our new formulation leads to a better algorithm for solving the companion eigenvalue problem (which is unitary-plus-rank-one). Our algorithm is faster than all of the competing algorithms. We can prove it is backward stable, and it is stable in a stronger sense than the algorithm that Matlab uses. Thus our algorithm is faster and more accurate than Matlab's. In the final chapter we present a generalization of Francis's algorithm that we published (in a SI
