比较Python中的根查找(函数)算法

Question

我想比较在python中找到函数根的不同方法(如牛顿方法或其他简单的基于calc的方法).我不认为编写算法会有太多麻烦.什么是进行实际比较的好方法？我读了一下Big-O.这会是要走的路吗？

(任何项目的想法或曲折也将不胜感激)

谢谢.

Answer 1

来自@sarnold的答案是对的 - 做一个Big-Oh分析是没有意义的.

根查找算法之间的主要区别是:

• 收敛速度(迭代次数)
• 每次迭代的计算工作量
• 什么是输入所需(即你需要知道一阶导数,你需要设置二分的低/低限制等)
• 它运行良好的功能(即在多项式上工作正常但在极点函数上失效)
• 它对函数做出了什么假设(即连续的一阶导数或分析等)
• 该方法实施起来有多简单

我想你会发现每种方法都有一些好的品质,一些不好的品质,以及一系列最合适的选择.

Answer 2

大 O 表示法非常适合表达算法的渐近行为，因为算法的输入“增加”。对于寻根算法来说，这可能不是一个很好的措施。

\n\n

相反，我认为使实际误差低于某个 epsilon \xce\xb5 所需的迭代次数将是更好的衡量标准。另一个衡量标准是使连续迭代之间的差异低于某个 epsilon \xce\xb5 所需的迭代次数。（如果您手头没有输入的精确根值，连续迭代之间的差异可能是更好的选择。您可以使用连续差异等标准来了解实践中何时终止根查找器，因此您可以或者也应该在这里使用它们。）

\n\n

虽然您可以通过不同算法之间的比率来表征不同算法所需的迭代次数（一种算法可能需要大约十倍的迭代才能达到与另一种算法相同的精度），但作为输入的迭代通常不会“增长”改变。

\n\n

当然，如果您的算法使用“更大”的输入进行更多迭代，那么大 O 表示法就有意义。

\n