一元方程的不动点迭代法

1、第六章非线性方程组的迭代解法 6.2 一元方程的不动点迭代法一元方程的不动点迭代法6.2.2 局部收敛性和加速收敛法局部收敛性和加速收敛法6.2.1 不动点迭代法及其收敛性不动点迭代法及其收敛性第六章非线性方程组的迭代解法 6.2.1 不动点迭代法及其收敛性不动点迭代法及其收敛性非线性方程是连续的，为了求一元设一元函数)(xf0)(xf（6.2.1）的实根，先将它转化成等价形式的实根，先将它转化成等价形式),(kxx（6.2.2）构造迭代公式是一个连续函数。然后其中)(x。,.1 ,0),(1kxxkk（6.2.3）第六章非线性方程组的迭代解法 ）的根。也是方程（按等价性，），从而满足方程（既

2、则有有极限，若由此迭代生成的序列对于给定的初值1 . 2 . 62 . 2 . 6),(,lim,*0 xxxxxxxxkkk,)(3 . 2 . 6称为迭代函数）称为基本迭代法，迭代式（x单步法。决定，因此，这是一种仅由迭代过程中，。）也称为不动点迭代法的不动点，式（称为kkxxxx1*3 . 2 . 6)(第六章非线性方程组的迭代解法 把（6.2.1）转换成等价形式（6.2.2）的方法很多，迭代函数的不同选择对应不同的迭代法，它们的收敛性可能有很大的差异。当方程有多个解时，同一迭代法的不同初值，也可能收敛到不同的根。举例说明如下。第六章非线性方程组的迭代解法 的一个实根。求01)(3xxx

3、f例6.2解解 转换成两种等价形式把0)(xf, 1)(, 1)(3231xxxxxx对应的迭代法分别为对应的迭代法分别为。,.1 , 0, 1, 13131kxxxxkkk。敛，第二个迭代法发散。显然第一个迭代法收。此方程有唯一实根迭代结果列于表点为初值，既令为有根区间。取它的中，从而内变号，在区间既连续函数由于57244753247179. 126, 5 . 121 21 )(, 5)2(, 1) 1 (*0 xxxfff第六章非线性方程组的迭代解法 表表 6-2012111.51.51.357208812.375000001.3308609612.39648441.32471796113

4、3kkxxk例例 6.3的根。求02)(2 xxf解解转换成等价形式把0)(xf),2(21)(xxxx第六章非线性方程组的迭代解法 对应的迭代法为。,.1 , 0),2(211kxxxkkk所示。果如表计算结迭代结果分别收敛到取初值36,2, 1*0 xx表表6-311.41421356-1.414213561.41421356-1.414213561.41421569-1.414215691.416666671.416666671.5-1.51-154320kkxxk第六章非线性方程组的迭代解法 上连续，并且满足在闭区间设函数,)(bax定理定理6.1 ;,)(,) 1 (baxbax，有

5、对任意有。使对任意存在正数, 1)2(bayxL。yxLyx)()(6.2.4)函数的收敛性质取决于迭代由此可见，基本迭代法基本定理。的收敛性法的选取。下面给出迭代和初值)3 . 2 . 6()(0 xx第六章非线性方程组的迭代解法 则对方程（则对方程（6.2.2）有）有。上存在唯一的不动点在闭区间函数*,)() 1 (xbax）生成的序列由迭代法（对于任何初值3 . 2 . 6,)2(0bax 。收敛到不动点*xxk有误差估计式) 3(。1*1kkkxxLLxx（6.2.5）证证 )(, 0)(,)()()(babaxxxx知，则由令则有上有两个相异的不动点在。若上有不动点在上有零点，既是连

6、续函数，故它在。因为,)(,)(,)(0*2*1*xxbaxxbaxbax第六章非线性方程组的迭代解法 进而显然有,.,1 , 0,kbaxk。*0*1*1*)()(xxLxxLxxxxkkkk。既从而*lim, 0limxxxkkk显然有，111)()(kkkkkkxxLxxxx上只有一个不动点。在这是个矛盾式子，因此,)(bax*12121212()(),xxxxL xxxx第六章非线性方程组的迭代解法 ,p进而 对任意的正整数 ，同理可得kkkkpkpkkpkxxxxxxxx1121。kkpxxLL11) 1(,1)1 (10101pkkLLLLL，从而因为。11111kkkkkpkxx

7、LLxxLxx定理得证。由收敛性既得令),5 . 2 . 6(,p第六章非线性方程组的迭代解法 中的）内可导，那么定理在区间（如果函数1 . 6,)(bax）可用更强的条件条件（2),(, 1)( baxLx（6.2.6）理，对任何成立，则由微分中值定代替。事实上，若上式都有,bayx),()( )()(yxLyxyx）成立。之间，从而条件（与在其中4 . 2 . 6yx第六章非线性方程组的迭代解法 由估计式（由估计式（6.2.5）可知，只要相邻两次计算结果的偏差）可知，只要相邻两次计算结果的偏差 足够小，且足够小，且 不很接近不很接近1，既可保证近似值，既可保证近似值 具有足够的精度。因具有

8、足够的精度。因 此，可以通过检查此，可以通过检查 的大小来判断迭代过程是否终止。并的大小来判断迭代过程是否终止。并 且，由（且，由（6.2.5）有）有1kkxx1kkxxkxL。01*1xxLLxxKk（6.2.7）的次数。的精度确定出需要迭代），我们可对给定的值，则由（如果能恰当计算出7 . 2 . 6L)(,)(*xyxyxx 与曲线在几何上是直线的不动点函数是发散的情形。图）是收敛的情形其中图（所示，的几何解释如图，定理的交点的横坐标。因此)(,262 . 6ba第六章非线性方程组的迭代解法 4 . 6例们的收敛性。的两种迭代法，讨论它对于例 2 . 6解。其导数对于迭代函数32131)

9、 1(31)(, 1)(xxxxa1x*x0 xabybxxy )(xy)(a1x*x0 xabybxxy )(xy)(b26 图aa第六章非线性方程组的迭代解法 有容易验证，对任意2 , 1 x。121. 0)(,2 , 1 45. 1 ,26. 1 )(11xx。上的唯一不动点，都收敛到区间给出的迭代法由因此，对于任何初值*1021 )(,2 , 1 xxx。显然，其导数对于迭代函数22323)(, 1)(xxxx该迭代法发散。要初值从几何上可以说明，只的条件。不满足定理，有对,1 . 6, 1)(70)(2 , 1 *022xxxxx 有时，对于一些不满足定理有时，对于一些不满足定理6.

10、1的条件问题，可以的条件问题，可以通过转化，化为适合于迭代的形式。这要针对具体情通过转化，化为适合于迭代的形式。这要针对具体情况进行讨论况进行讨论。第六章非线性方程组的迭代解法 5 .6例试问如何满足的已知, 13)( )( )(xxxx代函数？构造一个收敛的简单迭利用)(x解，可得由)(xx,3)(3xxxx即可得等价方程。)(3(21xxx因此，令)(3(21)(xxx则有,21)( 321)(xx)(1kkxx因此，迭代式收敛。), 1 , 0(k第六章非线性方程组的迭代解法 6.2.2 局部收敛性和加速收敛法局部收敛性和加速收敛法上的收讨论的是迭代法在区间由于定理,16. ba，给出如

11、下定义。近的收敛性问题。为此附根检验。所以常常讨论在全局收敛性的情形不易说来，上收敛的情形。但一般敛性也包括在无穷区间局收为全局收敛性定理。全敛性，因而，可以称之*x6.1定义的一个邻域的不动点，若存在是设*)(xxx 收敛的。）是局部，则称迭代法（且收敛到）生成的序列满足），有迭代法（，（使得对任何初值3 .2 .6),(3 .6.2, 0,),(*0*xxsxxsxxxxsk第六章非线性方程组的迭代解法 定理定理 6.2的某个邻域在的一个不动点，是设*)( )(xxxx）局部收敛。则迭代法（上连续，并且有3 . 2 . 6, 1)( *x证所以存在处连续，且在因为, 1)( )( *xxx

12、并且有在其上的一个闭邻域, 1)( ,*Lxxxx,)()()(*xxLxxxx 收敛。定理得证。）迭代法（，对任意根据定理。，有即对一切3 . 2 . 6,1 . 6,*0*xxxxxxxxx上述定理称为局部收敛定理，它给出了局部收敛的一个上述定理称为局部收敛定理，它给出了局部收敛的一个第六章非线性方程组的迭代解法 充分条件。当迭代收敛时，收敛的快慢用下述收敛阶段来充分条件。当迭代收敛时，收敛的快慢用下述收敛阶段来衡量。衡量。若存记误差收敛到设序列*,xxexxkkk定义定义6.2，使得和在实数01cpceepkkk1lim（6.2.8）方收敛。时，称为平当时，称为超线性收敛。敛。当时，称为

13、线性收阶收敛的，当是则称序列211ppppxk阶无穷小量的是时，）表明，当式（peekkk 18 . 2 . 6。）中的常数满足（是线性收敛的，越大，收敛越快。如果因此，阶数108 .2 .6 cp则满足即中，还有如果在定理, 1)( 0)( , 0)( 2 . 6*xxx第六章非线性方程组的迭代解法 对对 ，必有，必有 ,k=1,2,，而且，而且*0 xx*xxkkkkkkexxxxe)()()(*11其中在其中在 与与 之间。于是之间。于是k*x。0)()(limlim*1xeekkkkk 从而，在这种情况下，从而，在这种情况下，x k 是线性收敛的。可见，提高收敛是线性收敛的。可见，提高

14、收敛阶的一个途径是选择迭代函数阶的一个途径是选择迭代函数 ，使它足，使它足 。下。下面给出整数阶超线形收敛的一个充分条件。面给出整数阶超线形收敛的一个充分条件。)(x0)(*x定理定理6.3 设设 是是 的一个不动点，若有正整数的一个不动点，若有正整数p 2,使得使得 在在 的领域上连续，并且满足的领域上连续，并且满足*x)(x)(xp*x, 0*)(, 0)()()()(*) 1(* *xxxxpp第六章非线性方程组的迭代解法 则由迭代法生成的序列在的领域是则由迭代法生成的序列在的领域是p阶收敛的，且有阶收敛的，且有!)(*)(1limpxeepkkk证证 因因 ，由定理，由定理6.2知迭代

15、法知迭代法(6.2.3)是局部收敛的。是局部收敛的。取充分接近取充分接近 的的 , 设设 有有 ， k=1,2,。由。由Taylor展开式有展开式有0)(*x*x0 x*0 xx*xxk,)(!)()()!1()()()()(*)(1*1*1pkkppkpkkkxxpxxpxxxxxxx其中其中 在在 与与 之间。由之间。由(6.2.9)有有kxk*x第六章非线性方程组的迭代解法 ).(!(*1)(*1xxpxxkkpk由由 的连续性可得的连续性可得(6.2.10)。定理得证。定理得证。)(xp 对于线形收敛的迭代法，常常收敛的很慢，所以要在这些对于线形收敛的迭代法，常常收敛的很慢，所以要在这

16、些迭代法的基础上考虑加速收敛的方法。迭代法的基础上考虑加速收敛的方法。*,xxexxkkk满足则迭代误差线性收敛到设.0*11limlimcxxxxeekkkkkk因此，当因此，当k充分大时有充分大时有,*1*2*1xxxxxxxxkkkk第六章非线性方程组的迭代解法 .2)(*122122kkkkkkxxxxxxx从中解出从中解出 得得*x所以，我们在计算了所以，我们在计算了 之后，之后， 可以用可以用上式右端作为的一个修正值。这样，我们可将迭代法改造上式右端作为的一个修正值。这样，我们可将迭代法改造成下述过程，称为成下述过程，称为Steffensen迭代法迭代法：21,kkkxxx和2kx

17、, 1 , 02)(),(),(21kxyzyzzxyzxykkkkkkkkkkk它的不动点形式是, 1 ,0),1kxxkk（第六章非线性方程组的迭代解法 K 0 1 28 29Xk 0.5 0.606530660 0.567143282 0.567143295表表64其中的迭代函数为xxxxxxxxxxxxx)(2)()()(2)()()()22（例例6.6 求方程的根。求方程的根。 。01)(xxexf解解 此方程等价于此方程等价于 。由。由y=x和和 可以看出可以看出 ， 只有一个不动点只有一个不动点x*0,都有都有 ,所以迭代法所以迭代法 线性收敛。取初始值线性收敛。取初始值 =0.

18、5，迭代结果列于表，迭代结果列于表64。准确解。准确解是是=0.56714329040978，可见线性收敛的速度是很慢的。，可见线性收敛的速度是很慢的。 10 xexkxkex1)(x*xxexx)(xey0 x第六章非线性方程组的迭代解法 如果使用如果使用Steffensen迭代法，仍取初值迭代法，仍取初值x0=0.5.则则。,1 ,0,2)(,21,kxyzyzzxezeykkkkkkkykxkkk计算结果列于表计算结果列于表65。与表。与表64比较，可见比较，可见Steffensen迭代法比迭代法比原方法收敛快得多，仅迭代原方法收敛快得多，仅迭代4次就达到了原方法次就达到了原方法29次的

19、结果。次的结果。K 0 1 2 3 4 Xk 0.5 0.567623876 0.567143314 0.567143290 0.567143290表表65定理定理6.4 设函数按（设函数按（6.2.13）定义。）定义。第六章非线性方程组的迭代解法 （1）若）若x*是是 的不动点，的不动点， 在在x*处连续，且处连续，且 ，则，则x*也是的不动点；反之，若也是的不动点；反之，若x*是是 的不动点，则的不动点，则x*也是也是 的的 的不动点。的不动点。)x（)(x1)*x（)(x)x（ （2）若）若x*是是 的不动点，的不动点， 在在x*处连续，且处连续，且 ,则则Steffensen迭代法迭代

20、法(6.2.11）至少具有二阶局部收敛性。）至少具有二阶局部收敛性。1)*x（)(x)( x证证 （1）若）若x*= ，则当，则当x=x*时，（时，（6.2.13）式的分子）式的分子分母都为零。对它的极限用分母都为零。对它的极限用LHospitale法则，由法则，由于于 ，得知，得知)(*x1)(*x*2*2* 1)( 1)(1)(2)()()()(2)()()()(limlim*xxxxxxxxxxxxxxxxxx从而从而 。反之，若。反之，若 ，则由（，则由（6.2.13）得）得 知知 。)(*xx)(*xx)(*xx第六章非线性方程组的迭代解法 于是，由 对（6.2.14）的两边求极限，因为x*至少是 p(x)和q(x)二重根，所以，使用两次LHospitale法则得 。可知（0)()(, 1)*xqxpx)()()(1xqxpx 其中（2）由（1）可知x* 是 的不动点，于是，由定理6.3，