牛顿迭代法加速收敛的一种修正格式.docx

牛顿迭代法加速收敛的一种修正格式吕 勇，刘兴国（湖南株洲工学院 信息与计算科学系，湖南 株洲 412008）摘 要：牛顿迭代法是求解非线性方程的一种重要的数值计算方法，在通常情况下，它具有至少平方 f ( xn ) 收敛。本文利用文献4所建立的迭代格式 xn +1 = xn f ( x ) + f ( x ) ，对迭代格式中的参数 的讨论，nn实现了牛顿迭代法加速收敛的一种修正格式。关键词：非线性方程；牛顿迭代法；加速收敛；迭代格式文章编号：10095160(2006)006803中图分类号：O174文献标识码：A1 引言在科学和工程计算中，常常需要用数值计算方法求解非线性方程f ( x ) = 0在一系列数值计算方法中，牛顿迭代法无疑是求解此类方程的一种重要的数值方法，其迭代格式为（1） f ( xn )x= x （2）n +1nf ( x )n众所周知，牛顿迭代法在通常情况下具有至少平方收敛，即：定理 1：设函数 f ( x ) 满足 f ( x* ) = 0 ， f ( x* ) 0 且 f ( x ) 在 x* 的邻域内有二阶连续导数，则当初值 x 足够0接近 x* 时，由迭代式（ 2）可知序列 x 至少是平方收敛的3 。n*但是，我们知道，利用牛顿迭代法在求解非线性方程（1）时，初值 x0 必须选定在方程解 x 的附近，同时 每一步迭代都要保证 f ( xn ) 0 。为了克服牛顿迭代法这一局限性，许多学者呕心沥血，从不同侧面和角度来克服它、改善它，并得到了很多好的结果。文献4就是为了克服第二种局限性，利用动力系统平衡点原理，成功 地解决了这一问题，并由此构造了新的迭代格式。定理 2：设 f ( x ) 在 x* 的充分小的邻域内连续， f ( x* ) = 0 ， f ( x* ) 0 。 f ( x ) + f ( x ) 0（其中 + ），则迭代格式 f ( xn ) x = x （3）n +1n f ( x ) + f ( x )nn是平方收敛的，并且他们和牛顿迭代格式具有相同的计算效能。由于迭代格式中的参数 可以取一切实数，因此在对非线性方程（1）利用迭代格式（3）进行数值计算时， 为了保证每一步迭代都能顺利进行，只要选取 f ( xn ) + f ( xn ) 0 的参数 即可。2 牛顿迭代法加速收敛的修正式（3）是带有参数 的一族迭代格式，当 = 0 时，则对应了经典的牛顿迭代格式（2）。选择不同的参数 收稿日期：2006-01-12作者简介：吕勇（1966-），男，讲师、硕士，研究方向：微分方程数值解，有限元超收敛.69第 2 期吕 勇，等：牛顿迭代法加速收敛的一种修正格式就得到修改后的牛顿迭代法。根据定理 2，每一种迭代法都至少具有平方收敛。于是我们提出，是否可以在迭代格式中找寻一个 ，使得迭代格式有加速收敛的效果呢？设（1）式的等价方程为：x = ( x )根据方程（4）建立迭代格式：xn +1 = ( xn ) 。 (n = 0,1, 2,)如果迭代格式（5）满足不动点原理。不妨设 x* 是式（5）的不动点，则有定理 3：1 - 2 对于不动点迭代格式（5）。若 (k ) ( x ) 在所求根 x* 充分小的邻域内连续，并且有 ( x* ) = ( x* ) = = (k 1) ( x* ) = 0 ， (k ) ( x* ) 0则此迭代法在 x* 邻域内是 k 阶收敛的。对非线性方程（1），根据定理 2 的迭代格式，设（4）（5）f ( x ) ( x ) = x 在 x* 邻域内满足 ( x ) 连续条件下，有（6） f ( x ) + f ( x ) ( x ) = 1 + f f f 2（7）( f + f )2( f + f )( f f f )2 ( x ) = f f f f 2（8）( f + f )2( f + f )3其中： f (i ) = f (i ) ( x ) ， i = 0,1, 2, 3 。因为 f ( x* ) = 0 ，则 ( x* ) = 0 ，所以无论 取何值，迭代格式（3）至少具有二阶收敛。下面为了讨论具有更高阶的收敛，比如至少具有三阶收敛，那么根据定理 3，必须保证 ( x* ) = 0 ， ( x* ) = 0 。 实际上只需要讨论 ( x* ) = 0 。因此欲使 ( x* ) = 0 ，则只需选取满足条件 2 f ( x ) + f ( x ) = 0 的 ，即：f ( x ) f ( x )1 = 2（9）f ( x )f ( x )= *定理 4：设 f ( x ) 在 x* 的充分小的邻域内连续，f ( x* ) = 0 ，f ( x* ) 0 ， f ( x ) + f ( x ) 0 ，且 则迭代格式（3）至少具有三阶收敛。( x* )2 f此定理反映了在普通修改的牛顿迭代格式的基础上，通过适当选取参数 ，使修改的牛顿迭代格式达到至少三阶收敛，比经典的牛顿迭代格式的收敛高了一阶。 但是由于在求解非线性方程（1）根的时候，并不知道它的根 x* ，因此 f ( x* ) 和 f ( x* ) 的值也无法求出， f ( x0 )那么也就无法求出所对应的参数 。为了克服这一矛盾，我们采用 序列 i 的形式，即取： 0 = ，)(2 f x0 f ( xn )则 = n = 1, 2, 。n2 f ( x )n由于 f ( x ) 在 x* 的充分小的邻域内连续， f ( x* ) = 0 ， f ( x* ) 0 。所以f ( x )f ( xn )= *= n + ，则有2 f ( x* )n2 f ( x )n70武 汉 科 技 学 院 学 报2006 年f ( xn )= 定理 5：设 f ( x ) 在 x* 的充分小的邻域内连续， f ( x* ) = 0 ， f ( x* ) 0 。且 迭代格式n = 1, 2, 则n2 f ( x )n f ( xn ) x = x （10）n +1n f ( x ) + f ( x )nnn具有三阶收敛。这样利用 i 序列的形式克服了我们提出的问题。当然在计算的过程中，对于所出现的导数项，我们还可以采用差商的形式来代替它，这里就不再赘述。3 数值例子例 1：求方程 x3 27 = 0求解此方程时，我们知道它的实根 x* 为 3。因此利用经典的牛顿迭代法和定理 4 的改进型的迭代法，设f ( x) = x3 27 ，则 f ( x) = 3x2 ， f (3) = 27 ； f ( x) = 6x ， f (3) = 18 ，取 = 1 ，设初值 x = 2 ，计算结果如03表 1。表 1 两种迭代法的计算结果n0123经典的牛顿迭代法 xn改进型的迭代法 xn2.0000002.0000003.5833333.0363643.0898082.9999983.0025853.000000表 1 反映了利用改进型的迭代法，三次迭代就可以得到方程的准确值，而利用经典的牛顿迭代法，三次迭代后误差大于 103 。参考文献：12 34翟瑞彩，谢伟松. 数值分析M.天 津：天津大学出版社, 2000.关治，陆金甫. 数值分析基础M. 北京：高等教育出版社, 1998.郑权. 牛顿迭代法在弱条件下的二阶收敛性和比值收敛因子J. 北方工业大学学报, 2003，15（1）：26-29.吴新元. 对牛顿迭代法的一个重要修改J. 应用数学和力学，1999，20（8）：863-866.A Improvement Format Of Newtons Method Accelerating ConvergenceLV Yong, LIU Xing-guo(Department of Information and Computing Science, Zhuzhou Institute of Technology, Zhuzhou Hunan 412008, China)Abstract：Newtons method is one of the most powerful and well-known numerical methods for solving a root-finding problem.Ordinarily it is quadratic convergence. In this paper, the parameter of the iterative format is discussed and a improvement format of f (