牛頓法

牛頓法，也稱為牛頓-拉夫森方法，是一種求根演算法，它使用函式 在疑似根附近的泰勒級數的前幾項。牛頓法有時也稱為 牛頓迭代法，儘管在本文中，後一個術語保留用於應用牛頓法計算平方根。

對於，一個多項式，牛頓法本質上與霍納法相同。

泰勒級數 關於點 由下式給出

(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) 和 的牛頓法收斂所需的迭代次數。