数值计算方法第二章

1、数值计算方法数值计算方法第二章第二章非线性方程的数值解法非线性方程的数值解法 计算机与通信工程学院2本章内容安排本章内容安排n在实际中许多方程问题无法求出公式解在实际中许多方程问题无法求出公式解 nn次代数方程次代数方程n超越方程超越方程 n需要引进能够达到一定精度要求的求方程近似需要引进能够达到一定精度要求的求方程近似值的方法值的方法 0tg xx0sin8889. 4tg25. 0 xx计算机与通信工程学院3本章内容安排本章内容安排n2.1 初始近似值的搜索初始近似值的搜索n2.2 二分法二分法n2.3 迭代法迭代法n2.4 牛顿迭代法牛顿迭代法n2.5 弦截法弦截法计算机与通信工程学院4

2、2.1 初始近似值的搜索初始近似值的搜索n方程的根方程的根n逐步扫描法逐步扫描法计算机与通信工程学院5方程的根方程的根n代数方程代数方程 n对于一元非线性方程对于一元非线性方程 f (x)=0 ,如果如果f (x) 为代数多项为代数多项式式 则称则称f (x)=0 为代数方程为代数方程 n超越方程超越方程 n超越方程包括指数方程、对数方程和三角方程等超越方程包括指数方程、对数方程和三角方程等 n方程的根方程的根0111.axaxaxannnn计算机与通信工程学院6方程的根方程的根n如果存在如果存在x*使使f (x*)=0 ，则称，则称x*是方程的解或根，是方程的解或根，也称也称x*是函数是函数

3、f (x) 的零点或根的零点或根n重根重根n如果函数如果函数 f (x) 可分解为可分解为 其中其中m是大于是大于1的正整数，则称的正整数，则称x*是方程是方程f (x)=0 的的m重根重根 n重根的判断条件重根的判断条件n设函数设函数f (x) 有有m阶连续导数，方程阶连续导数，方程f (x)=0 有有m重根重根x*的充要条件是的充要条件是0*)(),(*)()(xgxgxxxfm计算机与通信工程学院7方程的根方程的根n例例2.1.1：求：求x=0是方程是方程 的几重的几重根？根？n解：解：因此，因此，x=0是是 的三重根的三重根0*)(, 0*)(.*)( *)()() 1(xfxfxfx

4、fmm0221)(22xxexfx0)0(,221)(22fxxexfx0) 0( ,422)( 2fxexfx0)0( , 44)( 2fexfx08)0( ,8)( 2fexfx0221)(22xxexfx计算机与通信工程学院8方程的根方程的根n方程求根需要解决的问题方程求根需要解决的问题n根的存在性：方程是否有根，如果有根，有几个根？根的存在性：方程是否有根，如果有根，有几个根？ n根的隔离：找出有根区间，把有根区间分成较小的根的隔离：找出有根区间，把有根区间分成较小的子区间，每个子区间有一个根，将有根区间内的任子区间，每个子区间有一个根，将有根区间内的任一点都看成该根的一个初始近似值一

5、点都看成该根的一个初始近似值n根的精确化：对已知根的初始近似值，逐步精确化根的精确化：对已知根的初始近似值，逐步精确化 n求根的步骤求根的步骤n判断根是否存在，若存在，确定根的某个初始近似判断根是否存在，若存在，确定根的某个初始近似值值 计算机与通信工程学院9方程的根方程的根n将初始近似值逐步加工成满足精度要求的结果将初始近似值逐步加工成满足精度要求的结果 n有根区间有根区间 n如果方程在区间如果方程在区间a, b内至少有一个根，则称内至少有一个根，则称a, b为为有根区间有根区间 n隔根区间隔根区间n如果方程在区间如果方程在区间a, b内恰有一个根，则称内恰有一个根，则称a, b为隔为隔根区

6、间根区间 n根的隔离根的隔离n寻找隔根区间寻找隔根区间a, b的步骤，叫做根的隔离的步骤，叫做根的隔离 计算机与通信工程学院10方程的根方程的根n定理定理2.1：设函数：设函数f (x)在区间在区间a, b上连续，如果上连续，如果f (a) f (b) 0，则方程，则方程f (x) = 0在在a, b内至少有内至少有一实根一实根x* n定理定理2.2：设函数：设函数f (x)在区间在区间a, b上是单调连续上是单调连续函数，并且函数，并且f (a) f (b) 0，则方程，则方程f (x) = 0在在a, b上有且仅有一实根上有且仅有一实根x* 计算机与通信工程学院11方程的根方程的根n寻找有

7、根区间（隔根区间）的方法寻找有根区间（隔根区间）的方法n画图法画图法n逐步扫描法逐步扫描法abx*f(x)0 xhx 0计算机与通信工程学院12逐步扫描法逐步扫描法n实现步骤实现步骤 n设单值连续函数设单值连续函数f(x)在有根区间在有根区间a, b，从左端点，从左端点x = a出发，按某个预先选定的步长出发，按某个预先选定的步长h一步一步地向右跨一步一步地向右跨 n每跨一步都检验每步起点每跨一步都检验每步起点x0和终点和终点x0 + h的函数值的函数值n如果如果 那么所求的根那么所求的根x*必在必在x0与与x0+h之间之间 0)()(00hxfxf计算机与通信工程学院13逐步扫描法逐步扫描法

8、n例例2.1.2：考察方程：考察方程 利用逐步扫描法确定一个有根区间利用逐步扫描法确定一个有根区间 n解：注意到解：注意到f (0) 0，知，知f (x)至少有一个至少有一个正的实根正的实根 设从设从x = 0出发，取出发，取h = 0.5为步长向右进行根的扫描为步长向右进行根的扫描 因此在区间（因此在区间（1, 1.5）内必有实根）内必有实根 01)(3xxxfx00.51.01.5f (x) 的符号的符号计算机与通信工程学院142. 2 二分法二分法n二分法的基本思想二分法的基本思想n首先，假定方程首先，假定方程f (x) = 0在区间在区间a, b内有唯一的实内有唯一的实根根x*n就是将

9、方程根所在的区间平分为两个小区间，判断就是将方程根所在的区间平分为两个小区间，判断根属于哪个小区间；把有根的小区间再平分为二，根属于哪个小区间；把有根的小区间再平分为二，再判断根所在的更小的区间，对分；重复这一过程，再判断根所在的更小的区间，对分；重复这一过程，最后求出所要的近似值最后求出所要的近似值 n二分法的步骤二分法的步骤n1计算计算f (x)在有解区间在有解区间a, b端点处的函数值端点处的函数值 f (a) ，f (b)n2计算计算f (x)在区间中点处的值在区间中点处的值f (x0) 计算机与通信工程学院152. 2 二分法二分法n3判断若判断若f (x0) = 0，则，则 即是根

10、，否则检验：即是根，否则检验：n（1）若）若f (x0)与与f (a)异号，则知根位于区间异号，则知根位于区间a, x0，以，以x0代替代替b；n（2）若）若f (x0)与与f (a)同号，则知根位于区间同号，则知根位于区间x0, b，x0代代替替a n反复执行步骤反复执行步骤2、3，便可得到一系列有根区间：，便可得到一系列有根区间：a, b, a1, b1, , ak, bk, ，其中每个区间都是前，其中每个区间都是前一个区间的一半，因此区间长度为一个区间的一半，因此区间长度为20bax)(21ababkkk计算机与通信工程学院162. 2 二分法二分法n二分法的误差估计二分法的误差估计n由

11、于由于 只要有根区间只要有根区间ak+1, bk+1的长度小于预先给定的误差的长度小于预先给定的误差 ，那么就可以取，那么就可以取 作为所求根作为所求根x*的第的第k+1次近似值。其误差估计为次近似值。其误差估计为 )(21kkkbax)(211*abxxkk11*)(21kkkkkababxx计算机与通信工程学院172. 2 二分法二分法n例例2.2.1：证明：证明1-x-sinx=0 在在0, 1内有一个根，内有一个根，使用二分法求误差不大于使用二分法求误差不大于 的根要二分多少的根要二分多少次？次？n证：令证：令 f(x)=1-x-sinx，f(x) 是连续函数是连续函数 f (x) =

12、-1-cosx, x0,1 f(x)在在0, 1单调减少单调减少 又又 f(0)=10 ， f(1)=-sin10 f (1) = -7 0，由定理，由定理2.1知方程知方程在在0, 1中必有一实根，现将原方程改为同解方程中必有一实根，现将原方程改为同解方程 由此得迭代格式由此得迭代格式n取初始值取初始值x0 = 1，可逐次算得，可逐次算得 x1 = 0.4771 x2 = 0.3939 0210)(xxxf210 xx)2lg( xx)2lg(1kkxx计算机与通信工程学院30迭代过程的收敛性迭代过程的收敛性 x6 = 0.3758 x7 = 0.3758n因为因为x6和和x7已趋于一致，所

13、以取已趋于一致，所以取x7 = 0.3758为原方程为原方程在在0, 1内的一个根的近似值内的一个根的近似值n一个方程的迭代格式不唯一，且迭代也不总是收敛一个方程的迭代格式不唯一，且迭代也不总是收敛的，如上述方程也可改写成的，如上述方程也可改写成 得迭代格式得迭代格式 经过验证，该迭代公式不收敛经过验证，该迭代公式不收敛210 xx2101kxkx计算机与通信工程学院31全局收敛性全局收敛性n定义定义2.1：对任意初值：对任意初值 x0 a,b，如果按照迭代，如果按照迭代格式格式xk+1=(xk)生成的序列生成的序列 xk a,b，则该迭，则该迭代格式映内。代格式映内。 n例例2.3.3：求方

14、程：求方程x=e-x 在在0.5附近的根附近的根n解：解：将方程改写为将方程改写为x=-lnx，而，而lnx的定义域为（的定义域为（0，），当取），当取x0=0.5时，进行迭代可得时，进行迭代可得x1=0.693, x2=0.3666, x3=1.0034, x4=-0.0034。可见。可见x4已经超过已经超过了了lnx的定义域，迭代不能继续，此格式不映内。的定义域，迭代不能继续，此格式不映内。n不仅考虑映内性，为使迭代法有效，还必须保不仅考虑映内性，为使迭代法有效，还必须保证它的收敛性证它的收敛性计算机与通信工程学院32计算机与通信工程学院33全局收敛性全局收敛性n定理定理2.3：设函数：设

15、函数(x) 在在a,b上具有连续的一阶上具有连续的一阶导数，且满足导数，且满足（1）当）当x a, b时，时， (x) a, b（2）当任意）当任意x a, b，存在，存在0 L 1，使，使 则方程则方程x= (x)在在a, b上有唯一的根上有唯一的根x*,且对任意且对任意初值初值x0 a, b时，迭代序列时，迭代序列xk+1=(xk)(k = 0, 1, )收敛于收敛于x*。1)( Lx计算机与通信工程学院34全局收敛性全局收敛性n证明：先证明根的唯一性证明：先证明根的唯一性构造连续函数构造连续函数 ，根据条件，根据条件(1)可以得到可以得到由函数的连续性定理可知，存在由函数的连续性定理可知

16、，存在x*a,b，使使 ，也就是存在解，即，也就是存在解，即假设有两个解假设有两个解 ，则，则根据中值定理有根据中值定理有从而有从而有xxx)()(0)()(aaa0)()(bbb0*)(*)(xxx*)(*xx,*,baxx)(*),(*xxxx,),*)( )(*)(*baxxxxxx0)( 1)*(xx计算机与通信工程学院35全局收敛性全局收敛性根据条件根据条件(2)有有 所以所以 ，即，即 ，也就是解唯一。，也就是解唯一。 设设x*是方程的根，即是方程的根，即x*= (x*)，由拉格朗日定理，由拉格朗日定理 因为因为0 L 1，由，由 知知 即即 xk+1 = (xk)收敛收敛)( )

17、()(*1*kkkxxxxxx0*11*2*1*)( )()(xxLxxLxxLxxxxxxkkkkkk0lim1kkL)(01*kxxk1| )( |x0*xxxx *计算机与通信工程学院36全局收敛性全局收敛性n定理定理2.4：设在区间：设在区间a,b方程方程 x= (x) 有根有根x*，并，并且对且对 有有| (x)| 1，则对于任意，则对于任意x0(x*) a,b ,迭代过程迭代过程 xk+1 = (xk)一定发散。一定发散。n推论推论2.1：在定理：在定理3的条件下，有误差估计式的条件下，有误差估计式,bax11*kkkxxLLxx011*xxLLxxkk计算机与通信工程学院37全局

18、收敛性全局收敛性n证：证： 即即 已知已知L1，因此有，因此有 只要只要 充分小，就可以保证充分小，就可以保证 足够小足够小 因此可用条件因此可用条件 来控制迭代过程的结束来控制迭代过程的结束 11*kkkkkxxxxLxxLxx)*(1kkkxxxxL1*)1 (kkkxxLxxL11*kkkxxLLxx1kkxxkxx *1kkxx计算机与通信工程学院38全局收敛性全局收敛性 即即)( )()(21211kkkkkkxxxxxx21kkxxL.11*2121kkkkkxxlLxxLLxx011xxLLk011*xxLLxxkk计算机与通信工程学院39全局收敛性全局收敛性n迭代法的终点判断迭

19、代法的终点判断n只要相邻两次迭代值的偏差充分小，就能保证迭代只要相邻两次迭代值的偏差充分小，就能保证迭代值足够准确，因而用值足够准确，因而用|x k- x k-1| 控制迭代过程的结控制迭代过程的结束束计算机与通信工程学院40全局收敛性全局收敛性n例例2.3.4：对方程：对方程 xex-1=0构造收敛的迭代格式并构造收敛的迭代格式并求其根，要求精度求其根，要求精度10-5 n解：设解：设f(x)=xex-1, 则则 f(0)=-10 因此因此f(x)=0在（在（0，1）内有根）内有根 又又 因此方程因此方程f(x)=0在在(0, )内仅有一根内仅有一根 令令 在在0,1上，上， 因此因此 x=

20、e-x 收敛收敛 取取x0=0.5进行迭代，计算结果如下表所示进行迭代，计算结果如下表所示 0)1 ()( xexeexfxxxxex)(1| )( |xex 1 , 0 1 ,1)(ex计算机与通信工程学院41全局收敛性全局收敛性kxkkxk00.500000100.56690710.606531110.56727720.545239129.56706730.579703130.56718640.560065140.56711950.571172150.56715760.564863160.56713570.568438170.56714880.566409180.56714190.5675

21、60计算机与通信工程学院42全局收敛性全局收敛性 取取x*0.56714 n例例2.3.5：用迭代法求方程：用迭代法求方程 x3-2x-5=0 的最小正的最小正根根n解：解： 取正根区间取正根区间2,3，迭代格式，迭代格式 不满足收敛定理不满足收敛定理 5171810000007. 0567148. 0567141. 0 xxx0 01 12 23 3 f(x)-5-5-6-6-1-116 16 3115)2kkxx（2233( ),( )13.512maxxxxx 计算机与通信工程学院43全局收敛性全局收敛性n将原方程改写成将原方程改写成 迭代格式迭代格式 收敛收敛 取初值取初值x0=2.5

22、 进行迭代，结果如下所示进行迭代，结果如下所示 3(25)xx2332( )25,( )(25),3xxxx3125kkxx3 , 2)(x计算机与通信工程学院44全局收敛性全局收敛性 取方程的根取方程的根 x*= 2.0946 计算机与通信工程学院全局收敛性全局收敛性n例例2.3.6：求方程：求方程 x3-3x+1=0 在在0, 0.5内的根，内的根，精确到精确到10-5 45计算机与通信工程学院46局部收敛性局部收敛性n定义定义2.2： 如果存在如果存在x* 的某个邻域的某个邻域: |x-x*| ，使迭代过程使迭代过程 xk+1 = (xk)对于任意初值对于任意初值 x0 均均收敛，则称迭

23、代过程收敛，则称迭代过程xk+1 = (xk)在根在根x* 附近具附近具有局部收敛性。有局部收敛性。 n定理定理2.5： 设设 (x)在在x= (x)的根的根x* 邻域有连续的邻域有连续的一阶导数，且有一阶导数，且有 | (x*) |1，则迭代格式，则迭代格式 xk+1 = (xk)在根在根x*附近具有局部收敛性。附近具有局部收敛性。 n证明证明:由于由于 | (x*) |1 ，存在充分小的邻域：，存在充分小的邻域： |x-x*| ，使下式成立，使下式成立 | (x) | L1计算机与通信工程学院局部收敛性局部收敛性 根据微分中值定理根据微分中值定理 由于由于 (x*) =x*，又当，又当x时

24、时，因此，因此n由定理由定理2.3的条件的条件(1)可以断定可以断定xk+1 = (xk)对于任意对于任意x0均收敛均收敛n已知根的初值已知根的初值x0在根在根 x*邻域，又根据邻域，又根据(x)的连的连续性，则可采用续性，则可采用 |(x0) | 1 来代替来代替|(x* ) | 1，判断迭代的收敛性，判断迭代的收敛性 47*)( *)()(xxxx| *| *| *)(|xxxxLxx计算机与通信工程学院48局部收敛性局部收敛性n例例2.3.7：迭代过程：迭代过程 ，当局部收敛，当局部收敛到到 时，确定时，确定C的值的值n解：迭代函数解：迭代函数 当局部收敛到当局部收敛到 时，时， 有有

25、)5(21kkkxcxx5)5()(2xcxxcxx21)( 51521)5( c15211c051c计算机与通信工程学院49局部收敛性局部收敛性n例例2.3.8：对方程：对方程x3-x2-1=0在初值在初值x0=1.5附近建立附近建立收敛的迭代格式，并求解，要求精确到小数点收敛的迭代格式，并求解，要求精确到小数点后后4位位 n解：构造迭代公式，写出方程的等价形式解：构造迭代公式，写出方程的等价形式 迭代格式为迭代格式为 321xx3211kkxx322) 1(32)( xxx14558. 0)( 5 . 100 xx计算机与通信工程学院50局部收敛性局部收敛性迭代收敛迭代收敛 ，计算过程如下

26、，取，计算过程如下，取x*x9=1.4656，此时，此时 kxk|xk+1-xk|0 01.51.51 11.481241.481240.0187630.0187632 21.472711.472710.008530.008533 31.468821.468820.003890.003894 41.467051.467050.001770.001775 51.466241.466240.000810.000816 61.465881.465880.000360.000367 71.465701.465700.000180.000188 81.465631.465630.000070.00007

27、9 91.465601.465600.000030.000034891021 xx计算机与通信工程学院51局部收敛性局部收敛性n迭代的计算步骤迭代的计算步骤n确定确定 f(x)=0的等价形式的等价形式 x= (x) ，选初值，选初值x0 ，判断，判断收敛性收敛性| (x0) |1n由公式由公式 x1 = (x0) 计算计算x1n如果如果|x 1- x 0| 则停止计算，取则停止计算，取x*= x1 ；否则令；否则令x 0 =x 1 ，重复步骤，重复步骤2和和3，直到计算停止，直到计算停止 n例例2.3.9：给定函数：给定函数f(x) ，设迭代程，设迭代程 选取选取值，使在值，使在 f(x)=0

28、 的单根附近收敛的单根附近收敛 )(1kkkxfxx计算机与通信工程学院迭代过程的收敛速度迭代过程的收敛速度n迭代过程的收敛速度，是指在接近收敛时迭代迭代过程的收敛速度，是指在接近收敛时迭代误差的下降速度误差的下降速度n定义定义2.3：设迭代过程：设迭代过程 xk+1 = (xk)收敛于收敛于 x = (x)的根的根x*，令迭代误差，令迭代误差ek=xk-x*，如果存在常，如果存在常数数p(p1)和和c(c0)，使，使则称序列则称序列 xk是是p阶收敛的，阶收敛的，c称渐近误差常数。称渐近误差常数。52计算机与通信工程学院迭代过程的收敛速度迭代过程的收敛速度n定理定理2.6：对迭代过程：对迭代

29、过程 xk+1 = (xk) ，如果，如果 (p)(x)在所求根在所求根x*的邻域连续，且的邻域连续，且 则迭代过程在则迭代过程在x*邻域是邻域是p阶收敛的。阶收敛的。n证：由于证：由于 (x*) =0，即在，即在x*邻域邻域| (x*) |1 ，所以，所以xk+1 = (xk) 具有局部收敛性。具有局部收敛性。 将将 (xk)在在x*处泰勒展开到处泰勒展开到p-1阶阶53计算机与通信工程学院迭代过程的收敛速度迭代过程的收敛速度 将已知的将已知的 代入代入n由于由于xk+1 = (xk) , x*= (x*) ， 那么有那么有54计算机与通信工程学院迭代过程的收敛速度迭代过程的收敛速度n例例2

30、.3.10：迭代过程：迭代过程 收敛于收敛于 时，问其收敛速度。时，问其收敛速度。n解：因为解：因为 所以所以n将将 代入代入n因此因此 xk是二阶收敛的是二阶收敛的55计算机与通信工程学院迭代过程的收敛速度迭代过程的收敛速度n例例2.3.11：设：设 ，要使迭代过程，要使迭代过程xk+1 = (xk) 至少平方收敛到至少平方收敛到 ，确定，确定a的的值值56计算机与通信工程学院57迭代的加权法加速迭代的加权法加速n加权法加权法 n设设 xk是根是根x* 的某近似值，取的某近似值，取 ，由中值定理由中值定理 其中其中 x*, xk，假定，假定 () 变化不大，设变化不大，设 () c ，有，有

31、 1(),()kkxxxx1()()( )()kkkxxxxxx 1()kkxxc xx1kkxcxxcx1111kkcxxxcc计算机与通信工程学院58迭代的加权法加速迭代的加权法加速 取取 即即11111kkkcxxxcc)(111kkkcxxcx计算机与通信工程学院59迭代的加权法加速迭代的加权法加速n例例2.3.12：用加权法加速技术求方程：用加权法加速技术求方程x=e-x 在在0.5附近的一个根附近的一个根 n解：因为在解：因为在x0=0.5附近附近 所以加速迭代公式所以加速迭代公式 可以写成可以写成6 . 0| )( 5 . 05 . 05 . 0eexx)6 . 0(6 . 11

32、1kxkxexk计算机与通信工程学院60迭代的加权法加速迭代的加权法加速计算结果如下表所示计算结果如下表所示 kxkkxk00.530.56714310.56658240.56714320.567132计算机与通信工程学院612.4 牛顿迭代法牛顿迭代法n迭代公式的建立迭代公式的建立n牛顿迭代法的几何意义牛顿迭代法的几何意义n牛顿迭代法的收敛性牛顿迭代法的收敛性n牛顿迭代法的修正牛顿迭代法的修正计算机与通信工程学院62迭代公式的建立迭代公式的建立n已知方程已知方程f (x) = 0的一个近似根的一个近似根x0，把，把f (x)在在x0处作泰勒展开处作泰勒展开n取前两项来近似代替取前两项来近似代

33、替f (x) ，则得近似的线性方，则得近似的线性方程程n设设f (x0) 0 ，解之得，解之得 200000)(! 2)()( )()(xxxfxxxfxfxf0)( )(000 xxxfxf)( )(000 xfxfxx计算机与通信工程学院63迭代公式的建立迭代公式的建立n取取x作为原方程作为原方程f (x) = 0的近似根的近似根x1，即，即n再重复用上述方法得再重复用上述方法得n一般地，有迭代公式一般地，有迭代公式)( )(0001xfxfxx), 2, 1, 0()( )(1kxfxfxxkkkk)( )(1112xfxfxx计算机与通信工程学院64牛顿迭代法的几何意义牛顿迭代法的几何

34、意义n当求得当求得x*的近似值的近似值xk以后，过曲线以后，过曲线y= f (x) 上对上对应点（应点（xk, f (xk)）作）作f (x) 的切线，其切线方程为的切线，其切线方程为 n求此切线方程和求此切线方程和x轴的交点，即得轴的交点，即得x*的新的近似的新的近似值值xk+1必须满足方程必须满足方程n即牛顿法的迭代公式即牛顿法的迭代公式 的计算结果的计算结果 )( )(kkkxxxfxfy0)( )(kkkxxxfxf)( )(1kkkkxfxfxx计算机与通信工程学院65牛顿迭代法的几何意义牛顿迭代法的几何意义计算机与通信工程学院66例题例题n例例2.4.1：用牛顿迭代法求：用牛顿迭代

35、法求 x=e-x 在在0.5附近的根附近的根n 解：由解：由x=e-x ，有，有xex-1=0由牛顿迭代公式由牛顿迭代公式 可知可知取取x0=0.5，计算结果如下所示：，计算结果如下所示： xxxeexf)( 01)(xxexfkxkkxkxxkkkxexxexeexxxkkkk111计算机与通信工程学院67例题例题kxkkxk00.530.56714329110.57102044040.56714329020.567155560计算机与通信工程学院68例题例题n例例2.4.2：造平方根表，用牛顿迭代法计算：造平方根表，用牛顿迭代法计算 n解：令解：令 ，则，则x2-a=0, 求求 等价于求等

36、价于求f (x)= x2-a=0 的正实根，因为的正实根，因为 f (x)= 2x ，由牛顿迭代公式得由牛顿迭代公式得 当当a=115时，取初值时，取初值 x0=10，迭代，迭代4次可得次可得10，10.7500，10.723837，10.723805， 10.723805axaa211(),0,1,2,22kkkkkkxaaxxxkxx723805.10115 计算机与通信工程学院69例题例题n例：用牛顿迭代法求例：用牛顿迭代法求3a计算机与通信工程学院70牛顿迭代法的收敛性牛顿迭代法的收敛性n定理定理2.7：设：设 f (x*)=0， f (x*) 0， f (x*) 在在x*邻域连续，则

37、牛顿迭代法在邻域连续，则牛顿迭代法在x*局部收敛，局部收敛，且至少且至少2阶收敛。并有阶收敛。并有n证：证：因为因为f (x*)=0 ，而，而f (x*) 0 ，在，在x*邻域，则邻域，则12()lim2()kkkefxefx计算机与通信工程学院71牛顿迭代法的收敛性牛顿迭代法的收敛性 因为因为f (x)在在x*邻域连续，则牛顿迭代法局部收敛，邻域连续，则牛顿迭代法局部收敛，当当f (x*) 0时时， (x*) 0 ，牛顿迭代法在，牛顿迭代法在x*邻邻域为二阶收敛。域为二阶收敛。 计算机与通信工程学院牛顿迭代法的收敛性牛顿迭代法的收敛性72计算机与通信工程学院73牛顿迭代法的修正牛顿迭代法的修

38、正n牛顿迭代法对初值的要求较高：要求初值牛顿迭代法对初值的要求较高：要求初值x0充分接近充分接近x*才能保证局部收敛性。如果才能保证局部收敛性。如果初值初值x0偏离偏离x*较远，那么牛顿迭代法可能较远，那么牛顿迭代法可能发散或收敛很慢。发散或收敛很慢。n例例2.4.4：用牛顿迭代法求方程：用牛顿迭代法求方程f (x) = x3 x 1 = 0在在x= 1.5附近的根。附近的根。n解：构造牛顿迭代公式解：构造牛顿迭代公式312131kkkkkxxxxx计算机与通信工程学院74牛顿迭代法的修正牛顿迭代法的修正分别取初值分别取初值1.5和和0.6进行迭代计算，结果如下所示：进行迭代计算，结果如下所示

39、： k (初值初值1.5) (初值初值0.6) 0 1.5 0.6 1 1.34783 17.9 2 1.32520 11.9468 3 1.32472 7.986 计算机与通信工程学院牛顿迭代法的修正牛顿迭代法的修正n牛顿下山法就是扩大初值范围的修正牛顿法，牛顿下山法就是扩大初值范围的修正牛顿法，为了防止初值的选取造成迭代发散或迭代值偏为了防止初值的选取造成迭代发散或迭代值偏离所求根而采用的一种对初值离所求根而采用的一种对初值x0的修正措施。的修正措施。n要求迭代过程对所选的初值能达到使函数值单要求迭代过程对所选的初值能达到使函数值单调下降，也就是要满足下山条件调下降，也就是要满足下山条件n

40、将牛顿迭代法的计算结果将牛顿迭代法的计算结果75)()(1kkxfxf计算机与通信工程学院牛顿迭代法的修正牛顿迭代法的修正 与前一步的近似值与前一步的近似值xk适当加权平均作为新的改适当加权平均作为新的改进值进值xk+1n将上述两式合并可得牛顿下山法的迭代公式将上述两式合并可得牛顿下山法的迭代公式 其中其中 是一个参数，是一个参数， 的选取应满足的选取应满足0 1 ， 为下山因子下界为下山因子下界。开始时可简单地取开始时可简单地取 = 1，然后逐步分半减少，然后逐步分半减少76), 2, 1, 0()( )(1kxfxfxxkkkk计算机与通信工程学院77牛顿迭代法的修正牛顿迭代法的修正n牛顿

41、下山法的步骤牛顿下山法的步骤（1）选取初始近似值）选取初始近似值x0；（2）取下山因子）取下山因子 = 1；（3）计算）计算（4）计算）计算f (x1)，并比较，并比较| f (x1)| 与与 | f (x0)|的大小的大小 若若| f (x1)| | f (x0)| ，把，把x1带到牛顿迭代公式带到牛顿迭代公式中进行迭代；中进行迭代； 若若 | f (x1)| | f (x0)| ，则当，则当 计算过程结束计算过程结束，重新选择一个，重新选择一个x0进行牛顿下山；否则当进行牛顿下山；否则当 ，则将下山因子缩小一半，取则将下山因子缩小一半，取 /2代入，并转向（代入，并转向（3）重复计算）重复

42、计算)( )(0001xfxfxx计算机与通信工程学院78牛顿迭代法的修正牛顿迭代法的修正n例例2.4.5：求方程：求方程f (x) = x3 x 1 = 0在在1.5附附近的一个根近的一个根n解：解：已知方程已知方程f (x) = x3 x 1 = 0的一个根为的一个根为x* = 1.32472，若取初值，若取初值x0 = 0.6，用牛顿法，用牛顿法计算计算 反而比反而比x0 = 0.6更偏离根更偏离根x*。若改用牛顿下山法。若改用牛顿下山法 计算，仍取计算，仍取x0 = 0.6，计算结果如下表计算结果如下表9 .17)( )(0001xfxfxx)( )(1kkkkxfxfxx计算机与通信工程学院79牛顿迭代法的修正牛顿迭代法的修正k xkf(xk)| f(xk+1)| f(xk)|010.6-1.3841117.95716否否1/29.25781否否1/44.925114否否1/82.762517.319否否1/161.681252.0709否否1/321.140625-0.625是是211.366810.1866311.326286.6710-341