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

第七章矩阵的特征值与特征向量,第一节乘幂法与反幂法1.1乘幂法：用于求矩阵的模（绝对值）最大的特征值。记矩阵A的特征值为：相应的特征向量为：任取非零向量，记则有：这里，表示向量的第i个分量,具体计算时，对于任意取的初始向量，按以下格式计算：,则有,例子：求矩阵的模最大特征值及其特征向量计算结果程序,%用乘幂法计算矩阵模最大的特征值和相应的特征向量A=-1,2,1;2,-4,1;1,1,-6z0=1,1,1;errtel=1e-6;er=1;k=0;whileererrtelk=k+1;yk=A*z0;c,p=max(abs(yk);mk=yk(p)zk=yk/mk;er=norm(zk-z0);z0=zk;endk,mk,zk,1.2加速技术：显然，乘幂法的收敛速度依赖，如此比值接近1，则收敛速度会很慢。,用ApI代替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.1QR分解设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）确定计算精度10E-m（2）对矩阵取加速因子进行加速（3）判断矩阵的最后一行非对角元素是否小于要求的精度，如果不小于，继续加速迭代，如已经小于精度，停止计算，并划掉矩阵的最后一行和最后一列，产生一个子矩阵（4）对子矩阵重复进行上面的加速计算,一个新的计算方案：对于矩阵取变换,于是，取R为Householder矩阵，则化为除第一个分量外其余分量为零的向量。如此下去，可以将矩阵A化为拟上三角矩阵。利用前面带原点位移的QR方法的性质，可以看出，用拟上三角矩阵进行原点位移的QR方法计算是非常方便的。,QR方法的总结：（1）利用Householder矩阵，将矩阵A相似于拟上三角矩阵（尤其，对于对称矩阵可以化为三对角矩阵）（2）利用带原点位移的QR方法构造矩阵序列（3