计算方法第六章(迭代法)PPT课件

.,1,第六章迭代法,.,2,第一节非线性方程求根（）1、二分法利用连续函数的性质进行对分。计算框图为：,.,3,压缩映射：集合A上的映射，A上两个点之间的距离记为，如映射满足下面条件，称为压缩映射例：设函数满足：，则该函数为压缩映射,定理：如果为闭集合A上的压缩映射，则方程x=(x)在集合A上有唯一解。且解可以用下面迭代得到：,.,4,2、简单迭代：对于形如的方程，可以通过迭代求解。定理：满足下面条件时，为压缩映射：（1）当时，（2）存在正数L1时，称为超线性收敛，p2时称为平方收敛。p越大，序列收敛越快。如果是线性收敛，则0c1,.,10,加速收敛技术：1、松弛法选择适当的常数（松弛因子），令,.,11,例子：求方程的根迭代格式：取1.15，,.,12,计算结果要求准确到小数后8位数字,2.1544347393126992.1036120826483502.0959274643276272.0947605999163422.0945833046495202.0945563634929972.0945522695502622.0945516474387052.0945515529032052.0945515385376762.094551536354704,2.1025999584485222.0947499378817042.0945564465017492.0945516575136532.0945515389722662.094551536038016,.,13,x=2.510y=xx=(2*y+5)*(1.0/3.0)if(abs(x-y).lt.0.00000001)thengoto15endifgoto10,15x=2.520y=xx=(2*y+5)*(1.0/3.0)x=1.15*x+(1.0-1.15)*yif(abs(x-y).lt.0.00000001)thengoto30endifgoto2030end,.,14,Aitken加速法（适用于线性收敛情况）,.,15,3、插值加速法,.,16,由线性插值公式：,.,17,斯特芬森迭代（迭代两次后用Aitken加速）：,迭代一次用插值加速，称为插值加速迭代：,.,18,3.对于一般的函数方程f(x)=0的求解，解决方案为：构造等价的方程x=(x)，利用迭代法求解。,这称为牛顿迭代，迭代序列收敛条件为：,这在函数方程f(x)=0根a的某邻域内显然成立。,.,19,牛顿迭代法的几何意义：,.,20,一个例子：,.,21,牛顿迭代法是局部收敛。因此，只有初值选得靠近精确解时，才能保证迭代序列收敛。定理：设函数f(x)在区间a,b上二阶导数存在，且：则牛顿迭代序列收敛于f(x)0在区间a,b上的唯一根。,.,22,利用泰勒展开容易证明，牛顿迭代法具有二阶收敛性，即平方收敛。收敛速度快这是牛顿迭代法的主要优点。计算步骤（框图）：,例子：建立求某个正实数c的平方根的迭代格式。,.,23,设函数方程f(x)=0的根为，将f()泰勒展开,.,24,改进牛顿迭代或柯西迭代,.,25,设函数y=f(x)的反函数为x=(y)，f(x)=0的根为,.,26,牛顿迭代法的收敛性：牛顿迭代法二阶收敛，两种改进牛顿迭代法三阶收敛,.,27,简化牛顿法：目的：避免计算迭代格式中的导数方法：将牛顿迭代中导数取为某个定点的值，如，按如下格式迭代几何意义如图,.,28,进一步，取任意常数c代替迭代公式中的导数值，迭代公式为迭代函数为，为使迭代序列收敛，c应满足这称为简化牛顿法，显然，当c与导数同号且满足上面式子时，迭代收敛。,.,29,本例中，c与导数异号，迭代发散,.,30,弦割法：用过两个点的直线的斜率代替函数在点处函数的导数，进行迭代。迭代公式：同样，此法具有局部收敛性。其收敛是超线性收敛，收敛阶为1.618,.,31,单点弦割法：用固定点代替可以证明，单点法也是局部收敛的，且收敛阶为线性收敛，即1阶收敛。,.,32,牛顿下山法：目的是解决初值的选取范围太小这以困难。构造迭代格式为：其中的参数满足：这个方法称为牛顿下山法。其中的参数称为下山因子，通常取，然后逐步减半。牛顿下山法当时，只有线性收敛速度，但对初值的选取却放的相当宽。,.,33,第二节线性代数方程组迭代解法求解代数方程组方法：将方程组改造为一个等价的方程组构造迭代格式：,设为事先给定的误差精度，则可以得到迭代次数：,定理：对于上面的迭代格式，如果B的范数小于1，则对于任意的初始向量与常向量g，迭代格式收敛，迭代误差估计：,.,34,2.1雅可比迭代与高斯赛德尔迭代考虑n阶方程组，设系数阵非奇异，且对角元非零将方程组变形为：,.,35,任意取一组初值，可以建立迭代格式：显然，如上面的迭代收敛，则收敛向量必然为方程组的唯一解。这个迭代法称为雅可比迭代。雅可比迭代也称为同时（或整体）代换,.,36,显然，如果雅可比迭代法收敛，则将迭代格式中每一步迭代得到的迭代向量分量带入下一步迭代，则迭代效果应该更好，这种迭代称为高斯赛德尔迭代，（逐个代换法）雅可比迭代与高斯赛德尔迭代都称为简单迭代。,.,37,逐个超松弛（SOR）迭代：,.,38,基本迭代的收敛,.,39,雅可比迭代的矩阵形式：高斯赛德尔迭代的矩阵形式：超松弛（SOR）迭代矩阵形式：,.,40,代数方程组简单迭代法收敛的条件定义：矩阵A的特征值中模最大者，称为矩阵的谱半径，矩阵A的谱半径记为(A)定理：简单迭代收敛的充分必要条件是或矩阵B的谱半径(B)1,.,41,推论1：如果迭代矩阵的范数小于1，则简单迭代收敛。推论2：逐次超松弛迭代法收敛的一个条件是02推论3：A严格对角占优时，雅可比迭代、01的SOR法都收敛。推论4：A对称正定时，雅可比迭代法收敛的充要条件是2DA对称正定，SOR收敛的充要条件是02,1、A严格对角占优，则雅可比、高斯赛德尔迭代都收敛。2、如A对称正定，则高斯赛德尔迭代收敛。3、如果A对称正定，D为A的对角线上的元组成的矩阵，如2DA也对称正定，则雅可比迭代收敛；如A对称正定而2DA非正定，则雅可比迭代不收敛。,.,42,第三节非线性方程组的迭代解法3.1一般迭代。设有非线性方程组,.,43,将方程组改写为下式，,可得Jacobi型迭代格式,.,44,记,，称为,关于x的Frechet导数。,定理：若,满足：1、存在凸闭区域,，使得,2、存在正常数,，使得,，则,在,在惟一的不动点x*，并且迭代序列,收敛于x*，而且有上述关于方程式迭代一样的误差估计。,注：上述矩阵的范数可取1范数、2范数、无穷范数等。,存,.,45,例子：,.,46,2.249999996274710E-0010.000000000000000E+0002.186919316403400E-0015.466796866210643E-0022.325557956363573E-0015.317841537994177E-0022.317490821626177E-0015.644888021896249E-0022.325921363078080E-0015.625890688180394E-0022.325180586318136E-0015.645743714344483E-0022.325700280145271E-0015.643999442076879E-0022.325640279518354E-0015.645223144329810E-0022.325672764847015E-0015.645081864117191E-0022.325668208064959E-0015.645158355581563E-0022.325670264099253E-0015.645147625974770E-0022.325669930999687E-0015.645152467207023E-0022.325670062538411E-0015.645151682875589E-0022.325670038780621E-0015.645151992602669E-002,.,47,x=0.0y=0.010 x1=xy1=yx=0.25*(1+y1-0.1*exp(x1)y=0.25*(x1-0.125*x1*x1)write(10,*)x,yif(abs(x-x1)+abs(y-y1).lt.0.00000001)thengoto15endifgoto1015end,.,48,类似的可以得到高斯赛德尔型迭代：,.,49,2.249999996274710E-0015.466796866210643E-0022.323589238058666E-0015.640252253045976E-0022.325613187635559E-0015.645018072260635E-0022.325668492678739E-0015.645148296139392E-0022.325670003634809E-0015.645151853905563E-0022.325670044914536E-0015.645151951104690E-002,.,50,x=0.0y=0.020 x1=xy1=yx=0.25*(1+y1-0.1*exp(x1)y=0.25*(x-0.125*x*x)write(20,*)x,yif(abs(x-x1)+abs(y-y1).lt.0.00000001)thengoto30endifgoto2030end,.,51,3.2牛顿迭代,对非线性代数方程组,，若,是其根,的一个近似，因为,令,，就得到非线性代数方程组,的Newton迭代格式。因为,令,，则得到,满足的线性代数方程组，,解出即得,.,52,或解,于是可以得到迭代格式：,满足的方程组,.,53,简化牛顿法。目的是避免计算迭代公式中繁杂的导数，解决方法与一元函数牛顿法类似，即将所有导数取为固定值，如迭代初值的导数值。,.,54,与单个方程的情形类似，牛顿法中f的导数的元素用合适的差商来近似，如,就可得到拟牛顿法或弦截法。,.,55,若用格式,其中下山因子,合适地选取使得,就得到牛顿下山法。,若用格式,，其中,是,的简单,修正，且满足,则得到Broyden算法。特别，若取,，其中,u,v是待定