数值分析第6章—线性方程组的迭代解法.ppt

Jacobi、GS 和 SOR 算法 若A严格对角占优 ，得 由 下面证明|? |1。 若不然, 即|? |?1, 则 定理6 若矩阵 A 行（或列）严格对角占优或不可约对角占优，则解线性方程组 Ax=b 的Gauss-Seidel 迭代法均收敛 。 是行严格对角占优矩阵, 故可逆, 与式(1)矛盾, 所以|? |1, 从而 ?( BG)1, 即Gauss—Seidel迭代法收敛。 即矩阵 定理7 若系数矩阵A对称，对角线元素 , 则Jacobi迭代收敛的充分必要条件是A和2D-A * * 基本思想：迭代法是按照某一规则构造一个向 量序列 使得其极限向量 是方程组 的精确解。 第一节 Jacobi迭代法 与Gauss-Seidel迭代法 如何构造迭代序列的？ 第六章 线性方程组的迭代解法 生成向量序列{ x(k) }，若 称为迭代格式（1）的迭代矩阵。 则有x* =Bx*+f ， 即x*为原方程组Ax=b 的解，B 将方程组 Ax=b ( |A|?0 ) 转化为与其等价的方程组 x = Bx+f x(k+1) = Bx(k) + f （k=0,1,2,?) (1) 取初始向量 x(0)按下列迭代格式 第一节 Jacobi迭代法 与Gauss-Seidel迭代法 一 Jacobi迭代法 设方程组 1，构造的迭代序列是否收敛？在什么情况下收敛？ 2，如果收敛，收敛速度如何？ 3，近似解的误差如何？ 其中 aii(i)?0 ( i=1 , 2 , …, n) 等 价 方 程 组 建立迭代格式 称为Jacobi迭代法，又称简单迭代法。 或缩写为 记 A=D-L-U 其中 于是Jacobi迭代法可写为矩阵形式 其迭代矩阵为 二 Gauss-Seidel迭代法 在 Jacobi 迭代中,计算xi(k+1)（2? i ? n）时,使用xj(k+1)代替xj(k) （1? j ? i-1），即 建 立 迭 代 格 式 或缩写为 称为Gauss — Seidel迭代法。 其迭代矩阵为 BG = (D - L)-1U 于是Gauss-Seidel迭代法可写为矩阵形式 例1 用Jacobi迭代法解方程组 解：Jacobi 迭代格式为 1.29999 1.19999 1.09999 12 1.29999 1.19999 1.09999 11 … … … … 1.15 1.07 0.971 2 0.84 0.83 0.72 1 x3(k) x2(k) x1(k) k 取 计算如下 解： Gauss-Seidel 迭代格式为 例2 用Gauss—Seidel 迭代法解上题。 取 x(0)=(0,0,0)T 计算如下： 1.3 1.199999 1.099998 8 … … … … 1.1644 0.902 0.72 1 x3(k) x2(k) x1(k) k 逐次超松弛法(SOR方法) 逐次超松驰法是Gauss-Seidel迭代方法的一种加速方法，是解大型稀疏矩阵方程组的有效方法。 松弛法也可写成矩阵形式 称为松弛法，w=1为Gauss—Seidel 迭代法。 其迭代矩阵为 例 1 用逐次超松弛法法求解方程组 解 取 迭代公式 取w =1.055计算结果为 … 1.3 1.3 1.3002 1.2991 1.2481 … 1.2 1.2000 1.1998 1.2005 0.95578 … 1.1 1.0999 1.1008 1.0820 0.7596 … 5 4 3 2 1 K Jacobi 算法 GS 算法 SOR 算法 迭代法及其收敛性 一 迭代法的一般格式 B 为迭代矩阵 定理1 二 迭代法的收敛性 定理 2 迭代格式 x(k+1) = Bx(k) + f 收敛 ? ?( B )1。 x (k) -x*= B k( x (0) -x*) ， 充分性 设?( B )1 故 lim x (k) =x* 由定理1 lim B k =O； 必要性 设 lim x (k) =x* x (k) -x*= B k( x (0) -x*) →0 B k( x (0) -x*) →0 ( x (0) -x*) B k( x (0) -x*) →0 ( x (0) -x*) 由定理（