数值分析第7章—非线性方程与方程组的数值解法

1、17.1 7.1 方程求根与二分法方程求根与二分法设非线性方程为设非线性方程为 f (x)=0 (7-1) 方程方程(2-1)的解的解 称为称为方程的根方程的根或或函数函数 f (x)的零点。的零点。 x )()(xgxxxfm 其中其中m为大于为大于1 1的整数的整数, ,且且g(x) 0,称称 为方程为方程(7-1)的的m重根重根, ,或或函数函数 f (x) 的的m重零点重零点. . x若若 f (x) 为为n 次多项式次多项式, ,则称则称 f (x)=0为为n 次代数方程次代数方程 . 若若 f (x) 为超越函数为超越函数, ,则称则称f (x)=0 为为超越方程超越方程 。 若若

2、 f (x) 可表示为可表示为第第7章章 非线性方程求根非线性方程求根2一、求有根区间的一般方法一、求有根区间的一般方法若若 f(x) 满足条件满足条件: (1) 在在a,b内连续内连续, , (2) f(a) f(b)0, f (0)=10, f (3)=- -260f (x) 在此三区间的符号分别为在此三区间的符号分别为“- -”、“- - ”、“+”由由 f (x)= 4 x2(x- -3)=0 得驻点得驻点 x1=0, x2=3。6以上分析可用下表表示以上分析可用下表表示x(-,0)0 (0,3) 3 (3,4) 4(4,+) f (x) f (x) - - 0 + - - 0 - -

3、+ + 隔根区间隔根区间(0,3)(3,4)可见可见 f (x) 仅有两个实根仅有两个实根, , 分别位于分别位于(0, 3) , (3,+), 又又 f (4)=10, 所以第二根的隔根区间可缩小为所以第二根的隔根区间可缩小为 (3,4)。72. 逐步搜索法逐步搜索法 (增值寻根法增值寻根法)搜索过程搜索过程, ,可从可从a 开始开始, ,也可从也可从 b 开始开始,这时应取步长这时应取步长 h 0。 增值寻根法的基本思想是增值寻根法的基本思想是: 从初值从初值 开始开始, 按规按规定的一个初始步长定的一个初始步长h 来增值。来增值。 同时计算同时计算 . 可能遇到三可能遇到三种情形：种情形

4、：0 x1(0,1,2,)nnxxhn )(1 nxf1(3)()()0nnf xf x ，0)()1(1 nxf此时此时 即为方程的根即为方程的根1 nx。 x1(2)()()0nnf xf x 说明区间说明区间 内无根内无根 ,1 nnxx说明区间说明区间 内有根内有根 ,1 nnxx8图图2-1图图2-29三、三、 二分法二分法设设方程方程f(x)=0 在区间在区间a,b 内有且只有一个实根内有且只有一个实根x* 。即即 f(x) 满足条件满足条件: (1) 在在a,b内连续内连续, , (2) f(a) f(b)0 , (3) f(x) 在在a,b内严格单调。内严格单调。10 二分法的

5、步骤：二分法的步骤：(2)若若 则则 令令 a2= a , b2=x1 ;1( )()0 ,f af x1( ,),xa x (3)若若 则则 , 令令 a2= x1 , b2=b。 1()( )0 ,f xf b1(, )xx b 11(),2xab记记a, b = a1, b1, 中点中点 计算计算f(x1),(1)若若 f ( x1 ) = 0, 则则 x1 就是方程的根就是方程的根x*,计算结束计算结束 ;对压缩了的有根区间对压缩了的有根区间 a2, b2, , 实行同样的步骤实行同样的步骤. .若每次二分时所取区间中点都不是根，则上述过程若每次二分时所取区间中点都不是根，则上述过程将

6、无限进行下去。将无限进行下去。111122,nna ba ba b 如此反复进行如此反复进行, , 可得一系列有根区间套可得一系列有根区间套由于每一区间都是前一区间的一半，因此区间由于每一区间都是前一区间的一半，因此区间 an , bn 的长度为的长度为11()2nnnbaba 当当 n 时时, 区间必将最终收缩为一点区间必将最终收缩为一点x*, 显然显然x* 就就是所求的根是所求的根。12)(nnnbax 21只要只要n 足够大足够大, 即区间二分次数足够多即区间二分次数足够多, 误差就可足误差就可足够小。够小。),(,11 nnnbaxx若取区间若取区间 的中点的中点,nnba作为作为 的

7、近似值，则有下述误差估计式的近似值，则有下述误差估计式 x11()()22nnnnxxbaba 13 由于在偶重根附近曲线由于在偶重根附近曲线 y=f(x) 为上凹或下凸为上凹或下凸, ,即即 f(a) 与与 f(b) 的符号相同的符号相同, ,因此不能用二分法求偶重根因此不能用二分法求偶重根. .005. 0 nxx解解 可知可知 要想满足题意，即要想满足题意，即：)5 . 1 , 1 ( x例例 2 用二分法求方程用二分法求方程 f(x)=x3-x-1=0在在 上的上的实实根根, ,要求误差不超过要求误差不超过0.005。)5 . 1 , 1(14为所求之近似根。即为所求之近似根。即 x*

8、 1.3242 (1) f (a)0 (2) 根据精根据精 度要求度要求, 取到小数取到小数 点后四位点后四位 即可即可.- + - + + - -1.25 1.375 1.3125 1.3438 1.3281 1.3203 1.32421.5 1.5 1.375 1.375 1.3438 1.3281 1.32811.0 1.25 1.25 1.3125 1.3125 1.3125 1.32031 2 3 4 5 6 7 annnbnx)(nxf15例例 3用二分法求用二分法求 在在 内的一个实根，且要求满足精度内的一个实根，且要求满足精度0104)(23 xxxf2 , 131021 nx

9、x解解用二分法计算结果如表用二分法计算结果如表2-1：160.0000721.3647460941.36718751.363281259-0.032151.3642578131.36718751.35937580.032361.363281251.3751.3593757-0.096411.3593751.3751.343756-0.350981.343751.3751.31255-0.848391.31251.3751.2540.162111.3751.51.253-1.798671.251.51.022.3751.52.01.01n17-0.007991.3647460941.365234

10、3751.36425781311-0.016051.3642578131.3652343751.3632812510nnanbnx)(nxf接上图接上图迭代迭代11 次，次，近似根近似根364746094. 111 x即为所求，即为所求，其误差其误差311111021000488281. 02 abxxn187.2 不动点迭代法及其收敛性不动点迭代法及其收敛性一、迭代法的基本思想一、迭代法的基本思想 迭代法是一种重要的逐次逼近法迭代法是一种重要的逐次逼近法, ,其其基本思想基本思想是：是：将方程将方程 f (x)= 0 化为等价方程化为等价方程, )(xx 然后在隔根区间内取一点然后在隔根区间

11、内取一点 x0 ，按下式计算按下式计算1()(0,1,2,)kkxxk 计算结果生成数列计算结果生成数列,10kxxx如果这个数列有极限如果这个数列有极限 xxkklim19这种求根方法称为这种求根方法称为不动点迭代法不动点迭代法。 如果迭代序列收敛如果迭代序列收敛, ,则称则称迭代格式收敛迭代格式收敛, ,否则称为否则称为发发散散。当当 (x) 连续时连续时, ,显然显然 就是方程就是方程 x= (x) 之根。之根。 x于是于是可以从数列可以从数列 中求得满足精度要求的近似根。中求得满足精度要求的近似根。kx1()(0,1,2,)kkxxk 称为称为迭代格式迭代格式, (x) 称为称为迭代函

12、数迭代函数, x0 称为称为迭代初值迭代初值,数列数列 称为称为迭代序列迭代序列。kx20 03224xxx14)(2 xxx 32)(243 xxxx 4121)23()(xxxx 对方程进行如下三种变形：对方程进行如下三种变形：用迭代法求方程用迭代法求方程 x4+2x2-x-3=0 在区间在区间1, 1.2内内的的 实根实根。解解例例121分别按以上三种形式建立迭代格式，并取分别按以上三种形式建立迭代格式，并取x0=1进行进行迭代计算，结果如下：迭代计算，结果如下：12411()(32)kkkkxxxx 26271.124123xx12()41kkkxxx 4213()23kkkkxxxx

13、 73496,8.49530710 xx22第二种格式比第一种格式收敛快得多第二种格式比第一种格式收敛快得多, ,而第三种格式而第三种格式不收敛。不收敛。可见迭代格式不同可见迭代格式不同, , 收敛情况也不同。收敛情况也不同。准确根准确根 = 1.124123029 。 x23例例2 用迭代法求方程用迭代法求方程0104)(23 xxxf2 , 1在在内的一个近似根，取初始近似值内的一个近似根，取初始近似值5 . 10 x解解原方程的等价方程可以有以下不同形式原方程的等价方程可以有以下不同形式xxxxxxxxxxx 410)4(1021)3(410)2(104)1(32324对应的迭代公式有：

14、对应的迭代公式有：nnnnnnnnnnxxxxxxxxxxxn 410)4(1021)3(410)2(104)1(1312311取取,5 . 10 x列表计算如下列表计算如下251.365230021.3659167381.365229941.3638870071.3652230581.3678469761.365225591.3600941951.365264751.3751702541.364957011.34545838-469.731.367376371.402540802.99696.73221.348399731.286953770.8165-0.87511.51.51.51.50

15、(4)(3)(2)(1)n表表2-226二、二、 迭代法的几何意义迭代法的几何意义一般来说从一般来说从,0)( xf构造构造)(x 不止一种，有的不止一种，有的收敛，有的不收敛，这收敛，有的不收敛，这取决于取决于 的性态的性态。)(x 方程方程 的根，在几何上就是直线的根，在几何上就是直线)(xx xy 与曲线与曲线 交点的横坐标交点的横坐标)(xy 。 x如图如图2-3所示所示27)1(1)(0 x 281()0(2)x 29()1(3)x ()1(4)x 30三、不动点的存在性与迭代法的收敛性三、不动点的存在性与迭代法的收敛性定理定理 1 (1) 当当xa , b时时，; ,)(bax (

16、2) 存在正数存在正数L1，使对任意的使对任意的 xa , b,。1)( Lx 方程方程在在a , b存在唯一根存在唯一根)(xx x, ,且满足条件且满足条件：设设 则则 ,)(baCx 31 证方程证方程)(xx 之解存在且唯一之解存在且唯一.由于由于)(x 在在 a , b上存在上存在, )()(xxxf f (x) 在在a , b上连续。上连续。作函数作函数由条件由条件)(x 连续连续。所以所以证证使使 0)( xf。)( xx 即即则则(1) f (a) 0 , f (b) 0 , 故存在故存在 ,bax 32则由微分中值定理及条件值定理及条件则由微分中值定理及条件值定理及条件(2)

17、(2)有有 xLxxx)()()(此式仅当此式仅当0 x才能成立才能成立，。 x 因此因此则由微分中值定理及条件则由微分中值定理及条件(2) 有有设方程设方程)(xx 还有一不动点还有一不动点, 33定理定理 2 (1) 当当xa , b时时，; ,)(bax (2) 存在正数存在正数L1，使对任意的使对任意的 xa , b,对任意迭代初值对任意迭代初值 x0a , b,迭代序列迭代序列), 2 , 1 , 0()(1 kxxkk 。1)( Lx , ,且满足条件且满足条件：设设收敛于收敛于 。 x 则则 ,)(baCx 11011kkkkkLxxxxLLxxxxL 且有下列误差估计式且有下列

18、误差估计式 34即迭代过程收敛，即迭代过程收敛， 且且。 xxkklim反复用此不等式，并注意反复用此不等式，并注意 0 L 1 ,111)()()( kkkkxxLxxxxxx )(00 kxxLxxkk因此因此先证迭代格式先证迭代格式)(1kkxx 收敛收敛任取任取 x0 a, b ，由微分中值定理，有由微分中值定理，有35提示提示：定理的证明利用定理定理的证明利用定理1 1以及微分中值定理。以及微分中值定理。3637则任取则任取 x0 U , )(1kkxx 迭代格式迭代格式均收敛于均收敛于 , x定理定理 3 若方程若方程)( xx 之根的某邻域之根的某邻域 L 1时称为时称为超线性收

19、敛超线性收敛.利用微分中值定理及泰勒展式可得下面的定理利用微分中值定理及泰勒展式可得下面的定理3. 显然显然,收敛阶越大收敛阶越大,收敛越快收敛越快.p = 2 时称为时称为二阶二阶( (平方平方) )收敛收敛, , 特别地特别地, ,令令, xxekk若若44则迭代过程在则迭代过程在 的邻近为的邻近为 p 阶收敛阶收敛。 x,1)(0 x (1) 若若为线性收敛为线性收敛；则迭代过程在则迭代过程在 的邻近的邻近 x, 0)(,0)()()()() 1( xxxxpp (2) 若若定理定理 4)(xx 之根之根, ,在在 的邻域的邻域 U内内)(x 有连续的有连续的 p 阶导数，阶导数，则则

20、设设 为为 x x454631)(limkkkxaxa 由泰勒展式可得由泰勒展式可得113311limlim()()3!4()kkkkkkaxeaeaax 解解)0( aa的三阶方法。假设的三阶方法。假设 x0 充分靠近充分靠近 , 求求证明迭代公式证明迭代公式 xk+1=xk(xk2+3a)/(3xk2+a) ，试求试求 x例例 247加速迭代法加速迭代法松弛法迭代公式：松弛法迭代公式：)()1()(111nnnnnnnxwxwxxw ), 2 , 1 , 0( nnw为松弛因子为松弛因子7.3 7.3 迭代收敛的加速方迭代收敛的加速方法法48称为称为斯蒂芬森斯蒂芬森 ( Steffense

21、n ) 加速法加速法. .则埃特金法为则埃特金法为平方收敛平方收敛；(1)1(2)(1)11(2)(1)2(2)1111(2)(1)11()()()2kkkkkkkkkkkxxxxxxxxxxx 若若)(1kkxx 为为 p ( p 1)阶收敛阶收敛，)(x 导数连续导数连续,的的 p 阶阶可以证明可以证明: :)(1kkxx 若若为线性收敛为线性收敛, ,则埃特金法为则埃特金法为 2p 1 阶收敛阶收敛。迭代格式迭代格式49 求方程求方程 x = e x 在在 x = 0.5 附近的根附近的根. .x25 = x26 = 0.5671433 若对此格式用若对此格式用斯蒂芬森斯蒂芬森法法, 则

22、则 取取 x0 = 0.5, 迭代格式迭代格式kxkex 1 得得解解例例3kxkex )1(1)1(1)2(2 kxkexkkkkkkkxxxxxxx )1(1)2(12)1(1)2(1)2(112)(50仍取仍取 x0 = 0.5 , 得得5671433. 05671433. 05671433. 05671433. 05672979. 05668708. 05676279. 05452392. 06065307. 03)2(3)1(32)2(2)1(21)2(1)1(1 xxxxxxxxx由此可见由此可见,斯蒂芬森斯蒂芬森法加速收敛效果是相当显著法加速收敛效果是相当显著的的. .51例例4

23、分别用松弛法、分别用松弛法、斯蒂芬森斯蒂芬森法求方程法求方程 在初值在初值 附近的一个根，取迭代格式附近的一个根，取迭代格式010423 xx5 . 10 x21410 xx解解 用松弛法计算，取用松弛法计算，取21410)( xx 234210)( xx 52因此松弛法的迭代公式为因此松弛法的迭代公式为 )(1421011123nnnnnnxwxwxxw , 2 , 1 , 0 n 列表计算如下：列表计算如下：1.3652300131.3652300121.3649539161.50.8871308690.8871308690.890803686 3 2 1 0nnwnx53用用斯蒂芬森斯蒂

24、芬森方法计算，迭代格式为：方法计算，迭代格式为：nnnnnnnnnnnxxxxxxxxxxx )1(1)2(12)1(1)2(1)2(1121)1(1)2(121)1(12)(410410, 2 , 1 , 0 n 54列表计算如下：列表计算如下：1.3652305831.3673763721.3652255341.3483997251.3652300131.3652652241.5 2 1 0 nnx)1(1 nx)2(1 nx557.4 7.4 牛顿法牛顿法一、牛顿法的基本思想一、牛顿法的基本思想 设已知方程设已知方程 f (x) = 0 的近似根的近似根 x0，且在且在 x0附近附近 可

25、用一阶泰勒多项式近似，表示为可用一阶泰勒多项式近似，表示为)(xf)()()(000 xxxfxfxf 方程方程 f (x) = 0 可用线性方程近似代替，即可用线性方程近似代替，即0)()(000 xxxfxf56解此线性方程得解此线性方程得)()(000 xfxfxx 取此取此 x 作为原方程的新近似根作为原方程的新近似根 x1，重复以上步骤重复以上步骤，得迭代公式得迭代公式1()(0,1,)()kkkkf xxxkfx 此式称为此式称为牛顿牛顿(Newton)迭代公式迭代公式。0)()(000 xxxfxf57例例 1 用牛顿法求方程用牛顿法求方程0104)(23 xxxf在在 内一个实

26、根，取初始近似值内一个实根，取初始近似值。5 . 10 x21 ，解解xxxf83)(2 所以迭代公式为：所以迭代公式为：, 2 , 1 , 0)83()104(2231 nxxxxxxnnnnnn列表计算如下：列表计算如下：1.365230011.365262011.37333331.5 3 2 10nnx58二、牛顿法的几何意义二、牛顿法的几何意义)()(000 xxxfxfy 0 x方程方程 的根就是曲线的根就是曲线 与与 轴交轴交点的横坐标点的横坐标 ，当初始值，当初始值 选取后，过选取后，过 作切线，其切线方程为：作切线，其切线方程为：0)( xf)(xfy x x)(,(00 xf

27、x)()(0001xfxfxx 它与它与x轴交点的横坐标为：轴交点的横坐标为：59一般地，设一般地，设 是是 的第的第n 次近似值，过次近似值，过 作作 的切线，其切线与的切线，其切线与x 轴交点的横坐标为：轴交点的横坐标为：nx x)(,(nnxfx)(xfy )()(1nnnnxfxfxx 即用切线与即用切线与 x 轴交点的横坐标近似代替曲线轴交点的横坐标近似代替曲线 与与x 轴交点的横坐标，如图轴交点的横坐标，如图2-4。60若过曲线若过曲线 y= f (x)上的点上的点 P ( xk , f ( xk )引切线，引切线，该切线与该切线与 x 轴交点的横坐标即为由牛顿迭代公式轴交点的横坐

28、标即为由牛顿迭代公式求得的求得的 xk+1 , 因此因此牛顿迭代法也称牛顿切线法牛顿迭代法也称牛顿切线法。图图2-461将原方程化为将原方程化为 x e x = 0，则则牛顿迭代格式为牛顿迭代格式为kkxxkkkeexxx 11取取 x0 =0.5，迭代得迭代得x1=0.566311, x2=0.5671431, x3=0.5671433 f(x)= x e x ， f (x)=1+ e x, 用牛顿迭代法求方程用牛顿迭代法求方程 x = e x 在在 x =0.5 附近的根。附近的根。例例4 4 解解 62三、牛顿迭代法的收敛速度三、牛顿迭代法的收敛速度)()()(xfxfxx 牛顿迭代法的

29、迭代函数为牛顿迭代法的迭代函数为 )()()(0)()()()( xfxfxxfxfxfx 不为不为 0由于由于 ,0)( xf所以当所以当 时时, ,0)( xf63只是收敛速度将大大减慢只是收敛速度将大大减慢。1、当当 为单根时，牛顿迭代法在为单根时，牛顿迭代法在根根 的附近的附近 是二阶收敛的是二阶收敛的； x x2、当当 为重根时，设为为重根时，设为m重根，则重根，则 f (x)可表为可表为 x)()()(xgxxxfm 其中其中 此时用牛顿迭代法求此时用牛顿迭代法求 仍然收敛仍然收敛，,0)( xg x64)()()()()()()(1kkkkkkkkkkxgxxxgmxgxxxxf

30、xfxx 事实上，因为事实上，因为令令 xxekk则则)()()(*11kkkkkkkkxgexmgxgeexxe 1()limlim1()()110kkkkkkkkeg xemg xe g xm 65可见用牛顿法求方程的重根时仅为线性收敛。可见用牛顿法求方程的重根时仅为线性收敛。1()limlim1()()110kkkkkkkkeg xemg xe g xm 663、计算重根的牛顿迭代法计算重根的牛顿迭代法有两种方法可以提高求重根的收敛速度：有两种方法可以提高求重根的收敛速度：1()()kkkkf xxxmfx 1）采用如下迭代格式采用如下迭代格式672）将求重根问题化为求单根问题，注意函数

31、将求重根问题化为求单根问题，注意函数)01)()()()()()( mxQxQxxxfxfxu所以化为求所以化为求 u(x)=0的单根是平方收敛的。的单根是平方收敛的。 12()()()()()()()kkkkkkkkkku xf xfxxxxu xfxf xfx 格式为格式为68 用牛顿迭代法求用牛顿迭代法求 f (x)=(x-1)sin(x-1)+3x-x3+1=0 在在0.95 附近之根附近之根。 取取 x0 = 0.95 用牛顿迭代用牛顿迭代法求得的法求得的 xk 见右表见右表。解解例例 5k xk k m0 1 2 3 4 5 60.95 0.9744279 0.9870583 0.

32、9934878 0.9967328 0.9983576 0.99919010.5090 0.5047 0.5007 0.51252.0369 2.0190 2.0028 2.0511可见可见 xk 收敛很慢。收敛很慢。69由重根数由重根数 m 为为 2 , 用加速法用加速法 x0=0.95 x1=0.9988559 x2=x3=1收敛速度大大加快于直接用牛顿迭代公式收敛速度大大加快于直接用牛顿迭代公式. .1()()kkkkf xxxmfx 求得求得704、简化牛顿迭代法简化牛顿迭代法1()(0,1,)kkkf xxxkM 此式称为此式称为简化牛顿迭代公式简化牛顿迭代公式。只要只要 M 选择得

33、当选择得当，上式总是线性收敛的。上式总是线性收敛的。在牛顿迭代公式中用一常数在牛顿迭代公式中用一常数 M 代替代替 得得, )(kxf 7172牛顿下山法牛顿下山法73用常数用常数 M 来代替来代替 f ( xk )虽然简单，但没充分虽然简单，但没充分利用利用 f (x)本身的特性本身的特性，因此收敛较慢。因此收敛较慢。若在牛顿迭代公式中改用差商若在牛顿迭代公式中改用差商11)()( kkkkxxxfxf代替导数代替导数 f (xk) ，得迭代公式得迭代公式1、割线（弦截）法割线（弦截）法7.5 7.5 弦截法与抛物线法弦截法与抛物线法74111()()()()kkkkkkkf xxxxxf xf x 每步只用一新点，此格式为每步只用一新点，此格式为弦截法（双点割线法）弦截法（双点割线法）。可以证明它的收敛阶为可以证明它的收敛阶为1(15)1.6182p 。确实比式确实比式1()kkkf xxxM 收敛快。收敛快。7576将式将式)()()()(0001xxxfxfxfxxkkkk 每步只用一新点，此格式为每步只用一新点，此格式为单点割线法。单点割线法。中的中的 xk-1 改为改为 x0，即即111()()()()kkkkkkkf xxxxxf xf x 773、割线法的几何意义、割线法的几何意义双点割线法是用过点双点割线法是用过点 和和 两两点的割线与点的割线与 x 轴交