"which one is more accurate"

Your question is not correct. To evaluate the quality of a numerical approximation of the derivative you must evaluate first the accuracy order, therefore one can discuss only if you have a comparison between formulas of the same order of accuracy.

Moreover, the stencil is relevant (compact, central or asymmetric) in producing a specific local truncation error and the spectral resolution is a further parameter to evaluate the formula.

It is quite common to consider better a formula of higher accuracy order but in solving PDEs. that can be tricky.

Hi, numerical differentiation (finite difference methods) lead to an approximation of the derivative to a given order. With automatic differentiation you should obtain the exact derivative (if your function is differentiable) as automatic differentiation tools are based on operator overloading and differentiate each operation of your code.

Hi, in fact automatic differentiation should give the same result as a symbolic differentiation. The difference is that instead of differentiating the whole formula, automatic differentiation differentiates each line of the original code (FORTRAN, C...) ensuring a consistency between the computation of the function and that of its derivative. Of course, a closed-form of the derivative cannot be obtained as in symbolic calculation (MATHEMATICA, MAPLE).

I am not an user, I just had a search on automatic differentiation in TensorFlow

https://www.tensorflow.org/tutorials/eager/automatic_differentiation

I am sure that using symbolic differentiation in Maple will allow to get the analytical expression, I don't know if this is the same in TensorFlow. But if this is the case, I would be not sure about the real meaning of the question as it is tautological that an exact expression is better that any numerical approximation.

Thank you Dr. Richard Epenoy

I did not know the definition of automatic differentiation, so I suspect that it is also a numerical approximation of differentiation such as FD.

So if automatic differentiation gives the exact value of the derivative of a function for a specific value, as Dr. Filippo Maria Denaro said, my question is irrelevant.

as Dr. Tapan K. Sengupta

so it seems that I should compare the accuracy of two methods experimentally.

Hhhti, I agree with your last comment. Notice that if your code is in FORTRAN you can use different autamoatic differentiation tools : ADIFORhttps://www.mcs.anl.gov/research/projects/adifor/) or the equivalent French tool TAPENADE (

Sorry, this is the link for TAPENADE : https://www.sop.inria.fr/tropics/tapenade.html

Hi Ali Namadchian

Personally I do love to use complex-step instead of standard finite differences if the function is differentiable (e.g., no look-up tables), and dual-number-based differentiation if I want exact results. I'd suggest you to check out those methods as well.

I use them in optimization to approximate large Jacobian matrices.

Hi, interesting comment from Marco. Complex differentiation is also very efficient. Nevertheless, the language used has to extend all operations to the complex plane. It is the case with MATLAB for e.g. but not of all languages.

Richard Epenoy absolutely correct. I use it in Matlab, but for other languages you need to find / write a proper library.

Dear Marco Sagliano

Never studied the dual number differentiation, I now read on internet that can be related to the Taylor series so I wonder if it implies an error due to some truncation.

As far as Automatic differentiation is concerned, a simple reading is on wikipedia https://en.wikipedia.org/wiki/Automatic_differentiation

however, I am not able to comment the statements about the superiority over symbolic computation and numerical differentiation.

However, this is definitely not in my field of experience.

Hi, this technique is known as "complex step differentiation". By a Taylor series we can write

f(x + ih) = f(x) + ih f'(x) + ....

So f'(x) = Im(f(x + ih ))/h + O(h^2)

You can find more details on the web.

Hi Richard Epenoy

thanks for the answer, and yes, we come back to the original question about the comparison of the accuracy order. You highlighted the local truncation error appearence also for the complex step differentiation, the expression of this latter having an impact on the result.

I do not understand in what is superior to a FD (explicit or implicit) or a spectral derivative.

Hi, the complex step differentiation is superior to the classical one as you obtain a h^2 error only by evaluating one time the function

So, "superior" means only less computational cost? Otherwise I don't see a specific superiority...

And what about the explicit expression of such O(h^2) term?

Dear Filippo Maria Denaro

DN-differentiation does not have truncation errors. It is an exact differentiation method. It can be interpreted as some kind of automatic differentiation, because you "hide" the derivatives of elementary functions in the dual part of the number.

Please check out some work I made with my students to see more details about it.

https://elib.dlr.de/103880/1/Donofrio_2016.pdf

https://elib.dlr.de/112107/1/Sagliano_2017c.pdf

As Richard Epenoy said, complex-step directly gives you an O(h^2) error with one single (complex) evaluation of the function.

I also attached Vincenzo's Master thesis. You can see some tests we did about several differentiation techniques there.

Interesting, thanks

Dear Marco Sagliano

I am struggling with the dual number-based differentiation as one thing appears to me tricky.

Consider the Taylor expansion in the Lagrange form

f(x+a)=f(x)+a*f'(c)

that defines the exact derivative in the Lagrange point c. Of course, in terms of a classical FD derivative, we have a first order approximation of the derivative in x or x+a.

According to the dual number differentiation I would understand that you get the same "exact" expression for f'(x) and f'(c), a fact that is not possible...

What I am missing?

If we want to talk about accuracy, certainly the automatic differentiation is more accurate. But numerical derivatives and automatic derivatives have the same precision in dealing with polynomials. There are also cases that can only be treated using numerical differentiation.

Hi Filippo Maria Denaro

the trick is that if you take

f(x+eps*b)

and expand in Taylor series you get

f(x+eps*b) = f(x)+eps*f'(x)*b + 1/2*b^2*eps^2*f'"(x)

and since eps is such that eps^2 = eps^3 = eps^n = 0

you get

f(x+eps*b) = f(x) + eps*f(x)*b

so if you solve for f'(x) you get

f' (x) = Dual(f(x+eps*b)/(b)).

But this requires (as Richard Epenoy wrote) operator overloading. because you have to be able to evaluate functions in dual space (e.g., f(x+eps*b)) and to extract the dual part (when you perform Dual ( argument )).

Please check Chapter4 of the thesis I sent you.

Another excellent introduction to the topic is given by Dr. Fike (you can find details in the references of the aforementioned thesis).

I hope this helps a bit.

Hi Marco Sagliano

I understand the idea but that does not answer my doubt. Consider the Taylor series you wrote above but in the Lagrange form

f(x+eps*b) = f(x)+eps*f'(c)*b

you end up to compute f’(c) now but using the same expression of f’(x), isn‘t that?

how can be possible??

Hi Filippo Maria Denaro

I'm sorry, but I don't know what you mean by "Lagrange form". I'm talking about normal, differentiable functions.

We start from the assumption that we want to evaluate the function of f in a given "x". From there you get the different approaches according to the type of perturbation (real, complex, or dual).

Could you please explain me where does this "c" that you mention come from?

Hi Tapan K. Sengupta

thanks for your nice questions:

1) For the function shown in Fig. 2.16, the arguments on either side not same. Can you clarify also, what are the values of \omega and \lambda?

I have to look it up from archived code, so please give me some more time.

2) As you plot the x-axis in radian, does it mean that your x = \omega t?

I think there is a consistent typo in these examples, the independent variable should in this case always be t, and the evaluated derivative is df(t)/dt.

Thanks for noticing it, I didn't before.

3) In evaluating the Jacobian, you need derivatives in multiple variables, then how does one apply the complex-step derivative technique? For each derivative you define an auxilliary complex number?

Correct. You perturb each derivative independently with a complex number. So if you have, say f(x,y), you'll have df/dx by using (x+ih, y) and df/dy by using (f, y+ih).

4) On page 38, it is stated: "The only disadvantage is the need to have an analytical function, meaning that, for instance, it is not possible to apply this approximation to look-up table". If this is correct, then how does one solve the re-entry problem in chapter 6, where aerodynamic data will be given to one in tabular or graphical form? Are you implying some sort of analytic curve fit?

In the Space Shuttle example aerodynamic coefficients are continuous functions of AoA. However in other cases where only tabulated data is given I typically generate a curve fitting the data, as you said. That can be done by using multivariate polynomials whose coefficients are least-squares estimated, or by using more complicated spline-based approach. You get an error, but typically that error is rather small compared to the intrinsic uncertainty of the aerodynamic database anyway.

Marco Sagliano

The Taylor series is an exact representation fo the function in x+a when you consider the last term as the remainder. This term has the (n+1)-th derivative in a point c of the interval (x,x+a), this point being unknown (lagrangian point).

If you write the first order term (n=0) of the Taylor expansion in terms of the remainder, this is the Lagrangian form (also mean value theorem). This is a classical theory in mathematical analysis.

https://brilliant.org/wiki/taylors-theorem-with-lagrange-remainder/

https://en.wikipedia.org/wiki/Taylor%27s_theorem

Using this form, you get in to my question and doubt.

To tell the truth, not only I am struggling with my doubt about the inconsistence in comparison to the Lagrange form but (if I understad correctly the idea of the dual number), as eps is a nilpotent matrix, the argument of the Taylor expansion (x+a) is also a matrix. That involves a more complex analysis being the derivatives applied to matrix arguments (Frechét derivatives, see http://eprints.ma.man.ac.uk/2291/1/paper.pdf).

And I am quite lost in deducing the final result of an exact derivative...

Hi Filippo Maria Denaro

The one from the remainder is a very interesting perspective that I never considered, I have to admit I was not very formal in the approach.

If I get it correctly in Lagrange form you can express the remainder as product between the n+1 derivative of the function in any intermediate point c and the (c-x), which is what you wrote before. Your question is how this holds if we have n+1 = 1 for dual numbers since the remainder would imply that f'(c) = f'(b).

I might be wrong but I would suspect this is a weird property coming from the fact that in the dual space any function is "linear" (in abstract sense, due to the fact that there are no quadratic terms). I'll try to make a more formal analysis of this, I'm getting very curious about the outcome...

Concerning the nilpotent elements, yes it is correct that dual unities correspond to nilpotent matrices [0 1; 0 0], but you don't use this representation so Taylor expansion is not a matrix, in the same way that it is not a matrix if case you use a complex-step even if there is a matrix representation of the imaginary unit i = [0 -1; 1 0]. I'll check out the pdf you sent me, never heard of Frechét derivatives before, thanks!

Hi Tapan K. Sengupta

The claim of complex-step is to get rid of cancellation error due to subtraction, which does not imply that multiplication/division do not contribute to roundoff. The purpose was mainly to analyze quantitatively how getting rid of the subtraction-based error improves the quality of results for estimating numerical derivatives.

I apologize if this was not stressed enough throughout the thesis.

Hi @Tapan,

Many thanks for your suggestions. I’ll keep them in mind for the future!

Best Regards,

Marco

Hi Marco Sagliano

if the answer to the issue in the Lagrangian point is in the linearity of the term in the dual number differentiation, then the key is that this method does not provide an exact derivative...in other words, you should consider that the cancelled higher order terms has a role in terms of a numerical error.

Furthermore, I would explicit consider the matrix form of the independent variable in the Taylor series, the fact that the matrix (x+a) is hidden in your (scalar) formulation does not help to understand clearly the theory.

I think that this is a fundamental issue to be clarified as such effort can introduce a further improvement. I was thinking about an extension to such formulation for solving PDE equations.

Let me know if you proceed in this analysis.

Some new element about the issue of the real accuracy in dual number differentiation?

Dear Tapan K. Sengupta

I am discussing about the topic with one of my previous students and now independent researcher @Paolo Lampitella

https://www.cfd-online.com/Forums/main/211740-dual-number-differentiation-discussion.html

We think a truncation error is implied by the interpolant

Hi Filippo Maria Denaro and Tapan K. Sengupta

I would also be interested to understand your definition of exact, because probably mine is not very rigorous, but I was assuming as "exact" a derivative computed with DN if the difference with respect to the true derivative was in the order of the machine-epsilon.

Hi Marco Sagliano

have a read to the discussion I linked. I think that the key is that the error is implied by the adoption of a polynomial. You can derive it exactly but the truncation error is still present.

Hi Filippo Maria Denaro

I just read the thread, thanks.

Best Regards,

Marco

Please allow me to make an example that would probably clarify the issue.

Dear Marco Sagliano, if I would give you a discrete vector of values of an unknown function with constant h spacing, would the dual number approach be applicable and, if so, to what accuracy would it provide the derivative of the underlying function in the same points where the original function is given (or any other point for that matter)?

Just note that using a Lagrange interpolant for the discrete data before applying anything else to it would carry an error which is nothing else that the same error due to the use of FD of correspondent order on the raw data. This should be clear if piecewise linear interpolation is used.

Otherwise, could you clarify how the comparison tests, between the dual approach and FD, are made in the papers you linked? My understanding is that the exact derivative is built within the original definition of the function via overloaded dual numbers. That is, the exact information is already within the data you use, which are different from the FD case.

Dear Marco Sagliano

According to what Paolo Lampitella wrote, I think we should focus on the differences between the lagrangian polinomial P(x)=p0+p1*x+.... pn*x^n and the infinite Taylor expansion (or its exact lagrangian form).

Using dual number in P(x) you get

P(a+b*eps) = P(a)+b*P'(a)*eps

where P' is the analytical derivative of the polynomial you detemine via dual number differentiation. That has nothing to do with the exact derivative of the function that the polynomial approximatively interpolates. I can define "exact" FD derivatives by analytical derivation of the lagrange polynomial but such derivates have a local truncation error. This is the local truncation error that seems hidden in the discussion in the papers you posted, isn't that?

If not, honestly I am not understanding nothing about DN differentiation....

Yet, to answer the original question, let me add that, where suitable, automatic differentiation is better than finite difference.

AD "better" than FD without a term of comparison that involves accuracy?

Hi, AD is a relatively old technique now, as the first AD tool for FORTRAN codes, ADIFOR was developed during the 1990s by Argonne and Rice University:

https://www.mcs.anl.gov/research/projects/adifor/

Dear Richard Epenoy

28 years is a relatively long period in term of scientific research and DN differentiation does not seem to have reached (yet?) a large audience.

But the problem is not in the hystorical assessment, we are debating here about a simple issue, the real presence of a truncation error, and we do not reached yet a clear answer...

Hi Filippo Maria Denaro, from the mathematical point of view it is clear that the complex step differentiation is associated with a truncation error in O(h^2). Nevertheless, from the numerical point of view, it has been shown that the derivative computed with complex step differentiation is much less sensitive to the value of the step h than classical numerical differentiation (due to the fact that it is not subject to cancellation as said in the above discussions).

Hereafter a link to an interesting numerical example illustrationg this point:

https://blogs.mathworks.com/cleve/2013/10/14/complex-step-differentiation/

Dear Richard Epenoy

yes, the link you posted says explicitly the order of accuracy. Therefore the question is why the DN-differentiation does not state a truncation error and it is stated it as an "exact" derivative?

Dear Filippo Maria Denaro,

if I understand well (I am not an expert in this topic), as shown in the link given above, in DN-differentiation as there is no cancellation it is possible to choose step h very small, typically equal to 10^-8 leading to a truncation error of 10^-16 close to the machine precision (in double precision). This is why it may be possible to say that DN-differentation is "exact" numerically.

Well, this is a diffent thing and the same reasoning can be deduced for a FD derivative: a very small value of h makes the FD derivative (for the consistence property) to be "exact".

But I am not able to find any reference where it is explicitly stated that DN-differentiation has some O(h^k) truncation error....

On the other hand, that is compatible to the impossibilty to define the Taylor expansion when the function is not regular...

Well, the original question is not well posed as it puts together PDE and tensorflow. My claim of AD superiority stems from considering where AD is actually used which, let me highlight this, IS NOT DISCRETIZATION OF PDE DERIVATIVES as you might think. AD is used to track exact derivatives of known functions (not unknown discretized fields) where in theory you would be able to do it by hand. Thus the claim is just that: setting cos(x) as the derivative of sin(x) is better than using [sin(x+h)-sin(x)]/h for any practical value of h. The key to understand the claim is understanding that we know we are differentiating sin(x) and not an unknown function.

Of course, I remain skeptical of how results are presented in those papers, which (as this discussion seems to confirm) is misleading, and I'm waiting for an answer to my question.

And yes, of course, the method doesn't work if a derivative doesn't actually exist. But then, other methods also get in theoretical trouble. AD requires upfront definition of the derivative for every intrinsics, including abs, max, min, etc.

I agree Paolo, the target of the DN differentiation seems not suitable for the numerical solution of PDE. I think that the comparisons shown in the thesis between the slope of the error in FD and the absence of an error in DN differentiation was misleading

If we want, maybe, it is also a matter of information theory. A sampled unknown function with step h does not contain the information on its exact derivative at its sampling points (or any other point), no matter what. Thus, in such conditions, no method can actually get that.

I think this is not correct, a set of discrete values representing a sampling of a function allows a spectral representation up to the Nyquist frequency. That means you can recognize the derivatives of frequencies up to pi/h.

This, in general, does not correspond to the definition of exact derivative. You can get there very fast with spectral approximations, but if you know nothing about the function and how h relates to its spectral content, you are not sure

Paolo, the spectral polynomial is exact up to Nyquist (just consider that the modified wavenumber is equal to k). The only error can be due if one does the sampling at step h of a function that has a spectral content behind pi/h. But this is an error in the sampling and nothing can be done...

Can we summarize by saying that it is no better than the underlying discrete Fourier series representation?

Yes, theoretically the Fourier polynomial is the best fitting method one has to represent a continuous function from a discrete set of data.

If the function is unknown probably the best you can do is to approximate it by some polynomial,or also other class of smooth functions, in least squares or also Tchebychev sense and then use the derivative values of the approximating function.(Fourier is just one possible choice but numerically convenient due to the FFT).If you expect that your unknown function is smooth,there is nothing wrong to use finite differences with a suitable h.Finally derivatives of distributions

like abs,sign etc can be approximated using members of the transcendental functions involved in their definition via limiting processes.

I think, the real objective of AD is to compute the hessian operator, quickly and not expansive, of models (function) which are already coded. This hessian will be used in the optimisation part.

Article Automatic differentiation strategy for the local sensitivity...

If you have sampled data, and you just want the derivative, a simple two-point differentiation algorithm will produce the most accurate solution (a three point algorithm smooths fast inflection points).

Or am I missing the point...?

This is a really interesting discussion!

I'd like to contribute with a few points:

1) Filippo Maria Denaro " Well, this is a diffent thing and the same reasoning can be deduced for a FD derivative: a very small value of h makes the FD derivative (for the consistence property) to be "exact". " This is not true, numerically: if you use finite differences and plot the difference of the approximated derivative wrt the analytic derivative (take sine or cosine for instance) you'll find that the total error decreases until around 10^-8 and then increases again. There are different contributions to the total error, one is truncation and the other is due to finite precision arithmetic. The second becomes more important than the first as h tends to zero, so the choice of the "optimal" step size (minimising the total error of the derivative) is not trivial and requires knowledge of the function to be differentiated. I think the complex step derivative has the advantage over FD that the finite precision term does not impact so much the results, hence one can really use very small h. See Article New Complex-Step Derivative Approximations with Application ...

2) In general, a computer performs only elementary operations. Even innocent looking functions like sine/cosine are as far as I know computed via high order Taylor series (which are compositions of elementary functions). Thus, I think that the most consistent results would come from differentiating those polynomials directly. However, I expect that the derivatives of those polynomials will lead to a polynomial with different coefficients (and order!) than the polynomial approximation of the derivative. This kind of "duality gap" is probably intrinsic in how the functions are approximated/computed numerically.

Lorenzo A. Ricciardi

yes but the round-off error is at a level we can control by single, double or more precision. The increasing of the error you see after the threshold of the selected precision means only that you have to stop in evaluating the error.

Filippo Maria Denaro true, but I'd read this in the opposite direction: for a given precision, there's a minimum finite difference step size under which the floating point errors are larger than the truncation error. One is not always able to change the precision

I'm not sure what you mean with "after the threshold of the selected precision means only that you have to stop in evaluating the error. " The error experienced by any algorithm is the total error, one cannot simply ignore it. Practically this means that when using finite difference approximations, using a too small step (like 10^-16) can be worse results than using a larger one (like 10^-8).

See also

https://math.stackexchange.com/questions/815113/is-there-a-general-formula-for-estimating-the-step-size-h-in-numerical-different

and

Article An analytical approach to computing step sizes for finite-di...

Lorenzo A. Ricciardi

I know what you mean but you should be aware about what is the "error" we are talking about.

In your example, you are analysing the "discretization error", that is the difference between the exact function and the numerical solution. The exact function is sampled on the same grid of the numerical solution and just the sampling of the continuous function can introduce the round-off error. This is the reason we see the effect of the round-off error when h is below the chosen machine precision.

Conversely, the rigorous definition of the order of accuracy of a discrete derivative is based on the analysis of the "local truncation error" which is an analytical expression that provides infinite terms. When we discuss about the accuracy we must consider the LTE since the DE is an indirect measure of the accuracy order.

Let me restate again that, while interesting per se, the whole discussion on automatic differentiation related to PDE resolution is largely misleading, which is what OP asked about.

You can automatically differentiate a PDE solver to have adjoints, Jacobians, etc., but you can't use automatic differentiation to actually solve the PDE itself.

Thus, comparing automatic differentiation with finite differences is largely misleading and a non argument in favor of automatic differentiation with respect to finite differences (or any other numerical derivative discretization method). Because finite differences (volumes, elements) can solve PDEs, automatic differentiation can't.

Filippo Maria Denaro I agree that from the theoretical point of view the LTE is what defines order of accuracy.

However in this discussion, I think the author meant "as close as possible to the analytical ones", but the question was indeed a bit vague. Errors introduced by finite precision arithmetics are very relevant in the context of optimisation of very sensitive problems (convergence can be impaired). For the solution of PDEs the effect of finite precision on the derivatives is probably very different, but I don't have expertise in that field

Very interesting discussion indeed!

As said many times: automatic differentiation is better (by definition). Let me profit from this forum for self-promotion: statistical considerations can largely improve precision of finite-difference methods. Such method is time-consuming but presumably the most precise on the market: http://vixra.org/abs/1706.0210

Nice Contribution A. Liptaj

Specifically, automatic differentiation uses arithmetic operations such as addition multiplication, and division along with functions like log, sin, cos, and exp, and by applying the chain rule, which is essentially a way of breaking down a complex function into less complex ones, automatic differentiation is able to reduce the function to a composite of these primitives of which it can compute the derivatives and combine to get the derivative of the entire function. It does this using approximately the same amount of operations as the original function (which is a neat thing for efficiency). This way it’s also a good method of computing partial derivatives which are useful for gradient descent.

The numerical differentiation aims to approximate derivatives through the finite differentiating, but the solution quality is greatly affected by the potential truncation and round-off errors associated with different finite difference formulas. On the other hand, the automatic differentiation (AD) technique utilises the chain rule-based principle to evaluate complex derivatives analytically. Hence, it promise more precise computation of derivatives w.r.t. specified parameters through chain rules.