数值分析第六章线性方程组迭代解法剖析.ppt

* 第六章线性方程组的迭代解法 数值分析 —— 迭代法基本概念 * 线性方程组迭代解法 运算量大，不适合大规模的线性方程组求解 无法充分利用系数矩阵的稀疏性 直接法的缺点： 从一个初始向量出发，按照一定的迭代格式，构造出一个趋向于真解的无穷序列 只需存储系数矩阵中的非零元素 运算量不超过 O(kn2)，其中 k 为迭代步数 迭代法 迭代法是目前求解大规模线性方程组的主要方法 * 矩阵分裂迭代法 矩阵分裂迭代法基本思想 Ax = b k = 0, 1, 2, … 给定一个初始向量 x(0)，可得 迭代格式 其中 B = M-1N 称为迭代矩阵 A = M - N Mx = Nx + b M 非奇异 A 的一个 矩阵分裂 * 向量序列的极限 定义：设向量序列 ， ，若存在向量 ，使得 i = 1, 2, … , n 则称向量序列 收敛到 x，记作 相类似地，可以定义矩阵序列的极限与收敛 * 矩阵分裂迭代法 k = 0, 1, 2, … 定义：若 存在，则称该迭代法收敛，否则称为发散 性质：若 ，则 x* 为原方程组 Ax = b 的解 引入误差向量 ,由 得 迭代法收敛： 那么B满足什么条件有 ？ * 向量序列的极限 定理： 定理： 定理： 定理： * 收敛性分析 定理：对任意初始向量 x(0)，上述迭代格式收敛的充要条件是 定理：若存在算子范数 || · ||，使得 ||B|| 1，对任意的初始向量 x(0)，上述迭代格式收敛。 例：考虑迭代法 x(k+1) = Bx(k) + f 的收敛性，其中 基本收敛定理 充分条件 * 收敛性分析 B = M-1N 定理：若存在算子范数 || · ||，使得 ||B|| = q 1，则 迭代法收敛 * 收敛速度 第 k 步的误差： 平均每次迭代后的误差压缩率约为： 若要求 k 步迭代后上述误差比值不超过 ?，则 * 收敛速度 定义：迭代格式 x(k+1) = Bx(k) + f 的平均收敛速度为 渐进收敛速度为 ?(B) 越小，收敛越快 * 第六章线性方程组的迭代解法 数值分析 —— 基本的矩阵分裂迭代法 * 本讲内容 Jacobi 迭代算法 Gauss-Seidel 迭代算法 SOR 迭代算法 收敛性分析 矩阵分裂迭代法的典型代表 * Jacobi 迭代 考虑线性方程组 Ax = b 其中 A=(aij)n?n 非奇异，且对角线元素全不为 0。 将 A 分裂成 A = D - L- U， 其中 * Jacobi 迭代 k = 0, 1, 2, … 令 M = D，N = L + U，可得 雅可比 (Jacobi) 迭代方法 Jacobi 迭代 迭代矩阵记为： 分量形式： i = 1, 2, … , n， k = 0, 1, 2, … * Jacobi 迭代 Jacobi 迭代的分量形式： * Gauss-Seidel 迭代 在计算 时，如果用 代替 ，则可能会得到更好的收敛效果。 * Gauss-Seidel 迭代 写成矩阵形式: 此迭代方法称为 高斯-塞德尔 (Gauss-Seidel) 迭代法 k = 0, 1, 2, … 可得 迭代矩阵记为： * 举例 例：分别用 Jacobi、G-S迭代解线性方程组 取初始向量 x(0) = ( 0, 0, 0 )，迭代过程中小数点后保留 4 位。 解： Jacobi 迭代： 迭代可得： x(1) = ( 0.5000, 2.6667, -2.5000 )T x(21) = ( 2.0000, 3.0000, -1.0000 )T * 举例 G-S 迭代： x(1) = ( 0.5000, 2.8333, -1.0833 )T x(9) = ( 2.0000, 3.0000, -1.0000 )T 迭代可得： * Jacobi 迭代收敛的充要条件 ?(J)1 G-S 迭代收敛的充要条件 ?(G)1 收敛性 收敛性定理 Jacobi 迭代收敛的充分条件 ||J|| 1 G-S 迭代收敛的充分条件 ||G|| 1 * SOR 迭代 为了得到更好的收敛效果，可在修正项前乘以一个 松弛因子?，于是可得迭