正向自动，数值与符号微分的计算效率 [英] Computational Efficiency of Forward Mode Automatic vs Numeric vs Symbolic Differentiation

问题描述

我正在尝试解决使用C语言中的Newton-Raphson(NR)方法查找函数根的问题.我想找到根的函数主要是多项式函数，但也可能包含三角函数和对数函数.

I am trying to solve a problem of finding the roots of a function using the Newton-Raphson (NR) method in the C language. The functions in which I would like to find the roots are mostly polynomial functions but may also contain trigonometric and logarithmic.

NR方法需要找到函数的微分.实施差异化的方法有3种:

The NR method requires finding the differential of the function. There are 3 ways to implement differentiation:

• 符号
• 数字
• 自动(子类型为正向模式和反向模式.对于这个特定问题，我想重点介绍正向模式)

我有成千上万个这样的功能，所有这些功能都需要在最快的时间内找到根.

I have thousands of these functions all requiring finding roots in the quickest time possible.

据我所知，自动区分通常比符号区分更快，因为它可以更有效地处理表达膨胀"的问题.

From the little that I do know, Automatic differentiation is in general quicker than symbolic because it handles the problem of "expression swell" alot more efficiently.

因此，我的问题是，在所有其他条件都相同的情况下，哪种微分方法在计算上更有效:自动微分(更具体地说是前向模式)还是数字微分?

My question therefore is, all other things being equal, which method of differentiation is more computationally efficient: Automatic Differentiation (and more specifically, forward mode) or Numeric differentiation?

推荐答案

如果您的函数确实是所有多项式，则符号导数很简单.假设多项式的系数存储在具有条目p[k] = a_k的数组中，其中索引k对应于x ^ k的系数，则导数由具有条目dp[k] = (k+1) p[k+1]的数组表示.对于多元多项式，这可以直接扩展到多维数组.如果您的多项式不是标准形式，例如如果它们包含诸如(x-a)^2或((x-a)^2-b)^3之类的术语，则需要做一些工作才能将它们转换为标准格式，但这仍然是您应该做的事情.

If your functions are truly all polynomials, then symbolic derivatives are dirt simple. Letting the coefficients of the polynomial be stored in an array with entries p[k] = a_k, where index k corresponds to the coefficient of x^k, then the derivative is represented by the array with entries dp[k] = (k+1) p[k+1]. For multivariable polynomial, this extends straightforwardly to multidimensional arrays. If your polynomials are not in standard form, e.g. if they include terms like (x-a)^2 or ((x-a)^2-b)^3 or whatever, a little bit of work is needed to transform them into standard form, but this is something you probably should be doing anyways.

这篇关于正向自动，数值与符号微分的计算效率的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！