数值计算方法二.

第二章非线性方程的数值解法2.1二分法2.2一般迭代法2.3牛顿迭代法2.4弦截法（1）确定初始含根区间数值计算方法主要分为两大类。第一类是区间收缩法。0)(:xf求解问题（2）收缩含根区间第二类是迭代法。（1）选定根的初始近似值（2）按某种原则生成收敛于根的近似点列2.1二分法(对分法)一、根的隔离将含根区间一个个隔开，找到根的范围，使每个区间只有一个根。定理：对f(x)=0,f(x)在[a,b]上连续,f(a)f(b)0且f(x)严格单调上升（或严格单调下降），则f(x)在[a,b]内仅有一根。1。利用零点存在定理2。搜索法：内含有根。在区间，但直到若出发，取步长的一根，则从内存在若已知))1(,(0)(0))1(()(0)())1((0)2()(,0)()()()(,00)(),(00000000000hixihxxfhixfihxfihxfhixfhxfhxfhxfxfhafafhaxxfba3。作图xxxx1tan1tan:例找出交点)2/,0(xxy*xxytanxy/1二、对分法设f(x)在（a,b)上连续且f(x)=0在（a,b)内只有一个根2),(),(),(00100baxbababa的中点，取第一步：记1。算法],[,0()(11011101babbxabfxf新的含根区间，则取）若1*10)(xxxf则取若],[2),2211211babaxba重复上述过程的中点第二步：取（110101,,0)()(xbaaafxf则取若;],[],[11kkkkkbaxbaK，记为的中点步：取第)(21)(21)(21)(),(),(00222110011abababababababkkkkkkkkkkkxxxxxkkklim,,,,:21且有次得到一个数列每次对分含根区间，依2。收敛性*0011*lim0)(21)(21xxababxxkkkkkkk根据精度终止计算。3。误差控制*1,?,0xxKk可以使问事先给定的事先误差估计abkababxxkkklg2lg)1(2)(2111*1即]2lg/[lg12lg/lgabKabk2lglg,10mabKm时特别当2,2.2,.1**kkkkkkkkbaxabbaxab取若或取若事后误差估计例2.1：试用二分法求的非零实根，使其误差小于10-204sin2xx09113.0)2(,244350.0)5.1(,5.13,5917.0)1(,12,4171.0)5.0(,5.0,0)(,0fhafhafhafhaafa4sin)(2xxxf令解：(1)根的隔离内有唯一的实根），在（04sin2xx2,5.100ba取取h=0.542xyxysinxy)2,5.1(04sin2xxx唯一的实根(2)预先算出计算步数5]64.5[]2lg2)5.12lg([2lglgmabK(3)计算（用表格形式写出来）的符号)(11kkkkxfxbak0(+)1.5(-)21.75+11.7521.875+21.87521.9375–31.8751.93751.90265+41.902651.93751.921875+51.921881.93751.92688+93.1255*bax2.1.3二分法评述优点：简单可靠，易于编程实现，它对函数要求低，适用于的奇数重根情形。缺点：不能直接用于求偶重根，不能用于求复根，也难以向方程组推广使用，收敛速度慢。2.2一般迭代法)1(0)(xf对迭代法的算法思想为：(A)把（1）等价变换为如下形式)2()(xgx的不动点称为当)(,)(*xgxxgx(B)建立迭代格式)3()(1kkxgx(C)适当选取初始值x0，递推计算出所需的解。一迭代法的算法思想迭代格式迭代函数其中)()(:1kkxgxxg称为简单迭代法或更一般地建立迭代格式)3()1(),,(11mxxxgxmkkkk例)3,2(052)(3xxxxf253xx由此建立迭代格式25)(),(31xxgxgxkk其中：352xx也可建立迭代格式3152)(,)(xxgxgxkk其中：,,,,),(,)()(2111201kkkxxxxgxxgxxgx得到数列,,,,),(,)()(2111201kkkxxxxgxxgxxgx得到数列-----发散-----收敛二迭代法的收敛性则称在内李普希兹连续。)(xg定义2.1设在某个区间内，函数满足下述李普希兹条件：)10,,(|||)()(|为常数LyxyxLygxg)())(()()(yxgygxg|||||)(||)()(|yxLyxgygxg命题得证。证则在内李普希兹连续。)(xg命题2.1若在闭区间内连续且)(xg)(1|)(|xLxg（1）首先用数学归纳法证明：,2,1,0kxk由假设知0x又设，则kx||kxx|||||)()(|||*1kkkkxxxxLxgxgxx所以1kx即综上，由归纳法原理知，结论成立。证定理2.1设x*=g(x*),g(x)在闭区间：内李普希兹连续，则对任何初值由迭代格式xk+1=g(xk)计算得到的解序列收敛于x*(这时我们称迭代格式xk+1=g(xk)在x*的邻域上局部收敛）。||xx0xkx)(0||||||01时kxxLxxLxxkkk因此，，定理得证。xxkklim反设存在)~(~,0)~(~,~xgxxfxxx即且|~||~||)()~(||~|0xxxxLxgxgxx则矛盾。所以结论成立。2)迭代函数在x*附近李普希兹连续从而收敛的迭代格式统称为皮卡（Picard）迭代(2)由（1）的结论和g(x)在内李普希兹连续的假设，可递推得到注1)g(x)在内李普希兹连续的条件保证了x*为f(x)=0在内的唯一根。证推论设x*=g(x*)，若g(x)在x*附近连续可微且，则迭代格式xk+1=g(xk)在x*附近局部收敛。1|)(|*xg注由于x*事先未知，故实际应用时，代之以近似判则。但需注意，这实际上是假设了x0充分接近x*，若x0离x*较远，迭代格式可能不收敛。1|)(|0xg定理2.2（非局部收敛定理）如果在上连续可微且以下条件满足：)(xg],[ba],[)(,],[)1(baxgbax则若1)(,],[)2(Lxgbax对.}{)(,],[,*1xxxgxbaxkkk收敛于的解序列对那么命题2.2若在区间内，则对任何，迭代格式不收敛。],[ba1][xg)(1kkxgx],[0bax]3,2[052)(3xxxxf2531kkxx3152kkxx发散收敛证明,25)(3xxg1|)('|]3,2[,23)('2xgxxg内在知由所以该迭代格式在内不收敛，不可取。352)(xxg易知在x0时g(x)单调增，故有2g(2)g(x)g(3)323321()03(25)20()(2)193gxxgxg又由在取间内单调减得故由定理2.2得：任取，该迭代格式收敛。0[2,3]x1ln1||ln|ln|101LxxLK||11kkxxLL（2）事后误差估计(1)事前误差估计简单地代之以||1kkxx)2/1(||1nkkaaxx或三、迭代法的误差估计对给定的精度可进行||*xxk例2.2试建立收敛的迭代格式求解x–e–x=0在x=0.5附近的一个根（ε=10-3）。解建立迭代格式5.0)(0xxgexx初始值,1)(15.000收敛kxkxexeexg00.560.5648610.6065370.5684420.5452480.5664130.5797090.5675640.56006100.5669150.57117kkkxkx3*10910100.567.xxxx四、迭代法的收敛速度与加速收敛技巧则称该迭代格式是p阶收敛的。p=1时称为线性收敛1p2时称为超线性收敛p=2时称为平方收敛。)112()0(1为常数CCeepkk定义2.2设迭代格式的解序列收敛于的根，如果迭代误差当时满足渐近关系式)(1kkxgxkxxxekkk)(xgx*x对分法：线性收敛212/)(4/)(2/)(2/)(111111**11kkkkkkkkkkkkababababxxxxee一般迭代法：线性收敛***11****()()()()()()1kkkkkkkkkexxgxgxgxxexxxxxxggx2.3牛顿迭代法一、牛顿迭代公式的构造设f(x)在其零点附近连续可微，已知为的第k次近似值，则*xkx)())(()()())(()()(12xPxxxfxfxxOxxxfxfxfkkkkkkk取的根作为的第k+1次近似值0)(1xPx1kx)122()()(1kkkkxfxfxx解得其迭代函数为)132()()()(xfxfxxg牛顿迭代法ABxyoabx1kx)(xfykx2kx几何意义：过点作函数y=f(x)的切线l：)(,kkxfxP))(()(kkkxxxfxfy以切线l与x轴的交点作为的新近似值1kx*x二、牛顿迭代法的收敛性与收敛速度定理2.3给定f(x)=0，如果在根附近f(x)二阶连续，且为f(x)=0的单根，则牛顿迭代法在附近至少是平方收敛的。*x*x*x证2)()()()(xfxfxfxg对牛顿迭代法首先证明牛顿迭代法的收敛性：因此由定理2.1的推论知，牛顿迭代法局部收敛。1)(xg即证1)(0)(0)(**xgxgxf而单根条件保证了其次证明牛顿迭代法的收敛速度：之间与介于由kkkkkxxxxfxxxfxfxf2))((21))(()()(0整理得212)()()(21)()()(21)()(kkkkkkkkxxxffxxxxffxfxfxx)()(21)()(2121xfxfxffeekkkk所以可见，当时，牛顿迭代法为平方收敛；当时，牛顿迭代法超平方收敛。0)(xf0)(xf例2.4试用牛顿迭代法求解在区间(2,3)内满足精度要求的根。052)(3xxxf810相应于该方程的牛顿迭代公式为2352231kkkkkxxxxx取x0=2，计算结果见表2-4。解0212.10.122.094568121-0.00543187932.094551482-0.00001663942.09455148201kkkxxxk83410xx牛顿迭代法评述优点：是收敛速度比较快缺点：(1)局部收敛，对初始值的要求比较高。为解决这一问题，可采用二分法来提供足够“好”的近似值作为迭代初值，或通过增加“下山”限制来放宽对初值的要求，即