线性方程组的迭代解法ppt课件.ppt

第四章 线性方程组的迭代解法,迭代法的基本思想Jacobi迭代和GaussSeidel迭代迭代法的收敛性超松弛迭代分块迭代法,第四章 线性方程组的迭代解法,4.1 迭代法的基本思想：,例：求解方程组,其精确解是x*=(3,2,1)T。,现将原方程组改写为,简写为x=B0 x+f，其中,任取初始值，如取x(0)=(0,0,0)T，代入x=B0 x+f右边，若等式成立则求得方程组的解，否则，得新值x(1)=(x1(1),x2(1),x3(1)T=(2.5,3,3)T，再将x(1)代入，反复计算，得一向量序列x(k)和一般的计算公式（迭代公式）：,简写为x(k+1)=B0 x(k)+f k=0,1,2,x(10)=(3.000032,1.999838,0.999813)T,迭代到第10次时有,|(10)| =|x(10)x*|=0.000187,定义：,（1）对于给定方程组x=Bx+f，用迭代公式x(k+1)=Bx(k)+f (k=0,1,2,)逐步代入求近似解的方法称迭代法；,（2）若k时lim x(k)存在（记为x*），称此迭代法收敛，显然x*就是方程组的解，否则称迭代法发散；,（3）B称为迭代矩阵。,问题：, 如何建立迭代格式？ 收敛速度？ 向量序列的收敛条件？ 误差估计？,设Ax=b，A非奇异，且对角元不为零，将原方程组改写为,4.2 Jacobi迭代与GaussSeidel迭代,4.2.1 Jacobi迭代法,又代入，反复继续，得迭代格式：,称Jacobi迭代法。,选取初始向量,代入上面方程组右端得,Jacobi迭代法的矩阵表示：,计算公式为：,(i=1,2,n)，(k=0,1,2,表迭代次数),矩阵表示：,则BJ=I- D-1 A= D-1(L+U)， fJ=D-1b，称BJ为Jacobi迭代矩阵。,（aii0）,将方程组Axb的系数矩阵A分解为：A=D-L-U,例1:,用Jacobi迭代法求解方程组，误差不超过10-4。,解:,依此类推,得方程组满足精度的解为x12,迭代次数：12次,x4 = 3.0241 1.9478 0.9205 d = 0.1573 x5 = 3.0003 1.9840 1.0010 d = 0.0914 x6 = 2.9938 2.0000 1.0038 d = 0.0175 x7 = 2.9990 2.0026 1.0031 d = 0.0059 x8 = 3.0002 2.0006 0.9998 d = 0.0040 x9 = 3.0003 1.9999 0.9997 d = 7.3612e-004x10 = 3.0000 1.9999 0.9999 d = 2.8918e-004x11 = 3.0000 2.0000 1.0000 d = 1.7669e-004x12 = 3.0000 2.0000 1.0000 d = 3.0647e-005,若在迭代时尽量利用最新信息，则可将迭代格式变为,4.2.2 GaussSeidel迭代法,称GaussSeidel迭代法.,计算公式：,（i=2,3,n-1）,(i = 1,2,n),即,其中 BG-S=(D-L)-1 U 称GaussSeidel迭代矩阵。,(D L)x(k+1) = b Ux (k),故,GaussSeidel迭代格式：,1. 矩阵的范数（三种算子范数、谱半径、谱范数、F-范数）,前一次课内容回顾,3. 迭代法求解线性方程组（Jacobi迭代、Gauss-Seidel迭代及其矩阵表示）,2. 线性方程组求解的误差分析（病态方程组、良态方程组、扰动分析、事后误差估计）,例2.,用Gauss-Seidel迭代法求解例1方程组,要求误差仍然不超过10-4。,解:,Gauss-Seidel迭代格式为,x1 =2.5000 2.0909 1.2273 d =3.4825x2=2.9773 2.0289 1.0041 d =0.5305x3 =3.0098 1.9968 0.9959 d =0.0465x4 =2.9998 1.9997 1.0002 d =0.0112x5 =2.9998 2.0001 1.0001 d =3.9735e-004x6 =3.0000 2.0000 1.0000 d =1.9555e-004x7 =3.0000 2.0000 1.0000 d =1.1576e-005,取初值x(0)=(0,0,0)T通过迭代，至第7步得到满足精度的解x7：,从例1和例2可以看出，Gauss-Seidel迭代法的收敛速度比Jacobi迭代法要快。,Jacobi迭代法和Gauss-Seidel迭代法统称为简单迭代法。,4.3 迭代法的收敛性,设求解线性方程组的迭代格式为,将上面两式相减,得,而方程组的精确解为x*，则,则,因此迭代法收敛的充要条件,可转变为,引理：迭代格式,收敛的充要条件为,定理：迭代格式,收敛的充要条件为,迭代矩阵的谱半径(B)1。,证: 对任何 n 阶矩阵B，都存在非奇矩阵P，使 B = P 1 J P其中， J 为B的 Jordan 标准型。,其中, Ji 为Jordan块,其中i 是矩阵B的特征值， 由 B = P 1 J P,B k = (P 1 J P) (P 1 J P) (P 1 J P)= P 1 J k P,迭代法 x(k+1) = B x(k) + f 收敛 ,(i = 1, 2, r),(i = 1, 2, r),谱半径 (B) 1,定理：设x*为方程组 Ax=b 的解，若|B|1,则 对迭代格式 x(k+1) = B x(k) + f ， 有,（1）,（2）,推论 若|B|1，则迭代法x(k+1) = B x(k) + f 收敛。,（因为(B) |B| ）,证 由|B|1,有,所以,| x(k+1) x* | |B| | x(k) x* |,x(k+1)x* =(Bx(k)+f ) (Bx*+f ) =B(x(k) x* ),|x(k) x* |= |(x(k) x(k+1)+ ( x(k+1)x* )| |x(k) x(k+1)| + | x(k+1)x*| |x(k) x(k+1)| +|B| |x* x(k)| = |x(k+1) x(k)| +|B| | x(k)x* |,所以,x(k+1)x(k) =(Bx(k)f ) (Bx(k-1)f ) =B(x(k) x(k-1) ),|x(k+1)x(k)| |B | | x(k) x(k-1) |,故可得误差估计式:,注： （1）式说明，只要|B|不是很接近1，当x(k+1) 和x(k) 很接近时， x(k) 也越接近x*，故可用| x(k+1) - x(k) |中止迭代。,（2）式说明，|B|越小， x(k) 收敛越快，可作误差估计式。,例3.,判别下列方程组用Jacobi法和Gauss-Seidel法求解是否收敛:,解:,(1) 求Jacobi法的迭代矩阵,所以,即Jacobi迭代法收敛。,(2) 求Gauss-Seidel法的迭代矩阵：,显然BJ的几种常用算子范数|BJ|1，故用其特征值判断。,所以Gauss-Seidel迭代法发散。,注：在例1和例2中，Gauss-Seidel迭代法收敛速度比Jacobi迭代法要高，但例3却说明Gauss-Seidel迭代法发散时而Jacobi迭代法却收敛，因此，不能说Gauss-Seidel迭代法比Jacobi迭代法更好。,可得,故,定义 设A=(aij )nn Rnn ，若 (i=1,2,n)，则称A为对角占优矩阵，若不等式严格成立，则称A为严格对角占优矩阵。,迭代法收敛的其他结论：,定理 若Ax=b中A为严格对角占优矩阵，则Jacobi迭代和GaussSeidel迭代均收敛。,证明：,因为系数矩阵A严格对角占优，所以,故Jacobi迭代法收敛,(1)对于Jacobi迭代法，其迭代矩阵为,即,从而,因此,(2)对于GS迭代法，其迭代矩阵为,BG的特征值满足,分析：要证GS迭代法收敛，即证其迭代矩阵的谱半径(B)1，只要证明其特征值 1即可.,由于,可得,矛盾,由前述定理知，,GS迭代法收敛。,定理 若A为对称正定阵，则GaussSeidel迭代收敛。,考虑解线性方程组的Gauss-Seidel迭代法,4.4 超松弛迭代法（SOR）迭代法的加速,令,因此,上式称为逐次超松弛法(SOR迭代法),由GS迭代法的矩阵形式,上式为逐次超松弛法(SOR迭代法)的矩阵形式,令,当1时，SOR法化为,GS迭代法,GS法为SOR法的特例, SOR法为G-S法的加速。,例1.,用GS法和SOR法求下列方程组的解:,要求精度1e-6,解:,(1)G-S迭代法,x1 x2 x3 1 1 1 0.7500000 0.3750000 1.5000000 0.5625000 0.5312500 1.5416667 0.6510417 0.5963542 1.6145833 0.7018229 0.6582031 1.6727431. 0.9999933 0.9999923 1.9999926 0.9999943 0.9999935 1.9999937 0.9999952 0.9999944 1.9999946 k = 71,x=0.9999950.9999941.999995,满足精度的解,迭代次数为71次,(2)SOR迭代法,x1 x2 x3 1 1 1 0.6375000 0.0121875 1.3199063 0.2004270 0.3717572 1.3122805 0.6550335 0.5340119 1.6922848 0.7058468 0.7733401 1.7771932. 0.9999990 0.9999976 1.9999991 0.9999984 0.9999993 1.9999989 0.9999998 0.9999994 1.9999998 0.9999996 0.9999998 1.9999997 k = 24,x=1.0000001.0000002.000000,满足精度的解,迭代次数为24次,选取适当的，SOR法的收敛速度比G-S法要快得多。,SOR迭代收敛条件： SOR迭代收敛(B)1； SOR迭代收敛的必要条件是02； 若A对称正定，则当02时，SOR收敛。 若A为严格对角占优矩阵，则当01 时，SOR收敛。,另外，松弛因子的选取是很困难的，一般采用试算进行。,设 ARnn，xRn， bRn，将方程组Ax = b中系数矩阵A分块,其中，AiiRnini， AijRninj， xiRni，biRni,4.5 分块迭代法,将A分解，A = DB LB UB,Jacobi块迭代 DB x(k+1) = (LB + UB)x(k) + b,i=1,2, r,(2)Gauss-Seidel块迭代 DB x(k+1) = LB x(k+1)+ UBx(k) + b,i=1,2, r,P101-102习题四：1 （1），2，3，4，5,本章作业,