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

y_t=f_t(x,x_t,p_t)=2*x*x_t-p_t

and/or an adjoint

x_a=f_a(x,y_a)=2*x*y_a

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 

fx*xp+fp=0

at the root and hence 

xp=-fp/fx=-1/(2*x).

Similar ideas can be exploited in many more general situations.