迭代法求非线性方程的根.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,1,*,迭代法求非线性方程的根,迭代法是求解非线性方程近似根的一种方法，这种方法的关键是确定迭代函数,(,x)，,简单迭代法 用直接的方法从原方程中隐含的求出,x，,从而确定迭代函数(,x)，,这种迭代法收敛速度较慢，迭代次数多，因此常用于理论中,Newton,迭代法采用另一种迭代格式,具有较快的收敛速度，由,牛顿迭代法可以得到很多其他迭代格式,。,下一页,1,迭代法,一、,简单迭代法的概念与结论,二、,Newton,迭代法的基本思想,三、,牛顿法的几何意义,四、牛顿迭代法的步骤,五、例题,六、其他注意的事项,2,一、简单迭代法的概念与结论,简单迭代法又称逐次迭代法，基本思想是构造不动点方程，以求得近似根。即由方程,f(x)=0,变换为,x=,(x),然后建立迭代格式，,当给定处值,x,0,后,由迭代格式可求得数列,x,k,。,如果,x,k,收敛于,x,*,，,则它就是方程的根。因为：,但迭代格式有多种，迭代格式如何建立才能保证迭代法的数列收敛？有如下定理：,返回,下一页,7,定理一：,假定函数 满足下列条件：,1、对任意 有,；(1.1),2、存在正数,L1，,使对任意 有,(1.2),则迭代过程 对于任意初值,均收敛于方程 的根 ，且有如下的误差估计式：,(1.3),返回,下一页,实用中(1.2)式常用,8,证明：,设方程 在区间 内有根 ，,则有 由,故,据此反复递推有,返回,下一页,9,故当 时迭代值,按(1.2)式 有 (1.4)，,据此反复递推得：,于是对任意正整数,p,有,在上式令 ，注意到 即得式(1.3)。证毕,。,返回,下一页,10,定理二：,对于迭代过程 ，如果 在所求根,的邻近连续，并且,(*),则该迭代过程在点 邻近是,P,阶收敛的。,证明：由于 。据定理一，立即可以断定迭 代过程,具有局部收敛性。再将 在根 处展开，利用条件,(,*),，,则有,注意到 ，由上式得,返回,下一页,11,因此对迭代误差有:。这表明迭代过程,确实为,P,阶收敛，证毕。,上述定理告诉我们，迭代过程的收敛速度依赖于迭代函数.如果选取当 时 ,则该迭代过程只能是线性收敛。对于牛顿迭代公式(1)，其迭代函数为,由于 ,假定 是,f(x),的一个单根，即 ，则由上式知 。于是依据定理二可以断定，牛顿法在根 的邻近是平方收敛的。,返回,下一页,12,定义一：,如果存在 的某个邻域 ，使迭代过程,对于任意初值 均收敛，则称迭代过程,在根 邻近具有局部收敛性。,定理三：设 为方程 的根，在 的邻近连续。且则迭代过程在邻近具有局部收敛性。,返回,下一页,13,证明：,由连续函数的性质，存在 的某个邻域,，使对于任意 成立 。此外,对于任意 总有 。这是因为 ，依据定义三，可以断定，迭代过程 对于任意初值 均收敛。证毕。,返回,下一页,14,二.,Newton,迭代法的基本思想,设 是,f(x)=0,的一个近似根，把,f(x),在 处作泰勒展开,若取前两项来近似代替,f(x)(,称为,f(x),的线性化)，则得近似的线性方程,设 ,令其解为 ,得,（1),这称为,f(x)=0,的牛顿迭格式。,返回,下一页,3,它对应的迭代方程为 显然是,f(x)=0,的同解方程，,故其迭代函数为,在,f(x)=0,的根 的某个邻域 内,在 的邻域,R,内，对任意初值 ，,应用,由公式（1）,来解方程的方法就称为,牛顿迭代法,。它是解代数方程和超越方程的有效方法之一,.,返回,下一页,4,三、牛顿法的几何意义,由（1）式知 是点 处 的切线 与,X,轴的交点的横坐标（如图）。也就是说，新的近似值 是用代替曲线,y=f(x),的切线与,x,轴相交得到的。继续取点 ,再做切线与,x,轴相交，又可得 。由图可见，只要初值取的充分靠近 ,这个序列就会很快收敛于,。,Newton,迭代法又称切线法,返回,下一页,5,返回,下一页,6,四、,牛顿迭代法的步骤,步一、,准备。,选定初始近似值 ，计算,步二、,迭代。,按公式 迭代一次，得到新的近似值 ，计算,步三、,控制。,如果 满足 或 .则终止迭代，以 作为所求的根；否则转步四。此处 是允许误差,返回,下一页,15,而 。其中,c,是取绝对值或相对误差,的控制常数，一般可取,c=1。,步四、修改。如果迭代次数达到预定指定的次数,N，,或者 则方法失败；否则以 代替 转步二继续迭代。,返回,下一页,16,五.例题,例1:,用牛顿法求下面方程的根,解 因 ,所以迭代公式为,选取 ,计算结果列于下表,从计算结果可以看出,牛顿法的收敛速度是很快的,进行了四次迭代就得到了较满意的结果.,返回,下一页,17,例2 计算,的近似值。,=10,-,6,x,0,=0.88,解：令,x=,问题转化为求,(x)=x,2,-0.78265=0,的正根,由牛顿迭代公式,x,k,+1,=,x,k,-(,x,k,)/(,x,k,)=,x,k,/2+0.78265/2x,k,迭代结果,k,0,1 2 3,x,k,0.880000 0.884688,0.884675 0.884675,满足了精度要求,=0.884675,返回,下一页,18,六其他注意的事项,下一页,19,返回,下一页,20,七、牛顿迭代法的优缺点,1、优点：牛顿迭代法具有平方收敛的速度，所以在迭代过程中只要迭代几次就会得到很精确的解。这是牛顿迭代法比简单迭代法优越的地方。,2、缺点：选定的初值要接近方程的解，否则有可能的不到收敛的结果。再者，牛顿迭代法计算量比较大。因每次迭代除计算函数值外还要计算微商值,。,返回,下一页,21,八、,迭代的一般概念,迭代法可分为单点迭代法与多点迭代法。,单点迭代法的一般形式为：,x,i,+1,=,(,x,i,),i,=0,1,2,.,需一个初始点,x,0,启动,多点迭代法的一般形式为：,x,i,+1,=,(,x,i,，,x,i,-1,x,i,-k+1,),需多个初始点,x,0，,x,1,x,2,x,k,启动,对于单点迭代：,n=1,22,求方程,x,3,+x=2x,2,+3,在,x,0,=4,附近的根。,解：函数,(,x)=x,3,-2x,2,+x-3,写成嵌套形式,(,x)=x,3,-2x,2,+x-3=(x-2)x+1)x-3,(x)=3x,2,-4x+1=(3x-4)x+1,计算结果如下：,N X N X,0 4.000000000000,4 2.175554938721,1 3.000000000000 5 2.174560100666,2 2.437500000000 6 2.174559410293,3 2.213032716315 7 2.174559410292,8 2.174559410292,练习,1,设,(,x),在有根区间(,a,b),上存在二阶导数，且满足,（1）,(,a),(b)0。,则牛顿迭代序列,x,i,收敛于,(,x)=0,在(,a,b),内唯一的根。,判别,Newton,法收敛的充分条件,1,