特征值问题的计算方法.ppt

第八章特征值问题的计算方法 ComputationalMethodofEigenvalueProblem 本章主要介绍矩阵的特征值和特征向量的计算方法 特征值和特征向量的基本概念与性质 1基本概念与性质 若的所有特征值都是半单的 则称是非亏损的 相似矩阵有相同的特征值 设 本章QR算法的基本思想 说明 对称矩阵的特征值总是良态的 注意 实际问题中矩阵一般都是由计算或实验得到 本身必然存在误差 不妨假设 2幂法与反幂法 PowerMethodandReversedPowerMethod 幂法是计算一个矩阵的模最大的特征值和对应的特征向量的一种迭代方法 又称为乘幂法 一 幂法的基本思想与算法 假设是可对角化的 即存在如下分解 其中 不妨假设 对于 说明 当k充分大时 的一个近似特征向量为 特征向量可以相差一个倍数 因为向量中含有未知量 实际不能计算 但我们关心的仅是的方向 故作如下处理 令 其中为的模最大分量 幂法迭代算法 设和均收敛 由算法知 解 Step1 Step2 Step3 Step4 特征值及相应的特征向量精确值为 幂法的收敛性 证明 设有如下Jordan分解 是属于的Jordan块构成的块上三角矩阵 是半单的特征值 令 将和如下分块 记 是属于的一个特征向量 几点说明 幂法的收敛速度取决于的大小 幂法可以计算第二个模最大特征值 常用的方法 降阶方法 收缩技巧 设已经计算出模最大特征值及其特征向量 对向量 采用复的Household变换计算酉矩阵 其中是n 1阶方阵 二 反幂法的基本思想与算法 反幂法是求一个矩阵的模最小的特征值和对应的特征向量的一种迭代方法 又称为反迭代法 设 则 不妨假设的特征值为 则的特征值为 反幂法算法 若和均收敛 由幂法知 带位移的反幂法 实际应用中 反幂法主要用于求特征向量 且用某种方法已经得到的特征值的近似值 对矩阵采用反幂法迭代格式为 记 假设的特征值满足 求解方程组化为 带位移的反幂法迭代格式 设矩阵存在Doolittle分解 解 其中 Step1 反幂法具有一次 迭代性 Step2 所求近似特征向量为 3Jacobi方法 Jacobi法 计算实对称矩阵全部特征值和相应特征向量 基本思想 对 存在正交矩阵 满足 记 则 正交相似变换求法 通过Givens变换来实现 经典Jacobi方法 设 令 非对角 范数 例如取 记 首先由确定 其次确定旋转平面 由F 范数的正交不变性 设经过一次正交相似变换后变为矩阵 注意到 经典Jacobi方法的迭代格式 证明见教材 经典Jacobi方法的迭代算法 需比较个元素 习惯上称次Jacobi迭代为一次 扫描 循环Jacobi方法 自然顺序 按照自然顺序的循环Jacobi方法是渐进平方收敛的 4QR方法 基本思想 QR方法的迭代格式 设 令 对矩阵进行QR分解 再对矩阵进行QR分解 一 QR基本迭代方法 一般地有 QR方法的迭代算法 由迭代格式同时还得到 记 代入 等式两端同时右乘 记 其中是的第一列 是的相应元素 QR方法的收敛性 证明 令 则有 且 当m充分大时 存在唯一QR分解 且 QR分解 记的QR分解为 为保证上述QR分解中上三角矩阵的对角元为正 令 由QR分解唯一性知 代入 趋于上三角阵 实QR迭代格式 设 二 实Schur标准形 见文献 13 称下述形状的矩阵为上Hessenberg矩阵 三 上Hessenberg化 基本思想和约化过程 记矩阵 下面采用Householde变换寻找 Step1选取Householde变换 使得 其中 令 其中 Step2选取Householde变换 使得 其中 令 令 其中 按照前述方法 经过n 2步后 可以得到 记 则 称分解式为矩阵的上Hessenberg分解 上Hessenberg分解算法 8 4 1 然后对上Hessenberg矩阵进行QR迭代 上Hessenberg矩阵的QR迭代算法 实用的QR迭代算法 仅计算特征值 四 三对角化 对称矩阵的上Hessenberg化 设为对称矩阵 的上Hessenberg分解为 其中为对称三对角矩阵 Step1选取Householde变换 使得 其中 令 其中 主要工作量在于计算 减少运算量 三对角分解算法 8 4 2 五 隐式对称的QR迭代方法 仅适用于对称矩阵 带原点位移的QR迭代格式 迭代过程中产生的矩阵序列均为三对角矩阵 的选取方法 著名的Wilkinson位移 一种简单的取法 记矩阵 令 取 收敛性见文献 4 隐式对称QR迭代的实现方法 设一次对称QR迭代的格式为 例如 n 4时 Wilkinson位移隐式对称分解迭代算法 8 4 3 终止法则 的下三角元素均趋于零 注 此算法仅给出了1次的迭代过程