Implicit double shift QR-algorithm for companion matrices
Implicit double shift QR-algorithm for companion matrices
复制标题
用于伴随矩阵的隐式双移 QR 算法
作者：
M. Barel;R. Vandebril;P. Dooren;K. Frederix
本文将提出一种计算伴随矩阵和同伴矩阵特征值的隐式（双）移位QR方法。伴随矩阵和同伴矩阵是Hessenberg矩阵，可以分解为酉矩阵和秩1矩阵的和。在QR方法的一个步骤下，Hessenberg，酉以及秩1结构被保留。这使得这些矩阵适合于快速QR方法的设计。已经存在用于执行QR步骤的若干技术。这些方法的实现高度依赖于所使用的表示。不幸的是，对于大多数的方法压缩是需要的，因为一个是不能保持所有三个，酉，海森伯格和秩1结构。在这份手稿中，隐式算法将被设计用于执行一个步骤的QR-方法的伴侣或同伴矩阵的基础上组成的吉文斯变换的新表示。此外，不需要压缩，因为所涉及的矩阵的特定表示被保持。最后，还提出了一个双移位版本的隐式方法。
In this paper an implicit (double) shifted QR-method for computing the eigenvalues of companion and fellow matrices will be presented. Companion and fellow matrices are Hessenberg matrices, that can be decomposed into the sum of a unitary and a rank 1 matrix. The Hessenberg, the unitary as well as the rank 1 structures are preserved under a step of the QR-method. This makes these matrices suitable for the design of a fast QR-method. Several techniques already exist for performing a QR-step. The implementation of these methods is highly dependent on the representation used. Unfortunately for most of the methods compression is needed since one is not able to maintain all three, unitary, Hessenberg and rank 1 structures. In this manuscript an implicit algorithm will be designed for performing a step of the QR-method on the companion or fellow matrix based on a new representation consisting of Givens transformations. Moreover, no compression is needed as the specific representation of the involved matrices is maintained. Finally, also a double shift version of the implicit method is presented.