线性方程组迭代解法市公开课获奖课件

1、第四章线性方程组迭代解法第1页第1页第四章目录1 向量序列与矩阵序列极限2 Jacobi迭代法3 GaussSeidel迭代法4 松驰法5 迭代法收敛条件及误差预计 5.1 矩阵谱半径 5.2 迭代法收敛条件 5.3 误差预计第2页第2页第四章 方程组迭代解法概述 这一章讨论线性方程组另一类解法迭代法，由于迭代法能充足避免系数矩阵中零元存贮与计算，因此尤其适合用于求解系数矩阵阶数很高而零元素又诸多（即大型稀疏）线性方程组。 解线性方程组迭代法基本思想与解方程迭代法相似，首先将方程组Ax = b化为等价方程组x = Mx + g，其中M为n阶方阵，b = (b1,b2,bn)T，g Rn，任取初

2、始向量x(0) Rn，代入迭代公式：产生向量序列x(k)，若此序列收敛于x*，则有x* = Mx*+g，即x*为原方程组解。因此，可依据精度要求选择一个适当x(k)（k充足大时）作为近似解，这就是解线性方程组迭代法，上式称为迭代格式，M称为迭代矩阵，若序列x(k)极限存在，称此迭代过程收敛，不然称为发散。 第3页第3页1 向量与矩阵范数 与求解方程类似，需要讨论问题是：如何建立迭代公式，向量序列收敛条件是什么，若向量序列x(k)收敛，如何进行误差预计？ 第4页第4页4.1 向量与矩阵范数 这三个性质刻画了向量长度基本特性，并能够用其将平面向量长度概念推广到普通n维向量，于是有下列定义： 定义1

3、下屏将给出范数种类：第5页第5页惯用向量范数 容易证实它们都满足上述三条性质。能够看出，2范数是平面向量长度计算公式在形式上推广，也是线性代数中内积定义。此处引入各种范数来刻画向量大小，是为了在不同情况下用不同范数研究问题。向量范数证实：（只对第三条） 对范数：前面2条显然，对第三条，由于对任意实数x, y，绝对值不等式：|x+y|x|+|y| 成立，因而有:分别称为向量x2范数，1范数，无穷范数。第6页第6页对2范数利用实数柯西不等式： 于是，有：惯用向量范数（续）第7页第7页Rn中范数等价性 比如可证实下列等价性： 因此，2范数与范数是等价。不难证实：亦即1范数与范数是等价 。事实上: R

4、n 中任意两种范数都是等价。 第8页第8页矩阵范数 定义2对任意n阶方阵A = (aij)nn，若相应一个非负实数|A|，满足： 则称|A|为矩阵A范数。 与向量范数定义比较，前三条性质只是向量范数定义推广，而第四条性质则是矩阵乘法性质要求，它使矩阵范数在数值计算中使用更以便。 第9页第9页惯用矩阵范数惯用矩阵范数有： 它们分别叫做矩阵范数，1范数，2范数，F范数，矩阵F范数是向量2范数推广，矩阵范数，1范数计算容易，而矩阵2范数与ATA特性值相关，因此又称为谱范数，它计算较困难，但由于它有一些好性质，所以也是惯用范数。 第10页第10页惯用矩阵范数（续）能够证实，这些范数都满足定义2。以|A

5、|为例，前2条性质显然成立，而对：第11页第11页最大行和矩阵范数证实第12页第12页最大行和矩阵范数证实第13页第13页范数相容性 在误差预计中，由于矩阵与向量会同时用到，我们总希望有上面不等式成立， 但对任意向量范数与矩阵范数却未必如此，因而尤其地把满足此不等式范数称为相容，能够证实，上述惯用范数是相容，即有： 在使用范数时，应选取相容矩阵范数与向量范数。 分别称为 关于P范数绝对误差与相对误差。 有了矩阵范数，就能够用它描述矩阵误差，设 是A近似矩阵， 称为 残差阵，则：第14页第14页求范数举例例10第15页第15页 向量序列与矩阵序列极限 与求解方程类似，需要讨论问题是：如何建立迭代

6、公式，向量序列收敛条件是什么，若向量序列x(k)收敛，如何进行误差预计？ 1 向量序列与矩阵序列极限 由于Rn中向量可与Rn点建立一一相应关系，因此由点列收敛概念及向量范数等价性，可得到向量序列收敛概念。定义3第16页第16页 向量序列与矩阵序列极限（续） n维点列收敛一个等价描述是其相应坐标序列均收敛，向量序列也有类似结论。 定理1 第17页第17页矩阵序列收敛概念及定理定义3完全类似地，能够定义矩阵序列收敛：与向量序列类似，也有：定理2 第18页第18页4.3 矩阵谱半径 迭代法收敛性与迭代矩阵特性值相关：设A为n阶方阵，i (i = 1,2,，n)为A特性值，称特性值模最大值为矩阵A谱半

7、径，记为：定义5第19页第19页矩阵谱半径（续） 矩阵谱半径与范数之间有下列关系： 设x为相应于特性值A特性向量，则由： 这个不等式对A任何范数、任意特性值都成立，因此，可得矩阵A谱半径与A范数之间一个主要关系：A谱半径不超出A任一个范数。即： 第20页第20页公式 主要性阐明 它之因此主要是由于：(A)难计算，而|A|、 |A|1计算容易，并且对于任意正数，存在一个矩阵范数很靠近(A)，使得成立： 对任意n阶方阵A，普通不存在矩阵范数使(A) =|A|，但若A为对称矩阵，则有： 下面结论对建立迭代法收敛条件十分主要 ：定理3第21页第21页定理3（续）证实：第22页第22页由5.1 结果，能

8、够得到下列收敛定理 ：定理4对任意初始向量x(0)和右端项g，由迭代格式：证实：第23页第23页推论1第24页第24页 能够看出，后两个方程组与第一个方程组相比，系数矩阵或右端向量仅有0.0005下列误差，但准确解却相差很大。 4.2 方程组误差分析 数值稳定算法是否一定能求得精度比较高解呢？回答是不一定，解精度还与方程组本身性态相关，下面来考察几种例： 例11第25页第25页例12若其系数，常数项改用三位有效数字小数表示，则方程组为 ：第26页第26页右端项b产生0.1%改变引起解改变最大改变184%。初始数据误差（相对）0.3% = 0.003，而解相对误差却超出50%。 例13第27页第

9、27页方程组性态讨论 病态、良态 在许多实际问题中，线性方程组系数矩阵和右端项元素大多为前面计算结果，因此上述例中微小误差是避免不了。而对上述例中方程组，无论用多么稳定算法求解，计算中产生微小误差就使解面目全非，因此这些方程组性态是很差。 当方程组Ax = b系数矩阵与右端向量b微小变动（小扰动）而引起解严重失真时，称此方程组为病态方程组，其系数矩阵A称为病态矩阵，不然称为良态方程组，A称为良态矩阵，为了定量刻画方程组“病态”程度，下面对方程组Ax = b在系数矩阵A及右端项b有扰动几种情形进行讨论。第28页第28页 此不等式表明，当右端项有扰动时，解相对误差不超出b相对误差 倍。 首先考察右

10、端项b扰动对解影响，设b有扰动b，A为准确,记引起解x扰动为x, 即：第29页第29页方程组性态讨论（续2） 当b为准确而A有微小扰动A时，在A充足小时也同样可推得： 紧接下屏讨论：第30页第30页第31页第31页方程组性态讨论续（3） 而当A,b同时有微小扰动A，b时，则可进一步导出更普通误差预计式：注意到：第32页第32页在b充足小时，此式右端事实上即为：方程组性态讨论续（4）第33页第33页矩阵条件数 在三种情况下得到这三个不等式反应理解相对误差与A及b相对误差关系；数|A|A-1|越小，解相对误差也越小；反之数|A|A-1|越大，解相对误差也越大，事实上这个数反应理解对方程组原始数据敏

11、感程度，揭示了矩阵A和方程组本身性态，称之为方程组或矩阵A条件数，记作： cond(A)越大，A病态程度越严重。至于cond(A)多大才算病态，这是一个相对概念，没有一个严格数量界线。 第34页第34页判断病态矩阵几点参考 求条件数要计算逆阵范数，很不以便，下列一些现象可作为判断病态矩阵参考。（1）在用主元消去法时消元过程出现小主元（如例12）（2）矩阵A中元素间数量级相差很大；（3）A行列式det(A)满足（行列式值相对很大） ：（4）矩阵一些行（或列）近似相关（如例11）。 第35页第35页利用条件数判断矩阵性态举例A条件数很大，因此方程组是病态。特例，它是典型“病态”阵，n越大，“病态”

12、越严重，如n=6时，cond(A)=29106，对严重“病态”方程组，即使用主元素法求解也难以确保数值稳定性。 第36页第36页3 雅可比（Jacobi）迭代法 设有n阶线性方程组：简记为：其系数矩阵A非奇异，不妨设aii 0 (1,2,n)可将上式改写为等价方程组：第37页第37页雅可比（Jacobi）迭代法（续）也可写作为：可简记为：由此可建立迭代格式：第38页第38页Jacobi迭代法定义 选取初始向量x(0)代入（4-4）右端，可得x(1) = Bx(0) + g，再将x (1)代入（3-4）右端，可得x(2) = Bx(1) + g，如此继续下去，就产生一个向量序列x(k)，按（3-

13、2）或（3-3）格式迭代求解办法称为雅可比（Jacobi）迭代法，又叫简朴迭代法。 迭代式（3-4）中B 称为迭代矩阵，它可直接由（3-2）或（3-3）得到，也可用系数矩阵A来表示：若将系数矩阵A分解为A = DLU，其中： 第39页第39页Jacobi迭代法定义（续）式（3-5）为简朴迭代法矩阵形式。第40页第40页Jacobi迭代法举例用Jacobi迭代法求解线性方程组： 例1解：由第一个方程解x1，第二个方程解x2，第三个方程解x3得Joacbi迭代格式为： 继续迭代下去，迭代结果见表3-1：取x(0) = (0,0,0)T代入迭代式（3-6）或（3-7）得：第41页第41页Jacobi

14、迭代法举例 00.00000.00000.000017.8.30008.400029.710010.700011.5000310.570011.570012.4820410.853511.853412.8282510.951011.951012.9414610.983411.983412.9504710.994411.998112.9934810.998111.994112.9978910.999411.999412.9992表3-1k x1(k) x2(k) x3(k) 迭代9次，得近似解x(9) = (10.9994,11.9994,12,9992)T，此方程组准确解为x =(11,12,

15、13)T，从表3-1能够看出，伴随迭代次数增长，迭代结果越来越靠近准确解。 第42页第42页 收敛条件 迭代格式收敛充要条件是G谱半径1。对于Jacobi迭代，我们有一些确保收敛充足条件定理：若A满足下列条件之一，则Jacobi迭代收敛。 A为行对角占优阵 A为列对角占优阵第43页第43页证实：证毕第44页第44页例4 讨论Jacobi迭代法收敛性。 解：首先要求出迭代矩阵，对Jacobi迭代法：第45页第45页第46页第46页3 高斯塞德尔(Gauss-Seidel)迭代法 Jacobi迭代法长处是公式简朴，迭代矩阵容易得到，它又称为同时替换法：在每一步迭代计算过程中，计算x(k+1)时是用

16、x(k)所有分量代入求x (k+1)所有分量。因此需同时保留两个近似解向量x(k)和x(k+1)。 第47页第47页第48页第48页Gauss-Seidel迭代法求解 例2 用Gauss-Seidel迭代法求解例1 解：Gauss-Seidel迭代格式为：仍取x (0) = (0,0,0)T，计算结果见下表： 00.00000.00000.000017.9.020011.6440210.430811.671912.8205310.931311.957212.9778410.991311.994712.9972510.998911.999312.9996610.999911.999913.000

17、0k x1(k) x2(k) x3(k) 表3-2 显然，用Gauss-Seidel迭代法比Jacobi迭代法收敛快，这个结论在多数情况下是成立，但也有Gauss-Seidel迭代比Jacuobi迭代收敛慢，甚至尚有Jacobi迭代收敛，Gauss-Seidel迭代发散情形。 第49页第49页求例2中Gauss-Seidel法迭代阵M两种办法第50页第50页求例2中Gauss-Seidel法迭代阵M两种办法续1办法2：可按代入法求M，以避免计算逆矩阵，在Gauss-Seidel迭代式（3-10）中，第 二个式子中以第一个式子代替。可将第二式右端上标都化为k（能够无论常数）：第51页第51页求例

18、2中Gauss-Seidel法迭代阵M两种办法续2由于（3-10）第一式及（3-11），（3-12）右端上标均为k ，即为同时替换迭代式，类似于Jacobi迭代法可直接由它们得迭代阵为： 第52页第52页 收敛条件 迭代格式收敛充要条件是G谱半径1。我们看一些充足条件定理：若A满足下列条件之一，则Gauss-Seidel 迭代收敛。 A为行或列对角占优阵 A对称正定阵第53页第53页证实：设G特性多项式为，则为对角占优阵，则时为对角占优阵即即证毕注：二种办法都存在收敛性问题。 有例子表明：Gauss-Seidel法收敛时，Jacobi法也许不收敛；而Jacobi法收敛时， Gauss-Seid

19、el法也也许不收敛。第54页第54页两种迭代法举例例4 讨论Jacobi迭代法与Gauss-Seidel迭代法收敛性。 解：首先要求出迭代矩阵，然后利用推论1（充足条件）及定理4（充足必要条件）进行讨论。 对Jacobi迭代法：第55页第55页例4（ Jacobi迭代法续）第56页第56页例4（ G-S迭代法续）对G-S迭代法： 第57页第57页两种迭代法阐明注1：对G-S法，为避免求逆阵可按下面两个办法：第58页第58页两种迭代法阐明（续）第59页第59页4 松驰法 通过引入参数，在Gauss-Seidel法基础上作适当修改，在不增长过多计算量条件下，可得到一个新，收敛更快迭代法。 将Gau

20、ss-Seidel迭代格式（3-9）改写为： 第60页第60页松驰法（续） 通过选择适当参数使此迭代格式收敛更快。称为松驰因子，1时称为超松驰法， = 1是Gauss-Seidel迭代，简称为SOR法（Successive Over-Relaxation）。 第61页第61页将（3-13）代入（3-14）可得： 其矩阵形式为： 因此SOR法迭代矩阵为：第62页第62页用SOR法解线性方程组（例3） 例3 取 =1.4,x (0) = (1,1,1)T，用SOR法解线性方程组 第63页第63页例 3 （续1）继续下去，计算结果下列：01.00001.00001.000011.00001.0000

21、1.560021.00001.39201.618431.27441.46821.640641.21801.41361.593451.20231.39161.606861.19321.40341.600771.20511.40271.601681.19991.40001.599491.1.39961.6001表3-3k x1(k) x2(k) x3(k) 第64页第64页例 3 （续2）因此，方程组近似解为: 松驰因子选取对收敛速度影响极大，怎样选取使收敛速度加紧，或达到最快？这是非常主要，但又很困难，当前尚无可供实用计算最正确松驰因子方法，通常作法是采取试算法：即从同一初值出发，选不同松驰因子

22、进行试算，迭代相同次数，来比较残量r (k) = b Ax(k) 大小，选取使r(k) 最小（各分量总体相差最小）松驰因子。这么做较简朴，但比较有效。 小结下列：第65页第65页迭代法收敛条件（续2） 定理4表明，迭代法收敛是否只决定于迭代矩阵谱半径，与初始向量及方程组右端项无关。 对同一方程组，因为不同迭代法其迭代矩阵不同，因此可能出现有方法收敛，有方法发散情形。推论2第66页第66页 定理4即使给出了判别迭代法收敛充要条件，但实际使用时很不以便，由于求逆矩阵和特性值难度并不亚于用直接法求解线性方程组。而推论1仅为充足条件。诸多情况下如例3，由推论1无法判别收敛性。下面对一些特殊方程组，从方程组本身出发给出几种惯用判别条件，而不必求迭代阵特性值或范数。 直接用矩阵A鉴定敛散性且至少有一个 i 值，使上式中不等号严格成立，则称A为弱对角占优阵。若对所有 i，上式中不等号均严格成立，则称A为严格对角占优阵。 定义4第67页第67页直接用矩阵A鉴定敛散性（续