逸代浩-雅可比( Jacobi)迭代 地代-高斯-塞德尔( Gauss- Seder1)迭代 将A分解为A=D-L-U,其中D=diag(a1 cobi选代公式D(+=Lx(k)+Ux()+b 0 0 )+03x4+05 uA1203“+1进x=02x+40x”+05 设对角阵D非奇异(即a≠0,i=1…n)Ax=b Gauss-Seideily选代公式Dx4+)=Lxk+)+Ux)+b 4 Dx-(L+U)x=b x=D(L+U)x+D-b 在D非奇异的假设下(D-L)可逆,于是得到 记B1=D(L+U B2=(D-L)U, f2=(D-L)b 迭代格式 x(+=B2x()+/2(k=0,2…) f=Dbx+=Bx+f(k=012…) 代沽的收笕 B=D-(L+L 选代法的收做性 Jacobi选代x=Bx)+f1f=Db 序列收敛x*)→x'(k→∞)的充分条件 Gauss-Seideili选代x=B2x1)+f2B=(D-0 1)若A是严格对角占优的,即>∑内(=1…m) 一般选代形式x=Bx4+f f2=(D-L)-b 则雅可比和高斯一赛德尔迭代均收敛 星组的解x满足:x=Bx+f 代k次得到x“-x=B(x-x) 2)若A对称正定,则高斯一塞德尔迭代收敛 序列收敛x→x(k→∞)的充要条件 3)若B=q<L,则迭代公式x“=Bx“)+∫收敛 B→0(k→∞)⊙B的所有特征根(取模)小于1 且p-x14k--x越小收敛越快 B的谱半径p(B)=ma B 谱半径性质:P(B)圳B‖其中是任何一种矩阵范数 A(i=1…m)是B的特征根 (学静学实鉴 (大学数学实验) 「选代法一超松弛SOR遗代 迭代法一超松弛SOR选代 auss- Seidel选代公式 D(Lx++U)+ box (k+)=Bx(k) x4和x加权o作平均改进 B,=(D-OL)oU+(1-O)D O(D-OL b C)x(4) 若A对称正 收敛充要条件 >1 <1 超松弛迭代 低松弛迭代 Gaus- Seidel1遗代 SOR选代—解大型稀疏矩阵方程組4 迭代法 - 雅可比（Jacobi）迭代 将 A 分解为 A = D − L − U ，其中 ( , , ) D = diag a11 a22 Lann ， ⎥ ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎢ ⎣ ⎡ = − ⎥ ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎢ ⎣ ⎡ = − − − 0 0 0 , 0 0 0 1,1 12 1 1 2 , 1 21 n n n n n n a a a U a a a a L O O M L L M O O 设对角阵D非奇异（即a 0, i 1, n) ii ≠ = L f D b B D L U 1 1 1 1 ( ) − − = 记 = + ( 0,1,2 ) 1 ( ) 1 x (k+1) =Bx k + f k = L 迭代格式 Ax = b Dx − (L +U )x = b x D L U x D b 1 1 ( ) − − = + + 迭代法 - 高斯-塞德尔(Gauss-Sedeil)迭代 在D非奇异的假设下(D − L)可逆，于是得到 B D L U f D L b 1 2 1 2 ( ) , ( ) − − = − = − ( 0,1,2 ) 2 ( ) 2 x(k+1) = B x k + f k = L Jacobi迭代公式 Dx Lx Ux b k k k = + + ( +1) ( ) ( ) Dx Lx Ux b k k k = + + Gauss-Seideil迭代公式 ( +1) ( +1) ( ) 0.1 0.3 1.4 0.2 0.3 0.5 0.3 0.1 1.4 ( ) 2 ( ) 1 ( 1) 3 ( ) 3 ( ) 1 ( 1) 2 ( ) 3 ( ) 2 ( 1) 1 =− − + = + + =− − + + + + k k k k k k k k k x x x x x x x x x 改进 0.1 0.3 1.4 0.2 0.3 0.5 0.3 0.1 1.4 ( 1) 2 ( 1) 1 ( 1) 3 ( ) 3 ( 1) 1 ( 1) 2 ( ) 3 ( ) 2 ( 1) 1 = − − + = + + = − − + + + + + + + k k k k k k k k k x x x x x x x x x 迭代法的收敛性 原方程组的解 *x 满足： x = Bx + f * * 1 ( ) 1 ( 1) x B x f k k = + + Jacobi迭代 2 ( ) 2 ( 1) x B x f k k = + + Gauss-Seideil迭代 f D b B D L U 1 1 1 1 ( ) − − = = + f D L b B D L U 1 2 1 2 ( ) ( ) − − = − = − x Bx f k k = + ( +1) ( ) 一般迭代形式 ( ) ( ) * (0) * k x x B x x k k 迭代 次得到 − = − () * ( ) k 序列收敛 的 x xk → →∞ 充要条件 B → 0(k → ∞) k ⇔B的所有特征根（取模）小于1 （ 是 的特征根 的谱半径 i n B B B i i i n 1, ) ( ) max 1 = L = ≤ ≤ λ ρ λ ρ(B) <1 2）若 A 对称正定，则高斯—塞德尔迭代收敛; 迭代法的收敛性 谱半径性质：ρ(B) ≤|| B || 其中||B||是任何一种矩阵范数 () * ( ) k 序列收敛 的 x xk → →∞ 充分条件 则雅可比和高斯 赛德尔迭代均收敛； 若 是严格对角占优的，即 − > ∑ = ≠ 1) A b b (i 1, n), j i ii ij L 3) 若 B = q < 1，则迭代公式 x(k+1) = Bx(k ) + f 收敛 且 x x ，q越小收敛越快 q q x x (k 1) * (k 1) (k ) 1 − − − ≤ + + 迭代法 -超松弛 SOR 迭代 Gauss-Seideil迭代公式 ( 1) 1 ( 1) ( ) 1 ( 1) ( ) k kk k x D Lx Ux D b x +−+ − + = ++ ￾ % ( 1) ( 1) ( ) (1 ) k ~ k k x = ωx + −ω x + + 改进 ( 1) k x ω + % 和x 加权 作平均 k ω > 1 ω < 1 ω = 1 超松弛迭代 低松弛迭代 Gauss-Seideil迭代 ( 1) ( ) 1 1 , ( ) [ (1 ) ], ( ) k k x Bx f B DL U D f D Lb ω ω ω ω ωω ω ω ω + − − = + = − +− = − 迭代法 -超松弛 SOR 迭代 若A对称正定 收敛充要条件 0 2 < ω < SOR 迭代------解大型稀疏矩阵方程组