Python 中有效的根搜索算法

作为数据科学家和计算机科学家，我们经常在日常工作中处理求根算法，即使我们没有意识到。这些算法旨在定位特定值、局部/全局最大值或最小值的邻近区域。

我们使用求根算法来搜索特定值、局部/全局最大值或最小值的邻近区域。

在数学中，求根通常意味着我们试图求解像 f(X) = 0 这样的方程组。这将使求根算法成为一种非常有效的搜索算法。我们所要做的就是定义 g(X) = f(X) - Y，其中 Y 是搜索目标，然后求解 X，例如 g(X) = f(X) - Y = 0。

这些方法主要分为两大类：

1. 区间逼近法（例如，二分法）
2. 迭代法（例如，牛顿法、割线法、Steffensen 法等等）

在接下来的教程中，我们将了解其中一些算法在 Python 编程语言中的实现，并进行比较。这些算法包括：

1. 二分法
2. 假位法
3. 伊利诺伊算法
4. 割线法
5. Steffensen 算法

在开始之前，我们假设有一个连续函数 f，并且想要搜索一个值 y。因此，我们正在求解方程：f(x) - y = 0。

理解二分法

二分法，也以其离散版本（二分搜索）或树变体（二叉搜索树）而闻名，是一种在给定范围内搜索目标值的有效算法。因此，这种算法也被称为求根的区间逼近法。

主要优点

1. 二分法是一种鲁棒的算法，可以保证以合理的收敛速度接近目标值。

主要缺点

1. 该算法需要了解根的估计区域。例如，3 ≤ π ≤ 4。
2. 该算法只有在估计区域内只有一个根时才能很好地工作。

假设我们知道 x 介于 f(p) 和 f(q) 之间，这构成了搜索区间。该算法将检查 x 是大于还是小于 f((p + q) / 2)，即区间的中间点。

在搜索连续函数时，我们可能永远无法找到确切的值（例如，找到 π 的末尾？）。需要一个误差范围来检查与区间的中间点的距离。我们可以将误差范围视为当计算值接近目标值时的提前停止。例如，如果误差范围是 0.001%，那么 3.141624 足够接近 π，大约 3.1415926...

如果计算值足够接近目标值，则搜索完成；否则，如果 x 小于 f((p + q) / 2)，则在下半部分搜索该值，反之亦然。

现在让我们看以下 Python 代码片段，演示了这一点。

示例

说明

在上述代码片段中，我们定义了一个名为 bisectionAlgorithm 的函数，它接受一些参数，如 f, p, q, y 和 margin，其中 f 是一个可调用的连续函数，p 是一个浮点值，表示搜索的下限，q 也是一个浮点值，表示搜索的上限，y 再次是一个浮点值，表示目标值，而 margin 是绝对项的误差范围，也是一个浮点值。然后，我们使用 if 条件语句来检查分配给 f(p) 的下限是否大于分配给 f(q) 的上限，在这种情况下，p 和 q 的值等于 q 和 p，下限和上限等于上限和下限。然后，我们使用 assert 关键字来调试 y 的值。然后，我们使用 while 循环，在该循环中，我们将 r 的值定义为 p 和 q 的平均值。在该循环内部，我们还使用了 if-elif-else 条件语句来检查分配给 f(r) - y 的 y_r 是否小于 margin 并返回 r。

理解假位法

与二分法类似，假位法，也称为 Regula Falsi，也采用区间逼近法。但与二分法不同的是，它不采用将问题空间每次迭代减半的暴力方法。相反，该算法迭代地从 f(p) 到 f(q) 绘制一条直线，并比较截距与目标值。然而，不能保证搜索效率始终得到提高。例如，下图描述了下限如何以递减的速度增加，而上限保持不变。

图 1：停滞边界减慢收敛速度

主要优点

1. 该算法通常比二分法收敛更快。
2. Regula Falsi 的好处在于，随着区间的缩小，连续函数将收敛到一条直线。

主要缺点

1. 当算法遇到停滞边界时，Regula Falsi 也会显示出较慢的收敛速度。
2. 该算法需要了解根的近似区域。例如，3 ≤ π ≤ 4。

Regula Falsi 和二分法在实现上的主要区别在于 r 不再是 p 和 q 之间的中点；而是估计为

让我们看下面的代码片段来说明这一点：

示例

说明

在上述代码片段中，我们定义了一个名为 regulaFalsiAlgorithm 的函数，它接受一些参数，如 f, p, q, y 和 margin，其中 f 是一个可调用的连续函数，p 是一个浮点值，表示搜索的下限，q 也是一个浮点值，表示搜索的上限，y 再次是一个浮点值，表示目标值，而 margin 是绝对项的误差范围，也是一个浮点值。然后，我们使用 assert 关键字来调试 y 的值。然后，我们使用 while 循环，在该循环中，我们定义了 r 的值。在该循环内部，我们还使用了 if-elif-else 条件语句来检查分配给 f(r) - y 的 y_r 是否小于 margin 并返回 r。

理解伊利诺伊算法（修改后的假位法）

为了克服停滞边界，我们可以插入一个条件规则，当一个边界连续两轮保持停滞时。以前面的例子为例，由于 q 已经两轮没有移动，并且 r 尚未接近根 x，在下一轮中，直线将画到 f(q) / 2 而不是 f(q)。如果下限是停滞边界，也将对下限实施相同的操作。

图 2：伊利诺伊算法避免长期停滞边界以加快收敛。

主要优点

1. 伊利诺伊算法比二分法和假位法收敛速度更快。
2. 我们可以通过将停滞边界到目标值的距离减半来避免停滞边界。

主要缺点

1. 当算法遇到停滞边界时，该算法也会显示出较慢的收敛速度。
2. 该算法需要了解根的估计区域。例如，3 ≤ π ≤ 4。

示例

说明

在上述代码片段中，我们定义了一个名为 illinoisAlgorithm 的函数，它接受一些参数，如 f, p, q, y 和 margin，其中 f 是一个可调用的连续函数，p 是一个浮点值，表示搜索的下限，q 也是一个浮点值，表示搜索的上限，y 再次是一个浮点值，表示目标值，而 margin 是绝对项的误差范围，也是一个浮点值。然后，我们使用 assert 关键字来调试 y 的值。然后，我们定义了一个名为 stagnant 的变量，并将其赋值为零。然后，我们使用 while 循环，在该循环中，我们定义了 r 的值。在该循环内部，我们还使用了 if-elif-else 条件语句来检查分配给 f(r) - y 的 y_r 是否小于 margin 并返回 r。

理解割线法（准牛顿法）

到目前为止，我们一直在实施区间逼近法。如果我们不知道区间的确切位置怎么办？在这种情况下，割线法可能会有所帮助。割线法是一种迭代算法，从两个值开始并尝试向目标值收敛。虽然在算法收敛时我们可以获得更好的性能，并且不需要了解粗略的根位置，但如果两个初始值离真实根太远，我们可能会面临发散的风险。

主要优点

1. 割线法不需要包含根的区间。
2. 该方法不需要了解根的估计区域。

主要缺点

1. 与所有早期方法不同，割线法不能保证收敛。

割线法从检查两个用户定义的种子开始。假设我们要找到 x² - math.pi = 0 的根，从 x_0 = 4 和 x_1 = 5 开始；我们的种子将分别是 4 和 5。（注意：这个过程类似于搜索 x，例如 x² = math.pi）

图 3：割线法根据 x1 和 x2 定位 x3

然后，我们通过 f(x_0) 和 f(x_1) 绘制一条直线来定位与目标值 x_2 的截距，这与我们在 Regula Falsi 算法中所做的相同。如果 f(x_2) 不够接近目标值，我们必须重复该步骤并定位 x_3。通常，我们可以使用以下公式计算下一个 x：

让我们看下面的代码片段来说明这一点：

示例

说明

在上述代码片段中，我们定义了一个名为 secantAlgorithm 的函数，它接受一些参数，如 f, x0, x1, y, iterations 和 margin，其中 f 是一个可调用的连续函数，x0 和 x1 是浮点值和初始种子，y 再次是一个浮点值和目标值，iterations 是一个整数值，存储最大迭代次数以避免无限发散，而 margin 是绝对项的误差范围，也是一个浮点值。然后，我们使用 assert 关键字来检查 x0 的值是否不等于 x1 的值。然后，我们使用 if 条件语句来检查分配给 f(x0) - y 的 y0 是否小于 margin 变量并返回 x0 变量。我们再次使用 if 条件语句来检查分配给 f(x1) - y 的 y1 是否小于 margin 变量并返回 x1 变量。最后，我们使用 for 循环来迭代存储在 iterations 变量中的值，并定义查找根的公式。在循环中，我们再次使用 if 条件语句并返回 x2。

理解 Steffensen 方法

割线法通过消除包含根的区间的需求，进一步改进了 Regula Falsi 算法。让我们回顾一下，直线只是两个 x 值（或 Regula Falsi 和 Illinois 算法中的上限和下限）的切线（即导数）的朴素值。当搜索收敛时，这个值将是完美的。在 Steffensen 算法中，我们将尝试用更好的导数值替换直线，以进一步改进割线法。

主要优点

1. Steffensen 方法不需要包含根的区间。
2. 此方法也不需要了解根的估计区域。
3. 如果可能，此方法比割线法收敛更快。

主要缺点

1. 如果初始种子离真实根太远，Steffensen 方法不能保证收敛。
2. 连续函数将比割线法多评估两次，以更好地计算导数。

借助 Steffensen 算法，我们可以通过根据用户定义的初始种子 x0 计算以下内容来更好地估计导数：

这等价于以下内容，其中 h = f(x)

取 h 趋于 0 的极限，我们将得到 ?(?) 的导数。

然后，我们将使用广义评估斜率函数，按照与割线法相同的程序定位下一步

让我们看下面的代码片段来说明这一点：

示例

说明

在上述代码片段中，我们定义了一个名为 secantAlgorithm 的函数，它接受一些参数，如 f, x0, x1, y, iterations, 和 margin，其中 f 是一个可调用的连续函数，x0 和 x1 是浮点值和初始种子，y 再次是一个浮点值和目标值，iterations 是一个整数值，存储最大迭代次数以避免无限发散，而 margin 是绝对项的误差范围，也是一个浮点值。然后，我们使用 assert 关键字来检查初始种子是否不等于零。然后，我们使用 if 条件语句来检查分配给 f(x) - y 的 yx 是否小于 margin 变量并返回 x 变量。最后，我们使用 for 循环来迭代存储在 iterations 变量中的值，并定义查找根的公式。在循环中，我们再次使用 if 条件语句并返回 x。

结论

在上面的教程中，我们了解了以下五种用于搜索根的算法的优点、缺点和实现。

1. 二分法
2. 假位法
3. 伊利诺伊算法
4. 割线法
5. Steffensen 算法

现在让我们看下表，显示了我们已实现的算法的比较。

一旦我们熟悉了这些算法，还有许多其他本教程中未涉及的求根算法值得探索。其中一些包括牛顿-拉夫逊法、逆二次插值、Brent 法等等。继续探索，并将上述算法添加到您的工具库中。