《数值分析第七章方程求根》由会员分享，可在线阅读，更多相关《数值分析第七章方程求根（84页珍藏版）》请在金锄头文库上搜索。
1、数数数 值值值 分分分 析析析Numerical Analysis数数数理理理学学学院院院School of Mathematics and Physics,第第第七七七章章章方方方程程程求求求根根根1根根根的的的搜搜搜索索索一一一 引引引言言言1. 问问问题题题的的的提提提出出出许许许多多多工工工程程程问问问题题题最最最终终终都都都化化化为为为非非非线线线性性性方方方程程程(组组组)f(x) = 0的的的求求求解解解问问问题题题. 本本本章章章主主主要要要介介介绍绍绍几几几个个个常常常用用用的的的求求求解解解非非非线线线性性性方方方程程程根根根的的的方方方法法法.2. 根根根的的的存存存在在
2、在性性性定定定理理理定定定理理理: 若若若f(x) Ca, b, f(a)f(b) 0, 则则则存存存在在在 (a, b), 使使使得得得f() = 0.13. 方方方程程程f(x) = 0求求求根根根的的的数数数值值值解解解法法法的的的基基基本本本思思思想想想(步步步骤骤骤)第第第一一一步步步: 求求求根根根的的的隔隔隔离离离区区区间间间.确确确定定定根根根所所所在在在的的的区区区间间间, 使使使方方方程程程在在在这这这个个个小小小区区区间间间内内内有有有且且且仅仅仅有有有一一一个个个根根根, 所所所得得得小小小区区区间间间称称称为为为方方方程程程的的的根根根的的的隔隔隔离离离区区区间间间或
3、或或有有有根根根区区区间间间. 显显显然然然所所所求求求隔隔隔离离离区区区间间间越越越小小小越越越好好好.第第第二二二步步步: 将将将根根根精精精确确确化化化.选选选用用用适适适当当当方方方法法法把把把第第第一一一步步步所所所得得得根根根的的的近近近似似似值值值精精精确确确化化化, 使使使其其其满满满足足足精精精度度度要要要求求求.说说说明明明: 隔隔隔离离离区区区间间间的的的确确确定定定方方方法法法(或或或初初初始始始近近近似似似值值值x0的的的确确确定定定方方方法法法):1) 作作作y = f(x)的的的草草草图图图, 由由由y = f(x)与与与横横横轴轴轴交交交点点点的的的大大大致致致
4、位位位置置置来来来确确确定定定.2) 将将将f(x) = 0改改改写写写成成成f1(x) = f2(x), 据据据y = f1(x)和和和y = f2(x)交交交点点点横横横坐坐坐标标标来来来确确确定定定根根根的的的隔隔隔离离离区区区间间间.3) 逐逐逐步步步搜搜搜索索索: 从从从a点点点出出出发发发, 选选选取取取适适适当当当的的的步步步长长长h, 比比比较较较f(a + ih)与与与f(a +(i + 1)h)的的的符符符号号号来来来确确确定定定根根根的的的隔隔隔离离离区区区间间间.2例例例题题题 考考考察察察方方方程程程f(x) = x3 x 1 = 0.注注注意意意到到到f(0) 0,
5、知知知f(x)在在在区区区间间间(0,2)内内内至至至少少少有有有一一一个个个实实实根根根, 试试试在在在区区区间间间(0, 2)内内内求求求一一一个个个适适适当当当的的的根根根的的的隔隔隔离离离区区区间间间.解解解:设设设从从从x = 0出出出发发发,取取取h = 0.5为为为步步步长长长向向向右右右进进进行行行根根根的的的搜搜搜索索索, 列列列表表表记记记录录录各各各个个个节节节点点点上上上函函函数数数值值值的的的符符符号号号(见见见下下下表表表)我我我们们们发发发现现现区区区间间间1.0, 1.5内内内必必必有有有一一一根根根.x00.51.01.5f(x)+说说说明明明: 在在在具具具
6、体体体运运运用用用上上上述述述方方方法法法时时时, 步步步长长长h的的的选选选择择择是是是个个个关关关键键键, 很很很明明明显显显,只只只要要要步步步长长长h取取取得得得足足足够够够小小小, 利利利用用用这这这种种种方方方法法法可可可以以以得得得到到到具具具有有有任任任意意意精精精度度度的的的近近近似似似根根根, 不不不过过过当当当h缩缩缩小小小时时时, 所所所要要要搜搜搜索索索的的的步步步数数数相相相应应应增增增多多多, 从从从而而而使使使计计计算算算量量量增增增大大大. 因因因此此此, 如如如果果果精精精度度度要要要求求求比比比较较较高高高, 单单单用用用这这这种种种逐逐逐步步步搜搜搜索索
7、索方方方法法法是是是不不不合合合算算算的的的. 下下下述述述二二二分分分法法法可可可以以以看看看作作作是是是逐逐逐步步步搜搜搜索索索方方方法法法的的的一一一种种种改改改进进进.3二二二 二二二分分分法法法1. 算算算法法法介介介绍绍绍设设设f(x)在在在区区区间间间a,b上上上连连连续续续, 且且且f(x) = 0在在在a,b区区区间间间上上上仅仅仅有有有一一一根根根,f(a) 6= 0,f(b) 6= 0, 则则则用用用二二二分分分法法法求求求方方方程程程f(x) = 0在在在a, b上上上的的的根根根的的的算算算法法法步步步骤骤骤如如如下下下:step1. 取取取x0= (a + b)/2
8、step2. 若若若f(a)f(x0) 0则则则f(x)的的的零零零点点点在在在区区区间间间x0,b上上上, 把把把x0看看看成成成新新新的的的a,即即即a := x0得得得新新新的的的区区区间间间a,b若若若f(a) f(x0) 0则则则b := x0若若若f(a) f(x0) = 0则则则x0为为为所所所求求求的的的根根根, 停停停机机机.step3. 若若若|b a| 2(为为为给给给定定定精精精度度度),则则则输输输出出出近近近似似似根根根为为为a+b2;否否否则则则转转转第第第一一一步步步.42. 算算算法法法分分分析析析1) 上上上面面面算算算法法法的的的1, 2步步步每每每执执执
9、行行行一一一次次次就就就把把把新新新的的的a, b区区区间间间分分分成成成两两两半半半, 根根根的的的范范范围围围也也也缩缩缩小小小了了了一一一半半半, 从从从而而而称称称为为为二二二分分分法法法, 与与与上上上面面面的的的求求求初初初始始始近近近似似似解解解中中中的的的搜搜搜索索索法法法不不不同同同, 在在在那那那里里里每每每搜搜搜索索索一一一次次次, 根根根的的的范范范围围围缩缩缩小小小步步步长长长h.2) 若若若给给给定定定近近近似似似解解解 x的的的误误误差差差为为为, 那那那么么么可可可以以以由由由原原原区区区间间间长长长度度度|b a|及及及不不不等等等式式式12k+1|b a|
10、大大大致致致定定定出出出算算算法法法执执执行行行的的的次次次数数数k log2|ba| 1.3) 二二二分分分法法法的的的工工工作作作量量量:主主主要要要在在在调调调用用用函函函数数数方方方面面面, 每每每执执执行行行一一一次次次, 调调调用用用函函函数数数f(x)一一一次次次.4) 优优优点点点: 简简简单单单, 可可可靠靠靠, 对对对f(x)的的的光光光滑滑滑性性性要要要求求求不不不高高高, 全全全局局局收收收敛敛敛.5) 缺缺缺点点点: 要要要求求求f(x)在在在a, b内内内是是是单单单实实实根根根, 不不不能能能求求求偶偶偶重重重根根根, 也也也不不不能能能求求求复复复根根根.5例例
11、例题题题 求求求方方方程程程f(x) = x3 x 1 = 0在在在区区区间间间1.0, 1.5内内内的的的一一一个个个实实实根根根, 要要要求求求准准准确确确到到到小小小数数数点点点后后后的的的第第第2位位位.解解解:这这这里里里a = 1.0,b = 1.5, 而而而f(a) 0.取取取a, b的的的中中中点点点x0= 1.25将将将区区区间间间二二二等等等分分分, 由由由于于于f(x0) 0, 即即即f(x0)与与与f(a)同同同号号号, 故故故所所所求求求的的的根根根x必必必在在在x0右右右侧侧侧, 这这这时时时应应应令令令a1= x0= 1.25,b1= b = 1.5, 而而而得得
12、得到到到新新新的的的有有有根根根区区区间间间a1, b1, 如如如此此此反反反复复复二二二分分分下下下去去去.我我我们们们现现现在在在预预预估估估所所所要要要二二二分分分的的的次次次数数数, 按按按误误误差差差估估估计计计|x xk| (bk ak)/2 = (b a)/2k+1只只只要要要二二二分分分6次次次(k = 6), 便便便能能能达达达到到到预预预定定定的的的精精精度度度|x x6| 0.005. 二二二分分分法法法的的的计计计算算算结结结果果果如如如下下下表表表.6kakbkxkf(xk)01.01.51.2511.251.375+21.3751.312531.31251.3438
13、+41.34381.3281+51.32811.320361.32031.324272迭迭迭代代代法法法一一一 迭迭迭代代代法法法的的的基基基本本本思思思想想想对对对于于于给给给定定定的的的方方方程程程f(x) = 0(1)如如如果果果我我我们们们将将将其其其改改改写写写为为为x = (x)(2)其其其中中中(x)连连连续续续. 在在在此此此基基基础础础上上上, 根根根据据据初初初始始始近近近似似似解解解x0, 我我我们们们可可可得得得到到到如如如下下下迭迭迭代代代公公公式式式xk+1= (xk), k = 0, 1, ,若若若上上上述述述迭迭迭代代代所所所得得得序序序列列列xk收收收敛敛敛于
14、于于x, 则则则由由由limkxk+1= limk(xk) x= (x)即即即我我我们们们得得得到到到x是是是方方方程程程(2)的的的一一一个个个根根根, 从从从而而而x是是是原原原方方方程程程(1)的的的一一一个个个根根根.8说说说明明明:1) 将将将方方方程程程f(x) = 0改改改写写写为为为x = (x), 总总总是是是可可可以以以实实实现现现的的的且且且实实实现现现方方方法法法不不不唯唯唯一一一.2) x0的的的确确确定定定可可可以以以通通通过过过求求求根根根的的的隔隔隔离离离区区区间间间得得得到到到, 也也也可可可在在在此此此基基基础础础上上上利利利用用用二二二分分分法法法得得得到
15、到到具具具有有有一一一定定定精精精度度度的的的近近近似似似解解解作作作为为为x0.二二二 相相相关关关的的的几几几个个个概概概念念念在在在刚刚刚才才才的的的基基基础础础上上上我我我们们们可可可以以以给给给出出出下下下面面面几几几个个个概概概念念念.1. 迭迭迭代代代公公公式式式: xk+1= (xk), k = 0,1,2,;2. 迭迭迭代代代函函函数数数: (x);3. 初初初始始始近近近似似似解解解: x0;4. 第第第k次次次近近近似似似解解解: xk;5. 迭迭迭代代代序序序列列列: xk.9引引引例例例 求求求方方方程程程f(x) = x3 x 1 = 0在在在x0= 1.5附附附近
16、近近的的的根根根x解解解: 方方方法法法一一一, 设设设将将将上上上述述述方方方程程程改改改写写写成成成下下下列列列形形形式式式x =3px + 1并并并据据据此此此建建建立立立迭迭迭代代代公公公式式式xk+1=3qxk+ 1, (k = 0,1,2,)下下下表表表记记记录录录了了了各各各步步步迭迭迭代代代的的的结结结果果果. 我我我们们们看看看到到到, 如如如果果果仅仅仅取取取6位位位有有有效效效数数数字字字, 那那那么么么结结结果果果x7与与与x8完完完全全全相相相同同同, 这这这时时时可可可以以以认认认为为为x7实实实际际际上上上已已已满满满足足足上上上述述述方方方程程程, 即即即为为为
17、所所所求求求的的的根根根.kxkkxk01.551.3247611.3572161.3247321.3308671.3247231.3208881.3247241.3249410方方方法法法二二二, 设设设将将将上上上述述述方方方程程程改改改写写写成成成下下下列列列形形形式式式x = x3 1并并并据据据此此此建建建立立立迭迭迭代代代公公公式式式xk+1= x3k 1, (k = 0,1,2,)由由由此此此迭迭迭代代代公公公式式式可可可得得得迭迭迭代代代结结结果果果如如如下下下表表表.k0123xk1.52.37512.39651904.01易易易见见见该该该迭迭迭代代代产产产生生生的的的序序
18、序列列列发发发散散散, 因因因此此此, 不不不能能能用用用此此此迭迭迭代代代得得得到到到原原原方方方程程程的的的根根根.11四四四 存存存在在在问问问题题题1. 如如如何何何选选选择择择初初初始始始近近近似似似解解解x0及及及迭迭迭代代代函函函数数数(x)才才才能能能保保保证证证迭迭迭代代代公公公式式式产产产生生生的的的序序序列列列xk收收收敛敛敛.2. 当当当序序序列列列xk收收收敛敛敛时时时, 如如如何何何估估估计计计k次次次近近近似似似解解解的的的误误误差差差, 即即即何何何时时时迭迭迭代代代可可可以以以中中中断断断.3. 若若若两两两个个个迭迭迭代代代均均均收收收敛敛敛, 如如如何何何
19、取取取舍舍舍?五五五 迭迭迭代代代法法法的的的理理理论论论基基基础础础定定定理理理1 (压压压缩缩缩映映映象象象不不不动动动点点点定定定理理理) 设设设迭迭迭代代代函函函数数数(x)在在在a, b上上上且且且满满满足足足1对对对任任任意意意x a, b有有有a (x) b,2存存存在在在正正正数数数L 1, 使使使得得得对对对任任任意意意x0, x00 a, b有有有|(x0) (x00)| L|x0 x00|,则则则有有有121) 方方方程程程x = (x)在在在a, b上上上唯唯唯一一一根根根x(x称称称为为为(x)的的的不不不动动动点点点)2) 对对对任任任意意意x0 a,b, 迭迭迭代
20、代代格格格式式式xk+1= (xk)收收收敛敛敛, 且且且 limkxk= x.3)|xk x| L1 L|xk xk1|, k = 1,2,4)|xk x| Lk1 L|x1 x0|, k = 1,2,5) 若若若0(x)存存存在在在, 则则则有有有limkx xk+1x xk= 0(x).13证证证明明明: 1) 令令令g(x) = x (x), 由由由1可可可得得得g(a) g(b) 0,故故故g(x) = 0在在在a, b内内内至至至少少少有有有一一一个个个根根根.又又又若若若x, y是是是x = (x)的的的两两两个个个互互互异异异的的的不不不动动动点点点, 由由由2有有有|(x)
21、(y)| L|x y| |(x) (y)| |x y|,矛矛矛盾盾盾, 故故故x = (x)在在在a, b内内内存存存在在在唯唯唯一一一根根根, 记记记为为为x.2) 由由由 x0 a, b及及及1知知知xk a, b, k = 1,2, 利利利用用用x= (x), xk+1= (xk)可可可得得得xk+1 x= (xk) (x), k = 1,2, ,由由由2可可可得得得 |xk+1 x| L|xk x|类类类推推推可可可得得得|xk x| Lk|x0 x|由由由 |L| 1得得得 limkxk= x.143)|xk+p xk|xk+p xk+p1| + |xk+p1 xk+p2| + +
22、|xk+1 xk|Lp|xk xk1| + Lp1|xk xk1| + + L|xk xk1|=L(1 Lp)1 L|xk xk1|令令令p 即即即得得得|xk x| L1 L|xk xk1|4) 由由由|xk xk1| Lk1|x1 x0|, 代代代入入入结结结论论论(3)可可可得得得|xk x| L1 L|xk xk1| Lk1 L|x1 x0|.5) 由由由x xk+1= (x) (xk)及及及导导导数数数0(x)存存存在在在, 知知知结结结论论论正正正确确确.15说说说明明明:1) 定定定理理理1的的的第第第3个个个结结结论论论|xk x| L1 L|xk xk1|为为为实实实际际际计
23、计计算算算提提提供供供了了了终终终止止止迭迭迭代代代的的的依依依据据据, 即即即当当当|xk xk1| 时时时, 可可可以以以认认认为为为xk x也也也基基基本本本达达达到到到精精精度度度要要要求求求, 这这这种种种估估估计计计误误误差差差的的的方方方法法法就就就是是是前前前面面面谈谈谈到到到的的的事事事后后后误误误差差差的的的估估估计计计.2) 可可可以以以由由由结结结论论论(4)大大大致致致估估估计计计出出出满满满足足足精精精度度度的的的迭迭迭代代代次次次数数数k(但但但由由由于于于L未未未知知知, 因因因此此此不不不太太太可可可行行行).3) 定定定理理理1又又又可可可称称称为为为全全全
24、局局局性性性收收收敛敛敛定定定理理理, 即即即在在在根根根的的的分分分隔隔隔区区区间间间内内内的的的任任任一一一初初初始始始近近近似似似解解解均均均能能能保保保证证证该该该迭迭迭代代代收收收敛敛敛.4) 显显显然然然L越越越小小小收收收敛敛敛速速速度度度越越越快快快.5) 若若若将将将|(x0)(x00)| L|x0x00|换换换成成成更更更强强强, 更更更便便便于于于应应应用用用的的的条条条件件件|0(x)| L 1,x a, b, 则则则上上上述述述定定定理理理仍仍仍然然然成成成立立立.162. 局局局部部部收收收敛敛敛定定定义义义及及及局局局部部部收收收敛敛敛性性性定定定理理理定定定义义
25、义1 若若若存存存在在在x的的的某某某个个个邻邻邻域域域 U : |x x| , 使使使迭迭迭代代代过过过程程程xk+1= (xk)对对对于于于任任任意意意初初初值值值x0 U均均均收收收敛敛敛, 则则则称称称迭迭迭代代代过过过程程程在在在根根根x邻邻邻近近近具具具有有有局局局部部部收收收敛敛敛性性性.定定定理理理2 设设设x为为为方方方程程程x = (x)的的的根根根, 0(x)在在在x的的的邻邻邻近近近连连连续续续, 且且且|0(x)| 1则则则迭迭迭代代代过过过程程程xk+1= (xk)在在在x邻邻邻近近近具具具有有有局局局部部部收收收敛敛敛性性性.证证证明明明: 由由由连连连续续续函函
26、函数数数的的的性性性质质质, 存存存在在在x的的的某某某个个个邻邻邻域域域U : |x x| , 使使使对对对于于于任任任意意意x U有有有|0(x)| L 1时时时称称称超超超线线线性性性收收收敛敛敛, p = 2时时时称称称平平平方方方收收收敛敛敛.2) 收收收敛敛敛速速速度度度定定定理理理定定定理理理 对对对于于于迭迭迭代代代过过过程程程xk+1= (xk), 如如如果果果(p)(x)在在在所所所求求求根根根x邻邻邻近近近连连连续续续,并并并且且且0(x) = 00(x) = = (p1)(x) = 0; (p)(x) 6= 0,则则则该该该迭迭迭代代代过过过程程程在在在点点点x邻邻邻近
27、近近是是是p阶阶阶收收收敛敛敛的的的.20证证证明明明:由由由于于于0(x) = 0, 据据据定定定理理理2立立立即即即可可可以以以断断断定定定迭迭迭代代代过过过程程程xk+1=(xk)具具具有有有局局局部部部收收收敛敛敛性性性.再再再将将将(xk)在在在根根根x处处处展展展开开开, 利利利用用用条条条件件件(p)(x) 6= 0则则则有有有(xk) = (x) +(p)()p!(xk x)p注注注意意意到到到(xk) = xk+1,(x) = x, 由由由上上上式式式可可可得得得xk+1x=(p)()p!(xkx)p因因因此此此迭迭迭代代代误误误差差差满满满足足足ek+1epk(p)(x)p
28、!.这这这表表表明明明迭迭迭代代代过过过程程程xk+1= (xk)确确确实实实为为为p阶阶阶收收收敛敛敛, 证证证毕毕毕.上上上述述述定定定理理理告告告诉诉诉我我我们们们, 迭迭迭代代代过过过程程程的的的收收收敛敛敛收收收敛敛敛速速速度度度依依依赖赖赖于于于迭迭迭代代代函函函数数数(x)的的的选选选取取取.如如如果果果当当当x a, b时时时0(x) 6= 0, 则则则迭迭迭代代代过过过程程程至至至多多多是是是线线线性性性收收收敛敛敛.21例例例题题题例例例1. 为为为求求求方方方程程程x3 x2 1 = 0在在在x = 1.5附附附近近近的的的一一一个个个根根根, 将将将方方方程程程改改改写
29、写写成成成下下下列列列等等等价价价形形形式式式, 并并并建建建立立立相相相应应应的的的迭迭迭代代代公公公式式式1) x = 1 + 1/x2, 迭迭迭代代代公公公式式式xk+1= 1 + 1/x2k;2) x3= 1 + x2, 迭迭迭代代代公公公式式式xk+1=3q1 + x2k;3) x2=1x1,迭迭迭代代代公公公式式式xk+1= 1/xk 1.试试试分分分析析析每每每种种种迭迭迭代代代公公公式式式的的的收收收敛敛敛性性性, 并并并选选选取取取一一一种种种公公公式式式求求求出出出具具具有有有四四四位位位有有有效效效数数数字字字的的的近近近似似似根根根.解解解: 1) 迭迭迭代代代函函函数
30、数数1(x) = 1 +1x2,01(x) = 2x3,01(1.5) 0.5926,|01(1.5)| 1,故故故迭迭迭代代代公公公式式式xk+1= 1 + 1/x2k在在在x0= 1.5附附附近近近局局局部部部收收收敛敛敛.222) 迭迭迭代代代函函函数数数2(x) = (1 + x2)13, 02(x) =2x3(1+x2)2/3,|02(1.5)| 0.4558 1, 故故故迭迭迭代代代公公公式式式xk+1= 1/xk 1在在在x0= 1.5附附附近近近发发发散散散.选选选取取取上上上述述述第第第二二二种种种迭迭迭代代代公公公式式式: xk+1=3q1 + x2k从从从x0= 1.5出
31、出出发发发可可可得得得如如如下下下数数数据据据表表表:kxkxk+1 xk01.511.481250.0187521.472710.0085431.468820.0038941.467050.0017751.466240.0008161.465880.00036 12 10323例例例2. 给给给定定定函函函数数数f(x),设设设对对对一一一切切切x, f0(x)存存存在在在且且且0 m f0(x) M,证证证明明明对对对于于于范范范围围围0 2/M内内内的的的任任任意意意定定定数数数, 迭迭迭代代代过过过程程程xk+1= xkf(xk)均均均收收收敛敛敛于于于f(x)的的的根根根x.证证证明
32、明明: 迭迭迭代代代函函函数数数(x) = x f(x), 0(x) = 1 f0(x), 利利利用用用m f0(x) M m f0(x) M M f0(x) m 1 M 1 f0(x) 1 m |1 f0(x)| max(|1 m|, |1 M|)从从从而而而|0(x)| = |1 f0(x)| max(|1 m|, |1 M|)下下下面面面估估估计计计|1 m|, |1 M|的的的大大大小小小.24一一一方方方面面面, 由由由0 2M 0 M 2 1 1 M 1 |1 M| 1.另另另一一一方方方面面面, 由由由0 m M M m 0 1 M 1 m 11 1 m 1 |1 m| 1故故故
33、有有有|0(x)| 1恒恒恒成成成立立立.25例例例3. 已已已知知知x = (x)在在在区区区间间间a,b内内内只只只有有有一一一根根根, 而而而当当当a x 1, 试试试问问问如如如何何何将将将x = (x)化化化为为为适适适于于于迭迭迭代代代的的的形形形式式式?解解解: 因因因为为为(1(x)0=10(x), 故故故当当当|0(x)| k 1时时时,|1(x)0| =flflflflfl10(x)flflflflfl 1, x a, b.因因因此此此, 将将将x = (x)改改改写写写成成成x = 1(x), 用用用它它它给给给出出出迭迭迭代代代公公公式式式xk+1= 1(xk), k
34、= 0,1,2,则则则迭迭迭代代代法法法是是是收收收敛敛敛的的的.26例例例4. 方方方程程程x = tanx, 试试试计计计算算算其其其在在在x0= 4.5弧弧弧度度度附附附近近近的的的根根根.利利利用用用上上上述述述结结结论论论应应应将将将上上上述述述方方方程程程改改改成成成等等等价价价的的的形形形式式式x = arctanx + 相相相应应应的的的收收收敛敛敛的的的迭迭迭代代代公公公式式式为为为xk+1= + arctanxk,迭迭迭代代代可可可得得得下下下表表表kxkkxkkxk04.534.4934101564.49340945814.49372003544.49340949174.
35、49340945824.49342411354.4934094627六六六 迭迭迭代代代公公公式式式的的的加加加工工工1. Aitken 加加加速速速法法法及及及Steffensen 迭迭迭代代代法法法1) 方方方法法法思思思想想想及及及Aitken加加加速速速法法法与与与Steffensen 迭迭迭代代代法法法由由由limkxk+1 xxk x= 0(x)可可可得得得, 当当当k适适适当当当大大大时时时, 有有有xk+2 xxk+1 xxk+1 xxk x由由由此此此解解解出出出xxkxk+2 x2k+1xk+2 2xk+1+ xk由由由此此此可可可以以以将将将一一一个个个已已已知知知的的的
36、序序序列列列xk, 转转转换换换成成成一一一个个个新新新的的的序序序列列列x0k:28x0k=xkxk+2 x2k+1xk+2 2xk+1+ xk这这这就就就是是是Aitken加加加速速速法法法.若若若将将将xk+1= (xk), xk+2= (xk+1) = (xk)代代代入入入得得得xxk(xk) (xk)2(xk) 2(xk) + xk把把把上上上式式式右右右端端端的的的值值值作作作为为为新新新的的的近近近似似似值值值xk+1, 于于于是是是我我我们们们得得得到到到一一一个个个新新新的的的迭迭迭代代代格格格式式式xk+1= (xk), k = 0,1,2,其其其中中中(x) =x(x)
37、(x)2(x) 2(x) + x上上上述述述迭迭迭代代代公公公式式式xk+1= (xk)也也也可可可写写写成成成如如如下下下形形形式式式29(I) xk+1= (xk) xk+1= ( xk+1)xk+1= xk+1( xk+1 xk+1)2 xk+1 2 xk+1+ xk或或或(II) xk+1= (xk) xk+1= ( xk+1)xk+1= xk( xk+1 xk)2 xk+1 2 xk+1+ xk上上上述述述处处处理理理(迭迭迭代代代)过过过程程程通通通常常常称称称作作作为为为Steffensen 迭迭迭代代代法法法.302) 算算算法法法分分分析析析(1) 用用用罗罗罗必必必塔塔塔法
38、法法则则则可可可以以以证证证明明明: 若若若x是是是(x) = x的的的根根根, 且且且(x)在在在x的的的附附附近近近存存存在在在一一一阶阶阶连连连续续续导导导数数数, 则则则x是是是方方方程程程x = (x)的的的根根根. 即即即x是是是(x)的的的不不不动动动点点点, 则则则x也也也是是是x = (x)的的的不不不动动动点点点. 反反反之之之亦亦亦然然然.(2) 收收收敛敛敛性性性定定定理理理: 设设设在在在x附附附近近近(x)有有有p + 1阶阶阶连连连续续续导导导数数数, 则则则对对对一一一个个个充充充分分分靠靠靠近近近x的的的初初初始始始值值值x0, 有有有1如如如果果果迭迭迭代代
39、代格格格式式式xk+1= (xk)是是是线线线性性性收收收敛敛敛的的的, 则则则格格格式式式xk+1= (xk)是是是二二二阶阶阶收收收敛敛敛的的的.2如如如果果果迭迭迭代代代格格格式式式xk+1= (xk)是是是p(p 2)阶阶阶收收收敛敛敛的的的, 则则则迭迭迭代代代格格格式式式xk+1=(xk)是是是2p 1阶阶阶收收收敛敛敛的的的.31例例例题题题 用用用Steffensen方方方法法法求求求解解解方方方程程程f(x) = x3 x 1 = 0.解解解: 前前前面面面我我我们们们曾曾曾经经经指指指出出出, 求求求解解解这这这一一一方方方程程程的的的下下下述述述迭迭迭代代代公公公式式式是
40、是是发发发散散散的的的:xk+1= x3k 1,我我我们们们现现现在在在以以以这这这种种种迭迭迭代代代公公公式式式为为为基基基础础础形形形成成成Steffensen算算算法法法: xk+1=x3k 1; xk+1= x3k+1 1;xk+1= xk+1( xk+1 xk+1)2 xk+1 2 xk+1+ xk仍仍仍然然然取取取x0= 1.5, 计计计算算算结结结果果果如如如下下下表表表32k xk xkxk01.512.3750012.39651.4162921.840925.238881.3556531.491402.317281.3289541.347101.444351.3248051.
41、325181.327141.32472我我我们们们看看看到到到, 将将将发发发散散散的的的迭迭迭代代代公公公式式式化化化通通通过过过Steffensen方方方法法法处处处理理理后后后, 竟竟竟获获获得得得了了了相相相当当当好好好的的的收收收敛敛敛性性性.333 牛牛牛顿顿顿法法法一一一 Newton法法法的的的主主主要要要思思思想想想Newton法法法是是是一一一种种种迭迭迭代代代法法法, 在在在已已已知知知方方方程程程f(x) = 0的的的第第第k次次次近近近似似似解解解xk时时时, Newton法法法是是是利利利用用用y =f(x)在在在xk处处处 的的的 切切切 线线线 来来来 近近近
42、似似似 曲曲曲线线线y = f(x), 把把把切切切线线线与与与x轴轴轴的的的交交交点点点xk+1作作作为为为y = f(x)与与与x轴轴轴的的的交交交点点点x的的的第第第k + 1次次次近近近似似似, 由由由此此此得得得到到到方方方程程程f(x) = 0根根根的的的第第第k +1次次次近近近似似似. 如如如图图图1 所所所示示示.图图图134二二二 Newton法法法的的的算算算法法法步步步骤骤骤Step 1. 通通通过过过求求求根根根的的的隔隔隔离离离区区区间间间或或或二二二分分分法法法手手手段段段选选选取取取x0作作作为为为初初初始始始近近近似似似解解解.Step 2. 确确确定定定xk
43、+1用用用f(x)在在在xk点点点的的的一一一阶阶阶泰泰泰勒勒勒展展展开开开式式式作作作为为为f(x)近近近似似似, 即即即f(x) f(xk) + f0(xk)(x xk),方方方程程程f(xk)+f0(xk)(xxk) = 0的的的根根根作作作为为为方方方程程程f(x) = 0根根根的的的第第第k+1次次次近近近似似似xk+1, 由由由此此此可可可得得得xk+1= xkf(xk)f0(xk).Step 3. 若若若|xk+1xk| eps或或或|f(xk+1)| eps, 则则则打打打印印印近近近似似似解解解xk+1,否否否则则则转转转第第第2步步步.35三三三 算算算法法法分分分析析析1
44、. 收收收敛敛敛性性性定定定理理理 设设设f(x)在在在x的的的某某某一一一邻邻邻域域域内内内具具具有有有三三三阶阶阶连连连续续续导导导数数数, 则则则Newton法法法不不不论论论x是是是f(x) = 0的的的单单单根根根, 还还还是是是m重重重根根根均均均是是是局局局部部部收收收敛敛敛的的的且且且对对对单单单根根根是是是二二二阶阶阶收收收敛敛敛的的的, 对对对重重重根根根是是是一一一阶阶阶收收收敛敛敛的的的.证证证明明明: 易易易见见见牛牛牛顿顿顿法法法的的的迭迭迭代代代函函函数数数为为为(x) = x f(x)f0(x).因因因此此此有有有:0(x) = 1 f0(x)2 f00(x)f
45、(x)f0(x)2=f(x)f00(x)f0(x)200(x) = f(x) f00(x)(f0(x)20= f0(x) f00(x)(f0(x)2+ f(x)f00(x)(f0(x)20361) 当当当x是是是f(x) = 0的的的单单单根根根时时时, 则则则有有有f(x) = (x x)g(x), 其其其中中中 g(x) 6= 0,故故故有有有f0(x) = g(x) + (x x)g0(x),于于于是是是f0(x) = g(x) 6= 0,所所所以以以0(x) =f(x)f00(x)f0(x)2= 0,00(x) =f00(x)f0(x)一一一般般般地地地00(x) 6= 0故故故牛牛牛
46、顿顿顿法法法对对对单单单根根根是是是二二二阶阶阶局局局部部部收收收敛敛敛的的的.372) 当当当x是是是f(x) = 0的的的m(m 2)重重重根根根时时时, 则则则有有有f(x) = (x x)mg(x),其其其中中中 g(x) 6= 0.因因因此此此f0(x) = m(x x)m1g(x) + (x x)mg0(x)相相相应应应的的的迭迭迭代代代函函函数数数可可可以以以化化化为为为:(x)=x f(x)f0(x)=x (x x)mg(x)m(x x)m1g(x) + (x x)mg0(x)=x (x x)g(x)mg(x) + (x x)g0(x)38因因因此此此,0(x)=limxx(x
47、) (x)x x=limxxx (xx)g(x)mg(x)+(xx)g0(x) xx x=limxx1 g(x)mg(x) + (x x)g0(x)=1 1m由由由此此此得得得:|0(x)| 0都都都是是是收收收敛敛敛的的的.事事事实实实上上上, 由由由迭迭迭代代代公公公式式式可可可得得得:xk+1C =(xkC)22xk;xk+1+C =(xk+C)22xk.42以以以上上上两两两式式式相相相除除除得得得xk+1Cxk+1+C=xkCxk+C#2据据据此此此反反反复复复递递递推推推有有有xkCxk+C=x0Cx0+C#2k记记记q =x0Cx0+C, 整整整理理理上上上式式式, 得得得xkC
48、 = 2Cq2k1 q2k.对对对任任任意意意x0 0, 总总总有有有|q| 1, 故故故由由由上上上式式式推推推知知知, 当当当k 时时时xkC, 即即即迭迭迭代代代过过过程程程恒恒恒收收收敛敛敛.43特特特别别别地地地, 我我我们们们利利利用用用上上上述述述方方方法法法求求求115.解解解:取取取初初初值值值x0= 10, 对对对C = 115由由由迭迭迭代代代公公公式式式xk+1=12(xk+Cxk)迭迭迭代代代3次次次便便便得得得到到到精精精度度度为为为106的的的结结结果果果(见见见下下下表表表).k01234xk1010.75000010.72383710.72380510.723
49、80544例例例3. 对对对于于于给给给定定定的的的正正正数数数C, 应应应用用用牛牛牛顿顿顿法法法于于于方方方程程程1xC = 0, 可可可导导导出出出求求求1/C而而而不不不用用用除除除法法法的的的迭迭迭代代代公公公式式式:xk+1= xk(2 Cxk).试试试证证证明明明: 当当当初初初值值值x0满满满足足足0 x02C时时时, 迭迭迭代代代是是是收收收敛敛敛的的的.证证证明明明: 由由由于于于xk+11C= xk(2 Cxk) 1C= C(xk1C)2两两两边边边同同同乘乘乘C, 并并并令令令rk= 1 Cxk可可可得得得递递递推推推公公公式式式rk+1= r2k.由由由此此此有有有r
50、k= r2k0若若若初初初值值值满满满足足足0 x02C, 则则则对对对r0= 1 Cx0有有有|r0| 1),g(x)在在在x处处处可可可导导导, 证证证明明明:迭迭迭代代代公公公式式式xn+1= xn qf(xn)f0(xn),n = 0,1,2,在在在根根根x附附附近近近具具具有有有二二二阶阶阶的的的收收收敛敛敛速速速度度度.证证证明明明: 设设设(x) = x qf(x)f0(x), 则则则(x)=x q(x x)g(x)(x x)g0(x) + qg(x)=x (x x)qg(x)(x x)g0(x) + qg(x)460(x) = 1qg(x)(x x)g0(x) + qg(x)(
51、xx)(qg(x)(x x)g0(x) + qg(x)0故故故0(x) = 1 qg(x)qg(x)= 1 1 = 0故故故迭迭迭代代代格格格式式式局局局部部部收收收敛敛敛. 此此此外外外, 由由由于于于00(x)=2(qg(x)(x x)g0(x) + qg(x)0|x=x=2g0(x)/qg(x) 6= 0故故故上上上式式式迭迭迭代代代公公公式式式在在在x附附附近近近具具具有有有二二二阶阶阶收收收敛敛敛速速速度度度.47例例例5. 研研研究究究求求求a的的的牛牛牛顿顿顿公公公式式式xk+1=12(xk+axk),x0 0证证证明明明对对对一一一切切切k = 1,2, 有有有xka且且且序序
52、序列列列x1,x2,是是是递递递减减减的的的.证证证明明明: 易易易见见见xk 0, 由由由xk+1=12(xk+axk)知知知xk+1122sxkaxk=a.另另另一一一方方方面面面xk+1 xk=12(axk xk) =a x2k2xk 0.故故故结结结论论论成成成立立立.48例例例6. 对对对于于于f(x) = 0的的的牛牛牛顿顿顿公公公式式式xk+1= xk f(xk)/f0(xk)证证证明明明Rk= (xk xk1)/(xk1 xk2)2收收收敛敛敛到到到f00(x)/(2f0(x), 这这这里里里x为为为f(x) = 0的的的根根根, f(x)具具具有有有二二二阶阶阶连连连续续续导
53、导导数数数.证证证明明明:Rk=(x xk1) (x xk)(x xk1) (x xk2)2=(x xk1)/(x xk2)2 (x xk)/(x xk2)2(x xk1)/(x xk2) 1249由由由(xk+1 x)/(x xk)2=(xk x)(1 f0(x)+12f00()(xkx)f0(xk)(xk x)2=f0(xk) f0(x)(xk x)f0(xk)f00()2f0(xk)xkxf00(x)f0(x)12f00(x)f0(x)=12f00(x)f0(x)6= 得得得xk+1 x(xk x) 0, (k )50并并并注注注意意意xk x(x xk2)2=x xk(x xk1)x
54、xk1(x xk2)2 0代代代入入入Rk即即即得得得结结结论论论.例例例7. 试试试就就就下下下列列列函函函数数数讨讨讨论论论牛牛牛顿顿顿法法法的的的收收收敛敛敛性性性和和和收收收敛敛敛速速速度度度:1) f(x) =(x,x 0x,x 02) f(x) =3px2,x 03px2,x 051解解解:1) 当当当x 0时时时, f(x) =x,其其其牛牛牛顿顿顿迭迭迭代代代函函函数数数(x) = x x12x= x当当当x 0时时时, f(x) = x,其其其牛牛牛顿顿顿迭迭迭代代代函函函数数数(x) = x x12x= x则则则迭迭迭代代代公公公式式式xk+1= (xk) = xk,k =
55、 0,1,2故故故对对对f(x) = 0, 其其其牛牛牛顿顿顿迭迭迭代代代公公公式式式发发发散散散.522) 类类类似似似可可可得得得迭迭迭代代代公公公式式式为为为xk+1= xk2, k = 0, 1, 2, 收收收敛敛敛, 但但但只只只是是是线线线性性性收收收敛敛敛速速速度度度(x= 0, xk+1 x= 0.5(xk x).思思思考考考: 为为为什什什么么么Newton法法法用用用于于于此此此方方方程程程得得得不不不到到到二二二阶阶阶收收收敛敛敛速速速度度度?53五五五 牛牛牛顿顿顿下下下山山山法法法前前前面面面已已已经经经讨讨讨论论论过过过牛牛牛顿顿顿法法法的的的局局局部部部收收收敛敛
56、敛性性性. 一一一般般般地地地说说说, 牛牛牛顿顿顿法法法的的的收收收敛敛敛性性性依依依赖赖赖于于于初初初值值值x0的的的选选选取取取, 如如如果果果x0偏偏偏离离离所所所求求求的的的根根根x比比比较较较远远远, 则则则牛牛牛顿顿顿法法法可可可能能能发发发散散散.例例例如如如, 用用用牛牛牛顿顿顿法法法求求求方方方程程程x3 x 1 = 0在在在x = 1.5附附附近近近的的的一一一个个个根根根x.设设设取取取迭迭迭代代代初初初值值值x0= 1.5, 用用用牛牛牛顿顿顿公公公式式式xk+1= xkx3k xk 13x2k 154计计计算算算得得得x1= 1.34783, x2= 1.32520
57、, x3= 1.32472.迭迭迭代代代3次次次得得得到到到的的的结结结果果果x3有有有6位位位有有有效效效数数数字字字.但但但是是是, 如如如果果果改改改用用用x0= 0.6作作作为为为迭迭迭代代代初初初值值值, 则则则依依依牛牛牛顿顿顿公公公式式式xk+1= xkx3k xk 13x2k 1迭迭迭代代代一一一次次次得得得x1= 17.9.这这这个个个结结结果果果反反反而而而比比比x0= 0.6更更更偏偏偏离离离了了了所所所求求求的的的根根根x= 1.32472.为为为了了了防防防止止止迭迭迭代代代发发发散散散, 我我我们们们对对对迭迭迭代代代过过过程程程再再再附附附加加加一一一项项项要要要
58、求求求, 即即即具具具有有有单单单调调调性性性:|f(xk+1)| |f(xk)|满满满足足足这这这项项项要要要求求求的的的算算算法法法称称称为为为下下下山山山法法法.55我我我们们们将将将牛牛牛顿顿顿法法法与与与下下下山山山法法法结结结合合合起起起来来来使使使用用用, 即即即在在在下下下山山山法法法保保保证证证函函函数数数值值值稳稳稳定定定下下下降降降的的的前前前提提提下下下, 用用用牛牛牛顿顿顿法法法加加加快快快收收收敛敛敛速速速度度度. 为为为此此此, 我我我们们们将将将牛牛牛顿顿顿法法法的的的计计计算算算结结结果果果 xk+1= xkf(xk)f0(xk)与与与前前前一一一步步步的的的
59、近近近似似似值值值xk适适适当当当加加加权权权平平平均均均作作作为为为新新新的的的改改改进进进值值值xk+1= xk+1+ (1 )xk其其其中中中(0 1)称称称下下下山山山因因因子子子. 我我我们们们希希希望望望挑挑挑选选选下下下山山山因因因子子子, 使使使单单单调调调条条条件件件|f(xk+1)| |f(xk)|成成成立立立.下下下山山山因因因子子子的的的选选选择择择是是是个个个逐逐逐步步步探探探索索索的的的过过过程程程. 设设设从从从 = 1开开开始始始反反反复复复将将将减减减半半半进进进行行行试试试算算算, 如如如果果果能能能定定定出出出值值值使使使单单单调调调条条条件件件成成成立立
60、立, 则则则称称称下下下山山山成成成功功功. 与与与此此此相相相反反反,如如如果果果把把把在在在上上上述述述过过过程程程中中中找找找不不不到到到使使使条条条件件件成成成立立立的的的下下下山山山因因因子子子, 则则则称称称下下下山山山失失失败败败.这这这时时时需需需另另另选选选初初初值值值x0重重重算算算.564 弦弦弦截截截法法法与与与抛抛抛物物物线线线法法法一一一 问问问题题题提提提出出出上上上一一一节节节介介介绍绍绍的的的牛牛牛顿顿顿法法法, 它它它在在在求求求xk+1时时时不不不但但但要要要求求求给给给出出出函函函数数数值值值f(xk), 而而而且且且要要要求求求提提提供供供导导导数数数
61、值值值f0(xk). 当当当函函函数数数f比比比较较较复复复杂杂杂时时时, 提提提供供供它它它的的的导导导数数数值值值, 往往往往往往是是是有有有困困困难难难的的的. 我我我们们们现现现在在在设设设法法法多多多利利利用用用一一一些些些函函函数数数值值值f(xk),f(xk1),来来来回回回避避避导导导数数数值值值f0(xk)的的的计计计算算算.二二二 方方方法法法思思思想想想设设设xk,xk1, ,xkr是是是f(x) = 0的的的一一一组组组近近近似似似根根根, 我我我们们们利利利用用用函函函数数数值值值f(xk),f(xk1), f(xkr),构构构造造造插插插值值值多多多项项项式式式Pr
62、(x), 并并并适适适当当当选选选取取取Pr(x) = 0的的的一一一个个个根根根作作作为为为f(x) =0的的的新新新的的的近近近似似似根根根xk+1, 这这这就就就确确确定定定了了了一一一个个个迭迭迭代代代过过过程程程, 记记记迭迭迭代代代函函函数数数为为为:xk+1= (xk,xk1, ,xkr)57三三三 弦弦弦截截截法法法1. 算算算法法法介介介绍绍绍设设设xk, xk1是是是f(x)的的的近近近似似似根根根, 我我我们们们利利利用用用f(xk), f(xk1)构构构造造造一一一次次次插插插值值值多多多项项项式式式P1(x), 并并并用用用P1(x) = 0的的的根根根作作作为为为f
63、(x) = 0的的的新新新的的的近近近似似似根根根xk+1. 由由由于于于P1(x) = f(xk) +f(xk) f(xk1)xk xk1(x xk)因因因此此此有有有xk+1= xkf(xk)f(xk) f(xk1)(xk xk1)(3)说说说明明明: 这这这样样样导导导出出出的的的迭迭迭代代代公公公式式式可可可以以以看看看作作作牛牛牛顿顿顿公公公式式式xk+1= xkf(xk)f0(xk)中中中的的的导导导数数数f0(x)用用用差差差商商商f(xk)f(xk1)xkxk1取取取代代代的的的结结结果果果.582. 算算算法法法的的的几几几何何何解解解释释释现现现 在在在 解解解 释释释 这
64、这这 种种种 迭迭迭 代代代 过过过 程程程 的的的 几几几 何何何 意意意义义义.如如如图图图2, 曲曲曲线线线y = f(x)上上上横横横坐坐坐标标标为为为xk,xk1的的的点点点分分分别别别记记记为为为Pk,Pk1, 则则则弦弦弦(割割割线线线)PkPk1的的的斜斜斜率率率等等等于于于差差差商商商值值值f(xk) f(xk1)xk xk1.其其其方方方程程程是是是y = f(xk)+f(xk) f(xk1)xk xk1(xxk)因因因此此此按按按(3)式式式求求求得得得的的的xk+1实实实际际际上上上是是是弦弦弦线线线PkPk1与与与x轴轴轴交交交点点点的的的横横横坐坐坐标标标.这这这种
65、种种算算算法法法因因因此此此称称称为为为弦弦弦截截截法法法.图图图2593. 与与与牛牛牛顿顿顿法法法的的的关关关系系系弦弦弦截截截法法法与与与牛牛牛顿顿顿法法法都都都是是是线线线性性性化化化方方方法法法, 但但但两两两者者者有有有本本本质质质的的的区区区别别别.牛牛牛顿顿顿切切切线线线法法法在在在计计计算算算xk+1时时时只只只用用用到到到前前前一一一步步步的的的值值值xk, 是是是单单单步步步方方方法法法.而而而弦弦弦截截截法法法(3)在在在求求求xk+1时时时要要要用用用到到到前前前面面面两两两步步步的的的结结结果果果xk,xk1, 是是是两两两步步步方方方法法法. 因因因此此此使使使用
66、用用这这这种种种方方方法法法必必必须须须先先先给给给出出出两两两个个个初初初始始始值值值x0,x1, 而而而且且且后后后者者者没没没有有有用用用到到到函函函数数数的的的导导导数数数.604. 算算算法法法分分分析析析1) 收收收敛敛敛速速速度度度定定定理理理假假假设设设f(x)在在在根根根x的的的邻邻邻域域域 : |x x| 内内内具具具有有有二二二阶阶阶连连连续续续导导导数数数,且且且对对对任任任意意意x 有有有f06= 0, 又又又初初初值值值x0,x1 , 那那那么么么当当当邻邻邻域域域半半半径径径充充充分分分小小小时时时,弦弦弦截截截法法法(3)将将将按按按阶阶阶p =1+52 1.6
67、18收收收敛敛敛到到到根根根x.证证证明明明:为为为使使使迭迭迭代代代过过过程程程不不不致致致中中中断断断, 我我我们们们首首首先先先需需需要要要保保保证证证一一一切切切迭迭迭代代代值值值xk全全全属属属于于于. 用用用数数数学学学归归归纳纳纳法法法证证证明明明.首首首先先先证证证明明明当当当xk1,xk 时时时xk+1必必必属属属于于于.记记记P1(x)是是是以以以xk1,xk为为为节节节点点点的的的插插插值值值多多多项项项式式式, 注注注意意意到到到f(x) = 0, 据据据插插插值值值余余余项项项公公公式式式f(x) P1(x) =f00(1)2(x xk)(x xk1)知知知61P1(
68、x) = f00(1)2(x xk)(x xk1) = f00(1)2ekek1式式式中中中ek= xk x表表表示示示迭迭迭代代代误误误差差差.另另另一一一方方方面面面, 由由由于于于xk+1是是是P1(x) = 0的的的根根根, 故故故P1(x)=P1(x) P1(xk+1) = P01()(x xk+1)=f(xk) f(xk+1)xk xk1(x xk+1) = f0(2)ek+1上上上面面面两两两个个个式式式子子子联联联立立立给给给出出出ek+1=f00(1)2f0(2)ekek1(4)由由由于于于1,2均均均在在在xk1,xk与与与x所所所界界界定定定的的的范范范围围围内内内, 当
69、当当xk1,xk 时时时必必必有有有1,2 .62记记记M =maxx|f00(x)|2 minx|f0(x)|我我我们们们选选选取取取邻邻邻域域域半半半径径径充充充分分分小小小, 以以以保保保证证证M 1, 则则则当当当xk1与与与xk属属属于于于时时时,按按按(4)式式式有有有|ek+1| M|ek| |ek1| M (5)于于于是是是xk+1 . 注注注意意意到到到已已已经经经假假假定定定x0,x1 , 从从从而而而一一一切切切xk全全全属属属于于于.另另另外外外, 据据据递递递推推推不不不等等等式式式(5)易易易知知知M|ek+1| M2|ek|ek1|,k = 1,2, ,于于于是是
70、是有有有M|ek| M2|ek1|ek2|,63两两两式式式相相相乘乘乘可可可得得得|ek+1|M2|ek1|2|ek2|(M)3/M.类类类似似似的的的, 可可可以以以得得得到到到|ek| 1M(M)k.故故故当当当k 时时时有有有ek 0, 收收收敛敛敛性性性得得得证证证.进进进一一一步步步确确确定定定收收收敛敛敛的的的阶阶阶, 当当当k充充充分分分大大大时时时,按按按(4)式式式有有有|ek+1| M|ek| |ek1|, M= |f00(x)2f0(x)|(6)64设设设方方方法法法的的的收收收敛敛敛阶阶阶为为为p, 即即即limk|ek+1|ek|p= C(7)由由由此此此有有有|e
71、k1| C1|ek|1/p, C1= C1/p.带带带入入入(6)式式式可可可得得得|ek+1| MC1|ek|1+1/p.由由由此此此可可可得得得p 1 + 1/p, 解解解得得得p 1.618.这这这说说说明明明弦弦弦截截截法法法收收收敛敛敛的的的阶阶阶p 1.618.2) 工工工作作作量量量:每每每次次次迭迭迭代代代的的的工工工作作作量量量主主主要要要是是是调调调用用用f(x)一一一次次次.65例例例题题题例例例1. 用用用弦弦弦截截截法法法解解解方方方程程程f(x) = xex 1 = 0.解解解: 设设设取取取x0= 0.5, x1= 0.6作作作为为为开开开始始始值值值, 用用用弦
72、弦弦截截截法法法求求求得得得的的的结结结果果果见见见下下下表表表k01234xk0.50.60.565320.567090.56714与与与牛牛牛顿顿顿法法法的的的计计计算算算结结结果果果进进进行行行比比比较较较可可可以以以看看看出出出,弦弦弦截截截法法法的的的收收收敛敛敛速速速度度度也也也是是是相相相当当当快快快的的的.66四四四 抛抛抛物物物线线线法法法1. 算算算法法法介介介绍绍绍设设设已已已知知知方方方程程程f(x) = 0的的的三三三个个个近近近似似似根根根xk, xk1, xk2, 我我我们们们以以以这这这三三三点点点为为为节节节点点点构构构造造造二二二次次次插插插值值值多多多项项
73、项式式式P2(x), 并并并适适适当当当选选选取取取P2(x)的的的一一一个个个零零零点点点xk+1作作作为为为新新新的的的近近近似似似根根根, 这这这样样样确确确定定定的的的迭迭迭代代代过过过程程程称称称抛抛抛物物物线线线法法法, 亦亦亦称称称密密密勒勒勒法法法. 在在在几几几何何何图图图形形形上上上, 这这这种种种方方方法法法的的的基基基本本本思思思想想想是是是用用用抛抛抛物物物线线线y = P2(x)与与与x轴轴轴的的的交交交点点点xk+1作作作为为为所所所求求求根根根x的的的近近近似似似位位位置置置.现现现在在在推推推导导导抛抛抛物物物线线线法法法的的的计计计算算算公公公式式式. 插插
74、插值值值多多多项项项式式式P2(x) = f(xk)+fxk, xk1(xxk)+fxk, xk1, xk2(xxk)(xxk1)有有有两两两个个个零零零点点点xk+1= xk2f(xk) q2 4f(xk)fxk, xk1, xk2,(8)67式式式中中中 = fxk, xk1 + fxk, xk1, xk2(xk xk1).为为为了了了从从从(8)式式式定定定出出出一一一个个个值值值xk+1, 我我我们们们需需需要要要讨讨讨论论论根根根式式式前前前正正正负负负号号号的的的取取取舍舍舍问问问题题题.在在在xk, xk1, xk2三三三个个个近近近似似似根根根中中中, 自自自然然然假假假定定定
75、以以以xk更更更接接接近近近所所所求求求的的的根根根x, 这这这时时时, 为为为了了了保保保证证证需需需要要要精精精度度度, 我我我们们们选选选式式式(8)中中中较较较接接接近近近xk的的的一一一个个个值值值作作作为为为新新新的的的近近近似似似根根根xk+1, 为为为此此此, 只只只要要要令令令根根根式式式前前前的的的符符符号号号与与与的的的符符符号号号相相相同同同即即即可可可.2. 算算算法法法分分分析析析在在在一一一定定定条条条件件件下下下可可可以以以证证证明明明, 对对对于于于抛抛抛物物物线线线法法法, 迭迭迭代代代误误误差差差有有有下下下列列列渐渐渐近近近关关关系系系式式式|ek+1|
76、ek|1.840flflflflflf000(x)6f0(x)flflflflfl0.42,可可可见见见抛抛抛物物物线线线法法法也也也是是是超超超线线线性性性收收收敛敛敛的的的, 其其其收收收敛敛敛的的的阶阶阶p = 1.840, 收收收敛敛敛速速速度度度比比比弦弦弦截截截法法法更更更接接接近近近于于于牛牛牛顿顿顿法法法.68例例例题题题例例例1. 用用用抛抛抛物物物线线线法法法求求求解解解方方方程程程f(x) = xex 1 = 0.解解解: 利利利用用用下下下表表表k01234xk0.50.60.565320.567090.56714中中中的的的前前前三三三个个个值值值x0= 0.5, x
77、1= 0.6, x2= 0.56532作作作为为为开开开始始始值值值, 计计计算算算得得得f(x0) = 0.175639, f(x1) = 0.093271;f(x2) = 0.005031, fx1, x0 = 2.68910;fx2, x1 = 2.83373, fx2, x1, x0 = 2.21418;69故故故 = fx2, x1+fx2, x1, x0(x2x1) = 2.75694代代代入入入(8)式式式求求求得得得x3= x22f(x2) +q2 4f(x2)fx2, x1, x0= 0.56714以以以上上上计计计算算算表表表明明明, 抛抛抛物物物线线线法法法一一一步步步就
78、就就得得得到到到割割割线线线法法法两两两步步步才才才得得得到到到得得得结结结果果果, 该该该计计计算算算结结结果果果说说说明明明其其其收收收敛敛敛速速速度度度比比比割割割线线线法法法快快快.705 代代代数数数方方方程程程求求求根根根一一一 问问问题题题提提提出出出如如如果果果f(x)是是是多多多项项项式式式, 则则则f(x) = 0特特特别别别地地地称称称作作作代代代数数数方方方程程程. 前前前面面面介介介绍绍绍的的的求求求根根根方方方法法法原原原则则则上上上也也也适适适用用用于于于解解解代代代数数数方方方程程程, 但但但由由由于于于多多多项项项式式式的的的特特特殊殊殊性性性, 我我我们们们
79、可可可以以以针针针对对对其其其特特特点点点提提提供供供更更更为为为有有有效效效的的的算算算法法法.二二二 问问问题题题的的的解解解决决决方方方法法法1. 代代代数数数方方方程程程的的的牛牛牛顿顿顿法法法设设设多多多项项项式式式方方方程程程f(x) = a0xn+ a1xn1+ + an1x + an= 0, 考考考察察察牛牛牛顿顿顿公公公式式式xk+1= xkf(xk)f0(xk)(9)利利利用用用秦秦秦九九九韶韶韶或或或Horner方方方法法法(9)式式式中中中的的的函函函数数数值值值f(xk)及及及f0(xk)均均均可可可方方方便便便的的的求求求出出出.712. 劈劈劈因因因子子子法法法1
80、) 方方方法法法的的的基基基本本本思思思想想想如如如果果果能能能从从从多多多项项项式式式f(x) = a0xn+ a1xn1+ + an1x + an中中中分分分离离离出出出一一一个个个二二二次次次因因因式式式(x) = x2+ ux + v我我我们们们就就就能能能获获获得得得它它它的的的一一一对对对共共共轭轭轭复复复根根根.劈劈劈因因因子子子法法法的的的基基基本本本思思思想想想是是是, 从从从某某某个个个近近近似似似的的的二二二次次次因因因子子子(x) = x2+ ux + v出出出发发发, 用用用某某某种种种迭迭迭代代代过过过程程程使使使之之之逐逐逐步步步精精精确确确化化化.72用用用二二
81、二次次次式式式(x)除除除f(x), 记记记商商商为为为p(x), 它它它是是是个个个n 2次次次多多多项项项式式式, 余余余式式式为为为一一一次次次式式式, 记记记为为为r0x + r1即即即f(x) = (x2+ ux + v)p(x) + r0x + r1(10)显显显然然然r0, r1均均均为为为u, v的的的函函函数数数:(r0= r0(u, v);r1= r1(u, v).(11)劈劈劈因因因子子子法法法的的的目目目的的的就就就是是是逐逐逐步步步修修修正正正u,v的的的值值值, 使使使余余余数数数r0, r1变变变得得得很很很小小小.73设设设变变变量量量u,v的的的调调调整整整量
82、量量分分分别别别为为为u, v, 我我我们们们希希希望望望(r0(u + u, v + v) 0;r1(u + u, v + v) 0.(12)解解解此此此方方方程程程组组组可可可以以以近近近似似似得得得到到到u, v的的的调调调节节节量量量u, v.为为为了了了能能能够够够求求求出出出方方方程程程组组组(12)的的的近近近似似似解解解, 将将将方方方程程程组组组(12)的的的左左左边边边用用用其其其在在在点点点(u, v)处处处的的的一一一阶阶阶Taylor展展展开开开来来来近近近似似似. 于于于是是是有有有r0+r0uu +r0vv 0;r1+r1uu +r1vv 0.(13)解解解出出出
83、增增增量量量u, v, 即即即可可可得得得到到到改改改进进进的的的二二二次次次因因因子子子(x) = x2+ (u + u)x + v + v以以以下下下具具具体体体说说说明明明如如如何何何计计计算算算方方方程程程组组组(16)的的的各各各个个个系系系数数数.742) 方方方法法法的的的推推推导导导a) 计计计算算算r0和和和r1将将将p(x) = b0xn2+ b1xn3+ + bn3x + bn2代代代入入入f(x) = (x2+ ux + v)p(x) + r0x + r1并并并比比比较较较各各各次次次幂幂幂的的的系系系数数数, 可可可得得得a0= b0;a1= b1+ u0b0;ai=
84、 bi+ u0bi1+ vbi2, 2 i n 2an1= ubn2+ vbn3+ r0;an= vbn2+ r1.由由由此此此可可可得得得r0和和和r1的的的计计计算算算公公公式式式为为为75b0= a0;b1= a1 ub0;bi= ai ubi1 vbi2, 2 i n 2r0= bn1;r1= bn+ ubn1.(14)76b) 计计计算算算r0v,r1v将将将f(x) = (x2+ ux + v)p(x) + r0x + r1式式式关关关于于于v求求求导导导, 得得得p(x) = (x2+ ux + v)pv+ s0x + s1(15)式式式中中中s0= r0v, s1= r1v.可
85、可可见见见, 用用用x2+ ux + v除除除p(x), 作作作为为为余余余式式式可可可以以以得得得到到到解解解决决决s0x + s1.77由由由于于于p(x)是是是n 2次次次多多多项项项式式式, 这这这里里里商商商pv是是是n 4次次次多多多项项项式式式, 记记记pv= c0xn4+ c1xn5+ + cn5x + cn4,代代代入入入(15)可可可得得得c0= b0;c1= b1 ub0;ci= bi uci1 vci2, 2 i n 2s0= cn3;s1= cn2+ ucn3.从从从而而而可可可得得得r0v= s0,r1v= s1.78c) 计计计算算算r0u,r1u再再再将将将f(
86、x) = (x2+ ux + v)p(x) + r0x + r1式式式关关关于于于u求求求导导导, 得得得xp(x) = (x2+ ux + v)pur0ux r1u.将将将p(x) = (x2+ ux + v)pv+ s0x + s1代代代入入入上上上式式式, 可可可知知知xp(x)又又又可可可以以以写写写成成成79xp(x)=(x2+ ux + v)xpv+ (s0x + s1)x=(x2+ ux + v)(xpv s0) (us0 s1)x vs0比比比较较较上上上面面面两两两个个个式式式子子子, 可可可得得得x2+ ux + v除除除xp(x)的的的余余余项项项的的的两两两种种种表表表
87、示示示, 显显显然然然他他他们们们应应应该该该相相相等等等, 故故故有有有r0u= us0 s1,r1u= vs080至至至此此此, 我我我们们们给给给出出出了了了方方方程程程组组组r0+r0uu +r0vv 0;r1+r1uu +r1vv 0.(16)中中中的的的所所所有有有系系系数数数的的的确确确定定定方方方法法法.解解解此此此方方方程程程组组组, 得得得到到到u,v的的的校校校正正正量量量u,v,由由由此此此得得得到到到新新新的的的u,v, 继继继续续续校校校正正正u, v直直直至至至满满满足足足精精精度度度要要要求求求, 最最最终终终我我我们们们可可可以以以得得得到到到f(x)的的的一
88、一一个个个二二二次次次因因因子子子x2+ ux + v.说说说明明明:求求求出出出f(x)的的的二二二次次次因因因子子子x2+ ux + v后后后就就就可可可以以以得得得到到到f(x) = 0的的的两两两个个个根根根.如如如把把把x2+ ux + v除除除f(x)得得得到到到的的的多多多项项项式式式作作作为为为新新新的的的f(x), 又又又若若若新新新的的的f(x)的的的次次次数数数超超超过过过2, 则则则继继继续续续将将将新新新的的的f(x)进进进行行行刚刚刚才才才的的的分分分解解解因因因子子子的的的过过过程程程,重重重复复复这这这样样样的的的过过过程程程就就就可可可以以以得得得到到到方方方
89、程程程f(x) = 0的的的所所所有有有根根根.81本本本章章章说说说明明明:方方方程程程f(x) = 0求求求根根根有有有多多多种种种方方方法法法, 本本本章章章突突突出出出牛牛牛顿顿顿法法法. 牛牛牛顿顿顿法法法是是是一一一种种种行行行之之之有有有效效效的的的迭迭迭代代代法法法, 在在在单单单根根根附附附近近近具具具有有有较较较高高高的的的收收收敛敛敛速速速度度度. 应应应用用用牛牛牛顿顿顿法法法的的的关关关键键键在在在于于于选选选取取取足足足够够够精精精确确确的的的初初初值值值. 如如如果果果初初初值值值选选选取取取不不不当当当(偏偏偏离离离所所所求求求的的的根根根比比比较较较远远远),
90、 则则则牛牛牛顿顿顿法法法可可可能能能发发发散散散. 牛牛牛顿顿顿下下下山山山法法法有有有时时时可可可用用用来来来克克克服服服这这这个个个局局局限限限性性性.牛牛牛顿顿顿法法法的的的另另另一一一个个个局局局限限限性性性是是是要要要求求求计计计算算算导导导数数数值值值. 如如如果果果把把把函函函数数数f的的的形形形式式式复复复杂杂杂而而而不不不便便便于于于求求求导导导, 则则则可可可用用用导导导数数数的的的估估估值值值或或或差差差商商商代代代替替替导导导数数数, 而而而得得得出出出简简简化化化的的的牛牛牛顿顿顿法法法或或或近近近似似似的的的牛牛牛顿顿顿法法法, 不不不过过过这这这样样样处处处理理理势势势必必必会会会影影影响响响收收收敛敛敛速速速度度度.82THANK YOUApr. 2008
