数值分析3-牛顿迭代法

§3牛顿迭代法NewtonIteration————切线法牛顿迭代法是最著名的方程求根方法。已经通过各种方式把它推广到解其他更为困难的非线性问题。【例如】非线性方程组、非线性积分方程和非线性微分方程。虽然牛顿法对于给定的问题不一定总是最好的方法，但它的简单形式和快的收敛速度常常使得解非线性问题的人优先考虑它。迭代一般理论告诉我们，构造好的迭代函数可使收敛速度提高。然而迭代函数的构造方法又各不相同，方法多样。牛顿法是受几何直观启发，给出构造迭代函数的一条重要途径。牛顿迭代的基本思想:方程f(x)=0的根，几何意义是曲线y=f(x)与ox轴y=0的交点。求曲线与y=0的交点没有普遍的公式，但直接与0x轴的交点容易计算。用直线近似曲线y=f(x)，从而用直线方程的根逐步代替f(x)=0的根。即把非线性方程逐步线性化。方法：设xk是f(x)=0的一个近似根，把f(x)在xk处作一阶Taylor展开，得到))(()()(kkkxxxfxfxf（19）设)(kxf≠0，由于0)())(()(xfxxxfxfkkk所以求得解记为1kx，有牛顿迭代公式：)()(1kkkkxfxfxx（20）按牛顿迭代计算称为牛顿迭代法。牛顿法的几何意义：选初值xk以后，过))(,(kkxfxp点，作曲线y=f(x)的切线，其切线方程为))(()()(kkkxxxfxfxf(21)切线与ox轴的交点，为1kx，则)(/)(1kkkkxfxfxx（22）牛顿迭代法也称为切线法。迭代法的收敛性：如果取)(/)()(kkxfxfxxg，则有x=g(x)，从而牛顿迭代公式就是)(1kkxgx因此就可以由考察g(x)的性质，来讨论迭代法的收敛性及收敛速度。迭代过程的收敛速度是指迭代过程中误差的下降速度。【收敛阶定义1】设迭代过程)(1kkxgx收敛于方程x=g(x)的根x*，如果迭代误差*xxekk，当k→∞时成立)0(/1的常数cceepkk（24）则称该迭代过程是p阶收敛的。特别p=1时称为线性收敛，p1时称超线性收敛，p=2时称为平方收敛。【定理3】若f(x)在根附近存在连续的二阶导数，x*是f(x)的单根，且初始值x0充分接近x*，则牛顿迭代过程收敛，而且有21)(2/)(xxxfxfxxkk（25）证明1)对于f(x)，取)(/)()(xfxfxxg，则牛顿迭代过程为)(1kkxgx，注意到3222)(/)()(2)(/)()()()()(;)](/[)()()(xfxfxfxfxfxfxfxfxgxfxfxfxg由于x*是f(x)=0的单根，即)(xf=0,0)(xf，所以有0)(/)()(,0)(xfxfxgxg(26)由定理2知，迭代过程是局部收敛的。2)将g(x)在x*处进行泰勒展开并代入kxx，有22*)*)]((/*)([21*)(*)(!2*)(*)*)((*)()(xxxfxfxgxxxgxxxgxgxgkkkk注意到)(1kkxgx，x*=g(x*)，得到21)())(2/)((xxxfxfxxkk因此有21)(2/)(xxxfxfxxkk定理证毕【说明】)0*)(2/*)((/21xfxfcceekk，即牛顿迭代过程在x*附近具有平方收敛速度。牛顿迭代法的优点:快速收敛性,算法简单、容易实现缺点：初值0x必须选在x*附近，否则，可能不收敛【例】用牛顿法解下面方程在x=0.5附近的根，要求精确到510。01xxe解牛顿迭代公式为kxkkkxexxxk11取初值5.00x，迭代计算，得到5671432.0,5671432.0,5671555.0,5710204.04321xxxx【注】牛顿法的收敛速度非常快附：牛顿法的算法函数程序：(存至work目录中)functiony=newton(x0)x1=x0-f1(x0);n=1;while(norm(x1-x0)=1.0e-6)&(n=1000)x0=x1;x1=x0-f1(x0);n=n+1;endvpa(x1,7),n%输出n,方程的近似解functiony=f1(x)y=(x-exp(-x))/(1+x);endnewton(0.5)观察初值的选取对解的影响【例】用牛顿法求方程1)(3xxxf=0的根。首先选取初值：(转到指令窗)x=-10:0.01:10;y=x.^3-x-1;plot(x,y,'r',x,0*x)-10-8-6-4-20246810-1000-800-600-400-20002004006008001000解牛顿迭代公式为131231kkkkkxxxxxfunctiony=f1(x)y=(x^3-x-1)/(3*x^2-1);end分别取初值6.00x和1.3,比较所用迭代次数.newton(0.6)newton(1.3)