数值分析3 牛顿迭代法.docx
数值分析3 牛顿迭代法§3 牛顿迭代法Newton Iteration 切线法 牛顿迭代法是最著名的方程求根方法。已经通过各种方式把它推广到解其他更为困难的非线性问题。 非线性方程组、非线性积分方程和非线性微分方程。 虽然牛顿法对于给定的问题不一定总是最好的方法，但它的简单形式和快的收敛速度常常使得解非线性问题的人优先考虑它。 迭代一般理论告诉我们，构造好的迭代函数可使收敛速度提高。然而迭代函数的构造方法又各不相同，方法多样。牛顿法是受几何直观启发，给出构造迭代函数的一条重要途径。 牛顿迭代的基本思想:方程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展开，得到 f(x)»f(xk)+f¢(xk)(x-xk) 设f¢(xk)0，由于 f(xk)+f¢(xk)(x-xk)»f(x)=0 所以求得解记为xk+1，有 牛顿迭代公式： xk+1=xk-f(xk) ¢f(xk)按牛顿迭代计算称为牛顿迭代法。 牛顿法的几何意义：选初值xk以后，过p(xk,f(xk)点，作曲线y=f(x)的切线，其切线方程为f(x)=f(xk)+f¢(xk)(x-xk) (21) 切线与ox轴的交点，为xk+1，则 xk+1=xk-f(xk)/f¢(xk) 牛顿迭代法也称为切线法。 迭代法的收敛性：如果取g(x)=x-f(xk)/f¢(xk)，则有x=g(x)，从而牛顿迭代公式就是 xk+1=g(xk) 因此就可以由考察g(x)的性质，来讨论迭代法的收敛性及收敛速度。迭代过程的收敛速度是指迭代过程中误差的下降速度。 设迭代过程xk+1=g(xk)收敛于方程x=g(x)的根x*，*如果迭代误差ek=xk-x，当k时成立 ek+1/ekp®c(c¹0的常数) 则称该迭代过程是p阶收敛的。特别p=1时称为线性收敛，p>1时称超线性收敛，p=2时称为平方收敛。 若f(x)在根附近存在连续的二阶导数，x*是f(x)的单根，且初始值x0充分接近x*，则牛顿迭代过程收敛，而且有 xk+1-x*»f¢¢(x*)/2f¢(x*)×xk-x* 2证明 1)对于f(x)，取g(x)=x-f(x)/f¢(x)，则牛顿迭代过程为xk+1=g(xk)，注意到 g¢(x)=f(x)f¢¢(x)/f¢(x)2;g¢¢(x)=f(x)f¢¢¢(x)+f¢(x)f¢¢(x)/f¢(x)2-2f(x)f¢¢(x)2/f¢(x)3*由于x*是f(x)=0的单根，即f(x)=0,f¢(x)¹0，所以有 *g¢(x*)=0,g¢¢(x*)=f¢¢(x*)/f¢(x*)¹0 (26) 由定理2知，迭代过程是局部收敛的。 2)将g(x)在x*处进行泰勒展开并代入x=xk，有 g(xk)»g(x*)+g¢(x*)(xk-x*)+g¢¢(x*)(xk-x*)22!1=g(x*)+×f¢¢(x*)/f¢(x*)(xk-x*)22注意到xk+1=g(xk)，x*=g(x*)，得到 xk+1-x*»(f¢¢(x*)/2f(x*)×(xk-x*)2 因此有 xk+1-x*»f¢¢(x*)/2f¢(x*)×xk-x* 定理证毕 ek+1/ek®c(c=f¢¢(x*)/2f¢(x*)¹0)，即牛顿迭代过程在22x*附近具有平方收敛速度。 牛顿迭代法的优点:快速收敛性,算法简单、容易实现 缺点：初值x0必须选在x*附近，否则，可能不收敛 用牛顿法解下面方程在x=0.5附近的根，要求精确到e=10。 -5xex-1=0 解 牛顿迭代公式为 xk+1xk-e-xk =xk-1+xk取初值x0=0.5，迭代计算，得到 x1=0.5710204,x2=0.5671555,x3=0.5671432,x4=0.5671432牛顿法的收敛速度非常快 附：牛顿法的算法函数程序：(存至work目录中) function y=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; end vpa(x1,7),n %输出n,方程的近似解 function y=f1(x) y=(x-exp(-x)/(1+x); end newton(0.5) 观察初值的选取对解的影响 用牛顿法求方程f(x)=x-x-1=0的根。 首先选取初值：(转到指令窗) x=-10:0.01:10;y=x.3-x-1;plot(x,y,'r',x,0*x) 310008006004002000-200-400-600-800-1000-10-8-6-4-20246810解 牛顿迭代公式为 xk+13xk-xk-1 =xk-23xk-1function y=f1(x) y=(x3-x-1)/(3*x2-1); end 分别取初值x0=0.6和1.3,比较所用迭代次数. newton(0.6) newton(1.3)
