第四章 线性方程组迭代解法 (2)优秀PPT.ppt

《第四章 线性方程组迭代解法 (2)优秀PPT.ppt》由会员分享，可在线阅读，更多相关《第四章 线性方程组迭代解法 (2)优秀PPT.ppt（75页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第四章 线性方程组迭代解法第一页，本课件共有75页第四章目录1 向量序列与矩阵序列的极限向量序列与矩阵序列的极限2 Jacobi迭代法迭代法3 GaussSeidel迭代法迭代法4 松驰法松驰法5 迭代法的收敛条件及误差估计迭代法的收敛条件及误差估计 5.1 矩阵的谱半径矩阵的谱半径 5.2 迭代法的收敛条件迭代法的收敛条件 5.3 误差估计误差估计第二页，本课件共有75页第四章 方程组的迭代解法概述 这一章讨论线性方程组的另一类解法这一章讨论线性方程组的另一类解法这一章讨论线性方程组的另一类解法这一章讨论线性方程组的另一类解法迭代法，由于迭代法，由于迭代法，由于迭代法，由于迭代法能充分避免系

2、数矩阵中零元的存贮与计算，因此特别迭代法能充分避免系数矩阵中零元的存贮与计算，因此特别迭代法能充分避免系数矩阵中零元的存贮与计算，因此特别迭代法能充分避免系数矩阵中零元的存贮与计算，因此特别适用于求解系数矩阵阶数很高而零元素又很多（即大型稀疏）适用于求解系数矩阵阶数很高而零元素又很多（即大型稀疏）适用于求解系数矩阵阶数很高而零元素又很多（即大型稀疏）适用于求解系数矩阵阶数很高而零元素又很多（即大型稀疏）的线性方程组。的线性方程组。的线性方程组。的线性方程组。解线性方程组的迭代法的基本思想与解方程的迭代法相解线性方程组的迭代法的基本思想与解方程的迭代法相解线性方程组的迭代法的基本思想与解方程的迭

3、代法相解线性方程组的迭代法的基本思想与解方程的迭代法相似，首先将方程组似，首先将方程组似，首先将方程组似，首先将方程组AxAx=b b化为等价方程组化为等价方程组化为等价方程组化为等价方程组x x=MxMx+g g，其中，其中，其中，其中MM为为为为n n阶方阵，阶方阵，阶方阵，阶方阵，b b=(=(b b1 1,b b2 2,b bn n)T T，g g R Rn n，任取初始向量，任取初始向量，任取初始向量，任取初始向量x x(0)(0)R Rn n，代入迭代公式：代入迭代公式：代入迭代公式：代入迭代公式：产生向量序列产生向量序列产生向量序列产生向量序列 x x(k k)，若此序列收敛于，

4、若此序列收敛于，若此序列收敛于，若此序列收敛于x x*，则有，则有，则有，则有x x*=*=MxMx*+g+g，即，即，即，即x x*为原方程组的解。因此，可根据精度要求选择一个合适的为原方程组的解。因此，可根据精度要求选择一个合适的为原方程组的解。因此，可根据精度要求选择一个合适的为原方程组的解。因此，可根据精度要求选择一个合适的x x(k k)（k k充分大时）作为近似解，这就是解线性方程组的迭代法，充分大时）作为近似解，这就是解线性方程组的迭代法，充分大时）作为近似解，这就是解线性方程组的迭代法，充分大时）作为近似解，这就是解线性方程组的迭代法，上式称为迭代格式，上式称为迭代格式，上式称

5、为迭代格式，上式称为迭代格式，MM称为迭代矩阵，若序列称为迭代矩阵，若序列称为迭代矩阵，若序列称为迭代矩阵，若序列 x x(k k)极限存极限存极限存极限存在，称此迭代过程收敛，否则称为发散。在，称此迭代过程收敛，否则称为发散。在，称此迭代过程收敛，否则称为发散。在，称此迭代过程收敛，否则称为发散。第三页，本课件共有75页1 向量与矩阵的范数 与求解方程类似，需要讨论的问题是：如何建与求解方程类似，需要讨论的问题是：如何建立迭代公式，向量序列的收敛条件是什么，若向量立迭代公式，向量序列的收敛条件是什么，若向量序列序列x(k)收敛，如何进行误差估计？收敛，如何进行误差估计？第四页，本课件共有75

6、页4.1 向量与矩阵的范数 这三个性质刻画了向量长度的基本特征，并可以用其将平这三个性质刻画了向量长度的基本特征，并可以用其将平面向量长度的概念推广到一般面向量长度的概念推广到一般n维向量，于是有如下定义：维向量，于是有如下定义：定义定义1下屏将给出范数的种类：下屏将给出范数的种类：第五页，本课件共有75页常用的向量范数 容易证明它们都满足上述三条性质。可以看出，容易证明它们都满足上述三条性质。可以看出，2范范数是平面向量长度计算公式在形式上的推广，也是线性代数是平面向量长度计算公式在形式上的推广，也是线性代数是平面向量长度计算公式在形式上的推广，也是线性代数是平面向量长度计算公式在形式上的推

7、广，也是线性代数中的内积定义。此处引入多种范数来刻画向量的大小，数中的内积定义。此处引入多种范数来刻画向量的大小，数中的内积定义。此处引入多种范数来刻画向量的大小，数中的内积定义。此处引入多种范数来刻画向量的大小，是为了在不同情况下用不同的范数研究问题。是为了在不同情况下用不同的范数研究问题。向量范数的证明：（只对第三条）向量范数的证明：（只对第三条）向量范数的证明：（只对第三条）向量范数的证明：（只对第三条）对对对对 范数：前面范数：前面范数：前面范数：前面2条显然，对第三条，由于对任意实数条显然，对第三条，由于对任意实数条显然，对第三条，由于对任意实数条显然，对第三条，由于对任意实数x,y

8、，绝，绝对值不等式：对值不等式：|x+y|y|x|+|y|成立，因而有成立，因而有:分别称为向量分别称为向量x的的2范数，范数，1范数，无穷范数。范数，无穷范数。第六页，本课件共有75页对2范数利用实数的柯西不等式利用实数的柯西不等式：于是，有：于是，有：常用的向量范数（续）常用的向量范数（续）第七页，本课件共有75页Rn中范数的等价性 例如可证明如下等价性：例如可证明如下等价性：所以，所以，2范范范范数与数与 范数范数是等价的。是等价的。不难证明：不难证明：亦即亦即1范数与范数与 范数是等价的范数是等价的。事实上事实上:Rn 中任意中任意两种范数两种范数都是等价都是等价的的。第八页，本课件共

9、有75页矩阵范数 定义定义2对任意对任意n阶方阵阶方阵A A=(aij)n n，若对应一个非负实数，若对应一个非负实数|A|，满足：，满足：则称则称|A|为矩阵为矩阵A的范数。的范数。与向量范数定义比较，前三条性质只是向量范与向量范数定义比较，前三条性质只是向量范数定义的推广，而第四条性质则是矩阵乘法性质数定义的推广，而第四条性质则是矩阵乘法性质的要求，它使矩阵范数在数值计算中使用更方便。的要求，它使矩阵范数在数值计算中使用更方便。第九页，本课件共有75页常用的矩阵范数常用的矩阵范数有：常用的矩阵范数有：它们分别叫做矩阵的它们分别叫做矩阵的 范数，范数，1范数，范数，范数，范数，2范数，范数，

10、F范数，范数，范数，范数，矩阵矩阵F F范数是向量范数是向量范数是向量范数是向量2范数的推广，矩阵范数的推广，矩阵 范数，范数，1范数计算范数计算容易，而矩阵容易，而矩阵2范数与范数与ATA的特征值有关，所以又称为谱的特征值有关，所以又称为谱的特征值有关，所以又称为谱的特征值有关，所以又称为谱范数，它的计算较困难，但因为它有一些好的性质，所范数，它的计算较困难，但因为它有一些好的性质，所以也是常用的范数。以也是常用的范数。以也是常用的范数。以也是常用的范数。第十页，本课件共有75页常用的矩阵范数（续）可以证明，这些范数都满足定义可以证明，这些范数都满足定义2。以以|A A|为例，前为例，前为例

11、，前为例，前2 2条性质显然成立，而对：条性质显然成立，而对：第十一页，本课件共有75页最大行和矩阵范数的证明第十二页，本课件共有75页最大行和矩阵范数的证明第十三页，本课件共有75页范数的相容性 在误差估计中，由于矩阵与向量会同时用到，我们总在误差估计中，由于矩阵与向量会同时用到，我们总希望有上面的不等式成立，希望有上面的不等式成立，希望有上面的不等式成立，希望有上面的不等式成立，但对任意的向量范数与矩阵范数却但对任意的向量范数与矩阵范数却未必如此，因而特别地把满足此不等式的范数称为相容的，可未必如此，因而特别地把满足此不等式的范数称为相容的，可以证明，上述常用的范数是相容的，即有：以证明，

12、上述常用的范数是相容的，即有：在使用范数时，应选用相容的矩阵范数与向量范数。在使用范数时，应选用相容的矩阵范数与向量范数。分别称为分别称为 的关于的关于P范数的范数的绝对误差与相对误差。绝对误差与相对误差。有了矩阵范数，就可以用它描述矩阵的误差，设有了矩阵范数，就可以用它描述矩阵的误差，设 是是A的的近似矩阵，近似矩阵，称为称为 的的残差阵残差阵，则：，则：第十四页，本课件共有75页求范数举例例例10第十五页，本课件共有75页 向量序列与矩阵序列的极限 与求解方程类似，需要讨论的问题是：如何建与求解方程类似，需要讨论的问题是：如何建与求解方程类似，需要讨论的问题是：如何建与求解方程类似，需要讨

13、论的问题是：如何建立迭代公式，向量序列的收敛条件是什么，若向量立迭代公式，向量序列的收敛条件是什么，若向量立迭代公式，向量序列的收敛条件是什么，若向量立迭代公式，向量序列的收敛条件是什么，若向量序列序列序列序列x(k)收敛，如何进行误差估计？收敛，如何进行误差估计？1 向量序列与矩阵序列的极限向量序列与矩阵序列的极限 由于由于由于由于Rn中的向量可与中的向量可与中的向量可与中的向量可与Rn的点建立一一对应关系，的点建立一一对应关系，因此由点列的收敛概念及向量范数的等价性，可得因此由点列的收敛概念及向量范数的等价性，可得到向量序列的收敛概念。到向量序列的收敛概念。定义定义定义定义3第十六页，本课

14、件共有75页 向量序列与矩阵序列的极限（续）n维点列收敛的一种等价描述是其对应坐标序列均维点列收敛的一种等价描述是其对应坐标序列均维点列收敛的一种等价描述是其对应坐标序列均维点列收敛的一种等价描述是其对应坐标序列均收敛，向量序列也有类似的结论。收敛，向量序列也有类似的结论。定理定理1 第十七页，本课件共有75页矩阵序列的收敛概念及定理定义定义3 3完全类似地，可以定义矩阵序列的收敛：完全类似地，可以定义矩阵序列的收敛：与向量序列类似，也有：与向量序列类似，也有：定理定理2 第十八页，本课件共有75页4.3 矩阵的谱半径矩阵的谱半径 迭代法的收敛性与迭代矩阵的特征值有关：迭代法的收敛性与迭代矩阵

15、的特征值有关：设设设设A A为为n阶方阵，阶方阵，i(i=1,2,=1,2,，n)为为为为A A的特征值，的特征值，称特征值模的最大值为矩阵称特征值模的最大值为矩阵称特征值模的最大值为矩阵称特征值模的最大值为矩阵A的谱半径，记为：的谱半径，记为：定义定义5第十九页，本课件共有75页矩阵的谱半径（续）矩阵的谱半径与范数之间有如下关系：矩阵的谱半径与范数之间有如下关系：矩阵的谱半径与范数之间有如下关系：矩阵的谱半径与范数之间有如下关系：设设x为对应于特征值为对应于特征值为对应于特征值为对应于特征值 的的A的特征向量，则由：的特征向量，则由：的特征向量，则由：的特征向量，则由：这个不等式对这个不等式

16、对A的任何范数、任意特征值都成立，的任何范数、任意特征值都成立，因此，可得矩阵因此，可得矩阵因此，可得矩阵因此，可得矩阵A的谱半径与的谱半径与A的范数之间的一个重要的范数之间的一个重要的范数之间的一个重要的范数之间的一个重要关系：关系：A的谱半径不超过的谱半径不超过A的任一种范数。即：的任一种范数。即：第二十页，本课件共有75页公式 的重要性说明 它之所以重要是因为：它之所以重要是因为：(A A)难计算，而难计算，而|A A|、|A|1 1计算容易，并且对于任意正数计算容易，并且对于任意正数 ，存在一种矩阵范数，存在一种矩阵范数很接近很接近 (A)，使得成立：，使得成立：，使得成立：，使得成立

17、：对任意对任意n阶方阵阶方阵A，一般不存在矩阵范数使，一般不存在矩阵范数使(A)=|A|A|，但若，但若A为对称矩阵，则有：为对称矩阵，则有：下面的结论对建立迭代法的收敛条件十分重要下面的结论对建立迭代法的收敛条件十分重要：定理定理3第二十一页，本课件共有75页定理3（续）证明：证明：第二十二页，本课件共有75页由由由由5.1 的结果，可以得到如下收敛定理的结果，可以得到如下收敛定理：定理定理定理定理4对任意初始向量对任意初始向量x(0)和右端项和右端项g，由迭代格式：，由迭代格式：证明：证明：第二十三页，本课件共有75页推论推论1第二十四页，本课件共有75页 可以看出，后两个方程组与第一个方

18、程组相可以看出，后两个方程组与第一个方程组相比，系数矩阵或右端向量仅有比，系数矩阵或右端向量仅有0.0005以下的误差，以下的误差，但准确解却相差很大。但准确解却相差很大。4.2 方程组的误差分析 数值稳定的算法是否一定能求得精度比较高数值稳定的算法是否一定能求得精度比较高的解呢？回答是不一定，解的精度还与方程组本的解呢？回答是不一定，解的精度还与方程组本身的性态有关，下面来考察几个例：身的性态有关，下面来考察几个例：例例11第二十五页，本课件共有75页例例12若其系数，常数项改用三位有效数字的小数表示，若其系数，常数项改用三位有效数字的小数表示，则方程组为则方程组为：第二十六页，本课件共有7

19、5页右端项右端项b产生产生0.1%的变化的变化引起解的变化引起解的变化最大变化最大变化184%。初始数据的误差（相对）初始数据的误差（相对）0.3%=0.003，而解的相对误差却超过，而解的相对误差却超过50%。例例13第二十七页，本课件共有75页方程组的性态讨论 病态、良态 在许多实际问题中，线性方程组的系数矩阵和在许多实际问题中，线性方程组的系数矩阵和右端项的元素大多为前面计算的结果，因此上述右端项的元素大多为前面计算的结果，因此上述例中的微小误差是避免不了。而对上述例中的方例中的微小误差是避免不了。而对上述例中的方程组，无论用多么稳定的算法求解，计算中产生程组，无论用多么稳定的算法求解，

20、计算中产生的微小误差就使解面目全非，所以这些方程组的的微小误差就使解面目全非，所以这些方程组的性态是很差的。性态是很差的。当方程组当方程组Ax=b的系数矩阵与右端向量的系数矩阵与右端向量b的微的微小变动（小扰动）而引起解严重失真时，称此方小变动（小扰动）而引起解严重失真时，称此方程组为病态方程组，其系数矩阵程组为病态方程组，其系数矩阵A称为病态矩阵，称为病态矩阵，否则称为良态方程组，否则称为良态方程组，A称为良态矩阵，为了定量称为良态矩阵，为了定量刻画方程组刻画方程组“病态病态”的程度，下面对方程组的程度，下面对方程组Ax=b在在系数矩阵系数矩阵A及右端项及右端项b有扰动的几种情形进行讨论。有

21、扰动的几种情形进行讨论。第二十八页，本课件共有75页 此不等式表明，当右端项有扰动时，解的相对误差不此不等式表明，当右端项有扰动时，解的相对误差不超过超过b的相对误差的的相对误差的 倍。倍。首先考察右端项首先考察右端项b的扰动对解的影响，设的扰动对解的影响，设b有扰有扰动动 b，A为准确为准确,记引起解记引起解x的扰动为的扰动为 x,即：即：第二十九页，本课件共有75页方程组的性态讨论（续2）当当b为精确的而为精确的而A有微小扰动有微小扰动 A时，在时，在 A充分小时充分小时也同样可推得：也同样可推得：紧接下屏讨论：紧接下屏讨论：第三十页，本课件共有75页第三十一页，本课件共有75页方程组的性

22、态讨论续（3）而当而当而当而当A A,b b同时有微小扰动同时有微小扰动 A，b时，则可进一步导出更一时，则可进一步导出更一般的误差估计式：般的误差估计式：注意到：注意到：第三十二页，本课件共有75页在在 b充分小时，充分小时，此式右端实际上即此式右端实际上即为：为：方程组的性态讨论续（4）第三十三页，本课件共有75页矩阵的条件数 在三种情况下得到的这三个不等式反映了解的相对误在三种情况下得到的这三个不等式反映了解的相对误差与差与差与差与A及及b的相对误差的关系；数的相对误差的关系；数的相对误差的关系；数的相对误差的关系；数|A|AA|A-1|越小，解的相对越小，解的相对越小，解的相对越小，解

23、的相对误差也越小；反之数误差也越小；反之数误差也越小；反之数误差也越小；反之数|A|A-1|越大，解的相对误差也越大，实越大，解的相对误差也越大，实际上这个数反映了解对方程组原始数据的敏感程度，揭示了矩际上这个数反映了解对方程组原始数据的敏感程度，揭示了矩阵阵A和方程组本身的性态，称之为方程组或矩阵和方程组本身的性态，称之为方程组或矩阵A A的的条件数条件数，记作：记作：cond(A)越大，越大，A的病态程度越严重。至于的病态程度越严重。至于condcond(A)多大才多大才算病态，这是一个相对概念，没有一个严格的数量界限。算病态，这是一个相对概念，没有一个严格的数量界限。算病态，这是一个相对

24、概念，没有一个严格的数量界限。算病态，这是一个相对概念，没有一个严格的数量界限。第三十四页，本课件共有75页判断病态矩阵的几点参考 求条件数要计算逆阵的范数，很不方便，如下求条件数要计算逆阵的范数，很不方便，如下一些现象可作为判断病态矩阵的参考。一些现象可作为判断病态矩阵的参考。（1）在用主元消去法时消元过程出现小主元（如例）在用主元消去法时消元过程出现小主元（如例1212）（2）矩阵）矩阵）矩阵）矩阵A A中元素间数量级相差很大；中元素间数量级相差很大；中元素间数量级相差很大；中元素间数量级相差很大；（3）A的行列式的行列式det(A A)满足（行列式值相对很大）满足（行列式值相对很大）：（

25、4）矩阵的某些行（或列）近似相关（如例）矩阵的某些行（或列）近似相关（如例）矩阵的某些行（或列）近似相关（如例）矩阵的某些行（或列）近似相关（如例1111）。）。）。）。第三十五页，本课件共有75页利用条件数判断矩阵的性态举例A的条件数很大，所以方程组是病态的。的条件数很大，所以方程组是病态的。的特例，它是典型的的特例，它是典型的“病态病态”阵，阵，n越大，越大，“病态病态”越严越严重，重，如如n=6时，时，cond(A)=29106，对严重，对严重“病态病态”的方程组，的方程组，即即使用主元素法求解也难以保证数值稳定性。使用主元素法求解也难以保证数值稳定性。第三十六页，本课件共有75页3 雅

26、可比（Jacobi）迭代法 设有设有n阶线性方程组：阶线性方程组：简记为：简记为：其系数矩阵其系数矩阵A非奇异，不妨设非奇异，不妨设aii 0(1,2,n)可将上式可将上式可将上式可将上式改写为等价方程组：改写为等价方程组：第三十七页，本课件共有75页雅可比（Jacobi）迭代法（续）也可写作为：也可写作为：也可写作为：也可写作为：可简记为：可简记为：由此可建立迭代格式：由此可建立迭代格式：第三十八页，本课件共有75页Jacobi迭代法定义 选取初始向量选取初始向量选取初始向量选取初始向量x x(0)(0)代入（代入（代入（代入（4-44-4）右端，可得）右端，可得）右端，可得）右端，可得x

27、x(1)(1)=BxBx(0)(0)+g g，再将再将再将再将x x(1)(1)代入（代入（代入（代入（3-43-4）右端，可得）右端，可得）右端，可得）右端，可得x x(2)(2)=BxBx(1)(1)+g g，如此继续下去，如此继续下去，如此继续下去，如此继续下去，就产生一个向量序列就产生一个向量序列就产生一个向量序列就产生一个向量序列 x x(k k)，按（，按（，按（，按（3-23-2）或（）或（）或（）或（3-33-3）格式迭代求解）格式迭代求解）格式迭代求解）格式迭代求解的方法称为的方法称为的方法称为的方法称为雅可比（雅可比（JacobiJacobi）迭代法）迭代法）迭代法）迭代法

28、，又叫，又叫，又叫，又叫简单迭代法简单迭代法。迭代式（迭代式（迭代式（迭代式（3-43-4）中的）中的）中的）中的B B 称为迭代矩阵，它可直接由（称为迭代矩阵，它可直接由（称为迭代矩阵，它可直接由（称为迭代矩阵，它可直接由（3-23-2）或（或（或（或（3-33-3）得到，也可用系数矩阵）得到，也可用系数矩阵）得到，也可用系数矩阵）得到，也可用系数矩阵A A来表示：来表示：来表示：来表示：若将系数矩阵若将系数矩阵A分解为分解为A A=DLU，其中：其中：其中：其中：第三十九页，本课件共有75页Jacobi迭代法定义（续）式（式（3-5）为简单迭代法的矩阵形式）为简单迭代法的矩阵形式。第四十页

29、，本课件共有75页Jacobi迭代法举例用用用用JacobiJacobi迭代法求解线性方程组：迭代法求解线性方程组：迭代法求解线性方程组：迭代法求解线性方程组：例例1解解解解：由第一个方程解：由第一个方程解：由第一个方程解：由第一个方程解x x1 1，第二个方程解，第二个方程解，第二个方程解，第二个方程解x x2 2，第三，第三，第三，第三个方程解个方程解个方程解个方程解x x3 3得得得得JoacbiJoacbi迭代格式为：迭代格式为：迭代格式为：迭代格式为：继续迭代下去，迭代结果见表继续迭代下去，迭代结果见表3-1：取取x x(0)=(0,0,0)T T代入迭代式代入迭代式（3-63-6）

30、或（）或（3-7）得：）得：）得：）得：第四十一页，本课件共有75页Jacobi迭代法举例 0 00.00000.00000.00000.00000.00000.00001 17.20007.20008.30008.30008.40008.40002 29.71009.710010.700010.700011.500011.50003 310.570010.570011.570011.570012.482012.48204 410.853510.853511.853411.853412.828212.82825 510.951010.951011.951011.951012.941412.94

31、146 610.983410.983411.983411.983412.950412.95047 710.994410.994411.998111.998112.993412.99348 810.998110.998111.994111.994112.997812.99789 910.999410.999411.999411.999412.999212.9992表表表表3-13-1k x1(k)x2(k)x3(k)迭代迭代9次，得近似解次，得近似解x(9)=(10.9994,11.9994,12,9992)=(10.9994,11.9994,12,9992)T，此方，此方程组的准确解为程组的准

32、确解为x=(11,12,13)T，从表，从表3-13-1可以看出，随着迭可以看出，随着迭可以看出，随着迭可以看出，随着迭代次数的增加，迭代结果越来越接近精确解。代次数的增加，迭代结果越来越接近精确解。代次数的增加，迭代结果越来越接近精确解。代次数的增加，迭代结果越来越接近精确解。第四十二页，本课件共有75页 收敛条件收敛条件 迭代格式收敛的充要条件是G的谱半径1。对于Jacobi迭代，我们有一些保证收敛的充分条件定理：若A满足下列条件之一，则Jacobi迭代收敛。A为行对角占优阵 A为列对角占优阵第四十三页，本课件共有75页证明：证毕第四十四页，本课件共有75页例例例例4 讨论讨论Jacobi

33、迭代法的收敛性。迭代法的收敛性。迭代法的收敛性。迭代法的收敛性。解：首先要求出迭代矩阵，解：首先要求出迭代矩阵，对对对对Jacobi迭代法：迭代法：第四十五页，本课件共有75页第四十六页，本课件共有75页3 高斯塞德尔(Gauss-Seidel)迭代法 Jacobi迭代法的优点是公式简单，迭代矩阵容易得到，迭代法的优点是公式简单，迭代矩阵容易得到，它又称为同时替换法：在每一步迭代计算过程中，计算它又称为同时替换法：在每一步迭代计算过程中，计算它又称为同时替换法：在每一步迭代计算过程中，计算它又称为同时替换法：在每一步迭代计算过程中，计算x(k k+1)时是用时是用x(k)的全部分量代入求的全部

34、分量代入求x(k+1)的全部分量。因此的全部分量。因此的全部分量。因此的全部分量。因此需同时保留两个近似解向量需同时保留两个近似解向量x(k)和和x(k+1)。第四十七页，本课件共有75页第四十八页，本课件共有75页Gauss-Seidel迭代法求解 例例2 用用Gauss-Seidel迭代法求解例迭代法求解例1 解：解：解：解：Gauss-SeidelGauss-Seidel迭代格式为：迭代格式为：迭代格式为：迭代格式为：仍取仍取仍取仍取x x (0)(0)=(0,0,0)=(0,0,0)T T，计算结果见下表：计算结果见下表：计算结果见下表：计算结果见下表：0 00.00000.00000

35、.00000.00000.00000.00001 17.20007.20009.02009.020011.644011.64402 210.430810.430811.671911.671912.820512.82053 310.931310.931311.957211.957212.977812.97784 410.991310.991311.994711.994712.997212.99725 510.998910.998911.999311.999312.999612.99966 610.999910.999911.999911.999913.000013.0000k xk x1 1(k

36、 k)x x2 2(k k)x x3 3(k k)表表表表3-23-2 显然，用显然，用显然，用显然，用Gauss-SeidelGauss-Seidel迭代法比迭代法比迭代法比迭代法比JacobiJacobi迭代法收敛快，这个结论迭代法收敛快，这个结论迭代法收敛快，这个结论迭代法收敛快，这个结论在多数情况下是成立的，但也有在多数情况下是成立的，但也有在多数情况下是成立的，但也有在多数情况下是成立的，但也有Gauss-SeidelGauss-Seidel迭代比迭代比迭代比迭代比JacuobiJacuobi迭代收迭代收迭代收迭代收敛慢，甚至还有敛慢，甚至还有敛慢，甚至还有敛慢，甚至还有Jacobi

37、Jacobi迭代收敛，迭代收敛，迭代收敛，迭代收敛，Gauss-SeidelGauss-Seidel迭代发散的情形。迭代发散的情形。迭代发散的情形。迭代发散的情形。第四十九页，本课件共有75页求例2中的Gauss-Seidel法的迭代阵M的两种方法第五十页，本课件共有75页求例2中的Gauss-Seidel法的迭代阵M的两种方法续1方法方法2：可按代入法求可按代入法求M，以避免计算逆矩阵，在，以避免计算逆矩阵，在Gauss-SeidelSeidel迭代式（迭代式（3-103-10）中，第）中，第 二个式子中的以第一个式子二个式子中的以第一个式子代替。可将第二式右端上标都化为代替。可将第二式右端

38、上标都化为k（可以不管常数）：（可以不管常数）：第五十一页，本课件共有75页求例2中的Gauss-Seidel法的迭代阵M的两种方法续2由于（由于（3-10）第一式及（）第一式及（3-11），），），），（3-12）的右端上标均为）的右端上标均为k，即，即为同时替换迭代式，类似于为同时替换迭代式，类似于JacobiJacobi迭代法可直接由它们得迭代法可直接由它们得迭代阵为：迭代阵为：第五十二页，本课件共有75页 收敛条件收敛条件 迭代格式收敛的充要条件是G的谱半径1。我们看一些充分条件定理：若A满足下列条件之一，则Gauss-Seidel 迭代收敛。A为行或列对角占优阵 A对称正定阵第五十三

39、页，本课件共有75页证明：设G的特征多项式为，则为对角占优阵，则时为对角占优阵即即证毕注：注：二种方法都存在收敛性问题。有例子表明：Gauss-Seidel法收敛时，Jacobi法可能不收敛；而Jacobi法收敛时，Gauss-Seidel法也可能不收敛。第五十四页，本课件共有75页两种迭代法举例例例4 讨论讨论Jacobi迭代法与迭代法与Gauss-Seidel迭代法的收敛性。迭代法的收敛性。解：首先要求出迭代矩阵，然后利用推论解：首先要求出迭代矩阵，然后利用推论1（充分条件）（充分条件）（充分条件）（充分条件）及定理及定理及定理及定理4（充分必要条件）进行讨论。（充分必要条件）进行讨论。（

40、充分必要条件）进行讨论。（充分必要条件）进行讨论。对对Jacobi迭代法：迭代法：迭代法：迭代法：第五十五页，本课件共有75页例4（Jacobi迭代法续）第五十六页，本课件共有75页例4（G-S迭代法续）对对对对G-S迭代法：迭代法：第五十七页，本课件共有75页两种迭代法说明注注1：对：对：对：对G-S法，为避免求逆阵可按下面两个方法：法，为避免求逆阵可按下面两个方法：第五十八页，本课件共有75页两种迭代法说明（续）第五十九页，本课件共有75页4 松驰法 通过引入参数，在通过引入参数，在Gauss-Seidel法的基础上作适当修改，法的基础上作适当修改，在不增加过多的计算量的条件下，可得到一种

41、新的，收敛在不增加过多的计算量的条件下，可得到一种新的，收敛在不增加过多的计算量的条件下，可得到一种新的，收敛在不增加过多的计算量的条件下，可得到一种新的，收敛更快的迭代法。更快的迭代法。将将Gauss-Seidel迭代格式（迭代格式（3-93-9）改写为：）改写为：第六十页，本课件共有75页松驰法（续）通过选择适当的参数通过选择适当的参数 使此迭代格式收敛更快。使此迭代格式收敛更快。称为称为松驰因子松驰因子，1时称时称为为超松驰法超松驰法，=1是是Gauss-Seidel迭代迭代，简称为，简称为SOR法法（Successive Over-Relaxation）。）。第六十一页，本课件共有75

42、页将（将（3-13）代入（）代入（3-14）可得：）可得：）可得：）可得：其矩阵其矩阵其矩阵其矩阵形式为：形式为：所以所以所以所以SORSOR法的迭代矩阵为：法的迭代矩阵为：第六十二页，本课件共有75页用SOR法解线性方程组（例3）例例3 取取取取 =1.4,x(0)=(1,1,1)=(1,1,1)T，用用SOR法解线性方程组法解线性方程组 第六十三页，本课件共有75页例 3（续1）继续下去，计算结果如下：继续下去，计算结果如下：0 01.00001.00001.00001.00001.00001.00001 11.00001.00001.00001.00001.56001.56002 21.

43、00001.00001.39201.39201.61841.61843 31.27441.27441.46821.46821.64061.64064 41.21801.21801.41361.41361.59341.59345 51.20231.20231.39161.39161.60681.60686 61.19321.19321.40341.40341.60071.60077 71.20511.20511.40271.40271.60161.60168 81.19991.19991.40001.40001.59941.59949 91.20001.20001.39961.39961.600

44、11.6001表表表表3-33-3k k x x1 1(k k)x x2 2(k k)x x3 3(k k)第六十四页，本课件共有75页例 3（续2）所以，方程组近似解为所以，方程组近似解为:松驰因子松驰因子 的选取对收敛速度影响极大，如何选取的选取对收敛速度影响极大，如何选取 使收使收敛速度加快，或达到最快？这是非常重要的，但又很困难，敛速度加快，或达到最快？这是非常重要的，但又很困难，目前尚无可供实用的计算最佳松驰因子的办法，通常的作法目前尚无可供实用的计算最佳松驰因子的办法，通常的作法是采用试算法：即从同一初值出发，选不同的松驰因子进行是采用试算法：即从同一初值出发，选不同的松驰因子进行

45、试算，迭代相同的次数，来比较残量试算，迭代相同的次数，来比较残量r(k)(k)=b b Ax(k)的大小，的大小，的大小，的大小，选取使选取使选取使选取使r(k k)最小（各分量总体相差最小）的松驰因子。这样最小（各分量总体相差最小）的松驰因子。这样做较简单，但比较有效。做较简单，但比较有效。小小结结如如下下：第六十五页，本课件共有75页迭代法的收敛条件（续2）定理定理定理定理4表明，迭代法收敛与否只决定于迭代矩阵表明，迭代法收敛与否只决定于迭代矩阵表明，迭代法收敛与否只决定于迭代矩阵表明，迭代法收敛与否只决定于迭代矩阵的谱半径，与初始向量及方程组的右端项无关。的谱半径，与初始向量及方程组的右

46、端项无关。的谱半径，与初始向量及方程组的右端项无关。的谱半径，与初始向量及方程组的右端项无关。对同一方程组，由于不同的迭代法其迭代矩阵不同，对同一方程组，由于不同的迭代法其迭代矩阵不同，因此可能出现有的方法收敛，有的方法发散的情形。因此可能出现有的方法收敛，有的方法发散的情形。推论推论推论推论2 2第六十六页，本课件共有75页 定理定理4 4虽然给出了判别迭代法收敛的充要条件，但实际虽然给出了判别迭代法收敛的充要条件，但实际虽然给出了判别迭代法收敛的充要条件，但实际虽然给出了判别迭代法收敛的充要条件，但实际使用时很不方便，因为求逆矩阵和特征值的难度并不亚于使用时很不方便，因为求逆矩阵和特征值的

47、难度并不亚于用直接法求解线性方程组。而推论用直接法求解线性方程组。而推论用直接法求解线性方程组。而推论用直接法求解线性方程组。而推论1仅为充分条件。很多仅为充分条件。很多仅为充分条件。很多仅为充分条件。很多情况下如例情况下如例3，由推论，由推论1 1无法判别收敛性。下面对一些特殊无法判别收敛性。下面对一些特殊的方程组，从方程组本身出发给出几个常用的判别条件，的方程组，从方程组本身出发给出几个常用的判别条件，而不必求迭代阵的特征值或范数。而不必求迭代阵的特征值或范数。直接用矩阵A判定敛散性且至少有一个且至少有一个 i 值，使上式中不等号严格成立，则值，使上式中不等号严格成立，则称称A为为弱对角占

48、优阵弱对角占优阵。若对所有。若对所有 i，上式中不等号均，上式中不等号均严格成立，则称严格成立，则称A为为严格对角占优阵严格对角占优阵。定义定义4第六十七页，本课件共有75页直接用矩阵A判定敛散性（续）为严格对角占优阵，为严格对角占优阵，Jacobi迭代法与迭代法与迭代法与迭代法与G-S迭代法均收敛。迭代法均收敛。又如例又如例3中，系数矩阵：中，系数矩阵：为非严格对角占优，但为非严格对角占优，但A为对称正定矩阵，且为对称正定矩阵，且 =1.4 松驰法收敛。松驰法收敛。如例如例1中，线性方程组的系数矩阵：中，线性方程组的系数矩阵：设有线性方程组设有线性方程组AxAx=b，下列结论成立：，下列结论

49、成立：1.若若若若A A为严格对角占优阵，则为严格对角占优阵，则为严格对角占优阵，则为严格对角占优阵，则Jacobi迭代法与迭代法与G-S法均收敛；法均收敛；2.若若A为严格对角占优阵，为严格对角占优阵，0 1，则松驰法收敛；，则松驰法收敛；3.若若若若A为对称正定矩阵，为对称正定矩阵，0 2 2，则松驰法收敛；，则松驰法收敛；若若A为对称正定阵，松驰法收敛为对称正定阵，松驰法收敛 0 2。第六十八页，本课件共有75页三种迭代法判定敛散性举例解：可以总结，讨论迭代法的收敛性，应首先从解：可以总结，讨论迭代法的收敛性，应首先从A出发讨出发讨论其是否具有主对角占优或对称正定性；其次对迭代法的论其是

50、否具有主对角占优或对称正定性；其次对迭代法的迭代阵讨论其是否有范数小于迭代阵讨论其是否有范数小于迭代阵讨论其是否有范数小于迭代阵讨论其是否有范数小于1；最后利用迭代阵的谱；最后利用迭代阵的谱；最后利用迭代阵的谱；最后利用迭代阵的谱半径讨论（这是充分必要条件）。半径讨论（这是充分必要条件）。半径讨论（这是充分必要条件）。半径讨论（这是充分必要条件）。例例5 5第六十九页，本课件共有75页例 5(续）对对Jacobi迭代法，其迭代阵容易由迭代法，其迭代阵容易由迭代法，其迭代阵容易由迭代法，其迭代阵容易由A直接得到：直接得到：第七十页，本课件共有75页两点注释 注注1：值得注意的是，改变方程组中方程