Newton-Raphson算法詳解

一、介紹

Newton-Raphson算法（簡稱NR算法）是一種非常常用的數值求解算法，可用於求解非線性方程、最優化問題等。該算法來源於牛頓迭代法，是一種通過一次一次的改進來逐步逼近函數零點的方法。

舉個簡單例子，假設我們要求解一個一元二次方程 ax^2 + bx + c = 0 的根，我們可以通過NR算法求解。當然，在實際應用中，我們會用更高階的多項式函數或者非線性方程來描述問題。但是無論問題本身如何，NR算法都可以在保持高精度的同時，大大提高求解效率。

二、算法原理

NR算法的具體實現就是基於泰勒級數（Taylor series）展開，利用一階導數（也稱為Jacobian矩陣）來逼近函數的零點。

設待求解的函數為 f(x)，零點為 x*，則泰勒展開式為：

f(x) = f(x*) + f'(x*)(x – x*) + O((x – x*)^2)

在NR算法中，我們通常會丟掉O((x – x*)^2)這一項，因為其在x接近x*時會趨近於0，用Jacobian矩陣來代替我們有：

f(x*) + J(x*)(x – x*) = 0

移項得：

x = x* – J(x*)^-1 * f(x*)

上述公式就是NR算法的核心，不斷迭代x的值，最終可以將x逼近x*。

三、算法流程

NR算法的流程如下：

1. 選取初始點x0
2. 計算函數f在x0處的導數f'(x0)
3. 計算函數f在x0處的函數值f(x0)
4. 更新x： x = x0 – f(x0) / f'(x0)
5. 如果x與上一次迭代的結果的差距小於某一個設定的閾值，則停止迭代
6. 如果迭代次數達到了上限，則停止迭代
7. 返回結果x

四、代碼示例

#include 
#include 

double f(double x) {
    return x * x - 3;
}

double df(double x) {
    return 2 * x;
}

double NewtonRaphson(double x0, int max_iter, double tol) {
    int i = 0;
    double x = x0, dx = tol + 1;
    while (dx > tol && i < max_iter) {
        double fx = f(x); // 計算f(x)
        double dfx = df(x); // 計算f'(x)
        dx = std::abs(fx / dfx); // 計算|f(x)/f'(x)|
        x -= fx / dfx; // 更新x
        ++i; // 更新迭代次數
    }
    return x;
}

int main() {
    double x0 = 1.0; // 初始點
    int max_iter = 100; // 最多迭代100次
    double tol = 1e-6; // 精度要求為1e-6
    double x = NewtonRaphson(x0, max_iter, tol);
    std::cout << "x = " << x << std::endl;
    return 0;
}

五、總結

NR算法是一種非常常見的數值求解算法，適用於求解非線性方程、最優化問題等應用場景，具有高精度和高效等優點。通過不斷迭代求解，可以逐步逼近函數零點的位置。在實際應用中，我們需要注意設定合理的起始點、迭代次數和誤差範圍等參數，以保證算法的正確性和效率。