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

第六章第六章 迭代法迭代法第六章 迭代法1第一节第一节 非线性方程求根非线性方程求根（）1、二分法、二分法利用连续函利用连续函数的性质进数的性质进行对分。行对分。计算框图为：计算框图为：第一节 2压缩映射：压缩映射：集合集合 A 上的映射上的映射 ，A 上两个点上两个点 之间的距离之间的距离记为记为 ，如映射满足下面条件，称为压缩映射，如映射满足下面条件，称为压缩映射例：设函数例：设函数 满足：满足：，则该函数为压缩映射，则该函数为压缩映射定理：如果定理：如果 为闭集合为闭集合 A 上的压缩映射，则方程上的压缩映射，则方程 x=(x)在在集合集合 A 上有唯一解。且解可以用下面迭代得到：上有唯一解。且解可以用下面迭代得到：压缩映射：定理：如果 为闭集合 A 上的压缩映射，则方程32、简单迭代：简单迭代：对于形如的方程对于形如的方程 ，可以通过迭代求解。，可以通过迭代求解。定理：定理：满足下面条件时，为压缩映射：满足下面条件时，为压缩映射：（1）当）当 时，时，（2）存在正数存在正数 L 1 时，时，称为超线性收敛，称为超线性收敛，p2时称为平方收敛。时称为平方收敛。p 越大，序列收敛越快。如果是线性收敛，则越大，序列收敛越快。如果是线性收敛，则 0 c 1收敛阶：9加速收敛技术：加速收敛技术：1、松弛法、松弛法选择适当的常数选择适当的常数 （松弛因子），令（松弛因子），令加速收敛技术：10例子：求方程例子：求方程 的根的根迭代格式：迭代格式：取取 1.15，例子：求方程 11计算结果要求准确到小数后计算结果要求准确到小数后8位数字位数字 2.154434739312699 2.103612082648350 2.095927464327627 2.094760599916342 2.094583304649520 2.094556363492997 2.094552269550262 2.094551647438705 2.094551552903205 2.094551538537676 2.094551536354704 2.102599958448522 2.094749937881704 2.094556446501749 2.094551657513653 2.094551538972266 2.094551536038016计算结果要求准确到小数后8位数字 2.154412 x=2.510 y=x x=(2*y+5)*(1.0/3.0)if(abs(x-y).lt.0.00000001)then goto 15endifgoto 1015 x=2.520 y=x x=(2*y+5)*(1.0/3.0)x=1.15*x+(1.0-1.15)*yif(abs(x-y).lt.0.00000001)then goto 30endifgoto 2030 end x=2.515 x=2.513Aitken加速法（适用于线性收敛情况）加速法（适用于线性收敛情况）Aitken加速法（适用于线性收敛情况）143、插值加速法、插值加速法3、插值加速法15由线性插值公式：由线性插值公式：由线性插值公式：16斯特芬森迭代斯特芬森迭代（迭代两次后用（迭代两次后用Aitken加速）加速）：迭代一次用插值加速，称为迭代一次用插值加速，称为插值加速迭代插值加速迭代：斯特芬森迭代（迭代两次后用Aitken加速）：迭代一次用插值173.对于一般对于一般的函数方程的函数方程 f(x)=0 的求解，解决方案为：构造的求解，解决方案为：构造等价的方程等价的方程 x=(x)，利用迭代法求解。利用迭代法求解。这称为牛顿迭代，迭代序列收敛条件为：这称为牛顿迭代，迭代序列收敛条件为：这在函数方程这在函数方程 f(x)=0 根根 a 的的某邻域内显然成立。某邻域内显然成立。3.对于一般的函数方程 f(x)=0 的求解，解决方18牛顿迭代法的几何意义：牛顿迭代法的几何意义：牛顿迭代法的几何意义：19一个例子：一个例子：一个例子：20牛顿迭代法是局部收敛。因此，只有牛顿迭代法是局部收敛。因此，只有初值选得靠近精确解初值选得靠近精确解时，时，才能保证迭代序列收敛。才能保证迭代序列收敛。定理：设定理：设函数函数 f(x)在区间在区间a,b上二上二阶导数存在，且：阶导数存在，且：则牛顿迭代序列收敛于则牛顿迭代序列收敛于f(x)0 在区间在区间a,b上的唯一根。上的唯一根。牛顿迭代法是局部收敛。因此，只有初值选得靠近精确解时，才能保21利用泰勒展开容易证明，利用泰勒展开容易证明，牛顿迭代法具有二阶收牛顿迭代法具有二阶收敛性，即平方收敛。收敛性，即平方收敛。收敛速度快这是牛顿迭代敛速度快这是牛顿迭代法的主要优点。法的主要优点。计算步骤（框图）：计算步骤（框图）：例子：建立求某个例子：建立求某个正实数正实数 c 的平方根的平方根的迭代格式。的迭代格式。利用泰勒展开容易证明，例子：建立求某个22设函数方程设函数方程 f(x)=0 的根为的根为 ，将将 f()泰勒展开泰勒展开设函数方程 f(x)=0 的根为，将 f()23改进牛顿迭代改进牛顿迭代 或或 柯西迭代柯西迭代改进牛顿迭代 或 柯西迭代24设函数设函数 y=f(x)的反函数为的反函数为 x=(y)，f(x)=0 的根的根为为 设函数 y=f(x)的反函数为 x=(y)，25牛顿迭代法的收敛性：牛顿迭代法的收敛性：牛顿迭代法二阶收敛，两种改进牛顿迭代法三阶收敛牛顿迭代法二阶收敛，两种改进牛顿迭代法三阶收敛牛顿迭代法的收敛性：26简化牛顿法：简化牛顿法：目的：避免计算迭代格式中的导数目的：避免计算迭代格式中的导数方法：将牛顿迭代中导数取为某个定点的值，如方法：将牛顿迭代中导数取为某个定点的值，如 ，按如下格式按如下格式 迭代迭代几何意义几何意义如图如图简化牛顿法：27进一步，取任意常数进一步，取任意常数 c 代替代替迭代公式中的导数值，迭代公式为迭代公式中的导数值，迭代公式为迭代函数为迭代函数为 ，为使迭代序列收敛，为使迭代序列收敛，c 应满足应满足这称为简化牛顿法，显然，当这称为简化牛顿法，显然，当 c 与导数同号且满足上面式子时，与导数同号且满足上面式子时，迭代收敛。迭代收敛。进一步，取任意常数 c 代替迭代公式中的导数值，迭代公式为28本例中，本例中，c 与导数异号，迭代发散与导数异号，迭代发散本例中，c 与导数异号，迭代发散29弦割法：用过弦割法：用过 两个点的直线的斜两个点的直线的斜率代替函数在点率代替函数在点 处函数的导数，进行迭代。处函数的导数，进行迭代。迭代公式：迭代公式：同样，此法具有局部同样，此法具有局部收敛性。其收敛是超收敛性。其收敛是超线性收敛，收敛阶为线性收敛，收敛阶为1.618弦割法：用过 30单点弦割法：用固定点单点弦割法：用固定点 代替代替可以证明，单点法可以证明，单点法也是局部收敛的，也是局部收敛的，且收敛阶为线性收且收敛阶为线性收敛，即敛，即 1 阶收敛。阶收敛。单点弦割法：用固定点 代替31牛顿下山法：牛顿下山法：目的是解决初值的选取范围太小这以困难。目的是解决初值的选取范围太小这以困难。构造迭代格式为：构造迭代格式为：其中的参数满足：其中的参数满足：这个方法称为牛顿下山法。其中的参数称为下山因子，这个方法称为牛顿下山法。其中的参数称为下山因子，通常取通常取 ，然后逐步减半。，然后逐步减半。牛顿下山法当牛顿下山法当 时，只有线性收敛速度，但对初值的选取时，只有线性收敛速度，但对初值的选取却放的相当宽。却放的相当宽。牛顿下山法：32第二节第二节 线性代数方程组迭代解法线性代数方程组迭代解法求解代数方程组求解代数方程组方法：将方程组改造为一个等价的方程组方法：将方程组改造为一个等价的方程组构造迭代格式：构造迭代格式：设设 为事先给定的误差精度，为事先给定的误差精度，则可以得到迭代次数：则可以得到迭代次数：定理：对于上面的迭代格式，如果定理：对于上面的迭代格式，如果B的范数小于的范数小于1，则对于任，则对于任意的初始向量与常向量意的初始向量与常向量 g，迭代格式收敛，迭代误差估计：迭代格式收敛，迭代误差估计：第二节 线性代数方程组迭代解法设 为事先给定的误差精度332.1 雅可比迭代与高斯赛德尔迭代雅可比迭代与高斯赛德尔迭代考虑考虑n阶方程组，设系数阵非奇异，且对角元非零阶方程组，设系数阵非奇异，且对角元非零将方程组变形为：将方程组变形为：2.1 雅可比迭代与高斯赛德尔迭代34任意取一组初值任意取一组初值 ，可以建立迭代格式：，可以建立迭代格式：显然，如上面的迭代收敛，则收敛向量必然为方程组的唯一解。显然，如上面的迭代收敛，则收敛向量必然为方程组的唯一解。这个迭代法称为这个迭代法称为雅可比迭代雅可比迭代。雅可比迭代也称为同时（或整体）代换雅可比迭代也称为同时（或整体）代换任意取一组初值 35显然，如果雅可比迭代法收敛，则将迭代格式中每一步迭代得显然，如果雅可比迭代法收敛，则将迭代格式中每一步迭代得到的迭代向量分量带入下一步迭代，则迭代效果应该更好，这到的迭代向量分量带入下一步迭代，则迭代效果应该更好，这种迭代称为种迭代称为高斯赛德尔迭代高斯赛德尔迭代，（逐个代换法），（逐个代换法）雅可比迭代与高斯赛德尔迭代都称为简单迭代。雅可比迭代与高斯赛德尔迭代都称为简单迭代。显然，如果雅可比迭代法收敛，则将迭代格式中每一步迭代得36逐个超松弛（逐个超松弛（SOR）迭代：迭代：逐个超松弛（SOR）迭代：37基本迭代的收敛基本迭代的收敛基本迭代的收敛38雅可比迭代的矩阵形式：雅可比迭代的矩阵形式：高斯高斯赛德尔迭代的矩阵形式：赛德尔迭代的矩阵形式：超松弛（超松弛（SOR）迭代矩阵形式迭代矩阵形式：雅可比迭代的矩阵形式：39代数方程组简单迭代法收敛的条件代数方程组简单迭代法收敛的条件定义：定义：矩阵矩阵 A 的特征值中模最大者，称为矩阵的谱半径，的特征值中模最大者，称为矩阵的谱半径，矩矩阵阵 A 的谱半径记为的谱半径记为 (A)定理：简单迭代定理：简单迭代 收敛的充分收敛的充分必要条件是必要条件是 或矩阵或矩阵 B 的谱半径的谱半径 (B)1代数方程组简单迭代法收敛的条件40推论推论1：如果迭代矩阵的范数小于：如果迭代矩阵的范数小于1，则简单迭代收敛。，则简单迭代收敛。推论推论2：逐次超松弛迭代法收敛的一个条件是：逐次超松弛迭代法收敛的一个条件是 0 2推论推论3：A严格对角占优时，雅可比迭代、严格对角占优时，雅可比迭代、0 1 的的SOR法法都收敛。都收敛。推论推论4：A对称正定时，雅可比迭代法收敛的充要条件是对称正定时，雅可比迭代法收敛的充要条件是 2D A 对称正定，对称正定，SOR收敛的充要条件是收敛的充要条件是0 21、A严格对角占优，则雅可比、高斯赛德尔迭代都收敛。严格对角占优，则雅可比、高斯赛德尔迭代都收敛。2、如、如 A 对称正定，则高斯赛德尔迭代收敛。对称正定，则高斯赛德尔迭代收敛。3、如果、如果 A 对称正定，对称正定，D 为为 A 的对角线上的元组成的矩阵，如的对角线上的元组成的矩阵，如 2DA也对称正定，则雅可比迭代收敛；如也对称正定，则雅可比迭代收敛；如A对称正定而对称正定而 2DA 非正定，则雅可比迭代不收敛。非正定，则雅可比迭代不收敛。推论1：如果迭代矩阵的范数小于1，则简单迭代收敛。1、A严格41第三节第三节 非线性方程组的迭代解法非线性方程组的迭代解法3.1 一般迭代。一般迭代。设有非线性方程组设有非线性方程组 第三节 非线性方程组的迭代解法42将方程组改写为下式，将方程组改写为下式，可得可得Jacobi型迭代格式型迭代格式将方程组改写为下式，可得Jacobi型迭代格式43记记，称为关于 x 的Frechet导数。定理定理：若满足：1、存在凸闭区域，使得2、存在正常数，使得，则在在惟一的不动点 x*，并且迭代序列收敛于 x*，而且有上述关于方程式迭代一样的误差估计。注：上述矩阵的范数可取注：上述矩阵的范数可取1范数、范数、2范数、无穷范数等。范数、无穷范数等。存记，称为关于 x 的Frechet导数。定理：若满足：1、存44例子：例子：例子：45 2.249999996274710E-001 0.000000000000000E+000 2.186919316403400E-001 5.466796866210643E-002 2.325557956363573E-001 5.317841537994177E-002 2.317490821626177E-001 5.644888021896249E-002 2.325921363078080E-001 5.625890688180394E-002 2.325180586318136E-001 5.645743714344483E-002 2.325700280145271E-001 5.643999442076879E-002 2.325640279518354E-001 5.645223144329810E-002 2.325672764847015E-001 5.645081864117191E-002 2.325668208064959E-001 5.645158355581563E-002 2.325670264099253E-001 5.645147625974770E-002 2.325669930999687E-001 5.645152467207023E-002 2.325670062538411E-001 5.645151682875589E-002 2.325670038780621E-001 5.645151992602669E-002 2.249999996274710E-001 0.46x=0.0y=0.010 x1=x y1=y x=0.25*(1+y1-0.1*exp(x1)y=0.25*(x1-0.125*x1*x1)write(10,*)x,y if(abs(x-x1)+abs(y-y1).lt.0.00000001)then goto 15endif goto 1015 endx=0.047类似的可以得到高斯赛德尔型迭代：类似的可以得到高斯赛德尔型迭代：类似的可以得到高斯赛德尔型迭代：48 2.249999996274710E-001 5.466796866210643E-002 2.323589238058666E-001 5.640252253045976E-002 2.325613187635559E-001 5.645018072260635E-002 2.325668492678739E-001 5.645148296139392E-002 2.325670003634809E-001 5.645151853905563E-002 2.325670044914536E-001 5.645151951104690E-002 2.249999996274710E-001 5.49 x=0.0 y=0.020 x1=x y1=y x=0.25*(1+y1-0.1*exp(x1)y=0.25*(x-0.125*x*x)write(20,*)x,y if(abs(x-x1)+abs(y-y1).lt.0.00000001)then goto 30endifgoto 2030 end x=0.0503.2 牛顿迭代牛顿迭代对非线性代数方程组，若是其根的一个近似，因为令，就得到非线性代数方程组的Newton迭代格式。因为令，则得到满足的线性代数方程组，解出即得3.2 牛顿迭代对非线性代数方程组，若是其根的一个近似，因51或解或解于是可以得到迭代格式：于是可以得到迭代格式：满足的方程组满足的方程组或解于是可以得到迭代格式：满足的方程组52简化牛顿法简化牛顿法。目的是避免计算迭代公式中繁杂的导数，解决方。目的是避免计算迭代公式中繁杂的导数，解决方法与一元函数牛顿法类似，即将所有导数取为固定值，如迭法与一元函数牛顿法类似，即将所有导数取为固定值，如迭代初值的导数值。代初值的导数值。简化牛顿法。目的是避免计算迭代公式中繁杂的导数，解决方法与一53与单个方程的情形类似，牛顿法中 f 的导数的元素用合适的差商来近似，如就可得到拟牛顿法或弦截法。拟牛顿法或弦截法。与单个方程的情形类似，牛顿法中 f 的导数的元素用合适的差商54若用格式其中下山因子合适地选取使得就得到牛顿下山法。若用格式，其中是的简单修正，且满足则得到Broyden算法。特别，若取，其中u,v 是待定的列向量，使其满足上式，则得到秩一Broyden算法。比如若用格式其中下山因子合适地选取使得就得到牛顿下山法。若用格式55小结小结 1、本章的目的是求解形如、本章的目的是求解形如 f(x)=0 的方程，而其核心方法是的方程，而其核心方法是将所要求解的方程变形为将所要求解的方程变形为 x=(x)，利用利用 (x)为压缩映射，为压缩映射，通过迭代求出其解。通过迭代求出其解。2、变形中切记要恒等变形！、变形中切记要恒等变形！3、在恒等变形中，为使变形得到的函数、在恒等变形中，为使变形得到的函数 (x)为压缩映射，一为压缩映射，一个技巧是利用待定参数。个技巧是利用待定参数。4、恒等变形的一种重要格式是牛顿迭代，证明其迭代收敛阶、恒等变形的一种重要格式是牛顿迭代，证明其迭代收敛阶的一个常用技巧是泰勒展开。的一个常用技巧是泰勒展开。5、n维空间中代数方程迭代求解的收敛条件是谱半径小于维空间中代数方程迭代求解的收敛条件是谱半径小于 1.小结 56