数值分析-第8-9讲-QR方法.ppt

朱立永 北京航空航天大学数学与系统科学学院 数值分析 Email numerical analysis Password beihang答疑时间 星期四下午2 30 5 30答疑地点 主216 第八讲矩阵特征值与特征向量的计算 2 Jacobi方法和QR方法 第三章矩阵特征值与特征向量的计算 常用的求特征值的方法有 幂法与反幂法Jacobi法QR方法 上次课内容回顾 幂法可以用来求矩阵模最大的特征值和特征向量 反幂法可以用来求矩阵模最小的特征值和特征向量 理论上可以用带原点平移的反幂法求得矩阵所有特征值和特征向量 在用幂法与反幂法求矩阵特征值和特征向量时 初始值u0的第一个分量不要为零 当 1 2 但 1 2时 直接幂法失败 当 n 1 n 但 n 1 n时 直接反幂法失败 当是多重特征值时 幂法和反幂法仍有效 Jacobi法 只适用于实对称方阵可以求出所有特征值和特征向量 矩阵的两个重要的基本性质 1 如A为实对称矩阵 则一定存在正交矩阵Q 使之相似于一个对角矩阵 而该对角矩阵的对角元正是A的特征值 2 一个矩阵左乘一个正交矩阵或右乘一个正交矩阵 其F范数 Frobenius 不变 Jacobi法的基本原理 Jacobi法基于的原理是 对一个实对称矩阵A一定存在一个正交矩阵R R 1 RT 使得RTAR D 其中D diag d1 d2 dn 我们有D的对角元素即为A的特征值 对应的R的行向量即为相应的特征向量 思路 通过一系列的旋转变换 正交变换 把A中非对角线上的非零元变为零 下面的矩阵是一个n阶正交矩阵 p q 旋转变换Upq其元素特点 如果apq 0那么我们可以选取一个 A 1 仍为实对称矩阵 使得 A 1 的元素为 选取 满足 我们就有 Jacobi法的算法 令k 1 R 1 I 给定矩阵A A 1 收敛条件 找绝对值最大的计算 sin 和cos 其中 满足计算A k 1 计算R k 1 如果则停止 否则返回第2步 Jacobi算法的收敛性 定理 设A是实对称矩阵 由Jacobi方法第k次迭代得到的矩阵记为A k 记 则有 成立 QR方法 cf 矩阵计算 G H Golub F VanLoan袁亚湘等译 第五章 5 1 5 2节 QR方法是计算中小型矩阵特征值和特征向量的有效方法之一 QR方法最重要的一步是对A进行正交分解使得A QR 其中Q为一特殊正交矩阵 理论上 QR方法可以应用于任何矩阵 但对以下几类矩阵效率很高 1 对称三对角矩阵 2 Hessenberg矩阵 3 对称带状矩阵 QR方法的理论依据 定理 实Schur分解定理 设A是一个n阶实方阵 那么存在一个正交矩阵Q使得A相似于 其中对角块为一阶或二阶方阵 每一个一阶对角块对应于A的一个实特征值 每一个二阶对角块的两个特征值是A的一对共轭复特征值 QR方法的一般形式 由于产生的矩阵序列 Ak 中的每一个矩阵都与A有相同的特征值 要解决的问题是上述算法的工作量和Q的选择 定理 对任意实方阵A 由QR方法产生的矩阵序列 Ak 本质上收敛于分块上三角矩阵 对角块以上的元素可能不收敛 其中对角块为一阶或二阶方阵 每一个一阶对角块对应于A的一个实特征值 每一个二阶对角块的两个特征值是A的一对共轭复特征值 Q的选择 Householder矩阵 镜面映象变换 定义 设 为n维单位向量 即 T 1 H I 2 THouseholder变换 矩阵 1 Householder矩阵是正交矩阵 2 3 记S为与w垂直的平面 则几何上x与y Hx关于平面S对称 事实上 由 几何意义 引理3 1 设有非零向量s和单位向量e 则必存在Householder矩阵H使得Hs e 其中 是实数且 与平面旋转不同的是 镜面反射变换可成批的消去向量的非零元 定理 设A是一个n阶实方阵 那么A可分解为一个正交矩阵Q和一个上三角矩阵R的乘积 A QR 减少QR算法的工作量 矩阵的拟上三角化 把A变成Hessenberg矩阵 拟上三角矩阵 的目是减少QR方法的计算量 把A变成Hessenberg矩阵 拟上三角矩阵 能够减少QR方法计算量的主要原因是对拟上三角矩阵的QR分解时 Q一定是拟上三角矩阵 RQ Ak 1 的乘积为拟上三角矩阵 QR方法 定理 对任意实方阵A 由QR方法产生的矩阵序列 Ak 本质上收敛于分块上三角矩阵 对角块以上的元素可能不收敛 其中对角块为一阶或二阶方阵 每一个一阶对角块对应于A的一个实特征值 每一个二阶对角块的两个特征值是A的一对共轭复特征值 QR方法的加速 带原点位移的QR方法 尽管通过Householder矩阵已把矩阵A相似地变成为Hessenberg矩阵从而已减少了QR方法的不少工作量 但上述方法工作量仍太大 其中主要工作量在第二步的QR分解和收敛速度问题 带原点位移的QR方法为加速收敛 每次选取位移 作该矩阵序列有如下性质 1 2 如为拟上三角 则也为拟上三角矩阵 拟上三角矩阵指的是次对角线下的元素为零的矩阵 3 如取位移为 则最后一行非对角元二阶收敛于零 特别对于对称矩阵 能达到三阶收敛 其余次对角元收敛于零的速度会慢一些 加速技术下的算法 1 确定计算精度10E m 2 对矩阵取加速因子进行加速 3 判断矩阵的最后一行非对角元素是否小于要求的精度 如果不小于 继续加速迭代 如已经小于精度 停止计算 并划掉矩阵的最后一行和最后一列 产生一个子矩阵 4 对子矩阵重复进行上面的加速计算 带原点位移的QR方法的总结 1 利用Householder矩阵 将矩阵A相似于拟上三角矩阵 尤其 对于对称矩阵可以化为三对角矩阵 2 利用带原点位移的QR方法构造矩阵序列 3 对矩阵取加速因子进行加速 4 判断矩阵的最后一行非对角元素 由于是拟上三角矩阵 只有一个元素 是否小于要求的精度 5 如已经小于精度 停止计算 并划掉矩阵的最后一行和最后一列 产生一个子矩阵 对子矩阵重复进行上面的加速计算 QR方法的