摘要
众所周知,在工程计算和实际应用中有许多问题最终都归结为矩阵计算问题,而且不同的应用会导出一些具有特殊结构的矩阵计算.最常见的一些结构矩阵有ToepHtz矩阵|α_i-j|,Hankel矩阵|a_i+j|,Toeplitz-plus-Hankel矩阵,Cauchy矩阵[(?)]等等.处理与这些结构矩阵有关的矩阵计算问题(例如计算特征值、求解线性方程组等),若矩阵的阶数较小时,通常的经典算法是可行的(例如LU分解算法、QR算法等).然而,在许多实际应用当中,矩阵的阶数n很大(n-10~6-10~9)或某个线性方程组需要多次计算直到得到一个满意的结果(例如迭代法时),此时这些经典的算法由于代价太大而失去了实际意义.
因此,针对这些结构矩阵的特点而设计一些能利用它们的结构的,数值稳定的快速算法,具有非常重要的意义.正因为结构矩阵在实际应用中所具有的重要意义,国内外众多的学者将目光投入到这一领域.结构矩阵的快速算法中最著名的莫过于央速傅里叶变换(即FFT),有许多快速算法均是由快速傅里叶变换导出的.因此,著名数学家Charles Van Loan曾这样评价快速傅里叶变换算法:“从计算的角度看,快速傅里叶变换是本世纪最杰出的成就之一,毫不夸张地说,快速傅里叶变换改变了科学与工程计算的面貌,如果没有它,生活将会是另一种景象”.
本论文主要研究了实Hankel-circulant和Hankel-skew-circulant矩阵的奇异值分解,给出了对称Toeplitz-plus-Hankel矩阵特征值的快速算法和这个计算矩阵特征值算法的数值实验.理论和数值实验显示,这个快速算法是行之有效的.
第一章,我们简单介绍了研究结构矩阵快速算法的现实意义、研究概况以及常用的研究方法,同时也给出了与本论文有关的几类结构矩阵的定义及其基本性质.
第二章,我们给出了n阶对称Toeplitz-plus-Hankel矩阵与一个n维向量乘积的快速算法;并利用n阶矩阵的对称性,对其实施Lanczos三对角化和QR对角化,计算出矩阵的所有特征值.该算法的计算复杂度为O(n~2 log n).
第三章,我们研究了实Hankel-circulant、Hankel-skew-circulant矩阵与Hankel矩阵的关系,并给出了它们的奇异值分解,为我们研究实Hankel-circulant矩阵、Hankel-skew-circulant矩阵的奇异值分解提供了理论基础.
Many important problems in engineering and applied sciences can be finally reduced to matrix computation problems. Moreover, various applications often introduce some special structures into the corresponding matrices. Among classical examples are Toeplitz matrices [a_(i-j)], Hankel matrices [a_(i+j)], Toeplitz-plus-Hankel matrices, Cauchy matrices (?) and others. When we deal with the related matrix problem (such as computing eigenvalue , solving linear systems and so on) with special structure, as we know, the standard linear algebra(such as Gaussian elimination algorithm, QR algorithm, etc)are, of course, readily available for small-size problems.However, in many practical applications, the order of matrices are very large (n - 10~6 -10~9) or the linear equations may have to be solved over and over again (such as iterative methods), with different problem or model parameters, until a satisfactory solution to the original physical problem is obtained.In such cases, the number of flops required to solve the related matrix problems can become prohibitively large so that these classical methods have no senses.Therefore, to achiving a fast and stable algorithm for these matrices with special of characteristic structure is an important issue in many applied areas.
Thus, it is not surprising that in recent years the design of fast algorithms for structured matrices has become an increasingly important activity in a diverse variety of branches of the exact sciences. As to fast algorithms, perhaps the most widely and importantly known example of fast algorithms is the fast Fourier transform(FFT) .There are many classical fast algorithms which are been deduced by FFT. Its importance is widely acknowledged and nicely described in numerous papers and monographs, e.g., as follows: "The fast Fourier transform(FFT)is one of the truly great computational developments of this century. It has changed the face of science and engineering so that it is not an exaggeration to say that life as we know it would be very different without FFT " (Charles Van Loan, a famous mathematician).
In this paper, we mainly discuss SVD of Hankel-circulant and Hankel-skew- circulant matrices and design a fast algorithm for symmetric Toeplitz-plus-Hankel matrices. As theoretical and numerical experiments results show, the fast algorithm is very useful.
In chapter 1, we give a brief introduction to the importance, the current research situation and classical research methods on structured matrices. Moreover, some definition and properties of the structured matrices which are discussed in our paper have been given.
In chapter 2, we present a fast symmetric Toeplitz-plus-Hankel matrix-vector product algorithm and apply the Lanczos-type tridiagonalization and QR-type diagonalization method to find all the eigenvalues of an n×n symmetric Toeplitz-plus-Hankel matrix in O(n~2 log n) operation.
In chapter 3, we study the relation between real Hankel-circulant、Hankel-skew-circulant matrix and Hankel matrix. Moreover, we present several singular value decompositions of real Hankel-circulant and Hankel-skew-circulant matrices. The singular value decompositions of this chapter are given in explicit form which can be easily evaluated in computer programs and provide a useful basis for theoretical investigations.
引文
[1] J.W.Cooley, J.W.Tukey, An algorithm for the machine calculating of complex Fourier series, J.Comp.Math., 19(1965)372-376.
[2] Y.Eidelman, Fast recursive algorithm for a class of structured matrices, Appl. Math.Lett., 13(2000)57-62.
[3] G.Heinig, K.Rost, Recusive solution of Cauchy-Vandermonde systems of equations , Lin.Alg.Appl., 218(1995)59-72.
[4] T.Kailath, S.Kung, M.Morf, Displacement ranks of matrices and linear equations, J. Math. Anal. Appl., 68(1979)395-407.
[5] T.Kailath, A.Sayed, Displacement structure:Theory and Applications, SIAM Rev., 37(1995)297-386.
[6] V.Y.Pan, Structured Matrices and Polynomials:Unified Superfast Algorithm , Springer-Verlag, New York, 2001.
[7] G.Cybenko, C.F.Van Loan, Computing the minimum eigenvalue of asymmetric positive definite Toeplitz matrix, SIAM J.Sci.Stat.Comput., 7 (1986)123-131.
[8] W.Trench , Numerical solution of the eigenvalue problem for Hermitian Toeplitz matrices, SIAM J.Matrix Anal.Appl., 10(2)(1989)135-146.
[9] W.Trench , Numerical solution of the eigenvalue problem for efficiently structured Hermitian matrices, Lin. Alg. Appl., 154-156(1991)154-156.
[10] M.Ng, Preconditioned Lanczos methods for the minimum eigenvalue of a symmetric positive definite Toeplitz matrix, SIAM J.Sci.Comput., 21 (6)(2000) 1973-1986.
[11] J.K.Cullum , R.A.Willoughby , A QL procedure for computing the eigenvalues of complex symmetric tridiagonal matrices, SIAM J.Matrix Anal.Appl., 17(1) (1996)83-109.
[12] W.Mackens , H. Voss , The minimum eigenvalue of a symmetric positive-definite Toeplitz matrix and rational Hermitian interpolation, SIAM J.Matrix Anal.Appl., 18(1997)521-534.
[13] W.Trench, Some spectral properties of Hermitian Toeplitz matrices , SIAM J.Matrix.Anal.Appl., 15(1994)938-942.
[14] D.Fasino, Spectral properties of Toeplitz-plus-Hankel matrices, Calcolo, 33(19-96) 87-98.
[15] R.H.Chan, M.K.Ng, Conjugate gradient methods for Toeplitz systems, SIAM Rev., 38(3)(1996)427-482.
[16] F.T.Luk, S.Qiao, A fast eigenvalue algorithm for Hankel matrices, Lin.Alg.Appl., 30(2000)171-182.
[17] C.F.Van Loan, Computational frameworks for the Fast Fourier Transform, SIAM, Philadephia, PA, 1992.
[18] H.C.Raymond, Sine transform based preconditioned for symmetric Toeplitz systems, Lin.Alg.Appl., 232(1996)237-259.
[19] M.K.Ng, R.J.Plemmons, Fast recursive least squares adaptive filtering by fast Fourier transform-based conjugate gradient iterations, SIAM.J.Sci.Comput., 4(1996)920-941.
[20] G.H. Golub, C.F. Van Loan, Matrix Computations, third ed. , The Johns Hopkins University Press, Baltimore, MD, 1996.
[21] C.Sun, J.Hahn, Parameter reduction for stable dynamical systems based on Hankel singular values and sensitivity analysis, Chem.Eng. Sci., 61(2006)5393-5403.
[22] D.Fasino , Spectral properties of Hankel matrices and numerical solutions of finite moment problems, J.Comput.Appl.Math., 65(1995)145-155.
[23] R.W.Freund, Hongyuan Zha, A look-head algorithm for the solution of general Hankel systems, Numer.Math., 64(1993)295-321.
[24] H.Karner, J.Schneid, C.W.Ueberhuber, Spectral decomposition of real circulant matrices, Lin.Alg.Appl., 367(2003)301-311.
[25] B.N. Paxlett, The Symmetric Eigenvalue Problem, SIAM, Philadelphia, PA, 1998.
[26] F.T.Luk , S.Qiao , Using complex-orthogonal transformations to diagonalize a complex symmetric matrix , Advanced Signal Processing: Algorithms, Archi-tectures and Implementations VII, Proc.SPIE., 3162(1997)418-425.
[27] D. Vandevoorde , A fast exponential decomposition algorithm and its applications to structured matrices, Ph.D.Dissertation, Computer Science Department, Rensselaer Polytechnic Institute, Troy, NY, 1996.
[28] C.X.Gu, L.Patton, Commutation relations for Toeplitz and Hankel matrices, SIAM J.Matrix.Anal.Appl., 24(2003)28-746.
[29] J.K. CuUum, R.A.Willoughby. Lanczos Algorithms for Large Symmetric Eigenvalue Computations, SIAM, Philadelphia, PA, 2002.
[30] Kh.D.Ikramov, V.N.Chugunov, Several observations on Toeplitz and Hankel circulants, J.Math.Sci., 141(2007)1639-1642.
[31] M.Fiedler, Spectral properties of real Hankel matries, Cont. Math., 280(2001)313-320.
[33] M.V.Barel, P.Kravanja, A stabilized superfast solver for indefinite Hankel systems, Lin.Alg.Appl., 284(1998) 335-355.
[34] Zhongzhi Bai, Gene H. Golub, Linzhang Lu , Junfeng Yin, Block triangular and skew-Hermitian splitting methods for positive definite linear systems, SIAM J. Sci. Comput., 26(3)(2005)844-863.
[35] Linzhang Lu, Wai-ki Ching, Michael K. Ng, Exact algorithm for singular triangular systems unth applications to Markov chains, Appl. Math. Comput., 159(2004)275-289.
[36] Linzhang Lu , C. E. M. Pearce, Some new bounds for singular values and eigenvalues of matrix products, Ann.Oper. Res., 98(2000)141-148.
[39] 汪祥，卢琳璋， alpha双对角占优与H矩阵的判定，厦门大学学报(自)，42(5)(2003)，570-573．
[40] 汪祥，卢琳璋，alpha双对角占优矩阵，厦门大学学报(自)，42(4)(2003)425-428．
