第二章-一元非线性方程的数值解法

第二章一元非线性方程的数值解法在科学和工程计算中，如电路和电力系统计算、非线性微分和积分方程、非线性规划、非线性力学等众多领域中，经常会遇到求解非线性方程的问题．非线性科学是当今科学发展的一个重要的研究方向，而非线性方程的数值解法又是其中不可缺少的内容．本章主要讨论一元非线性方程0)(xf(5.0.1)的数值解法，其中Rx，)(xf为x的非线性函数．在方程(5.0.1)中，若函数)(xf是x的n次多项式，则称方程(5.0.1)为多项式方程或代数方程：023368xxx；若函数)(xf是超越函数（自变量之间的关系不能用有限次加、减、乘、除、乘方、开方运算表示的函数。如指数函数、对数函数、三角函数和反三角函数等都是超越函数），则称方程(5.0.1)为超越方程：例06tan3xex使()0fx的*x称为方程0)(xf的根，又称为函数)(xf的零点．若)(xf可分解为)(xf=)()(*xgxxm，其中m为正整数，且0)(*xg．当m=1时，称*x为方程0)(xf的单根，而当1m时，则称*x为方程0)(xf的m重根，或称*x为)(xf的m重零点．设*x为)(xf的m重零点，且)(xg充分光滑，则0)()()(*)1(**xfxfxfm，0)(*)(xfm.根的求解：对于n次多项式方程，当次数4n时，多项式方程的根可用求根公式表示：2,1n时方程的根是我们已经熟知的，4,3n时虽然有求根公式，但已不适合用于数值计算；而次数5n时，就不能用公式表示多项式方程的根了．因此，对于次数3n的多项式方程和一般连续函数方程(5.0.1)，在实际应用时，通常并不需要得到方程根的解析表达式，只要得到满足一定精度的数值近似根就可以了．对于非线性方程0)(xf，求其近似数值根一般分为四步：(1)判断根的存在性：判断方程0)(xf是否有根？若有，有几个？(2)确定根的分布范围：分析并估计方程根的分布情况，并将每一个根用相应区间分隔开，即确定方程根的有根区间；(3)根的初始化：确定根的初始近似值(称之为初始近似根)；(4)根的精确化：对根的某个初始近似值设法逐yaObxx*图5.1步精确化，使其满足一定的精度要求．由以上步骤可以看出，求非线性方程数值近似根的方法一般为迭代法．第一节初始近似根的确定一、有根区间的确定设)(xf为区间],[ba上的连续函数，若0)()(bfaf，由闭区间上连续函数的性质（根的存在定理）可知，方程0)(xf在),(ba内至少存在一个实根，此时则称],[ba为方程0)(xf的有根区间(RootedInter-val)．此外我们也可以借助某些数学软件(如MathCAD,Mathematics,Matlab等)描绘出)(xf的图像，直观地了解方程0)(xf根的分布情况．因此，我们可用试探的办法或根据函数的图象，确定出根的分布范围，即将函数)(xf的定义域分成若干个只含一个实根的区间．例5.1试确定方程01)(6xxxf的有根区间.解由于16)(5xxf，当561x时0)(xf，则)(xf为严格单调增函数；而当561x时0)(xf，则)(xf为严格单调减函数．又由于0615f，0)(f，所以方程01)(6xxxf只有两个实根．经进一步分析可知，0)2()1(ff，则方程在[1，2]内有一个实根；0)0()1(ff，则方程的另一个实根在[-1，0]内.下面介绍的几种求方程的根的常用数值解法，即二分法，牛顿迭代法，都是将方程的初始近似根逐步精确化的方法．第二节二分法二分法也称为区间对分法，是解非线性方程最直观、最简单的方法．为讨论方便，不妨设函数)(xf在],[ba上连续，严格单调，且0)()(bfaf，则方程0)(xf在区间],[ba内有且仅有一个实根x．二分法的基本思想：将方程的有根区间平分为两个小区间，然后判断根在哪个小区间，舍去无根小区间，而后再把有根的小区间一分为二，判断根属于哪个更小的区间，如此反复，直到求出满足精度要求的近似根．二分法的具体计算过程如下：1.取区间],[ba的中点)(210bax，计算区间中点函数值)(0xf，并判断：若0)()(0xfaf，则根],[0xax，令011,xbaa，则新的有根区间为],[11ba；若0()0fx，则0x即为所求根x；若0)()(0xfaf，则根],[0bxx，令bbxa101,，则新的有根区间为],[11ba．2.对有根区间11[,]ab施行同样的操作，即取中点)(21111bax，再将11[,]ab分为两个子区间11[,]ax和11[,]xb，计算)(1af和)(1xf，若0)()(11xfaf则11[,]xax，令1212,xbaa；否则11[,]xxb，令1212,bbxa．这样又确定了一个有根区间22[,]ab，其长度是区间11[,]ab长度的一半．如此反复，便得到一系列有根区间],[],[],[],[2211nnbabababa显然，区间],[nnba的长度为nnnnnababab2211(5.2.1)abxy0y=f(x)x0b1a1abxy0y=f(x)x0b1a1图5.2二分法示意图当n时，上式的极限为0，区间[,]kkab最终必收敛于一点,该点就是所求方程(5.0.1)的根x．我们取二分后的最后的有根区间],[nnba的中点nx作为方程(5.0.1)的根x的近似根2nnnbax，],[nnnbax，其误差估计式为||*nxx2nnab12nab(5.2.2)当n时，取||*nxx02nnab，即*xxn．对预先给定的精度0(即指定的绝对误差限)，可以用以下方式结束二分法：当||11nnab时，必有||nxx，结束二分法计算，取nxx；二分法的计算步骤如下：(1)输入有根区间的端点ba,及预先给定的精度；(2)2/)(:bax；(3)若0)()(xfaf，则xb:，转向(4)；否则xa:，转向(4)；(4)若ab，则输出方程满足精度的根x，结束；否则转向(2)．二分法的优点：1、是算法简单；2、对函数的性质要求较低(只要连续即可)；3、收敛性可保证．二分法的缺点：1、收敛速度很慢；2、不能求偶数重根，原因在于当方程(5.0.1)有偶数重根时所分区间端点处函数值同号，而将该区间舍去造成失根现象．因此．在实际应用时，可用它求方程根的初始近似值．例5.2用二分法求方程01)(23xxxf在]1,0[上的根(取310)．解(1)这里1,0ba，01)1(,01)0(ff，得有根区间]1,0[；(2)计算0125.0)5.0(,5.02100fx，得有根区间]1,5.0[；(3)计算001563.0)75.0(,75.0215.02fx得有根区间]1,75.0[；如此继续，直到3110kkxx时停止，计算结果见表5.1：表5.1kkakbkx()kfx1kkxx012345678900.50.750.750.750.750.750.750.753910.753911110.8750.81250.81250.765630.757820.757820.755870.50.750.8750.81250.781250.765630.757820.753910.755870.75489-0.625-0.015630.435550.196540.087190.034990.00950-0.003110.003200.000040.50.250.125-0.0625-0.03125-0.01562-0.00781-0.003910.00196-0.00098由表5.1知3980.0009810xx所以原方程在]1,0[内的根*90.75489xx．第三节牛顿迭代法及其收敛性迭代法在数学的各个分支都有着重要的应用．本节主要讨论迭代法在非线性方程求根的应用．一、迭代法的基本思想迭代法的基本思想是：将方程(5.0.1)中()0fx化为下列等价形式)(xgx(5.3.1)若要求*x满足0)(*xf，则只需求出)(**xgx即可；反之也是如此，则称*x为函数)(xg的一个不动点，求函数)(xf的零点就等价于求函数)(xg的不动点．在有根区间内选一个初始近似值0x，然后按(5.3.1)构造公式,2,1,0),(1kxgxkk(5.3.2)可得到一个数列,,,,,210kxxxx称kx为迭代序列，而称(5.3.1)式中的)(xg为迭代函数．如果迭代序列kx是收敛的，且收敛于*x，则当)(xg连续时，在(5.3.2)式两边取极限即得)(**xgx，即0)(*xf从而*x便是方程(5.0.1)的根．但实际计算当然不可能做无穷多步，实用上，当k充分大时，若1kkxx就取kx作为原方程的近似根．这种求根法称为不动点迭代法，或称逐次逼近法(Picard迭代法)．(5.3.2)就是一个不动点迭代公式．当迭代公式(5.3.2)产生的迭代序列kx收敛时，就称迭代法或迭代公式(5.3.2)是收敛的，否则就称为是发散的．二、不动点迭代法的构造我们使用迭代法求解非线性方程(5.0.1)时需要解决如下四个问题：(1)迭代函数的构造；(2)初始近似根的选取；(3)迭代序列收敛性分析；(4)收敛速度和误差分析．三、牛顿迭代法及其收敛性设x是一元非线性方程0)(xf的根，函数)(xf在*x的某邻域内连续可微，kx是某个迭代近似根，且0)(kxf．把)(xf在点kx处进行一阶泰勒展开，可得))(()()(kkkxxxfxfxf则方程0)(xf可近似表示为0))(()(kkkxxxfxf(5.3.3)这是一个线性方程，求解得)()(kkkxfxfxx将其右端项作为新的迭代值1kx，则可得迭代公式)()(1kkkkxfxfxx,2,1,0k(5.3.4)这就是牛顿迭代法(Newton’sMethod)，(5.3.4)称为牛顿迭代公式.如图5.3所示，曲线)(xfy与x轴的交点x就是方程0)(xf的根．设xk是方程0)(xf的一个近似根，过曲线yfx()上的点))(,(kkkxfxP作切线，切线与x轴的交点为xk1,切线的方程为yfxfxxxkkk()()()设切线点与x轴的交点为(,)xk10，若0)(kxf，则可得牛顿迭代公式(5.3.4))()(1kkkkxfxfxx,,2,1,0k因此，牛顿迭代法又称为切线法(TangentMethod)．牛顿迭代法的几何意义：用曲线)(xfy在点))(,(kkxfx处的切线与x轴的交点的横坐标1kx来代替曲线)(xfy与x轴交点的横坐标x．牛顿迭代法的计算步骤为：图5.3切线法示意图()1给出初始近似根0x及精度；()2计算)()(:0001xfxfxx；()3对于给定的允许误差，若01xx,转向()4；否则10:xx,转向()2；()4输出满足精度的根1x，结束．例5.3用牛顿迭代法求方程01xxe在5.0x附近的根，精度为810．解这里1)(xxexf,xxxeexf)(，相应的牛顿迭代公式为kxkkxkxxkkkxexxexeexxxkkkk111,,2,1,0k取5.00x，迭代结果见表5.3，易见8341000001000.0||xx故567143290.04xx迭代了4次就得到了较满意的结果．例5.4用牛顿法计算3．解令3x，则032x，即求3等价于求方程03)(2xxf的正实根．因为xxf2)(，由牛顿迭代公式得)3(212321kkkkkkxxxxxx