第4章非线性方程数值解法

1、第4章 非线性方程的数值解法 本章重点介绍求解非线性方程 的几种常见和有效的数值方法,同时也对非线性方程组 求解,简单介绍一些最基本的解法.无论在理论上,还是在实际应用中,这些数值解法都是对经典的解析方法的突破性开拓和补充,许多问题的求解,在解析方法无能为力时,数值方法则可以借助于计算机出色完成.0)(xf), 2 , 1(0),(21nixxxfni4.1二分法求非线性方程0)(xf 确定方程的有根区间 计算根的近似值的根的方法分为两步：n首先确定有限区间：依据零点定理。 设 ，且 ，则方程 在区间 上至少有一个根。如果 在 上恒正或恒负，则此根唯一。,)(baCxf0)()(bfaf0)(

2、xf),(ba)(xf),(ba等步长扫描法求有根区间 n用计算机求有根区间：等步长扫描法。 设h0是给定的步长，取 ，若 则扫描成功；否则令 ，继续上述方法，直到成功。如果 则扫描失败。再将h 缩小，继续以上步骤。haxax10,0)()(10 xfxfhxxxx0110,bx 1等步长扫描算法 n算法：（求方程 的有根区间）(1) 输入 ；(2) ； (3) ，若 输出失败信息，停机。(4)若 。输出 ，已算出方程的一个根，停机。0)(xfhba,)(0aff )(,1xffhaxbx 01fx等步长扫描算法(5) 若 。输出 为有根区间，停机(6) ，转 3）n注：如果对足够小的步长h扫

3、描失败。说明：在 内无根在 内有偶重根010ff, ,xaxaxa ,ba,ba二分法 n用二分法(将区间对平分)求解。 令 若 ，则 为有根区间，否则 为有根区间 记新的有根区间为 ， 则 且 )(,1121111bacbbaa0)()(11cfaf,11ca,11bc,22ba,2211baba)(112122abab二分法n对 重复上述做法得n且 ,22ba.,.,2211nnbababa)(211ababnnn二分法 设 所求的根为 ， 则 即 取 为 的近似解 x.2 , 1,nbaxnn.2 , 1nbxann0)(21lim)(lim1nababnnnnxbannnnlimlim

4、)(21nnnbacxx求方程f(x)=0的根的二分法算法).(21)4(;endwhile.,;,0)()()2);(),(21)1|)3(;3,10)()()2(;,:)1 (baxbxbaelsexabathenxfafifxfbaxbawhileelsebathenbfafifbaba输出计算令时做步转第值输入重新步返回第值及精度控制量的有根区间输入求方程f(x)=0的全部实根的二分法算法);();(211|while)2endwhile;0)()(while) 1while) 3(;)2(;,:) 1 (11011111111111xfbaxabhabaabfafbbhabaahba

5、计算时做做时做输入求方程f(x)=0的全部实根的二分法算法;endwhile;10;:)3;endwhile.,0)()(if3);3(0)(if2111111111100habhxaxbxbaelsexabathenxfafxf输出转例题n例1 设方程 解：取h=0.1,扫描得： 又 即 在 有唯一根。 3( )1, , 1,1.5f xxxa b0344. 0)4 . 1 (061. 0)3 . 1 (ff.4 . 1 , 3 . 1 方程的有根区间为4 . 1 , 3 . 1 , 013)(2xxxf0)(xf4 . 1 , 3 . 1 nx=1:0.001:1.5; y=x.3-x-1

6、;nz=0; plot(x,y,r,x,z,b)11.051.11.151.21.251.31.351.41.451.5-1-0.8-0.6-0.4-0.200.20.40.60.81例2 对 求出1，1.5的实根，要求误差不超过0.005解：f=x3-x-1; bisection(f,1,1.5,20,5e-3) n xa xb xc fc n 1.0000 1.0000 1.5000 1.2500 -0.2969n 2.0000 1.2500 1.5000 1.3750 0.2246n 3.0000 1.2500 1.3750 1.3125 -0.05153( )1,fxxxn 4.000

7、0 1.3125 1.3750 1.3438 0.0826n 5.0000 1.3125 1.3438 1.3281 0.0146n 6.0000 1.3125 1.3281 1.3203 -0.0187n 7.0000 1.3203 1.3281 1.3242 -0.0021n x*= 1.32424.2一般迭代法n4.2.1 迭代法及收敛性 对于 有时可以写成 形式 如： 0)(xf)(xx3331101xxxxxxxxxxcos0cos迭代法及收敛性 考察方程 。这种方程是隐式方程，因而不能直接求出它的根，但如果给出根的某个猜测值 ， 代入 中的右端得到 ，再以 为一个猜测值，代入 的右

8、端得 反复迭代得)(xx0 x)(xx)(01xx1x)(xx)(12xx,.1 , 0)(k1kkxx迭代法及收敛性 若 收敛，即 则得 是 的一个根kx xxkklimx)(xx)()lim()(limlim1nxxxxxnnnnn迭代法的几何意义n 交点的横坐标 *x)()(xyxyxxy=x2x0 x1x简单迭代法 将 变为另一种等价形式 。选取 的某一近似值 ，则按递推关系 产生的迭代序列 。这种方法算为简单迭代法。0)(xf)(xxx,0bax ,.1 , 0)(k1kkxxkx例题n解：输入bdd12201(0,1,2,)(1)( )(14.2.1)10.0.4,4. kkxkx

9、f xx xx求解方程在区间0,1的一个实根 初始值精确至 位有例用迭代格效数字式0246810121416180.40.420.440.460.480.50.52例题 例4.2.2 试用迭代法求方程 在区间(1，2)内的实根。 解：由 建立迭代关系 k=10,1,2,3.计算结果如下:31xx01)(3xxxf311kkxx例题n精确到小数点后五位5102132472. 1x例题n但如果由 建立迭代公式 仍取 ，则有 ， 显然结果越来越大， 是发散序列1x3x,.2 , 1131kxxkk 5 . 10 x2.3751x12.392x kx迭代法的收敛性n定理4.2.1（压缩映像原理）设迭代

10、函数 在闭区间 上满足（1）（2） 满足Lipschitz条件即 有且 。 )(x ,ba,)(,baxbax)(x,21baxx)()(2121xxLxx10 L压缩映像原理则 在 上存在 唯一解 ，且对 ，由 产生的序列 收敛于 。 )(xx,0bax )(k1kxx.1kxx,bax压缩映像原理n证明：不失一般性,不妨设 否则 为方程的根。n首先证明根的存在性 令 bbaa)(,)(ba或xxx)()(压缩映像原理 则 ， 即 由条件2） 是 上的连续函数 是 上的连续函数。故由零点定理 在 上至少有一根0)()(aaa0)(b0)()(ba)(x,ba)(x所以,ba0)(x,ba),

11、(bax 压缩映像原理n再证根的唯一性 设有 均为方程的根 则 因为 0L1 ，所以只可能 ， 即根是唯一的。,21baxx| )()(|212121xxLxxxx21xx压缩映像原理n最后证迭代序列的收敛性 与n 无关，而0L1 即| )()(|1xxxxnn由于|1xxLn|0 xxLn.xx ,0因为0lim|lim0nnnnLxxxx所以 xxnnlim压缩映像原理n误差估计 n若 满足定理2.2.1条件，则n 这是事后估计，也就是停机标准。L越小，收敛速度越快。n 这是事前估计。选取n，预先估计迭代次数。 )(xx|L1L|1nnxxxxn|L1L|01nxxxxn例题n例例4.2.

12、2 证明函数 在区间1，2上满足迭代收敛条件。n证明：31)x(x上严格单调增函数。是区间所以因为,)(2 , 1 0) 1(31)x(32baxxx例题 2 , 1 1431|) 1(31| )(|332xLxx又23)2(12) 1 (33，而）。满足条件（，所以即1)(2 , 1 )2(),1 (x）。满足条件（所以2)(x满足压缩映像原理。在故2 , 1 1)x(3x例题n若取迭代函数 ， 不满足压缩映像原理，故不能肯定 收敛到方程的根。 1)x(3 x2 , 1 3|3| )(|2xxx因为,.1 , 0)(1nxxnn简单迭代收敛情况的几何解释4.3 Newton迭代法n设x *

13、是方程f (x ) = 0的根，又x0 为x * 附近的一个值 ，将f (x ) 在x0附近做泰勒展式 令 ，则 之间和在其中020000)()(21)()()()(xxfxxxfxxxfxf *xx )()(21)()()()(020*00*0*fxxxfxxxfxf Newton迭代法去掉 的二次项，有：即以x1代替x0重复以上的过程，继续下去得：0*xx 0)()()(000*0 xfxxfxxf)()(0001*xfxfxxxNewton迭代法,.1 , 0)()(1nxfxfxxnnnn以此产生的序列Xn得到f(x)=0的近似解，称为Newton法，又叫切线法。Newton迭代法几何

14、解释n几何意义例题n例4.3.1 用Newton法计算 。解：220)(2aaxxf其中迭代公式得及由Newtonxxf2)(,.1 , 0)2(212221nxxxxxxnnnnnn。有十位有效数的近似值是已的精确值相比，。与，则取332102414213562. 1414215686. 11.416666675 . 1xxxxxNewton迭代法算法框图Newton迭代法算法。输出）转（做输入1101001001000:)4(;2) 3;)2;/) 1|while(3);();()2(;,) 1 (xendwhilexxffxxfxffxffxn解：f=inline(x3+2*x2+10*

15、x-20);n df=inline(3*x2+4*x+10);n Newton(f,df,1.5,0.5e-6)32*2102001.368808107.Leonardoxxxx例4.3.2 公元1225年，宣布他求得方程的一个根当时颇为轰动，但无人知道他是用什么方法得到的.试用牛顿迭代法解读这个结果.nIt.no= 0 x 0= 1.500000000nIt.no= 1 x 1= 1.373626374nIt.no= 2 x 2= 1.368814820nIt.no= 3 x 3= 1.368808108nIt.no= 4 x 4= 1.368808108Newton迭代法收敛性定理2.3.

16、1 设函数 ，且满足 若初值 满足 时，由Newton法产生的序列收敛到 在a,b上的唯一根。,)(2baCxf上恒正或恒负。在,)() 3);,( , 0)()2; 0)()() 1baxfbaxxfbfaf ,0bax 0)()(00 xfxf0)(xfNewton迭代法收敛性证明： 根的存在性n根的唯一性内至少有一个根。在知）及由条件（),(0)(,)(1baxfbaCxf。记此根为内有唯一根在上严格单调函数，因此是故保号，知及由*,),(0)(,)()(,bCa,)(, 0)(xbaxfbaxfxfxfxfNewton迭代法收敛性n收敛性)()(0)()(0)(, 0)(, 0)(,0

17、)()(0)(, 0)(, 0)(, 0)(010000001000*000 xxxfxfxxfxfxxxfxfxfbxxxfxfxfxfbfaf 即有，所以知，由，不妨设Newton迭代法收敛性 继续上述推理有代替。再以因此有两式相减展式由另一方面0101*20*01*20*0*00*0)()()(21)(21)()()(0Taylor,xxxxxxxxffxxxxfxxxfxfxf Newton迭代法收敛性。，由根的唯一性知可得时当由。故必有极限，记。是单调减有下界的序列故序列*10011*0)(,.2 , 1)()(lim.xaafnnxfxfxxaxxxxxxxnnnnnnnnnNew

18、ton迭代法收敛性n推论 在定理4.3.1条件下， Newton迭代法具有平方收敛速度。故结论成立。之间，则与介于其中，证明，一般有类似定理证明0)()(21lim)()()(211 . 3 . 2* 21*2*1n* xfxfeexxxxxffxxnnnnnnnn代数方程的Newton迭代法n代数方程的Newton迭代法推导设n次代数方程用Newton迭代法求有限区间的实根，则要计算 ，一般采用秦九韶算法。,.2 , 1)()(1nxfxfxxnnnn)0(0)(0110 aaxaxaxfnnn)(),(nnxfxf代数方程的Newton迭代法n由Taylor展式)2(!)()(.! 2)(

19、)()()() 1 ()()()(!)()(.! 2)()()()()()()(1)(2nxfxxxfxxxfxQxQxxxfnxfxxxfxxxfxxxfxfnnnnnnnnnnnnnnnnnn 其中代数方程的Newton迭代法 ) 3()()()()(),()()2(12110 nnnnnnnbxbxbxQxQxxxfxfxQ的余式，令除以为且式知，由);()(1)() 1 (nnxfxQnxfxx，余式为次多项式为，得商）去除式表示，用（nnnnnnnnnaxaxaxabxbxbxxxfxf 111012110.)()()(1) 3(）式得式代入（),.,2 , 1()(100nkxxf

20、bbababxnnnkkk的同次幂系数得比较等式两边代数方程的Newton迭代法同理 )()()()()(xRxxxfxQxQxxnnn有取除以用)4()(23120 nnncxcxcxR令12211023120.)()()() 3 () 4( nnnnnnnnnbxbxbxbcxcxcxxxfxQ式得式代入代数方程的Newton迭代法比较x的同次幂系数得：故代数方程的Newton迭代公式) 1,.,2 , 1()(1100nkxxfccbcbcnnnkkk,.)2 , 1(11ncbxxnnnn代数方程的Newton迭代法算法步。返回第停止计算输出做对计算输入2)(,;,|(4);)(3;1

21、,.,2 , 1)2;) 1);(),()2(;,),.,2 , 1 , 0(:) 1 (101*01100101010000100000 xxelsexxthenxxifffxxxfffxfafnkffafxfxfxniaki 4.4弦截法nNewton迭代法有一个较强的要求是 且存在。因此，用弦的斜率 近似的替代 。 0)( xf)(xf )()()()()(,(P)(,(P,)(10101111100010*xxxxxfxfxfyxfxxfxbxaxxbaxf得弦的方程及则过，取上有唯一零点在设弦截法n令y=0,解得弦与x轴的交点是坐标x2.,.)2 , 1()()()(.,)()()(0)()()()(00132010101121201011称之为定端点弦截法计算再由解得nxfxfxfxxxxxxxxfxfxfxxxxxxxxxfxfxfnnnnn弦截法.,.)2 , 1()()()(,111321又称快速弦截法称之为变端点弦截法以此类推计算若由nxfxfxfxxxxxxxnnnn