大规模矩阵伪谱计算的数值方法
|
摘要
矩阵伪谱在很多领域都有重要的理论意义和工程价值,是理解各种矩阵过程的一个非常有用的工具,拓展了我们对矩阵计算现象的理解。对非正规矩阵,已经证明伪谱是一个很有用的工具。从科学计算的观点看,非正规矩阵或算子的伪谱要比它的谱更可靠。但是伪谱的计算量很大,因此需要寻找能够在一定合理时间内计算伪谱的方法。
本文在概述伪谱的理论和算法的基础上,给出了计算大规模矩阵伪谱的一种投影算法,包括正交投影算法和斜投影算法,并将这种算法推广到矩阵多项式伪谱的计算中。和已有的矩阵伪谱算法不同,本文提出了求解矩阵伪谱的最佳秩-k逼近算法,这种方法对于特定矩阵的伪谱计算有很好的效果。本文还将矩阵伪谱的QR分解定义推广到了矩阵多项式伪谱。对各种算法,本文分别给出了数值试验,以验证它们的有效性。
The computation of matrix pseudospectra, which have been widely used in many fields, is an interesting and important problem for discussion with special theoretic sense and engineering value. The pseudospectra of matrix is a powerful concept that broadens our understanding of the bahaviour of various matrix process and phenomena based on matrix computation. For non-normal matrices and operator, matrix pseudospectra had been proved to be more useful than eigenvalues. However, the compution of pseudospectra is a very expensive computational task. Thus, the use of high performace computing recources becomes key to obtaining useful answers in acceptable amouts of time.
This paper, based on a brief summary of pseudospectra theory and algorithms, proposed an advanced kind of projection methods for computing the pseudospectra of large scale matrices, including orthogonalization projection method and oblique projection method respectively, which had been generalized to the computing of matrix polynomials pseudospectra. Different form the methods that have been developed, this paper develop a method called optimal rank-k method for the computing of matrix pseudospectra. This method has good performance for certain matrices. Also, this paper give a new definition of pseudospectra of matrix polynomials by using QR decomposition, which is generalized form the the QR decomposition definition of matrix pseudospectra. Nnumerical experiments illustrate the efficiency of different methods.
本文在概述伪谱的理论和算法的基础上,给出了计算大规模矩阵伪谱的一种投影算法,包括正交投影算法和斜投影算法,并将这种算法推广到矩阵多项式伪谱的计算中。和已有的矩阵伪谱算法不同,本文提出了求解矩阵伪谱的最佳秩-k逼近算法,这种方法对于特定矩阵的伪谱计算有很好的效果。本文还将矩阵伪谱的QR分解定义推广到了矩阵多项式伪谱。对各种算法,本文分别给出了数值试验,以验证它们的有效性。
The computation of matrix pseudospectra, which have been widely used in many fields, is an interesting and important problem for discussion with special theoretic sense and engineering value. The pseudospectra of matrix is a powerful concept that broadens our understanding of the bahaviour of various matrix process and phenomena based on matrix computation. For non-normal matrices and operator, matrix pseudospectra had been proved to be more useful than eigenvalues. However, the compution of pseudospectra is a very expensive computational task. Thus, the use of high performace computing recources becomes key to obtaining useful answers in acceptable amouts of time.
This paper, based on a brief summary of pseudospectra theory and algorithms, proposed an advanced kind of projection methods for computing the pseudospectra of large scale matrices, including orthogonalization projection method and oblique projection method respectively, which had been generalized to the computing of matrix polynomials pseudospectra. Different form the methods that have been developed, this paper develop a method called optimal rank-k method for the computing of matrix pseudospectra. This method has good performance for certain matrices. Also, this paper give a new definition of pseudospectra of matrix polynomials by using QR decomposition, which is generalized form the the QR decomposition definition of matrix pseudospectra. Nnumerical experiments illustrate the efficiency of different methods.
引文
[1] Trefethen L N. Pseudospectra of linear operators. SIAM Review, 1997, 39(3): 383~406.
[2] Robbe M, Sadkane M. Discrete-time Lyapunov stability of the large matrices. Journal of Computational and Applied Mathematics, 2000, 115: 479~494.
[3] Higham N J, Tisseur F. More on pseudospectra for polynomial eigenvalue problems and applications in control theory. Linear Algebra and its Applications, 2002: 435~453.
[4] Tippett M K, Marchesin D. Upper bounds for the solution of the discrete algebraic Lyapunov equation. Automatica, 1999, 35: 1485~1489.
[5] Nachtigal N M, Reddy S C, Thfethen L N. A hybrid GMRES algorithm for nonsymmetric liner systems. SIAM J. Matrix Anal. Appl., 1992, 13: 796~825.
[6] Reddy S C, Trefethen L N. Stability of the method of lines. Numerical Mathematics, 1992, 62: 235~267.
[7]李宝成,蒋耀林.关于动力学系统伪谱与扰动系统谱之间关系的研究.工程数学学报, 2004, 21(6): 936~940.
[8] L J, Dorsselaer M V. Pseudospectra for matrix pencils and stability of equilibria. BIT, 1997, 37: 833~845.
[9] Kailath T. Linear Systems. Englewood Cliffs, NJ: Prentice-Hall, 1980.
[10] Eising R. Between controllable and uncontrollable. Systems Control Lett., 1984, 4: 263~264.
[11] Gu M. New methods for estimating the distance to uncontrollability. SIAM J. Matrix Anal. Appl., 2000, 21: 989~1003.
[12] Thompson G L, Weil R L. The roots of matrix pencils( Ay =λBy): Existence, calculations, and relations to game theory. Linear Algebra and its Applications, 1972, 5: 207~226.
[13] Trefethen L N. Computation of pseudospectra. Acta Numerica, 1999, 8: 247~295.
[14] Wright T G, Trefethen L N. Large-scale computation of pseudospectra using ARPACK and eigs. SIAM J. Sci. Comput., 2001, 23(2): 591~605.
[15] Embree M, Trefethen L N. Generalizing eigenvalue theorems to pseudospectra theorems. SIAM J. Sci. Comput., 2001, 23(2): 583~590.
[16] Braconnier T, Higham N J. Computing the field of values and pseudospectra using the Lanczos method with continuation. Numerical Mathematics, 1996, 36(3): 422~440.
[17] Bekas C, Kokiopoulou E, Gallopoulos E. The design of a distributed MATLAB-based environment for computing pseudospectra. Future Generation Computer Systems, 2005, 21:930~941.
[18] Godunov S K, Sadkane M. Computation of pseudospectra via spectral projectors. Linear Algebra and its Applications, 1998, 279: 163~175.
[19] Malyshev A N, Sadkane M. Componentwise pseudospectrum of a matrix. Linear Algebra and its Applications, 2004, 378: 283~288.
[20]李宝成,孙铮.特征值定理向伪谱定理推广的标记.南京理工大学学报, 2003, 27: 52~55.
[21]李宝成,孙铮.广义特征值定理向伪谱定理的推广.南京理工大学学报, 2005, 29(1): 113~115.
[22] Wright T G. Matlab Pseudospectra GUI. http://www.comlab.ox.ac.uk/pseudospectra/psagui/.
[23] Wright T G. Algorithms and Software for Pseudospectra. Oxford: University of Oxford, 2002.
[24] Bottcher A, Grudsky S, Kozak A. On the distance of a large Toeplitz band matrix to the nearest singular matrix. In: Toeplitz Matrices and Singular Integral Equations(Pobershau 2001), Operational Theory Advances and Application, vol.135. Birkhauser: Basel, 2002: 101~106.
[25] Byers R, He C, Mehrmann V. Where is the nearest nonregular pencil?. Linear Algebra and its Applications, 1998, 285: 81~105.
[26] Hinrichsen D, Kelb B. Spectral value set: a graphical tool for robustness analysis. Systerms Control Lett., 1993, 21(2): 127~136.
[27] Lancaster P, Panayiotis P. On the pseudospectra of matrix polynomials. SIAM J. Matrix Anal. Appl., 2005, 27(1): 115~129.
[28] Boulton L, Lancaster P, Psarrakos P. On pseudospectra of matrix polynomials and their boundaries. Numerical Mathematics, 2008, 77: 313~334.
[29] Tisseur F, Higham N J. Structured pseudospectra for polynomial eigenvalue problems, with applications. SIAM J. Matrix Anal. Appl., 2001, 23(1): 187~208.
[30] Sk Safique A, Rafikul A. Pseudospectra, critical points and multiple eigenvalues of matrix polynomials. Linear Algebra and its Applications, 2008: 1~25.
[31] Golub G H, Van Loan C F. Matrix computations, the 2nd ed.. Baltimore, MD: Johns Hopkins University Press, 1989.
[32] Saad Y. Numerical methods for large eigenvalue problems. Manchester, UK: Manchester University Press, 1992.
[33] Bai Z J, Demmel J, Dongarra J, Ruhe A, Van der Vorst H. Templates for the solution of algebraic eigenvalue problems: A practical guide. SIAM Philadelphia, 2000.
[34] Van Vorst H A. Computational methods for large eigenvalue problems. Amsterdam: Elsevier,2002.
[35] Wright T G, Trefethen L N. Pseudospectra of rectangular matrices. IMA Journal of Numerical Analysis, 2002, 22: 501~519.
[36] Eckart C, Young G. The approximation of a matrix by another of lower rank. Psychometrika, 1936, 1: 211~218.
[37] Shen Y, Zhao J, Fan H. Properties and computations of matrix pseudospectra. Applied mathematics and Computation, 2005, 161: 385~393.
[38] Du K. A note on properties and computations of matrix pseudospectra. Applied mathematics and Computation, 2006, 174: 1007~1019.
[39] Bruhl M. A curve tracing algorithm for computing the pseudospectra. BIT, 1996, 36: 441~454.
[40]刘颖,白峰衫.伪谱的边界曲线及其跟踪算法的步长控制.高等学校计算数学学报, 2003, 25(1): 1~11.
[41] Wagenknecht T, Michiels W, Green K. Structured pseudospectra for nonlinear eigenvalue problems. Journal of Computational and Applied Mathematics, 2008, 212: 245~259.
[42] Rump S M. Eigenvalues, pseudospectrum and structured perturbations. Linear Algebra and its Applications, 2006, 413: 567~593.
[43] Trefethen L N, Contedini M, Embree M. Spectra, Pseudospectra and Localization for Random Bidiagonal Matrices. Communications on Pure and Applied Mathematics, 2000, 54: 595~623.
[44] Graillat S. A note on structured pseudospectra. Journal of Computational and Applied Mathematics, 2006, 191: 68~76.
[45] Lumsdaine A, Wu D. Spectra and pseudospectra of Block Toeplitz Matrices. Linear Algebra and its Applications, 1998, 272: 103~130.
[46] Rump S M. Structured perturbations.I.Normwise distances. SIAM J. Matrix Anal. Appl., 2003, 25(1): 1~30(electronic).
[47] Tisseur F, Graillat S. Structured condition numbers and backward errors in scalar product space. Numerical Analysis Report, Manchester, England: Manchester Centre for Computation Mathematics, 2005
[2] Robbe M, Sadkane M. Discrete-time Lyapunov stability of the large matrices. Journal of Computational and Applied Mathematics, 2000, 115: 479~494.
[3] Higham N J, Tisseur F. More on pseudospectra for polynomial eigenvalue problems and applications in control theory. Linear Algebra and its Applications, 2002: 435~453.
[4] Tippett M K, Marchesin D. Upper bounds for the solution of the discrete algebraic Lyapunov equation. Automatica, 1999, 35: 1485~1489.
[5] Nachtigal N M, Reddy S C, Thfethen L N. A hybrid GMRES algorithm for nonsymmetric liner systems. SIAM J. Matrix Anal. Appl., 1992, 13: 796~825.
[6] Reddy S C, Trefethen L N. Stability of the method of lines. Numerical Mathematics, 1992, 62: 235~267.
[7]李宝成,蒋耀林.关于动力学系统伪谱与扰动系统谱之间关系的研究.工程数学学报, 2004, 21(6): 936~940.
[8] L J, Dorsselaer M V. Pseudospectra for matrix pencils and stability of equilibria. BIT, 1997, 37: 833~845.
[9] Kailath T. Linear Systems. Englewood Cliffs, NJ: Prentice-Hall, 1980.
[10] Eising R. Between controllable and uncontrollable. Systems Control Lett., 1984, 4: 263~264.
[11] Gu M. New methods for estimating the distance to uncontrollability. SIAM J. Matrix Anal. Appl., 2000, 21: 989~1003.
[12] Thompson G L, Weil R L. The roots of matrix pencils( Ay =λBy): Existence, calculations, and relations to game theory. Linear Algebra and its Applications, 1972, 5: 207~226.
[13] Trefethen L N. Computation of pseudospectra. Acta Numerica, 1999, 8: 247~295.
[14] Wright T G, Trefethen L N. Large-scale computation of pseudospectra using ARPACK and eigs. SIAM J. Sci. Comput., 2001, 23(2): 591~605.
[15] Embree M, Trefethen L N. Generalizing eigenvalue theorems to pseudospectra theorems. SIAM J. Sci. Comput., 2001, 23(2): 583~590.
[16] Braconnier T, Higham N J. Computing the field of values and pseudospectra using the Lanczos method with continuation. Numerical Mathematics, 1996, 36(3): 422~440.
[17] Bekas C, Kokiopoulou E, Gallopoulos E. The design of a distributed MATLAB-based environment for computing pseudospectra. Future Generation Computer Systems, 2005, 21:930~941.
[18] Godunov S K, Sadkane M. Computation of pseudospectra via spectral projectors. Linear Algebra and its Applications, 1998, 279: 163~175.
[19] Malyshev A N, Sadkane M. Componentwise pseudospectrum of a matrix. Linear Algebra and its Applications, 2004, 378: 283~288.
[20]李宝成,孙铮.特征值定理向伪谱定理推广的标记.南京理工大学学报, 2003, 27: 52~55.
[21]李宝成,孙铮.广义特征值定理向伪谱定理的推广.南京理工大学学报, 2005, 29(1): 113~115.
[22] Wright T G. Matlab Pseudospectra GUI. http://www.comlab.ox.ac.uk/pseudospectra/psagui/.
[23] Wright T G. Algorithms and Software for Pseudospectra. Oxford: University of Oxford, 2002.
[24] Bottcher A, Grudsky S, Kozak A. On the distance of a large Toeplitz band matrix to the nearest singular matrix. In: Toeplitz Matrices and Singular Integral Equations(Pobershau 2001), Operational Theory Advances and Application, vol.135. Birkhauser: Basel, 2002: 101~106.
[25] Byers R, He C, Mehrmann V. Where is the nearest nonregular pencil?. Linear Algebra and its Applications, 1998, 285: 81~105.
[26] Hinrichsen D, Kelb B. Spectral value set: a graphical tool for robustness analysis. Systerms Control Lett., 1993, 21(2): 127~136.
[27] Lancaster P, Panayiotis P. On the pseudospectra of matrix polynomials. SIAM J. Matrix Anal. Appl., 2005, 27(1): 115~129.
[28] Boulton L, Lancaster P, Psarrakos P. On pseudospectra of matrix polynomials and their boundaries. Numerical Mathematics, 2008, 77: 313~334.
[29] Tisseur F, Higham N J. Structured pseudospectra for polynomial eigenvalue problems, with applications. SIAM J. Matrix Anal. Appl., 2001, 23(1): 187~208.
[30] Sk Safique A, Rafikul A. Pseudospectra, critical points and multiple eigenvalues of matrix polynomials. Linear Algebra and its Applications, 2008: 1~25.
[31] Golub G H, Van Loan C F. Matrix computations, the 2nd ed.. Baltimore, MD: Johns Hopkins University Press, 1989.
[32] Saad Y. Numerical methods for large eigenvalue problems. Manchester, UK: Manchester University Press, 1992.
[33] Bai Z J, Demmel J, Dongarra J, Ruhe A, Van der Vorst H. Templates for the solution of algebraic eigenvalue problems: A practical guide. SIAM Philadelphia, 2000.
[34] Van Vorst H A. Computational methods for large eigenvalue problems. Amsterdam: Elsevier,2002.
[35] Wright T G, Trefethen L N. Pseudospectra of rectangular matrices. IMA Journal of Numerical Analysis, 2002, 22: 501~519.
[36] Eckart C, Young G. The approximation of a matrix by another of lower rank. Psychometrika, 1936, 1: 211~218.
[37] Shen Y, Zhao J, Fan H. Properties and computations of matrix pseudospectra. Applied mathematics and Computation, 2005, 161: 385~393.
[38] Du K. A note on properties and computations of matrix pseudospectra. Applied mathematics and Computation, 2006, 174: 1007~1019.
[39] Bruhl M. A curve tracing algorithm for computing the pseudospectra. BIT, 1996, 36: 441~454.
[40]刘颖,白峰衫.伪谱的边界曲线及其跟踪算法的步长控制.高等学校计算数学学报, 2003, 25(1): 1~11.
[41] Wagenknecht T, Michiels W, Green K. Structured pseudospectra for nonlinear eigenvalue problems. Journal of Computational and Applied Mathematics, 2008, 212: 245~259.
[42] Rump S M. Eigenvalues, pseudospectrum and structured perturbations. Linear Algebra and its Applications, 2006, 413: 567~593.
[43] Trefethen L N, Contedini M, Embree M. Spectra, Pseudospectra and Localization for Random Bidiagonal Matrices. Communications on Pure and Applied Mathematics, 2000, 54: 595~623.
[44] Graillat S. A note on structured pseudospectra. Journal of Computational and Applied Mathematics, 2006, 191: 68~76.
[45] Lumsdaine A, Wu D. Spectra and pseudospectra of Block Toeplitz Matrices. Linear Algebra and its Applications, 1998, 272: 103~130.
[46] Rump S M. Structured perturbations.I.Normwise distances. SIAM J. Matrix Anal. Appl., 2003, 25(1): 1~30(electronic).
[47] Tisseur F, Graillat S. Structured condition numbers and backward errors in scalar product space. Numerical Analysis Report, Manchester, England: Manchester Centre for Computation Mathematics, 2005