求方程根的近似方法

1、 f(x)=0=0的根的根( (或或f(x)的零点的零点) )，当，当f(x)复杂时，很难求复杂时，很难求（需要找到有效简单的近似方法去求）。（需要找到有效简单的近似方法去求）。 第二章第二章 求方程根的近似方法求方程根的近似方法2.1 2.1 二分法二分法理理 论论: : f(x) ca,b, ca,b, 单调单调, , f(a)f(b)0 0 f(x)=0=0在在(a,b)(a,b)中有惟一根。中有惟一根。abx1x2ab何时停下来?11xxkk 2)(xf 或或不能保证不能保证 x 的精的精度度x* 2xx*解解： f(1)=-50 -(1,2)+ x1=1.5 f(1.5)0 (1,1

2、.5) x2=1.25 f(1.25)0 (1.25,1.375) x4=1.313 f(1.313)0 (1.313,1.375) x5=1.344 f(1.344)0 (1.344,1.375) x6=1.360 f(1.360)0 (1.360,1.368) x8=1.364 例例2.1.12.1.1 用二分法求用二分法求 在在(1,2)(1,2)内内 的根，要求绝对误差不超过的根，要求绝对误差不超过010423 xx21102。*21 |10 , 822nnbaxxn：。先先验验估估计计解解出出等等分分次次数数*81.364xx若 取 近 似 根*211|(1.3681.360)0.0

3、041022xx8，则则 （事后估计事后估计）误差误差 分析：分析：第第1步产生的步产生的21bax 有误差有误差21abx*|x 第第 k 步产生的步产生的 xk 有误差有误差kkabx*|x2 对于给定的精度对于给定的精度 , 可估计二分法所需的步数可估计二分法所需的步数 k ： lnln2ln 2kbabak 缺点：收敛速度慢，缺点：收敛速度慢， 不易求偶数重根不易求偶数重根. . 如图如图用二分法求根，最好先给出用二分法求根，最好先给出 f (x) 草图以确定根的大草图以确定根的大概位置。或用搜索程序，将概位置。或用搜索程序，将a, b分为若干小区间，对每一分为若干小区间，对每一个满足

4、个满足 f (ak)f (bk) 0 的区间调用二分法程序，可找出区的区间调用二分法程序，可找出区间间a, b内的多个根，且不必要求内的多个根，且不必要求 f (a)f (b) 0 。yx优点：条件和方法简单优点：条件和方法简单( (只要求只要求f(x)连续即可连续即可) )，方法收敛；，方法收敛； ( )0 ( )(f xxxf 改改写写成成， 连连续续）1 1. . 建建立立: :把把 ,.,., 121，nnx xxx 则则产产生生数数列列若若此此数数列列收收敛敛，不不妨妨设设极极限限为为则则 一一. 迭代法的建立与收敛性迭代法的建立与收敛性01 () (0, 1, 2,.)nnxxxn

5、 取取 定定 初初 值值 1limlim (), i.e., ( )nnnnxx 所以所以, 为为f的根的充要条件是的根的充要条件是 为为 的不动点。的不动点。2.2 2.2 迭代法迭代法 1( )0nf xnx 即即 是是当当时时为为。的的根根，故故充充分分大大, ,可可作作的的近近似似值值.newton( )3335 31011习题，第一种方法，另一种方法用迭代法，在1,2收敛，初值取1.5：。xxxxxxx 形形式式不不唯唯一一， 我我们们该该怎怎样样取取它它？或或如如 3103101 1.51 1.5 nnnnxxxxxx取取取取前者收敛前者收敛：1.5; 1.35721; 1.330

6、86; 1.32588; 1.32494; 1.32476; 1.32473; 1.32472; 1.32472;后者发散后者发散: : 1.5; 2.375; 12.39; 问题：何时收敛？问题：何时收敛？xyy = xxyy = xxyy = xxyy = x y= (x)y= (x)y= (x)y= (x)x0p0 x1p1 x0p0 x1p1 x0p0 x1p1x0p0 x1p12.2.收敛定理收敛定理 (2)1, , , |( )|.lxa bxl 存存在在常常数数使使得得有有 ( ) ( ) ;1 (3) 1 (4) 011101() , 2 , ,(,|.1nnnnnnnxxa

7、bxa bxxxxxllxxxl 则则：方方程程在在上上有有唯唯一一根根；）收收敛敛到到 1 , ( );xa baxb （） ，有有( ) , xa b 设设在在上上满满足足下下列列两两项项条条件件定理定理2.2.12.2.1注1：l l越小，收敛越快。越小，收敛越快。由定理结论由定理结论(3)(3)或或(2.2.2)(2.2.2)，只要前后两次迭代值的差值足，只要前后两次迭代值的差值足 够小，就可使近似值够小，就可使近似值 达到任意的精度。在实际计算达到任意的精度。在实际计算 中，一般用中，一般用 来控制迭代过程结束来控制迭代过程结束。1nx1|nnxx定理条件非必要条件，可将定理条件非必

8、要条件，可将a, b缩小，定义缩小，定义局部收敛性局部收敛性：定义定义2.2.1 若存在若存在 的某的某 邻域邻域 b = x | | x | , 使使由由 x0 b 开始的迭代都收敛开始的迭代都收敛, 则称迭代法具有则称迭代法具有局部收敛性局部收敛性。定理定理2.2.2 设设(x)在在 的某的某 邻域内具有连续的一阶导数，邻域内具有连续的一阶导数， 且且 | ( ) | 1， 则迭代法则迭代法xn+1 = (xn)具有局部收敛性具有局部收敛性。证明证明 省略省略。3 3编程停机判断编程停机判断 nnxx1时，由（时，由（2.2.22.2.2）式知）式知 l11 nx 比较小，此时停机，比较小

9、，此时停机，1n x )(1nnxx （取定初值（取定初值x0）计算，当）计算，当 由由二二. .迭代法的收敛阶迭代法的收敛阶( (收敛速度收敛速度) )1| (0), |limnpnnxccx 则称则称xn p阶收敛阶收敛, ,相应的迭代法称为相应的迭代法称为p阶方法阶方法. . 特别特别, , p=1=1时叫线性收敛时叫线性收敛, ,此时要求此时要求00c1;0,0,使使 定义定义2.2.22.2.2: : 设设定理定理2.2.32.2.3 设设(x)在在 的某邻域的某邻域 内有充分多阶连续内有充分多阶连续导数，则迭代法导数，则迭代法xn+1 = (xn)为为p阶收敛阶收敛的充要条件是的充

10、要条件是 ( ) = ( ) = = (p-1)( ) =0， (p)( ) 0.证明证明 利用利用taylor展开式（略）展开式（略） 2.32.3牛顿（牛顿（newtonnewton）法）法)( )( )()()(! 2)()( )( )()(2nnnnnnnnxxxfxfxfxxxfxxxfxfxf taylortaylor展开线性化展开线性化0)( xf近似于近似于0)()( )( nnnxxxfxf 1()- (0, 1, 2,)(2.1)()nnnnf xxxnfx 将将f(x)在在xn点点taylortaylor展开展开 解出解出 记为记为，则则1 nxx一一. newton .

11、 newton 迭代法迭代法 1.1.迭代公式的建立：迭代公式的建立：2.newton2.newton迭代法的几何意义迭代法的几何意义)()( )(nnnxxxfxfy 与与 0 y求交点，解出求交点，解出1nxx , 则则1()()nnnnf xxxfx ) )(,(nnxfx 的切线的切线 过过3. newton3. newton迭代法的收敛定理（迭代法的收敛定理（定理定理 2.3.12.3.1）（1 1）)(),( xfxf连续，且分别不变号；连续，且分别不变号；则则 newton newton 迭代法（迭代法（2.12.1）产生的数列）产生的数列 1 nx收敛到根收敛到根 。0)( x

12、f在在 a,b 上有根上有根 , , 且且)(xf在在 a,b 上满足上满足设设0,xa b , ,使使（2 2） 取初值取初值0)()(00 xfxf 解：设解：设, 0,2 cxcx则则取取cxxf 2)(，则由（，则由（2.12.1）)(21221nnnnnnxcxxcxxx 例例2.3.12.3.1(0).cc 用用 newton newton 迭代法求迭代法求4.newton4.newton迭代法的收敛阶迭代法的收敛阶( (收敛速度收敛速度) )（定理定理 2.3.22.3.2） ( )0则则单单的的n ne ew wt to on n迭迭代代法法如如果果收收敛敛, ,其其收收敛敛至至少少是是二二阶阶的的。求的根f x 0)( xf在在 a,b 有单根有单根 ，且，且)(xf 在在 a,b 上有上有设设直到二阶的连