计算方法第七章(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 whileer errtelk 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 则收敛速度会很慢 用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 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