4-牛顿迭代法1

1/26牛顿迭代法Newton迭代格式Newton迭代法的收敛性弦截法迭代格式数值实验题介绍2/26初值:x1=1.5迭代格式:xn+1=0.5(xn+2/xn)(n=1,2,·····)平方根算法求2xnError1.4166666666666672.45e-0031.4142156862745102.12e-0061.4142135623746901.59e-0121.4142135623730952.22e-0161.4142135623730952.22e-016牛顿(Newton)迭代法3/24基本思想：将方程f(x)=0中函数f(x)线性化,以线性方程的解逼近非线性方程的解.设函数f(x)在有根区间[a,b]二次连续可微,则f(x)在x0处的泰勒展开式为:],[ba只取关于x线性项，有设，其解记为(*)4/24牛顿迭代法的几何意义yxOx0x1x2图2.3牛顿迭代法在单变量情况下又称为切线法.(*)迭代格式(*)称为牛顿迭代法.构造迭代格式：5/26设C0,Cxx2–C=0令f(x)=x2–C,则xxf2)(nnnnxCxxx221][211nnnxCxx应用——求正数平方根算法返回6/24)(211nnnxCxxC例1设C0，证明由迭代格式(n=0，1，……)产生的迭代序列{xn}，对任意的x00，均收敛于;且具有2阶收敛速度。分析：由迭代格式，有C返回7/24)(211nnnxCxxC证明：由迭代格式，有C等式两端同减，配方得同理有返回8/24将上面两式相除有反复递推，得令则有化简得9/26由此可知,平方根迭代具有2阶收敛速度nnnxCxCx21)(21CCxCxnnn21||||lim21CxCxCxnnn][21122)(21]2[21CxxCCxxxnnnnnCxnnlim10/26Newton迭代法的局部收敛性定理2.7设f(x)在点x*的某邻域内具有二阶连续导数,且设f(x*)=0,f’(x*)≠0,则对充分靠近点x*的初值x0,Newton迭代法至少平方收敛.)()(1nnnnxfxfxx)()()(xfxfxx0)](/[)()()(2****xfxfxfx所以,Newton迭代法至少平方收敛。)()()(***xfxfx11/26例2.求f(x)=xex–1=0在x0=0.5附近的根解:迭代格式为xexxf)1()(nnxnxnnnexexxx)1(11(n=0,1,·····)f=inline('x*exp(x)-1');f1=inline('(x+1)*exp(x)');x0=0.5;er=1;k=0;whileer0.00001x=x0-f(x0)/f1(x0);er=abs(x-x0)x0=x;k=k+1endx=0.5671k=4er=1.2347e-01000.51-101xxexp(x)-112/26缺陷1.被零除错误2.程序死循环-6-4-20246-200-1000100200xx3-3x+2y=arctanx方程:f(x)=x3–3x+2=0在重根x*=1附近,f’(x)近似为零对f(x)=arctanx存在x0,Newton迭代法陷入死循环13/24例3用牛顿迭代法解方程f（x）=x3–x–3=0.x1=–3，x2=–1.9615，x3=–1.1472，x4=–0.0066，……数列中的项以四项为一个周期重复（死循环）.取x0=0,(n=0,1,·····)14/24例4用牛顿迭代法解方程f（x）=xe–x=0.初值取x0=2，x1=4，x2=5.33333，……，x15=19.72354943，……f（x15）=0.000000053615/26f’0,f”0f’0,f”0f’0,f”0f’0,f”0牛顿迭代法收敛的四种情况16/26定理:若函数f(x)在[a，b]上满足条件则方程f(x)=0在[a，b]上有唯一根x*，且由初值x0按牛顿迭代公式求得的序列{xn}二阶收敛于x*。（1）f(a)f(b)0；（2）f’(x)，f”(x)在[a，b]上连续且不变号（恒为正或恒为负）；（3）取x0∈[a，b]使得f(x0)f”(x0)0。17/260))((21))(()()(2***kkkkkxxfxxxfxfxf2**)()(2)(])()([kkkkkkxxxffxfxfxx2*1*)()(2)(kkkkxxxffxx|)(|2|)(||)(|2|)(|lim)(||lim**2**1xfxfxffxxxxkkkkkk18/26设x*是方程f(x)=0的根,x0和x1是x*附近的两个点.0)()()()(101011xxxxxfxfxfNewton迭代法的变形－弦截法曲线y=f(x)在点(x0,f(x0))和点(x1,f(x1))处的割线与X轴交点f(x)=019/26)()()()(0101112xxxfxfxfxx)()()()(111nnnnnnnxxxfxfxfxx(n=1,2,·······)例2.8确定悬链线方程axaycosh已知y(50)=y(0)+10求解方程:01050coshaaaa=126.632420/26f=inline(‘u.*cosh(50/u)-u-10');a0=120;a=150;k=1;y0=f(a0);y=f(a);whileabs(a0-a)0.0001t=a-y*(a-a0)/(y-y0);a0=a;y0=y;a=t;y=f(a);k=k+1;endAnsK=6,a=126.6324f=inline('u.*cosh(50/u)-u-10');f1=inline('cosh(50/u)-50*sinh(50/u)/u-1');a0=150;y0=f(a0);k=1;er=1;whileer0.0001t=a0-f(a0)/f1(a0);er=abs(t-a0);a0=t;k=k+1;endAnsK=6,t=126.6324割线法:切线法:21/243．计算重根的牛顿迭代法如果x*为f(x)的m重零点，此时有*x)(xf显然x*为的单根，相应的牛顿迭代格式：该迭代格式具有至少二阶收敛性质，但不知道重数m，因而难以直接使用.22/243．计算重根的牛顿迭代法*x)(xf)(xf利用f(x)的重根分解式，得)(xf得到修正的牛顿迭代法:该迭代格式至少是二阶收敛23/26牛顿迭代法的收敛域问题:用牛顿迭代法求解复数方程z3–1=0，该方程在复平面上三个根分别是iz23212iz23213z1=1选择中心位于坐标原点，边长为2的正方形内的任意点作初始值，进行迭代，把收敛到三个根的初值分为三类，并分别标上不同颜色（例如红、黄、蓝）。对充分多的初始点进行实验，绘出牛顿迭代法对该方程的收敛域彩色图。24/26收敛到z1的牛顿迭代初值点集合收敛到z2的牛顿迭代初值点集合收敛到z3的牛顿迭代初值点集合25/26在复平面内,有一些例外点是牛顿迭代不收敛的初值点.这些例外点构成了朱莉娅集(为纪念法国女数学家Julia).26/26作业：用牛顿法或二分法求下面非线性方程组的根4exp()(1-)4arctan()(22223311)yxy,xfyxy,xf//交作业邮箱：[e-mail]邮件主题：学号+姓名+第几次作业