研究生数值分析牛顿(Newton)迭代法.ppt

,则近似方程转化为,设 ，上式解为,5 牛顿(Newton)迭代法,（1）牛顿迭代公式 设xk是非线性方程 f(x)=0的一个近似根，把 f(x)在xk处作一阶泰勒展开，即用前两项近似代替,于是方程 f(x)=0的新的近似根xk+1，可由牛顿迭代公式,牛顿迭代公式具有明显的几何意义。,方程 是曲线 y=f(x)在点,处的切线方程，迭代公式就是切线与x轴,交点的横坐标。因此，牛顿迭代法又称为切线法。,求出,（2）牛顿迭代法收敛的充分条件,具有相同的根。因此，牛顿迭代法是一种以,为迭代函数的迭代法。,当 时，方程 与,定理 对于方程 ，若存在区间 ， 使,1、在 内存在方程的单根 ；,2、 在内 连续。,则牛顿迭代法在 附近具有局部收敛性。,证明：由迭代函数得,所以 且,由条件（2），必存在区间 ，,使 ，在 内连，且 。,根据定理2，牛顿迭代公式在 附近局部收敛。,因为 是 在 内的单根，,定理 对方程 ，若存在区间 ，使,（3）对任意 ，都有 ；,在 上的唯一实根 。,（1） 在 上连续；,（2） ；,（4） 在 上保号，,则当初值 ，且 时，,牛顿迭代公式产生的迭代序列 收敛于方程,定理的简要几何说明：,条件（2）保证了方程y = f (x) 在a ,b内至少有一实根；,条件（3）说明在a ,b上恒有 或,即f(x)=单调，f(x)=0在a,b内最多有一实根。,由条件(1)、(2)、(3)知，方程 f(x)=0在a ,b内有唯一实根 。,条件（4）表明曲线y=f(x)在a ,b内凹向不变。,条件（1）保证了曲线 y=f (x)的连续性和光滑性；,不难看出，只要初始近似值满足条件 及 ，则迭代过程必收敛。,曲线y=f(x)在a ,b上只有下图四种情形。,的实根，要求准确到,解：设 ，则,容易验证 在0，3上,例4 用牛顿迭代法求方程,满足定理的条件,当 时,牛顿迭代公式 收敛,计算结果如下,因为 ，所以,为满足精度要求的近似根。,例5 给出用牛顿迭代法求平方根 的迭代公式，并计算,使其精确至7位有效数字。,的牛顿迭代公式为,解：作函数 ，,则f (x)=0的正根 就是,现在分析迭代公式的收敛性，考虑区间,（1） ，故,（2）当 时， ；,（3）当 时， ，连续；,满足定理条件，牛顿迭代公式收敛。,事实上，由迭代公式可得,两式相除得到 ，,令 ，于是,对任意 ，总有 ，,说明对任意初值 ，迭代公式都是收敛的。,所以当 时，,解得,由此递推可得,利用迭代公式，取,计算结果,精确至7位有效数字，,与精确值,比较，可知牛顿迭代公式只需迭代3次 就能达到精度要求。,当迭代过程收敛，且 连续时,有,这表明当 时,简单迭代法是线性收敛的。,例6 分析简单迭代法与牛顿迭代法的收敛速度。,解：对于简单迭代法，由,对于牛顿迭代法，,（1）若 是方程 的单根（即 ）,则由,容易验证，当所涉及到的各阶导数在 附近连续时,这表明牛顿迭代法用于求单根时至少是二阶收敛的。,（2）若 是方程 的 重根，,这表明直接用牛顿迭代法对方程 求重根 只有线性收敛速度。,即,此时有,对 是方程 重根的情形，如将方程改写成,则 是方程 的单根，再对,用牛顿迭代法求 就具有二阶收敛速度。,对于一般的线性收敛序列 ,可通过下述方法加速：,设序列 收敛于 且,则当 充分大时，,解出 ，得,这样又获得了一个由 确定的新近似值。,通过算式,有可能产生一个收敛速度较快的新序列 .这种加速方法称为埃特肯(Aitken)加速方法.,只要充分大，这个新近似值就有可能比 更好地逼近 。根据这个原理，在收敛速度较慢的序列 的基础上，,的距离又较大时埃特肯加速可能失效。,注意：当 变化幅度大，,将埃特肯加速方法用于迭代法，可得如下算式,称为埃特肯算法。,例 用迭代法求方程 在0，1内根,的近似值，精确到,解：取初始近似根,用简单迭代法,2.用牛顿迭代法,3.用埃特肯算法,（1）,（2）,（3）,分别求出满足精度要求的近似根，如下表,6 求方程 m重根的Newton法,设 s 是方程 f(x)=0 的 m 重根(m2), f(x)在 s 的某邻域内有m阶连续导数 ,这时,由Taylor公式,得,其中,都在x与s之间。,由Newton法的迭代函数,可得,由此可见，方程 f(x)=0 的 m 重根 s 仍然是其等价方程 x=(x)的根。,由于,，所以，只要 充分靠近 s，,由Newton法,产生的序列,仍收敛于s，但是只有线性的收敛速度。,若把迭代函数修改为,则有,等式说明，当 s 是方程f(x)=0的m重根时,变形的Newton法,不仅可以收敛于 s，且还具有二阶的收敛速度。,在重根的情况下，一般重数m是不知道的。因此，使用变形的Newton法公式就有困难。为此，构造函数u(x) ：当x=s时，u(x) =0；当 时,因s是f(x)的m重零点，故 ，s是u(x),的单零点求解方程u(x)=0的Newton法迭代函数为,于是，迭代公式,产生的序列,如果收敛于方程f(x)=0的m重根s,就至少是二阶收敛的。它的缺点是要计算,例如，已知方程,有一个三重根s=0.8，这里,如果使用Newton法,进行迭代，并取初值 ，则有,越往后收敛越慢。如果使用迭代公式,也取初值 ，则有,收敛得非常快。,设有方程,为常数，,（1）构造一个不用除法计算1/c的迭代格式， （2）证明：当初值x0满足0x02/c，则迭代数列xn平方收敛于1/c。 （3）按迭代法求具有6位有效数字的1/0.324的近似值.,练习：,解: (1) 令f(x)=1/x-c，则f(x)=-1/x2 . 代入Newton迭代公式得,(2)收敛性证明：将上述迭代式两端同减1/c， 则,又,这表明：数列 xn单调递增有界，,故,存在，即xn收敛于1/c，,也可按下面的方法来证。因为,反复递推，得,因为,故,即,又因,，-c为不等于零的常数,从而,，即xn为平方收敛于的。,（3）按提意