C++ 中的数值方法第 3 部分： 根近似算法
5.00/5 (13投票s)
实现二分法、牛顿法、Dekker 法和 Brent 法等根近似算法
欢迎回到 thoughts-on-cpp.com 的新文章。这次，我想更深入地探讨我经常用于解决众多数值问题的根近似方法。我们将从简单的二分法开始，然后研究牛顿法和割线法，最后以 Dekker 和 Brent 的黑盒方法进行总结。
前导码
在接下来的章节中，我们将详细介绍几种用于函数根近似的算法。我们将所有算法都与非线性函数 
进行比较，该函数在定义的区间 [a,b] 中**只有一个根**（这个条件非常重要，否则可能难以确定算法得到的解是哪个）。附加条件是 
。请记住，我们不检查迭代次数。这可能是必要的，因为我们通常不希望陷入无限循环。一如既往，您可以在 GitHub 上找到所有源代码。
二分法
让我们从一种主要用于搜索任意大小数组中的值的方法开始，即 二分法。但它也可用于根近似。二分法的优点在于其实现简单且保证收敛（如果存在解，二分法总能找到它）。算法相当简单：
- 计算给定区间 [a,b] 的中点
- 计算中点 m 的函数结果 f(m)
- 如果新的 m-a 或 |f(m)| 满足收敛条件，则我们找到了解 m
- 比较 f(m) 的符号，并替换 f(a) 或 f(b)，使得结果区间包含所寻找的根
二分法实现
正如我们从源代码中看到的，二分法的实际实现非常简单，大部分代码只是为了输出。重要部分发生在 while 循环内，该循环一直执行，直到 f(x) 的结果不满足条件 
。新位置 x 在 calculateX() 方法中计算，该方法检查 f(x) 的符号，并根据结果将 x 赋值给 a 或 b，以定义包含根点的新范围。重要的是要注意，二分法始终需要 f(a) 和 f(b) 具有不同符号的结果，这是通过 checkAndFixAlgorithmCriteria() 方法确保的。该算法收敛速度较慢，需要 36 次迭代才能达到 
的收敛条件，但只要有足够的时间，它终究会收敛。
牛顿法
只要我们还知道函数的导数并且函数是光滑的，我们就可以使用速度更快的 牛顿法，其中根的下一个更接近的点 
可以通过以下公式计算：
牛顿法实现
同样，该算法会一直迭代，直到 f(x) 的结果不满足条件 
。calculateX() 方法不仅应用牛顿法的公式，还会检查 f(x) 的导数是否接近于零。由于浮点数不能直接比较，我们必须将 f'(x) 与最接近零的最小浮点数进行比较，这可以通过调用 std::numeric_limits<double>::min() 来获得。在这种 f'(x) 为零的情况下，算法将无法收敛（达到驻点），如下图所示。
牛顿法的优势在于其极高的速度。在我们的例子中，它只需要 6 次迭代就能达到 
的收敛条件。但该算法也有几个缺点，如上所述，例如：
- 仅适用于我们知道函数导数的情况
- 仅适用于光滑且连续的函数
- 如果起始点
选择不当，或者计算出的点 
位于局部最大值或最小值处或附近，则 f'(x) 的导数为 0，我们就遇到了驻点条件。 - 如果函数的导数行为不佳，牛顿法倾向于“过冲”。此时
可能离根太远，对算法没有帮助。
割线法
在许多情况下，我们没有函数的导数，或者计算它可能过于复杂。在这种情况下，我们可以使用 割线法。该方法基本与 Newton 方法相同，但计算必需的斜率不是通过函数导数 f'(x)，而是通过使用 f(x) 计算的两个 x 和 y 值的商来完成。
割线法实现
该算法需要一个区间 [a,b]，该区间可能（不绝对必要但有帮助）包含我们正在寻找的根。它使用 calculateX() 方法，该方法不仅计算 
，还会检查分母 
是否为 0。此外，该算法也非常快，在一个选择良好的区间内只需要 7 次迭代，在一个较宽的区间内需要 10 次迭代。这两种计算都满足 
的相同收敛条件。与牛顿法一样，该算法也有一些缺点需要注意：
- 仅适用于光滑且连续的函数
- 如果计算出的某个点
位于局部最大值或最小值处或附近，则 f'(x) 的导数为 0，我们就遇到了驻点条件。 - 如果计算出的函数斜率商非常平坦，割线法也可能“过冲”。此时
可能离根太远，对算法没有帮助。 - 如果区间 [a,b] 选择不当，例如包含局部最小值和最大值，算法会趋向于振荡。总的来说，局部或全局的最小值和最大值在某些情况下对割线法来说是个问题。
Dekker 法
Dekker 法的思路是将牛顿法/割线法的速度与二分法的收敛保证相结合。算法定义如下：
是当前迭代的根的猜测值，而 
是 
的当前对应点，使得 
和 
符号相反。- 算法必须满足条件
，以便 
是最接近根的解。 
是上一次迭代的值，算法开始时 
。- 如果 s 在 m 和
之间，则 
，否则 
。 - 如果
，则 
，否则 
。
Dekker 法实现
正如我们在 Dekker 法的实现中所见，我们始终使用 calculateSecant() 和 calculateBisection() 方法计算 m 和 s 的值，并根据 useSecantMethod() 方法的确认结果来分配这些值，该方法会确认 s 是否在 m 和 
之间（如规则 4 所定义）。在第 32-33 行，我们确认函数 f(x) 的结果值是否满足规则 5。由于存在二分法，我们在每次迭代后都必须检查并纠正 $latex f(a_k)f(b_k) < 0 &s=1 &$ 的条件是否仍然满足，这通过 checkAndFixAlgorithmCriteria() 方法完成。
Dekker 算法的速度与牛顿法/割线法一样快，同时也保证了收敛。在选择良好的区间情况下需要 7 次迭代，在较宽的区间情况下需要 9 次迭代。正如我们所见，Dekker 算法非常快，但也有一些例子表明 
非常小但仍然使用了割线法。在这种情况下，算法将比纯二分法花费更多迭代。
Brent 法
由于 Dekker 法收敛速度较慢，该方法被 Brent 扩展，现在称为 Brent 法或 Brent-Dekker 法。该算法通过使用四个点（a、b、
和 
）而不是三个点，以及使用 逆二次插值而不是线性插值和二分法，以及额外的条件来防止收敛缓慢，从而扩展了 Dekker 算法。该算法根据以下条件决定使用哪种方法：二分法、割线法或逆二次插值。
- 二分法（B = 上次迭代使用了二分法）
- 逆二次插值
- 在所有其他情况下，使用割线法。
Brent 法实现
通过这些修改，Brent 算法至少和二分法一样快，但在最佳情况下比纯割线法略快。Brent 算法在选择良好的区间情况下需要 6 次迭代，在较宽的区间情况下需要 9 次迭代。
那么，选择哪种算法？
我们已经看到了五种可以用来近似函数根的算法：二分法、牛顿法、割线法、Dekker 法和 Brent 法。它们都有不同的可能性和缺点。总的来说，我们可以对选择哪种算法进行如下论述：
- 如果函数光滑且行为良好，并且您也知道函数的导数，请使用牛顿法。
- 如果函数光滑且行为良好，但您不知道函数的导数，请使用割线法。
- 如果您不确定或知道您的函数有跳跃或其他问题，请使用 Brent 法。
| 算法 | 开始/区间 | 迭代次数 |
| 二分法 | [0, 2] | 36 |
| Newton | x0 = 1.5 | 6 |
| 割线法（好） | [1.5, 2] | 7 |
| 割线法（差） | [0, 2] | 10 |
| Dekker 法（好） | [1.5, 2] | 7 |
| Dekker 法（差） | [0, 2] | 9 |
| Brent 法（好） | [1.5, 2] | 6 |
| Brent 法（差） | [0, 2] | 9 |
您喜欢这篇文章吗？
您有什么想法？您喜欢这篇文章吗？
欢迎评论和分享本文。