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

中图科亨技术大学数学系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS 第6章解线性方程组的迭代法 直接法得到的解是理论上准确的，但是我们可以看得出， 它们的计算量都是数量级，存储量为量级，这在n比较小的 时候还比较合适(<1000,1G5,15秒，8M),但是对于现在的 很多实际问题，往往要我们求解很大的的矩阵，而且这些矩阵 往往是稀疏矩阵就是这些矩阵含有大量的元素。对于这类的矩 阵，在用直接法时就会耗费大量的时间和存储单元。因此我们 有必要引入一类新的方法：迭代法。 迭代法具有的特点是速度快。与非线性方程的迭代方法一 样，需要我们构造一个等价的方程，从而构造一个收敛序列， 序列的极限值就是方程组的根

数 学 系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS 第6章 解线性方程组的迭代法 直接法得到的解是理论上准确的，但是我们可以看得出， 它们的计算量都是n 3数量级，存储量为n 2量级，这在n比较小的 时候还比较合适（n<1000 , 1G/s , 15秒 , 8M），但是对于现在的 很多实际问题，往往要我们求解很大的n的矩阵，而且这些矩阵 往往是稀疏矩阵就是这些矩阵含有大量的0元素。对于这类的矩 阵，在用直接法时就会耗费大量的时间和存储单元。因此我们 有必要引入一类新的方法：迭代法。 迭代法具有的特点是速度快。与非线性方程的迭代方法一 样，需要我们构造一个等价的方程，从而构造一个收敛序列， 序列的极限值就是方程组的根

中图科亨技术大学数学系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS 对方程组Ax=b做等价变换x=Gx+g 如：令A=M-N,则 Ax=b→(M-N)x=b→=b+Nx→x=M1Nx+Mb 则，我们可以构造序列x+)=Gx)+g 若x)〉x*→x*=Gx*+g→Ax*=b 同时：xk+-x*=Gx)-Gx*=G(x)-x*) =.=G+1(x0)-X*) 所以，序列收敛台G→0 与初值的选取无关

数 学 系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS 对方程组 Ax = b 做等价变换 x = Gx + g Ax b M N x b Mx b Nx x M Nx M b 1 1 ( ) − − =  − =  = +  = + 如：令 A= M − N ，则 则，我们可以构造序列 x G x g k k = + ( +1) ( ) 若 * ( ) x x k →  x* = G x*+g  Ax* = b 同时： * * ( *) ( 1) ( ) ( ) x x Gx Gx G x x k k k − = − = − + ( *) 1 (0) G x x k = = −  +  → 0 k 所以，序列收敛 G 与初值的选取无关

中图科李技术大学数学系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS 定义： (收敛矩阵)G→0 定理：G→0台p(G)<1 矩阵G为收敛矩阵，当且仅当G的谱半径<1 由p(G)<G知，若有某种范数G。<1则，迭代收敛

数 学 系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS 定义：（收敛矩阵） → 0 k G 定理： 矩阵G为收敛矩阵，当且仅当G的谱半径<1 G →0  (G) 1 k  由 (G)  G 知，若有某种范数 1 p G 则，迭代收敛

中固科亨技术大学数学案 University of Science and Technology of China DEPARTMENT OF MATHEMATICS 6.1 Jacobii迭代 a11X1+.+a1mXn=b1 am+amnxn=bn (dp2++duntB) -1 → x2=(a21X1+a23x3+.+a1nxn-b2) a22 x=。(ax+.+ana-x-b) ann

数 学 系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS 6.1 Jacobi迭代      + + = + + = n nn n n n n a x a x b a x a x b    1 1 11 1 1 1           + + − − = + + + − − = + + − − =  − − ( ) 1 ( ) 1 ( ) 1 1 1 1 1 2 1 1 2 3 3 1 2 2 2 2 1 2 2 1 1 1 1 1 n n n n n n n n n n n n a x a x b a x a x a x a x b a x a x a x b a x    

中图科亨技术大学数学系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS x=二a,x++ax-b) 1 =二（ax+ax++a-6) X2 022 () 格式很简单： w=a,x+a,g-b) ai j=l =i+1

数 学 系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS           + + − − = + + + − − = + + − − =  − − + + + ( ) 1 ( ) 1 ( ) 1 ( ) 1 1 ( ) 1 1 ( 1) 2 ( ) 1 ( ) 2 3 3 ( ) 2 1 1 2 2 ( 1) 2 1 ( ) 1 ( ) 1 2 2 1 1 ( 1) 1 n k n n n k n n n k n k n n k k k k n n k k a x a x b a x a x a x a x b a x a x a x b a x     格式很简单： ( ) 1 1 ( ) 1 1 ( 1) ( ) i n j i k i j j i j k i j j i i k i a x a x b a x + − − =  = + − = +

中图 科亨技术大学数学系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS Jacobii迭代算法 1、输入系数矩阵A和向量b,和误差控制eps 2、X1={0,0,0},2={1,1,1}1/赋初值 3.while(x1-x2ll>eps){ X1=X2: for(i=0;i<n;i++){ x2[0=0; for(j=0;j<i;j++){ x2[0+=A[]0]*x10] } for(j=i+1;j<n;j++){ 2[0+=A[]]*x1[] x2[0=-(x2[-b[)MA0 4、输出解x2

数 学 系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS Jacobi迭代算法 1、输入系数矩阵A和向量b，和误差控制eps 2、x1={0,0,.,0} , x2={1,1,.,1} //赋初值 3、while( ||x1-x2||>eps) { x1=x2; for(i=0;i<n;i++) { x2[i]=0; for(j=0;j<i;j++) { x2[i] += A[i][j]*x1[j] } for(j=i+1;j<n;j++) { x2[i] += A[i][j]*x1[j] } x2[i]=-(x2[i]-b[i])/A[i][i] } } 4、输出解x2

中图科亨技术大学数学系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS ●迭代矩阵 记A=D-L-U a D 0 0 (0-412 d21 0 U= 0 0 0n-ln 一anm-l 0 0 0

数 学 系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS ⚫ 迭代矩阵 记 A= D− L−U           = ann a D 0 11 0                  − − − = − 0 0 0 0 0 1 1 2 1 an an n a L                     − − − = − 0 0 0 0 0 1 1 2 1 n n n a a a U    

中固科营技术大学数学系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS 易知，Jacobii迭代有 (D-L-U)x=b Dx=(L+U)x+b x=D(L+U)x+D-b .G=D (L+U)=1-D-A,8=D-b

数 学 系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS 易知，Jacobi迭代有 (D − L −U)x = b Dx = (L +U)x + b x D L U x D b 1 1 ( ) − − = + + G D L U I D A g D b 1 1 1 ( ) , − − −  = + = − =

中图科亨技术大学数学系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS 收敛条件 迭代格式收敛的充要条件是G的谱半径∑a ② A为列对角占优阵口，小∑a ③A满足

数 学 系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS ⚫ 收敛条件 迭代格式收敛的充要条件是G的谱半径<1。对于 Jacobi迭代，我们有一些保证收敛的充分条件 定理：若A满足下列条件之一，则Jacobi迭代收敛。 ① A为行对角占优阵 ② A为列对角占优阵 ③ A满足    j i aii aij    i j ajj aij  1 i j ii ij a a

中图科亨技术大学数学系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS 证明：G=D(L+U) lGl。=max 2、 l台∑la<laa lG,=max∑ <1 ②A为列对角占优阵，则AT为行对角占优阵，有 p(I-D-A)<1 ∴.p(I-DA)=p(I-DA)<1 #证毕

数 学 系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS 证明： ( ) 1 G = D L +U − i i j i i j j i i i i j i a a a a G =         max 1 max 1 1 =   i j ii ij i a a G ② A为列对角占优阵，则A T为行对角占优阵，有 ( ) 1 1 −  − T  I D A ( ) ( ) 1 1 1  − = −  − − T  I D A  I D A ＃证毕