子空间加速方法的研究
|
摘要
子空间方法是计算大型稀疏对称矩阵特征值问题的有效数值方法。初始迭代向量的选取和算法的收敛率直接影响到子空间方法的计算效率,很多加速的子空间方法都是从这两个方面考虑的。为了加速子空间方法的收敛,本文在总结已有的加速方法的基础上提出了以下几种加速策略:
首先,为了选取最佳迭代向量数值使得总运算量最小,本文详细分析了影响算法总运算量的一些参变量,在此基础上,提出了根据这些参变量选取最佳迭代向量数的新方法。
其次,为了选取好的初始迭代向量,本文根据圆盘定理提出了新的选取策略。
接下来,针对Qian和Dhatt与Lam和Bertolini分别提出的重复逆迭代的加速思想,提出了改进方法。针对Lam和Bertolini根据收敛率确定逆迭代的迭代向量,本文为了改进这种方法带来的误差,提出根据相邻特征值选取迭代向量的策略,提出了一种新的确定最大迭代步数的方法。根据不同实际问题,利用上述思想给出了两种具体的算法。
最后,根据超松弛加速策略所体现的思想提出了新的改进方法,克服了F.A. Akl和K.J.Bathe加速子空间方法中计算松弛因子的困难。
此外,在各章的后面对各种改进的算法都做了具体的数值实验。
Subspace iteration method is one of efficient numerical methods for solution of large sparse symmetric eigenproblems. The efficient of subspace iteration method is dependent on the selection of initial vectors and convergence rate. Many accelerated subspace iteration methods is based on these two aspects. For obtain a higher convergence rate, the paper presents following accelerated-strategies based on summary of the existing accelerated methods.
Firstly, for selecting the best number of iterative vectors which cause the total operation to be smallest, the paper analysis the parameters influence the total operation of algorithm. According to these parameters, a new method is proposed. Secondly, in order to select best initial vectors, a new selection method is proposed based on the circle theorem.
Then, using the accelerated-strategy of extra inverse iteration which is presented by Qian and Lam, the improvement method is proposed. Lam and Bertolini select vectors that need to be extra inverse iteration by convergence rate. For reduction the error of this method, the new method using consistent eigenvalues is proposed. And one new method for determination biggest iteration step is introduced. Two algorithms are presented for different problems.
Finally, using the accelerated-strategy of over-relaxation method, a method which improves the difficulty of computing over-relaxation factors is proposed. And the numerical examples of different algorithms are presented at the end of every chapter.
首先,为了选取最佳迭代向量数值使得总运算量最小,本文详细分析了影响算法总运算量的一些参变量,在此基础上,提出了根据这些参变量选取最佳迭代向量数的新方法。
其次,为了选取好的初始迭代向量,本文根据圆盘定理提出了新的选取策略。
接下来,针对Qian和Dhatt与Lam和Bertolini分别提出的重复逆迭代的加速思想,提出了改进方法。针对Lam和Bertolini根据收敛率确定逆迭代的迭代向量,本文为了改进这种方法带来的误差,提出根据相邻特征值选取迭代向量的策略,提出了一种新的确定最大迭代步数的方法。根据不同实际问题,利用上述思想给出了两种具体的算法。
最后,根据超松弛加速策略所体现的思想提出了新的改进方法,克服了F.A. Akl和K.J.Bathe加速子空间方法中计算松弛因子的困难。
此外,在各章的后面对各种改进的算法都做了具体的数值实验。
Subspace iteration method is one of efficient numerical methods for solution of large sparse symmetric eigenproblems. The efficient of subspace iteration method is dependent on the selection of initial vectors and convergence rate. Many accelerated subspace iteration methods is based on these two aspects. For obtain a higher convergence rate, the paper presents following accelerated-strategies based on summary of the existing accelerated methods.
Firstly, for selecting the best number of iterative vectors which cause the total operation to be smallest, the paper analysis the parameters influence the total operation of algorithm. According to these parameters, a new method is proposed. Secondly, in order to select best initial vectors, a new selection method is proposed based on the circle theorem.
Then, using the accelerated-strategy of extra inverse iteration which is presented by Qian and Lam, the improvement method is proposed. Lam and Bertolini select vectors that need to be extra inverse iteration by convergence rate. For reduction the error of this method, the new method using consistent eigenvalues is proposed. And one new method for determination biggest iteration step is introduced. Two algorithms are presented for different problems.
Finally, using the accelerated-strategy of over-relaxation method, a method which improves the difficulty of computing over-relaxation factors is proposed. And the numerical examples of different algorithms are presented at the end of every chapter.
引文
[1] Bathe, K.J. and Ramaswamy, S. An accelerated subspace iteration method. Comput Meth Appl Mech Eng. v23(1980). pp.313-331.
[2] Bathe, K.J. and Wilson, E.L. Large eigenvalue problems in dynamic analysis [J]. J Eng Mech Div ASCE. v98(1972). pp.1471-1485.
[3] Bathe KJ. Solution methods for large generalized eigenvalue problems in structural engineering. UC SESM Report 71-20, Department of Civil Engineering, University of California, Berkeley, CA, November, 1971.
[4] Wilson, E.L. and Itoh, T. An eigensolution strategy for large systems [J]. Computer & Structures. v16(1983). pp.259-265.
[5]曹志浩.矩阵特征值问题[M].上海:上海科学技术出版社,1980
[6]曹志浩,张玉德和李瑞遐.矩阵计算和方程求根[M].高等教育出版社,1979.
[7] Jung, H.J. and Lee, I.W. An Improved subspace iteration method with shift for structures with multiple natural frequencies [J]. J Sound Vib. v227 (1999). pp.271-291.
[8] Lee, I.W., Kim, M.C. and Robinson, A.R. Determination of the natural frequencies and mode shapes for large structures by accelerated Newton-Raphson method [J]. Computer & Structures. v63(1997). pp.61-68.
[9] Lee, J.H. and Kim, H.T. Hybrid method for natural frequency extraction: performance improvement using Newton-Raphson method [J]. J Electromagn Waves Appl. v19 (2005). pp.1043-1055.
[10] Rajendran,S and Narasimhan,M.V. An accelerated subspace iteration method [J]. International Journal of Numerical Methods in Engineering, Vol.37(1994).pp.141-153.
[11] Yuan-yao Qian and G.Dhatt. An acclerated subspace method for generalized eigenproblems [J]. Computer & Structures, 1995. pp. 1127-1134.
[12] Y.C. Lam and A.F. Bertolini. Acceleration of the subspace iteration method by selective repeated inverse iteration [J]. Finite Elements Anal Des 18 (1994). pp. 309–317.
[13] A.F. Bertolini and Y.C. Lam. Accelerated reduction of subspace upper bound by multiple inverse iteration [J]. Comput Syst Eng 6 (1995). pp. 67–72.
[14] A.F. Bertolini and Y.C. Lam. Acclerated subspace iteration using adaptive multiple inverse iteration [J]. Computer & Structures, 1998. pp.45-57.
[15] T-C.Cheu, C.P. Johnson and R.R.Craig,JR. Computer algorithms for calculating efficient initial vectors for subspace iteration method [J]. International Journal of Numerical Methods in Engineering,Vol.24(1987).pp.1841-1848.
[16] Yamamoto, Y. and Ohtsubo, H. Subspace iteration accelerated by using Chebyshev polynomials for eigenvalue problems with symmetric matrices [J]. Int J Numer Meth Eng. v10(1976). pp.935-944.
[17] Bathe KJ. Convergence of subspace iteration. In: Bathe KJ, Oden JT, Wunderlich W, editors. Formulations and computational algorithms in finite element analysis [M]. Cambridge (MA): MIT Press, 1977.
[18] F.A. Akl, W.H. Dilger and B.M. Irons. Over-relaxation and subspace iteration [J]. Int J Num Meth Eng 14 (1979), pp. 629–630.
[19] F.A. Akl, W.H. Dilger and B.M. Irons. Acceleration of subspace iteration [J]. Int J Num Meth Eng 18(1982), pp. 583–589.
[20] Wang, X.L. and Zhou, J. An accelerated subspace iteration method for generalized eigenproblems [J]. Comput Struct. v71(1999). 293-301..
[21] Rutishauser, H. Computational aspects of F.L. Bauer's simultaneous iteration method [J]. Numer Math. v13(1969). 4-13.
[22] Rutishauser, H. Simultaneous iteration method for symmetric matrices [J]. Numer Math. v16(1970). 205-223.
[23] Clint, M. and Jennings, A. The evaluation of eigenvalues and eigenvectors of real symmetric matrices by simultaneous iteration [J]. Comput J. v13(1970). 76-80.
[24] Rajendran, S. and Liew, K.M. A variant of the subspace iteration algorithm for generalized eigenproblems [J]. Int J Numer Meth Eng. v57(2003). 2027-2042.
[25] Gong, Y.C., Zhou, H.W., Chen, P. and Yuan, M.W. Comparison of subspace iteration, iterative Ritz vector method and iterative Lanczos method [J]. J Vib Eng. v18 (2005). pp.227-232.
[26] Chen P, Gong YC, Chen YQ. On a computable error bound in the subspace iteration method. Report 2005-02, Dept of Mechanics and Engineering Science, Peking University, 2005.
[27] Zhao Q-C et al. Accelerated subspace iteration with aggressive shift. Computer & Structures[J]. 2007.
[28] Xue, H.Y. Shifted progressive subspace iteration method with changeable subspace dimension and its implementation on microcomputers [J]. J Suzhou Univ (Natural Sci). v11(1995). pp.60-63.
[29]刘裔宏.关于广义特征值估计的一个Gerschgorin型定理[J].工科数学,10:1994.49-51.
[30] D.T. Nguyen and J.S. Arora. Eigensolution for large structural systems with sub-structures [J]. Int J Num Meth Eng 4 (1980), pp. 333–341.
[31] Lu, X., Lin, J.H. and Zhong, W.X . Subspace iteration method in multi-level substructure systems [J]. Comput &Struct. v33 (1989). pp.459-462.
[32] Wilson, E.L., Bathe, K.J. and Doherty, W.P. Direct solution of large system of linear equations [J]. Comput&Struct. v4(1974). pp.363-372.
[33] Lanczos, C. An iteration method for the solution of the eigenvalue problem of linear differential and integral operators. J. Res. Natl. Bur. Stand., 45(1950), pp.255–282.
[34] Matthies, H. G. A subspace Lanczos method for the generalized symmetric eigenproblem [J]. Comput Struct, 21(1985), pp.319-325.
[35] Nour-Omid, B., Parlett, B. N., and Taylor, R. L. Lanczos versus subspace iteration for solution of eigenproblems [J]. Int J Numer Meth Eng. v19(1983), pp.859-871.
[36] Paige, C. C. Computational variants of the Lanczos method for the eigenproblem [J]. J.Inst.Math.Appl.,v10(1972), pp.373-381.
[37] Parlett, B. N., and Scott, D. S. The Lanczos algorithm with selective orthogonalization [J]. Math Comput, v33(1979), pp.217-238.
[38] Simon, H. D. The Lanczos algorithm with partial reorthogonalization [J]. Math Comput, v42(1984), pp.115-142.
[39] Jia Zhongxiao. A refined subspace iteration algorithm for large sparse eigenproblems[J]. Appl Numer Math,2000,32:35-52.
[40]威尔金森.代数特征值问题[M].北京:科学出版社,1987.
[41]格罗布,范罗恩.矩阵计算[M].北京:科学出版社,2000.
[2] Bathe, K.J. and Wilson, E.L. Large eigenvalue problems in dynamic analysis [J]. J Eng Mech Div ASCE. v98(1972). pp.1471-1485.
[3] Bathe KJ. Solution methods for large generalized eigenvalue problems in structural engineering. UC SESM Report 71-20, Department of Civil Engineering, University of California, Berkeley, CA, November, 1971.
[4] Wilson, E.L. and Itoh, T. An eigensolution strategy for large systems [J]. Computer & Structures. v16(1983). pp.259-265.
[5]曹志浩.矩阵特征值问题[M].上海:上海科学技术出版社,1980
[6]曹志浩,张玉德和李瑞遐.矩阵计算和方程求根[M].高等教育出版社,1979.
[7] Jung, H.J. and Lee, I.W. An Improved subspace iteration method with shift for structures with multiple natural frequencies [J]. J Sound Vib. v227 (1999). pp.271-291.
[8] Lee, I.W., Kim, M.C. and Robinson, A.R. Determination of the natural frequencies and mode shapes for large structures by accelerated Newton-Raphson method [J]. Computer & Structures. v63(1997). pp.61-68.
[9] Lee, J.H. and Kim, H.T. Hybrid method for natural frequency extraction: performance improvement using Newton-Raphson method [J]. J Electromagn Waves Appl. v19 (2005). pp.1043-1055.
[10] Rajendran,S and Narasimhan,M.V. An accelerated subspace iteration method [J]. International Journal of Numerical Methods in Engineering, Vol.37(1994).pp.141-153.
[11] Yuan-yao Qian and G.Dhatt. An acclerated subspace method for generalized eigenproblems [J]. Computer & Structures, 1995. pp. 1127-1134.
[12] Y.C. Lam and A.F. Bertolini. Acceleration of the subspace iteration method by selective repeated inverse iteration [J]. Finite Elements Anal Des 18 (1994). pp. 309–317.
[13] A.F. Bertolini and Y.C. Lam. Accelerated reduction of subspace upper bound by multiple inverse iteration [J]. Comput Syst Eng 6 (1995). pp. 67–72.
[14] A.F. Bertolini and Y.C. Lam. Acclerated subspace iteration using adaptive multiple inverse iteration [J]. Computer & Structures, 1998. pp.45-57.
[15] T-C.Cheu, C.P. Johnson and R.R.Craig,JR. Computer algorithms for calculating efficient initial vectors for subspace iteration method [J]. International Journal of Numerical Methods in Engineering,Vol.24(1987).pp.1841-1848.
[16] Yamamoto, Y. and Ohtsubo, H. Subspace iteration accelerated by using Chebyshev polynomials for eigenvalue problems with symmetric matrices [J]. Int J Numer Meth Eng. v10(1976). pp.935-944.
[17] Bathe KJ. Convergence of subspace iteration. In: Bathe KJ, Oden JT, Wunderlich W, editors. Formulations and computational algorithms in finite element analysis [M]. Cambridge (MA): MIT Press, 1977.
[18] F.A. Akl, W.H. Dilger and B.M. Irons. Over-relaxation and subspace iteration [J]. Int J Num Meth Eng 14 (1979), pp. 629–630.
[19] F.A. Akl, W.H. Dilger and B.M. Irons. Acceleration of subspace iteration [J]. Int J Num Meth Eng 18(1982), pp. 583–589.
[20] Wang, X.L. and Zhou, J. An accelerated subspace iteration method for generalized eigenproblems [J]. Comput Struct. v71(1999). 293-301..
[21] Rutishauser, H. Computational aspects of F.L. Bauer's simultaneous iteration method [J]. Numer Math. v13(1969). 4-13.
[22] Rutishauser, H. Simultaneous iteration method for symmetric matrices [J]. Numer Math. v16(1970). 205-223.
[23] Clint, M. and Jennings, A. The evaluation of eigenvalues and eigenvectors of real symmetric matrices by simultaneous iteration [J]. Comput J. v13(1970). 76-80.
[24] Rajendran, S. and Liew, K.M. A variant of the subspace iteration algorithm for generalized eigenproblems [J]. Int J Numer Meth Eng. v57(2003). 2027-2042.
[25] Gong, Y.C., Zhou, H.W., Chen, P. and Yuan, M.W. Comparison of subspace iteration, iterative Ritz vector method and iterative Lanczos method [J]. J Vib Eng. v18 (2005). pp.227-232.
[26] Chen P, Gong YC, Chen YQ. On a computable error bound in the subspace iteration method. Report 2005-02, Dept of Mechanics and Engineering Science, Peking University, 2005.
[27] Zhao Q-C et al. Accelerated subspace iteration with aggressive shift. Computer & Structures[J]. 2007.
[28] Xue, H.Y. Shifted progressive subspace iteration method with changeable subspace dimension and its implementation on microcomputers [J]. J Suzhou Univ (Natural Sci). v11(1995). pp.60-63.
[29]刘裔宏.关于广义特征值估计的一个Gerschgorin型定理[J].工科数学,10:1994.49-51.
[30] D.T. Nguyen and J.S. Arora. Eigensolution for large structural systems with sub-structures [J]. Int J Num Meth Eng 4 (1980), pp. 333–341.
[31] Lu, X., Lin, J.H. and Zhong, W.X . Subspace iteration method in multi-level substructure systems [J]. Comput &Struct. v33 (1989). pp.459-462.
[32] Wilson, E.L., Bathe, K.J. and Doherty, W.P. Direct solution of large system of linear equations [J]. Comput&Struct. v4(1974). pp.363-372.
[33] Lanczos, C. An iteration method for the solution of the eigenvalue problem of linear differential and integral operators. J. Res. Natl. Bur. Stand., 45(1950), pp.255–282.
[34] Matthies, H. G. A subspace Lanczos method for the generalized symmetric eigenproblem [J]. Comput Struct, 21(1985), pp.319-325.
[35] Nour-Omid, B., Parlett, B. N., and Taylor, R. L. Lanczos versus subspace iteration for solution of eigenproblems [J]. Int J Numer Meth Eng. v19(1983), pp.859-871.
[36] Paige, C. C. Computational variants of the Lanczos method for the eigenproblem [J]. J.Inst.Math.Appl.,v10(1972), pp.373-381.
[37] Parlett, B. N., and Scott, D. S. The Lanczos algorithm with selective orthogonalization [J]. Math Comput, v33(1979), pp.217-238.
[38] Simon, H. D. The Lanczos algorithm with partial reorthogonalization [J]. Math Comput, v42(1984), pp.115-142.
[39] Jia Zhongxiao. A refined subspace iteration algorithm for large sparse eigenproblems[J]. Appl Numer Math,2000,32:35-52.
[40]威尔金森.代数特征值问题[M].北京:科学出版社,1987.
[41]格罗布,范罗恩.矩阵计算[M].北京:科学出版社,2000.