资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考!,第四章,线性方程组,迭代解法,1/65,第四章目录,1,向量序列与矩阵序列极限,2,Jacobi,迭代法,3,GaussSeidel,迭代法,4,松驰法,5,迭代法收敛条件及误差预计,5.1 矩阵谱半径,5.2 迭代法收敛条件,5.3 误差预计,6,非线性方程组迭代法,6.1,Newton,法,6.2 最速下降法,2/65,第四章 方程组迭代解法概述,这一章讨论线性方程组另一类解法,迭代法,，因为迭代法能充分防止系数矩阵中零元存贮与计算，所以尤其适合用于求解系数矩阵阶数很高而零元素又很多（,即大型稀疏,）线性方程组。,解线性方程组,迭代法基本思想,与解方程迭代法相同，首先将方程组,Ax,=,b,化为,等价,方程组,x,=,Mx,+,g,，,其中,M,为,n,阶方阵，,b,=(,b,1,b,2,b,n,),T,，,g,R,n,，,任取初始向量,x,(0),R,n,，,代入迭代公式：,3/65,迭代解法概述(续）,产生向量序列,x,(,k,),，,若此序列,收敛于,x,*,，,则有,x,*=,Mx,*,+g,，,即,x,*,为原方程组解。所以，可依据精度要求选择一个适当,x,(,k,),（,k,充分大时）作为,近似解,，这就是解线性方程组,迭代法,，上式称为,迭代格式,，,M,称为,迭代矩阵,，若序列,x,(,k,),极限存在，称此迭代过程,收敛,，不然称为,发散,。,4/65,1 向量序列与矩阵序列极限,与求解方程类似，需要讨论,问题是,：怎样建,立迭代公式，向量序列收敛条件是什么，若向量,序列,x,(k),收敛，怎样进行误差预计？,1 向量序列与矩阵序列极限,因为,R,n,中向量可与,R,n,点建立一一对应关系，,所以由点列收敛概念及向量范数等价性，可得,到,向量序列收敛概念,。,定义1,5/65,向量序列与矩阵序列极限（续）,n,维点列收敛一个等价描述是其对应坐标序列均,收敛，向量序列也有类似结论。,定理1,6/65,矩阵序列收敛概念及定理,定义2,完全类似地，能够定义矩阵序列收敛：,与向量序列类似，也有：,定理2,7/65,2 雅可比（,Jacobi,）,迭代法,设有,n,阶线性方程组：,简记为：,其系数矩阵,A,非奇异，不妨设,a,ii,0(1,2,n,),可将上式,改写为等价方程组：,8/65,雅可比（,Jacobi,）,迭代法（续）,也可写作为：,可简记为：,由此可建立迭代格式：,9/65,Jacobi,迭代法定义,选取初始向量,x,(0),代入,（4-4）,右端，可得,x,(1),=,Bx,(0),+,g,，,再将,x,(1),代入,（4-4）,右端，可得,x,(2),=,Bx,(1),+,g,，,如此继续下去，,就产生一个向量序列,x,(,k,),，,按,（4-2）,或,（4-3）,格式迭代求解,方法称为,雅可比（,Jacobi,）,迭代法,，,又叫,简单迭代法,。,迭代式（3-4）中,B,称为迭代矩阵，它可直接由,（4-2）,或,（4-3）,得到，也可用系数矩阵,A,来表示：,若将系数矩阵,A,分解为,A,=,D,L,U，,其中：,10/65,Jacobi,迭代法定义（续）,式（4-5）为简单迭代法矩阵形式,。,11/65,Jacobi,迭代法举例,用,Jacobi,迭代法求解线性方程组：,例1,解,：由第一个方程解,x,1,，,第二个方程解,x,2,，,第三,个方程解,x,3,得,Joacbi,迭代格式为：,继续迭代下去，迭代结果见表,4-1：,取,x,(0),=(0,0,0),T,代入迭代式,（4-6）,或,（4-7）,得：,12/65,Jacobi,迭代法举例,0,0.0000,0.0000,0.0000,1,7.,8.3000,8.4000,2,9.7100,10.7000,11.5000,3,10.5700,11.5700,12.4820,4,10.8535,11.8534,12.8282,5,10.9510,11.9510,12.9414,6,10.9834,11.9834,12.9504,7,10.9944,11.9981,12.9934,8,10.9981,11.9941,12.9978,9,10.9994,11.9994,12.9992,表4-1,k,x,1,(,k,),x,2,(,k,),x,3,(,k,),迭代,9次,，得近似解,x,(9),=(10.9994,11.9994,12,9992),T,，,此方程组准确解为,x,=(11,12,13),T,，,从,表4-1,能够看出，伴随迭代次数增加，迭代结果越来越靠近准确解。,13/65,3 高斯塞德尔(,Gauss-Seidel,),迭代法,Jacobi,迭代法优点是公式简单，迭代矩阵轻易得到，,它又称为同时替换法：在每一步迭代计算过程中，计算,x,(,k,+1),时是用,x,(,k,),全部分量代入求,x,(k+1),全部分量。所以,需同时保留两个近似解向量,x,(,k,),和,x,(,k,+1),。,14/65,高斯塞德尔(,Gauss-Seidel,),迭代法续1,15/65,Gauss-Seidel,迭代法求解,例2,用,Gauss-Seidel,迭代法求解例1,解：,Gauss-Seidel,迭代格式为：,仍取,x,(0),=(0,0,0),T,，,计算结果见下表：,0,0.0000,0.0000,0.0000,1,7.,9.0200,11.6440,2,10.4308,11.6719,12.8205,3,10.9313,11.9572,12.9778,4,10.9913,11.9947,12.9972,5,10.9989,11.9993,12.9996,6,10.9999,11.9999,13.0000,k x,1,(,k,),x,2,(,k,),x,3,(,k,),表4-2,显然，用,Gauss-Seidel,迭代法比,J,acobi,迭代法收敛快，这个结论,在多数情况下是成立，但也有,Gauss-Seidel,迭代比,Jacuobi,迭代收,敛慢，甚至还有,J,acobi,迭代收敛，,Gauss-Seidel,迭代发散情形。,16/65,求例2中,Gauss-Seidel,法迭代阵,M,两种方法,17/65,求例2中,Gauss-Seidel,法迭代阵,M,两种方法续1,方法2,：,可按代入法求,M,，,以防止计算逆矩阵，在,Gauss-,Seidel,迭代式,（4-10）,中，第 二个式子中以第一个式子,代替。可将第二式右端上标都化为,k,（,能够不论常数）,：,18/65,求例2中,Gauss-Seidel,法迭代阵,M,两种方法续2,因为,（4-10）,第一式及,（4-11）,，,（,4-12）,右端上标均为,k,，,即,为同时替换迭代式，类似于,Jacobi,迭代法可直接由它们得,迭代阵为：,19/65,4 松驰法,经过引入参数，在,Gauss-Seidel,法基础上作适当修改，,在不增加过多计算量条件下，可得到一个新，收敛,更加快迭代法。,将,Gauss-Seidel,迭代格式,（4-9）,改写为,：,20/65,松驰法（续）,经过选择适当参数,使此迭代格式收敛更加快。,称为,松驰因子,，,1时称,为,超松驰法,，,=1是,Gauss-Seidel,迭代,，,简称为,SOR,法,（,S,uccessive,O,ver-,R,elaxation,）。,21/65,SOR,法迭代矩阵,将,（4-13）,代入,（4-14）,可得：,其矩阵,形式为：,所以,SOR,法迭代矩阵为：,22/65,用,SOR,法解线性方程组（例3）,例3,取,=1.4,x,(0),=(1,1,1),T,，,用,SOR,法解线性方程组,23/65,例 3（续1）,继续下去，计算结果以下：,0,1.0000,1.0000,1.0000,1,1.0000,1.0000,1.5600,2,1.0000,1.3920,1.6184,3,1.2744,1.4682,1.6406,4,1.2180,1.4136,1.5934,5,1.2023,1.3916,1.6068,6,1.1932,1.4034,1.6007,7,1.2051,1.4027,1.6016,8,1.1999,1.4000,1.5994,9,1.,1.3996,1.6001,表4-3,k,x,1,(,k,),x,2,(,k,),x,3,(,k,),24/65,例 3（续2）,所以，方程组近似解为:,松驰因子,选取对收敛速度影响极大，怎样选取,使收敛速度加紧，或到达最快？这是非常主要，但又,很困难,，当前尚无可供实用计算最正确松驰因子方法，通常作法是采取,试算法：,即从同一初值出发，选不一样松驰因子进行试算，迭代相同次数，来比较残量,r,(k),=,b,Ax,(,k,),大小，选取使,r,(,k,),最小（各分量总体相差最小）松驰因子。这么做较简单，但比较有效。,小结以下：,25/65,5 迭代法收敛条件及误差预计,5.1 矩阵谱半径,迭代法收敛性与迭代矩阵特征值相关：,设,A,为,n,阶方阵，,i,(,i,=1,2,，,n,),为,A,特征值，,称特征值模最大值为矩阵,A,谱半径，记为：,定义3,26/65,矩阵谱半径（续）,矩阵谱半径与范数之间有以下关系：,设,x,为对应于特征值,A,特征向量，则由：,这个不等式对,A,任何范数、任意特征值都成立，,所以，可得矩阵,A,谱半径与,A,范数之间一个主要,关系：,A,谱半径不超出,A,任一个范数,。即：,27/65,公式 主要性说明,它之所以主要是因为：,(,A,),难计算，而,|,A,|,、|,A,|,1,计算轻易，而且对于任意正数,，存在一个矩阵范数,很靠近,(,A,),，,使得成立：,对任意,n,阶方阵,A,，,普通不存在矩阵范数使,(,A,)=|,A|,，,但若,A,为对称矩阵,，则有：,下面结论对建立迭代法收敛条件十分主要：,定理3,28/65,定理3（续）,证实：,29/65,5.2 迭代法收敛条件,证实：,定理4,由,5.1,结果，能够得到以下收敛定理：,对任意初始向量,x,(0),和右端项,g,，,由迭代格式：,30/65,迭代法收敛条件（续1）,推论1,31/65,迭代法收敛条件（续2）,推论2,定理4,表明，迭代法收敛是否只决定于迭代矩阵谱半径，与初始向量及方程组右端项无关。,对同一方程组，因为不一样迭代法其迭代矩阵不一样，所以可能出现有方法收敛，有方法发散情形。,32/65,两种迭代法举例,例4,讨论,Jacobi,迭代法与,Gauss-Seidel,迭代法收敛性。,解：,首先要求出迭代矩阵，然后利用,推论1,（充分条件）及,定理4,（充分必要条件）进行讨论。,对,Jacobi,迭代法：,33/65,例4（,Jacobi,迭代法续）,34/65,例4（,G-S,迭代法续）,对,G-S,迭代法：,35/65,两种迭代法说明,注1,：,对,G-S,法,，为防止,求逆阵,可按下面两个方法：,36/65,两种迭代法说明（续）,注2,：,例4,也说明,0,2,确实只是松驰法,必要条件,，,而,非充分条件,，因为,G-S,法,即为,=,1,情形。,37/65,定理4即使给出了判别迭代法收敛充要条件，但实际,使用时很不方便，因为求逆矩阵和特征值难度并不亚于,用直接法求解线性方程组。而推论1仅为充分条件。很多,情况下如例3，由推论1无法判别收敛性。下面对一些特殊,方程组，从方程组本身出发给出几个惯用判别条件，,而无须求迭代阵特征值或范数。,直接用矩阵,A,判定敛散性,且最少有一个,i,值，使上式中不等号严格成立，则称,A,为,弱对角占优阵,。若对全部,i,，,上式中不等号均严格成立，则称,A,为,严格对角占优阵,。,定义4,38/65,直接用矩阵,A,判定敛散性（续）,为严格对角占优阵，,Jacobi,迭代法与,G,-,S,迭代法均收敛。,又如例3中,，系数矩阵：,为非严格对角占优，但,A,为对称正定矩阵，且,=1.4,松驰法收敛。,如例1中,，线性方程组系数矩阵：,设有线性方程组,Ax,=,b,，,以下结论成立：,1.,若,A,为严格对角占优阵，则,Jacobi,迭代法与,G,-,S,法均收敛；,2.,若,A,为严格对角占优阵，0,1，则松驰法收敛；,3.,若,A,为对称正定矩阵，0,2，则松驰法收敛；,若,A,为对称正定阵，松驰法收敛,0,2。,39/65,三种迭代法判定敛散性举例,解：,能够总结，讨论迭代法收敛性，应首先从,A,出发讨,论其是否含有主对角占优或对称正定性；其次对迭代法,迭代阵讨论其是否有范数小于1；最终利用迭代阵谱半径讨论（这是充分必要条件）。,例5,40/65,例 5(续）,对,Jacobi,迭代法，其迭代阵轻易由,A,直接得到：,41/65,例,6,解,Jacobi,迭代阵为：,例,6,42/65,G-S,迭代阵为：,43/65,两点注释,注1,：,值得注意是，改变方程组中方程,次序，即将系数矩阵进行行交换，会改变迭代法收,敛性，比如，设有方程组,Ax,=,b,，,其中：,两点注释,44/65,两点注释（续）,注2,：,在利用迭代阵范数判定收敛时（推论1），只要,迭代阵范数小于1，即可判 定其收敛性，但当|1时,，则无法判定，还需利用谱半径作最终判定，而且，由,于不一样范数其值不一样，可能会出现某一个范数小于1,但很靠近于1（收敛），这时另一个范数可能会大于1,（无法判定）情况，如设,Ax,=,b,，,其中（见下）:,45/65,5.3 误差预计,定理5,证实,46/65,定理5（续）,利用,定理5,对,例1,，若给出,=10,4,，即要求各分量,误差绝对值不超出10,4,，则因为：,式,（4-20）,惯用于事后预计误差，即在实际计算时，利用相邻两次迭代值之差是否到达精度要求作为停机标准。,这表明需要迭代13次才能确保各分量绝对误差不超出10,-4,。,47/65,迭代改进法,不论是用直接法还是用迭代法求得病态方程组计算解,当精度不理想时，,能够使用迭代改进方法进行处理，即,使用迭代改进法,此法惯用于解不十分严重病态方程组。,迭代改进法：,（2）也可与直接法结合进行直接求解。,（1）可用于改进已求得近似争精度，,1.,对,Ax=b,用列主元消元法，分解法均可，,分解法（选主元）最好。,即：,详细步骤为：,48/65,迭代改进法（续1）,2.,求,x,(1),修正量,z,(1),：,先求,然后由,即可,解。,而,就是近似解,x,(1),改进解,.,这是因为有：,3.,可继续下去：再求,49/65,迭代改进法（续2）,例1：,与准确解,若用,Gauss,消元法求解（取五位有效数字）,比较，相差太远。,50/65,迭代改进法（续3）,若用迭代改进法：,K,0,0,0,0,0,1,9.9773,6.9786,0.0063242,0.0027559,2,8.1665,5.7110,0.00028017,0.0015411,3,8.4954,5.9413,0.00012774,0.0038975,4,8.4356,5.8994,0.00024094,0.000072077,51/65,迭代改进法（续4）,例2,Hilbert,阵,较准确解为,若用列主元法求得近似解：,对,x,(1),用迭代改进法进行改进：先求,52/65,迭代改进法（续5）,用,Doolittle,分解法求解,x,(3,),显然已含有四位有效数字,可计算,可继续求：,并由,Dolittle,分解法解,可得,53/65,6 非线性方程组解法,非线性方程组普通形式为：,这一节讨论它求解方法，主要是迭代解法（因为,除了极为特殊非线性方程组以外，类似于线性方程组,直接解法几乎是不可能），而且这里介绍迭代解,法都采取线性化方法组成各种形式迭代格式，只介,绍方法，不讨论收敛性。,其中：,x,i,是实变量，,f,i,是,x,i,非,线性实函数(,i,=1，2，,n,),可,记为,x,=(,x,1,，,x,2,，,x,n,),T,，,F,(,x,)=(,f,1,(,x,)，,f,2,(,x,)，,f,n,(,x,),T,，,上述方程组又可记为：,F,(,x,)=0,54/65,非线性方程组解法（续）,选取一组初值,x,1,(0),，,x,2,(0),，,x,n,(0),代入迭代,格式，可得向量序列,x,(,k,),，,而且普通有，若,x,(,k,),收敛，只要,g,i,连续，则收敛到原方程组,解（向量形式：,x,=,g,(,x,)，,x,(,k,+1),=,g,(,x,(,k,),)）。,普通方法：将上述方程组改写等价形式：,下面主要介绍,Newton,法,，,只介绍基本方法。,55/65,此式可展为：,6.1,Newton,法,按上述过程求,F,(,x,)=0,近似解方法称为,Newton,法,。,56/65,57/65,Newton,法详细做法,用,Newton,法详细做时：,每迭代一次，即要解一个线性方程组（即,Newton,方程组）,而且每次系数矩阵,F,(,x,(,k,),),不一样。,能够证实,：,Newton,法含有二阶收敛速度。,控制结束,：,对预先给定精度,：,58/65,两个方程情况下,Newton,法,两个方程情况，加深了解,Newton,法：,59/65,两个方程情况下,Newton,法举例,Newton,方程组,F,(,x,),在,x,(0),处取值，,F,(,x,),在,x,(0),取值得：,同单个方程,Nweton,法一样：解非线性方程组,Newton,法：收敛快，形式简单，格式固定。,但同时也：,1.对初值要求高；,2.迭代一次，需计算,n,+,n,2,个函数值及导数值；,3.求解一个,n,阶非线性方程组，计算量较大。,60/65,6.2 最速下降法,这一小节只介绍大约算法，因为要用别知识较多。,61/65,最速下降法（续）,所以，非线性方程组求解可转化为求解最优化问题,（求,(,x,),最小值）,而且没有任何约束条件，称为无条件约束最优化问题。,求解这类问题一个基本方法是最速下降法。,最速下降法,基本思想,是,：,从最优化问题近似解,x,(,k,),出发，沿使函数,(,x,),下,降最快方向，寻找新近似解,x,(,k,+1),，,这么继续下去，,逐步迫近最优化问题解。,62/65,最速下降法二维说明,以二维情形看,较轻易接收：,63/65,最速下降法二维说明（续）,64/65,最速下降法二维说明续,而在一维搜索方法中：若,(,),简单，就直接用一元函数极值方法求解。,普通可用：,对分搜索，,Fibonacci,搜索，黄金分割，插值法等。,用一维搜索任一个方法求出,后代入公式：,即得到第,k,+1,次近似解。,上述整个过程就是求解,(,x,1,x,2,),最速下降法,，,最速下降法,优点,是计算简单，收敛性好，,但,收敛速度为线性，故收敛速度较慢，可与,Newton,法,适用,：先,用最速下降法求一很好近似值，,再,用,Newton,法,。,对无约束最优化问题，还可用别方法求解。,65/65,
展开阅读全文
浙ICP备2021020529号-1 | 浙B2-20240490 
