中图苔技术大荸数学系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS 第6章解线性方程组的迭代法 直接法得到的解是理论上准确的,但是我们可以看得出,它们的计算量都是n3 数量级,存储量为n2量级,这在n比较小的时候还比较合适(n<400),但是对于现 在的很多实际问题,往往要我们求解很大的n的矩阵,而且这些矩阵往往是系数矩阵 就是这些矩阵含有大量的0元素。对于这类的矩阵,在用直接法时就会耗费大量的时 间和存储单元。因此我们有必要引入一类新的方法:迭代法 迭代法具有的特点是速度快。与非线性方程的迭代方法一样,需要我们构造一 个等价的方程,从而构造一个收敛序列,序列的极限值就是方程组的根
数 学 系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS 第6章 解线性方程组的迭代法 直接法得到的解是理论上准确的，但是我们可以看得出，它们的计算量都是n 3 数量级，存储量为n 2量级，这在n比较小的时候还比较合适（n<400），但是对于现 在的很多实际问题，往往要我们求解很大的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→Mx=b+Mx→x=MMx+Mb 则,我们可以构造序列x()=Gx)+g 若x()→x*→x*=Gx*+g→Ax*=b 同时:x(x+)-x*米=Gx6)-Gx*=G(x32-x* Gk+(x 所以,序列收敛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 定义61:(收敛矩阵)G→0 定理:G→>0<P(G)<1矩阵G为收敛矩阵,当且仅当G的谱半径<1 由p()<|G‖知,若有某种范数|Gn<1则,迭代收敛
数 学 系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS 定义6.1：（收敛矩阵） → 0 k G 定理： G →0 (G) 1 矩阵G为收敛矩阵，当且仅当G的谱半径<1 k 由 (G) G 知，若有某种范数 1 p G 则，迭代收敛
) 中图学技术大荸学系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS 61 Jacob迭代 +…+a,x.=b In x +…+ax.=b nn n (a12x2+…+a1nxn-b1) (a21x1+a23x3+…+a1nxn-b2) (an1x1+…+a nn-n-I n
数 学 系 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 (k+1) 122+…+y(h) (k) (k+1) (△yx1+ax(k)++a1 (k) b,) 22 (k+1) (an1x1+…+a (k) nn n-1 格式很简单: (k+1) (k) x +∑anx-b) =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 Jacobi迭代算法 1、输入系数矩阵A和向量b,和误差控制eps 2、x1={0,0,……0,x2={1,1,,1}∥赋初值 3、whe(|A*x2-b!eps){ 1=x2; for(=0;i<ni++){ 2叮=0 for(j=0; j<1; j ++)I x2+=A[]*×1 forj=计+1j<n;j++){ x2[+=AU]×1j x2[=(x2[]-b)/A[j[ 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( ||A*x2-b||>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 0 D 0 0 0 0-a n-In 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 易知, Jacobi迭代有 (D-L-Ux=b Dx=(L+O)x+b DL+U)x+D b G=DL+0=I-DA,8=Db
数 学 系 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满足 ∑
数 学 系 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/) - maX ∑|<1<∑l ≠1 =mx∑< ②A为列对角占优阵,则A为行对角占优阵,有 P(-DA< p(Ⅰ-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 ＃证毕
