第4章线性方程组的迭代解法.ppt

线性方程组迭代解法 基础教学部数学教研室彭晓华 立体化教学资源系列 数值分析 线性方程组迭代解法 4 1引言 当A为低阶稠密矩阵时 选主元消去法是有效方法 对于大型稀疏的线性方程组迭代法是合适的 迭代法的基本步骤 2 迭代公式 基本思想 用某种极限过程逐步逼近方程组的精确解 则迭代过程收敛 线性方程组迭代解法 3 计算机算法 本章讨论 2 迭代法的收敛性与收敛速度 误差估计 1 常用的迭代方法及具体形式 4 2基本迭代法 4 2 1雅可比迭代法 一 三阶方程组的雅可比 Jacobi 迭代法 例1解方程组 线性方程组迭代解法 解1 等价形式 2 雅可比迭代公式 3 取初始向量 终止条件 线性方程组迭代解法 迭代计算结果如表 二 n阶方程组的雅可比迭代法 线性方程组迭代解法 第i个方程 对于n阶线性方程组Ax b A为非奇异矩阵 且 等价方程 雅可比 Jacobi 迭代公式 对于 任取x 0 计算得 三 雅可比迭代法的矩阵描述 其中 线性方程组迭代解法 终止条件 为满足精度 的近似值 即 雅可比迭代公式的矩阵形式 线性方程组迭代解法 其中 称为雅可比迭代矩阵 调用函数Jacobi m解例1 线性方程组迭代解法 计算得到 输入 A 1031 2 103 1310 b 14 514 ep 0 005 x k index Jacobi A b ep x 0 9982k 7index 1迭代成功 收敛 1 00010 9982 4 2 2高斯 塞德尔 G S 迭代法 线性方程组迭代解法 解1 等价方程组 2 高斯 赛德尔迭代公式 线性方程组迭代解法 3 取初始向量 线性方程组迭代解法 迭代计算 得 注 高斯 赛德尔迭代法比雅可比迭代法收敛快 线性方程组迭代解法 二 n阶方程组的高斯 塞德尔迭代法 第i个方程 等价方程组 高斯 赛德尔 G S 迭代公式 对于 终止条件 G S迭代的矩阵形式 线性方程组迭代解法 注 1 迭代法的分量形式 用于计算编程 矩阵形式 用于研究迭代序列是否收敛等理论分析 2 Jacobi适合并行计算 不足 需存放两个向量 3 G S迭代法只需一个向量存储空间 三 高斯 塞德尔迭代法的矩阵描述 矩阵表示 调用函数Gauss Seidel m解例1 线性方程组迭代解法 x 0 9998k 4index 1迭代成功 收敛 0 99981 0001 得到 输入 A 1031 2 103 1310 b 14 514 ep 0 005 x k index Gauss Seidel A b ep 4 在某些情况下 G S迭代法加速收敛 但它是一种典型的串行算法 例3分别用雅可比和高斯 赛德尔迭代法解方程组 均取相同初值 1 Jacobi迭代4次达到精度 G S发散 线性方程组迭代解法 2 Jacobi发散 G S发散 3 Jacobi迭代89次达到精度 G S迭代8次达到同样的精度 线性方程组迭代解法 4 Jacobi发散 Jacobi和G S可能同时发散 注 也可能同时收敛 但一个快另一个慢 可能一个收敛而另一个发散 G S迭代10次达到精度 线性方程组迭代解法 4 2 3逐次超松弛 SOR 迭代法 SOR迭代法 G S迭代法基础上 用参数校正残差加速 一 逐次超松弛迭代公式 G S迭代公式中加 减 线性方程组迭代解法 第i个方程的残差 2 为加速收敛 将校正量乘加速因子 有 为松驰因子 称为超松驰因子 20 二 逐次超松弛迭代法的矩阵描述 其中 松弛迭代矩阵 整理得 记作 写成矩阵形式 线性方程组迭代解法 例4用SOR解方程组 取 解方程组的精确解为 取初值 用G S迭代得 线性方程组迭代解法 利用SOR方法 初值 迭代计算结果 线性方程组迭代解法 注 SOR迭代5次 与G S法迭代10次的结果大体相同 SOR方法的松驰因子起到了加速收敛的重要作用 线性方程组迭代解法 注 最佳松驰因子 使迭代收敛最快 记为 特殊情形 若A为对称正定的三对角矩阵时 例方程组 取 精度为 线性方程组迭代解法 4 3迭代法的收敛性 研究 1 收敛性与迭代矩阵关系 2 迭代公式收敛的充要条件 充分条件 3 迭代收敛速度 4 3 1迭代法收敛性判别 迭代法收敛的充要条件 n阶线性方程组 A为非奇异矩阵 且 等价形式为 一 迭代矩阵B 线性迭代公式 线性方程组迭代解法 定理1 迭代法收敛的充分条件 由 定理2 则 收敛 且 二 迭代矩阵的范数 注 迭代矩阵范数小于1是收敛的充分条件 线性方程组迭代解法 迭代法收敛的基本定理 定义1 方阵A的谱半径 定理3 证明 1 充分性 设 因为 2 必要性 若迭代法收敛 根据定理1 因此 三 迭代矩阵的谱半径 迭代法收敛的基本定理 线性方程组迭代解法 证明1 2 Jacobi收敛 G S发散 注 BJ 4 1 利用迭代矩阵的范数不能判别其收敛性 线性方程组迭代解法 4 3 2特殊方程组的迭代法收敛性 定义2 行占优 列占优 对角占优矩阵 一个不等式是严格成立 定义3 可约矩阵 存在置换阵P使 不存在置换阵P使上式成立 不可约矩阵 注 可约阵经过行列重排 求解 化为求解 线性方程组迭代解法 定理4 2 A为弱对角占优阵 且A不可约 则Jacobi和G S收敛 只证明Jacobi Jacobi收敛 例6 解 A严格对角占优 Jacobi和G S收敛 定理5 证明 线性方程组迭代解法 例7 A对称正定 则G S收敛 1 取 2 Jacobi发散 G S收敛 线性方程组迭代解法 定理6 SOR收敛 证明 定理7 A为实对称正定矩阵 则 SOR收敛 定理8 1 A严格对角占优阵 或弱对角占优不可约阵 则解Ax b的SOR收敛 2 线性方程组迭代解法 4 3 3迭代法的收敛速度 B为对称矩阵 定义4 迭代法收敛速度 线性方程组迭代解法 4 4稀疏方程组及MATLAB实现 4 4 1分块迭代法 对x及b同样分块 线性方程组迭代解法 一 块雅可比迭代法 BJ 其中 注 块雅可比迭代法需要求解低阶方程组 其中 线性方程组迭代解法 二 块SOR迭代法 BSOR 定理9 1 如果A为对称正定矩阵 2 则解Ax b的BSOR迭代收敛 4 4 2MATLAB的稀疏矩阵简介 例8 利用MATLAB生成稀疏矩阵及求解 并与满阵的解法作时间上的对比 线性方程组迭代解法 n 1000 e ones n 1 A spdiags e4 ee 1 1 n n 以对角带生成A或用sparse语句生成b e tic x A b elapsed time1 toc 输出解稀疏矩阵方程组所用时间a full A tic x a b elapsed time2 toc 输出解满阵方程组所用时间 与计算机速度有关 运行得到 解稀疏方程组所用时间为 elapsed time1 0 解满阵方程组所用时间为 elapsed time2 0 4380 线性方程组迭代解法 例9 首先编写数据文本文件sp dat sp dat 输入每个非零元素的行数 列数及非零元素5110352044305540 在MATLAB的命令窗口中输入指令 loadsp datA spconvert sp 将数据文件sp dat转换为稀疏矩阵A 线性方程组迭代解法 nn nnz A 输出矩阵A的非零元素个数 运行得到A 5 1 10 4 4 30 3 5 20 5 5 40nn 4 注 在MATLAB中利用sparse建立稀疏矩阵 例如 a 0120 103 100 309 A sparse a 将矩阵a转换为稀疏矩阵形式 线性方程组迭代解法 运行得到A 2 1 1 3 1 1 4 1 3 1 2 12 2 3 3 4 3 9 41 定义 设P是一个m n的 0 1 矩阵 如m n且PP E 则称P为一个m n的置换矩阵 其中P 是P的转置矩阵 E是m阶单位方阵 置换矩阵在数学中的矩阵论里 置换矩阵是一种系数只由0和1组成的方