不动点迭代法及其收敛定理课件.ppt

1、 6.2 不动点迭代法及其收敛定理 第第6章章 方程与方程组的迭代解法方程与方程组的迭代解法一、迭代法原理-(2)将非线性方程 f(x)=0 化为一个同解方程)(xx为连续函数并且假设)(x得的右端代入任取一个初值,)2(,0 x)(01xx)(12xx)(1kkxx继续-(3),2,1,0(k称(3)式为求解非线性方程(2)的简单迭代法(),kxxk 称称为为迭迭代代函函数数 称称为为第第 步步迭迭代代值值*,kxx如如果果存存在在一一点点使使得得迭迭代代序序列列满满足足*limxxkk则称迭代法则称迭代法(3)收敛收敛,否则称为发散否则称为发散-(4)例1.0123 xx用迭代法求解方程解

2、:123xx(1)将原方程化为等价方程得由迭代法如果取初值),3(,00 x12301xx112312xx312323xx5500 x显然迭代法发散321xx(2)如果将原方程化为等价方程00 x30121xx仍取初值3217937.031221xx327937.19644.0 x2=0.9644x3=0.9940 x4=0.9990 x5=0.9998x6=1.0000 x7=1.0000依此类推,得已经收敛,故原方程的解为0000.1x同样的方程不同的迭代格式有不同的结果什么形式的迭代法 能够收敛呢?迭代函数的构造有关012*xxxxO)(xyxy 0231*xxxxxO)(xyxy 如果

3、将(2)式表示为)(xyxy 与方程(2)同解收敛附近较平缓在*)(xx*012xxxxO)(xyxy 2013*xxxxxO)(xyxy 发散附近较陡峭在*)(xx定理1.(),xa b 设设迭迭代代函函数数在在上上连连续续 且且满满足足(1),();xa baxb 当当时时(2),01,LLxa b 存存在在一一正正数数满满足足且且有有Lx|)(|1.(),*oxxa bx 则则方方程程在在内内有有唯唯一一解解012.,()*okkxa bxxx 对对于于任任意意初初值值迭迭代代法法均均收收敛敛于于13.*1okkkLxxxxL 104.*1kokLxxxxL -(5)-(6)-(7)(局

4、部收敛性)迭代过程的收敛性迭代过程的收敛性证:由条件(1),()(xxxf设)()(aaaf0)()(bbbf0上连续可导在则,)(baxf由根的存在定理,上至少有一个根在方程,0)(baxf证:1|)(|Lx由)(1)(xxf0,)(上单调递增在则baxf上仅有一个根在,0)(baxf*,)(.1xbaxxo内有唯一解在方程所以),(.21kkoxx对于迭代法*1xxk*)()(xxk*)(xxk由微分中值定理kkxx1)()(1kkxx)(1kkxxkkxx11kkxxLLx|)(|由于*1xxk*xxLkkkxx11kkxxL)(*11kkkxxxxL)(*11kkkxxLxxLkkkx

5、xLLxx111*11*kkkxxLLxx2121kkxxLL011xxLLk,1L由于*)(limxxkk0*)(,10 xxxxkk均收敛于迭代法因此对任意初值11*kkkxxLLxx011xxLLk证毕.定理1指出,|()|1xL只要构造的迭代函数满足就收敛迭代法)(1kkxx11kkxxLL由(6)式,只要因此,当LLxxkk11迭代就可以终止,可以作为方程的近似解kx对于预先给定的误差限|*|xxk即要求-(8)定义定义1：如果存在 的某个邻域 ，使迭代过程 对于任意初值 均收敛，则称迭代过程 在根 邻近具有局部收敛性。*x*:xxR)(1kkxxRx 0)(1kkxx*x*1,0|

6、()|1,(2).kkxxxxxx若 是 的不动点在 的某邻域上存在若 是 的不动点在 的某邻域上存在且连续 并满足则迭代过程且连续 并满足则迭代过程 在 的邻域是线性 在 的邻域是线性理理收敛的收敛的定定例2.用迭代法求方程的近似解,精确到小数点后6位0210 xex解:,0 xe由于0102x则2.0 x,0时x,10 xe2102x本题迭代函数有两种构造形式102)(1xexx)102ln()(2xxx|)(|1x10 xe|)(|2xx102101102.0e102)(1xexx因此采用迭代函数为有根区间因此2.0,05由于00 x取初值10201xex1.0d1=0.1000000d

7、2=-0.0105171d3=0.1156e-002d4=-0.1265e-003d5=0.1390e-004d6=-0.1500e-005d7=0.1000e-006由于|d7|=0.1000e-0061),则利用m构造新的迭代公式:此时,至少2阶收敛.不实用:m往往不确定.方法二方法二.取 ,再对函数F(x)用Newton迭代:此时,X*为F(x)的单根,所以是2阶收敛.但要用到二阶导数.1()()kkkkf xxxmfx()*()(),()0f xfxxxmx()()()f xF xfx12()()()()()()()kkkkkkkkkkF xf xfxxxxF xfxf xfx)()(

8、1kkkkxfxfxxNewtonNewton迭代法迭代法需要求每个迭代点处的导数需要求每个迭代点处的导数 f(xk)复杂！复杂！得中的近似替代用,)(0kkxxfx)()(01xfxfxxkkk这种格式称为这种格式称为简化简化NewtonNewton迭代法迭代法精度稍低精度稍低则则NewtonNewton迭代法变为迭代法变为)()()()(111kkkkkkkxxxfxfxfxx这种格式称为这种格式称为弦截法弦截法收敛阶约为收敛阶约为1.6181.618)(kxf 如果用数值导数代替11)()()(kkkkkxxxfxfxf用简化用简化Newton法和弦截法解下面方程的根，并和法和弦截法解下

9、面方程的根，并和Newton 迭代法比较迭代法比较0133xx13)(3xxxf设33)(2xxf由简化由简化Newton法法)()(01xfxfxxkkk3313203xxxxkkk由弦截法由弦截法)()()()(111kkkkkkkxxxfxfxfxx由由Newton迭代法迭代法)()(1kkkkxfxfxx331323kkkkxxxxx0=0.5x1=0.3333333333x2=0.3497942387x3=0.3468683325x4=0.3473702799x5=0.3472836048x6=0.3472985550 x7=0.3472959759x8=0.3472964208x9

10、=0.3472963440 x10=0.3472963572x11=0.3472963553x0=0.5;x1=0.4;x2=0.3430962343x3=0.3473897274x4=0.3472965093x5=0.3472963553x6=0.3472963553简化简化Newton法法由弦截法由弦截法要达到精度要达到精度10-8 简化简化Newton法迭代法迭代11次次弦截法迭代弦截法迭代5次次Newton迭代法迭代迭代法迭代4次次x0=0.5;x1=0.3333333333x2=0.3472222222x3=0.3472963532x4=0.3472963553由由Newton迭代法

11、迭代法无论哪种迭代法：无论哪种迭代法：NewtonNewton迭代法迭代法简化简化NewtonNewton法法弦截法弦截法00 *x,)xarctan()x(f精精确确解解用用NewtonNewton迭代法求解迭代法求解:)1(arctan21kkkkxxxxx0=2x1=-3.54x2=13.95x3=-279.34x4=122017是否收敛均与初值的位置有关是否收敛均与初值的位置有关.20 x若若取取初初值值x0=1x1=-0.5708x2=0.1169x3=-0.0011x4=7.963110-10 x5=0收敛收敛发散发散10 x若若取取初初值值牛顿下山法牛顿下山法 一般地说，牛顿法的

12、收敛性依赖于初值 的选取，如果 偏离 较远，则牛顿法可能发散。为了防止发散，通常对迭代过程再附加一项要求，即保证函数值单调下降：满足这项要求的算法称为下山法下山法。牛顿下山法牛顿下山法采用以下迭代公式：其中 称为下山因子。1kkf xf x011kkkkf xxxfx0 x0 x*x牛顿下山法只有线性收敛牛顿下山法只有线性收敛.的选取方式的顺序，按322121211成立为止直到|)(|)(|1kkxfxf例7.30()0,0.993xf xxx 求解方程取初值5110|nnxx解:1.先用Newton迭代法1)(2xxf)()(1kkkkxfxfxx)1(3323kkkkxxxx)1(3320

13、03001xxxxx50598.32)1(332113112xxxxx69118.2115689.15x4=9.70724 x5=6.54091 x6=4.46497 x7=3.13384 x8=2.32607 x9=1.90230 x10=1.75248x11=1.73240 x12=1.73205x13=1.73205)1(332223223xxxxx迭代13次才达到精度要求2.用Newton下山法,结果如下k=0 x0=-0.99 fx0=0.666567k=1 x1=32.505829 f(x)=11416.4 w=0.5 x1=15.757915 f(x)=1288.5 w=0.25

14、 x1=7.383958 f(x)=126.8 w=0.125 x1=3.196979 f(x)=7.69 w=0.0625 x1=1.103489 f(x)=-0.655k=2 x2=4.115071 f(x)=19.1 w=0.5 x2=2.60928 f(x)=3.31 w=0.25 x2=1.85638 f(x)=0.27k=3 x3=1.74352 f(x)=0.023k=4 x4=1.73216 f(x)=0.00024k=5 x5=1.73205 f(x)=0.00000k=6 x6=1.73205 f(x)=0.000000)(kkxfxk下山因子0有重根在区间,0)(.2ba

15、xf2*,0)(mxmbaxf重根有在区间)(*)()(xgxxxfm因此可令0*)(xg且*)(xf*)(xf*)()1(xfm*)(xf 故有0*)()(xfm且由例3.)()(1kkkkxfxfxx对于Newton迭代法趋于零,0)(kxf即使Newton迭代法也只是线性收敛此时Newton迭代法可能不收敛由定理2，迭代法)()(1kkkkxfxfmxx至少是二阶收敛Steffensen方法 第第6章章 方程与方程组的迭代解法方程与方程组的迭代解法 简单迭代公式的加速简单迭代公式的加速 设 是根 的某个近似值，用迭代公式校正一次得假设 ，则有据此可导出如下加速公式：其一步分为两个环节：迭

16、代:改进:kx*x1kxq1kkxx*1kkxxq xx11111kkkqxxxqq1kkxx11111()111kkkkkkqqxxxxxxqqq11111()()()1nnnnnnnxxxxxxxqqq：迭代次数大大减少，总的计算工作量减少，但涉及导数值的计简单算不迭代便于法的实加速方案际应用。埃特金迭代法求方程的实根2221221121()2()2kkkkkkkkkkkkkxxxxAitkenxxxxxxxxx：加速方案:避免了导数值的计算，但需要简用单迭代法加两次迭代值速方进案的改进行计算。定理定理 设序列 线性收敛于x*,则 的Aitken序列 存在,且 即 比 更快收敛于x*.kx

17、*0,0,kkkexx 且1limkkkece(0|1)c kx kxkx*lim0kkkxxxxkx222112*121212121*2*221:limlim()2()2(1)(1)1102121kkkkkkkkkkkkkkkkkkkkkkkkkkkkkkeeeceeexxxxxxxxxeeeeeeexxceeexxccee 证明首先其次所以SteffensenSteffensen迭代迭代在Aitken加速法中,只要有三个相邻的点就可以进行家速,即对任意线性收敛序列 构建的.现将其与不 动点迭代 方法结合起来:迭代函数 迭代初始值 迭代序列kx21()()()20,1,kkkkkkkkkkkyxzySteffensenyxxxzyxk迭代)(1kkxxkx0 x()x或写成不动点迭代形式1(),kkxx即21()()2()0,1,kkkkkkkxxxxxxxk