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

1、2022-2-5第六章 线性方程组的迭代解法1第六章第六章 线性方程组的迭代解法线性方程组的迭代解法1 向量和矩阵的范数向量和矩阵的范数 1.1 1.1 向量的范数向量的范数 1.2 1.2 矩阵的范数矩阵的范数2 迭代解法与收敛性迭代解法与收敛性 2.1 2.1 迭代法的构造迭代法的构造 2.2 2.2 迭代法的收敛性条件迭代法的收敛性条件3 常用的三种迭代解法常用的三种迭代解法 2.1 Jacobi2.1 Jacobi迭代法迭代法 2.2 Gauss-Seidel2.2 Gauss-Seidel迭代法迭代法 2.2 2.2 超松弛超松弛(SOR)(SOR)迭代法迭代法2022-2-5第六章

2、 线性方程组的迭代解法21 向量和矩阵的范数向量和矩阵的范数一、向量的范数一、向量的范数 为了对线性方程组数值解的精确程度，以及方程组为了对线性方程组数值解的精确程度，以及方程组本身的性态进行分析，需要对向量和矩阵的本身的性态进行分析，需要对向量和矩阵的“大小大小”引引进某种度量，进某种度量，范数范数就是一种度量尺度，就是一种度量尺度，向量和矩阵的范向量和矩阵的范数数在线性方程组数值方法的研究中起着重要的作用。在线性方程组数值方法的研究中起着重要的作用。 定义定义6.1设设|是向量空间是向量空间Rn上的上的实值函数实值函数，且满足条件，且满足条件 求解线性方程组的数值解除了使用直接解法，迭代解

3、求解线性方程组的数值解除了使用直接解法，迭代解法也是经常采用的一种方法，这种方法更有利于编程计法也是经常采用的一种方法，这种方法更有利于编程计算，本章将介绍这种方法。算，本章将介绍这种方法。2022-2-5第六章 线性方程组的迭代解法3则称则称 | 为为 Rn 空间上的范数空间上的范数，| x |为向量为向量 x 的范数的范数。 理论上存在多种多样的向量范数，但最常用的是如下理论上存在多种多样的向量范数，但最常用的是如下三种。三种。（2）齐次性齐次性：对任何实数和向量：对任何实数和向量x | x| | | x |（3）三角不等式三角不等式：对任何向量：对任何向量x和和y，都有都有 | xy |

4、 x | y |设向量设向量x（x1，x2，xn）T，定义定义 （1）非负性非负性：对任何向量：对任何向量 x， | x |0，且，且| x |0当且仅当当且仅当x0可引进极限可引进极限2022-2-5第六章 线性方程组的迭代解法4向量向量1-范数范数： niixx1121122 niixx向量向量2-范数范数： 向量向量-范数范数： inixx 1max容易验证，以上容易验证，以上三种范数三种范数都满足向量范数的三个条件。都满足向量范数的三个条件。 例例6.1 设设x（1，3，2，0）T，求向量范数求向量范数| x |p，P1，2，。 欧氏范数欧氏范数最大范数最大范数(0,0)O12( ,)

5、A x xB2xx 2022-2-5第六章 线性方程组的迭代解法5 解解: :对于对于 向量向量 x(1，3，2，0)T ，根据定义，根据定义可以计算出：可以计算出： | x|1| 1 |3 | 2 | 0 |6 1402312122222 x 30,2,3,1max x 由此例可见，向量不同范数的值不一定相同，但这并不由此例可见，向量不同范数的值不一定相同，但这并不影响对向量大小做定性的描述，因为不同范数之间存在如影响对向量大小做定性的描述，因为不同范数之间存在如下等价关系下等价关系。 2022-2-5第六章 线性方程组的迭代解法6定义定义（范数的等价性）（范数的等价性） Rn上两种范数上两

6、种范数| 和和| 称为等价称为等价的的，如果存在着正数如果存在着正数 m，M，使得使得： nRxxMxxm , 范数的等价性表明，范数的等价性表明，一个向量若按某种范数是一个小一个向量若按某种范数是一个小量，则它按任何一种范数也将是一个小量量，则它按任何一种范数也将是一个小量。（等价有传递。（等价有传递性）容易证明，常用的三种向量范数满足下述等价关系。性）容易证明，常用的三种向量范数满足下述等价关系。 | x | | x |1 n| x | x | | x |2 | x | x | 2| x |1 n| x |2 niixx11例如例如：inixn 1max xnnn1定理定理6.2 n维向量

7、维向量x的的一切范数都等价一切范数都等价2022-2-5第六章 线性方程组的迭代解法7定义定义6.2 对于向量序列对于向量序列 , 2 , 1,),()()(2)(1)( kxxxxTknkkk*)(limxxkk *)(xxk 向量序列向量序列 x(k) 收敛于向量收敛于向量 x*，当且仅当它的当且仅当它的每一每一个分量序列个分量序列收敛于收敛于xi*的对应分量，即的对应分量，即 nixxxxikik, 2 , 1,*)(*)( Tnxxxx),(*2*1* 及向量及向量0lim*)( xxkk如果如果则称向量序列则称向量序列 x(k) 收敛于收敛于向量向量 x* 。记作记作 或或收敛与取哪

8、种范数无关收敛与取哪种范数无关1()*()*|m ax |inkkiixxxx 2022-2-5第六章 线性方程组的迭代解法8二、矩阵的范数二、矩阵的范数 矩阵范数是反映矩阵范数是反映矩阵矩阵“大小大小”的一种度量，具体定义如下。的一种度量，具体定义如下。 定义定义6.3 设设|是以是以n阶矩阵为变量阶矩阵为变量的的实值函数实值函数，且满足，且满足条件：条件： （1）| A |0，且，且| A |0时，当且仅当时，当且仅当A0 （2）|A| | A|，R （3）|AB| | A | B | （4）| AB | A | | B |则称则称| A |为矩阵为矩阵A的的范数范数。可定义矩可定义矩阵极

9、限阵极限2022-2-5第六章 线性方程组的迭代解法9设设 n 阶矩阵阶矩阵 A（aij），常用的矩阵范数有：），常用的矩阵范数有： 矩阵矩阵1-范数范数： niijnjaA111|max( () )122TAA A= =的的最最大大特特征征值值矩阵矩阵2-范数范数： njijniaA11|max矩阵矩阵-范数范数： 以上三种范数都满足矩阵范数的条件，通常将这三种以上三种范数都满足矩阵范数的条件，通常将这三种矩阵范数统一表示为矩阵范数统一表示为| A |p，P1，2，。 列和列和行和行和谱范数谱范数. 不好不好算理论上重要算理论上重要2022-2-5第六章 线性方程组的迭代解法10例例6.2

10、设矩阵设矩阵 4321A求矩阵求矩阵A的范数的范数| A |p，P1，2，。 解解 根据定义根据定义 6|4|2|,3|1|max1 A 43214231AAT由于由于 7|4|3|,2|1|max A 20141410则它的特征方程为则它的特征方程为: 0430201414102 AAIT2022-2-5第六章 线性方程组的迭代解法11此方程的根为矩阵此方程的根为矩阵ATA的特征值，解得的特征值，解得 221151 221152 因此因此 46522115212.A 在线性方程组的研究中，经常遇到矩阵与向量的乘积在线性方程组的研究中，经常遇到矩阵与向量的乘积运算，若将运算，若将矩阵范数矩阵范

11、数与与向量范数向量范数关联起来，将给问题的分关联起来，将给问题的分析带来许多方便。设析带来许多方便。设|是一种向量范数，由此范数派生是一种向量范数，由此范数派生的的矩阵范数定义矩阵范数定义为为 xAxAx0max (也称为也称为A的的算子范数算子范数) 此式左端此式左端|A|表示矩阵范数，而右端表示矩阵范数，而右端是向量是向量Ax 和和 x 的范数，利用向量范数所具有的性质不难的范数，利用向量范数所具有的性质不难验证，由上式定义的验证，由上式定义的矩阵范数矩阵范数满足满足矩阵范数的条件矩阵范数的条件。2022-2-5第六章 线性方程组的迭代解法12,nA xAxxR 通常将满足上式的矩阵范数称

12、为与向量范数通常将满足上式的矩阵范数称为与向量范数相容的相容的矩阵范矩阵范数。数。 可以证明，前述的三种矩阵范数可以证明，前述的三种矩阵范数| A |p，P1，2，就是由就是由向量范数向量范数| x |p派生出的矩阵范数，即派生出的矩阵范数，即 ,2,1,max0pxAxAppxp通过向量范数定义的矩阵范数，满足不等式关系：通过向量范数定义的矩阵范数，满足不等式关系：均为均为相容范数相容范数，即，即 ,2,1,pxAAxppp 可以证明可以证明, ,对方阵对方阵 和和 有有: nnRAnxR22|FAxAx2,1|nFiji jAa ( (向量向量2- -范数直接推广范数直接推广) )Frob

13、enius范数范数: :2022-2-5第六章 线性方程组的迭代解法13三、矩阵的谱半径三、矩阵的谱半径 矩阵范数同矩阵特征值之间有密切的联系，设矩阵范数同矩阵特征值之间有密切的联系，设是矩是矩阵阵A相应于相应于特征向量特征向量x的特征值，即的特征值，即 Axx,于是利用于是利用向量向量-矩阵范数的相容性，得到矩阵范数的相容性，得到| | x |x|从而，对从而，对A的的任何特征值任何特征值均成立均成立=| Ax| | A | |x| A | （6.1） 设设n阶矩阵阶矩阵A的的n个特征值为个特征值为1,2，n。称。称iniA 1max)(为矩阵为矩阵A的的谱半径谱半径，从（，从（6.1）式得

14、知，对矩阵）式得知，对矩阵A的任何一的任何一种相容范数都有种相容范数都有 (A)|A| （6.2）特征值上界特征值上界2022-2-5第六章 线性方程组的迭代解法14 另一个更深刻的结果另一个更深刻的结果,对于任意的对于任意的0，必存在一种相，必存在一种相容的矩阵范数，使容的矩阵范数，使| A | (A) （6.3） 式（式（6.2）和（）和（6.3）表明，矩阵）表明，矩阵A的的谱半径谱半径是它所有相是它所有相容范数的容范数的下确界下确界。定义定义6.4 设有设有nn矩阵序列矩阵序列 和和n阶阶方阵方阵A（aij）, 如果如果 ()()(),1,2,kkijAak 0|lim)( AAkk记作

15、记作 A（k）A，或，或 A（k）A。 klim称称 A（k）收敛于收敛于A， 定理：定理：设有设有nn矩阵序列矩阵序列 收敛于收敛于nn矩阵矩阵A（aij）的充要条件为）的充要条件为 ()()(),1,2,kkijAak n,j, i,aalimij)k(ijk21 2022-2-5第六章 线性方程组的迭代解法15121221.00012xxxx 121221.00012.0001xxxx 中扰动对结果的影响方程组bAx 0, 221xx1, 121xx扰动扰动( (改变量改变量) )解对原始数解对原始数据变化敏感据变化敏感四、矩阵的条件数四、矩阵的条件数如何定量描述这种现象？扰动（误差）对

16、解的影响如何定量描述这种现象？扰动（误差）对解的影响有多大？有多大？2022-2-5第六章 线性方程组的迭代解法16 引进了矩阵的度量标准引进了矩阵的度量标准范数范数，就可以对方程组求，就可以对方程组求解进行误差分析，对于方程组解进行误差分析，对于方程组Ax =b如果常数项产生了误差如果常数项产生了误差b, 并设求解时产生的误差为并设求解时产生的误差为x，则有则有A(x + x) =b+ b两式相减得到两式相减得到 A x = b当系数矩阵可逆时当系数矩阵可逆时x = A-1b取范数取范数|x| = |A-1b| |A-1 | |b|再由再由 Ax =b，得到，得到| b|= | Ax |A

17、| |x|绝对误差绝对误差2022-2-5第六章 线性方程组的迭代解法17于是，由于是，由 | x |A-1 | |b|得到解的得到解的相对误差相对误差为为bAx 11xbAAxb 及及 |b | |A | |x|令令 Cond(A)=|A | |A-1 | ,并称其为矩阵并称其为矩阵A的的条件数条件数。这时这时bbACondxx )(可见，求解线性方程组所产生的可见，求解线性方程组所产生的误差误差与系数矩阵的与系数矩阵的条件数条件数有关。有关。2022-2-5第六章 线性方程组的迭代解法18 对于线性方程组对于线性方程组 Ax=b，如果系数矩阵的条件数如果系数矩阵的条件数Cond(A)=|A

18、 | |A-1 | 太大，则称该方程组为太大，则称该方程组为病态方程组。病态方程组。 病态现象是方程组的固有属性，病态现象是方程组的固有属性，无法改变无法改变，因此在求，因此在求解时为了不至于产生太大的误差，应该尽量减少原始数据解时为了不至于产生太大的误差，应该尽量减少原始数据 A、b 的误差，或者用高精度的计算机计算。的误差，或者用高精度的计算机计算。例如：对于方程组例如：对于方程组121221.00012xxxx 系数矩阵和逆矩阵分别为系数矩阵和逆矩阵分别为 44441101010101,0001.1111AA可以求得可以求得 1)(AAACond442.0001(1210 )410 条件

19、数比较大，可见该方程组为条件数比较大，可见该方程组为病态方程组病态方程组。多大算病态没有标准。如果主元很小或者元素数量级相差大，可能是病态多大算病态没有标准。如果主元很小或者元素数量级相差大，可能是病态1)(11AAAAAcond2022-2-5第六章 线性方程组的迭代解法192 2 迭代解法与收敛性迭代解法与收敛性一、迭代解法一、迭代解法设有线性方程组设有线性方程组 Ax=b (1) ARnn, bRn .对对A 进行进行， A=A1+A2 , 其中其中 A1 可逆可逆，则则 (A1+A2)x=b A1x = - A2x+b令令 B= - A1-1 A2 , F =A1-1 b则则 x= B

20、x+F (2) x = - A1-1 A2 x + A1-1 b2022-2-5第六章 线性方程组的迭代解法20得到得到 x(1)= Bx(0)+F 称称(3)为求解为求解(1)的近似解的的近似解的，称，称x(k)为为(1)的的近似解序列，称近似解序列，称B为为迭代矩阵迭代矩阵。如果如果*)(limxxkk则有则有 x(2)= Bx(1)+F x(k+1)= Bx(k)+F , k=0 ,1 , , （3）x*= Bx*+F （4）我们称迭代法我们称迭代法(3)收敛收敛，否则为，否则为发散发散。下面分析迭代格。下面分析迭代格式式(3)收敛的条件收敛的条件. 由由 x= Bx+Fx(0)Rn确定

21、迭代格式确定迭代格式不动点不动点2022-2-5第六章 线性方程组的迭代解法21由由(3) (4)得得 x(k+1) - x* = B(x(k)- x* ) 令令 e(k)= x(k)- x* , 则有则有(1)( )2 (1)1 (0)kkkkeBeB eBe+ +- -+ += = = = =L L若若 x(k+1) x* ,则则 e(k+1) 0。这时只有这时只有 Bk+1 0 （k ）。）。x(k+1)= Bx(k)+F , k=0 ,1 , , （3）x*= Bx*+F （4）而而 Bk+1 0 (B)1，由此可得如下的收敛性条件。，由此可得如下的收敛性条件。2022-2-5第六章

22、线性方程组的迭代解法22二、迭代法收敛性条件二、迭代法收敛性条件 x(k+1)= Bx(k)+F , k=0 ,1 , , （3）定理定理6.3 若若 |B|1 ，则迭代格式，则迭代格式(3)(3)收敛收敛. . 定理定理6.4 若若 |B|1 ，则有估计式，则有估计式 定理定理6.2 迭代法格式迭代法格式(3)(3)收敛的收敛的充要条件充要条件是是(B)1. .（不好算）（不好算） 这是一个这是一个，根据范数与谱半径的关系式，根据范数与谱半径的关系式 (B)|B| ，容易推出该充分条件，容易推出该充分条件.()(1)(0)*1 kkBxxxxB)1()()(1* kkkxxBBxx迭代法基迭

23、代法基本定理本定理收敛只与收敛只与B有关，且有关，且(B)越小收敛越快越小收敛越快后验误后验误差估计差估计先验误先验误差估计差估计( )(0)(0)(0)*()(2)11kkkBBxxBxFxFxBB 2022-2-5第六章 线性方程组的迭代解法233 3 常用的三种迭代解法常用的三种迭代解法一、一、Jacobi迭代法迭代法对于线性方程组对于线性方程组 Ax=b (1) A=L+D+U (2)设设 det(A) 0 ，aii 0, i=0,1,2,n ，按照如下方式对，按照如下方式对A进行分裂：进行分裂： 0000002121nnaaaL nnaaaD0000002211 0000002112

24、nnaaaUL ,U称为严称为严格下（上）格下（上）三角阵三角阵2022-2-5第六章 线性方程组的迭代解法24则由则由 Ax=b 得到得到令令 BJ=-D-1(L+U) ， FJ= D-1 b.(L+D+U) x=b D x=-(L+U)x+b x=-D-1(L+U)x+ D-1 b则有则有 x= BJ x+ FJ (3)任取初始向量任取初始向量 x(0)Rn , 则可以由上式得到如下的迭代则可以由上式得到如下的迭代格式：格式：并称其为并称其为Jacobi迭代格式迭代格式（简单迭代法（简单迭代法/ /同步迭代法）同步迭代法），迭，迭代矩阵为代矩阵为 x(k+1)= BJ x(k)+ FJ (

25、4)BJ=-D-1(L+U) = -D-1(A - D)= E - D-1 A2022-2-5第六章 线性方程组的迭代解法25例如例如, 对于三元线性方程组对于三元线性方程组 232131333332312122223132121111xaxabxaxaxabxaxaxabxa 333323213123232221211313212111bxaxaxabxaxaxabxaxaxa )(1)(1)(1232131333332312122223132121111xaxabaxxaxabaxxaxabax2022-2-5第六章 线性方程组的迭代解法26 得到具体的迭代格式得到具体的迭代格式由定理由定

26、理6.4的结论的结论, ,可以通过可以通过| x(k+1)-x(k)|控制迭代次数。控制迭代次数。x(0)Rn(1)( )( )1112213311(1)( )( )2221123322(1)( )( )33311322331()1()1()kkkkkkkkkxba xa xaxba xa xaxba xa xa ,k210 2022-2-5第六章 线性方程组的迭代解法27对于对于 n 元线性方程组元线性方程组其一般式为：其一般式为：从中解出：从中解出： 得得Jacobi迭代格式迭代格式通过通过 | x(k+1)-x(k)| 控制迭代次数。控制迭代次数。)(1111 nijjijijjijii

27、iixaxabax)(11)(11)()1( nijkjijijkjijiiikixaxabaxininiiiiiiiiiibxaxaxaxaxa 111111 nnnnnnnnnbxaxaxabxaxaxabxaxaxa322112222212111212111n,i21 n,i21 n,i21 ,k210 分量形式分量形式2022-2-5第六章 线性方程组的迭代解法28二二、 Gauss-Seidel迭代法迭代法对于三元方程组对于三元方程组，将，将Jacobi迭代格式迭代格式改进为改进为(1)()()11122133111()kkkxbaxaxa+ += =- - -(1)(1)()222

28、11233221()kkkxbaxaxa+ + += =- - -(1)(1)(1)33311322331()kkkxbaxaxa+ + + += =- - -并称其为并称其为Gauss-Seidel迭代格式迭代格式（异步迭代法异步迭代法）。 )(1)(1)(1)(232)(131333)1(3)(323)(121222)1(2)(313)(212111)1(1kkkkkkkkkxaxabaxxaxabaxxaxabax,k210 2022-2-5第六章 线性方程组的迭代解法29对于对于n元方程元方程 先写出先写出Jacobi迭代格式迭代格式同样可以用同样可以用 | x(k+1)-x(k)|

29、控制迭代次数。控制迭代次数。 再写出再写出Gauss-Seidel迭代格式迭代格式ininiiiiiiiiiibxaxaxaxaxa 111111)(11)(11)()1( nijkjijijkjijiiikixaxabax)(11)(11)1()1( nijkjijijkjijiiikixaxabaxn,i21 ,k210 n,i21 2022-2-5第六章 线性方程组的迭代解法30 为讨论为讨论收敛性收敛性方便，下面再写出方便，下面再写出Gauss-Seidel迭代格迭代格式的式的矩阵表示式矩阵表示式。首先将。首先将Gauss-Seidel迭代格式迭代格式改写为：改写为：(1)()()kk

30、LD xUxb+ + += = - -+ +(1)1( )1()()kkxLDUxLDb+ +- - -= = - -+ + + +)(11)(11)1()1( nijkjijijkjijiiikixaxabax nij)k(jiji)k(iiiij)k(jijxabxaxa11111ikninkiiikiiikiiikibxaxaxaxaxa )()(11) 1() 1(11) 1(11n,i21 nnnnaaaaaaDL21222111000(1)1(1)(1)2(1)kkkknxxxx 2022-2-5第六章 线性方程组的迭代解法31令令 11(),()GGBLDU FLD- - -=

31、= - -+ += =+ +则有则有 (1)(),kkGGxB xF+ += =+ +其中其中 BG 为迭代矩阵。为迭代矩阵。(1)1( )1()()kkxLDUxLDb+ +- - -= = - -+ + + + 例例6.3 用用Jacobi迭代法和迭代法和Gauss-Seidel迭代法解下列方迭代法解下列方程组程组,已知方程组得精确解为已知方程组得精确解为 x*=(1，1，1)T 。 141035310214310321321321xxxxxxxxx,k210 2022-2-5第六章 线性方程组的迭代解法32解：先改写方程如下解：先改写方程如下再写出再写出Jacobi迭代格式迭代格式取初值

32、为取初值为: x(0)=(0，0，0)T , 求得求得:x(1)=(1.4，0.5，1.4)Tx(6)=(1.00025，1.00580，1.00251)T误差为由误差为由x*=(1，1，1)T 得到得到 |x(6)-x*|=0.00580 。 123213312114310152310114310 xxxxxxxxx (1)( )( )123(1)( )( )213(1)( )( )312114310152310114310kkkkkkkkkxxxxxxxxx ,k210 2022-2-5第六章 线性方程组的迭代解法33初值也取为初值也取为: x(0)=(0，0，0)T , 求得近似解：求得

33、近似解：Gauss-Seidel迭代格式为迭代格式为误差为由误差为由x*=(1，1，1)T 得到得到 |x(4)-x*|=0.00846 。 Jacobi迭代法迭代迭代法迭代6次与次与Gauss-Seidel迭代法迭代迭代法迭代4次的次的精度一致，说明精度一致，说明Gauss-Seidel迭代法收敛较快（迭代法收敛较快（一定条件一定条件下下）,求出求出 后后 不用保存不用保存。x(1)=(1.4，0.78，1.026)Tx(4)=(0.99154，0.99578，1.00210)T (1)( )( )123(1)(1)( )213(1)(1)(1)312114310152310114310kk

34、kkkkkkkxxxxxxxxx ,k210 )1( kjx)(kjx2022-2-5第六章 线性方程组的迭代解法34三三.超松弛超松弛(SOR)迭代法迭代法 (Successive Over Relaxation Method)对对Gauss-Seidel迭代进行改写迭代进行改写令令 nijkjijijkjijiiikixaxabax1)(11)1()1(1 nijkjijkiiiijkjijiiixaxaxaba)()(11)1(1 nijkjijijkjijiiikixaxabax)(11)1()(1 nijkjijijkjijiiikikikixaxabaxxr)(11)1()()1(

35、)(1 即为在即为在第第 k次迭代次迭代时的改变量时的改变量(增量增量)。2022-2-5第六章 线性方程组的迭代解法35再通过再通过加权加速收敛加权加速收敛： (1)()()kkkiiixxr+ += =+ +1()(1)()1inkkkiiijjijjjjiiixba xa xa 并称其为并称其为超松弛迭代法超松弛迭代法，称为称为松弛因子松弛因子。当当 0 1 时，称为时，称为低松弛低松弛； 当当 =1 时，为时，为Gauss-Seidel 迭代格式迭代格式 ；当当 1 2 时，称为时，称为高松弛高松弛。 ,k210 n,i21 )1()()()1()()1(1kikikikikikixx

36、xxxx加权平均加权平均2022-2-5第六章 线性方程组的迭代解法36超松弛迭代法超松弛迭代法(SOR)也可以用也可以用矩阵的形式矩阵的形式来表示来表示 (1)1( )1()()()kkxDLD DU x DLb+ +- - -= =+ +- -+ + + +令令 B =(D+ L)-1D- (D+U)则有则有 x(k+1)=B x(k)+F , k=0,1, 2 , 。1(1)()(1)()1inkkkkiiiijjijjjjiiixxba xa xa 1(1)()(1)()1inkkkkiiiiiiiijjijjjjia xa x ba xa x 改写改写SOR为为或者或者 (1)()(

37、)()kkDL xD DUxb+ + += =- -+ + +F = (D+L)-1 bn,i21 2022-2-5第六章 线性方程组的迭代解法37(1)11 1( 1)111(1)(1)22 221 1(1)2122(1)21(1)(1)(1)121000()kkkkkknkkknnnnnn nijjnja xaxa xa xaaxL Dxaaaa xa xx F说明：说明： (1)()()()kkDL xD DUxb+ + += =- -+ + +( )11111211( )22222( )2( )00000()0000knknkknnnnnaaaaxaaaxDD U xaax n,i21

38、 2022-2-5第六章 线性方程组的迭代解法38( )11111211( )22222( )2( )( )111( )222( )00000()0000000000knknkknnnnnkkknnnaaaaxaaaxDD U xaaxaxaxax ( )111211( )2222( )( )1( )1111( )( )22222( )( )000knknknnnnkjjkjknkjjjknnnknnnaaaxaaxaxa xa xa xa xa xa x n,i21 2022-2-5第六章 线性方程组的迭代解法39 定理定理6.6 Gauss-Seidel 迭代法迭代法 收敛的收敛的充要条件

39、充要条件是是(BG)1 ，收敛的，收敛的充分条件充分条件是是 |BG|1 。 定理定理6.7 对于对于 线性方程组线性方程组 Ax=b ，如果系数矩阵，如果系数矩阵A严格严格对角占优对角占优，则，则Jacobi、G-S迭代法都收敛。迭代法都收敛。定理定理6.8 SOR迭代法收敛的迭代法收敛的必要条件必要条件是是 0 2 。 定理定理6.9 如果系数矩阵如果系数矩阵A对称对称正定正定，且，且 0 2 ，则，则SOR 法收敛法收敛定理定理6.10 如果系数矩阵如果系数矩阵A对称正定对称正定，则，则G-S迭代法收敛。迭代法收敛。四、收敛性条件四、收敛性条件 定理定理6.5 Jacobi迭代法收敛的迭

40、代法收敛的充要条件充要条件是是(BJ)1 ，收敛的收敛的充分条件充分条件是是 |BJ |111/30010010/3()3/41/4 00015/2GBDLU- -轾轾轾轾轾轾- - -犏犏犏犏犏犏= = - -+ += = - -= =犏犏犏犏犏犏- - -臌臌臌臌臌臌10/315det()()0015/22GIB - -= = =+ += =+ +解得特征值解得特征值12150,2= -= -谱半径谱半径 (BG)1故故Jacobi迭代法迭代法和和Gauss-Seidel迭代法均发散迭代法均发散.但可以交换两个方程的次序，将原方程变为同解方程组但可以交换两个方程的次序，将原方程变为同解方程

41、组 71035492121xxxx这时方程组得系数矩阵严格这时方程组得系数矩阵严格对角占优，对角占优，两种迭代法都收敛两种迭代法都收敛。2022-2-5第六章 线性方程组的迭代解法42例例6.5 用用Jacobi迭代法解下列方程组，问是否收敛？迭代法解下列方程组，问是否收敛？ 解：方程组的系数矩阵为解：方程组的系数矩阵为 112130207A 非严格对角占优，非严格对角占优，无法判断迭代法是否收敛无法判断迭代法是否收敛。需要通过谱。需要通过谱半径判断，先写出半径判断，先写出Jacobi迭代法的迭代矩阵：迭代法的迭代矩阵：1()JBDLU- -= = - -+ +1()DAD- -= = - -

42、 -1EDA- -= =- 由于无穷范数由于无穷范数 |BJ |=31,还无法判断迭代法是否收敛。还无法判断迭代法是否收敛。 27213523121321xxxxxxx2022-2-5第六章 线性方程组的迭代解法43这时只能通过求迭代矩阵的谱半径来判断，由迭代矩阵这时只能通过求迭代矩阵的谱半径来判断，由迭代矩B 132712det()000JIB- - -= = - -= =解得特征值解得特征值12319190,2121= = = = - -谱半径谱半径 (BJ)1故故Jacobi迭代法收敛迭代法收敛.2022-2-5第六章 线性方程组的迭代

43、解法44 例例6.6 分别用分别用Jacobi迭代法和迭代法和Gauss-Seidel迭代法解下迭代法解下列方程组，问是否收敛？列方程组，问是否收敛？ 由于该矩阵非严格对角占优，由于该矩阵非严格对角占优，无法判断无法判断；但由于对称，再；但由于对称，再看是否正定。看是否正定。解：系数矩阵为解：系数矩阵为 各阶顺序主子式各阶顺序主子式 |A1|=1, |A2|=3/4, |A3|=1/2, 说明矩阵对称正定说明矩阵对称正定所以所以Gauss-Seidel迭代法收敛迭代法收敛。但无法判断。但无法判断Jacobi迭代法是迭代法是否收敛，再利用迭代矩阵的范数或者谱半径进行判断。否收敛，再利用迭代矩阵的

44、范数或者谱半径进行判断。 111212121212121A 221211212152121321321321xxxxxxxxx2022-2-5第六章 线性方程组的迭代解法45由系数矩阵由系数矩阵写出写出Jacobi迭代矩阵迭代矩阵其其-范数范数 |BJ |=1 和和 1-范数范数|BJ |1=1，不小于，不小于1，还无还无法判断是否收敛法判断是否收敛。再求其谱半径进行判断。再求其谱半径进行判断。由由 det(I-BJ)=0 求得特征值求得特征值1 = -1，2= 3=0.5 谱半径谱半径 (BJ)=|1| = 1，由此可知由此可知Jacobi迭代法发散。迭代法发散。 1112121212121

45、21A 000212121212121JB2022-2-5第六章 线性方程组的迭代解法46 例例6.7 取初值取初值 x(0)=(0，0，0)T 用用Jacobi迭代法解下列迭代法解下列方程组，如果要保证各分量的误差的绝对值小于方程组，如果要保证各分量的误差的绝对值小于10-6,问需问需要迭代多少次？要迭代多少次？ 解：由于方程组得系数矩阵严格对角占优，所以解：由于方程组得系数矩阵严格对角占优，所以Jacobi迭代法收敛。要确定迭代次数需要用到估计式迭代法收敛。要确定迭代次数需要用到估计式其中其中 BJ=E-D-1A ， FJ= D-1 b，范数用范数用-范数范数 。( )(0)*(2)1kkBxxFxB 30153212814322032132