A New Algorithm Solving Eigenvalue Problem Of Matrices

This thesis derives three algorithms for solving the eigenvalue problem of matrices on the basis of a divide-and-conquer Algorithm. The article includes three parts mainly:The first part presents a new divide-and-conquer Algorithm for the eigenvalue problem of symmetric tridiagonal matrices. The new algorithm bases on bisection and secant iteration, which is different Cuppen's method and Newton iteration. The results of theoretical analysis and numerical testing show that convergent rant of our algorithm is obviously faster that of the classical algorithm.The second part applies divide-and-conquer algorithm to calculate the eigenvalues of symmetrical matrices. The eigenvalues problem of symmetrical matrices Ax = x can be transformed the eigenvalues problem of symmetric tridiagonal matrices Tx = ux through Householder transform. We divide T into T1, T2 and apply symmetrical QR algorithm to computethe eigenvalues of T1, T2. At last we veneer these eigenvalues.The third part extends the algorithm to solve the eigenvalue problem of nonsymmetrical matrices. Considering the question Ax = fa (A is a nonsymmetrical matrix) A can be transformed upper Hessenberg matrix by means of Householder transform. Transformed A is divided into A1 A2 then. They utilize QR algorithm to solve their eigenvalues. The new algorithm bases on Langurre iteration. Theoretical analysis and numerical results show that the algorithm is fast. Above all, the algorithm is well suitable to parallel implementation.We have given theoretical analysis on each algorithm and done many numerical experiments and comparisons. Theoretical results and numerical experiments have confirm that the three new algorithms have better practical performance significantly less computational cost and less CPU time.