%  AmS-TeX file for notes for Fall, 1989 Undergraduate Numerical
%  Analysis -- automatic differentiation.
%
%\input{amstex}
\documentstyle{amsppt}
\parindent=22pt
%
\magnification\magstep1

\centerline{\sl Math. 455-01}
\centerline{\sl Spring, 1992}
\centerline{\sl R. B. Kearfott}
\bigskip
\centerline{\bf Elements of Automatic Differentiation}
\medskip
{\it Automatic Differentiation} is a procedure for simultaneously
computing values of both a function and its derivatives.  It differs
from {\it symbolic differentiation}, in which the computer
produces a symbolic expression for derivatives.  However, though
automatic differentiation gives numerical values for both the
function value and its derivative or derivatives, it does not
involve any truncation error, as in numerical differentiation.

The idea behind automatic differentiation is definition of the
operations underlying function evaluation on {\it ordered pairs}
$[u,u']$, instead of just on real numbers $u$.  The automatic
differentiaton then proceeds by performing these operations
in the order that would have been done had the function been evaluated
in real arithmetic.

Rules for the four elementary operations are

$$\align
[u,u']+[v,v'] &= [u+v,u'+v'], \tag{1}\\
[u,u']-[v,v'] &= [u-v,u'-v'], \tag{2}\\
[u,u']\cdot[v,v'] &= [u v, u v' + v u']\tag{3} \\
[u,u']/[v,v'] &= [u / v, (u' v - u v')/{v}^2] \tag{4}.\\
\endalign$$

We also have rules such as
$$\align
\sin\left([u,u']\right) &= [\sin u, u'\cos u],\tag{5} \\
{[u,u']}^2 &= [u^2, 2u u'], \tag{6}\\
{[u,u']}^3 &= [u^3, 3u^2 u'],\tag{7}
\endalign$$
etc.

With these rules, we may evaluate, for example, $f(x)$ and
$f'(x)$ at $x = 1$, where
$$f(x) = {\left[\sin\left(\pi x^3\right)\right]}^2.$$
We obtain

$$[x,1] \rightarrow {[x,1]}^3 = [x^3,3x^2] = [1,3],$$
$$[1,3] \rightarrow \pi [1,3] = [\pi, 3 \pi],$$
$$[\pi,3\pi] \to \sin\left([\pi,3pi]\right) = [\sin \pi, 3\pi\cos \pi]
= [0,-3\pi],$$
$$[0,-3\pi] \to {[0,-3\pi]}^2 = [0, 2\cdot0\cdot(-3\pi)] = [0,0].$$

Above, we identified $\pi$ with a constant whose derivative was
zero, so that we used \thetag{3} to get $\pi [1,3] = [\pi, 3 \pi]$.

Note that symbolic differentiation (by human or by machine) gives
$$f'(x) = 2 \left[\sin(\pi x^3)\right] \cos(\pi x^3) \pi (3x^2),$$
which evaluates to $0$.

Generally, we would have subroutines to do the operations
in \thetag{1} through \thetag{7}.  For example, we would have
subroutines
\medskip
\item{(1)} \qquad SUBROUTINE ADD(U,UP,V,VP,R,RP),
\item{(2)} \qquad SUBROUTINE SUB(U,UP,V,VP,R,RP),
\item{(3)} \qquad SUBROUTINE MULT(U,UP,V,VP,R,RP),
\item{(4)} \qquad SUBROUTINE DIV(U,UP,V,VP,R,RP),
\item{(5)} \qquad SUBROUTINE SIN(U,UP,R,RP),
\item{(6)} \qquad SUBROUTINE SQR(U,UP,R,RP),  and
\item{(7)} \qquad SUBROUTINE CUB(U,UP,R,RP).
\medskip

Let us assume that the above subroutines are ``safe'' in the sense
that we may duplicate variables as both input arguments and output
arguments (e.g. CALL CUB(R,RP,R,RP)).
If we were programming them, we could certainly
arrange this by storing the input arguments in temporary variables
upon entry, and using those values in computing the output variables.
Evaluation of $f$ as above could then proceed by the following
lines.

\medskip
\vbox{
\item{}\qquad U = 1
\item{}\qquad UP = 1
\item{}\qquad CALL CUB(U,UP,R,RP)
\item{}\qquad V = 4.*ATAN(1.)
\item{}\qquad VP = 0.
\item{}\qquad CALL MULT(V,VP,R,RP,R,RP)
\item{}\qquad CALL SIN(R,RP,R,RP)
\item{}\qquad CALL SQR(R,RP,R,RP)
}
\medskip

Some computer languages (such as Pascal-SC, C++, Fortran-SC, or
Fortran-8X) allow {\it operator overlaying}.  In those languages,
we may define a new datatype consisting of pairs of the form
$[u,u']$, and we may define the operations on that datatype in terms
of the subroutine package we supply.  When the compiler then
encounters an operation with one or more of the new datatypes, it
translates it to a call to a subroutine from our package.  Writing
a program to automatically differentiate a function thus becomes as
simple as writing a program to evaluate the function itself.

\proclaim{Exercises}
\item{1.}Write automatic differentiation subroutines,
as described above, for addition, subtraction, multiplication, and
division.  Make them ``safe'' but efficient.
\item{2.}Write a subroutine, which uses your routines, to evaluate
$f$ and $f'$, where
$$f(x) = 1 + 3x - x(x-1) + \frac{2}{3} x(x-1)(x-2).$$
\item{3.} Use your subroutine to evaluate the $f$ and its derivative
at
$$x_i = (i-1) h,\quad 1 \le i \le n+1,\quad h = 1/n, n=100.$$
\endproclaim
\enddocument



