算法學習筆記：19.牛頓迭代法——從原理到實戰，涵蓋 LeetCode 與考研 408 例題

牛頓迭代法（Newton's Method）是一種強大的數值計算方法，由英國數學家艾薩克?牛頓提出。它通過不斷迭代逼近方程的根，具有收斂速度快、適用范圍廣的特點，在科學計算、工程模擬、計算機圖形學等領域有著廣泛應用。

牛頓迭代法核心思路

算法原理

牛頓迭代法的核心思想是用切線逼近曲線，通過迭代逐步縮小與方程根的距離。對于方程\(f(x) = 0\)，其迭代公式為：
\(x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}\)
其中：
\(x_n\) 是第\(n\)次迭代的近似根
\(f'(x_n)\) 是函數\(f(x)\)在\(x_n\)處的導數
\(x_{n+1}\) 是第\(n+1\)次迭代的近似根

幾何意義

牛頓迭代法的幾何意義是：在每一次迭代中，用函數\(f(x)\)在\(x_n\)處的切線代替曲線，將切線與\(x\)軸的交點\(x_{n+1}\)作為新的近似根。通過不斷重復這一過程，近似根會快速收斂到方程的真實根。

以下是用 mermaid 繪制的牛頓迭代法幾何示意圖（以\(f(x) = x^2 - 2\)求解\(\sqrt{2}\)為例）：

算法流程

牛頓迭代法的基本流程如下：

選擇初始近似根\(x_0\)（初始值的選擇對收斂速度影響較大）。
計算函數值\(f(x_n)\)和導數值\(f'(x_n)\)。
代入迭代公式計算\(x_{n+1}\)。
判斷\(|x_{n+1} - x_n|\)是否小于預設精度\(\epsilon\)（如\(10^{-6}\)）：
若滿足，則\(x_{n+1}\)即為近似根，迭代結束。
若不滿足，則令\(x_n = x_{n+1}\)，返回步驟 2 繼續迭代。

其流程可用以下流程圖表示：

收斂性分析

收斂條件：若函數\(f(x)\)在根的鄰域內二階可導且一階導數不為 0，則牛頓迭代法具有局部收斂性，且收斂階為 2（二次收斂），即誤差以平方級速度減小。

影響因素：

- 初始值\(x_0\)的選擇：若初始值離真實根過遠，可能導致迭代發散或收斂到其他根。

- 導數為 0 的情況：若\(f'(x_n) = 0\)，迭代公式無意義，需特殊處理。

LeetCode 例題實戰

例題 1：69. x 的平方根（簡單）

題目描述：給你一個非負整數 x ，計算并返回 x 的算術平方根。由于返回類型是整數，結果只保留整數部分，小數部分將被舍去。

示例：

輸入：x = 8

輸出：2

解釋：8 的算術平方根是 2.82842...，由于返回類型是整數，小數部分將被舍去。

解題思路：將問題轉化為求方程\(f(t) = t^2 - x = 0\)的非負根，使用牛頓迭代法求解：

初始值選擇：當\(x \geq 1\)時，取\(x_0 = x\)；當\(x = 0\)時，直接返回 0。

迭代公式：\(f(t) = t^2 - x\)，\(f'(t) = 2t\)，代入迭代公式得\(t_{n+1} = \frac{1}{2}(t_n + \frac{x}{t_n})\)。

收斂判斷：當\(|t_{n+1} - t_n| < 1\)時，整數部分已穩定，可停止迭代，返回\(t_{n+1}\)的整數部分。

代碼實現：

class Solution {public int mySqrt(int x) {if (x == 0) {return 0;}double x0 = x; // 初始值double x1 = (x0 + x / x0) / 2; // 第一次迭代// 迭代直至精度滿足要求（差值小于1）while (Math.abs(x1 - x0) >= 1) {x0 = x1;x1 = (x0 + x / x0) / 2;}return (int) x1;}}

復雜度分析：

時間復雜度：\(O(\log x)\)，牛頓迭代法具有二次收斂性，迭代次數與\(x\)的大小呈對數關系。

空間復雜度：\(O(1)\)，僅使用常數額外空間。

說明：代碼中使用 double 類型存儲中間結果以保證精度，最后通過強制類型轉換取整數部分。

例題 2：367. 有效的完全平方數（簡單）

題目描述：給定一個正整數 num ，編寫一個函數，如果 num 是一個完全平方數，則返回 true ，否則返回 false 。

示例：

輸入：num = 16

輸出：true

輸入：num = 14

輸出：false

解題思路：同樣轉化為求方程\(f(t) = t^2 - num = 0\)的根，若根為整數，則 num 是完全平方數：

用牛頓迭代法求出近似根\(t\)。

驗證\(t\)的整數部分\(k\)是否滿足\(k^2 = num\)，若是則返回 true，否則返回 false。

代碼實現：

class Solution {public boolean isPerfectSquare(int num) {if (num < 1) {return false;}if (num == 1) {return true;}double x0 = num;double x1 = (x0 + num / x0) / 2;// 迭代至精度足夠高（差值小于1e-6）while (Math.abs(x1 - x0) > 1e-6) {x0 = x1;x1 = (x0 + num / x0) / 2;}int k = (int) Math.round(x1); // 四舍五入取整數return k * k == num;}}

復雜度分析：

時間復雜度：\(O(\log num)\)，迭代次數與 num 的大小呈對數關系。

空間復雜度：\(O(1)\)，僅使用常數額外空間。

說明：通過四舍五入處理近似根，確保整數部分的準確性，再驗證是否為完全平方數。

例題 3：50. Pow (x, n)（中等）

題目描述：實現 pow(x, n) ，即計算 x 的整數 n 次冪函數（即，\(x^n\)）。

示例：

輸入：x = 2.00000, n = 10

輸出：1024.00000

解題思路：當\(n\)為負整數時，\(x^n = 1 / x^{-n}\)，因此可先處理\(n\)為非負的情況。對于\(n > 0\)，可通過牛頓迭代法求指數函數，但更簡單的方式是結合快速冪思想優化：

轉化問題：計算\(e^{n \ln x}\)（利用指數與對數的關系\(x^n = e^{n \ln x}\)）。

牛頓迭代法求指數函數：但實際中更高效的是使用快速冪（分治法），此處僅展示牛頓迭代法在指數計算中的思路。

補充說明：本題雖更適合用快速冪，但牛頓迭代法可用于求解\(e^y\)的近似值（通過求方程\(f(t) = e^t - y = 0\)的根），進而間接計算\(x^n\)。以下代碼展示牛頓迭代法求\(e^y\)的思路：

class Solution {// 計算e^y的近似值private double exp(double y) {if (y < 0) {return 1 / exp(-y);}double t0 = y + 1; // 初始值double t1 = t0 - (Math.exp(t0) - y - 1) / Math.exp(t0); // 迭代公式（針對f(t)=e^t - t - 1 - y）while (Math.abs(t1 - t0) > 1e-6) {t0 = t1;t1 = t0 - (Math.exp(t0) - t0 - 1 - y) / (Math.exp(t0) - 1);}return Math.exp(t1) - 1;}public double myPow(double x, int n) {if (n == 0) {return 1.0;}long N = n; // 處理n為Integer.MIN_VALUE的情況if (N < 0) {x = 1 / x;N = -N;}// 利用x^N = e^(N ln x)return exp(N * Math.log(x));}}

說明：本題中牛頓迭代法并非最優解，但展示了其在超越函數計算中的應用。實際解題中，快速冪（時間復雜度\(O(\log |n|)\)）更為高效。

考研 408 例題解析

例題 1：數值計算應用題（408 高頻考點）

題目：用牛頓迭代法求方程\(f(x) = x^3 - 2x - 5 = 0\)在\(x_0 = 2\)附近的實根，要求迭代 3 次，并計算迭代誤差。

解題步驟：

確定函數與導數：\(f(x) = x^3 - 2x - 5\)，\(f'(x) = 3x^2 - 2\)。
迭代公式：\(x_{n+1} = x_n - \frac{x_n^3 - 2x_n - 5}{3x_n^2 - 2}\)。
計算前 3 次迭代：
第 1 次：\(x_0 = 2\)，\(f(x_0) = 8 - 4 - 5 = -1\)，\(f'(x_0) = 12 - 2 = 10\)，\(x_1 = 2 - (-1)/10 = 2.1\)。
第 2 次：\(f(x_1) = 2.1^3 - 2*2.1 - 5 ≈ 9.261 - 4.2 - 5 = 0.061\)，\(f'(x_1) ≈ 3*(2.1)^2 - 2 ≈ 13.23 - 2 = 11.23\)，\(x_2 ≈ 2.1 - 0.061/11.23 ≈ 2.0946\)。
第 3 次：\(f(x_2) ≈ (2.0946)^3 - 2*(2.0946) - 5 ≈ 0.0003\)，\(f'(x_2) ≈ 3*(2.0946)^2 - 2 ≈ 11.16\)，\(x_3 ≈ 2.0946 - 0.0003/11.16 ≈ 2.09455\)。
迭代誤差：\(|x_3 - x_2| ≈ 0.00005\)，已非常接近真實根（約 2.09455）。

答案：經過 3 次迭代，近似根為\(2.09455\)，迭代誤差約為\(5 \times 10^{-5}\)。