牛顿迭代法 - 求解非线性方程根的近似解

牛顿迭代法 - 求解非线性方程根的近似解

在算法中，牛顿迭代法主要用于求解非线性方程或优化问题。它是一种迭代算法，通过不断逼近来找到函数的根或者最小化/最大化某个目标函数。

这里呢，我们重点讲一下如何求解线性方程 \(F(X) = 0\) 近似根的大致步骤。

1. 选择一个初始猜测值\(x_0\):
   • 这个初始猜测应该尽可能接近实际的根，一个好的初始猜测可以加速收敛过程，并且有助于避免算法陷入局部极小值或不收敛的情况。
2. 定义迭代公式：
   • 牛顿迭代法的迭代公式是：\(X_(n+1) = X_n - \frac{F(X_n)}{F^`(X_n)}\)
   • 其中 \(F^`(X_n)\) 是函数 \(F(X)\) 在点 \(X_n\) 处的一阶导数。
3. 执行迭代过程：
   • 使用上面的迭代公式。从$ X_0$ 开始计算 \(X_1, X_2, X_3, ...\) ,直到满足停止条件。
4. 设置停止条件：
   • 停止条件通常有两种形式:
     • 当连续两次迭代的结果足够接近时，即 \(∣X_n+1 - X_n∣ < ϵ\) ，其中 ϵ 是预设的小正数。
     • 或者当函数值足够接近于零时,即 \(|F(X_(n+1))| < ϵ\) 。
   • 有时还会设置最大迭代次数以防止无限循环。
5. 检查结果的有效性：
   • 确认最终得到的 X 值确实是 \(F(X)=0\) 的根。如果函数在该点附近的行为复杂（如存在多个根或导数为零），可能需要进一步分析。

这里以牛客的一道题来举个例子：

计算一个浮点数的立方根而不使用库函数

我们就可以使用牛顿迭代法来逼近结果。

对于求解X的立方根，我们需要找到满足 \(Y^3 = X\) 的 \(Y\) , 这里可以通过解方程 \(F(Y) = Y^3 - X = 0\) 来实现，牛顿迭代的公式为：

\(Y_(n+1) = Y_n - \frac{F(Y_n)}{F^`(Y_n)}\)

其中 \(F(Y) = Y^3 - X\) , 导数 \(F^`(Y) = 3Y^2\)

带入后得到：

\(Y_(n+1) = Y_n - \frac{Y^3_n - X}{3Y_n^2}\)

下面是Java代码的实现:

public class Main {public static void main(String[] args) {double x = 27.0;    // 求Math.sqrt(x)double tolerance = 1e-10;   // 允许的误差System.out.printf("%f\n",calculateCubeRoot(x, tolerance));}private static double calculateCubeRoot(double x, double tolerance) {if (x == 0) return 0;   // 特殊值处理double y = x;   // 猜测初始值double diff;    // 计算出来的误差do {double nextY = y - (y * y * y - x)/(3 * y*y);   // 迭代公式，计算出新的迭代值diff = Math.abs(nextY - y); // 计算出新的迭代值与旧的迭代值之间的误差y = nextY;  // 更新迭代后的值} while (diff > tolerance);return y;   // 满足误差后跳出循环直接返回最终迭代后的结果}
}

运行结果如下:

3.000000