Please use this identifier to cite or link to this item:

Title: 利用計算矩陣特徵值的方法求多項式的根
Finding the Roots of a Polynomial by Computing the Eigenvalues of a Related Matrix
Authors: 賴信憲
Contributors: 王太林
Keywords: 傳統解多項式的方法
polynomial root-finding
symmetric tridiagonal matrix
QR algorithm
Date: 2000
Issue Date: 2016-04-18 16:31:43 (UTC+8)
Abstract: 我們將原本求只有實根的多項式問題轉換為利用QR方法求一個友矩陣(companion matrix)或是對稱三對角(symmetric tridiagonal matrix)的特徵值問題,在數值測試中顯示出利用傳統演算法去求多項式的根會比求轉換過後矩陣特徵值的方法較沒效率。
Given a polynomial pn(x) of degree n with real roots, we transform the problem of finding all roots of pn (x) into a problem of finding the eigenvalues of a companion matrix or of a symmetric tridiagonal matrix, which can be done with the QR algorithm. Numerical testing shows that finding the roots of a polynomial by standard algorithms is less efficient than by computing the eigenvalues of a related matrix.
Reference: [1] I. Bar-On and B. Codenotti, A fast and stable parallel QRalgorithm for symmetric tridiagonal matrices, Linear Algebra Appl. 220 (1995), 63-95.
[2] L. Brugnano and D. Trigiante, Polynomial Roots: The Ultimate Answer?, Linear Algebra Appl. 225 (1995), 207-219.
[3] B. N. Datta, Numerical Linear Algebra and Applications, Brooks/Cole, Pacific Grove, California, 1995.
[4] Edelman and H. Murakami, Polynomial roots from companion matrix eigenvalues, Math. Comp. 64 (1995), 763-776.
[5] S. Goedecker, Remark on algorithms to find roots of polynomials, SIAM J. Sci. Comput. 15 (1994), 1059-1063.
[6] IMSL User s manual, version 1.0 (1997), chapter 7.
[7] C. Moler, Cleve s corner: ROOTS-of polynomials, The Mathworks Newsletter. 5 (1991), 8-9.
[8] B. N. Parlett, The Symmetric Eigenvalue Problem, Prentice-Hall, Englewood Cliffs, N. J. 1980.
[9] V. Pan, Solving a polynomial equation: Some history and recent progress, SIAM Rev. 39 (1997), 187-220.
[10] G. Schmeisser, A real symmetric tridiagonal matrix with a given characteristic polynomial, Linear Algebra Appl. 193 (1993), 11-18.
[11] N. Trefethen and D. Bau, Numerical Linear Algebra, SIAM, Philadelphia, 1997.
Description: 碩士
Source URI:
Data Type: thesis
Appears in Collections:[應用數學系] 學位論文

Files in This Item:

File SizeFormat

All items in 學術集成 are protected by copyright, with all rights reserved.

社群 sharing