第9章--矩阵特征值的数值解法.doc

第9章 矩阵特征值的数值解法9.1 引言矩阵特征值问题有广泛的应用背景. 例如动力系统和结构系统中的振动问题、电力系统的静态稳定分析上、工程设计中的某些临界值的确定等，都归结为矩阵特征值问题. 数学中诸如方阵的对角化及解微分方程组等问题，都要用到特征值的理论.本章介绍n阶实矩阵的特征值与特征向量的数值解法.定义9.1.1已知n阶实矩阵，如果存在常数和非零向量x，使 或 (9.1.1)那么称为A的特征值(eigenvalue)，为的相应于的特征向量(eigenvector). 多项式 (9.1.2)称为特征多项式(characteristic polynomial)， (9.1.3)称为特征方程(characteristic equation).注式(9.1.3)是以为未知量的一元n次代数方程，是的n次多项式. 显然，的特征值就是特征方程(9.1.3)的根. 特征方程(9.1.3)在复数范围内恒有解，其个数为方程的次数(重根按重数计算)，因此n阶矩阵在复数范围内有n个特征值. 除特殊情况 (如或为上(下)三角矩阵)外，一般不通过直接求解特征方程(9.1.3)来求的特征值,原因是这样的算法往往不稳定.在计算上常用的方法是幂法与反幂法和相似变换方法. 本章只介绍求矩阵特征值与特征向量的这两种基本方法. 为此将一些特征值和特征向量的性质列在此处.定理9.1.2设阶方阵的特征值为，那么(1) ;(2) .定理9.1.3如果是方阵的特征值，那么(1) 是的特征值，其中是正整数;(2) 当是非奇异阵时，是的特征值.(3) 是的特征值，其中是多项式.定义9.1.4设都是阶方阵. 若有阶非奇异阵，使得，则称矩阵与相似(similar)，称为对进行相似变换(similarity transformation)，称为相似变换矩阵(similarity transformation matrix).定理9.1.5若矩阵与相似，则与的特征值相同.定理9.1.6 如果是阶正交矩阵，那么(1) ，且或;(2) 若，则, 即.定理9.1.7 设是任意阶实对称矩阵，则(1)的特征值都是实数；(2)有个线性无关的特征向量.定理9.1.8 设是任意阶实对称矩阵，则必存在阶正交矩阵，使得，其中是以的个特征值为对角元素的对角矩阵.定理 (圆盘定理)矩阵的任意一个特征值至少位于复平面上的几个圆盘，中的一个圆盘上。

9.2 幂法与反幂法9.2.1幂法及其加速9.2.1.1 幂法幂法是计算矩阵按模最大特征值(largest eigenvalue in magnitude)及相应特征向量的迭代法. 该方法稍加修改，也可用来确定其他特征值. 幂法的一个很有用的特性是：它不仅可以求特征值，而且可以求相应的特征向量. 实际上，幂法经常用来求通过其他方法确定的特征值的特征向量.下面探讨幂法的具体过程.设矩阵的n个特征值满足, (9.2.1)且有相应的n个线性无关的特征向量，则构成n维向量空间的一组基, 因此. 在中选取某个满足的非零向量.用矩阵同时左乘上式两边，得.再用矩阵左乘上式两边，得.这样继续下去，一般地有(9.2.2)记，则由式(9.2.2)得 (9.2.3)由假设(9.2.1)，结合式(9.2.3)，得 (9.2.4)于是对充分大的k有 (9.2.5)式(9.2.4)表明随着k的增大，序列越来越接近A的对应于特征值的特征向量的倍, 由此可确定对应于的特征向量. 当k充分大时，可得的近似值. 上述收敛速度取决于比值. 事实上，由式(9.2.3)知，.(9.2.6)再由式(9.2.1)得 .(9.2.7)结合式(9.2.6)和式(9.2.7)知，序列收敛速度取决于比值. 下面计算. 由式(9.2.3)知当k充分大时, .结合式(9.2.5)，得.这表明两个相邻向量大体上只差一个常数倍，这个倍数就是A的按模最大特征值. 记, 则有， (9.2.8)即两个相邻的迭代向量所有对应分量的比值收敛到.定义9.2.1上述由已知非零向量及矩阵的乘幂构造向量序列来计算的按模最大特征值及相应特征向量的方法称为幂法(power method)，其收敛速度由比值来确定，越小，收敛越快.注由幂法的迭代过程(9.2.3)容易看出，如果（或），那么迭代向量的各个非零的分量将随着而趋于无穷（或趋于零），这样在计算机上实现时就可能上溢(或下溢). 为了克服这个缺点，需将每步迭代向量进行规范化:记.若存在的某个分量，满足，则记. 将规范化,这样就把的分量全部控制在中. 例如，设，因为的所有分量中，绝对值最大的的是，所以，故. 综上所述，得到下列算法：算法9.2.1 (幂法)设是阶实矩阵，取初始向量，通常取，其迭代过程是：对，有 (9.2.9)定理9.2.1对式(9.2.9)中的序列和有, ， ()其收敛速度由确定.证明 由迭代过程(9.2.9)知, (9.2.11)其中. 若，则由(9.2.3)知：, 代入式(9.2.11)得，(9.2.12)故.(9.2.13)而,(9.2.14)于是,(9.2.15)故.(9.2.16)由式(9.2.6)和式(9.2.7)知：上述收敛速度由确定. 证毕！例9.2.1 用幂法求方阵按模最大特征值及相应的特征向量，要求.解选取初始向量，按式(9.2.9)迭代，结果见表9.2.1.表12345因此，所求按模最大特征值，相应特征向量.事实上，的按模最大特征值，相应特征向量, 故所得结果具有较高的精度..2幂法的加速从上面的讨论可知，由幂法求按模最大特征值，可归结为求数列的极限值，其收敛速度由确定. 当接近时, 收敛速度相当缓慢.为了提高收敛速度, 可以利用外推法进行加速.因为序列的收敛速度由确定，所以若收敛，当充分大时，则有，或改写为,其中是与无关的常数. 由此可得, (9.2.17)这表明幂法是线性收敛的. 由式(9.2.17)知.由上式解出，并记为，即， (9.2.18)这就是计算按模最大特征值的加速公式.将上面的分析归结为如下算法：算法9.2.2 (幂法的加速) 设是阶实矩阵，给定非零初始向量，通常取. 对，用迭代式求出及. 再对，迭代过程为 ()当(是预先给定的精度) 时，迭代结束，并计算；否则继续迭代，直至满足迭代停止条件.有关加速收敛技术，读者请参考文献[11]. 反幂法及其加速反幂法是计算矩阵按模最小特征值及相应特征向量的迭代法,其基本思想是：设矩阵非奇异，用其逆矩阵代替, 矩阵的按模最小特征值就是矩阵的按模最大特征值. 这样用代替做幂法，即可求出的按模最大特征值，也就是矩阵的按模最小特征值；这种方法称为反幂法(inverse power method). 因为矩阵非奇异，所以由可知：. 这说明：如果的特征值满足,(9.2.20)那么的特征值满足, (9.2.21)且对的应于特征值的特征向量也是的对应于特征值的特征向量.由上述分析知：对应用幂法求按模最大的特征值及相应的特征向量，就是求的按模最小的特征值及相应的特征向量. 算法9.2.3 (反幂法)任取初始非零向量，通常取. 为了避免求，对，将迭代过程(9.2.9)改写为: (9.2.22)仿定理9.2.1的证明，可得：定理9.2.2对式(9.2.22)中的序列和有, ()其收敛速度由确定.注按(9.2.22)进行计算，每次迭代都需要解一个方程组. 若利用三角分解法求解方程组，即，其中是下三角矩阵，是上三角矩阵，这样每次迭代只需解两个三角方程组原点平移法为了提高收敛速度，下面介绍加速收敛的原点平移法. 设矩阵，其中是一个待定的常数，与除主对角线上的元素外，其他元素相同.设的特征值为，则的特征值为,且与的特征向量相同. .1 原点平移法的幂法设是的按模最大的特征值，选择，使，及. (9.2.24)对应用幂法，得算法9.2.4对，有 (5)且 ()其收敛速度由确定.由式(9.2.24)知：在计算的按模最大特征值的过程(9.2.25)中，收敛速度得到加速；算法9.2.4又称为原点平移下的幂法(power method with shift)..2原点平移下的反幂法设是的按模最小的特征值，选择，使.(9.2.27)及. (9.2.28)若矩阵可逆，则的特征值为且有. (9.2.29)对应用反幂法，得：算法9.2.5对，有 ()且 ()其收敛速度由确定.由式(9.2.28)知：在计算的按模最大特征值的过程(9.2.30)中，收敛速度得到加速. 算法9.2.5又称为原点平移下的反幂法 (inverse power method with shift).定义9.2.8原点平移下的幂法与原点平移下的反幂法统称为原点平移法.注有的资料上的原点平移法专指原点平移下的反幂法；而有的资料上的反幂法指的就是原点平移下的反幂法.原点平移下的反幂法(算法)的主要应用是：已知矩阵的近似特征值后，求矩阵的特征向量. 其主要思想是：若已知的特征值的近似特征值为，则的特征值就是，其中是的特征值.而按模最小的特征值是，相应的特征向量与的特征向量相同. 利用公式(9.2.30)可求出，并且有，其收敛速度由确定. 于是当充分大时，可取，,只要近似值适当好，收敛速度就很快，往往迭代几次就能得到满意的结果.例9.2.2 已知特征值的近似值，用原点平移下的反幂法求方阵得对应特征值的特征向量.解 取，对矩阵.迭代公式(9.2.30)中的是通过解方程组求得的. 为了节省工作量，可先将进行LU分解.在LU分解中尽量避免较小的当除数，通常可以先对矩阵的行进行调换后再分解. 为此，我们可用乘后再进行LU分解，即， 即 .令 选取，使，得，，.由得，，.由于与的对应分量几乎相等，故的特征值为,相应的特征向量为. 而矩阵的一个特征值为，相应的特征向量为，由此可见得到的结果具有较高的精度.9.3 QR算法上一节我们介绍了求矩阵特征值的幂法和反幂法.幂法主要用来求矩阵的按模最大特征值，而反幂法主要用于求特征向量. 本节将介绍幂法的推广和变形——QR算法，它是求一般中小型矩阵全部特征值的最有效的方法之一，其基本思想就是利用矩阵的QR。