线性方程组的选代解法 A 线性方程组的迭代 解法 主讲:王开荣 PDF檔案使用"pdfFactoryPro"試用版本建立www.pdffactory.com
线性方程组的迭代解法 线性方程组的迭代 解法 主讲：王开荣 11 PDF 檔案使用 "pdfFactory Pro" 試用版本建立 www.pdffactory.com
线性方程组的选代解法 第三章线性方程组的迭代解法 §1迭代法的一般形式 设线性方程组Axb的系数矩阵A非奇异,从而有 组唯一的解构造等价的方程组x=B+:建立选代公式 x(l=Bx()+f,k=0,1,2,… 迭代法不需存储系数矩阵的零元素,特别适合求解 零元素较多的稀疏矩阵.用直接解法求解时,一次消 元就可能使系数阵丧失其稀疏性,不能充分利用其稀 疏的特点 迭代法产生的向量序列{的收敛终止条件常为 Ix(+D)x()k<8 2N PDF檔案使用"pdfFactoryPro"試用版本建立www.pdffactory.com
线性方程组的迭代解法 第三章 线性方程组的迭代解法 §1 迭代法的一般形式 22 x (k+1)=Bx(k)+f, k=0, 1, 2, … 设线性方程组 Ax=b的系数矩阵A非奇异, 从而有一 组唯一的解. 构造等价的方程组x=Bx+f. 建立迭代公式： 迭代法不需存储系数矩阵的零元素, 特别适合求解 零元素较多的稀疏矩阵. 用直接解法求解时, 一次消 元就可能使系数阵丧失其稀疏性, 不能充分利用其稀 疏的特点. 迭代法产生的向量序列{x (k)}的收敛终止条件常为 ||x (k+1) -x (k) ||<e PDF 檔案使用 "pdfFactory Pro" 試用版本建立 www.pdffactory.com
线性方程组的选代解法 §2几种常用的选代公式 1. Jacobi方法(简单迭代法) 构造迭代公式为 ∑anx)-∑a-x) j=i+1 i=1,2 k=0,1,2, 矩阵形式为x+=BAx()+f 其中 D(L+U,f=D b 2. Gauss- Seidel迭代法 (k+1) (k+1) a r(k) J=1+1 H;k=0,1,2 3 PDF檔案使用"pdfFactoryPro"試用版本建立www.pdffactory.com
线性方程组的迭代解法 33 §2 几种常用的迭代公式 1. Jacobi方法(简单迭代法) 构造迭代公式为 1 ( 1) ( ) ( ) 1 1 1, 2, , ; 0,1, 2, 1 ( ) i n k k k i i ij j ij j j j i ii i n k x b a x a x a - + = = + = = = - - å å L L 矩阵形式为 其中 x (k+1)=BJx (k) + fJ 1 1 ( ), BJ J D L U f D b - - = - + = 2. Gauss-Seidel 迭代法 1 ( 1) ( 1) ( ) 1 1 1 ( ) 1, 2, , ; 0,1, 2, i n k k k i i ij j ij j j j i ii x b a x a x a i n k - + + = = + = - - = = å å L L PDF 檔案使用 "pdfFactory Pro" 試用版本建立 www.pdffactory.com
线性方程组的选代解法 Seidel选代法的矩阵形式迭代公式 x(k+ )=Bux()+fs Bs=-(D+L)-U; fs=(D+L-b 注1 Seidel迭代法在用计算机计算时,只需一组内存 单元 注2在一定的条件下, Seidel选代法比 Jacobi选代法 收敛的速度快 注3 Jacobi迭代法可以并行计算 算法( Gauss-Seidel迭代法) 给定误差限≥0 1. FOR i=1 TO n x<0 2. DO PDF檔案使用"pdfFactoryPro"試用版本建立www.pdffactory.com
线性方程组的迭代解法 44 注1 Seidel 迭代法在用计算机计算时, 只需一组内存 单元. x (k+1)=BSx (k) + fS Seidel 迭代法的矩阵形式迭代公式 BS = -(D+L) -1U; fS=(D+L) -1b 注2 在一定的条件下, Seidel迭代法比Jacobi迭代法 收敛的速度快. 注3 Jacobi迭代法可以并行计算. 算法 (Gauss-Seidel迭代法) 给定误差限e³0. 1. FOR i=1 TO n xi¬0 2. DO PDF 檔案使用 "pdfFactory Pro" 試用版本建立 www.pdffactory.com
线性方程组的选代解法 3. 0 FOR i=l tO 5 xi 6. IFxr> P THEN P←kxt 7. WHILE p>C 8. OUTPUT x=(xu, x2,..., xn)/ 3逐次超松弛法(SOR方法) (k+1)_(k) ∑ aixi ∑ PDF檔案使用"pdfFactoryPro"試用版本建立www.pdffactory.com
线性方程组的迭代解法 55 3. p¬0 4. FOR i=1 TO n 5. t¬xi 1, n i ij j j j i i ii b a x x a = ¹ - ¬ å 6. IF |xi -t|>p THEN p¬|xi -t| 7. WHILE p>e 8. OUTPUT x=(x1 , x2 , …, xn ) T 3. 逐次超松弛法(SOR方法) 1 ( 1) ( ) ( 1) ( ) 1 i n k k k k i i i ij j ij j j j i ii x x b a x a x a w - + + = = æ ö = + ç ÷ - - è ø å å PDF 檔案使用 "pdfFactory Pro" 試用版本建立 www.pdffactory.com
线性方程组的选代解法 当0∞ 定理3.1对任意初始向量x0和,由x=B3+f产 生的选代序列{x}收敛的充要条件是p(B)<1. PDF檔案使用"pdfFactoryPro"試用版本建立www.pdffactory.com
线性方程组的迭代解法 66 当0<ω<1时, 称为低松弛法. 当ω=1时, 就是Gauss-Seidel迭代法. SOR方法的矩阵形式为 当1<ω<2时, 称为超松弛法. x (k+1)=Bwx (k)+fw 其中Bw=(D+wL) -1[(1-w)D-wU], fw= w(D+wL) -1b §3 迭代法的收敛条件 引理3.1 设迭代公式x (k+1)=Bx(k)+f 收敛, 则 ( ) ( ) lim lim 0 lim 0 k k k k k k x x B e * ®¥ ®¥ ®¥ = Û = Û = 定理3.1 对任意初始向量x (0)和f, 由x (k+1)=Bx(k)+f 产 生的迭代序列{x (k)}收敛的充要条件是r(B)<1. PDF 檔案使用 "pdfFactory Pro" 試用版本建立 www.pdffactory.com
线性方程组的选代解法 定理3.2若|B|<1,则由选代公式x(+)=Bx1)+f和任意 初始向量x产生的选代序列{}收敛于准确解x.且 有误差估计 (k) k (k-1 (0) 定理3.2是迭代法收敛的充分条件,它只能判别收敛 的情况,当‖B≥1时,不能由此断定选代不收敛常用 Bl1<1或‖B21判别选代法收敛 常用定理32中的结论(1)来设置选代终止的判别条 件,即只要相邻两次的迭代结果之差达到误差精度时, 迭代终止 PDF檔案使用"pdfFactoryPro"試用版本建立www.pdffactory.com
线性方程组的迭代解法 77 定理3.2 若||B||<1, 则由迭代公式x (k+1)=Bx(k)+f 和任意 初始向量x (0)产生的迭代序列{x (k)}收敛于准确解x * . 且 有误差估计 ( ) (1) (0) (2) 1 k k B x x x x B * - £ - - ( ) ( ) ( 1) (1) 1 k B k k x x x x B * - - £ - - 定理3.2是迭代法收敛的充分条件, 它只能判别收敛 的情况, 当||B||³1时, 不能由此断定迭代不收敛. 常用 ||B||1<1或||B||¥<1判别迭代法收敛. 常用定理3.2中的结论(1)来设置迭代终止的判别条 件, 即只要相邻两次的迭代结果之差达到误差精度时, 迭代终止. PDF 檔案使用 "pdfFactory Pro" 試用版本建立 www.pdffactory.com
线性方程组的选代解法 从定理3,2中的结论(2)可知,当‖的值越小,收敛就 越快也可以用‖的值来近似估计选代的次数在计算 出x①时,就可估计出选代次数k,不过估计偏保守,次数 一般偏大 定义3.2若矩阵A=(a;)nxn满足占优的 ∑l =1 且至少成立严格不等式,则称4是(弱对角占优的 定义3.3若矩阵A=( ain n满足 >∑|i=12 j=1,j 则称A是严格对角占优的 8 PDF檔案使用"pdfFactoryPro"試用版本建立www.pdffactory.com
线性方程组的迭代解法 88 从定理3.2中的结论(2)可知, 当||B||的值越小, 收敛就 越快. 也可以用||B||的值来近似估计迭代的次数. 在计算 出x (1)时, 就可估计出迭代次数k, 不过估计偏保守, 次数 一般偏大. 定义3.2 若矩阵 A=(aij)n×n 满足占优的. 1, , 1,2, , n ii ij j j i a a i n = ¹ ³ = å L 且至少成立严格不等式, 则称A是(弱)对角占优的. 定义3.3 若矩阵 A=(aij)n×n满足 1, , 1,2, , n ii ij j j i a a i n = ¹ > = å L 则称A是严格对角占优的. PDF 檔案使用 "pdfFactory Pro" 試用版本建立 www.pdffactory.com
线性方程组的选代解法 定义3.4若矩阵A通过行交换和相应的列交换,即能 找到一个置换矩阵P,使PAP能够变成 0 A 的形式,其中A1和A2为方阵,则称A是可约的,否则 称A是不可约的 引理32(1)若矩阵A严格对角占优,则A非奇异 (2)若A不可约,且具有对角占优,则4非奇异 定理3.3若A是严格对角占优或A是不可约对角占优 则解方程组Axb的Jcob选代法和 Gauss-Seide选代法 均收敛 定理3.4SOR方法收敛的必要条件是0<<2 PDF檔案使用"pdfFactoryPro"試用版本建立www.pdffactory.com
线性方程组的迭代解法 99 定义3.4 若矩阵 A 通过行交换和相应的列交换，即能 找到一个置换矩阵P, 使PAPT能够变成 的形式, 其中 A11 和 A22 为方阵, 则称 A是可约的, 否则 称 A 是不可约的. ÷ ÷ ø ö ç ç è æ 22 11 12 0 A A A 引理3.2 (1)若矩阵A严格对角占优, 则A非奇异. (2)若A不可约, 且具有对角占优, 则A非奇异. 定理3.3 若A 是严格对角占优或 A 是不可约对角占优, 则解方程组Ax=b的Jacobi迭代法和Gauss-Seidel迭代法 均收敛. 定理3.4 SOR方法收敛的必要条件是0<ω<2. PDF 檔案使用 "pdfFactory Pro" 試用版本建立 www.pdffactory.com
线性方程组的选代解法 定理3.5如果A是实对称正定矩阵,且0<0<2,则SOR 方法收敛 注由定理3.5的结论,若A是实对称正定矩阵,则 Gauss-Seidel方法收敛,但 cobi方法不一定收敛 定理3.6若A和2DA均为实对称正定矩阵,则解方程 组的 Jacobi选代法收敛(充分必要条件) 定理3.7如果4严格对角占优矩阵,则当0<0≤1时 SOR方法收敛 PDF檔案使用"pdfFactoryPro"試用版本建立www.pdffactory.com
线性方程组的迭代解法 1010 定理3.5 如果A是实对称正定矩阵, 且0<ω<2, 则SOR 方法收敛. 注 由定理3.5的结论, 若A是实对称正定矩阵, 则 Gauss-Seidel方法收敛, 但Jacobi方法不一定收敛. 定理3.6 若A和2D-A均为实对称正定矩阵, 则解方程 组的Jacobi迭代法收敛. (充分必要条件) 定理3.7 如果A严格对角占优矩阵, 则当0<w£1时 SOR方法收敛. PDF 檔案使用 "pdfFactory Pro" 試用版本建立 www.pdffactory.com