AD and Numerical Methods in a Nutshell

AD for Numerical Methods

For example, let the square root of p be computed as the root of y=f(x(p),p)=x*x-p using the Newton-Raphson method for a given starting value of x and an upper bound eps on the residual as

while (|y|>eps)   x+=y/y'

The method requires the derivative y'=fx of f with respect to x. AD can transform the given implementation of f as a computer program into a tangent


and/or an adjoint


program. Setting x_t=1, p_t=0 yields y_t=y'=2*x. Similarly, setting y_a=1 results in x_a=y'=2*x. 

In general, f might come as a much more complicated computer program. AD works as well!


AD of Numerical Methods

Suppose that we are interested in the derivative xp of the root x of f with respect to p. We could apply AD to the implementation of the Newton-Raphson method. Preferrably, we should simply differentiate f with respect to p yielding 


at the root and hence 


Similar ideas can be exploited in many more general situations.