计算方法2课件.ppt

1、第二章第二章 方程的近似解法方程的近似解法2.0 2.0 引引 言言 2.1 2.1 二分法（对分法）二分法（对分法） 2.2 2.2 简单迭代法简单迭代法2.3 Newton2.3 Newton迭代法及其变形迭代法及其变形2.1 2.1 引言引言求解非线性方程求解非线性方程 f f( (x x)=0)=0 一、问题一、问题困难困难：方程的解难以用公式表达。：方程的解难以用公式表达。例如例如:1):1)多项式方程：多项式方程：0)(0111axaxaxaxpnnnnn需要一定精度的近似解！需要一定精度的近似解！2)2)超越方程超越方程: :0cos2xex二、概念二、概念( )f x设设是连续

2、函数是连续函数,如果有如果有*x使使*()0f x，则称，则称( )f x的的零点零点；如果有；如果有*( )()( )mf xxxg x，且，且( )g x在在邻域内连续，邻域内连续，*()0g xm为正整数，则称为正整数，则称为方程为方程重根重根。当。当1m 时，称时，称为方程的为方程的单根单根。( )f x*x为方程为方程( )0f x 的根，或称为函数的根，或称为函数*x，*x( )0f x 的的m*x 设在区间设在区间 a a, ,b b 上方程有一个根，则称该区间为上方程有一个根，则称该区间为方程的一个方程的一个有根区间有根区间。若在区间。若在区间 a a, ,b b 上方程只有一

3、上方程只有一个根，则称该区间为方程个根，则称该区间为方程隔根区间隔根区间。RemarkRemark：若能把隔根区间不断缩小，则可以得出根的若能把隔根区间不断缩小，则可以得出根的近似值。近似值。三、根的隔离三、根的隔离基于函数基于函数f f( (x x) )的连续性质，常用的根的隔离的方的连续性质，常用的根的隔离的方法有：法有：描图法描图法与与逐步搜索法逐步搜索法。1、描图法描图法：画出画出y y= =f f( (x x) )的简图，从曲线与的简图，从曲线与x x轴交点轴交点的位置确定出隔根区间，或者将方程等价变形为的位置确定出隔根区间，或者将方程等价变形为g g1 1( (x x)=)=g g

4、2 2( (x x) )，画出函数，画出函数y y= = g g1 1( (x x) )和和y y= =g g2 2( (x x) )的简图，的简图，从两条曲线交点的横坐标的位置确定隔根区间。从两条曲线交点的横坐标的位置确定隔根区间。2 2、逐步搜索法、逐步搜索法：先确定方程先确定方程f f(x)=0(x)=0的所有实根所在的所有实根所在区间区间 a a, ,b b ，再按照选定的步长，再按照选定的步长 （n n为正整为正整数），取点数），取点x xk k= =a a+ +khkh( (k k=0,1,=0,1, ,n n) )，逐步计算函数值，逐步计算函数值f f( (x xk k) )，依

5、据函数值异号以及实根的个数确定隔根区，依据函数值异号以及实根的个数确定隔根区间。必要时可调整步长间。必要时可调整步长h h，总可把隔根区间全部找出。，总可把隔根区间全部找出。nabh3 3、根据函数单调性判断、根据函数单调性判断2.1 2.1 二分法（对分法）二分法（对分法）一、算法一、算法设设 在在 a,ba,b 上连续，上连续，f f( (a a) )f f(b)0(b)0且在且在 a a, ,b b 内内f f( (x x) )= =0 0仅有一个实根仅有一个实根 。二分法的。二分法的基本思想基本思想是：是：逐步将有根区间分半，通过判别函数值的符号，逐步将有根区间分半，通过判别函数值的符

6、号，进一步搜索有根区间，将有根区间缩小到充分小，进一步搜索有根区间，将有根区间缩小到充分小，从而求出满足给定精度的根从而求出满足给定精度的根 的近似值。的近似值。)(xf*x*x执行步骤：执行步骤：1计算计算f (x)在有解区间在有解区间a, b端点处的值端点处的值，f (a)，f (b)。2计算计算f (x)在区间中点处的值在区间中点处的值f (x1)。3判断若判断若f (x1) = 0，则则x1即是根，否则检验即是根，否则检验：（1）若若f (x1)与与f (a)异号异号，则知解位于区间则知解位于区间a, x1， b1=x1, a1=a;（2）若若f (x1)与与f (a)同号同号，则知解

7、位于区间则知解位于区间x1, b， a1=x1, b1=b。4. 反复执行步骤反复执行步骤2、3，便可得到一系列有根区间便可得到一系列有根区间：(a, b), (a1, b1), , (ak, bk), 当当11kkab时时)(211kkkbax则则即为方程的近似根即为方程的近似根二、误差估计二、误差估计定理定理2.12.1：给定方程给定方程 f f( (x x)=0)=0，设，设 f f( (x x) )在区间在区间 a a, ,b b 上连续，且上连续，且f f( (a a) )f f( (b b)0)0f (a) f (b)=0f (a) =0打印打印b, k打印打印a, k结束结束是是

8、是是是是否否否否否否m=(a+b)/2|a-b|0打印打印m, ka=mb=m结束结束k=K+1是是是是否否否否输入输入 ,bak = 0算法算法( (二分法二分法) ) 2.2 2.2 迭代法迭代法即序列即序列 的极限的极限 为为 的根。的根。kx*x0)(xf一、一、迭代迭代法法 1.1.基本思想：基本思想： 令方程令方程 , ,将其变成一个等价的方程将其变成一个等价的方程 , ,构造构造 , , 0)(xf)(xx, 1 , 0),(1kxxkkkx称为称为迭代数列迭代数列，)(1kkxx或或迭代过程迭代过程。)(x称为称为迭代函数迭代函数,称为称为迭代公式迭代公式 因此，我们可以通过求

9、迭代数列的极限的方法来因此，我们可以通过求迭代数列的极限的方法来求得方程求得方程f(x)=0的根，该方法称为的根，该方法称为简单迭代法简单迭代法。 当当 连续时，如果有连续时，如果有 或或 。)(x 取极限则有取极限则有)(*xx*()0f x*limkkxx ，对迭代公式两端，对迭代公式两端例例试为方程试为方程3( )10f xxx 建立迭代公式，并求建立迭代公式，并求其在其在1.51.5附近的根。附近的根。311kkxx311kkxx111kkxx3112kkkxxx 解利用方程的等价变形建立如下解利用方程的等价变形建立如下4 4种迭代公式种迭代公式 (1) (1) (2) (2) (3)

10、 (3) (4) (4) k91029108810265101210381011410取初值取初值计算结果如下：计算结果如下：01.5x 上面的结果表明，不同的等价变形构造出来上面的结果表明，不同的等价变形构造出来的迭代格式，有的收敛，有的不收敛。的迭代格式，有的收敛，有的不收敛。12102910881025610381091011410RemarkRemark：可以通过不同的途径将：可以通过不同的途径将f(x)=0化为化为 的形式，从而构造不同的迭代公式，得到不同的的形式，从而构造不同的迭代公式，得到不同的迭代序列。在所有这些构造的迭代公式中形成的迭代序列。在所有这些构造的迭代公式中形成的序

11、列中，有的序列是收敛的，而有些是发散的。序列中，有的序列是收敛的，而有些是发散的。( )xx问题问题：如何选取合适的迭代函数：如何选取合适的迭代函数 ？ 迭代函数迭代函数 应满足什么条件，序列应满足什么条件，序列xk收收敛？敛？ 怎样加速序列怎样加速序列xk的收敛？的收敛？( ) x( ) xxyy = xxyy = xxyy = xxyy = xx*x*x*x*y=g(x)y=g(x)y=g(x)y=g(x)x0p0 x1p1 x0p0 x1p1 x0p0 x1p1x0p0 x1p12.2.迭代法的收敛定理迭代法的收敛定理2, 1 ,0),(1kxxkk（2 2）对任意初值）对任意初值x x

12、0 0 a a, ,b b, , 迭代公式迭代公式 收敛，且收敛，且*lim.kkxx 则有：则有：定理定理2.2 2.2 ( (全局收敛定理全局收敛定理) )设方程设方程 ，如果满足，如果满足)(xx（3 3）存在常数）存在常数00L L1,1,使对任意使对任意 , ( )xa bxL有)(x（1 1）迭代函数）迭代函数 在区间在区间 a a, ,b b 具有一阶连续导函数；具有一阶连续导函数；,)(bax （2 2）当当x a,b时，时， ；*x（1 1）方程）方程 在区间在区间 a a, ,b b 上有惟一的根上有惟一的根 ；)(xx*110,11kkkkkLLxxxxxxxxLL（3

13、3）误差估计）误差估计*1*lim()kkkxxxxx（4 4）证明： 由于由于 上连续，作辅助函数上连续，作辅助函数 ,)(bax 在),()(xxxg( ) , ( )( )0, ( )( )0g xa bg aaag bbb则且，故由连续函数的介值定理知，至少存在故由连续函数的介值定理知，至少存在,*bax 又设 *12( ), , ( )( , ),xx xa bxa b有两个根。注意)( )()(*2*1*2*1*2*1xxxxxx00)( 1(*2*1*2*1xxxx，得,*2*1xx )(x即即 有唯一的根。有唯一的根。(1) (1) 先证方程根的存在性。先证方程根的存在性。*x

14、*)(, 0)(xxxg即使，即，即 是方程是方程 的根。的根。)(xx, 1)( Lx且故由拉格朗日中值定理知，故由拉格朗日中值定理知，2 , 1,*0*1*kxxLxxLxxkkk*1*1*1*)( )()(xxLxxxxxxkkkk（2）由拉格朗日中值定理）由拉格朗日中值定理,有有。即故,lim, 0lim, 10*baxxxxxLkkkk因*1xxk与其中介于 之间，故有（3）由011111)( )()(xxLxxLxxxxxxkkkkkkkkk0111*1111xxLLxxLLxxLxxkkkkkk*1*11*11*)()(xxLxxxxxxxxxxxxkkkkkkkkkk（4）由证

15、毕证毕*1()()( )kkkxxxxxx *1*lim()kkkxxxxx 由于由于 连续，且连续，且 （因为（因为 介于介于 和和 之间），所以有：之间），所以有： ( ) x*limkkxkkx1kx*1*( )kkxxxx 得3.3.迭代法的局部收敛定理迭代法的局部收敛定理迭代法的全局收敛性定理给出的是区间迭代法的全局收敛性定理给出的是区间 a a, ,b b 上的收敛上的收敛性，称之为性，称之为全局收敛性全局收敛性，一般不易验证，并且在较大，一般不易验证，并且在较大的隔根区间上此定理的条件不一定成立，而只能在根的隔根区间上此定理的条件不一定成立，而只能在根的一个较小的邻域内成立。下面

16、给出局部收敛定理：的一个较小的邻域内成立。下面给出局部收敛定理：定理2.3( (局部收敛定理局部收敛定理) )设存在方程设存在方程 根根 的闭邻域的闭邻域 以及小于以及小于1 1的正的正数数 L，使得，使得 连续且连续且 则对任意则对任意 ，迭代，迭代 收敛收敛( )xx*x*(, ),(0)U xxx ( ) x( )1xL*0(, )xU x1( )kkxx将前述将前述定理定理1 1中的中的a,ba,b取为取为 ，则只需证，则只需证明明 即可。即可。*(, ), ( )(, )xU xxU x ,*xx*)( )()()(xxxxLxxxxxx证明：证明：证毕证毕 故*( , ), ( )

17、( , )x U xxU x 。 当x ，即 时，由Lagrange中值定理有:*xx*(, )U x其中在x与x*之间，即 。*(, )U xRemark2Remark2：可以证明，若在根可以证明，若在根 的邻域中的邻域中 ，则，则可以以邻域内任何一点可以以邻域内任何一点 为初始值，用迭代过程产生为初始值，用迭代过程产生的序列就一定不会收敛于的序列就一定不会收敛于 。事实上，。事实上，*x1)( x0 x*x*0*1*1*1*)( )()(xxxxxxxxxxkkkkRemark3Remark3：当当 不取在不取在 的邻域内时可能不收敛。的邻域内时可能不收敛。0 x*xRemark1Rema

18、rk1：全局与局部收敛定理中的条件都是充分全局与局部收敛定理中的条件都是充分条件，条件满足则迭代法收敛，不满足则不能判定，条件，条件满足则迭代法收敛，不满足则不能判定，此时可以用试算来判定迭代法的是收敛性。此时可以用试算来判定迭代法的是收敛性。Remark4Remark4：全局收敛定理中的两个误差估计式实际上全局收敛定理中的两个误差估计式实际上给出了迭代收敛的两个准则：事后误差估计与事先误给出了迭代收敛的两个准则：事后误差估计与事先误差估计（利用估计式可以预先求出迭代次数差估计（利用估计式可以预先求出迭代次数k k）。）。4.4.迭代收敛准则迭代收敛准则方法一、事先误差估计法方法一、事先误差估

19、计法方法二、事后误差估计法方法二、事后误差估计法先计算满足误差要求的迭代次数先计算满足误差要求的迭代次数k k，再进行迭代。，再进行迭代。01*1xxLLxxkk有有LxxLkln)1 (ln01由由由由1*1kkkxxLLxx因此可以用因此可以用 来控制迭代过程。来控制迭代过程。1kkxx只要使只要使 ，就可使，就可使 ，1kkxxLLxxk1* 对于较为复杂的迭代函数，其导数也较为复杂，对于较为复杂的迭代函数，其导数也较为复杂，使得使得L L难以取得，因而实际中不常用此方法。难以取得，因而实际中不常用此方法。Remark1:Remark1:迭代方法的优点是计算程序简单，迭代方法的优点是计算

20、程序简单，并且虽然是以求解非线性方程的实根来讨论并且虽然是以求解非线性方程的实根来讨论的，但类似的结果完全可以推广到求方程的的，但类似的结果完全可以推广到求方程的复数根的情形。复数根的情形。Remark2Remark2：由全局收敛定理知，若由全局收敛定理知，若L L 1 1，则，则 x xk k 必然收敛较慢；若必然收敛较慢；若L L11，则收敛速度快。，则收敛速度快。km是是输出输出结束结束k=k+1是是否否输入输入0,xmk = 0算法算法( (迭代法迭代法) ) 定义定义 ( ) x10()xx10 xx已到最大迭代次数已到最大迭代次数1,x k01xx否否二、二、迭代法的收敛阶迭代法的

21、收敛阶若若00C C1,11称为称为超线性收敛超线性收敛；p p2 2称为称为平方收敛平方收敛（二次收敛二次收敛）。）。 p p 越大，收敛速度越越大，收敛速度越快；反之，快；反之，p p越小，收敛速度就越慢。因此，迭代法的越小，收敛速度就越慢。因此，迭代法的收敛阶是对迭代法收敛速度的一种度量。收敛阶是对迭代法收敛速度的一种度量。1limkpkkeCe（ C称为渐近误差常数）称为渐近误差常数）定义：定义：设设 收敛于收敛于 ，令迭代误差，令迭代误差 ，如果存在实数，如果存在实数 及非零正常数及非零正常数C使得使得1kkxx （ ）*( )xxx的根*kkexx1p 则称该迭代过程以及该迭代式是

22、则称该迭代过程以及该迭代式是p p阶收敛的阶收敛的，也，也称相应的迭代法是称相应的迭代法是p p阶方法。阶方法。三、迭代法的加速三、迭代法的加速 对于收敛的迭代序列，理论上迭代次数对于收敛的迭代序列，理论上迭代次数足够多时，就可以使计算结果满足任意给定的足够多时，就可以使计算结果满足任意给定的精度要求但在应用中，有的迭代过程收敛极精度要求但在应用中，有的迭代过程收敛极为缓慢，计算量很大，因此研究迭代格式的加为缓慢，计算量很大，因此研究迭代格式的加速方法非常必要速方法非常必要1.1.线性收敛序列的线性收敛序列的AitkenAitken加速法加速法*x1c0kkx*1*limkkkxxcxx 设设

23、 是一个线性收敛的序列，即有是一个线性收敛的序列，即有小于小于1 1的正常数的正常数c使得：使得：从上式可以看出，右端第二项是对从上式可以看出，右端第二项是对 的一种补偿的一种补偿。kx当当k充分大时，有充分大时，有*1*,kkxxcxx*2*1kkxxcxx*12*1kkkkxxxxxxxx于是有于是有22*2112121()22kkkkkkkkkkkkx xxxxxxxxxxxx解得：解得：2121()2kkkkkkkxxyxxxx，则得，则得AitkenAitken加速公式：加速公式： 定义另一序列定义另一序列0kky 上述公式得到的序列同样收敛于上述公式得到的序列同样收敛于 ，而，而且

24、收敛更快。且收敛更快。*x2. Steffensen(2. Steffensen(斯蒂芬森斯蒂芬森) )迭代法迭代法 将将AitkenAitken加速方法用于简单迭代法产生迭加速方法用于简单迭代法产生迭代序列时，得到著名的代序列时，得到著名的SteffensenSteffensen迭代法，具迭代法，具体迭代公式如下：体迭代公式如下：21()( )(0,1,2,)()2kkkkksxtsksxxxtsx 可以证明可以证明SteffensenSteffensen迭代法在一定的条件迭代法在一定的条件下与原简单迭代法的迭代序列具有相同的极限下与原简单迭代法的迭代序列具有相同的极限，但，但Steffen

25、senSteffensen迭代法收敛速度更快，可以达迭代法收敛速度更快，可以达到二阶收敛。到二阶收敛。 教材例教材例2.52.5给出了用给出了用SteffensenSteffensen迭代法求迭代法求解的一个例子，可以看出其明显比简单迭代解的一个例子，可以看出其明显比简单迭代法收敛快。法收敛快。一、一、NewtonNewton迭代法基本思想与迭代法基本思想与Newton-Newton-RaphsonRaphson公式公式2)(! 2)()( )()(kkkkkxxxfxxxfxfxf0)( )(kkkxxxfxf)(xf0)(xf取前两项近似代替取前两项近似代替 得近似得近似 的线性方程的线性

26、方程2.3 Newton2.3 Newton迭代法迭代法设设 是是 的一个近似根，则的一个近似根，则0)(xfkx基本思想基本思想：将非线性方程转化为线性方程来求解。：将非线性方程转化为线性方程来求解。由由 知知 是是 处处 的的切线切线 与与 轴交点的横坐标，轴交点的横坐标，)( )(1kkkkxfxfxx1kx)(,(kkxfx)(xfy )( )(kkkxfxxxfyx故故NewtonNewton法法的的几何意义几何意义是逐次用切线代替曲线，是逐次用切线代替曲线， 求切线与横坐标轴的交点。求切线与横坐标轴的交点。 NewtonNewton法亦称为切线法法亦称为切线法。（如下图）。（如下图

27、）设设 , ,令解为令解为 得得0)(xf1kx), 2 , 1 , 0( ,)( )(1kxfxfxxkkkk)0)( ()( )(xfxfxfxx0)(xf显然是显然是 的同解方程。的同解方程。 0)(xf上式上式称为称为 的的Newton迭代法迭代法，对应的方程，对应的方程x*x0 x1x2xyf(x)NewtonNewton迭代法逼近过程迭代法逼近过程222)()()()()()()(1)( xfxfxfxfxfxfxfx证明证明：（1）先证先证Nowton迭代法满足迭代法局部收敛定迭代法满足迭代法局部收敛定理的两个条件。理的两个条件。1.1.局部收敛性局部收敛性故，故， ( (x x

28、) )在在x* *的邻域可导。的邻域可导。由迭代函数由迭代函数 得得: : )()()(xfxfxxx定理定理2.4(Newton2.4(Newton迭代法局部收敛定理迭代法局部收敛定理) ) 设设 为为 的单根，在的单根，在 的邻域上的邻域上 连续。则存在连续。则存在 ，当，当 时，时，NowtonNowton迭代法产生的迭代法产生的序列序列 至少二阶收敛。至少二阶收敛。*x0)(xf( )fx*x0*0(, ),xU xxx0kkx二、二、NewtonNewton迭代法的收敛性迭代法的收敛性显然又有显然又有0)( *x 根据连续函数的性质，一定存在根据连续函数的性质，一定存在x*的某个闭的

29、某个闭邻域邻域 ，对于任意的，对于任意的 ，有，有*(, )U x*(, )xU x( )1xL 因此因此Nowton迭代法满足局部收敛性。迭代法满足局部收敛性。 （2 2）下面证明下面证明Nowton迭代法二阶收敛。迭代法二阶收敛。将将f(x)在在xk处作一阶处作一阶Taylor展开，展开，2)(! 21)( )()(kkkkkxxfxxxfxfxf其中其中 k在在x与与xk之间。因为之间。因为x， xk a,b,所以所以 k (a,b)。RemarkRemark：上述定理对于初值：上述定理对于初值x0的要求比较高，只有当的要求比较高，只有当初值选的充分靠近初值选的充分靠近 时，才能保证序列

30、收敛。时，才能保证序列收敛。*x将将x=x*代入上式，有代入上式，有0)(21)( )()(2*kkkkkxxfxxxfxfxf于是有于是有2*1*2*)()( )( 21)()( )( 21)( )(kkkkkkkkkkxxxffxxxxxffxfxfxx*1*2*()lim()2()kkkxxfxxxfx从而从而存在存在由收敛阶定理知，牛顿迭代法至少二阶收敛。由收敛阶定理知，牛顿迭代法至少二阶收敛。2.2.非局部收敛性非局部收敛性 定理（定理（NewtonNewton迭代法的非局部收敛性）：迭代法的非局部收敛性）：设设x x* *是方程是方程f f( (x x)=0)=0在隔根区间在隔根区

31、间 a a, ,b b 内的根，如果满足内的根，如果满足（2）取）取 使使,0bax 。0)( )(00 xfxf)( ),( xfxf（1）对于）对于x a,b， 连续且不变号；连续且不变号； 则由Newton迭代公式产生的数列收敛于根x*。Remark：定理的几何解释见下图。满足定理条定理的几何解释见下图。满足定理条件的情况只有件的情况只有4种。种。yx0aby=f(x)x00)(,0)( xfxf(a)x x0 0取靠近取靠近b b一侧一侧yx0aby=f(x)x00)(, 0)( xfxf(b)x x0 0取靠近取靠近a a一侧一侧yx0aby=f(x)x00)(, 0)( xfxf(

32、c)x x0 0取靠近取靠近a a一侧一侧yx0aby=f(x)x00)(, 0)( xfxf(d)x x0 0取靠近取靠近b b一侧一侧证明：证明：仅就图仅就图( (c c) )的情况进行证明。此时，有的情况进行证明。此时，有*0, 0)(, 0)(,xxxfxfbax要证要证 ，应证数列，应证数列 xk 单调递增上有界。单调递增上有界。*limxxkk（1 1）用数学归纳法证明数列上有界，即证）用数学归纳法证明数列上有界，即证xkx*。k0时，时，xkx*成立成立。一般的，设一般的，设x xk k x x* *成立，再证成立，再证x xk k1 1 x x* *成立即可。成立即可。将将f

33、f( (x x) )在在x xk k处作一阶处作一阶TaylorTaylor展开，展开，2)( ! 21)( )()(kkkkkxxfxxxfxfxf其中其中 k k在在x x与与x xk k之间。因为之间。因为x x， x xk k a a, ,b b,所以所以 k k ( (a a, ,b b) )。将将x=xx=x* *代入上式，有代入上式，有0)(21)( )()(2*kkkkkxxfxxxfxfxf于是有于是有2*1*2*)()( )( 21)()( )( 21)( )(kkkkkkkkkkxxxffxxxxxffxfxfxx由已知条件知，上式右端第二项小于零，从由已知条件知，上式右

34、端第二项小于零，从而有而有x xk k1 1 x x* *成立。成立。故由数学归纳法知，故由数学归纳法知，x xk k 0 0，则可以保证，则可以保证NewtonNewton迭代法的收敛性。迭代法的收敛性。 #三、牛顿迭代法的变形三、牛顿迭代法的变形Newton迭代优点：迭代优点： 格式构造容易；格式构造容易； 迭代收敛速度快；迭代收敛速度快；Newton迭代缺点：迭代缺点： 对初值的选取比较敏感，要求初值充对初值的选取比较敏感，要求初值充 分接近真解；分接近真解； 对重根收敛速度较慢；对重根收敛速度较慢； 当函数复杂时，导数计算工作量大当函数复杂时，导数计算工作量大1 1牛顿下山法牛顿下山法

35、牛顿下山法基本原理牛顿下山法基本原理： 方程的根方程的根 也是也是 的最小值点，若把的最小值点，若把 看成在看成在x x处的高度，则处的高度，则 是山谷的最低点。是山谷的最低点。*x( )f x( )f x*x( )f x 若序列若序列 满足：满足： ，则称，则称 为为 的下山序列。的下山序列。0 k kx1()( )kkf xf x0 k kx 牛顿迭代法中，初值的选取直接影响到迭代牛顿迭代法中，初值的选取直接影响到迭代结果，如果初值选择的离方程的根较远，牛顿结果，如果初值选择的离方程的根较远，牛顿迭代法甚至不收敛。迭代法甚至不收敛。牛顿下山法是一种降低对牛顿下山法是一种降低对初值要求的改进

36、的牛顿迭代法初值要求的改进的牛顿迭代法。)( )(1kkkkxfxfxx 引入下山因子引入下山因子 ，将牛顿迭代法修改为：，将牛顿迭代法修改为：(0,1 适当选择下山因子适当选择下山因子 ，使得，使得 成立。成立。1()( )kkf xf x 取取1 1 1 11,2 4 8 16 下山因子下山因子 选取方法：选取方法：试算法试算法 如果找到合适的如果找到合适的 ，则，则“下山成功下山成功”；否；否则，则，“下山失败下山失败”。牛顿下山法计算步骤如下：牛顿下山法计算步骤如下：（1 1）选取初始近似值）选取初始近似值x x0 0；（2 2）取下山因子）取下山因子 = 1= 1；)( )(1kkk

37、kxfxfxx（3 3）计算）计算)(1kxf)(kxf（4 4）计算）计算f f ( (xk+1) )，并比较，并比较 与与 的大的大小，分以下二种情况：小，分以下二种情况：)()1kkxfxf21kkxx21kkxx1 1）若）若 ，则当，则当 时，取时，取x* xk+1，计算过程结束计算过程结束; ; 当当 时，则把时，则把xk+1作为新的作为新的xk值，并重复回到（值，并重复回到（3）。）。11)(kxf当当 ；且；且 ，则将下山因子缩小一半，取，则将下山因子缩小一半，取 /2/2代入，并转向（代入，并转向（3 3）重复计算。）重复计算。 x xk k+1+1加上一个适当选定的小正数，

38、加上一个适当选定的小正数，)()1kkxfxf 2）若若 ，则当，则当 且且 ，取，取x* xk，计算过程结束；计算过程结束；11)(kxf11)(kxf否则若否则若 ，而，而 时，时，则把则把即取即取xk+1+ 作为新的作为新的xk值，值，并转向（并转向（3 3）重复计算；）重复计算；例例5 5：求方程：求方程f f ( (x x) = ) = x x3 3 x x 1 = 0 1 = 0 的根的根k xk010.611/251.14063211.36681311.32628411.32472牛顿下山法的计算结果：牛顿下山法的计算结果：2 2针对重根情形的加速算法针对重根情形的加速算法设设

39、是方程的是方程的m m 重根，并且存在函数重根，并且存在函数 ，使得，使得 *x( )g x*( )()( ),()0mf xxxg xg x*1*( )()( )() ( )( )( )()( )()( )( )()( )mmmf xxxg xxxg xxxxxfxm xxg xxxg xmg xxxg x*() ( )( )()( )()( )()limlim( )1lim11( )()( )xxxxxxxxg xxxxxmg xxxg xxxxxxg xmmg xxxg x 可见，此时牛顿迭代法仅为线性收敛可见，此时牛顿迭代法仅为线性收敛( )( )( )f xxfx法法1：令：令2(

40、)( )( )( )( )( )( )( )xf x fxxxxxfxf x fx12()()(0,1,2,)()()()kkkkkkkf xfxxxkfxf xfx法法2：( )( )( )fxxxmfx1()(0,1,2,)()kkkkf xxxmkfx为加速收敛，可以采取如下两种方法：为加速收敛，可以采取如下两种方法：3 3、 单点弦截法单点弦截法 ：牛顿法一步要计算牛顿法一步要计算 f 和和 f ，相当于，相当于2个函数值。现用个函数值。现用 f 的值近似的值近似 f :x0 x1切线切线 割线割线 切线斜率切线斜率 割线斜率割线斜率00)()()(xxxfxfxfkkk)()()()(001xxxfxfxfxxkkkkkx24 4、 双点弦截法双点弦截法 ：切线斜率切线斜率 割线斜率割线斜率11)()()( kkkkkxxxfxfxf)()()(111 kkkkkkkxfxfxxxfxx需要需要2个初值个初值 x0 和和 x1。x0 x1x2