数值分析幂法和反幂法

精品文档 1欢迎下载 题 目 幂法和反幂法求矩阵特征值幂法和反幂法求矩阵特征值 具 体 内 容 随机产生一对称矩阵 对不同的原点位移和初值 至少取 3 个 分别使用幂 法求计算矩阵的主特征值及主特征向量 用反幂法求计算矩阵的按模最小特征 值及特征向量 并比较不同的原点位移和初值说明收敛 要 求 1 认真读题 了解问题的数学原形 2 选择合适问题求解的数值计算方法 3 设计程序并进行计算 4 对结果进行解释说明 采 用 方 法 及 结 果 说 明 对于幂法和反幂法求解矩阵特征值和特征向量的问题将从问题分析 算 法设计和流程图 理论依据 程序及结果进行阐述该问题 一 问题的分析 求 n 阶方阵 A 的特征值和特征向量 是实际计算中常常碰到的问题 如 机械 结构或电磁振动中的固有值问题等 对于 n 阶矩阵 A 若存在数 和 n 维向量 x 满足 Ax x 1 则称为矩阵 A 的特征值 x 为相应的特征向量 由高等代数知识可知 特征值是代数方程 I A a a a 0 2 n 1 1 n 1 n n 的根 从表面上看 矩阵特征值与特征向量的求解问题似乎很简单 只需 求解方程 2 的根 就能得到特征值 再解齐次方程组 I A x 0 3 的解 就可得到相应的特征向量 上述方法对于 n 很小时是可以的 但当 n 稍大时 计算工作量将以惊 人的速度增大 并且由于计算带有误差 方程 2 未必是精确的特征方 程 自然就不必说求解方程 2 与 3 的困难了 幂法是一种计算矩阵 主特征值 矩阵按模最大的特征值 及对应特征向量的迭代方法 特别是 用于大型稀疏矩阵 反幂法是计算海森伯格阵或三角阵的对应一个给定近 似特征值的特征向量的有效方法之一 精品文档 2欢迎下载 二 算法设计及流程图 1 幂法算法 1 取初始向量 u 例如取 u 1 1 1 置精度要求 置 k 1 0 0 T 2 计算 v Au m max v u v m k 1 k k k k k k 3 若 m m 则停止计算 m 作为绝对值最大特征值 u作 k1 k k1 k 为相应的特征向量 否则置 k k 1 转 2 2 反幂法算法 1 取初始向量 u 例如取 u 1 1 1 置精度要求 置 k 1 0 0 T 2 对 A 作 LU 分解 即 A LU 3 解线性方程组 Ly u Uv y k 1 k k k 4 计算 m max v u v m k k k k k 5 若 m m 则停止计算 1 m 作为绝对值最小特征值 u作 k1 k kn k 为相应的特征向量 否则置 k k 1 转 3 精品文档 3欢迎下载 幂法流程图 开始 输入 A m u index pow A 1e 6 k 0 m1 v A u vmax i max abs v m v i u v m abs m m1 1e 6 index 1 break 输出 m u index 结束 m1 m k k 1 反幂法流程图 精品文档 4欢迎下载 开始 输入 A m u index pow inv A 1e 6 k 0 m1 0 v invA u vmax i max abs v m v i u v m abs m m1 1 2 n 则计算最大特征值与特征向量的迭代格式为 v Au m max v u v m 1 k 1 k k k k k k 其中 max v 表示向量 v绝对值的最大分量 k k 2 对于幂法的定理 按式 1 计算出 m和 u满足 k k m u k lim k1 k lim k max 1 1 x x 二 反幂法算法的理论依据及推导 反幂法是用来计算绝对值最小的特征值忽然相应的特征向量的方法 是对 幂法的修改 可以给出更快的收敛性 1 反幂法的迭代格式与收敛性质 设 A 是非奇异矩阵 则零不是特征值 并设特征值为 1 2 1 n n 则按 A的特征值绝对值的大小排序 有 1 n 1 1 1 n 1 1 对 A实行幂法 就可得 A的绝对值最大的特征值 1 和相应的特征向量 1 1 n 即 A 的绝对值最小的特征值和相应的特征向量 由于用 A代替 A 作幂法计算 因此该方法称为反幂法 反幂法的迭代格 1 式为 v Au m max v u v m 2 k1 1 k k k k k k 精品文档 6欢迎下载 2 对于反幂法的定理 按式 2 计算出的 m和 u满足 k k m u k lim k n 1 k lim k max n n x x 在式 2 中 需要用到 A 这给计算带来很大的不方便 因此 把 2 式 1 的第一式改为求解线性方程组 A v u 3 k 1 k 但由于在反幂法中 每一步迭代都需求解线性方程组 3 式 迭代做了大量 的重复计算 为了节省工作量 可事先把矩阵 A 作 LU 分解 即 A LU 所以线性方程组 3 改为 Ly u Uv y k 1 k k k 四 算法程序设计代码 幂法程序 在 matlab 中建立一个 M 文件并保存 精品文档 7欢迎下载 pow m function m u index k pow A u ep it max if nargin 4 it max 1000 end if nargin 3 ep 1e 5 end n length A index 0 k 0 m1 0 m0 0 I eye n T A m0 I while k it max v T u vmax i max abs v m v i u v m if abs m m1 ep index 1 break end m m m0 m1 m k k 1 end 在 matlab 输入面板 输入 A rand 4 产生一个 4 维随机矩阵 B A A u 1 1 1 1 设立初始向量 m u index k pow B u ep it max 最多可省略 2 个参数 程序结束 在 M 文件中可以通过改变 m0 的值改变原点位移 从而达到原点位移加速 反幂法程序设计代码 在 matlab 中建立一个 M 文件并保存 pow inv m function m u index k pow inv A u ep it max if nargin 4 it max 1000 end if nargin 3 精品文档 8欢迎下载 ep 1e 5 end n length A index 0 k 0 m1 0 m0 0 I eye n T A m0 I invT inv T while k it max v invT u vmax i max abs v m v i u v m if abs m m1 B rand 4 A B B A 0 2675 0 5776 0 6344 1 3130 0 5776 1 1503 0 7641 0 1367 0 6344 0 7641 0 0257 0 4193 1 3130 0 1367 0 4193 1 2248 u 1 1 1 1 m u index k pow A u m 精品文档 9欢迎下载 2 6813 u 0 8576 0 6934 0 5623 1 0000 index 1 k 49 修改 M0 1e 3 m 2 6814 u 0 8576 0 6934 0 5623 1 0000 index 0 k 1001 修改 M0 0 此时为幂法 m 精品文档 10欢迎下载 2 6815 u 0 8576 0 6935 0 5623 1 0000 index 1 k 10 修改 U 1 2 3 4 修改 M0 1e 4 m 2 6813 u 0 8576 0 6934 0 5623 1 0000 index 1 k 9 修改 M0 1e 3 m 精品文档 11欢迎下载 2 6805 u 0 8576 0 6934 0 5622 1 0000 index 1 k 7 修改 M0 0 m 2 6814 u 0 8576 0 6934 0 5623 1 0000 index 1 k 9 修改 U 3 5 6 7 修改 M0 1e 4 精品文档 12欢迎下载 m 2 6819 u 0 8577 0 6937 0 5624 1 0000 index 1 k 7 修改 M0 1e 3 m 2 6814 u 0 8576 0 6934 0 5623 1 0000 index 0 k 精品文档 13欢迎下载 1001 修改 M0 0 m 2 6820 u 0 8577 0 6937 0 5624 1 0000 index 1 k 7 总结以上 幂法如下 Um0muindexk 0 00012 6813 0 8576 0 6934 0 5623 1 0000 149 0 0012 6814 0 5876 0 6934 0 5623 1 0000 01001 1 1 1 1 02 6815 0 8576 0 6935 0 5623 1 0000 110 0 00012 6813 0 8576 0 6934 0 5623 1 0000 19 0 0012 6805 0 8576 0 6934 0 5622 1 0000 17 1 2 3 4 02 6814 0 8576 0 6934 0 5623 1 0000 19 3 5 6 7 0 00012 6819 0 8577 0 6937 0 5624 17 精品文档 14欢迎下载 1 0000 0 0012 6914 0 8576 0 6934 0 5623 1 0000 01001 02 692 0 8577 0 6937 0 5624 1 0000 17 反幂法结果显示 在 m0 为 0 时 精品文档 15欢迎下载 M0 0 001 U 1 1 1 1 精品文档 16欢迎下载 精品文档 17欢迎下载 M0 0 1 u 1 1 1 1 精品文档 18欢迎下载 M0 0 u 1 3 5 7 精品文档 19欢迎下载 M0 0 1 u 1 3 5 7 精品文档 20欢迎下载 M0 0 5 u 1 3 5 7 精品文档 21欢迎下载 M0 0 u 2 3 4 5 精品文档 22欢迎下载 M0 0 1 u 2 3 4 5 精品文档 23欢迎下载 M0 0 7 u 2 3 4 5 精品文档 24欢迎下载 综上 反幂法结果如下 um0muindexk 1 1 1 1 0 10 3847 0 8996 1 0000 0 2726 0 2364 115 0 0010 3847 0 8996 1 0000 0 2726 0 2364 116 00 3847 0 8996 1 0000 0 2726 0 2364 116 1 3 5 7 0 50 3847 0 8995 1 0000 0 2726 0 2364 127 0 10 3847 0 8996 1 0000 0 2726 0 2364 117 00 3847 0 8996 1 0000 0 2726 0 2364 120 2 3 4 5 0 70 7091 0 6962 0 4497 0 2196 1 0000 15 0 10 3847 0 8995 1 0000 0 2726 0 2364 117 00 3847 0 8996 1 0000 0 2726 0 2364 119 五 结果分析 采用幂法和反幂法 求矩阵的最大和最小特征