《牛顿（NEWTON）法求根》由会员分享，可在线阅读，更多相关《牛顿（NEWTON）法求根（42页珍藏版）》请在金锄头文库上搜索。
1、学习和了解科学计算的桥梁,Numerical Calculations,数值计算,上节课回顾,由方程f(x)=0变换为等价方程 x=(x) （#）,先取一个估计值x0（初始值），若(x0) =x0，则x*=x0(可能性很小)一般(x0) x0， 记 x1=(x0) ， 若x1(x1) ， 记 x2=(x1) ，再用x2继续试探 记 x3=(x2) 如此反复计算即形成一迭代公式 xk+1=(xk) ，(k=0,1,2,),简单迭代法的思想,x*是方程f(x)=0的根,x*是方程x=(x)的根,x*为(x) 的不动点,即：x*= (x*),当xk收敛于x*， x*即是(x)的不动点，也就是原方程的
2、根。,(x)是连续函数，称为迭代函数,1、迭代公式 xk+1=(xk)收敛 xk收敛于x*,2、若,则迭代公式xk+1=(xk) 收敛,全局收敛性,3、若(x)在x*邻近有连续的一阶导数，且| (x*)|1,则迭代公式xk+1=(xk)具有局部收敛性。,注：有局部收敛性的条件| (x*)|1可用| (x0)|1来近似代替。,迭代公式收敛性的判断,误差估计式,当迭代公式xk+1=(xk) 收敛时，有误差估计式：,即：只要前后两次迭代值的差值足够小，就可使近似值xk达到任意的精度。,| (x*)|L1或| (x0)|L1,特别地,当L1/2时，有不等式|x*-xk|xk-xk-1|,此时，只要|x
3、k-xk-1| ，就可以终止迭代，求出满足精度要求的近似根xk。,定理：对于迭代过程xk+1= (xk) ，如果(p)(x) 在所求根x*的邻近连续，并且(x*)= (x*) =.= (p-1)(x*) =0，(#)(p)(x*)0，则该迭代过程在点x* 邻近是P阶收敛的。,该定理告诉我们，迭代过程的收敛速度依赖于迭代函数. 如果选取当xa,b 时(x)0，则该迭代过程只能是线性收敛。,因此,简单迭代法的收敛速度一般较慢 . 有的公式未必收敛.,局部收敛时阶的确定,2.4 牛顿迭代法,一、 Newton迭代法的基本思想二、牛顿法的收敛速度三、牛顿法的几何意义四、牛顿迭代法的步骤,设 xk 是f
4、(x)=0的一个近似根,把f(x)在xk处作泰勒展开若取前两项来近似代替f(x)(称为f(x)的线性化)，则得近似的线性方程设 f (xk)0 ,令其解为 xk+1 ,得 称其为f(x)=0的牛顿迭代公式。,解出x,一. Newton迭代法的基本思想,应用公式（1）来解方程的方法就称为牛顿迭代法。它是解代数方程和超越方程的有效方法之一。,它对应的迭代方程为 显然是f(x)=0的同解方程,故其迭代函数为,迭代公式为:,(1),解 因 f (x)=3x2+4x+10 ,所以迭代公式为,例1:用牛顿法求下面方程的根f(x)=x3+2x2+10x-20,从计算结果可以看出,牛顿法的收敛速度是很快的,进
5、行了四次迭代就得到了较满意的结果.,选取x0=1,计算结果列于下表,由牛顿迭代公式,例2 计算 的近似值。 =10-6 x0=0.88,解： 令x= 问题转化为求(x)= x2-0.78265=0的正根,迭代结果 k 0 1 2 3 xk 0.880000 0.884688 0.884675 0.884675 满足了精度要求 0.884675,假定x* 是f (x)的一个单根即f(x*)=0 ，f (x*)0 ，则由上式知(x*)=0，由局部收敛性定理知，牛顿迭代公式是局部收敛的， 且牛顿公式在根x* 的邻近至少是平方收敛的。因此,收敛速度很快.,二、牛顿法的收敛速度:,其迭代函数为:,由于,
6、f(x*)=0 (x*)=0,三、牛顿法的几何意义：,方程f(x)=0的根x*在几何上解释为曲线 y=f(x)与x轴交点的横坐标。,# 设xk是根x*的某个近似值，过曲线y=f(x)上横坐标为xk的点Pk引切线与x轴相交与xk+1，继续取点pk+1(xk+1,f(xk+1)再做切线与x轴相交，又可得xk+2,.。由图可见，只要初值取的充分靠近x*,这个序列很快就会收敛于x*。# Newton迭代法又称切线法,x*,xk,xk+1,xk+2,x*,xk,xk+1,xk+2,y=f(x)在点（xk，f(xk)处的切线方程,有：,它与x轴交点的纵坐标为：y=0,1）给出初始近似根x0及精度；2）计算
7、x0-f(x0)/f (x0)x1；3）若|x1-x0|=esp)&(nnewton(0,1e-6)x1 = -0.4590n = 6,newton(-1,1e-6)x1 = -0.4590n = 5, newton(1,1e-6)x1 = 0.9100n = 4, newton(2,1e-6)x1 = 0.9100n = 5,注1:newton法不仅收敛的快些，而且可得到不同的解., newton(5,1e-6) x1 = 3.7331n = 7, newton(15,1e-6) x1 = 3.7331n = 17, newton(10,1e-6) x1 = 3.7331n = 12, ne
8、wton(4,1e-6) x1 = 3.7331n = 5,注2:当初始值x0远离根时,迭代次数增加了.,注：由于牛顿迭代法是局部收敛的，故初值x0应充分靠近x*才能保证收敛的更快，这在一般情况下难以做到。x0的选择可用以下三种方法:1)使用中可用Mtalab先做出函数的图形;2)同跨步搜索法搜索有根区间;3)用二分法做求根预处理，二分若干次后得到比较接近根x*的近似根x0，然后再用牛顿迭代法来求根，可以得到取长补短的作用。,作业：P34 7、8,注、牛顿迭代法的优缺点,1、优点：牛顿迭代法具有平方收敛的速度，所以在迭代过程中只要迭代几次就会得到很精确的解。这是牛顿迭代法比简单迭代法优越的地方
9、。2、缺点：选定的初值要接近方程的解，否则有可能得不到收敛的结果。再者，牛顿迭代法计算量比较大。因每次迭代除计算函数值外还要计算导数值。,为了避免导数的计算，我们又给出了另一种迭代法弦截法。,2.5 弦截法,为了避免牛顿法中的导数计算，可用差商来代换公式的导数，即,得到公式：,称为弦截公式。,弦截公式,弦截公式的几何解释：,xk,xk+1,P0,Pk,Pk+1,xk+2,曲线y=f(x)上横坐标为xk的点记为pk，则差商,表示弦线 的斜率。,迭代公式求得的xk+1是弦线 与x轴的交点,x0,.,一、弦截公式及其收敛性,收敛速度,故迭代函数为：,上述迭代公式是由f(x)=0的等价方程,建立起来的
10、,当x0充分接近x*时，0|(x*)|1，故由前面定理知弦截法具有局部收敛性，且具有线性收敛速度。由此可见，弦截法的收敛速度比牛顿法慢，但它的优点是不需要计算导数值。,二、快速弦截法,要提高弦截法的收敛速度，改用相邻两点的差商来替代牛顿公式中的导数f (xk)，故可导 出下面的迭代公式：,快速弦截公式,上述方法称为快速弦截法。,二、快速弦截法,要提高弦截法的收敛速度，改用相临两点的差商来替代牛顿公式中的导数f (xk)，故可导 出下面的迭代公式：,快速弦截公式,上述方法称为快速弦截法。,可以证明快速弦截法具有超线性收敛.,注：两者的区别：,弦截法：计算xk+1只需用到前一步的值xk单步法,快速
11、弦截法：计算xk+1需用到前两步的值xk,和xk-1两步法,三、快速弦截法的算法：,1）选定初始值x0,x1,并计算相应的函数值f(x0)与f(x1),2）计算,3）若满足|x1-x0|(为给定的精度要求),则转4）；否则转2）,4）输出满足精度要求的根x1，结束。,实验1.3（求非线性方程的根）实验目的：会求非线性方程的根实验内容：1、用Matlab软件做出下列方程的图形，观察根所在的区间：,2、用二分法求上述方程的根，并分析其误差；3、自编快速弦截法程序，分别用Newton迭代法和快速弦截法求上述方程的根；4、比较两种迭代法的收敛速度。,作业：P343510、11,思考题：有没有比快速弦截
12、法更简单的计算方法?,大M法 用某一给定的数M来代替f (xk)得到迭代公式：,这种做法更加简便。称作大M法。,四Newton法的变形,下一页,Newton法通常依赖初值x0的选取，如果x0选择不当，将导致迭代发散或产生无限循环（书上P27P28，例27） ；此外，每一步迭代都需要计算导数值，有时计算f (xk)是不方便的。基于这两点，产生了几种Newton迭代法的变形,1、Newton下山法 Newton下山法是为了防止因x0选取不当造成迭代发散或无限循环的情况。因为在根x*的附近，越接近x*的迭代值xk，其函数值的绝对值|f(xk)|越小（为什么？）所以在迭代中加入函数绝对值单调减少的条件：,强制使迭代过程收敛。满足上述条件的算法称为下山法。推导如下：,把牛顿法的计算结果记为：,即对应的迭代公式为：,其中01，称为下山因子。,即,将其与前一步迭代的近似值xk，适当加权平均，作为迭代改进值xk+1，即：,（*）,将（*）式代入后，整理得：,Newton下山法只有线性敛速。(x*)=1-0,下山因子的选取：搜索试探,先从=1开始，试探|f(xk+1)|f(xk)|是否成立，若不成立，则将减半进行试算，也即在集合,中依次挑选下山因子，直到找到某个使单调递减条件成立的下山因子。（书上P27P28，例27）,
