Automatic differentiation
|
|
In mathematics and computer algebra, automatic differentiation is a method to evaluate the derivative of a function, at a given point. Two classical ways of doing this are:
- symbolically differentiate the function and evaluate it in the point; or
- use finite differences.
The drawback with symbolic differentiation is low speed. Many functions grow too complex as higher derivatives are calculated. Two important drawbacks with finite differences are round-off errors in the discretization process, and cancellation. Thus both classical methods have problems with calculating higher derivatives, where the complexity and errors increase. Automatic differentiation solves all of the mentioned problems and is easily implemented on computers.
| Contents |
First-order automatic differentiation
A new arithmetic is introduced using ordered pairs as objects. The new arithmetic uses ordinary arithmetic on the first element of the pair and a first order differentiation arithmetic applying the chain rule on the second element. The basic arithmetic operations and some standard functions are defined by
- <math>\left(u,u'\right)+\left(v,v'\right)=\left(u+v, u'+v' \right)<math>
- <math>\left(u,u'\right)-\left(v,v'\right)=\left(u-v, u'-v' \right)<math>
- <math>\left(u,u'\right)*\left(v,v'\right)=\left( u v, u'v+uv' \right)<math>
- <math>\left(u,u'\right)/\left(v,v'\right)=\left( \frac{u}{v}, \frac{u'v-uv'}{v^2} \right)\quad \left(v\ne 0\right)<math>
- <math>\sin\left(u,u'\right)=\left(\sin\left(u\right),u'\cos\left(u\right)\right)<math>
- <math>\cos\left(u,u'\right)=\left(\cos\left(u\right),-u'\sin\left(u\right)\right)<math>
- <math>e^{\left(u,u'\right)}=\left(e^u,u'e^u\right)<math>
- <math>\log\left(u,u'\right)=\left(\log\left(u\right),u'/u\right)\quad \left(u>0\right)<math>
- <math>\left(u,u'\right)^k=\left(u^k,ku^{k-1}u'\right)\quad \left(u\ne 0\right)<math>
- <math>\left|\left(u,u'\right)\right|=\left(\left|u\right|,u'\mbox{sign}\left(u\right)\right)\quad \left(u\ne 0\right).<math>
The derivative of a function <math>f\left( x \right)<math> at the point <math>x_0<math> is now calculated by substituting <math>x_0<math> by the ordered pair <math>\left(x_0,1\right)<math> in the expression for <math>f\left( x \right)<math>. A constant c is substituted by <math>\left(c,0\right)<math>. Calculating <math>f'\left( x_0 \right) <math> using the above arithmetic gives <math>\left( f \left( x_0 \right), f' \left( x_0 \right) \right) <math> as the answer.
Higher order automatic differentiation
The above arithmetic can be generalized, in the natural way, to second order and higher derivatives. However, the arithmetic rules quickly grow very complicated. Instead, truncated Taylor series arithmetic is used. This is possible because the Taylor summands in a Taylor series of a function are products of known coefficients and derivatives of the function.
Software
There are plenty of libraries for automatic differentiation.
See also
External link
An "entry site to everything you want to know about automatic differentiation" (http://www.autodiff.org/)