矩阵特征值解法初探

矩阵特征值解法初探届 别 2012届系 别 数学系专 业 信息与计算科学姓 名 马晓娜指导教师 王川龙二○一二年五月矩阵特征值解法初探学生姓名: 马晓娜 指导老师: 王川龙摘要 矩阵的奇异值与特征值是矩阵分析中的重要课题. 本文研究了利用幂方法、Krylor方法、Lanczos方法、Frame方法、Samuelson方法解特征值的理论, 并在此基础上举例分析了奇异值与特征值的关系. 关键词 特征值; 奇异值; 谱范数; 谱半径基础知识(1) 设矩阵AÎCn‰n. 如果则称A 是酉矩阵.(2) 矩阵A的奇异值用 表示.定义1 设A =[a ij]∈Mn (C),若存在数l和和非零向量x, 使得 则称λ为矩阵A的特征值，x为A的属于特征值λ的标准特征向量.定理[1] (奇异值分解) 设矩阵AÎCn×n, rank(A)= k. 则存在酉矩阵U 和V, 使得,其中， (s1³……³sk >0)为A的非零奇异值. 因此, åk 由A 唯一确定.一、幂方法介绍n阶矩阵A有完备的特征向量系时，按模最大和最小的特征值与对应的特征向量的计算方法. 设AÎCn‰n的特征值为l1, l2, …, ln, 对应的特征向量依次为x1, x2, …, xn, 且它们线性无关1.乘幂法[2] (适用于求大型稀疏矩阵的主特征值)设A的特征值满足, (1) 给定非零向量V(0)ÎCn, 并分解 且要求a1≠0, 则有 (2)当k充分大时, 式(2)括号中第二项可以省略, 即A(k)v(0)近似于a1l1kx1, 从而可以对应于特征值的近似特征值向量. 但在实际计算中, 常数因子a1l1k当k→∞时会导致无限减小或无限增大, 所以每一步应使用一次单位化运算. 设u=(u1,u2,,un)T,记uÎCn的最大分量为 ，于是建立迭代公式 } (3)下面讨论向量序列{v(k)}的收敛性. 从式(3)逐次回代可得 上式分母是一个常数, 而v(k)的最大分量总是1, 所以 (4)在式(1)及a1≠0的假设下, 当k→∞时, 由式(2)有 于是得到：mk收敛于l1, 而v(k)收敛于对应l1的单位特征向量.2.逆幂法设可逆矩阵A的特征值满足, 则A-1的特征值满足 即1/ln是A-1的按模最大特征值, 将乘幂法迭代公式(3)用于A-1, 即得逆幂法迭代公式 由解出u(k), (5) （k=1,2,…）与乘幂法的收敛性分析相同, 有 为了计算A的第l个特征值及对应的特征向量, 选取常数q¹lI (i=1,2,…,n)满足 0<|ll-q|†|li-q| (i¹l) (6)即要求q接近于ll, 则(A-qI)-1的按模最大特征值为(ll-q)-1, 对矩阵A-qI应用逆幂法迭代公式(5), 可得 由解出u(k), (7) (k=1,2,…).于是有 只要q选择得能很好地满足式(6), 则迭代公式(7)的收敛速度可以很快. 参数q的选择可以利用Gerschgorin定理或其他有关特征值的信息. 迭代公式(7)称为原点位移的逆幂法. 它是目前求矩阵特征值和特征向量的有效方法之一. 二、Krylov方法通过计算n阶矩阵A的特征多项式的某些因子的零点, 得到A的全体互异特征值及其对应的特征向量.1 矩阵多项式设A的特征多项式为 (8)最小多项式为m(l). 且由j(A)=O, 所以1£¶m(l)£n.定理1 设n阶矩阵A的特征值为l1, l2, …, ln, 多项式f(l)满足f(A)=O, 则有(1) f(li)=0 (i=1,2,…,n)(2)A的最小多项式m(l)整除f(l).定理2 矩阵A的最小多项式m(l)唯一, 且m(l)与j(l)的零点相同(不计重数).2 向量相对于矩阵的零化多项式定义2.1 设AÎCn‰n, 0¹yÎCn. 如果yy(l)是使yy(A)y=0成立的次数最低的首1多项式, 那么称yy(l)为y相对于A的零化多项式. 定理3 设yy(l)为y相对于A的零化多项式, 则yy(l)|m(l).定理4 向量y相对于矩阵A的零化多项式唯一. 定理5 设An‰n¹0, 0¹yÎCn. 若有1£k£n, 使得y,Ay,…,Ak-1y线性无关，而y,Ay,…,Ak-1y,Aky线性相关, 则y相对于A的零化多项式为 其中列向量(p1,p2,…,pk)T是线性方程组 (9)的唯一解.3 向量相对于矩阵的零化多项式计算设 An‰n¹0, 0¹yÎCn. 令 (k=1,2,…,n),构造n×(n+1)矩阵 则 定理6 设1£k£n, y0, y1, … ,yk线性相关, 则推论 若则y0, y1, … ,yk-1线性无关. 定理7 设1£k£n, 则的充要条件是 综上所述, 确定yy(l)的步骤可归结为:(1)计算; (2)求方程组(6)的唯一解;(3)写出4 矩阵的最小多项式计算尽管在理论上可以给出矩阵A 的最小多项式m(l)的计算公式，但其计算过程比较复杂. 这里通过计算有限个不同的y相对于A的零化多项式yy(l)来确定m(l). 定理8 设y0(i)相对于A零化多项式为yi(l)且¶yi(l)=ki (i=1,2,…,N), 多项式y1(l),…yN(l)的最小公倍式为f(l), 记Cn的子空间 如果V1+V2+…+VN=Cn, 则m(l)=f(l). 根据定理8，可将确定m(l)的步骤归结为: (1)选取y0¹0, 计算rankB1=k1, 求出y0相对于A的零化多项式y1(l). 记 , 若V1=Cn, 则m(l)=y1(l);(2)当V1¹Cn 时, 选取y0(2)¹0且y0(2)ÏV1, 计算rankB2=k2, 求出y0(2)相对于A的零化多项式y2(l). 记 , 若, 则m(l)等于y1(l)与y2(l)的最小公倍式; (3)当V1+V2¹Cn, y0(3)¹0, 且y0(3)Ï V1+V2, ….因为dim(V1+V2+…+VN)³N, 所以存在某个N(1£N£n), 使得. 于是m(l)为y1(l), y2(l), …, yN(l)的最小公倍式. 三、Lanczos方法使用Krylov方法确定y相对于矩阵A的零化多项式yy(l)时, 需要求解线性方程组(6). 如果由向量y生成的矩阵B的秩较大, 方程组(6)的求解过程将会变得复杂. 现介绍能避免这一计算的Lanczos方法. 1 Lanczos正交化过程对于n阶矩阵A和n维非零列向量y0, 构造两两正交的向量序列{yk}:要求可得 . 记 则有 要求y2^yj可得 (j=0,1). 记 则有 要求y3^yj可得 (j=0,1,2). 记 则有 …… 要求yk^yj可得 (j=0,1,…,k-1). 记 (10)则有 由于Cn中两两正交的非零向量组含向量的个数最多为n, 所以必有r£n使得 (11)2 向量相对于矩阵的零化多项式计算定理9 设r£n使式(11)成立, 则由式(10)定义的多项式Pr(l)是y0相对于A的零化多项式. 3 矩阵的最小多项式计算定理10 设Pr1(l)与Qr2(l)分别是由Lanczos方法确定的y0与z0相对于A的零化多项式, 而y1,…,yr1-1与z1,…,zr2-1是由Lanczos正交化过程得到的向量组, 如果 则m(l)等于Pr1(l)与Qr2(l)的最小公倍式. 基于定理10可将确定m(l)的步骤归结如下.(1)取y0¹0, 计算y0相对于A的零化多项式Pr1(l). 当r1=n时, m(l)=Pr1(l). (2)当r1dimV1. 当dimV2=n时, (3)当dimV2dimV2.当dimV3=n时, 依次类推, 由于dimV1，dimV2，dimV3，…单调递增, 所以进行有限步后可得dimVl=n, 从而 四、Frame方法设n阶矩阵A的特征多项式为 记A的n个特征值为l1,l2,…,ln(重特征值重复编号). 令 则有Newton公式 (12)根据式(9)建立Frame算法如下: (13）定理11 由Frame算法(13)可得以下结论:(1)j(l)中的系数ai=-pi (i=1,2,…,n)(2)Bn=O;(3)当A可逆时, A-1= Bn-1.定理12 如果Frame算法(13)中的矩阵B1,B2,…,Bn-1使得 (14)则Qk的非零列向量时A的对应于特征值lk的特征向量. 定理13 如果A的最小多项式m(l)=j(l), 则式(11)成立. 五、Samuelson方法以下利用矩阵的初等行变换方法, 计算n阶矩阵A的特征多项式j(l)的诸系数. 在一些情况下, 该算法的结果可能失真, 因此需要对计算结果进行检验. 对矩阵A=(aij)n‰n进行分块 , (15)并设R¹0T (否则, a11是A的一个特征值, 只要计算M的特征值即可). 构造n‰(2n)矩阵 （16）并对B进行初等行变换, 如果将B1处的最后一行化为(0,…,0), 且B1处的前n-1行能够呈上三角(主对角线上的元素不等于零), 则B2处的最后一行成为(1,q1,…,qn). 构造多项式 一般地, f(l)就是j(l). 定理14 设A的分块形式如式(13), 且R¹OT, 则RMn-1可由R,RM,…,RMn-2线性表示. 六、矩阵特征值与奇异值的关系性质1 若AÎCn×n是正规矩阵,则A的奇异值满足si(A)= |li(A)|, i = 1, 2, …, n.证明：易知存在酉矩阵U, 使得 [1]其中, l1 , l2 ,……, ln 是A 的n 个特征值. 上式取共轭转置得 从而， 所以， 对于正规矩阵, 其谱范数等于谱半径. 需要指出, 对于一般矩阵, 奇异值与特征值之间的关系就不是这么简单了.下面考察几个简单例子.例1 设则 所以说明一般矩阵的奇异值与其特征值的模不相同(对其任何排列), 谱范数不等于谱半径.例2 设 则 所以，让k趋于无穷大,可知r(A)=max{|l|:lÎ矩阵A的特征值}中的不等号可以严格成立, 并且对任意充分大的正常数c,存在矩阵A,使得‖A‖2³cr(A).这说明我们不能通过特征值的有界性来判定矩阵序列的有界性. 下面给出一个类似于例2 的非奇异矩阵的例子.例3 设 则 由特征方程 解得 所以，当k®¥时， 性质2 设矩阵AÎ Cn × n非奇异, A 的奇异值为s1≥s2≥…≥sn>0, 则A- 1 的奇异值满足 >0特别的有 证明：由奇异值分解定理可知, 存在酉矩阵U和V, 使得则 且V-1和U-1仍然是酉矩阵. 所以, A-1的奇异值为. 小结本文先引入矩阵的特征值与奇异值, 而后深入研究了求解特征值的五种解法, 并举例研究了矩阵特征值与奇异值之间的关系. 参考文献[1]徐树方. 矩阵计算的理论与方法[M] . 北京: 北京大学出版社, 1995.[2]张凯院 徐仲.数值代数(第二版): 科学出版社[3]北京大学数学系. 1995. 高等代数(第二版). 北京：高等教育出版社[4]蔡大用. 1987. 数值代数. 北京：清华大学出版社[5]蔡大用, 白峰衫. 1997. 高等数值分析. 北京：清华大学出版社[6]解学书. 1986. 最优控制. 北京：清华大学出版社[7]古以熹.矩阵特征值的分布[J].应用数学学报，1994，4；501-511[8]逄明贤.矩阵谱论.长春:吉林大学出版社1989,47[9]Golub G.H.,Van Loan C.F.矩阵计算(袁亚湘等译).北京:科学出版社,2001[10]黄廷祝，游兆永．矩阵最小奇异值下界的估计［J］． 计算数学， 1997(4) : 359-364[11]徐仲, 张凯院, 路全. 1999. TOEPLITZ矩阵类的快速算法. 西安：西北工业大学出版社[12]Gohberg I, Kailath T, Koltracht I. 1986. Efficient solution of linear systems of equations with recursive. Linear Algebra Appl., 80: 81～113[13]Hou-Biao Li,Ting-Zhu Huang,An improvement on Ky Fan theorem of matrix eigenvalues.Computers and Mathematics with Application,2005,49:789-803[14]C.R.Johnson,A Gersgorin-type lower bound for the smallest singular value,Linear Algebra Appl,1989,112:1-7[15]Liqun Qi.Some simple Estimation for Singular Values of a Matrix.Linear Algebra Appl.,1984,56:105-119 Matrix eigenvalues research method Student: maxiaona teacher: wangchuanlongAbstract The matrix of the singular value and characteristic value is an important issue in matrix analysis. This paper studies the use of power method, Krylor method, Lanczos method, Frame method, Samuelson method of characteristic value solution theory, And based on this analysis, for example the singular value and characteristic value of the relationship.Key words singular values; eigenvalues; existence; decision theorems; spectrum norm; spectral radius Taiyuam Normal University the Department of Mathematic Shanxi Taiyuan 030012。