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

1、1,迭代法求非线性方程的根,迭代法是求解非线性方程近似根的一种方法，这种方法的关键是确定迭代函数(x)，简单迭代法 用直接的方法从原方程中隐含的求出x，从而确定迭代函数(x)，这种迭代法收敛速度较慢，迭代次数多，因此常用于理论中,Newton迭代法采用另一种迭代格式, 具有较快的收敛速度，由牛顿迭代法可以得到很多其他迭代格式。,下一页,2,迭代法,一、简单迭代法的概念与结论 二、 Newton迭代法的基本思想 三、牛顿法的几何意义 四、牛顿迭代法的步骤 五、例题 六、其他注意的事项,7,一、简单迭代法的概念与结论,简单迭代法又称逐次迭代法，基本思想是构造不动点方程，以求得近似根。即由方程f(x

2、)=0变换为x=(x), 然后建立迭代格式， 当给定处值x0 后, 由迭代格式可求得数列xk。如果xk收敛于x*，则它就是方程的根。因为： 但迭代格式有多种，迭代格式如何建立才能保证迭代法的数列收敛？有如下定理：,返回,下一页,8,定理一：假定函数 满足下列条件： 1、对任意 有 ；(1.1) 2、存在正数 L1，使对任意 有 (1.2) 则迭代过程 对于任意初值 均收敛于方程 的根 ，且有如下的误差估计式： (1.3),返回,下一页,实用中(1.2)式常用,9,证明：设方程 在区间 内有根 ， 则有 由 故 据此反复递推有,返回,下一页,10,故当 时迭代值 按(1.2)式 有 (1.4)，

3、 据此反复递推得： 于是对任意正整数p有 在上式令 ，注意到 即得式(1.3)。证毕。,返回,下一页,11,定理二：对于迭代过程 ，如果 在所求根 的邻近连续，并且 (*) 则该迭代过程在点 邻近是P阶收敛的。 证明：由于 。据定理一，立即可以断定迭 代过程 具有局部收敛性。再将 在根 处展开，利用条件(*)，则有 注意到 ， 由上式得,返回,下一页,12,因此对迭代误差有: 。这表明迭代过程 确实为P阶收敛，证毕。 上述定理告诉我们，迭代过程的收敛速度依赖于迭代函数. 如果选取当 时 ,则该迭代过程只能是线性收敛。对于牛顿迭代公式(1)，其迭代函数为 由于 ,假定 是f(x)的一个单根，即

4、， 则由上式知 。于是依据定理二可以断定，牛顿法在根 的邻近是平方收敛的。,返回,下一页,13,定义一：如果存在 的某个邻域 ，使迭代过程 对于任意初值 均收敛，则称迭代过程 在根 邻近具有局部收敛性。 定理三：设 为方程 的根， 在 的邻近连续。且则迭代过程在邻近具有局部收敛性。,返回,下一页,14,证明：由连续函数的性质，存在 的某个邻域 ，使对于任意 成立 。此外,对于任意 总有 。这是因为 ，依据定义三，可以断定，迭代过程 对于任意初值 均收敛。证毕。,返回,下一页,3,二. Newton迭代法的基本思想,设 是f(x)=0的一个近似根，把f(x)在 处作泰勒展开 若取前两项来近似代替

5、f(x)(称为f(x)的线性化)，则得近似的线性方程 设 ,令其解为 ,得 （1) 这称为f(x)=0的牛顿迭格式。,返回,下一页,4,它对应的迭代方程为 显然是f(x)=0的同解方程， 故其迭代函数为 在 f(x)=0的根 的某个邻域 内, 在 的邻域R 内，对任意初值 ，应用由公式（1）来解方程的方法就称为牛顿迭代法。它是解代数方程和超越方程的有效方法之一.,返回,下一页,5,三、牛顿法的几何意义,由（1）式知 是点 处 的切线 与X轴的交点的横坐标（如图）。也就是说，新的近似值 是用代替曲线y=f(x)的切线与x 轴相交得到的。继续取点 ,再做切线与x轴相交，又可得 。由图可见，只要初值

6、取的充分靠近 ,这个序列就会很快收敛于 。 Newton迭代法又称切线法,返回,下一页,6,返回,下一页,15,四、牛顿迭代法的步骤,步一、准备。选定初始近似值 ，计算 步二、迭代。按公式 迭代一次，得到新的近似值 ，计算 步三、控制。如果 满足 或 .则终止迭代，以 作为所求的根；否则转步四。此处 是允许误差,返回,下一页,16,而 。其中c是取绝对值或相对误差 的控制常数，一般可取c=1。 步四、修改。如果迭代次数达到预定指定的次数N，或者 则方法失败；否则以 代替 转步二继续迭代。,返回,下一页,17,五.例题,例1:用牛顿法求下面方程的根 解 因 ,所以迭代公式为 选取 ,计算结果列于

7、下表 从计算结果可以看出,牛顿法的收敛速度是很快的,进行了四次迭代就得到了较满意的结果.,返回,下一页,18,例2 计算 的近似值。 =10-6 x0=0.88 解： 令x= 问题转化为求(x)= x2-0.78265=0的正根 由牛顿迭代公式 xk+1= xk-(xk)/(xk)= xk/2+0.78265/2xk 迭代结果 k 0 1 2 3 xk 0.880000 0.884688 0.884675 0.884675 满足了精度要求 =0.884675,返回,下一页,19,六其他注意的事项,下一页,20,返回,下一页,21,七、牛顿迭代法的优缺点,1、优点：牛顿迭代法具有平方收敛的速度，

8、所以在迭代过程中只要迭代几次就会得到很精确的解。这是牛顿迭代法比简单迭代法优越的地方。 2、缺点：选定的初值要接近方程的解，否则有可能的不到收敛的结果。再者，牛顿迭代法计算量比较大。因每次迭代除计算函数值外还要计算微商值。,返回,下一页,22,八、迭代的一般概念,迭代法可分为单点迭代法与多点迭代法。 单点迭代法的一般形式为： xi+1=(xi) i=0,1,2,. 需一个初始点 x0启动 多点迭代法的一般形式为： xi+1= (xi，xi-1,xi-k+1) 需多个初始点 x0 ，x1, x2 ,xk启动 对于单点迭代：n=1,1,求方程x3+x=2x2+3在x0=4附近的根。 解：函数(x)=x3-2x2+x-3写成嵌套形式 (x)=x3-2x2+x-3=(x-2)x+1)x-3 (x)=3x2-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.21303271