牛顿迭代法

基础概念

牛顿迭代法（Newton’s method）是一种用于求解方程的迭代数值方法。它基于以下思想：通过使用切线逼近曲线，找到函数的根。

设我们要求解方程 f(x) = 0 的根，牛顿迭代法的基本思路如下：

1. 先猜测一个初始值 x₀；
2. 在函数 f(x) 上找到点 (x₀, f(x₀)) 处的切线；
3. 切线与 x 轴的交点作为新的猜测值 x₁；
4. 重复步骤2和步骤3，直到满足所需的精度或达到最大迭代次数。

设初始值为 x₀，对应的函数值为 f(x₀)，切线斜率为 f’(x₀)。假设切线与 x 轴的交点为 x₁，那么有：
$$
y-f(x_{0})=f’(x_{0})(x-x_{0})
$$
进而推导出 核心公式
$$
X_{k+1}=X_{k}-\frac{x_{k}}{f’(x_{k})}
$$
核心原理 -基本导数公式
$$
f’(x)=\frac{f(x_{k})}{x_{k}-x_{k+1}}
$$
重复以上步骤 可以得到更接近真实值的根

例题

用牛顿迭代法求解
$$
x=e^{-x}
$$
在x=1附近的根
$$
x_{k+1}=x_{k}-\frac{f(x_{k})}{f’(x_{k})} \
f(x)=x-e_{x} \
x_{k+1}=x_{k}-\frac{x_{k}-e^{-x_{k}}}{1+e^{-x_{k}}}\
f’(x)=1+e^{-x}
\
令x_{0}=1; 代入\
x_{1}=x_{0}-\frac{x_{0}-e^{-x_{0}}}{1+e^{-x_{0}}} =1-\frac{1-e^{-1}}{1+e^{-1}},k=0，k=1; \
x_{2}=x_{1}-\frac{x_{1}-e^{-x_{1}}}{1+e^{-x_{1}}};将x的值代入x_{2},再迭代到x_{3}

$$

牛顿迭代法的误差值

牛顿迭代法的误差可以用泰勒展开来近似表示。设真实根为 x，近似值为 x₀，那么有：
$$
f(x_{0})=f(x)+f’(x)(x_{0}-x^{})+R_{1}(x_{0})
其中R_{1}(x_{0})是余项
$$
忽略余项直接写为
$$
f(x_{0})=f(x)+f’(x)(x_{0})(x_{0}-x^{*})
$$

代码实现牛顿迭代法

代码实现求导（不精确）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

#include <stdio.h>
#include <math.h>

// 定义一个函数，可以是任意的表达式
double f(double x) {
    return x * x + x + 3;
}

// 定义一个函数，用数值求导的方法，计算f在x处的导数值
double derivative(double x) {
    double epsilon = 0.0001; // 设置一个无穷小的变量
    double x1 = x + epsilon; // x的右邻近点
    double x2 = x - epsilon; // x的左邻近点
    double f1 = f(x1); // f在x1处的函数值
    double f2 = f(x2); // f在x2处的函数值
    double result = (f1 - f2) / (2 * epsilon); // 根据导数的定义，计算导数值
    return result;
}

int main() {
    double x = 2; // 设置一个自变量的值
    double y = f(x); // 计算f在x处的函数值
    double dy = derivative(x); // 计算f在x处的导数值
    printf("f(%f) = %f\n", x, y); // 输出函数值
    printf("f'(%f) = %f\n", x, dy); // 输出导数值
    return 0;
}

牛顿迭代法代码实现

题目： 求
$$
y=\sqrt x
$$
的计算函数不能使用POW

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
    int mySqrt(int x) {
        if (x == 0) {
            return 0;
        }

        double C = x, x0 = x;
        while (true) {
            double xi = 0.5 * (x0 + C / x0);
            if (fabs(x0 - xi) < 1e-7) {
                break;
            }
            x0 = xi;
        }
        return int(x0);
    }
};