第七章 非线性方程的数值解法

1、1 第七章第七章 非线性方程的数值解法非线性方程的数值解法 求求 f (x) = 0 的根的根 第一节第一节 方程求根的二分法方程求根的二分法 第二节第二节 一元方程的不动点迭代法一元方程的不动点迭代法 第三节第三节 一元方程的常用迭代法一元方程的常用迭代法 上一页上一页 下一页下一页 返回返回 2 本章要讨论的问题：本章要讨论的问题： （非线性）方程（非线性）方程f (x)=0的数值解法的数值解法 首先引入定义：首先引入定义： 1. f (x)=0的解的解x*称为方程称为方程f (x)=0的根或函数的根或函数f (x) 的零点的零点. 2. 若若f (x)=(x- -x*)m g(x) ,

2、g (x*) 0 ，其中其中m为正整数，为正整数， 则称则称 x*为方程为方程f (x)=0的的m重根，或重根，或称称 x*为为函数函数 f (x)的的m重零点重零点. 上一页上一页 下一页下一页 返回返回 3 1 方程求根的二分法方程求根的二分法 方程求根步骤：方程求根步骤： 根的隔离根的隔离 确定根所在的区间确定根所在的区间a, b, 使在使在a, b内至少有方程的内至少有方程的 一个根一个根. 有根区间有根区间 近似根的精确化近似根的精确化 已知根的一个近似值后已知根的一个近似值后, 构造某种算法构造某种算法, 将此近似值将此近似值 精确化精确化, 使其满足给定的精度要求使其满足给定的精

3、度要求. 越小越好越小越好 上一页上一页 下一页下一页 返回返回 4 下面介绍方程求根的下面介绍方程求根的二分法二分法 在确立了有根区间在确立了有根区间a, b后后, 需要逐步缩小有根区间需要逐步缩小有根区间. 取取a, b的中点的中点x0 0=(=(a+ +b)/)/2, ,将区间一分为二将区间一分为二. .若若 f( (x0 0)=0,)=0,则则x0 0 就是方程的根 就是方程的根, ,否则判别根否则判别根 x* * 在在x0 0 的左 的左 侧还是右侧侧还是右侧. . 01100 0 xbaaxaxxfaf,),(*,)()(令令则则若若 bbxabxxxfaf 10100 0,),(

4、*,)()(令令则则若若 不论出现哪种情况不论出现哪种情况, (a1, b1)均为新的有根区间均为新的有根区间, 它它 的长度只有原有根区间长度的一半的长度只有原有根区间长度的一半, 达到了压缩有根达到了压缩有根 区间的目的区间的目的. 上一页上一页 下一页下一页 返回返回 5 重复以上过程重复以上过程, 继续进行二分继续进行二分, 可得一系列有根区间可得一系列有根区间 , 11kk bababa , 2 , 1, 2 k ab ab k kk 而而且且 .,将将收收缩缩为为一一点点区区间间时时当当显显然然 kk bak 由于每个小区间都是有根区间由于每个小区间都是有根区间, 所以这个点就是所

5、所以这个点就是所 求方程的根求方程的根. 同时同时, 在每次二分时在每次二分时, 所求出的中点所求出的中点 形成一个无穷数列形成一个无穷数列 k kk k ba x 2 , 10k xxx 这个数列必定收敛于这个数列必定收敛于 x*. 上一页上一页 下一页下一页 返回返回 6 a b x0 x1 a1 b2 when to stop? x* b1 上一页上一页 下一页下一页 返回返回 a2 7 误差误差 分析：分析： 第第1步产生的步产生的 2 0 ba x 有误差有误差 2 0 ab x*|x 第第 k 步产生的步产生的 xk 1 有误差 有误差 k k ab x*|x 2 1 对于给定的精

6、度对于给定的精度 ,可估计二分法所需的步数可估计二分法所需的步数 k ： 2ln lnln 2 ab k ab k 算法简单算法简单; ; 对对f (x) 要求不高要求不高(只要连续即可只要连续即可) ，收敛，收敛 性总能得到保证性总能得到保证 无法求复数根及偶数重根（函数值的正负号相同）；无法求复数根及偶数重根（函数值的正负号相同）； 要计算很多次函数值，收敛慢要计算很多次函数值，收敛慢 二分法的误差估计二分法的误差估计 式式 上一页上一页 下一页下一页 返回返回 8 例例1 用二分法求用二分法求f (x)= x 3- -x- -1=0 在区间在区间1, 1.5内内的一个实根的一个实根, ,

7、 要要 求误差不超过求误差不超过0.005. 0.005. 解：解： 由题可知由题可知x* (1, 1.5) , ,要想要想则则要要,005.0 * n xx 0050 2 1 151 2 1 2 1 211 .).()( nnn ab 解之得解之得 6.51 2lg 2 n 取取 n6. 按二分法计算的过程见下表按二分法计算的过程见下表, x6 为所求之近似根为所求之近似根. 上一页上一页 下一页下一页 返回返回 9 nanbnxnf (xn)备注备注 01.01.51.25- - f(a0 )0 根据精度要求根据精度要求xn取取 到小数点四位即可到小数点四位即可. 11.251.51.37

8、5+ + 21.251.3751.3125 - - 31.31251.3751.3438 + + 41.31251.34381.3281 + + 51.31251.32811.3203 - - 61.32031.32811.3242 - - 上一页上一页 下一页下一页 返回返回 10 逐步搜索法逐步搜索法 从区间从区间a，b的左端点的左端点 a 出发出发, 按选定的步长按选定的步长 h 0 一步步向右搜索一步步向右搜索, 若：若： ),1 ,0(,0)1()( jhjafjhaf 则区间则区间a +j h, a +( j+1) h内必有根内必有根. 上一页上一页 下一页下一页 返回返回 于是可

9、确定一个缩小了的有根区间于是可确定一个缩小了的有根区间a +j h, a +( j+1) h. 再对新的有根区间，取新的更小的预定步长，继续再对新的有根区间，取新的更小的预定步长，继续 搜索，直到有根区间的长度足够小。搜索，直到有根区间的长度足够小。 搜索过程也可从搜索过程也可从 b 开始开始, , 这时应取步长这时应取步长 h 0. 11 2 一元方程的不动点迭代法一元方程的不动点迭代法 迭代格式迭代格式 一、不动点迭代法及其收敛性一、不动点迭代法及其收敛性 1. 迭代法的基本思想迭代法的基本思想 )( xx 将方程将方程 f (x) =0化为等价方程化为等价方程 然后在然后在 有根区间内取

10、一点有根区间内取一点 x0, 按下式计算按下式计算 )(),()(1210 1 kxx kk 计算结果生成数列计算结果生成数列 xk )2(, 10 k xxx 上一页上一页 下一页下一页 返回返回 12 *limxxk k 如果这个数列有极限如果这个数列有极限 , x*就是方程就是方程 的根的根. )( xx 迭代式（迭代式（1）称为）称为基本迭代法基本迭代法. 称为称为迭代函数迭代函数, x 0称为称为迭代初值迭代初值, 数列数列(2)称称 为为迭代序列迭代序列. )( x 上一页上一页 下一页下一页 返回返回 如果迭代序列收敛如果迭代序列收敛, , 则称迭代格式则称迭代格式收敛收敛, ,

11、 否则否则 称为称为发散发散. . x* 称为称为 的的不动点。不动点。)( x 迭代过程中，迭代过程中，xk+1仅由仅由xk决定，因此，这是一决定，因此，这是一 种单步法。种单步法。 13 例例2 用迭代法求方程用迭代法求方程 x 4+2 x 2- - x- -3=0在区间在区间1, 1.2内的实根内的实根. 解：解：对方程进行如下三种变形对方程进行如下三种变形 4 1 2 1 )23()(xxxx 14)( 2 xxx 32)( 24 3 xxxx 分别按以上三种形式建立迭代格式分别按以上三种形式建立迭代格式, 并取并取 x0=1进行迭代计算进行迭代计算, 结果如下：结果如下： 12412

12、31 272611 .),( xxxx kk 准确根准确根 x*=1.124123029, 可见迭代格式不同可见迭代格式不同, 收敛情况也不收敛情况也不 同同, 收敛速度也不同收敛速度也不同. 上一页上一页 下一页下一页 返回返回 1241231 7621 .),( xxxx kk 7 4331 10495307896 .,),(xxxx kk 14 上一页上一页 下一页下一页 返回返回 的根。的根。求求02 2 xxf)(例例3 3 解：解：把把f (x)=0 转换成等价形式转换成等价形式 )()( x xxx 2 2 1 对应的迭代法为对应的迭代法为 )( k kk x xx 2 2 1

13、1 取初值取初值x0= =1,1,迭代结果分别收敛到迭代结果分别收敛到x*= , ,计算结果见下表计算结果见下表 2 k 0 1 2 3 4 5 xk 1 1.5 1.41666667 1.41421569 1.41421356 1.41421356 xk - -1 - -1.5 - -1.41666667 - -1.41421569 - -1.41421356 - -1.41421356 从而可见，基本迭代法的收敛性取决于迭代函数从而可见，基本迭代法的收敛性取决于迭代函数 和初和初 值值x0 0的选取。的选取。 )(x 15 问问 题题 2. 迭代格式应该满足什么条件才能保证收敛？迭代格式应

14、该满足什么条件才能保证收敛？ 3. 如何判断迭代收敛的速度如何判断迭代收敛的速度, 建立收敛快的迭代格式？建立收敛快的迭代格式？ 上一页上一页 下一页下一页 返回返回 1. 迭代函数迭代函数 如何构造？如何构造？ )(x 16 定理定理1 2. 收敛条件与误差估计收敛条件与误差估计 上一页上一页 下一页下一页 返回返回 迭代格式的收敛性与迭代函数迭代格式的收敛性与迭代函数 密切相关密切相关. .)(x 方程方程 x = ， ca, b, 满足条件满足条件 )(x )(x ( 1 ) 当当 x a, b 时，时， a, b； ( 2 ) 0 l 1 使得使得 | | l 1 对对 x a, b

15、成立成立. )(x )(x 则则 ( 1 ) 函数函数 在在a, b 上有唯一不动点上有唯一不动点 x*; ( 2 ) 对任意迭代初值对任意迭代初值 x0 a, b, 迭代序列迭代序列 x k+1 收敛于收敛于x* *. . )(x （3）有下列误差估计式：有下列误差估计式： 17 |*| 1 1 kkk xx l l xx | 1 |*| 01 xx l l xx k k ( k = 1, 2, ) 反之反之, 若在区间若在区间r 内内 , 则迭代必发散则迭代必发散.rxx , 1)( 上一页上一页 下一页下一页 返回返回 l 越越小小 收敛越快收敛越快 尚未计算时便估计出第尚未计算时便估计

16、出第 k 次迭代近似值次迭代近似值 的误差的误差, 称为称为事先误差估计事先误差估计. 18 由定理由定理1的误差估计式可看出的误差估计式可看出, 只要相邻两次迭代近似值只要相邻两次迭代近似值 xk 与与 xk- -1的偏差的偏差 | |xk xk - -1 | |充分小充分小, ,就可以保证迭代值就可以保证迭代值 xk 足够精足够精 确确. . 这种用前后两次迭代结果这种用前后两次迭代结果 估计误差的办法称为估计误差的办法称为事后事后 误差估计误差估计 上一页上一页 下一页下一页 返回返回 因此对于给定的允许误差因此对于给定的允许误差, , 当当 l 较小时较小时, 常用前后两次迭常用前后两

17、次迭 代是否满足代是否满足 |xk xk -1 -1 | 来终止迭代来终止迭代. . 19 | 1 |*| 01 xx l l xx k k 不但可以估计迭代不但可以估计迭代 k 次时的误差次时的误差, 也可以用来确定达到误差精度要求的迭代次数也可以用来确定达到误差精度要求的迭代次数 k . 当要求误差精度为当要求误差精度为,即要求即要求 , ,只要只要 |*| k xx | 1 01 xx l l k 即可即可, 从中解出从中解出 k 为为l xx l kln) )( ln( 10 1 实际应用中实际应用中,控制迭代结束的条件也常取为控制迭代结束的条件也常取为 e 其中其中 1 1 1 1

18、k k kk kkk x x xx xxx e 当当 当当 , , 上一页上一页 下一页下一页 返回返回 20 x y y = x x y y = x x y y = x x y y = x x*x* x* x* y=(x) y=(x) y=(x) y=(x) x0 p0 x1 p1 x0 p0 x1 p1 x0 p0 x1 p1 x0 p0 x1 p1 上一页上一页 下一页下一页 返回返回 迭代过程的几何解释如下图迭代过程的几何解释如下图 21 上一页上一页 下一页下一页 返回返回 例例4 4 对于例对于例2 2中的三种迭代法，讨论它们的收敛性。中的三种迭代法，讨论它们的收敛性。 4 1 2

19、 1 )23()(xxxx 14)( 2 xxx 32)( 24 3 xxxx 解解： 对于下面三种迭代函数对于下面三种迭代函数 其导函数在其导函数在1,1.2内分别有内分别有 4 3 2 4 3 2 1 212134 1214 234 14 ).( . )( )( xx x x 11 251544144 xxx)( xxx44 3 3 )( 1870 1 l. 1110 2 l. 18 3 l 根据定理根据定理1，例，例2中的第三种迭代法发散，第一、二种迭代中的第三种迭代法发散，第一、二种迭代 格式收敛，而且第二种迭代法比第一种迭代法收敛快得多。这格式收敛，而且第二种迭代法比第一种迭代法收敛

20、快得多。这 与实际计算结果完全吻合。与实际计算结果完全吻合。 22 迭代法的流程图如下：迭代法的流程图如下： 上一页上一页 下一页下一页 返回返回 23 上一页上一页 下一页下一页 返回返回 可可得得由由)( xx xxxx33)( 例例5 5 代代函函数数？构构造造一一个个收收敛敛的的简简单单迭迭 ，试试问问如如何何利利用用满满足足的的已已知知 )( )()()( x xxxx 13 解解： 即可得等价的方程即可得等价的方程 )(xxx 3 2 1 有时，对于不满足定理条件的问题，可以通过转化，化为有时，对于不满足定理条件的问题，可以通过转化，化为 适合于迭代的形式。适合于迭代的形式。 令令

21、)()(xxx 3 2 1 则有则有 2 1 3 2 1 )()(xx 故故 收收敛敛。迭迭代代法法),( )()(2103 2 1 1 kxxxx kkkk 24 上一页上一页 下一页下一页 返回返回 二、局部收敛性和加速收敛法二、局部收敛性和加速收敛法 定理定理1 1中，迭代法在区间中，迭代法在区间 a, ,b 上的收敛性，称之为上的收敛性，称之为全局收敛性全局收敛性. . 定义定义: : 若在若在 x* 的某的某 邻域邻域 r = x | | x x* | , 使迭代过程使迭代过程 xk+1= ( xk ), k=0,1,2, 对于任意对于任意x0 r 均收敛均收敛, ,则称该迭代过则称

22、该迭代过 程在程在x*处具有处具有局部收敛性局部收敛性. 定理定理2 局部收敛。局部收敛。，则迭代法，则迭代法且有且有 的某个邻域上连续，的某个邻域上连续，在在的不动点，的不动点，是是设设 )(1*)( *)()(* 1kk xxx xxxx 25 迭代过程的收敛速度迭代过程的收敛速度 定义定义 使使得得以以及及实实数数常常数数 如如果果有有非非零零记记收收敛敛于于设设数数列列 , , * 1 pc xxexx kkk c e e p k k k 1 lim .阶阶收收敛敛的的是是则则称称pxk p的大小反映了迭代过程收敛的快慢的大小反映了迭代过程收敛的快慢, p 越大收敛速度越快越大收敛速度

23、越快. 上一页上一页 下一页下一页 返回返回 是线性收敛；是线性收敛；称序列称序列时时当当, k xp1 是超线性收敛；是超线性收敛；称序列称序列时时当当, k xp1 .,是平方收敛是平方收敛称称时时 k xp2 26 定理定理3 且有且有阶收敛阶收敛的邻近为的邻近为过程在过程在 则迭代则迭代若若 , ,)(,)()()( )2( * *)(*)(* px xxxx pp 00 1 上一页上一页 下一页下一页 返回返回 设设 x*为函数为函数 的不动点的不动点 , 在在x* 的邻域的邻域 内内 有连续有连续 的的p p 阶导数阶导数( (p p1),),那么那么 )(x )(x ( 1 )

24、0 | | 1 , 则迭代过程在则迭代过程在x*的邻近为线性收敛；的邻近为线性收敛； *)(x . ! )( lim *)( p x e e p p k k k 1 27 ax axx x k kk k 2 2 1 3 )3( 例例6 证明迭代公式证明迭代公式 是求是求 的三阶方法的三阶方法. 假假 设设 xo 充分靠近充分靠近 x *, 求求 )0( aa 3 1 )( lim k k k xa xa 解：解： 此迭代格式的迭代函数为此迭代格式的迭代函数为 , 3 )3( )( 2 2 xa axx x , )( )( a aa aaa a 3 3 由由.)( 的的不不动动点点为为得得xa

25、确定的隐函数确定的隐函数看作由方程看作由方程将将0)3()()3()( 22 axxxaxx 方程两边对方程两边对 x 求导求导, 得得 033)(6)()3( 22 axxxxax 上一页上一页 下一页下一页 返回返回 . 0)(,可可得得令令aax 28 再将上式两边对再将上式两边对 x 求导求导, 得得 066123 2 xxxxxax)()()()( . 0)(,可可得得令令aax 上式再对上式再对 x 求导求导, 得得 06)(18)(18)()3( 2 xxxxax 上一页上一页 下一页下一页 返回返回 . 0 2 3 )(, a aax可可得得令令 所以，迭代格式是所以，迭代格式

26、是3 3阶收敛的阶收敛的. . a a xa xa e e k k k k k k 4 1 3 1 3 1 3 1 )( ! )( limlim 29 加速收敛的加速收敛的steffensen迭代法迭代法 对于线性收敛的迭代法，收敛很慢。对于线性收敛的迭代法，收敛很慢。 ),(),( 121 kkkk xxxx 有有充充分分大大时时当当,k k k k k xx xx xx xx * * * * 1 1 2 kkk kk k xxx xx xxx ）（ 即即得得解解出出 12 2 12 2 2 * , 上一页上一页 下一页下一页 返回返回 设设 xk 是方程是方程 根根 x*的一个近似值，由的

27、一个近似值，由xk 开始相继迭代两次开始相继迭代两次, , 将其结果记作将其结果记作 c e e e e k k k k k k 1 1 2 limlim . , *的 的近近似似值值得得到到精精度度更更高高的的 以以它它来来修修正正的的误误差差估估计计值值此此式式右右端端可可看看作作 x xx kk22 30 于是得到如下迭代格式于是得到如下迭代格式 , )( ),( 210 2 2 1 k xyz yz zx yzxy kkk kk kk kkkk ）（ 称之为称之为steffensen迭代法迭代法(其他教材也称之为其他教材也称之为埃特金埃特金(aitken)外外 推加速法推加速法). 上

28、一页上一页 下一页下一页 返回返回 它的不动点迭代格式是它的不动点迭代格式是, ),(210 1 kxx kk 其中迭代函数为其中迭代函数为 , )()( )( )()( )()( )( xxx xx x xxx xxx x 22 22 31 得得迭迭代代格格式式解解：取取, 5 . 0 10 k x k exx 5671433. 0 2625 xx 若对此格式用若对此格式用steffensen法法, 则则 kkk kk kk y k x k xyz yz zx ezey kk ）（ 2 2 1 , 得得仍仍取取5 . 0 0 x 567627905452392060653070 100 .x

29、zy 上一页上一页 下一页下一页 返回返回 567143305672979056687030 211 .xzy 567143305671433056714330 322 .xzy . 附附近近的的根根在在求求方方程程50 xex x 例例7 7 32 为为平平方方收收敛敛； 法法则则为为线线性性收收敛敛若若可可以以证证明明steffensen,)(: kk xx 1 .steffensen ,)(,)()( 阶阶收收敛敛法法为为则则 阶阶导导数数连连续续的的阶阶收收敛敛为为若若 12 1 1 p pxppxx kk 上一页上一页 下一页下一页 返回返回 .steffensen ,)( 法法至至

30、少少为为平平方方收收敛敛 由由它它构构成成的的是是否否收收敛敛不不管管原原迭迭代代法法 kk xx 1 一一种种改改善善。迭迭代代法法是是对对原原迭迭代代法法的的所所以以，steffensen 33 .,发发散散之之间间，迭迭代代法法解解：在在区区间间121 3 1 kk xx 133 2 xx)( kkk kk kk kkkk xyz yz zx yzxy ）（ 2 11 2 1 33 , ，计计算算结结果果见见下下表表取取51 0 .x 上一页上一页 下一页下一页 返回返回 .)(steffensen的的实实根根迭迭代代法法求求方方程程用用01 3 xxxf例例8 8 现在用函数现在用函数

31、 构造构造steffensen迭代法迭代法, 1 3 xx)( k 0 1 5 6 xk 1.5 1.4162930 1.3247180 1.3247180 可见，可见，steffensen迭代法对这种不收敛的情形同样有效。迭代法对这种不收敛的情形同样有效。 34 3 一元方程的常用迭代法一元方程的常用迭代法 一、一、newton迭代法迭代法 设设x*是方程是方程f (x)=0的实根。取的实根。取 x0 x*，将将 f (x)在在 x0 做一阶做一阶 taylor展开展开: 2 0000 )( ! 2 )( )()()(xx f xxxfxfxf ， 在在 x0 和和 x 之间。之间。 将将

32、(x* x0)2 看成高阶小量，则有：看成高阶小量，则有： )*)()(*)(0 000 xxxfxfxf )( )( * 0 0 0 xf xf xx x y x* x0 )( )( 1 k k kk xf xf xx 上一页上一页 下一页下一页 返回返回 由图示，可见由图示，可见xk+1为函数为函数f (x)在点在点 xk处的切线与横坐标轴的交点，处的切线与横坐标轴的交点， 所以，所以，newton迭代法也称迭代法也称切线法切线法。 newton迭代格式迭代格式 35 则则牛牛顿顿迭迭代代格格式式为为将将原原方方程程化化为为解解, 0)( x exxf k k x x k kk e ex

33、xx 1 1 迭迭代代得得取取, 5 . 0 0 x 5671433. 05671431. 056631. 0 321 xxx 上一页上一页 下一页下一页 返回返回 与上一节例与上一节例7 7相比，牛顿法的收敛速度快很多。相比，牛顿法的收敛速度快很多。 . 附附近近的的根根在在求求方方程程50 xex x 例例9 9 36 上一页上一页 下一页下一页 返回返回 牛顿迭代法的流程图牛顿迭代法的流程图 37 牛顿迭代法的收敛性依赖于牛顿迭代法的收敛性依赖于x0 的选取。的选取。 x* x0 x0 x0 上一页上一页 下一页下一页 返回返回 38 定理定理 上一页上一页 下一页下一页 返回返回 .

34、*)( *)( *)( * lim *,newton *)(,*)(,*)( xf xf xx xx x xxfxfxf k k k 2 2 2 00 2 1 阶阶收收敛敛，并并且且 则则至至少少是是迭迭代代法法局局部部收收敛敛于于阶阶连连续续导导数数，若若有有 的的一一个个区区间间上上在在包包含含且且设设 （收敛的充分条件收敛的充分条件）设）设 f c2a, b，若，若 (1) f (a) f (b) 0； 则牛顿迭代法产生的序列则牛顿迭代法产生的序列 xk 收敛到收敛到f (x) 在在 a, b 的唯一根。的唯一根。 定理定理 的单根。的单根。是方程是方程即即这里这里000)(*,*)(,

35、*)(xfxxfxf 有根有根 根唯一根唯一 产生的序列单调产生的序列单调 有界，保证收敛。有界，保证收敛。 保证保证f (x) 上凸上凸 或下凸或下凸 39 上一页上一页 下一页下一页 返回返回 10 cx 0 40 q1: 若若 ，牛顿迭代法牛顿迭代法是否仍收敛？是否仍收敛？ 0*)(xf 设设 x* 是是 f 的的 m 重零点重零点, 则：则： 且且 )(*)()(xgxxxf m 0*)( xg )()()( )()( )( )( * * 1 kkk kk k k k kk xgxxxmg xgxx x xf xf xx a1: 有局部收敛性，但仅为线性收敛有局部收敛性，但仅为线性收敛

36、. . 下面介绍计算重根的牛顿迭代法下面介绍计算重根的牛顿迭代法 )()()( )()( )( * * xgxxxmg xgxx xx 其其迭迭代代函函数数为为： m x 1 1*)( 1*)(0 x 即得即得 上一页上一页 下一页下一页 返回返回 41 因此因此, ,求求f( (x)=0 )=0 之之m重根重根x* 等价于求等价于求 (x)=0 的单根的单根x* 。 )()( )()()( )()( )( )( )( * * * xqxx xgxxxmg xgxx xf xf x 令令 .0)(, 0 1 )( * 的的单单根根是是 xx m xq 而对而对 (x)=0用牛顿迭代法求根则是平

37、方收敛的用牛顿迭代法求根则是平方收敛的, ,其迭代格式为其迭代格式为 (7.19) )()()( )()( )( )( kkk kk k k k kk xfxfxf xfxf x x x xx 2 1 令令 ，则，则 f 的重零点就是的重零点就是 的单零点。的单零点。 )( )( )( xf xf x a2: 方法方法1：将求将求 f 的重零点转化为求另一函数的单零点。的重零点转化为求另一函数的单零点。 q2: 如何加速求重根的收敛速度？如何加速求重根的收敛速度？ 上一页上一页 下一页下一页 返回返回 42 方法方法2：采用如下迭代格式采用如下迭代格式 (7.18) )( )( k k kk

38、xf xf mxx 1 可以证明它是求可以证明它是求m重根重根 x*的具有平方收敛的迭代格式的具有平方收敛的迭代格式. 如何确定根的重数如何确定根的重数 m ? 令令三三个个相相邻邻的的迭迭代代值值为为用用牛牛顿顿迭迭代代格格式式所所得得，设设 , 12kkk xxx 21 1 kk kk k xx xx 则：则： 1 2 1 121 1 * 2 * 1 * 1 * 1 1 )()( )()( k k k k k k kk kk kk kk k e e e e e e ee ee xxxx xxxx m m m k k 11 1lim m m xx xx kk kk k 1 21 1 故故 k

39、 m 1 1 上一页上一页 下一页下一页 返回返回 43 例例11 用牛顿迭代法求方程用牛顿迭代法求方程 .95. 0013)1)sin(1()( 3 附附近近之之根根在在 xxxxxf 解解： kxkk1/(1- -k ) 00.95 10.9744279 20.9870583 30.99348780.50902.0369 40.99673280.50472.0190 50.99835760.50072.0028 60.99919010.51252.0511 .,95. 0 0 见见下下表表用用牛牛顿顿迭迭代代法法求求得得取取 k xx 上一页上一页 下一页下一页 返回返回 44 2 1 1

40、 k 199885590950 3210 xxxx.,. 得得 .用用牛牛顿顿法法迭迭代代公公式式收收敛敛速速度度大大大大快快于于直直接接 上一页上一页 下一页下一页 返回返回 用用迭迭代代格格式式重重根根所所求求根根为为可可知知,2m )( )( k k kk xf xf xx 2 1 45 例例12 用用3种方法求解方程种方法求解方程 . *)(2044 24 xxxxf的的二二重重根根 解解： k k kk x x xx 4 2 1 2 1 newton )(法法有有用用 上一页上一页 下一页下一页 返回返回 有有迭迭代代公公式式式式，用用21872m).( )( k k kk x x

41、xx 2 2 2 1 式式，有有迭迭代代公公式式用用).( )(1973 2 2 2 2 1 k kk kk x xx xx )( 都取都取x0= =1.5，计算结果见下表：，计算结果见下表： 46 方法（方法（2）和方法（）和方法（3）都是二阶方法，）都是二阶方法，x3都精确到了小数点都精确到了小数点 后第后第9位，方法（位，方法（1）即普通牛顿迭代法，解重根是一阶方法，）即普通牛顿迭代法，解重根是一阶方法， 要近要近30次迭代才能有相同的精度。次迭代才能有相同的精度。 xk方法（方法（1 1）方法（方法（2 2）方法（方法（3 3） x01.51.51.5 x11.458 333 3331

42、.416 666 6671.411 764 706 x21.436 607 1431.414 215 6861.414 211 438 x31.425 497 6191.414 213 5621.414 213 562 上一页上一页 下一页下一页 返回返回 09537356221341412 . 47 牛顿法的牛顿法的优点优点 收敛速度快收敛速度快 牛顿法的牛顿法的缺点缺点 每次迭代要计算一次导数值每次迭代要计算一次导数值 ，当，当 表达表达 式复杂或无明显表达式时求解困难。式复杂或无明显表达式时求解困难。 )( k x f )(xf 48 简化牛顿迭代法简化牛顿迭代法 得得中中的的牛牛顿顿迭迭代代公公