簡易檢索 / 詳目顯示
| 研究生： |
賴信憲 |
|---|---|
| 論文名稱： |
利用計算矩陣特徵值的方法求多項式的根 Finding the Roots of a Polynomial by Computing the Eigenvalues of a Related Matrix |
| 指導教授： | 王太林 |
| 學位類別： |
碩士
Master |
| 系所名稱： |
理學院 - 應用數學系 Department of Mathematical Sciences |
| 論文出版年： | 2000 |
| 畢業學年度： | 88 |
| 語文別： | 英文 |
| 論文頁數： | 23 |
| 中文關鍵詞： | 傳統解多項式的方法 、三對角矩陣 、QR演算法 |
| 外文關鍵詞： | polynomial root-finding, symmetric tridiagonal matrix, QR algorithm |
| 相關次數： | 點閱：338 下載：36 |
| 分享至: |
| 查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報 |
我們將原本求只有實根的多項式問題轉換為利用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. Introduction
2. Basic Principles
2.1 Conditioning of a Problem
2.2 Computing the Eigenvalues of a Matrix
3. Numerical Methods
3.1 LG Method, JT Method and JTC Method
3.2 C-HQR Method
3.3 E-TQR Method
4. Numerical Examples and Results
4.1 Examples
4.2 Comparision of the Algorithms
5. Conclusions
References
Appendix
Appendix A: Orthogonal Polynomials
Appendix B: Programs
[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.