牛顿法

牛顿法，也称为牛顿-拉夫森方法，是一种求根算法，它使用函数 在疑似根附近的泰勒级数的前几项。牛顿法有时也称为 牛顿迭代法，尽管在本文中，后一个术语保留用于应用牛顿法计算平方根。

对于，一个多项式，牛顿法本质上与霍纳法相同。

泰勒级数 关于点 由下式给出

(1)

仅保留到一阶项，

(2)

方程 (2) 是曲线在 处的切线方程，所以 是该切线与 轴的交点。因此，图表可以很好地直观地说明为什么牛顿法在良好选择的起始点处有效，以及为什么它可能在选择不当的起始点处发散。

上面的表达式可以用来估计从初始猜测 开始，为了更接近根所需的偏移量 。令 并求解 (2) 中的 得到

(3)

这是一阶调整到根的位置。通过令 ，计算新的 ，等等，可以重复该过程，直到它使用下式收敛到不动点（这恰好是一个根）

(4)

不幸的是，此过程在水平渐近线或局部极值附近可能不稳定。但是，如果根的位置的初始选择良好，则可以迭代应用该算法以获得

(5)

对于 , 2, 3, .... 提供牛顿法安全收敛的初始点 称为近似零点。

牛顿法可以在 Wolfram 语言中实现为

  NewtonsMethodList[f_, {x_, x0_}, n_] :=
    NestList[# - Function[x, f][#]/
      Derivative[1][Function[x, f]][#]& , x0, n]

假设牛顿迭代 收敛于 且 ，并定义第 步后的误差为

(6)

将 在 附近展开得到

			(7)
			(8)
			(9)

但是

			(10)
			(11)
			(12)

取二阶展开式

(13)

得到

(14)

因此，当该方法收敛时，它是二次收敛的。

将牛顿法应用于任何二次或更高次多项式的根会产生一个 的有理映射，并且当存在三个或更多不同的根时，此映射的 Julia 集是一个分形。迭代方法求解 的根，起始点为 得到

(15)

（Mandelbrot 1983, Gleick 1988, Peitgen and Saupe 1988, Press et al. 1992, Dickau 1997）。由于这是一个 阶多项式，因此存在 个算法可以收敛到的根。为每个根的吸引盆（收敛到相同根的初始点 的集合）着色不同的颜色，然后给出上面的图。

分形通常也从非多项式映射中产生。上面的图显示了函数 (D. Cross, 私人通信, 1月 10, 2005) 和 的牛顿法收敛所需的迭代次数。