元方程的不动点迭代法市公开课一等奖百校联赛特等奖课件.pptx

第六章非线性方程组的迭代解法 6.2 一元方程不动点迭代法一元方程不动点迭代法6.2.2 局部收敛性和加速收敛法局部收敛性和加速收敛法6.2.1 不动点迭代法及其收敛性不动点迭代法及其收敛性第1页第六章非线性方程组的迭代解法 6.2.1 不动点迭代法及其收敛性不动点迭代法及其收敛性（6.2.1）实根，先将它转化成等价形式实根，先将它转化成等价形式（6.2.2）（6.2.3）第2页第六章非线性方程组的迭代解法 第3页第六章非线性方程组的迭代解法 把（6.2.1）转换成等价形式（6.2.2）方法很多，迭代函数不一样选择对应不一样迭代法，它们收敛性可能有很大差异。当方程有多个解时，同一迭代法不一样初值，也可能收敛到不一样根。举例说明以下。第4页第六章非线性方程组的迭代解法 例6.2解解 对应迭代法分别为对应迭代法分别为第5页第六章非线性方程组的迭代解法 表表 6-2012111.51.51.357208812.375000001.3308609612.39648441.324717961133-+kkxxk例例 6.3解解第6页第六章非线性方程组的迭代解法 对应迭代法为表表6-311.41421356-1.414213561.41421356-1.414213561.41421569-1.414215691.416666671.416666671.5-1.51-154320第7页第六章非线性方程组的迭代解法 定理定理6.1(6.2.4)第8页第六章非线性方程组的迭代解法 则对方程（则对方程（6.2.2）有）有（6.2.5）证证 第9页第六章非线性方程组的迭代解法 显然有第10页第六章非线性方程组的迭代解法 第11页第六章非线性方程组的迭代解法（6.2.6）第12页第六章非线性方程组的迭代解法 由预计式（由预计式（6.2.5）可知，只要相邻两次计算结果偏差）可知，只要相邻两次计算结果偏差 足够小，且足够小，且 不很靠近不很靠近1，既可确保近似值，既可确保近似值 含有足够精度。因含有足够精度。因 此，能够经过检验此，能够经过检验 大小来判断迭代过程是否终止。并大小来判断迭代过程是否终止。并 且，由（且，由（6.2.5）有）有（6.2.7）第13页第六章非线性方程组的迭代解法 第14页第六章非线性方程组的迭代解法 有时，对于一些不满足定理有时，对于一些不满足定理6.1条件问题，能够经条件问题，能够经过转化，化为适合于迭代形式。这要针对详细情况进行过转化，化为适合于迭代形式。这要针对详细情况进行讨论讨论。第15页第六章非线性方程组的迭代解法 第16页第六章非线性方程组的迭代解法 6.2.2 局部收敛性和加速收敛法局部收敛性和加速收敛法第17页第六章非线性方程组的迭代解法 定理定理 6.2上述定理称为局部收敛定理，它给出了局部收敛一个上述定理称为局部收敛定理，它给出了局部收敛一个第18页第六章非线性方程组的迭代解法 充分条件。当迭代收敛时，收敛快慢用下述收敛阶段来衡量。充分条件。当迭代收敛时，收敛快慢用下述收敛阶段来衡量。定义定义6.2（6.2.8）第19页第六章非线性方程组的迭代解法 对对 ，必有，必有 ,k=1,2,，而且，而且其中在其中在 与与 之间。于是之间。于是 从而，在这种情况下，从而，在这种情况下，x k 是线性收敛。可见，提升收敛阶是线性收敛。可见，提升收敛阶一个路径是选择迭代函数一个路径是选择迭代函数 ，使它足，使它足 。下面给。下面给出整数阶超线形收敛一个充分条件。出整数阶超线形收敛一个充分条件。定理定理6.3 设设 是是 一个不动点，若有正整数一个不动点，若有正整数p 2,使得使得 在在 领域上连续，而且满足领域上连续，而且满足第20页第六章非线性方程组的迭代解法 则由迭代法生成序列在领域是则由迭代法生成序列在领域是p阶收敛，且有阶收敛，且有证证 因因 ，由定理，由定理6.2知迭代法知迭代法(6.2.3)是局部收敛。是局部收敛。取充分靠近取充分靠近 ,设设 有有 ，k=1,2,。由。由Taylor展开式有展开式有其中其中 在在 与与 之间。由之间。由(6.2.9)有有第21页第六章非线性方程组的迭代解法 由由 连续性可得连续性可得(6.2.10)。定理得证。定理得证。对于线形收敛迭代法，经常收敛很慢，所以要在这些迭代对于线形收敛迭代法，经常收敛很慢，所以要在这些迭代法基础上考虑加速收敛方法。法基础上考虑加速收敛方法。设所以，当所以，当k充分大时有充分大时有第22页第六章非线性方程组的迭代解法 从中解出从中解出 得得所以，我们在计算了所以，我们在计算了 之后，之后，能够用能够用上式右端作为一个修正值。这么，我们可将迭代法改造成上式右端作为一个修正值。这么，我们可将迭代法改造成下述过程，称为下述过程，称为Steffensen迭代法迭代法：第23页第六章非线性方程组的迭代解法 K 0 1 28 29Xk 0.5 0.606530660 0.567143282 0.567143295表表64例例6.6 求方程根。求方程根。解解 此方程等价于此方程等价于 。由。由y=x和和 能够看出能够看出 ，只有一个不动点只有一个不动点x*0,都有都有 ,所以迭代法所以迭代法 线性收敛。取初始值线性收敛。取初始值 =0.5，迭代结果列于表，迭代结果列于表64。准确解是。准确解是=0.56714329040978，可见线性收敛速度是很慢。，可见线性收敛速度是很慢。第24页第六章非线性方程组的迭代解法 假如使用假如使用Steffensen迭代法，仍取初值迭代法，仍取初值x0=0.5.则则计算结果列于表计算结果列于表65。与表。与表64比较，可见比较，可见Steffensen迭代法比迭代法比原方法收敛快得多，仅迭代原方法收敛快得多，仅迭代4次就到达了原方法次就到达了原方法29次结果。次结果。K 0 1 2 3 4 Xk 0.5 0.567623876 0.567143314 0.567143290 0.567143290表表65定理定理6.4 设函数按（设函数按（6.2.13）定义。）定义。第25页第六章非线性方程组的迭代解法 （1）若）若x*是是 不动点，不动点，在在x*处连续，且处连续，且 ，则，则x*也是不动点；反之，若也是不动点；反之，若x*是是 不动点，则不动点，则x*也是也是 不动点。不动点。（2）若）若x*是是 不动点，不动点，在在x*处连续，且处连续，且 ,则则Steffensen迭代法迭代法(6.2.11）最少含有二阶局部收敛性。）最少含有二阶局部收敛性。证证（1）若）若x*=，则当，则当x=x*时，（时，（6.2.13）式分子分母）式分子分母都为零。对它极限用都为零。对它极限用LHospitale法则，因为法则，因为 ，得，得知知从而从而 。反之，若。反之，若 ，则由（，则由（6.2.13）得）得 知知 。第26页第六章非线性方程组的迭代解法 于是，由 对（6.2.14）两边求极限，因为x*最少是 p(x)和q(x)二重根，所以，使用两次LHospitale法则得 其中（2）由（1）可知x*是 不动点，于是，由定理6.3，只要证实 。对（6.2.13）两边求导得第27页第六章非线性方程组的迭代解法 可见，在定理6.4条件下，不论原迭代法 收敛还是不收敛，由它组成Steffensen迭代式（6.2.11）最少平方收敛。所以，Steffensen迭代法是对原迭代法一种改进。关于原迭代法不收敛情形，举比如下。例6.7 用Steffensen迭代法求方程 实根。解解 由例由例6.4可知，迭代法可知，迭代法 发散。现用发散。现用 结结构构Steffensen迭代法。迭代法。第28页第六章非线性方程组的迭代解法 表表66K 0 1 5 6 Xk 1.5 1.41629297 1.32471799 1.32471796仍取初值仍取初值 =1.5,计算结果如表计算结果如表66。可见，。可见，Steffensen迭迭代法对这种不收敛情形一样有效代法对这种不收敛情形一样有效。第29页