(数值分析 §2几种常用的选代公式 1. Jacobi方法(简单迭代法) 构造迭代公式为 ∑anx)-∑a-x) j=i+1 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 1,2,…,n;k=0,1,2 26 PDF檔案使用"pdfFactoryPro"試用版本建立www.pdffactory.com
数值分析 2626 §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 27 PDF檔案使用"pdfFactoryPro"試用版本建立www.pdffactory.com
数值分析 2727 注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 ∑ 28 PDF檔案使用"pdfFactoryPro"試用版本建立www.pdffactory.com
数值分析 2828 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<ω<1时,称为低松弛法 当Q=1时,就是 Gauss-Seidel迭代法 当1<<2时,称为超松弛法 SOR方法的矩阵形式为 +)=Bx()+1 其中B=(D+oL)(1-0)D-0U/,f=0(D+oL)b §3迭代法的收敛条件 引理3.1设选代公式x(+=Bx(+f收敛,则 limx)=x e lima k)=0s lim bk=0 k k→>∞ 定理3.1对任意初始向量x0和,由x=B3+f产 生的选代序列{x}收敛的充要条件是p(B)<1. 29不 PDF檔案使用"pdfFactoryPro"試用版本建立www.pdffactory.com
数值分析 2929 当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.且 有误差估计 (1)|x6)-xl≤ k (k-1 1-|6 (2) (0) 定理3.2是迭代法收敛的充分条件,它只能判别收敛 的情况,当‖B≥1时,不能由此断定选代不收敛常用 Bl1<1或‖B21判别选代法收敛 常用定理32中的结论(1)来设置选代终止的判别条 件,即只要相邻两次的迭代结果之差达到误差精度时, 迭代终止 30 PDF檔案使用"pdfFactoryPro"試用版本建立www.pdffactory.com
数值分析 3030 定理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