在 C/C++ 中实现导数

Implementing the derivative in C/C++

提问by vehomzzz

How is the derivative of a f(x)typically calculated programmatically to ensure maximum accuracy?

如何以f(x)编程方式计算通常的导数以确保最大精度？

I am implementing the Newton-Raphsonmethod, and it requires taking of the derivative of a function.

我正在实施Newton-Raphson方法，它需要取函数的导数。

回答by John D. Cook

I agree with @erikkallen that (f(x + h) - f(x - h)) / 2 * his the usual approach for numerically approximating derivatives. However, getting the right step size h is a little subtle.

我同意@erikkallen，这(f(x + h) - f(x - h)) / 2 * h是数值近似导数的常用方法。然而，获得正确的步长 h 有点微妙。

The approximation error in (f(x + h) - f(x - h)) / 2 * hdecreases as hgets smaller, which says you should take has small as possible. But as hgets smaller, the error from floating point subtraction increases since the numerator requires subtracting nearly equal numbers. If his too small, you can loose a lot of precision in the subtraction. So in practice you have to pick a not-too-small value of hthat minimizes the combination of approximationerror and numericalerror.

( 中的近似误差f(x + h) - f(x - h)) / 2 * h随着h变小而减小，这表明您应该h尽可能小。但是随着h变小，浮点减法的误差会增加，因为分子需要减去几乎相等的数字。如果h太小，您可以松开减法的精度很高。因此在实践中，您必须选择一个不太小的值，h以使近似误差和数值误差的组合最小化。

As a rule of thumb, you can try h = SQRT(DBL_EPSILON)where DBL_EPSILONis the smallest double precision number esuch that 1 + e != 1in machine precision. DBL_EPSILONis about 10^-15so you could use h = 10^-7or 10^-8.

作为一个经验法则，你可以试试h = SQRT(DBL_EPSILON)这里DBL_EPSILON是最小的双精度数e，使得1 + e != 1机器的精度。 DBL_EPSILON是关于10^-15所以你可以使用h = 10^-7or 10^-8。

For more details, see these noteson picking the step size for differential equations.

有关更多详细信息，请参阅有关为微分方程选择步长的说明。

回答by user151019

Newton_Raphson assumes that you can have two functions f(x) and its derivative f'(x). If you do not have the derivative available as a function and have to estimate the derivative from the original function then you should use another root finding algorithm.

Newton_Raphson 假设您可以有两个函数 f(x) 及其导数 f'(x)。如果您没有可用作函数的导数并且必须从原始函数估计导数，那么您应该使用另一种求根算法。

Wikipedia root findinggives several suggestions as would any numerical analysis text.

维基百科的根查找提供了一些建议，就像任何数值分析文本一样。

回答by Alexey Malistov

1) First case:

1) 第一种情况：

— relative rounding error, about 2^{-16} for double and 2^{-7} for float.

— 相对舍入误差，双精度约为 2^{-16}，浮点精度约为 2^{-7}。

We can calculate total error:

我们可以计算总误差：

Suppose that you are using double floating operation. Thus the optimal value of his 2sqrt(DBL_EPSILON/f''(x)). You do not know f''(x). But you have to estimate this value. For example, if f''(x)is about 1 then the optimal value of his 2^{-7} but if f''(x)is about 10^6 then the optimal value of his 2^{-10}!

假设您正在使用双浮动操作。因此h的最佳值为2sqrt(DBL_EPSILON/ f''(x))。你不知道f''(x)。但是你必须估计这个值。例如，如果f''(x)约为 1，则h的最佳值为2^{-7} 但如果f''(x)约为 10^6，则h的最佳值为2^{- 10}！

2) Second case:

2）第二种情况：

Note that second approximation error tends to 0 faster than first one. But if f'''(x) is very lagre then first option is more preferable:

请注意，第二个近似误差趋于 0 比第一个快。但是如果 f'''(x) 非常大，那么第一个选项更可取：

Note that in the first case h is proportional to e but in the second case h is proportional to e^{1/3}. For double floating operations e^{1/3} is 2^{-5} or 2^{-6}. (I suppose that f'''(x) is about 1).

请注意，在第一种情况下 h 与 e 成正比，但在第二种情况下 h 与 e^{1/3} 成正比。对于双浮点运算，e^{1/3} 是 2^{-5} 或 2^{-6}。（我想 f'''(x) 大约是 1）。

---

---

Which way is better?It is unkown if you do not know f''(x) and f'''(x) or you can not estimate these values. It is believed that the second option is preferable. But if you know that f'''(x) is very large use first one.

哪种方式更好？如果您不知道 f''(x) 和 f'''(x) 或者您无法估计这些值，则是未知的。相信第二种选择更可取。但是如果您知道 f'''(x) 非常大，请使用第一个。

What is the optimal value of h?Suppose that f''(x) and f'''(x) are about 1. Also assume that we use double floating operations. Then in the first case h is about 2^{-8}, in the first case h is about 2^{-5}. Correct this values if you know f''(x) or f'''(x).

h 的最佳值是多少？假设 f''(x) 和 f'''(x) 大约为 1。还假设我们使用双浮点运算。那么在第一种情况下 h 大约是 2^{-8}，在第一种情况下 h 大约是 2^{-5}。如果您知道 f''(x) 或 f'''(x)，请更正此值。

回答by MikeT

You definitely want to take into account John Cook's suggestion for picking h, but you typically don't want to use a centered difference to approximate the derivative. The main reason is that it costs an extra function evaluation, if you use a forward difference, ie,

您肯定要考虑约翰库克关于选择 h 的建议，但您通常不想使用居中差异来近似导数。主要原因是它需要额外的函数评估，如果你使用前向差分，即，

f'(x) = (f(x+h) - f(x))/h

Then you'll get value of f(x) for free because you need to compute it already for Newton's method. This isn't such a big deal when you have a scalar equation, but if x is a vector, then f'(x) is a matrix (the Jacobian), and you'll need to do n extra function evaluations to approximate it using the centered difference approach.

然后您将免费获得 f(x) 的值，因为您需要已经为牛顿方法计算它。当你有一个标量方程时，这没什么大不了的，但是如果 x 是一个向量，那么 f'(x) 是一个矩阵（雅可比矩阵），你需要做 n 个额外的函数评估来近似它使用中心差分法。

回答by erikkallen

fprime(x) = (f(x+dx) - f(x-dx)) / (2*dx)

for some small dx.

对于一些小的 dx。

回答by sellibitze

What do you know about f(x)? If you only have f as a black box the only thing you can do is to numerically approximate the derivative. But the accuracy is usually not that good.

你对 f(x) 了解多少？如果你只有 f 作为一个黑盒子，你唯一能做的就是在数值上近似导数。但精度通常不是那么好。

You can do muchbetter if you can touch the code that computes f. Try "automatic differentiation". There some nice libraries for that available. With a bit of library magic you can convert your function easily to something that computes the derivative automatically. For a simple C++ example, see the source code in thisGerman discussion.

你可以做很多更好，如果你可以触摸的代码，计算F。试试“自动微分”。有一些不错的库可用。借助一些库魔法，您可以轻松地将您的函数转换为自动计算导数的函数。有关简单的 C++ 示例，请参阅此德语讨论中的源代码。

回答by Rickard

In addition to John D. Cooks answer above it is important not only to take into account the floating point precision, but also the robustness of the function f(x). For instance, in finance, it is a common case that f(x) is actually a Monte Carlo-simulation and the value of f(x) has some noise. Using a very small step size can in these cases severely degrade the accuracy of the derivative.

除了上面的 John D. Cooks 回答之外，重要的是不仅要考虑浮点精度，还要考虑函数 f(x) 的稳健性。例如，在金融领域，f(x) 实际上是 Monte Carlo 模拟并且 f(x) 的值有一些噪音是一种常见的情况。在这些情况下，使用非常小的步长会严重降低导数的精度。

回答by Paul

Typically signal noise impacts the derivative quality more that anything else. If you do have noise in your f(x), Savtizky-Golay is a excellent smoothing algorithm that is often used to compute good derivatives. In a nutshell, SG fits a polynomial locally to your data, the then this polynomial can be used to compute the derivative.

通常，信号噪声对衍生质量的影响比其他任何因素都大。如果 f(x) 中确实存在噪声，Savtizky-Golay 是一种出色的平滑算法，通常用于计算良好的导数。简而言之，SG 在本地将多项式拟合到您的数据中，然后该多项式可用于计算导数。

Paul

保罗