计算方法第七章(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 ererrtel 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）确定计算精度10E-m （2）对矩阵 取加速因子 进行加速 （3）判断矩阵 的最后一行非对角元素是否小于要求的精 度，如果不小于，继续加速迭代，如已经小于精度，停止计 算，并划掉矩阵的最后一行和最后一列，产生一个子矩阵 （4）对子矩阵重复进行上面的加速计算 一个新的计算方案： 对于矩阵 取变换 于是，取R为Householder矩阵，则 化为除第一个分量外 其余分量为零的向量。 如此下去，可以将矩阵 A 化为拟上三角矩阵。 利用前面带原点位移的QR 方法的性质，可以看出，用拟上三 角矩阵进行原点位移的QR 方法计算是非常方便的。 QR 方法的总结： （1）利用Householder矩阵，将矩阵 A 相似于拟上三角矩阵 （尤其，对于对称矩阵可以化为三对角矩阵） （2）利用带原点位移的QR 方法构造矩阵