學術產出-學位論文
文章檢視/開啟
書目匯出
-
題名 利用計算矩陣特徵值的方法求多項式的根
Finding the Roots of a Polynomial by Computing the Eigenvalues of a Related Matrix作者 賴信憲 貢獻者 王太林
賴信憲關鍵詞 傳統解多項式的方法
三對角矩陣
QR演算法
polynomial root-finding
symmetric tridiagonal matrix
QR algorithm日期 2000 上傳時間 18-四月-2016 16:31:43 (UTC+8) 摘要 我們將原本求只有實根的多項式問題轉換為利用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.參考文獻 [1] I. Bar-On and B. Codenotti, A fast and stable parallel QRalgorithm for symmetric tridiagonal matrices, Linear Algebra Appl. 220 (1995), 63-95.\r\n[2] L. Brugnano and D. Trigiante, Polynomial Roots: The Ultimate Answer?, Linear Algebra Appl. 225 (1995), 207-219.\r\n[3] B. N. Datta, Numerical Linear Algebra and Applications, Brooks/Cole, Pacific Grove, California, 1995.\r\n[4] Edelman and H. Murakami, Polynomial roots from companion matrix eigenvalues, Math. Comp. 64 (1995), 763-776.\r\n[5] S. Goedecker, Remark on algorithms to find roots of polynomials, SIAM J. Sci. Comput. 15 (1994), 1059-1063.\r\n[6] IMSL User s manual, version 1.0 (1997), chapter 7.\r\n[7] C. Moler, Cleve s corner: ROOTS-of polynomials, The Mathworks Newsletter. 5 (1991), 8-9.\r\n[8] B. N. Parlett, The Symmetric Eigenvalue Problem, Prentice-Hall, Englewood Cliffs, N. J. 1980.\r\n[9] V. Pan, Solving a polynomial equation: Some history and recent progress, SIAM Rev. 39 (1997), 187-220.\r\n[10] G. Schmeisser, A real symmetric tridiagonal matrix with a given characteristic polynomial, Linear Algebra Appl. 193 (1993), 11-18.\r\n[11] N. Trefethen and D. Bau, Numerical Linear Algebra, SIAM, Philadelphia, 1997. 描述 碩士
國立政治大學
應用數學系
86751004資料來源 http://thesis.lib.nccu.edu.tw/record/#A2002001738 資料類型 thesis dc.contributor.advisor 王太林 zh_TW dc.contributor.author (作者) 賴信憲 zh_TW dc.creator (作者) 賴信憲 zh_TW dc.date (日期) 2000 en_US dc.date.accessioned 18-四月-2016 16:31:43 (UTC+8) - dc.date.available 18-四月-2016 16:31:43 (UTC+8) - dc.date.issued (上傳時間) 18-四月-2016 16:31:43 (UTC+8) - dc.identifier (其他 識別碼) A2002001738 en_US dc.identifier.uri (URI) https://ah.lib.nccu.edu.tw/item?item_id=95153 - dc.description (描述) 碩士 zh_TW dc.description (描述) 國立政治大學 zh_TW dc.description (描述) 應用數學系 zh_TW dc.description (描述) 86751004 zh_TW dc.description.abstract (摘要) 我們將原本求只有實根的多項式問題轉換為利用QR方法求一個友矩陣(companion matrix)或是對稱三對角(symmetric tridiagonal matrix)的特徵值問題，在數值測試中顯示出利用傳統演算法去求多項式的根會比求轉換過後矩陣特徵值的方法較沒效率。 zh_TW dc.description.abstract (摘要) 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. en_US dc.description.tableofcontents 封面頁\r\n證明書\r\n致謝詞\r\n論文摘要\r\n目錄\r\n1. Introduction\r\n2. Basic Principles\r\n2.1 Conditioning of a Problem\r\n2.2 Computing the Eigenvalues of a Matrix\r\n3. Numerical Methods\r\n3.1 LG Method, JT Method and JTC Method\r\n3.2 C-HQR Method\r\n3.3 E-TQR Method\r\n4. Numerical Examples and Results\r\n4.1 Examples\r\n4.2 Comparision of the Algorithms\r\n5. Conclusions\r\nReferences\r\nAppendix\r\nAppendix A: Orthogonal Polynomials\r\nAppendix B: Programs zh_TW dc.source.uri (資料來源) http://thesis.lib.nccu.edu.tw/record/#A2002001738 en_US dc.subject (關鍵詞) 傳統解多項式的方法 zh_TW dc.subject (關鍵詞) 三對角矩陣 zh_TW dc.subject (關鍵詞) QR演算法 zh_TW dc.subject (關鍵詞) polynomial root-finding en_US dc.subject (關鍵詞) symmetric tridiagonal matrix en_US dc.subject (關鍵詞) QR algorithm en_US dc.title (題名) 利用計算矩陣特徵值的方法求多項式的根 zh_TW dc.title (題名) Finding the Roots of a Polynomial by Computing the Eigenvalues of a Related Matrix en_US dc.type (資料類型) thesis en_US dc.relation.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.\r\n[2] L. Brugnano and D. Trigiante, Polynomial Roots: The Ultimate Answer?, Linear Algebra Appl. 225 (1995), 207-219.\r\n[3] B. N. Datta, Numerical Linear Algebra and Applications, Brooks/Cole, Pacific Grove, California, 1995.\r\n[4] Edelman and H. Murakami, Polynomial roots from companion matrix eigenvalues, Math. Comp. 64 (1995), 763-776.\r\n[5] S. Goedecker, Remark on algorithms to find roots of polynomials, SIAM J. Sci. Comput. 15 (1994), 1059-1063.\r\n[6] IMSL User s manual, version 1.0 (1997), chapter 7.\r\n[7] C. Moler, Cleve s corner: ROOTS-of polynomials, The Mathworks Newsletter. 5 (1991), 8-9.\r\n[8] B. N. Parlett, The Symmetric Eigenvalue Problem, Prentice-Hall, Englewood Cliffs, N. J. 1980.\r\n[9] V. Pan, Solving a polynomial equation: Some history and recent progress, SIAM Rev. 39 (1997), 187-220.\r\n[10] G. Schmeisser, A real symmetric tridiagonal matrix with a given characteristic polynomial, Linear Algebra Appl. 193 (1993), 11-18.\r\n[11] N. Trefethen and D. Bau, Numerical Linear Algebra, SIAM, Philadelphia, 1997. zh_TW
