newtoniteration

数值分析数值分析在科学研究的数学问题中更多的是非线性问题，它们又常常归结为非线性方程或非线性方程组的求解问题。1非线性方程求根的迭代法2非线性方程的Newton型迭代法3Newton型迭代法的改进第七章非线性方程的数值方法数值分析数值分析满足方程(1)的x值通常叫做方程的根或解，也叫函数f(x)=0的零点。非线性方程的一般形式f(x)=0(1)这里f(x)是单变量x的函数，它可以是代数多项式f(x)=a0+a1x+……+anxn(an≠0)也可以是超越函数，即不能表示为上述形式的函数。1.非线性方程求根的迭代法数值分析数值分析在用近似方法时，需要知道方程的根所在区间。若区间a,b含有方程f(x)=0的根，则称a,b为f(x)=0的有根区间；若区间a,b仅含方程f(x)=0的一个根，则称a,b为f(x)=0的一个隔根区间。求隔根区间有两种方法：一、非线性方程求根的基本问题包括：根的存在性、根的隔离和根的精确化根的存在定理(零点定理)：f(x)为[a,b]上的连续函数，若f(a)·f(b)0，则[a,b]中至少有一个实根。如果f(x)在[a,b]上还是单调递增或递减的，则f(x)=0仅有一个实根。数值分析数值分析例如，求方程3x-1-cosx=0的隔根区间。将方程等价变形为3x-1=cosx，易见y=3x-1与y=cosx的图像只有一个交点位于[0.5，1]内。画出y=f(x)的略图，从而看出曲线与x轴交点的大致位置。也可将f(x)=0等价变形为g1(x)=g2(x)的形式，y=g1(x)与y=g2(x)两曲线交点的横坐标所在的子区间即为含根区间。(1)描图法数值分析数值分析(2)逐步搜索法运用零点定理可以得到如下逐步搜索法：先确定方程f(x)=0的所有实根所在的区间为[a,b],从x0=a出发,以步长h=(b-a)/n其中n是正整数，在[a,b]内取定节点：xi=x0＋ih(i=0,1,2，……，n)计算f(xi)的值,依据函数值异号及实根的个数确定隔根区间,通过调整步长，总可找到所有隔根区间。数值分析数值分析例2.2求方程x3-3.2x2+1.9x+0.8=0的隔根区间。解：设方程的根为α，ν=max{1，|-3.2|，|1.9|}8.01μ=max{|-3.2|,|1.9|,|0.8|}=3.2故,即有根区间为(-4.2,-0.2)和(0.2,4.2)2420.||.对于m次代数方程f(x)=xm+am-1xm-1+…+a1x+a0=0其根的模的上下界有如下结论：(1)若μ=max{|am-1|,……,|a1|,|a0|}，则方程根的模小于μ+1(2)若ν=max{1，|am-1|,……,|a1|},则方程根的模大于01a11数值分析数值分析f=inline('x^3-3.2*x^2+1.9*x+0.8')h=1;n=4/h;fori=0:nf(-4.2+i*h)endfori=0:nf(0.2+i*h)end数值分析数值分析h=0.8-1.377160000000e+002-81.95600000000002-43.34800000000001-18.81999999999999-5.300000000000000.284000000000001.060000000000000.50000000000000-0.316000000000001.684000000000009.5720000000000026.42000000000000h=1-1.377160000000e+002-70.81600000000002-29.51600000000001-7.816000000000000.284000000000001.060000000000000.200000000000000.140000000000006.8800000000000026.42000000000000数值分析数值分析定义1若有x*满足(x*)=0，则称x*为方程的根或函数f(x)的零点，特别地，如果函数f(x)可分解为f(x)=(xx*)mg(x)且g(x*)0,则称x*是f(x)的m重零点或f(x)=0的m重根。当m=1时，称x*是f(x)的单根或单零点。数值分析数值分析定理1设函数f(x)∈Cm[a,b],则点p∈(a,b)是f(x)的m重零点，当且仅当f(p)=f’(p)=f’’(p)=…=f(m-1)(p)=0,但f(m)(p)≠0证明:(充分性)将f(x)在点p作m-1阶Taylor展开之间。与位于pxpxmfpxmpfpxpfpfxfxmxmmm)(!)()()!1()())((')()()(1)1(由假设)()()(!)()()(xgpxpxmfxfmmxm0!)()()(mpfpgm这里，证毕.)(1重零点的是，由定义mxfp!)()()(mfxgxm数值分析数值分析例给定方程：x-sinx=0,问x*=0是几重零点.解：设f(x)=x-sinx,则f(0)=0;f’(x)=1-cosx,f’(0)=0;f’’(x)=sinx,f’’(0)=0;f(3)(x)=cosx,f(3)(0)=1;由定理1,x*=0是3重零点.数值分析数值分析)lim()(limlim1kkkkkkxxx知α=φ(α)，即{xk}收敛于方程的根α。二、简单迭代法简单迭代法又称为不动点迭代法，基本思想是首先构造不动点方程x=φ(x)，即由方程f(x)=0变换为等价形式x=φ(x),式中φ(x)称为迭代函数。然后建立迭代格式：xk+1=φ(xk)称为不动点迭代格式。当给定初值x0后,由迭代格式xk+1=φ(xk)可求得数列{xk}。如果{xk}收敛于α，且φ(x)在α连续，则α就是不动点方程的根。因为：数值分析数值分析迭代法的几何意义记y1=x,y2=φ(x),它们交点的横坐标α即为方程的根xy1)(2xy))(,(00xx))(,(11xx),(22xx))(,(22xx),(11xx0x2x1xpxy00x1x2x)(2xyxy1xy0数值分析数值分析xyy=xxyy=xxyy=xxyy=xx*x*x*x*y=φ(x)y=φ(x)y=φ(x)y=φ(x)x0p0x1p1x0p0x1p1x0p0x1p1x0p0x1p1数值分析数值分析对于迭代法需要讨论的基本问题是，迭代函数的构造，迭代序列的收敛性和收敛速度以及误差估计。问题：φ(x)的形式不唯一，如：2100210xxxx)2lg(xx2101nxnx)2lg(1nnxx取初始值，计算结果如下：3.00x0.30.3-0.00470.3617-1.01080.37320.37530.37572101nxnx)2lg(1nnxx0x1x2x3x4x数值分析数值分析若从任何可取的初值出发都能保证收敛，则称它为大范围收敛。如若为了保证收敛性必须选取初值充分接近于所要求的根，则称它为局部收敛。通常局部收敛方法比大范围收敛方法收敛得快。因此，一个合理的算法是先用一种大范围收敛方法求得接近于根的近似值（如对分法），再以其作为新的初值使用局部收敛法（如迭代法）。这里讨论迭代法的收敛性时，均指的是局部收敛性。数值分析数值分析考虑方程x=φ(x),φ(x)C[a,b],若(I)当x[a,b]时，φ(x)[a,b]；(II)对x[a,b],有|φ’(x)|L1成立。则任取x0[a,b]，由xk+1=φ(xk)得到的序列收敛于φ(x)在[a,b]上的唯一不动点。并且有误差估计式：0kkx1|*|||1kkkLxxxxL10|*|||1kkLxxxxL(k=1,2,…)且存在极限1'*lim**kkkxxxxx定理2（收敛定理）数值分析数值分析证明：①φ(x)在[a,b]上存在不动点？令()()fxxx()axb0()(),faaa0()()fbbb)(xf有根②不动点唯一？反证：若不然，设还有，则()xx'(*)()()(*),xxξxxxx*~在和之间*xx~10'()(())x*xξ而1'|()|*ξxx③当k时，xk收敛到x*？|*|kxx111'|(*)()||()||*|kkkxxξxx0|*|......|*|01xxLxxLkk数值分析数值分析④?||1|*|1kkkxxLLxx|*||*||*||*|||11kkkkkkxxLxxxxxxxx?||1|*|01xxLLxxkk⑤1110||||......||kkkkkxxLxxLxx1'*lim*?*kkkxxxxx⑥1''*()(*)limlim(*)**kkkkkkkxxξxxxxxxx11111''|||()()||()()||()||()|||kkkkkkkkkkkkxxxxξxxξxxLxx||1||11|*|11kkkkkxxLLxxLxx数值分析数值分析注：定理条件非必要条件，可将[a,b]缩小，定义局部收敛性：若在x*的某领域B={x||xx*|}有φC1[a,b]且|φ’(x*)|1，则由x0B开始的迭代收敛。即调整初值可得到收敛的结果。数值分析数值分析迭代法收敛阶则称数列为阶收敛，也称相应的迭代法为阶方法。当且时，称数列为线性收敛.当时，称数列平方收敛（或二阶收敛）.当时，称数列为超线性收敛。定义设数列收敛于,令误差,如果存在某个实数及正常数，使}{nxnnxe1pCCeepnnn||||lim1}{nxpp1p10C}{nx2p}{nx1p}{nxp显然，越大，数列收敛的越快。所以，迭代法的收敛阶是对迭代法收敛速度的一种度量。数值分析数值分析定理3（迭代法的局部收敛定理）设α是方程x=φ(x)的根，如果(1)迭代函数φ(x)在α的邻域可导；(2)在α的某个邻域S={x:|x-α|≤δ},对于任意的xS有1|)('|Lx则对于任意的初值x0S，迭代公式xn+1=φ(xn)产生的数列{xn}，收敛于方程的根α。数值分析数值分析定理3’（迭代法的局部收敛定理）设α是方程x=φ(x)的根，如果(1)迭代函数φ(x)在α的邻域一阶导数连续；则存在α的某个邻域S={x:|x-α|≤δ}及正数L1,使对于任意的xS有|'()|1xL取任意的初值x0S，迭代公式xn+1=φ(xn)产生的数列{xn}，收敛于方程的根α。(2)|'()|1数值分析数值分析控制误差ε的方法：(1)先计算满足误差要求的迭代次数n，再迭代。由||1||01xxLLxnn可得LxxLnln||)1(ln01(2)事后误差估计法。由于||1||1nnnxxLLx因而可用|xn-xn-1|≤ε来控制迭代过程。数值分析数值分析例用迭代法求x3-x2-1=0在隔根区间[1.4,1.5]内的根，要求准确到小数点后第4位.解：(1)由方程的等价形式)(132xxx构造迭代公式3211nnxx由322)1(32)(xxx知φ(x)在（1.4,1.5)可导，且15.0|)(|x故迭代法收敛。数值分析数值分析functiony=diedai(fname,x0,e,N)%用途:迭代法求解非线性方程f(x)=0y=x0;x0=y+2*e;k=0;whileabs(x0-y)e&kNk=k+1;x0=y;y=fname(x0);disp(y)endifk==Ndisp('warning')endf=inline('(x^2+1)^(1