计算方法第七章(r).ppt

单击此处编辑母版标题样式,,单击此处编辑母版文本样式,,第二级,,第三级,,第四级,,第五级,,,*,第七章 矩阵的特征值与特征向量,,第一节 乘幂法与反幂法,,1.1 乘幂法：,用于求矩阵的模（绝对值）最大的特征值,记矩阵,A,,的,特征值为：,,相应的特征向量为：,,任取非零,向量 ，记,,,,则有：,,,,,这里， 表示向量的,第,i,,个分量,,具体计算时，对于任意取的初始向量，按以下格式计算：,,则有,,例子：求矩阵的模最大特征值及其特征向量,,,,,,,计算结果,,,程序,,%,用乘幂法计算矩阵模最大的特征值和相应的特征向量,,A=[-1,2,1;2,-4,1;1,1,-6],,z0=[1,1,1]';,,errtel=1e-6; er=1;,,k=0;,,while er>errtel,,k=k+1;,,yk=A*z0;,,[c,p]=max(abs(yk));,,mk=yk(p),,zk=yk/mk;,,er=norm(zk-z0);,,z0=zk;,,end,,k,mk,zk,,1.2 加速技术：,,显然，乘幂法的收敛速度依赖 ，如此比值接近1，则收敛速度会很慢。

用,A－ pI,,代替,A,，,进行,乘幂法迭代速度可能会大大加快这叫原点移位法埃特金加速：,,可以证明：乘幂法线性收敛,,,,,称为收敛率,,由于 线性收敛于 ，于是可以对之进行埃特金加速，,,,,,,以上是,计算特征向量,的埃特金加速，同样可以得到关于,计算特,,征值,的埃特金加速，,,1.3,反幂法,,如果,A,非奇异，用其逆矩阵代替,A,进行乘幂,法，称为,反幂法,逆矩阵的特征值与,A,互为倒数即为：,,,用,A,的逆进行乘幂法，得到,,迭代格式为：,,为避免矩阵的求逆运算，通常也采取如下的算法：,,,,,,每次迭代需要解 ，为此，可,将,A,,进行,LR,分解，则每次迭代只需解两个三角方程组,,,,最后求得：,,反幂法的一个主要应用是已知矩阵的近似特征值后，求其特征向量如果已求得矩阵某个特征值 的近似值 ，则,,,于是，用反幂法可以求出 的按模最小特征值及相应,,的特征向量此时，迭代为：,,通常，初值选为：,,,,,,这里，矩阵,L,为 分解中的单位下三角矩阵。

第二节 对称矩阵的雅可比方法,,两个重要的基本性质：,,（1）如,A,为实对称矩阵，则一定存在正交矩阵,Q,，,使之相似于一个对角矩阵，而该对角矩阵的对角元正是,A,的特征值2）一个矩阵左乘一个正交矩阵或右乘一个正交矩阵，其,E,范数不变下面的矩阵是,一个,n,阶正交矩阵：,(,p,),(,q,),,2.1 雅可比算法,,算法的思想：,,设,A,,为对称矩阵，选出,A,,的除对角元外的所有元素中绝对值最大的一个，然后用前一页中的正交矩阵将,此元化为零,如此，产生一个新的阵，然后再重复上面的步骤，直到最后将,A,化为对角矩阵，则对角元就是所要求的特征值！,,将上述过程数学化，首先，记 ，则,选取,,，使得,,第,k,步,迭代矩阵的元素为：,,,,,,,,,,,为使 ，必须,,在这里，我们通常，限制 ，如果 ，,,当 时，取 ，当 时，,,在具体计算第,k,步,迭代矩阵的元素时，需要计算正弦值和余弦值，通常按如下步骤计算：,,实际计算中，一般预先给,一个计算精度,,，当第,m,,步满足,,,,停止计算，这时，,,,则对角阵的对角元为特征值近似值，矩阵,P,,的列向量为特征向量近似值。

实际计算中，矩阵,P,,是按如下步骤计算：,,,最后，雅可比方法的计算步骤可以归纳为：,,（1）确定非对角绝对值最大元位置（,p,，,q,），,并,计算,sin,和,cos,的值；,,（2）计算迭代矩阵的元素；,,（3）计算特征向量；,,（4）与计算精度进行比较，以决定是否终止计算，并输出特征值和特征向量第三节,QR,分解方法,,3.1,QR,分解,,设,u,,为,n,维实单位向量，称下面矩阵为,Householder,矩阵：,,,容易验证,Householder,矩阵为正交阵，同时又是对称阵：,,,对任意的向量,x,,以及单位向量,g,，,存在,Householder,矩阵，使,,,,特别，取,g,=,e,= ( 1 , 0 , …… , 0),,将,矩阵,A,,记为,,,于是，可以求得,Householder,矩阵，将,A,,的第一个列向量化简对矩阵 又再重复前面的过程，即求出,Householder,矩阵,,,于是，我们记,,,,则,,,如此一直下去，最后得到,,,记 ，注意到这是一个正交矩阵，令,,,3.2 基本,QR,方法,,利用矩阵的,QR,分解，立即可以得到矩阵的一系列相似矩阵,,,,,,,,其中， 为正交矩阵， 为上三角矩阵， 称为,QR,序列,,最后，可以证明， 的对角线下面的元素（不包括对角线）收敛于零，由相似关系，不难推出其对角线上的元素收敛到矩阵,A,,的,特征值！,,最后，要指出的是，当用,QR,方法求出特征值后（准确讲，是特征值的近似值），我们可以用,反幂法,求出,更加精确的特征值，更为重要的是可以求出相应的特征向量,。

3.3 带原点位移的,QR,方法,,为加速收敛，每次选取位移 ，作,,,,该矩阵序列有如下性质：,,（1）,,（2）如 为拟上三角，则 也为拟上三角矩阵（拟上三角矩阵指的是次对角线下的元素为零的矩阵）,,（3）如取位移 为 ，则 最后一行非对角元二阶收敛于零（特别对于对称矩阵，能达到三阶收敛），其余次对角元收敛于零的速度会慢一些加速技术下的算法：,,（1）确定计算精度10,E-m,,（2）,对矩阵 取加速因子 进行加速,,（3）判断矩阵 的最后一行非对角元素是否小于要求的精度，如果不小于，继续加速迭代，如已经小于精度，停止计算，并划掉矩阵的最后一行和最后一列，产生一个子矩阵,,（4）对子矩阵重复进行上面的加速计算,,一个新的计算方案：,,对于矩阵,,,,,,取变换,,于是，取,R,为,Householder,矩阵，则 化为除第一个分量外其余分量为零的向量如此下去，可以将矩阵,A,,化为拟上三角矩阵利用前面,带原点位移的,QR,方法的性质，可以看出，用拟上三角矩阵进行,原点位移的,QR,方法计算是非常方便的。

QR,方法的总结：,,（1）利用,Householder,矩阵，将矩阵,A,,相似于拟上三角矩阵（尤其，对于对称矩阵可以化为三对角矩阵）,,（2）利用,带原点位移的,QR,方法构造矩阵序列,,（3）,对矩阵 取加速因子 进行加速,,（4）判断矩阵 的最后一行非对角元素（由于是拟上三角矩阵，只有一个元素 ）是否小于要求的精度,,（5）如已经小于精度，停止计算，并划掉矩阵的最后一行和最后一列，产生一个子矩阵，对子矩阵重复进行上面的加速计算。