期刊
SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS
卷 36, 期 3, 页码 942-973出版社
SIAM PUBLICATIONS
DOI: 10.1137/140983434
关键词
polynomial; root; rootfinding; companion matrix; eigenvalue; QR algorithm; rotators
资金
- Research Council KU Leuven [CREA-13-012, OT/11/055, CoE EF/05/006, F+/13/020]
- DFG [MA 5852/1-1]
- Fund for Scientific Research-Flanders (Belgium) project [G034212N]
- Interuniversity Attraction Poles Programme
- European Research Council under the European Union's Seventh Framework Programme (FP7)/ERC [291068]
- Belgian State, Science Policy Office, Belgian Network DYSCO (Dynamical Systems, Control, and Optimization)
A stable algorithm to compute the roots of polynomials is presented. The roots are found by computing the eigenvalues of the associated companion matrix by Francis's implicitly shifted QR algorithm. A companion matrix is an upper Hessenberg matrix that is unitary-plus-rankone, that is, it is the sum of a unitary matrix and a rank-one matrix. These properties are preserved by iterations of Francis's algorithm, and it is these properties that are exploited here. The matrix is represented as a product of 3n - 1 Givens rotators plus the rank-one part, so only O(n) storage space is required. In fact, the information about the rank-one part is also encoded in the rotators, so it is not necessary to store the rank-one part explicitly. Francis's algorithm implemented on this representation requires only O(n) flops per iteration and thus O(n(2)) flops overall. The algorithm is described, normwise backward stability is proved, and an extensive set of numerical experiments is presented. The algorithm is shown to be about as accurate as the (slow) Francis QR algorithm applied to the companion matrix without exploiting the structure. It is faster than other fast methods that have been proposed, and its accuracy is comparable or better.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据