1、第六章第六章 迭代法迭代法第一节第一节 非线性方程求根非线性方程求根（ ） 1、二分法、二分法利用连续函利用连续函数的性质进数的性质进行对分。行对分。计算框图为：计算框图为：( )0f x 压缩映射：压缩映射：集合集合 A 上的映射上的映射 ， A 上两个点上两个点 之间的距离之间的距离记为记为 ，如映射满足下面条件，称为压缩映射，如映射满足下面条件，称为压缩映射例：设函数例：设函数 满足：满足： ，则该函数为压缩映射，则该函数为压缩映射: AA12,xx12( ,)d x x121212,(0,1) , . .(), ()(,)x xAks tdxxkd x x( )f x( )1fxk定理
2、：如果定理：如果 为闭集合为闭集合 A 上的压缩映射，则方程上的压缩映射，则方程 x = (x) 在集在集合合 A 上有唯一解。且解可以用下面迭代得到：上有唯一解。且解可以用下面迭代得到：01*,(),()nnnxAxxxxxx*101nnkxxxxk2、简单迭代：简单迭代：对于形如的方程对于形如的方程 ，可以通过迭代求解。，可以通过迭代求解。定理：定理： 满足下面条件时，为压缩映射：满足下面条件时，为压缩映射：（1）当）当 时，时，（2）存在正数存在正数 L 1 时，时，称为超线性收敛，称为超线性收敛，p2时称为平方收敛。时称为平方收敛。p 越大，序列收敛越快。如果是线性收敛，则越大，序列收
3、敛越快。如果是线性收敛，则 0 c 1lim,()kkkkkxxx1kpkc1(1)()()( )( )( )0,( )0kkppxxapaaaa设迭代 收敛到 ， 充分可导，则迭代 阶收敛 但 加速收敛技术：加速收敛技术：1、松弛法、松弛法选择适当的常数选择适当的常数 （松弛因子），令（松弛因子），令*111(1)()(1)kkkkkxxxxx( )( )(1)xxx1( )( )(1)01( ) 121122()()kkkkkkxxxxxx例子：求方程例子：求方程 的根的根迭代格式：迭代格式：取取 1.15，3250 xx31125kkxx*1(1)kkkxxx计算结果要求准确到小数后计算
4、结果要求准确到小数后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.0945515389
5、72266 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 endAitken加速法（适用于线性收敛情况）加速法（适用于线性收敛情况）212112()()()kkkkkkkxxxxxxx2112()2kkkkkkxxxxxx2
6、*112()2kkkkkkkxxxxxxx3、插值加速法、插值加速法由线性插值公式：由线性插值公式：1111kkkkkkkkxxxxyxxxxxx1111kkkkkkkkxxxxxxxxxxx211112kkkkkkxxxxxxx21111()2kkkkkkxxxxxxx2*1111()2kkkkkkkxxxxxxx斯特芬森迭代斯特芬森迭代（迭代两次后用（迭代两次后用Aitken加速）加速）：12121123()()2kkkkkkkkkxxxxxxxxx1001111(),()()()kkkkkkkkkkkkxzxzxxxxzxxxzxz迭代一次用插值加速，称为迭代一次用插值加速，称为插值加速
7、迭代插值加速迭代：3. 对于一般对于一般的函数方程的函数方程 f (x) = 0 的求解，解决方案为：构造的求解，解决方案为：构造等价的方程等价的方程 x = (x) ，利用迭代法求解。利用迭代法求解。这称为牛顿迭代，迭代序列收敛条件为：这称为牛顿迭代，迭代序列收敛条件为：2( ) ( )( )1( )fx f xxLfx这在函数方程这在函数方程 f (x) = 0 根根 a 的的某邻域内显然成立。某邻域内显然成立。1( )( )( )0),( )( )( )()()()kkkkkf xf xxxfxxxfxfxf xxxxfx牛顿迭代法的几何意义：牛顿迭代法的几何意义：一个例子：一个例子：牛
8、顿迭代法是局部收敛。因此，只有牛顿迭代法是局部收敛。因此，只有初值选得靠近精确解初值选得靠近精确解时，时，才能保证迭代序列收敛。才能保证迭代序列收敛。定理：设定理：设函数函数 f(x) 在区间在区间a,b上二上二阶导数存在，且：阶导数存在，且：则牛顿迭代序列收敛于则牛顿迭代序列收敛于f(x) 0 在区间在区间a,b上的唯一根。上的唯一根。00000001( ) ( )02( )0 , , 3( ) , 4 , ,() ()0f a f bfxxa bfxxa bxa bfxf x不变号， 初值利用泰勒展开容易证明，利用泰勒展开容易证明，牛顿迭代法具有二阶收牛顿迭代法具有二阶收敛性，即平方收敛。
9、收敛性，即平方收敛。收敛速度快这是牛顿迭代敛速度快这是牛顿迭代法的主要优点。法的主要优点。计算步骤（框图）：计算步骤（框图）：例子：建立求某个例子：建立求某个正实数正实数 c 的平方根的平方根的迭代格式。的迭代格式。设函数方程设函数方程 f (x) = 0 的根为的根为 ，将将 f ( ) 泰勒展开泰勒展开2( )(1)11( )()()()()()2!11()()()()!(1)!kkkkknnnnkkkkff xfxxfxxfxxfxnn( )()()()kkkff xfxx()()kkkf xxfx1()()kkkkf xxxfx改进牛顿迭代改进牛顿迭代 或或 柯西迭代柯西迭代21( )
10、()()()()()2!kkkkkff xfxxfxx21()sgn()()2 ()()()kkkkkkkkfxfxfxf xfxxxfx122 ()()sgn()()2 ()()kkkkkkkkf xxxfxfxfxf xfx设函数设函数 y = f (x) 的反函数为的反函数为 x = (y)， f (x) = 0 的根的根为为 ( )0(0)f21(0)()()(0)()(0)2!kkkkkyyyyy()()kkkkf xyxy3()1()()()()kkkkkfxyyfxfx 213()()()()2()kkkkkkkf xfxxxfxfxfx改进牛顿法：牛顿迭代法的收敛性：牛顿迭代法
11、的收敛性：牛顿迭代法二阶收敛，两种改进牛顿迭代法三阶收敛牛顿迭代法二阶收敛，两种改进牛顿迭代法三阶收敛210( )()()()()()2!kkkkkff xfxxfxx1()()kkkkf xxxfx10()()()kkkkf xfxxx21()()2()kkkkfxxxfx 12()( )limlim()2()2( )kkkkkkxfxfxfxf简化牛顿法：简化牛顿法：目的：避免计算迭代格式中的导数目的：避免计算迭代格式中的导数方法：将牛顿迭代中导数取为某个定点的值，如方法：将牛顿迭代中导数取为某个定点的值，如 ，按如下格式按如下格式 迭代迭代几何意义几何意义如图如图10()()()0)kk
12、kkf xxxfxfx()kfx0()fx进一步，取任意常数进一步，取任意常数 c 代替代替迭代公式中的导数值，迭代公式为迭代公式中的导数值，迭代公式为迭代函数为迭代函数为 ，为使迭代序列收敛，为使迭代序列收敛， c 应满足应满足这称为简化牛顿法，显然，当这称为简化牛顿法，显然，当 c 与导数同号且满足上面式子时，与导数同号且满足上面式子时，迭代收敛。迭代收敛。1()kkkf xxxc( )( )f xxxc( )( )102,fxxLcxaa本例中，本例中， c 与导数异号，迭代发散与导数异号，迭代发散弦割法：用过弦割法：用过 两个点的直线的斜两个点的直线的斜率代替函数在点率代替函数在点 处
13、函数的导数，进行迭代。处函数的导数，进行迭代。迭代公式：迭代公式：同样，此法具有局部同样，此法具有局部收敛性。其收敛是超收敛性。其收敛是超线性收敛，收敛阶为线性收敛，收敛阶为1.61811(,() , (,()kkkkxf xxf xkx111()()()()kkkkkkkf xxxxxf xf x单点弦割法：用固定点单点弦割法：用固定点 代替代替可以证明，单点法可以证明，单点法也是局部收敛的，也是局部收敛的，且收敛阶为线性收且收敛阶为线性收敛，即敛，即 1 阶收敛。阶收敛。0011(,()(,()kkxf xxf x010()()()()kkkkkf xxxxxf xf x牛顿下山法：牛顿下
14、山法：目的是解决初值的选取范围太小这以困难。目的是解决初值的选取范围太小这以困难。构造迭代格式为：构造迭代格式为：其中的参数满足：其中的参数满足：这个方法称为牛顿下山法。其中的参数称为下山因子，这个方法称为牛顿下山法。其中的参数称为下山因子，通常取通常取 ，然后逐步减半。，然后逐步减半。牛顿下山法当牛顿下山法当 时，只有线性收敛速度，但对初值的选取时，只有线性收敛速度，但对初值的选取却放的相当宽。却放的相当宽。1()()kkkkf xxxfx1()()kkf xf x30111第二节第二节 线性代数方程组迭代解法线性代数方程组迭代解法求解代数方程组求解代数方程组方法：将方程组改造为一个等价的方
15、程组方法：将方程组改造为一个等价的方程组构造迭代格式：构造迭代格式：AxbxBxgx(1)( )( )kkkxBxgx( )*(1)(0)1kkBxxxxB(1)(0)(1)lnlnBkBxx设设 为事先给定的误差精度，为事先给定的误差精度，则可以得到迭代次数：则可以得到迭代次数：定理：对于上面的迭代格式，如果定理：对于上面的迭代格式，如果B的范数小于的范数小于1，则对于任，则对于任意的初始向量与常向量意的初始向量与常向量 g ，迭代格式收敛，迭代误差估计：迭代格式收敛，迭代误差估计：2.1 雅可比迭代与高斯赛德尔迭代雅可比迭代与高斯赛德尔迭代考虑考虑n阶方程组，设系数阵非奇异，且对角元非零阶
16、方程组，设系数阵非奇异，且对角元非零将方程组变形为：将方程组变形为：11 11221121 1222221 1220nnnniinnnnnna xa xa xba xa xa xbaa xa xa xb11221331111221 123322221 12211()/()/()/nnnnnnnnnnnnnxa xa xa xbaxa xa xa xbaxa xa xaxba 任意取一组初值任意取一组初值 ，可以建立迭代格式：，可以建立迭代格式：显然，如上面的迭代收敛，则收敛向量必然为方程组的唯一解。显然，如上面的迭代收敛，则收敛向量必然为方程组的唯一解。这个迭代法称为这个迭代法称为雅可比迭代雅
17、可比迭代。雅可比迭代也称为同时（或整体）代换雅可比迭代也称为同时（或整体）代换(0)(0)(0)12(,)nxxx(1)( )( )( )11221331111(1)( )( )( )221 12332222( )( )( )(1)1 12211()/()/()/kkkknnkkkknnkkkknnnnnnnnnxa xa xa xbaxa xa xa xbaxa xa xaxba 显然，如果雅可比迭代法收敛，则将迭代格式中每一步迭代得显然，如果雅可比迭代法收敛，则将迭代格式中每一步迭代得到的迭代向量分量带入下一步迭代，则迭代效果应该更好，这到的迭代向量分量带入下一步迭代，则迭代效果应该更好，
18、这种迭代称为种迭代称为高斯赛德尔迭代高斯赛德尔迭代，（逐个代换法），（逐个代换法）雅可比迭代与高斯赛德尔迭代都称为简单迭代。雅可比迭代与高斯赛德尔迭代都称为简单迭代。(1)( )( )( )11221331111(1)(1)( )( )221 12332222(1)(1)(1)( )331 13223222(1)(1)(1)(1)1 12211()/()/()/()/kkkknnkkkknnkkkknnkkkknnnnnnnxa xa xa xbaxa xa xa xbaxa xa xa xbaxa xa xaxba nn逐个超松弛（逐个超松弛（SOR）迭代：迭代：(1)( )( )( )11
19、2213311111(1)(1)( )( )221 123322222(1)(1)(1)( )331 132232223(1)(1)1 1()/(1)()/(1)()/(1)(kkkknnkkkkknnkkkkknnkkknnnxa xa xa xbaxxa xa xa xbaxxa xa xa xbaxxa xa(1)(1)2211)/(1)kknnnnnnknxaxbax基本迭代的收敛基本迭代的收敛112233nnaaDaa211,11,212,10000nnnnn naEaaaaa121,11,2,12,1,0000nnnnnnaaaaaFa雅可比迭代的矩阵形式：雅可比迭代的矩阵形式：高
20、斯高斯赛德尔迭代的矩阵形式：赛德尔迭代的矩阵形式：超松弛（超松弛（SOR）迭代矩阵形式迭代矩阵形式：11()kkxDEF xb11111() ()kkkkkxDExFxbxDEFxb11111(1)() (1)kkkkkkxDExFxbxxDEDF xb代数方程组简单迭代法收敛的条件代数方程组简单迭代法收敛的条件定义：定义：矩阵矩阵 A 的特征值中模最大者，称为矩阵的谱半径，的特征值中模最大者，称为矩阵的谱半径，矩矩阵阵 A 的谱半径记为的谱半径记为 ( A )定理：简单迭代定理：简单迭代 收敛的充分收敛的充分必要条件是必要条件是 或矩阵或矩阵 B 的谱半径的谱半径 ( B ) 11( )ma
21、xii nA (1)( )( )kkkxBxgx0()kBk推论推论1：如果迭代矩阵的范数小于：如果迭代矩阵的范数小于1，则简单迭代收敛。，则简单迭代收敛。推论推论2：逐次超松弛迭代法收敛的一个条件是：逐次超松弛迭代法收敛的一个条件是 0 2推论推论3：A严格对角占优时，雅可比迭代、严格对角占优时，雅可比迭代、0 1 的的SOR法法都收敛。都收敛。推论推论4：A对称正定时，雅可比迭代法收敛的充要条件是对称正定时，雅可比迭代法收敛的充要条件是 2D A 对称正定，对称正定，SOR收敛的充要条件是收敛的充要条件是0 21、A严格对角占优，则雅可比、高斯赛德尔迭代都收敛。严格对角占优，则雅可比、高斯
22、赛德尔迭代都收敛。2、如、如 A 对称正定，则高斯赛德尔迭代收敛。对称正定，则高斯赛德尔迭代收敛。3、如果、如果 A 对称正定，对称正定，D 为为 A 的对角线上的元组成的矩阵，如的对角线上的元组成的矩阵，如 2DA也对称正定，则雅可比迭代收敛；如也对称正定，则雅可比迭代收敛；如A对称正定而对称正定而 2DA 非正定，则雅可比迭代不收敛。非正定，则雅可比迭代不收敛。第三节第三节 非线性方程组的迭代解法非线性方程组的迭代解法3.1 一般迭代。一般迭代。 设有非线性方程组设有非线性方程组 11221212(,)0(,)0(,)0nnnnf x xxfx xxfx xx1122( )( )( )0
23、, ( )( )nnxf xxfxf xxf xxfx或写为， 其中 1112221212( ,)( ,)( ,)nnnnnxx xxxx xxxx xx(1)( )( )( )1112(1)( )( )( )2212(1)( )( )( )12(,)(,)(,)kkkknkkkknkkkknnnxxxxxxxxxxxx或将方程组改写为下式，将方程组改写为下式，可得可得Jacobi型迭代格式型迭代格式12( )( )( ),( )( )nxxxxxx或其中1()kkxx11112222121( )nnnnnnnxxxxxxxxxx( )()xLx 记记，称为() 关于 x 的Frechet导数
24、。定理定理：若( )x满足：1、存在凸闭区域，使得2、存在正常数1L ，使得，则在在惟一的不动点 x*，并且迭代序列10 ()kkkxxxx，收敛于 x*，而且有上述关于方程式迭代一样的误差估计。注：上述矩阵的范数可取注：上述矩阵的范数可取1范数、范数、2范数、无穷范数等。范数、无穷范数等。存例子：例子：112212140.111408xxxexxx( )1(1)( )12(0)(1)( )( )22111(10.1)4(0,0)11() 48kxkkkkkxxexxxx 2.249999996274710E-001 0.000000000000000E+000 2.1869193164034
25、00E-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.64522314432981
26、0E-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-002x=0.0y=0.010 x1=x
27、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类似的可以得到高斯赛德尔型迭代：类似的可以得到高斯赛德尔型迭代：(1)( )( )( )( )11123(1)(1)( )( )( )22123(1)(1)(1)( )( )33123(1)(1)(1)(1)( )( )121(1)(1)(1)12(,)(,)(,)(,)(,kkkkknkkkkknkkkkknkkkk
28、kkiiiinkkknnnxxxxxxxxxxxxxxxxxxxxxxxxx(1)( )1,)kknx( )1(1)( )12(0)(1)(1)(1)22111(10.1)4(0,0)11() 48kxkkkkkxxexxxx 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.
29、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 end3.2 牛顿迭代牛顿迭代对非线性代数方程组( )0f x ，若( )kx是其根的一个近似，因为( )( )(
30、)( )( )( )( )( )( )1( )( )()()()()0()()()()()kkkkkkkkkkff xfxxoxf xfxxxfxf x(1)( )( )1( )( ()()kkkkxxf xf x令，就得到非线性代数方程组的Newton迭代格式。因为( )( )(1)( )()()()0kkkkf xfxxx令( )(1)( )kkkxxx，则得到( )kx满足的线性代数方程组，解出即得(1)( )( )kkkxxx 或解或解( )kix( )( )( )( )( )( )( )1121121( )( )( )( )( )( )( )2122121( )( )( )( )(
31、)( )( )12121(,)(,)(,)(,)(,)(,)kkknkkkkniniikkknkkkkniniikkknkkkknninniif xxxxf xxxxfxxxxfxxxxfxxxxfxxxx (1)( )( )(1,2, )kkkiiixxxin于是可以得到迭代格式：于是可以得到迭代格式：( )(1,2, )kixin满足的方程组满足的方程组简化牛顿法简化牛顿法。目的是避免计算迭代公式中繁杂的导数，解决方。目的是避免计算迭代公式中繁杂的导数，解决方法与一元函数牛顿法类似，即将所有导数取为固定值，如法与一元函数牛顿法类似，即将所有导数取为固定值，如迭代初值的导数值。迭代初值的导数
32、值。(0)(0)(0)( )( )( )( )1121121(0)(0)(0)( )( )( )( )2122121(0)(0)(0)( )( )( )( )12121(,)(,)0(,)(,)0(,)(,)0nkkkknniiinkkkknniiinkkkknnnniiif xxxf xxxxxfxxxfxxxxxfxxxfxxxxx(1)( )( )(1,2, )kkkiiixxxin(1)( )(0)1( )()()kkkxxfxf x与单个方程的情形类似，牛顿法中 f 的导数的元素用合适的差商来近似，如就可得到拟牛顿法或弦截法。拟牛顿法或弦截法。( )( )( )12( )( )( )
33、( )( )( )11( )( )( )( )(1)( )11( )(1)(,)(,)(,)2(,)(,)kkkjnikkkkkkjiinjiinikkkkkkjinjinkkiifxxxxfxxhxfxxhxhfxxxfxxxxx或若用格式(1)( )( )1( )( ()()kkkkkxxf xf x其中下山因子(0,1k合适地选取使得(1)( )()()kkf xf x就得到牛顿下山法。若用格式1(1)( )( )()kkkkxxA f x，其中kA是1kA的简单修正，且满足( )(1)( )(1)()()()kkkkkA xxf xf x则得到Broyden算法。特别，若取1TkkAA
34、uv，其中u,v 是待定的列向量，使其满足上式，则得到秩一Broyden算法。比如( )(1)( )(1)11()(,()()TkkkkkkkTyAs sAAsxxyf xf xs s其中小结小结 1、本章的目的是求解形如、本章的目的是求解形如 f (x)=0 的方程，而其核心方法是的方程，而其核心方法是将所要求解的方程变形为将所要求解的方程变形为 x = (x)，利用利用 (x) 为压缩映射，为压缩映射，通过迭代求出其解。通过迭代求出其解。2、变形中切记要恒等变形！、变形中切记要恒等变形！3、在恒等变形中，为使变形得到的函数、在恒等变形中，为使变形得到的函数 (x) 为压缩映射，一为压缩映射，一个技巧是利用待定参数。个技巧是利用待定参数。4、恒等变形的一种重要格式是牛顿迭代，证明其迭代收敛阶、恒等变形的一种重要格式是牛顿迭代，证明其迭代收敛阶的一个常用技巧是泰勒展开。的一个常用技巧是泰勒展开。5、n维空间中代数方程迭代求解的收敛条件是谱半径小于维空间中代数方程迭代求解的收敛条件是谱半径小于 1 .
