English

运筹学学报 ›› 2015, Vol. 19 ›› Issue (4): 83-96.doi: 10.15960/j.cnki.issn.1007-6093.2015.04.008

• 运筹学 • 上一篇    下一篇

一个阶为2+\sqrt{6}的Newton改进算法

吕巍1,*, 隋瑞瑞1, 冯恩民2   

  1. 1. 上海大学数学系,上海  200444； 2. 大连理工大学数学科学学院,大连 116024
  • 收稿日期:2015-04-14 出版日期:2015-12-15 发布日期:2015-12-15
  • 通讯作者: 吕巍 lvwei@shu.edu.cn
  • 基金资助:

    1.国家自然科学基金青年科学基金(No.~11101262);2.国家自然科学基金(No.~11171050);

    3.大连理工大学专项基金(DUTTX2011106);4.上海市重点学科资助项目(S30104);5.上海高校一流学科(B类)资助项目

A modification of Newton method with convergence  of order  2+\sqrt{6}

L\"{U} Wei1,*, SUI Ruirui1, FENG Enmin2   

  1. 1.Department of Mathematics, Shanghai University, Shanghai 200444, China; 2.School of Mathematical Sciences, Dalian University of Technology, Dalian 116024, China
  • Received:2015-04-14 Online:2015-12-15 Published:2015-12-15

PDF

524

摘要：

针对非线性方程求单根问题,提出了一种新的Newton预测-校正格式.通过每步迭代增加计算一个函数值和一阶导数值,使得每步迭代需要估计两个函数值和两个一阶导数值.与标准的Newton算法的二阶收敛速度相比,新算法具有更高阶的收敛速度2+\sqrt{6}.通过测试函数对新算法进行测试, 与相关算法比较,表明算法在迭代次数、运算时间及最优值方面都具有较明显的优势. 最后,将这种新格式推广到多维向量值函数, 采用泰勒公式证明了其收敛性,并给出了两个二维算例来验证其收敛的有效性.

关键词: Newton算法, 阶数, 非线性方程

Abstract:

 In this paper, a new modification of the standard Newton method for approximating the root of a univariate function is introduced. Two evaluations of function and two evaluations of its first derivative are required at a cost of one additional function and first derivative evaluations per iteration. The modified method converges faster with the order of convergence  2+\sqrt{6}  compared with 2 for the standard Newton method. Numerical examples demonstrate the new
algorithm has advantages in the iteration number, computation time and optimal value compared with the current algorithms. At last, the predictor-corrector improvement is generalized to multi-dimensional vector-valued functions, its convergence is proved using Taylor formula, and two two-dimensional examples are given to illustrate its convergence.

Key words: Newton method, order of convergence, nonlinear equation