计算方法第六章迭代法课件.ppt

第六章第六章 迭代法迭代法第一节第一节 非线性方程求根非线性方程求根（（ ）） 1、二分法、二分法利用连续函利用连续函数的性质进数的性质进行对分计算框图为：计算框图为：压缩映射：压缩映射：集合集合 A 上的映射上的映射 ，， A 上两个点上两个点 之间的距离之间的距离记为记为 ，如映射满足下面条件，称为压缩映射，如映射满足下面条件，称为压缩映射例：设函数例：设函数 满足：满足： ，则该函数为压缩映射，则该函数为压缩映射定理：如果定理：如果   为闭集合为闭集合 A 上的压缩映射，则方程上的压缩映射，则方程 x =  (x) 在在集合集合 A 上有唯一解且解可以用下面迭代得到：上有唯一解且解可以用下面迭代得到：2、、简单迭代：简单迭代：对于形如的方程对于形如的方程 ，可以通过迭代求解可以通过迭代求解定理：定理： 满足下面条件时，为压缩映射：满足下面条件时，为压缩映射：（（1）当）当 时，时，（（2））存在正数存在正数 L < 1，，使得使得则方程在区间上有唯一解则方程在区间上有唯一解 ，且解可以用下面迭代，且解可以用下面迭代得到得到例：在区间例：在区间[1，， ）上求解方程）上求解方程可用迭代法求解，迭代序列可用迭代法求解，迭代序列误差估计：第误差估计：第k步迭代计算值与精确值误差为步迭代计算值与精确值误差为使用迭代法求解方程值得注意的事项：使用迭代法求解方程值得注意的事项：1、将要求解的方程化成、将要求解的方程化成 的形式。

的形式2、该迭代法第一个条件不易验证因此，实际使用时，总在、该迭代法第一个条件不易验证因此，实际使用时，总在根的附近区间内进行迭代计算，以保证每次迭代的值都在根的附近区间内进行迭代计算，以保证每次迭代的值都在迭代区间内迭代区间内3、、L很小时迭代收敛非常快，但如果很小时迭代收敛非常快，但如果L与与1很接近，则收敛相很接近，则收敛相当慢收敛阶：收敛阶：定义：设定义：设 ，，如果存在实数如果存在实数 p 和非零常数和非零常数 c，，使：使：则称序列则称序列 p 阶收敛，特别，阶收敛，特别，p＝＝1时，称为线性收敛，时，称为线性收敛，p > 1 时，时，称为超线性收敛，称为超线性收敛，p＝＝2时称为平方收敛时称为平方收敛p 越大，序列收敛越快如果是线性收敛，则越大，序列收敛越快如果是线性收敛，则 0 < c < 1加速收敛技术：加速收敛技术：1、松弛法、松弛法选择适当的常数选择适当的常数  （松弛因子），令（松弛因子），令例子：求方程例子：求方程 的根的根迭代格式：迭代格式：取取  ＝＝1.15，，计算结果要求准确到小数后计算结果要求准确到小数后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 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Aitken加速法（适用于线性收敛情况）加速法（适用于线性收敛情况）3、插值加速法、插值加速法由线性插值公式：由线性插值公式：斯特芬森迭代斯特芬森迭代（迭代两次后用（迭代两次后用Aitken加速）加速）：：迭代一次用插值加速，称为迭代一次用插值加速，称为插值加速迭代插值加速迭代：：3. 对于一般对于一般的函数方程的函数方程 f (x) = 0 的求解，解决方案为：构造的求解，解决方案为：构造等价的方程等价的方程 x =  (x) ，，利用迭代法求解。

利用迭代法求解这称为牛顿迭代，迭代序列收敛条件为：这称为牛顿迭代，迭代序列收敛条件为：这在函数方程这在函数方程 f (x) = 0 根根 a 的的某邻域内显然成立某邻域内显然成立牛顿迭代法的几何意义：牛顿迭代法的几何意义：一个例子：一个例子：牛顿迭代法是局部收敛因此，只有牛顿迭代法是局部收敛因此，只有初值选得靠近精确解初值选得靠近精确解时，时，才能保证迭代序列收敛才能保证迭代序列收敛定理：设定理：设函数函数 f(x) 在区间在区间[a,b]上二上二阶导数存在，且：阶导数存在，且：则牛顿迭代序列收敛于则牛顿迭代序列收敛于f(x) ＝＝0 在区间在区间[a,b]上的唯一根上的唯一根利用泰勒展开容易证明，利用泰勒展开容易证明，牛顿迭代法具有二阶收牛顿迭代法具有二阶收敛性，即平方收敛收敛性，即平方收敛收敛速度快这是牛顿迭代敛速度快这是牛顿迭代法的主要优点法的主要优点计算步骤（框图）：计算步骤（框图）：例子：建立求某个例子：建立求某个正实数正实数 c 的平方根的平方根的迭代格式的迭代格式设函数方程设函数方程 f (x) = 0 的根为的根为  ，，将将 f ( ) 泰勒展开泰勒展开改进牛顿迭代改进牛顿迭代 或或 柯西迭代柯西迭代设函数设函数 y = f (x) 的反函数为的反函数为 x =   (y)，， f (x) = 0 的根的根为为  牛顿迭代法的收敛性：牛顿迭代法的收敛性：牛顿迭代法二阶收敛，两种改进牛顿迭代法三阶收敛牛顿迭代法二阶收敛，两种改进牛顿迭代法三阶收敛简化牛顿法：简化牛顿法：目的：避免计算迭代格式中的导数目的：避免计算迭代格式中的导数方法：将牛顿迭代中导数取为某个定点的值，如方法：将牛顿迭代中导数取为某个定点的值，如 ，，按如下格式按如下格式 迭代迭代几何意义几何意义如图如图进一步，取任意常数进一步，取任意常数 c 代替代替迭代公式中的导数值，迭代公式为迭代公式中的导数值，迭代公式为迭代函数为迭代函数为 ，为使迭代序列收敛，，为使迭代序列收敛， c 应满足应满足这称为简化牛顿法，显然，当这称为简化牛顿法，显然，当 c 与导数同号且满足上面式子时，与导数同号且满足上面式子时，迭代收敛。

迭代收敛本例中，本例中， c 与导数异号，迭代发散与导数异号，迭代发散弦割法：用过弦割法：用过 两个点的直线的斜两个点的直线的斜率代替函数在点率代替函数在点 处函数的导数，进行迭代处函数的导数，进行迭代迭代公式：迭代公式：同样，此法具有局部同样，此法具有局部收敛性其收敛是超收敛性其收敛是超线性收敛，收敛阶为线性收敛，收敛阶为1.618单点弦割法：用固定点单点弦割法：用固定点 代替代替可以证明，单点法可以证明，单点法也是局部收敛的，也是局部收敛的，且收敛阶为线性收且收敛阶为线性收敛，即敛，即 1 阶收敛牛顿下山法：牛顿下山法：目的是解决初值的选取范围太小这以困难目的是解决初值的选取范围太小这以困难构造迭代格式为：构造迭代格式为：其中的参数满足：其中的参数满足：这个方法称为牛顿下山法其中的参数称为下山因子，这个方法称为牛顿下山法其中的参数称为下山因子，通常取通常取 ，然后逐步减半然后逐步减半牛顿下山法当牛顿下山法当 时，只有线性收敛速度，但对初值的选取时，只有线性收敛速度，但对初值的选取却放的相当宽。

却放的相当宽第二节第二节 线性代数方程组迭代解法线性代数方程组迭代解法求解代数方程组求解代数方程组方法：将方程组改造为一个等价的方程组方法：将方程组改造为一个等价的方程组构造迭代格式：构造迭代格式：设设  为事先给定的误差精度，为事先给定的误差精度，则可以得到迭代次数：则可以得到迭代次数：定理：对于上面的迭代格式，如果定理：对于上面的迭代格式，如果B的范数小于的范数小于1，则对于任，则对于任意的初始向量与常向量意的初始向量与常向量 g ，，迭代格式收敛，迭代误差估计：迭代格式收敛，迭代误差估计：2.1 雅可比迭代与高斯－赛德尔迭代雅可比迭代与高斯－赛德尔迭代考虑考虑n阶方程组，设系数阵非奇异，且对角元非零阶方程组，设系数阵非奇异，且对角元非零将方程组变形为：将方程组变形为：任意取一组初值任意取一组初值 ，可以建立迭代格式：，可以建立迭代格式：显然，如上面的迭代收敛，则收敛向量必然为方程组的唯一解显然，如上面的迭代收敛，则收敛向量必然为方程组的唯一解这个迭代法称为这个迭代法称为雅可比迭代雅可比迭代雅可比迭代也称为同时（或整体）代换雅可比迭代也称为同时（或整体）代换显然，如果雅可比迭代法收敛，则将迭代格式中每一步迭代得显然，如果雅可比迭代法收敛，则将迭代格式中每一步迭代得到的迭代向量分量带入下一步迭代，则迭代效果应该更好，这到的迭代向量分量带入下一步迭代，则迭代效果应该更好，这种迭代称为种迭代称为高斯－赛德尔迭代高斯－赛德尔迭代，（逐个代换法），（逐个代换法）雅可比迭代与高斯－赛德尔迭代都称为简单迭代。

雅可比迭代与高斯－赛德尔迭代都称为简单迭代逐个超松弛（逐个超松弛（SOR））迭代：迭代：基本迭代的收敛基本迭代的收敛雅可比迭代的矩阵形式：雅可比迭代的矩阵形式：高斯高斯——赛德尔迭代的矩阵形式：赛德尔迭代的矩阵形式：超松弛（超松弛（SOR））迭代矩阵形式迭代矩阵形式：：代数方程组简单迭代法收敛的条件代数方程组简单迭代法收敛的条件定义：定义：矩阵矩阵 A 的特征值中模最大者，称为矩阵的谱半径，的特征值中模最大者，称为矩阵的谱半径，矩矩阵阵 A 的谱半径记为的谱半径记为   ( A )定理：简单迭代定理：简单迭代 收敛的充分收敛的充分必要条件是必要条件是 或矩阵或矩阵 B 的谱半径的谱半径  ( B ) < 1推论推论1：如果迭代矩阵的范数小于：如果迭代矩阵的范数小于1，则简单迭代收敛则简单迭代收敛推论推论2：逐次超松弛迭代法收敛的一个条件是：逐次超松弛迭代法收敛的一个条件是 0 <   < 2推论推论3：：A严格对角占优时，雅可比迭代、严格对角占优时，雅可比迭代、0 <    1 的的SOR法法都收敛。

都收敛推论推论4：：A对称正定时，雅可比迭代法收敛的充要条件是对称正定时，雅可比迭代法收敛的充要条件是 2D －－ A 对称正定，对称正定，SOR收敛的充要条件是收敛的充要条件是0 <  < 21、、A严格对角占优，则雅可比、高斯－赛德尔迭代都收敛严格对角占优，则雅可比、高斯－赛德尔迭代都收敛2、如、如 A 对称正定，则高斯－赛德尔迭代收敛对称正定，则高斯－赛德尔迭代收敛3、如果、如果 A 对称正定，对称正定，D 为为 A 的对角线上的元组成的矩阵，如的对角线上的元组成的矩阵，如 2D－－A也对称正定，则雅可比迭代收敛；如也对称正定，则雅可比迭代收敛；如A对称正定而对称正定而 2D－－A 非正定，则雅可比迭代不收敛非正定，则雅可比迭代不收敛第三节第三节 非线性方程组的迭代解法非线性方程组的迭代解法3.1 一般迭代一般迭代 设有非线性方程组设有非线性方程组 将方程组改写为下式，将方程组改写为下式，可得可得Jacobi型迭代格式型迭代格式记记，称为关于 x 的Frechet导数定理定理：若满足：1、存在凸闭区域，使得2、存在正常数，使得，则在在惟一的不动点 x*，并且迭代序列收敛于 x*，而且有上述关于方程式迭代一样的误差估计。

注：上述矩阵的范数可取注：上述矩阵的范数可取1范数、范数、2范数、无穷范数等范数、无穷范数等存例子：例子： 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x=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 end类似的可以得到高斯－赛德尔型迭代：类似的可以得到高斯－赛德尔型迭代： 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 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3.2 牛顿迭代牛顿迭代对非线性代数方程组，若是其根的一个近似，因为令，就得到非线性代数方程组的Newton迭代格式。

因为令，则得到满足的线性代数方程组，解出即得或解或解于是可以得到迭代格式：于是可以得到迭代格式：满足的方程组满足的方程组简化牛顿法简化牛顿法目的是避免计算迭代公式中繁杂的导数，解决方目的是避免计算迭代公式中繁杂的导数，解决方法与一元函数牛顿法类似，即将所有导数取为固定值，如迭法与一元函数牛顿法类似，即将所有导数取为固定值，如迭代初值的导数值代初值的导数值与单个方程的情形类似，牛顿法中 f 的导数的元素用合适的差商来近似，如就可得到拟牛顿法或弦截法拟牛顿法或弦截法。