非线性方程的数值解法

第二章非线性方程的数值解法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。利用零点存在定理。一、根的隔离01:5xx例]2,1[15)(214xxxf对而）内至少有一个根。，则在（0)2(1)1(1)(5ffxxxf解：）内只有一根，在（严格单调上升21)()(0)(xfxfxf2。作图x1tgx1xtgx:例xyy=tgxy=1/x找出交点x3。隔离法：内含有根。则说明在区间直到出现的符号，再求若出现出发，取步长的一根，则可以从内存在若已知)h)1i(x,ihx(,0)h)1i(x(f)ihx(f)h2x(f)hx(f,0)hx(f)x(f)ha(f)a(f,0hax0)x(f)b,a(000000000设f(x)在（a,b)上连续且f(x)=0在（a,b)只有一个根1。算法00000*0000000001010000011011(,)(,)(,)2()022()()0,,22()(0,22[,]ababxababababfxababffaaabababffbabbab：取的中点若则取若则取若）则取，新的含根区间第一步二、对分法1111122(,)2[,]ababxab第二取的中点重复上述过程步：11111100112200212[,]2[,](,)(,)()111()()()222,,,,kkkkkkkkkkkkkkkkkkkkabababbababababababaxKxxxxk-1：取的中点x=，得新的含根区间，每次对分含根区间，依次得到一个数列第步2。收敛性*001*0)(21)(21xxababxxkkkkkkk3。误差控制**110,?,1()22(1)lg2lgkkkkKxxxxbababak对事先事给定的问可以使即前误差估计2lglg,10]2lg/[lg12lg/lgmabKabkabkm时特别当**1.,2.2,2kkkkkkkkbaxababbax若事后误差取或若取估计解例2.1：试用二分法求的非零实根，使其误差小于.4xxsin)x(f2210)2,5.1(x(2b,5.1a*00由图示：可知来）要求用表格的形式写出取4xy2xsinyxY)(kkkkxfxbak0(+)1.5(-)21.750.21836111.7521.8750.75179521.87521.9375-0.0049628831.8751.93751.902650.040420841.902651.93751.9218750.15601451.921881.93751.926880.0053634093.1xx5*2.1.3二分法评述优点：简单可靠，易于编程实现，它对函数要求低，适用于的奇数重根情形。缺点：不能直接用于求偶重根，不能用于求复根，也难以向方程组推广使用，收敛速度慢。2.2一般迭代法)22(0)(xf对迭代法的算法思想为：(1)把（2-2）等价变换为如下形式)22()(xgx的不动点称为从而)x(gx,)x(gx*(2)建立迭代格式)32()(1kkxgx或更一般地建立迭代格式)32()1(),,(11mxxxgxmkkkk(3)适当选取初始值，递推计算出所需的解。一迭代法的算法思想()0()fxxgx法以上方法称为简单迭代迭代格式初始值迭代序列迭代函数其中)()(10kkkxgxxxxg1()kkxgx)2()(10)(xgxxf）（3331011xxxxxx例：或,,,,)()()()(21112010kkkxxxxgxxgxxgxxxxgx得到数列代入右边出发，取从*{}?2.(){}kkxxgxx0问题：1.是否收敛？收敛于精确解如何选择x及，使是收敛。3.如何估计误差二迭代法的收敛性则称在内李普希兹连续。)(xg定义2.1设在某个区间内，函数g(x)满足下述李普希兹条件：)10,,(|||)()(|为常数LyxyxLygxg则在内李普希兹连续。)(xg命题2.1若在闭区间内连续且)(xg)(1|)(|xLxg)())(()()(yxgygxg|||||)(||)()(|yxLyxgygxg命题得证。证定理2.1设x*=g(x*),g(x)在闭区间：内李普希兹连续，则对任何初值由迭代格式xk+1=g(xk)计算得到的解序列收敛于x*(称迭代格式xk+1=g(xk)在x*的邻域上局部收敛）。||xx0xkx（1）首先用数学归纳法证明：,2,1,0kxk由假设知0x又设，则kx||kxx|||||)()(|||*1kkkkxxxxLxgxgxx所以1kx即综上，由归纳法原理知，结论成立。证)(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三、迭代法的误差估计)42(),2,1(||||11kxxLxxkkkk1121||||||(1,2,)ksksksksskkxxLxxLxxs故对正整数p，有||)1(1||)(||||||||1111211kkpkkppkkpkpkpkpkkpkxxLLLxxLLLxxxxxxxx取极限得令p)52()(1||1kkkxxLLxx||1||01xxLLxxkk1ln1||ln|ln|101LxxLK（2）事后误差估计由此，对给定的精度可进行|~|*xx(1)事前误差估计||11kkxxLL简单地代之以||1kkxx)2/1(||1nkkaaxx或四、迭代法的收敛速度与加速收敛技巧则称该迭代格式是p阶收敛的。p=1时称为线性收敛1p2时称为超线性收敛p=2时称为平方收敛。)112()0C(Ceepk1k为常数定义2.2设迭代格式的解序列收敛于的根，如果迭代误差当时满足渐近关系式)(1kkxgxkxxxekkk)(xgx*x例2.2试建立收敛的迭代格式求解在x=0.5附近的一个根。0exx310解建立迭代格式5.0x)x(gex0x初始值1kkk1kkk*x1k5.0x0xxxkxxxk)6.0,5.0(x1.0h,ex1ee)x(gk0用搜索法，取收敛00.5060.56486-0.0063110.606530.1065370.568440.0035820.54524-0.0612980.56641-0.0020330.579700.0344690.56756-0.0011540.56006-0.01964100.56691-0.0006550.571170.01111对分法：线性收敛212/)ab(4/)ab(2/)ab(2/)ab(xxxxee1k1k1k1k1k1kkk*k*1kk1k一般迭代法：线性收敛)1)x(g)x(gx(1)x(g)(gxx)xx)((gxx)x(g)x(gxxxxee*k*k*k*k*k*k*1kk1k2.3牛顿迭代法一、牛顿迭代公式的构造设f(x)在其零点附近连续可微，已知为的第k次近似值，则*xkx)())(()()())(()()(12xPxxxfxfxxOxxxfxfxfkkkkkkk取的根作为的第k+1次近似值0)(1xPx1kx)122()()(1kkkkxfxfxx解得其迭代函数为)132()()()(xfxfxxg牛顿迭代法几何意义：过点作函数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知，牛顿迭代法局部收敛。首先证明牛顿迭代法的收敛性：证1L)x(g即证1L)x(gxx,00)x(g0)x(f***时，使而单根条件保证了其次证明牛顿迭代法的收敛速度：之间与介于由kkkkkxxxxfxxxfxfxf))((21))(()()(0整理得212)()()(21)()()(21)()(kkkkkkkkxxxffxxxxffxfxfxx)x(f)x(f21)x(f)(f21eekk2k1k所以可见，当时，牛顿迭代法为平方收敛；当时，牛顿迭代法超平方收敛。0)(xf0)(xf例2.4试用牛顿迭代法求解在区间(2,3)内满足精度要求的根。052)(3xxxf810相应于该方程的牛顿迭代公式为2352231kkkkkxxxxx取x0=2，计算结果见表2-4。解牛顿迭代法评述优点：是收敛速度比较快缺点：(1)局部收敛，对初始值的要求比较高。为解决这一问题，可采用二分法来提供足够“好”的近似值作为迭代初值.（2）当为重根时，牛顿迭代法仅仅线性收敛。)2(0)(mxf的*x（3）由于涉及的计算，导致了对函数的要求高，并增加了每一迭代步的计算量，这在一定程度上减弱了该迭代法收敛快的优越性