工程硕士数值分析第三章线性方程组的迭代解法.ppt

* 第三章 线性方程组的解法 思路 与解 f (x)=0 的不动点迭代相似 …… ，将 等价 改写为 形式，建立迭代 　 。从初值 出发，得到序列 。 计算精度可控，特别适用于求解系数为大型稀疏矩阵 的方程组。 研究 内容： ? 如何建立迭代格式？　 ? 收敛速度？ ? 向量序列的收敛条件？ ? 误差估计？ 求解 ，有迭代法和直接法 先介绍迭代法 §3.1 雅可比(Jacobi )迭代法 其中 是迭代初值。 写成矩阵形式： A = L U D 写成迭代法形式 B称为Jacobi 迭代阵 即 其中 … … … … 写成矩阵形式： B Gauss-Seidel 迭代阵 §3.2 高斯-赛德尔(Gauss - Seidel )迭代法 例3.2.1 用Gauss-Seidel迭代法求解方程组 取初始向量 ,要求 时迭代终止。 解： Gauss- Seidel迭代格式为: 计算结果可列表如下 注：1. 未必Seidel方法一定比Jacobi方法好。 2. 二种方法都存在收敛性问题。 有例子表明：Gauss-Seidel法收敛时， Jacobi法可能不收敛； 而Jacobi法收敛时， Gauss-Seidel法也 可能不收敛。 残余误差 §3.3 超松弛迭代法 换个角度看Gauss - Seidel 方法： 其中ri(k+1) = 相当于在 的基础上加个余项生成 。 下面令 ，希望通过选取合适的 ? 来加速收敛，这就是松弛法 （或SOR法）。 ?称作松弛因子。 ii k i k i k i a r x x ) 1 ( ) ( ) 1 ( + + + = w 0 ? 1 低松弛法 ? = 1 Gauss - Seidel 法 1? 2 (渐次)超松弛法 写成矩阵形式： 松弛迭代阵 （Kahan 必要条件）设 A 可逆，且 aii ? 0，则松弛法 从任意 出发都收敛 ? 0 ? 2 。 定理3.3.1 证明：省略 §3.4 迭代法的收敛性 的收敛条件 设 存在唯一解，则从任意 出发， 迭代 收敛 ? ? ( B ) 1 定理3.4.1(迭代法基本定理) 证明： 从任意 出发， 记 ，则 (k ? ?) 收敛 Bk ? 0 ? ? ( B ) 1. 由定理1.2.5 ? ① ② 证明： ① ② （充分条件）若存在一个矩阵范数使得 || B || = q 1, 则迭代收敛，且有下列误差估计： 定理3.4.2 证明：省略。 （充分条件）若A 为严格对角占优阵, 则解 的Jacobi 和 Gauss - Seidel 迭代均收敛。 定理3.4.3 定义3.4.1 设A=(aij)n?n, 如果 即主对角线上的元素绝对值大于同行其它元素的 绝对值之和，那么称矩阵A是严格对角占优阵。 §3.5 高斯消去法 或叫高斯消元法，是一个古老的求解线性方程组的直接法。 思路 首先通过消元将A化为上三角阵，再回代求解 。 = 消元 记 第一步：设 ，计算因子 将增广矩阵第 i 行 ? mi1 ? 第1行，得到 其中 第k步：设 ，计算因子 且计算 共进行 ？ 步 n ? 1 回代 注：事实上，只要 A 非奇异，即 A?1 存在，则可通过逐次消元及行交换，将方程组化为三角形方程组，求出唯一解。 如果出现某个akk(k)=0或其绝对值很小, 则消元过程无法进行下去，或者将严重影响计算精度。这个问题通常可通过与以下的某行交换来克服。 §3.6 高斯主元素消去法 例3.6.1：单精度解方程组 /* 精确解为 和 */ 8个 8个 用高斯消去法计算： 8个 小主元可能导致计算失败。 一. 完全主元素消去法 每一步选绝对值最大的元素为主元素，保证 。 第k步: ① 选取 ② 如 ik ? k 则交换第 k 行与第 ik 行; 如 jk ?