中国科学技术大学：《计算方法》课程教学资源（课件讲义）第六章 解线性方程组的迭代法

第六章解线性方程组的迭代法 2

2 第六章 解线性方程组的迭代法

迭代法 ■ 求解线性方程的直接法： 。时间复杂度：O(n) ●空间复杂度：O(n2) ●理论上可经过有限次四则运算得到准确解，但因数值计算有舍入误差， 得到的仍然是近似解 ·适用情况：中等规模 ■求解线性方程的送代法： ●高阶稀疏线性方程组 ●主要运算：矩阵与向量的乘法 ●送代格式的构造 ●收敛性、收敛速度 3

迭代法  求解线性方程的直接法：  时间复杂度：  空间复杂度：  理论上可经过有限次四则运算得到准确解，但因数值计算有舍入误差， 得到的仍然是近似解  适用情况：中等规模  求解线性方程的迭代法：  高阶稀疏线性方程组  主要运算：矩阵与向量的乘法  迭代格式的构造  收敛性、收敛速度 3 3 O n( ) 2 O n( )

迭代法 ■ 基本思想：将线性方程组AX=b等价变形为X=MK十g , 构造送代关系式：x+=Mx)+g。若向量序列x) 收敛到x,则 X*=Mx*+g→Ax*=b ■例如： A=N-P→x=N-Px+N-b ■如何设计送代格式？ 收敛性、收敛速度 ■ 收敛条件（是否与初始值相关） 优点：占用存储空间少，程序实现简单，尤其适合于 高阶稀疏线性方程组

迭代法  基本思想：将线性方程组 等价变形为 ，构造迭代关系式： 。若向量序列 收敛到 ，则  例如：  如何设计迭代格式？  收敛性、收敛速度  收敛条件（是否与初始值相关）  优点：占用存储空间少，程序实现简单，尤其适合于 高阶稀疏线性方程组 Ax b = x Mx g = + ( 1) ( ) k k + x Mx g = + ( ) k x * x x Mx g Ax b ** * = +⇔ = − − 1 1 A N P x N Px N b = −⇒= + 4

迭代法 ■ 收敛性分析： x(k+1)-x*=Mx(k)-Mx*=M(x()-x*) =.=Mk+(x0)-X*) ■向量序列x)收敛台limM=0 与初值的选取无关 定理：求解线性方程组送代格式xk+=Mx+g收敛的 充分必要条件是p(M)<1 ■推论：若矩阵M的范数‖M‖2<1，则x+)=Mx+g收敛 ■常用矩阵范数：‖M山或Ml 注意：当川M≥1或川M≥1时，不能断定送代序列发散 ,例如 0.9 0 M= 0.20.8 5

迭代法  收敛性分析：  向量序列 收敛  定理：求解线性方程组迭代格式 收敛的 充分必要条件是  推论：若矩阵 的范数 ，则 收敛  常用矩阵范数： 或  注意：当 或 时，不能断定迭代序列发散 ，例如 ( 1) ( ) ( ) 1 (0) * * ( *) ( *) kk k k + + −= − = − = = − x x Mx Mx M x x  Mx x ( ) k x lim 0 k k→∞ ⇔ = M 与初值的选取无关 ( 1) ( ) k k + x Mx g = + ρ()1 M < M || || 1 M p < ( 1) ( ) k k + x Mx g = + 1 || || M || || M ∞ 1 || || 1 M ≥ || || 1 M ∞ ≥ 0.9 0 0.2 0.8   =     M 5

Jacobi送代 ■基本思想：求解第i个方程得到第i个未知量 a11X1+.+anXn=b anx1+.+AmnXn=bn 1 x=。(ax,+.tanx。-bh) 1 -1 X2=(a21X1+a23x3+.+a1nxn-b) → 22 x=ax+.叶ak1-b） 6

Jacobi迭代  基本思想：求解第 个方程得到第 个未知量 6      + + = + + = n nn n n n n a x a x b a x a x b    1 1 11 1 1 1 112 2 11 11 2 21 1 23 3 1 2 22 1 1 1 1 1 ( ) 1 ( ) 1 ( ) n n n n n n nn n n nn x ax ax b a x ax ax ax b a x ax a x b a − −  − = ++ −    −  = + ++ − ⇒     − = ++ −       i i

Jacobi送代 ■Jacobis送代格式： x上(a,++ax,-h) 飞上(ax图+a0++a-）) x,1 (anx+.+ann-x-b) i=l i=i+] 7

Jacobi迭代  Jacobi迭代格式： 7 ( 1) ( ) ( ) 1 12 2 1 1 11 ( 1) () () ( ) 2 21 1 23 3 1 2 22 ( 1) ( ) ( ) 1 1 1 1 1 ( ) 1 ( ) 1 ( ) k kk n n k kk k n n kk k n n nn n n nn x ax ax b a x ax ax ax b a x ax a x b a + + + − −  − = ++ −    −  = + ++ −     − = ++ −       ( ) 1 1 ( ) 1 1 ( 1) ( ) i n j i k ij j i j k ij j ii k i a x a x b a x + − − = ∑ ∑= + − = +

Jacobi送代 ■Jacobi:送代矩阵： 0 -12 (1) 11 a11 x(k) 0 a22 a22 D= 02 : x -an2 b。 ann Ax=b台(D-(D-A)x=b 台Dx=(D-A)x+b 台X=D(D-A)x+Db →M=D(D-A)=I-DA,g=Db 8

Jacobi迭代  Jacobi迭代矩阵： 8 12 1 1 ( 1) 11 11 ( ) 11 1 1 11 ( 1) 21 2 ( ) 2 2 2 22 22 22 22 ( 1) ( ) 1 2 0 0 , 0 n k k k k n k k n n nn n n n nn nn nn aa b aa a x x a a ab x x a a aa x x a a a b a a a + + +  − −                  − −              = + =                          − −        D          1 1 1 11 ( ( )) () () ( ) , − − − −−   =⇔ − − = ⇔ =− + ⇔= − + ⇒ = − =− = Ax b D D A x b Dx D A x b x D D Ax D b M D D A I DA g Db

Jacobis迭代 ■Jacobi.迭代收敛条件的充分必要条件： p(M)∑lai=1,2,n (2)A为严格列对角占优阵，即小>∑0，j=l,2,m 则Jacobi送代收敛 通常，对角元越占优，收敛速度就越快；但也有反例 ,如 9

Jacobi迭代  Jacobi迭代收敛条件的充分必要条件：  定理：若线性方程组 的系数矩阵 满足下列条件 之一： （1） 为严格行对角占优阵，即 （2） 为严格列对角占优阵，即 则Jacobi迭代收敛  通常，对角元越占优，收敛速度就越快；但也有反例 ，如： 9 ρ()1 M = ∑  A , 1,2, , . jj ij i j a aj n ≠ > = ∑  1 1 1/2 1/2 1   − =     − A 2 1 3/4 1/12 1   − =     − A

Jacobi送代 ■Jacobis迭代算法 Algorithm 15 Jacobi's Iteration Algorithm Input: n,(a),(b),(x),M,e 1:for k =1 to M do 2:for i=1 to n do 3: h←(6，-∑ax/a 4: end for 5: if u-x<e then g break; else 求 for i=1 to n do 9: E←u 10: end for 11: end if 12:end for Output: (x) 10

Jacobi迭代  Jacobi迭代算法 10

Gauss-Seidel送代 基本思想：使用最新计算出的分量进行送代 x上(ax四++a-4) au 3= +a23x,+.+anx,）-b) d22 X()= (b) aii j= i=i+l 11

Gauss-Seidel迭代  基本思想：使用最新计算出的分量进行迭代 11 ( 1) ( ) ( ) 1 12 2 1 1 11 ( 1) ( 1) ( ) ( ) 2 21 1 23 3 1 2 22 ( 1) ( 1) ( 1) 1 1 1 1 1 ( ) 1 ( ) 1 ( ) k kk n n k kk k n n kk k n n nn n n nn x ax ax b a x ax ax ax b a x ax a x b a + + + ++ + − −  − = ++ −    −  = + ++ −     − = ++ −       ( ) 1 1 ( ) 1 1 ( 1) ( 1) i n j i k ij j i j k ij j ii k i a x a x b a x + − − = ∑ ∑= + − = + +