电子科大 数值分析课件第四章 线性方程组的迭代解法

1、第四章 线性方程组的迭代解法,迭代法的基本思想 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=

2、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迭代与GaussSeid

3、el迭代,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.

4、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-004 x10 = 3.0000 1.9999 0.9999 d = 2.8918e-004 x11 = 3.0000 2.0000 1.0000 d = 1.7669e-004 x12 = 3.0000 2.0000

5、 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. 线性方程组求解的误差分析 （病态方

6、程组、良态方程组、扰动分析、事后误差估计）,例2.,用Gauss-Seidel迭代法求解例1方程组,要求误差仍然不超过10-4。,解:,Gauss-Seidel迭代格式为,x1 =2.5000 2.0909 1.2273 d =3.4825 x2=2.9773 2.0289 1.0041 d =0.5305 x3 =3.0098 1.9968 0.9959 d =0.0465 x4 =2.9998 1.9997 1.0002 d =0.0112 x5 =2.9998 2.0001 1.0001 d =3.9735e-004 x6 =3.0000 2.0000 1.0000 d =1.9555e

7、-004 x7 =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，都存在非奇

8、矩阵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 收敛。,（

9、因为(B) |B| ）,证 由|B|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迭代均收敛。,证明：

10、,因为系数矩阵A严格对角占优，所以,故Jacobi迭代法收敛,(1)对于Jacobi迭代法，其迭代矩阵为,即,从而,因此,(2)对于GS迭代法，其迭代矩阵为,BG的特征值满足,分析：要证GS迭代法收敛，即证其迭代矩阵的谱半径(B)1，只要证明其特征值 1即可.,由于,可得,矛盾,由前述定理知，,GS迭代法收敛。,定理 若A为对称正定阵，则GaussSeidel迭代收敛。,考虑解线性方程组的Gauss-Seidel迭代法,4.4 超松弛迭代法（SOR）迭代法的加速,令,因此,上式称为逐次超松弛法(SOR迭代法),由GS迭代法的矩阵形式,上式为逐次超松弛法(SOR迭代法)的矩阵形式,令,当1时，S

11、OR法化为,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

12、 1.9999946 k = 71,x= 0.999995 0.999994 1.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.000000 1.000000 2.000000,满足精度的解,迭代次数为24次,选取适当的，SOR法的收敛速度比G-S法要快得多。,SOR迭代收敛条件： SOR迭代收敛(B)1； SOR迭代收敛的必要条件是02； 若A对称正定，则当02时，SOR收敛。 若A为严格对角占优矩阵，则当01 时，SOR收敛。,另外，松弛因子的选取是很困难的，一般采用试算进行。,设 ARnn，xRn， bRn， 将方程组Ax = b中系数矩阵A分块,其中，