众所周知,牛顿求解非线性方程的方法在初始猜测“足够接近”解时会二次收敛。
什么是“足够接近”?
有没有关于这个吸引力盆地结构的文献?
众所周知,牛顿求解非线性方程的方法在初始猜测“足够接近”解时会二次收敛。
什么是“足够接近”?
有没有关于这个吸引力盆地结构的文献?
对于复域中的单个有理方程,吸引力盆地是分形的,即所谓的 Julia 集的组成元素。http://en.wikipedia.org/wiki/Julia_set。有关一些不错的在线数据的理论,请参见
http://mathlab.mathlab.sunysb.edu/~scott/Papers/Newton/Published.pdf
http://hera.ugr.es/doi/15019160.pdf
即使是“全球化”阻尼牛顿法有一个分形吸引盆;见http://www.jstor.org/stable/10.2307/2653002。
因此,详细说明什么是“足够接近”解决方案几乎没有意义。如果一个人知道二阶导数的界限,那么牛顿-坎托罗维奇定理给出了牛顿方法收敛的球半径的下界,但除了一维之外,这些往往是相当悲观的。
可以使用区间算术获得计算上有用的界限;例如,请参阅我的论文
Shen Zuhe 和 A. Neumaier,Krawczyk 算子和 Kantorovich 定理,J. Math。肛门。应用程序。149 (1990), 437-443。
http://www.mat.univie.ac.at/~neum/scan/61.pdf
“足够接近”很难描述,因为它产生了一类分形。具有全球化策略的牛顿方法,例如线搜索和信任域,扩展了吸引力盆地。如果有额外的问题结构可用,例如在优化中,收敛所需的假设可能会被进一步削弱。
牛顿法应用于复多项式有一些有用的结果。
Joel Friedman 在On the Convergence of Newton's Method (Theorem 2.2) 中给出了包含在多项式每个根的直接吸引盆中的圆盘的显式半径:
其他明确的界限由 Anthony Manning 在如何确保使用牛顿法(定理 1.2)找到复多项式的根中给出。
另请参阅 Hubbard 等人的如何通过牛顿法找到复多项式的所有根。
发明。数学。146(2001 年),第 1, 1-33。pdf