$Id: exp_eps.omh 2506 2012-10-24 19:36:49Z bradbell $
----------------------------------------------------------------------------
CppAD: C++ Algorithmic Differentiation: Copyright (C) 2003-12 Bradley M. Bell

CppAD is distributed under multiple licenses. This distribution is under
the terms of the 
                    Eclipse Public License Version 1.0.

A copy of this license is included in the COPYING file of this distribution.
Please visit http://www.coin-or.org/CppAD/ for information on other licenses.
-----------------------------------------------------------------------------
$begin exp_eps.hpp$$
$spell
	exp_eps
$$

$section exp_eps: Implementation$$
$index implementation, exp_eps$$
$index exp_eps, implementation$$

$code
$verbatim%introduction/exp_apx/exp_eps.hpp%0%// BEGIN C++%// END C++%$$
$$

$end
-----------------------------------------------------------------------------
$begin exp_eps.cpp$$
$spell
	exp_eps
$$

$section exp_eps: Test of exp_eps$$
$index test, exp_eps$$
$index exp_eps, test$$

$code
$verbatim%introduction/exp_apx/exp_eps.cpp%0%// BEGIN C++%// END C++%$$
$$

$end
-----------------------------------------------------------------------------
$begin exp_eps_for0$$
$spell
	cpp
	exp_eps_seq
	bool
$$

$section exp_eps: Operation Sequence and Zero Order Forward Sweep$$

$index exp_eps, operation sequence$$
$index example, operation sequence$$
$index operation, sequence example$$
$index sequence, example operation$$

$index zero, order forward$$
$index order, zero forward$$
$index forward, zero order$$

$head Mathematical Form$$
Suppose that we use the algorithm $cref exp_eps.hpp$$
to compute $codei%exp_eps(%x%, %epsilon%)%$$
with $icode x$$ is equal to .5
and $icode epsilon$$ is equal to .2. 
For this case, 
the mathematical form for the operation sequence 
corresponding to the $code exp_eps$$ is
$latex \[
	f( x , \varepsilon ) = 1 + x + x^2 / 2  
\] $$
Note that, for these particular values of $icode x$$ and $icode epsilon$$,
this is the same as the mathematical form for
$cref/exp_2/exp_2_for0/Mathematical Form/$$.


$head Operation Sequence$$
We consider the 
$cref/operation sequence/glossary/Operation/Sequence/$$
corresponding to the algorithm $cref exp_eps.hpp$$
with the argument $icode x$$ is equal to .5
and $icode epsilon$$ is equal to .2. 

$subhead Variable$$
We refer to values that depend on the input variables
$icode x$$ and $icode epsilon$$ as variables.

$subhead Parameter$$
We refer to values that do not depend on the input variables
$icode x$$ or $icode epsilon$$ as parameters.
Operations where the result is a parameter are not included
in the zero order sweep below.


$subhead Index$$
The Index column contains the index in the operation sequence
of the corresponding atomic operation and variable. 
A Forward sweep starts with the first operation 
and ends with the last.

$subhead Code$$
The Code column contains the C++ source code corresponding 
to the corresponding atomic operation in the sequence. 

$subhead Operation$$
The Operation column contains the 
mathematical function corresponding to each atomic operation in the sequence.

$subhead Zero Order$$
The Zero Order column contains the 
$cref/zero order derivative/exp_2_for0/Zero Order Expansion/$$
for the corresponding variable in the operation sequence.
Forward mode refers to the fact that
these coefficients are computed in the same order as the original algorithm;
i.e., in order of increasing index.


$subhead Sweep$$
$center
$table
$bold Index$$
	$cnext $pre  $$ $cnext $bold Code$$ 
	$cnext $pre  $$ $cnext $bold Operation$$
	$cnext $pre  $$ $cnext $bold Zero Order$$
$rnext
1
	$cnext $pre  $$ $cnext $code abs_x = x;$$
	$cnext $cnext $latex v_1 = x $$
	$cnext $cnext $latex v_1^{(0)} = 0.5$$
$rnext
2
	$cnext $pre  $$ $cnext $code temp  = term * abs_x;$$
	$cnext $cnext $latex v_2 = 1 * v_1 $$
	$cnext $cnext $latex v_2^{(0)} = 0.5$$
$rnext
3
	$cnext $pre  $$ $cnext $code term = temp / Type(k);$$
	$cnext $cnext $latex v_3 = v_2 / 1$$
	$cnext $cnext $latex v_3^{(0)} = 0.5$$
$rnext
4
	$cnext $pre  $$ $cnext $code sum  = sum + term;$$
	$cnext $cnext $latex v_4 = 1 + v_3 $$
	$cnext $cnext $latex v_4^{(0)} = 1.5$$
$rnext
5
	$cnext $pre  $$ $cnext  $code temp  = term * abs_x;$$
	$cnext $cnext $latex v_5 = v_3 * v_1 $$
	$cnext $cnext $latex v_5^{(0)} = 0.25$$
$rnext
6
	$cnext $pre  $$ $cnext $code term = temp / Type(k);$$
	$cnext $cnext $latex v_6 = v_5 / 2$$
	$cnext $cnext $latex v_6^{(0)} = 0.125$$
$rnext
7
	$cnext $pre  $$ $cnext $code sum  = sum + term;$$
	$cnext $cnext $latex v_7 = v_4 + v_6 $$
	$cnext $cnext $latex v_7^{(0)} = 1.625$$
$tend
$$

$head Return Value$$
The return value for this case is
$latex \[
	1.625 =
	v_7^{(0)} =
	f ( x^{(0)} , \varepsilon^{(0)} )
\] $$

$head Comparisons$$
If $icode x$$ were negative,
or if $icode epsilon$$ were a much smaller or much larger value,
the results of the following comparisons could be different:
$codep
	if( Type(0) > x ) 
	while(term > epsilon)
$$
This in turn would result in a different operation sequence.
Thus the operation sequence above only corresponds to 
$cref exp_eps.hpp$$
for values of $icode x$$ and $icode epsilon$$ within a certain range.
Note that there is a neighborhood
of $latex x = 0.5$$ for which the comparisons would have the 
same result and hence the operation sequence would be the same.

$children%
	introduction/exp_apx/exp_eps_for0.cpp
%$$

$head Verification$$
The file $cref exp_eps_for0.cpp$$ contains a routine 
that verifies the values computed above.
It returns true for success and false for failure.

$head Exercises$$
$list number$$
Suppose that $latex x^{(0)} = .1$$,
what is the result of a zero order forward sweep for 
the operation sequence above; 
i.e., what are the corresponding values for
$latex v_1^{(0)} , v_2^{(0)} , \ldots , v_7^{(0)}$$.
$lnext
Create a modified version of 
$cref exp_eps_for0.cpp$$ that verifies the values you obtained
for the previous exercise.
$lnext
Create and run a main program that reports the result of calling 
the modified version 
of $cref exp_eps_for0.cpp$$ in the previous exercise.
$lend

$end
-----------------------------------------------------------------------------
$begin exp_eps_for1$$
$spell
	exp_eps_for
$$

$section exp_eps: First Order Forward Sweep$$

$index first, order forward$$
$index order, first forward$$
$index forward, first order$$


$head First Order Expansion$$
$index first, order expansion$$
$index order, first expansion$$
$index expansion, first order$$
We define $latex x(t)$$ and $latex \varepsilon(t) ]$$ near $latex t = 0$$ 
by the first order expansions
$latex \[
\begin{array}{rcl}
	x(t) & = & x^{(0)} + x^{(1)} * t 
	\\
	\varepsilon(t) & = & \varepsilon^{(0)} + \varepsilon^{(1)} * t
\end{array}
\]$$
It follows that $latex x^{(0)}$$ ($latex \varepsilon^{(0)}$$) is the zero,
and $latex x^{(1)}$$  ($latex \varepsilon^{(1)}$$) the first,
order derivative of $latex x(t)$$
at $latex t = 0$$ ($latex \varepsilon (t)$$)
at $latex t = 0$$.

$head Mathematical Form$$
Suppose that we use the algorithm $cref exp_eps.hpp$$
to compute $codei%exp_eps(%x%, %epsilon%)%$$
with $icode x$$ is equal to .5
and $icode epsilon$$ is equal to .2. 
For this case, the mathematical function for the operation sequence
corresponding to $code exp_eps$$ is
$latex \[
f ( x , \varepsilon ) =   1 + x + x^2 / 2  
\] $$
The corresponding partial derivative with respect to $latex x$$,
and the value of the derivative, are
$latex \[
\partial_x f ( x , \varepsilon ) =   1 + x  = 1.5
\] $$

$head Operation Sequence$$

$subhead Index$$
The Index column contains the index in the operation sequence
of the corresponding atomic operation. 
A Forward sweep starts with the first operation 
and ends with the last.

$subhead Operation$$
The Operation column contains the 
mathematical function corresponding to each atomic operation in the sequence.

$subhead Zero Order$$
The Zero Order column contains the zero order derivatives
for the corresponding variable in the operation sequence
(see $cref/zero order sweep/exp_2_for1/Operation Sequence/Sweep/$$).

$subhead Derivative$$
The Derivative column contains the
mathematical function corresponding to the derivative
with respect to $latex t$$,
at $latex t = 0$$, for each variable in the sequence.

$subhead First Order$$
The First Order column contains the first order derivatives
for the corresponding variable in the operation sequence; i.e.,
$latex \[
	v_j (t) = v_j^{(0)} + v_j^{(1)} t
\] $$
We use $latex x^{(1)} = 1$$ and $latex \varepsilon^{(1)} = 0$$,
so that differentiation with respect to $latex t$$,
at $latex t = 0$$, 
is the same partial differentiation with respect to $latex x$$ 
at $latex x = x^{(0)}$$.


$subhead Sweep$$

$center
$table
$bold Index$$
	$cnext $pre  $$ $cnext $bold Operation$$ 
	$cnext $pre  $$ $cnext $bold Zero Order$$
	$cnext $pre  $$ $cnext $bold Derivative$$
	$cnext $pre  $$ $cnext $bold First Order$$
$rnext
1
	$cnext $pre  $$ $cnext $latex v_1 = x $$
	$cnext $cnext 0.5
	$cnext $cnext 
	$latex v_1^{(1)} = x^{(1)}  $$
	$cnext $cnext  $latex v_1^{(1)} = 1$$
$rnext
2
	$cnext $pre  $$ $cnext $latex v_2 = 1 * v_1$$
	$cnext $cnext 0.5
	$cnext $cnext 
	$latex v_2^{(1)} = 1 * v_1^{(1)}$$
	$cnext $cnext $latex v_2^{(1)} = 1$$
$rnext
3
	$cnext $pre  $$ $cnext $latex v_3 = v_2 / 1$$
	$cnext $cnext 0.5
	$cnext $cnext 
	$latex v_3^{(1)} = v_2^{(1)} / 1$$
	$cnext $cnext $latex v_3^{(1)} = 1$$
$rnext
4
	$cnext $pre  $$ $cnext $latex v_4 = 1 + v_3$$
	$cnext $cnext 1.5
	$cnext $cnext 
	$latex v_4^{(1)} = v_3^{(1)} $$
	$cnext $cnext $latex v_4^{(1)} = 1$$
$rnext
5
	$cnext $pre  $$ $cnext $latex v_5 = v_3 * v_1$$
	$cnext $cnext 0.25
	$cnext $cnext 
	$latex v_5^{(1)} = v_3^{(1)} * v_1^{(0)} + v_3^{(0)} * v_1^{(1)}$$
	$cnext $cnext $latex v_5^{(1)} = 1$$
$rnext
6
	$cnext $pre  $$ $cnext $latex v_6 = v_5 / 2$$
	$cnext $cnext 0.125
	$cnext $cnext 
	$latex v_6^{(1)} = v_5^{(1)} / 2$$
	$cnext $cnext $latex v_6^{(1)} = 0.5$$
$rnext
7
	$cnext $pre  $$ $cnext $latex v_7 = v_4 + v_6$$
	$cnext $cnext 1.625
	$cnext $cnext 
	$latex  v_7^{(1)} = v_4^{(1)} + v_6^{(1)}$$
	$cnext $cnext $latex  v_7^{(1)} = 1.5$$
$tend
$$

$head Return Value$$
The derivative of the return value for this case is
$latex \[
\begin{array}{rcl}
1.5 
& = & 
v_7^{(1)} =
\left[ \D{v_7}{t} \right]_{t=0} =
\left[ \D{}{t} f( x^{(0)} + x^{(1)} * t , \varepsilon^{(0)} ) \right]_{t=0}
\\
& = &
\partial_x f ( x^{(0)} , \varepsilon^{(0)} ) * x^{(1)} = 
\partial_x f ( x^{(0)} , \varepsilon^{(0)} )
\end{array}
\] $$
(We have used the fact that 
$latex x^{(1)} = 1$$ and $latex \varepsilon^{(1)} = 0$$.)

$children%
	introduction/exp_apx/exp_eps_for1.cpp
%$$

$head Verification$$
The file $cref exp_eps_for1.cpp$$ contains a routine 
that verifies the values computed above.
It returns true for success and false for failure.

$head Exercises$$
$list number$$
Suppose that $latex x = .1$$,
what are the results of a zero and first order forward mode sweep for 
the operation sequence above; 
i.e., what are the corresponding values for
$latex v_1^{(0)}, v_2^{(0)}, \cdots , v_7^{(0)}$$ and
$latex v_1^{(1)}, v_2^{(1)}, \cdots , v_7^{(1)}$$ ?
$lnext
Create a modified version of $cref exp_eps_for1.cpp$$ that verifies 
the derivative values from the previous exercise.
Also create and run a main program that reports the result
of calling the modified version of
$cref exp_eps_for1.cpp$$.
$lnext
Suppose that $latex x = .1$$ and $latex \epsilon = .2$$,
what is the operation sequence corresponding to 
$codei%
	exp_eps(%x%, %epsilon%)
%$$
$lend

$end
-----------------------------------------------------------------------------
$begin exp_eps_rev1$$
$spell
	exp_eps_rev
$$

$section exp_eps: First Order Reverse Sweep$$

$index exp_eps, reverse mode$$
$index example, reverse mode$$
$index reverse, mode example$$
$index mode, reverse example$$

$index first, order reverse$$
$index order, first reverse$$
$index reverse, first order$$

$head Purpose$$
First order reverse mode uses the 
$cref/operation sequence/exp_eps_for0/Operation Sequence/$$,
and zero order forward sweep values,
to compute the first order derivative
of one dependent variable with respect to all the independent variables. 
The computations are done in reverse 
of the order of the computations in the original algorithm.

$head Mathematical Form$$
Suppose that we use the algorithm $cref exp_eps.hpp$$
to compute $codei%exp_eps(%x%, %epsilon%)%$$
with $icode x$$ is equal to .5
and $icode epsilon$$ is equal to .2. 
For this case, the mathematical function for the operation sequence
corresponding to $code exp_eps$$ is
$latex \[
f ( x , \varepsilon ) =   1 + x + x^2 / 2  
\] $$
The corresponding partial derivatives,
and the value of the derivatives, are
$latex \[
\begin{array}{rcl}
\partial_x f ( x , \varepsilon ) & = &  1 + x  = 1.5
\\
\partial_\varepsilon f ( x , \varepsilon ) & = &  0
\end{array}
\] $$

$head epsilon$$
Since $latex \varepsilon$$ is an independent variable,
it could included as an argument to all of the
$latex f_j$$ functions below.
The result would be that all the partials with respect to 
$latex \varepsilon$$ would be zero and hence we drop it to simplify
the presentation.

$head f_7$$
In reverse mode we choose one dependent variable and
compute its derivative with respect to all the independent variables.
For our example, we chose the value returned by $cref exp_eps.hpp$$
which is $latex v_7$$.
We begin with the function $latex f_7$$ where $latex v_7$$ 
is both an argument and the value of the function; i.e.,
$latex \[
\begin{array}{rcl}
f_7 ( v_1 , v_2 , v_3 , v_4 , v_5 , v_6 , v_7 ) & = & v_7 
\\
\D{f_7}{v_7} & = & 1
\end{array}
\] $$
All the other partial derivatives of $latex f_7$$ are zero.

$head Index 7: f_6$$
The last operation has index 7, 
$latex \[
	v_7 =   v_4 + v_6  
\] $$
We define the function 
$latex f_6 ( v_1 , v_2 , v_3 , v_4 , v_5 , v_6 ) $$
as equal to $latex f_7$$
except that $latex v_7$$ is eliminated using 
this operation; i.e.
$latex \[
f_6  = 
f_7 [ v_1 , v_2 , v_3 , v_4 , v_5 , v_6 , v_7 ( v_4 , v_6 ) ]
\] $$
It follows that 
$latex \[
\begin{array}{rcll}
\D{f_6}{v_4} 
& = & \D{f_7}{v_4} + 
	\D{f_7}{v_7} * \D{v_7}{v_4} 
& = 1
\\
\D{f_6}{v_6} 
& = & \D{f_7}{v_6} + 
	\D{f_7}{v_7} * \D{v_7}{v_6} 
& = 1
\end{array}
\] $$
All the other partial derivatives of $latex f_6$$ are zero.

$head Index 6: f_5$$
The previous operation has index 6, 
$latex \[
	v_6 = v_5 / 2
\] $$
We define the function 
$latex f_5 (  v_1 , v_2 , v_3 , v_4 , v_5 ) $$
as equal to $latex f_6 $$
except that $latex v_6 $$ is eliminated using this operation; i.e.,
$latex \[
f_5 = 
f_6 [  v_1 , v_2 , v_3 , v_4 , v_5 , v_6 ( v_5 ) ]
\] $$
It follows that 
$latex \[
\begin{array}{rcll}
\D{f_5}{v_4} 
& = & \D{f_6}{v_4} 
& = 1
\\
\D{f_5}{v_5} 
& = & \D{f_6}{v_5} + 
	\D{f_6}{v_6} * \D{v_6}{v_5} 
& = 0.5
\end{array}
\] $$
All the other partial derivatives of $latex f_5$$ are zero.

$head Index 5: f_4$$
The previous operation has index 5,
$latex \[
	v_5 = v_3 * v_1
\] $$
We define the function 
$latex f_4 (  v_1 , v_2 , v_3 , v_4 ) $$
as equal to $latex f_5 $$
except that $latex v_5 $$ is eliminated using this operation; i.e.,
$latex \[
f_4 = 
f_5 [  v_1 , v_2 , v_3 , v_4 , v_5 ( v_3 , v_1 )  ]
\] $$
Given the information from the forward sweep, we have
$latex v_3 =  0.5 $$ and $latex v_1 = 0.5 $$.
It follows that 
$latex \[
\begin{array}{rcll}
\D{f_4}{v_1} 
& = & \D{f_5}{v_1} + 
	\D{f_5}{v_5} * \D{v_5}{v_1} 
& =  0.25
\\
\D{f_4}{v_2} & = & \D{f_5}{v_2}  & = 0
\\
\D{f_4}{v_3} 
& = & \D{f_5}{v_3} + 
	\D{f_5}{v_5} * \D{v_5}{v_3} 
& =  0.25
\\
\D{f_4}{v_4}
& = & \D{f_5}{v_4} 
& = 1
\end{array}
\] $$

$head Index 4: f_3$$
The previous operation has index 4,
$latex \[
	v_4 = 1 + v_3
\] $$
We define the function 
$latex f_3 (  v_1 , v_2 , v_3 ) $$
as equal to $latex f_4 $$
except that $latex v_4 $$ is eliminated using this operation; i.e.,
$latex \[
f_3 = 
f_4 [  v_1 , v_2 , v_3 , v_4 ( v_3 )  ]
\] $$
It follows that 
$latex \[
\begin{array}{rcll}
\D{f_3}{v_1} 
& = & \D{f_4}{v_1} 
& =  0.25
\\
\D{f_3}{v_2} & = & \D{f_4}{v_2}  & = 0
\\
\D{f_3}{v_3} 
& = & \D{f_4}{v_3} + 
	\D{f_4}{v_4} * \D{v_4}{v_3} 
& =  1.25
\end{array}
\] $$


$head Index 3: f_2$$
The previous operation has index 3,
$latex \[
	v_3 = v_2 / 1
\] $$
We define the function 
$latex f_2 (  v_1 , v_2 ) $$
as equal to $latex f_3 $$
except that $latex v_3 $$ is eliminated using this operation; i.e.,
$latex \[
f_2 = 
f_4 [  v_1 , v_2 , v_3 ( v_2 )  ]
\] $$
It follows that 
$latex \[
\begin{array}{rcll}
\D{f_2}{v_1} 
& = & \D{f_3}{v_1} 
& =  0.25
\\
\D{f_2}{v_2} & = & \D{f_3}{v_2}  +
	\D{f_3}{v_3} * \D{v_3}{v_2}
& = 1.25
\end{array}
\] $$

$head Index 2: f_1$$
The previous operation has index 1,
$latex \[
	v_2 = 1 * v_1
\] $$
We define the function 
$latex f_1 (  v_1 ) $$
as equal to $latex f_2 $$
except that $latex v_2 $$ is eliminated using this operation; i.e.,
$latex \[
f_1 = 
f_2 [  v_1 , v_2 ( v_1 )  ]
\] $$
It follows that 
$latex \[
\begin{array}{rcll}
\D{f_1}{v_1} & = & \D{f_2}{v_1}  +
	\D{f_2}{v_2} * \D{v_2}{v_1}
& = 1.5
\end{array}
\] $$

Note that $latex v_1$$ is equal to $latex x$$,
so the derivative of $codei%exp_eps(%x%, %epsilon%)%$$ 
at $icode x$$ equal to .5 and $icode epsilon$$ equal .2 is
1.5 in the $icode x$$ direction and zero in the $icode epsilon$$ direction.
We also note that 
$cref/forward/exp_eps_for1/$$ forward mode gave the 
same result for the partial in the $icode x$$ direction.


$children%
	introduction/exp_apx/exp_eps_rev1.cpp
%$$

$head Verification$$
The file $cref exp_eps_rev1.cpp$$ contains a routine 
that verifies the values computed above.
It returns true for success and false for failure.
It only tests the partial derivatives of
$latex f_j$$ that might not be equal to the corresponding
partials of $latex f_{j+1}$$; i.e., the
other partials of $latex f_j$$ must be equal to the corresponding
partials of $latex f_{j+1}$$.

$head Exercises$$
$list number$$
Consider the case where $latex x = .1$$
and we first preform a zero order forward mode sweep
for the operation sequence used above (in reverse order).
What are the results of a 
first order reverse mode sweep; i.e.,
what are the corresponding values for 
$latex \D{f_j}{v_k}$$ for all $latex j, k$$ such that
$latex \D{f_j}{v_k} \neq 0$$.
$lnext
Create a modified version of 
$cref exp_eps_rev1.cpp$$ 
that verifies the values you obtained for the previous exercise.
Also create and run a main program that reports the result
of calling the modified version of
$cref exp_eps_rev1.cpp$$.
$lend

$end
-----------------------------------------------------------------------------
$begin exp_eps_for2$$
$spell
	exp_eps_for
$$

$section exp_eps: Second Order Forward Mode$$

$index exp_eps, forward mode$$
$index example, forward mode$$
$index forward, mode example$$
$index mode, example forward$$
$index forward, second order$$


$head Second Order Expansion$$
$index second, order expansion$$
$index order, second expansion$$
$index expansion, second order$$

We define $latex x(t)$$ and $latex \varepsilon(t) ]$$ near $latex t = 0$$ 
by the second order expansions
$latex \[
\begin{array}{rcl}
	x(t) & = & x^{(0)} + x^{(1)} * t  + x^{(2)} * t^2 / 2
	\\
	\varepsilon(t) & = & \varepsilon^{(0)} + \varepsilon^{(1)} * t
	                 +   \varepsilon^{(2)} * t^2 / 2
\end{array}
\]$$
It follows that for $latex k = 0 , 1 , 2$$,
$latex \[
\begin{array}{rcl}
	x^{(k)}  & = & \dpow{k}{t} x (0)
	\\
	\varepsilon^{(k)}  & = & \dpow{k}{t} \varepsilon (0)
\end{array}
\] $$

$head Purpose$$
In general, a second order forward sweep is given the
$cref/first order expansion/exp_2_for1/First Order Expansion/$$
for all of the variables in an operation sequence,
and the second order derivatives for the independent variables.
It uses these to compute the second order derivative,
and thereby obtain the second order expansion,
for all the variables in the operation sequence.

$head Mathematical Form$$
Suppose that we use the algorithm $cref exp_eps.hpp$$
to compute $codei%exp_eps(%x%, %epsilon%)%$$
with $icode x$$ is equal to .5
and $icode epsilon$$ is equal to .2. 
For this case, the mathematical function for the operation sequence
corresponding to $code exp_eps$$ is
$latex \[
f ( x , \varepsilon ) =   1 + x + x^2 / 2  
\] $$
The corresponding second partial derivative with respect to $latex x$$,
and the value of the derivative, are
$latex \[
\Dpow{2}{x} f ( x , \varepsilon ) =   1.
\] $$

$head Operation Sequence$$

$subhead Index$$
The Index column contains the index in the operation sequence
of the corresponding atomic operation. 
A Forward sweep starts with the first operation 
and ends with the last.

$subhead Zero$$
The Zero column contains the zero order sweep results
for the corresponding variable in the operation sequence
(see $cref/zero order sweep/exp_2_for0/Operation Sequence/Sweep/$$).

$subhead Operation$$
The Operation column contains the 
first order sweep operation for this variable.

$subhead First$$
The First column contains the first order sweep results
for the corresponding variable in the operation sequence
(see $cref/first order sweep/exp_2_for1/Operation Sequence/Sweep/$$).

$subhead Derivative$$
The Derivative column contains the
mathematical function corresponding to the second derivative
with respect to $latex t$$,
at $latex t = 0$$, for each variable in the sequence.

$subhead Second$$
The Second column contains the second order derivatives
for the corresponding variable in the operation sequence; i.e.,
the second order expansion for the $th i$$ variable is given by
$latex \[
	v_i (t) = v_i^{(0)} + v_i^{(1)} * t +  v_i^{(2)} * t^2 / 2
\] $$
We use $latex x^{(1)} = 1$$, $latex x^{(2)} = 0$$,
use $latex \varepsilon^{(1)} = 1$$, and $latex \varepsilon^{(2)} = 0$$
so that second order differentiation
with respect to $latex t$$, at $latex t = 0$$, 
is the same as the second partial differentiation 
with respect to $latex x$$ at $latex x = x^{(0)}$$.


$subhead Sweep$$

$center
$table
$bold Index$$
	$cnext $pre  $$ $cnext $bold Zero$$
	$cnext $pre  $$ $cnext $bold Operation$$ 
	$cnext $pre  $$ $cnext $bold First$$
	$cnext $pre  $$ $cnext $bold Derivative$$
	$cnext $pre  $$ $cnext $bold Second$$
$rnext
1
	$cnext $cnext 0.5
	$cnext $cnext 
	$latex v_1^{(1)} = x^{(1)}  $$
	$cnext $cnext 1
	$cnext $cnext
	$latex v_2^{(2)} = x^{(2)}  $$
	$cnext $cnext 0
$rnext
2
	$cnext $cnext 0.5
	$cnext $cnext 
	$latex v_2^{(1)} = 1 * v_1^{(1)}$$
	$cnext $cnext 1
	$cnext $cnext
	$latex v_2^{(2)} = 1 * v_1^{(2)}$$
	$cnext $cnext 0
$rnext
3
	$cnext $cnext 0.5
	$cnext $cnext 
	$latex v_3^{(1)} = v_2^{(1)} / 1$$
	$cnext $cnext 1
	$cnext $cnext
	$latex v_3^{(2)} = v_2^{(2)} / 1$$
	$cnext $cnext 0
$rnext
4
	$cnext $cnext 1.5
	$cnext $cnext 
	$latex v_4^{(1)} = v_3^{(1)} $$
	$cnext $cnext 1
	$cnext $cnext
	$latex v_4^{(2)} = v_3^{(2)} $$
	$cnext $cnext 0
$rnext
5
	$cnext $cnext 0.25
	$cnext $cnext 
	$latex v_5^{(1)} = v_3^{(1)} * v_1^{(0)} + v_3^{(0)} * v_1^{(1)}$$
	$cnext $cnext 1
	$cnext $cnext
	$latex v_5^{(2)} = v_3^{(2)} * v_1^{(0)} + 2 * v_3^{(1)} * v_1^{(1)}
	                 + v_3^{(0)} * v_1^{(2)}$$
	$cnext $cnext 2
$rnext
6
	$cnext $cnext 0.125
	$cnext $cnext 
	$latex v_6^{(1)} = v_5^{(1)} / 2$$
	$cnext $cnext 0.5
	$cnext $cnext
	$latex v_6^{(2)} = v_5^{(2)} / 2$$
	$cnext $cnext 1
$rnext
7
	$cnext $cnext 1.625
	$cnext $cnext 
	$latex  v_7^{(1)} = v_4^{(1)} + v_6^{(1)}$$
	$cnext $cnext 1.5
	$cnext $cnext
	$latex  v_7^{(2)} = v_4^{(2)} + v_6^{(2)}$$
	$cnext $cnext 1
$tend
$$

$head Return Value$$
The second derivative of the return value for this case is
$latex \[
\begin{array}{rcl}
1 
& = & 
v_7^{(2)} =
\left[ \Dpow{2}{t} v_7 \right]_{t=0} =
\left[ \Dpow{2}{t} f( x^{(0)} + x^{(1)} * t , \varepsilon^{(0)} ) \right]_{t=0}
\\
& = &
x^{(1)} * \Dpow{2}{x} f ( x^{(0)} ,  \varepsilon^{(0)} ) * x^{(1)} =
\Dpow{2}{x} f ( x^{(0)} ,  \varepsilon^{(0)} )
\end{array}
\] $$
(We have used the fact that
$latex x^{(1)} = 1$$, $latex x^{(2)} = 0$$,
$latex \varepsilon^{(1)} = 1$$, and $latex \varepsilon^{(2)} = 0$$.)

$children%
	introduction/exp_apx/exp_eps_for2.cpp
%$$
$head Verification$$
The file $cref exp_eps_for2.cpp$$ contains a routine 
which verifies the values computed above.
It returns true for success and false for failure.

$head Exercises$$
$list number$$
Which statement in the routine defined by $cref exp_eps_for2.cpp$$ uses 
the values that are calculated by the routine 
defined by $cref exp_eps_for1.cpp$$ ?
$lnext
Suppose that $latex x = .1$$,
what are the results of a zero, first, and second order forward sweep for 
the operation sequence above; 
i.e., what are the corresponding values for
$latex v_i^{(k)}$$ for $latex i = 1, \ldots , 7$$ and $latex k = 0, 1, 2$$.
$lnext
Create a modified version of $cref exp_eps_for2.cpp$$ that verifies 
the derivative values from the previous exercise.
Also create and run a main program that reports the result
of calling the modified version of
$cref exp_eps_for2.cpp$$.
$lend

$end
-----------------------------------------------------------------------------
$begin exp_eps_rev2$$
$spell
	exp_eps_rev
$$

$section exp_eps: Second Order Reverse Sweep$$

$index exp_eps, reverse mode$$
$index example, reverse mode$$
$index reverse, mode example$$
$index mode, reverse example$$

$index second, order reverse$$
$index order, second reverse$$
$index reverse, second order$$

$head Purpose$$
In general, a second order reverse sweep is given the
$cref/first order expansion/exp_eps_for1/First Order Expansion/$$
for all of the variables in an operation sequence.
Given a choice of a particular variable, 
it computes the derivative, 
of that variables first order expansion coefficient, 
with respect to all of the independent variables.

$head Mathematical Form$$
Suppose that we use the algorithm $cref exp_eps.hpp$$
to compute $codei%exp_eps(%x%, %epsilon%)%$$
with $icode x$$ is equal to .5
and $icode epsilon$$ is equal to .2. 
For this case, the mathematical function for the operation sequence
corresponding to $code exp_eps$$ is
$latex \[
f ( x , \varepsilon ) =   1 + x + x^2 / 2  
\] $$
The corresponding derivative of the
partial derivative with respect to $latex x$$ is
$latex \[
\begin{array}{rcl}
\Dpow{2}{x} f ( x , \varepsilon ) & = &  1
\\
\partial_\varepsilon \partial_x f ( x , \varepsilon ) & = &  0
\end{array}
\] $$

$head epsilon$$
Since $latex \varepsilon$$ is an independent variable,
it could included as an argument to all of the
$latex f_j$$ functions below.
The result would be that all the partials with respect to 
$latex \varepsilon$$ would be zero and hence we drop it to simplify
the presentation.

$head f_7$$
In reverse mode we choose one dependent variable and
compute its derivative with respect to all the independent variables.
For our example, we chose the value returned by $cref exp_eps.hpp$$
which is $latex v_7$$.
We begin with the function $latex f_7$$ where $latex v_7$$ 
is both an argument and the value of the function; i.e.,
$latex \[
\begin{array}{rcl}
f_7 \left( 
	v_1^{(0)} , v_1^{(1)} , \ldots , v_7^{(0)} , v_7^{(1)} 
\right) 
& = & v_7^{(1)} 
\\
\D{f_7}{v_7^{(1)}} & = & 1
\end{array}
\] $$
All the other partial derivatives of $latex f_7$$ are zero.

$head Index 7: f_6$$
The last operation has index 7,
$latex \[
\begin{array}{rcl}
	v_7^{(0)} & = &   v_4^{(0)} + v_6^{(0)}  
	\\
	v_7^{(1)} & = &   v_4^{(1)} + v_6^{(1)}  
\end{array}
\] $$
We define the function 
$latex f_6 \left( v_1^{(0)} , \ldots , v_6^{(1)} \right) $$
as equal to $latex f_7$$
except that $latex v_7^{(0)}$$ and $latex v_7^{(1)}$$ are eliminated using 
this operation; i.e.
$latex \[
f_6  = 
f_7 \left[ v_1^{(0)} , \ldots , v_6^{(1)} , 
	v_7^{(0)} \left( v_4^{(0)} , v_6^{(0)} \right)  ,
	v_7^{(1)} \left( v_4^{(1)} , v_6^{(1)} \right)  
\right]
\] $$
It follows that 
$latex \[
\begin{array}{rcll}
\D{f_6}{v_4^{(1)}} 
& = & \D{f_7}{v_4^{(1)}} + 
	\D{f_7}{v_7^{(1)}} * \D{v_7^{(1)}}{v_4^{(1)}} 
& = 1
\\
\D{f_6}{v_6^{(1)}} 
& = & \D{f_7}{v_6^{(1)}} + 
	\D{f_7}{v_7^{(1)}} * \D{v_7^{(1)}}{v_6^{(1)}} 
& = 1
\end{array}
\] $$
All the other partial derivatives of $latex f_6$$ are zero.

$head Index 6: f_5$$
The previous operation has index 6, 
$latex \[
\begin{array}{rcl}
	v_6^{(0)} & = & v_5^{(0)} / 2
	\\
	v_6^{(1)} & = & v_5^{(1)} / 2
\end{array}
\] $$
We define the function 
$latex f_5 \left( v_1^{(0)} , \ldots , v_5^{(1)} \right) $$
as equal to $latex f_6 $$
except that $latex v_6^{(0)}$$ and $latex v_6^{(1)}$$ are eliminated using 
this operation; i.e.
$latex \[
f_5 = 
f_6 \left[ v_1^{(0)} , \ldots , v_5^{(1)} , 
	v_6^{(0)} \left( v_5^{(0)} \right) ,
	v_6^{(1)} \left( v_5^{(1)} \right) 
\right]
\] $$
It follows that 
$latex \[
\begin{array}{rcll}
\D{f_5}{v_4^{(1)}} 
& = & \D{f_6}{v_4^{(1)}} 
& = 1
\\
\D{f_5}{v_5^{(1)}} 
& = & \D{f_6}{v_5} + 
	\D{f_6}{v_6^{(1)}} * \D{v_6^{(1)}}{v_5^{(1)}} 
& = 0.5
\end{array}
\] $$
All the other partial derivatives of $latex f_5$$ are zero.

$head Index 5: f_4$$
The previous operation has index 5,
$latex \[
\begin{array}{rcl}
	v_5^{(0)} & = & v_3^{(0)} * v_1^{(0)}
	\\
	v_5^{(1)} & = & v_3^{(1)} * v_1^{(0)} + v_3^{(0)} * v_1^{(1)}
\end{array}
\] $$
We define the function 
$latex f_4 \left( v_1^{(0)} , \ldots , v_4^{(1)} \right) $$
as equal to $latex f_5 $$
except that $latex v_5^{(0)}$$ and $latex v_5^{(1)}$$ are eliminated using 
this operation; i.e.
$latex \[
f_4 = 
f_5 \left[  v_1^{(0)} , \ldots , v_4^{(1)} ,
	v_5^{(0)} \left( v_1^{(0)}, v_3^{(0)} \right) ,
	v_5^{(1)} \left( v_1^{(0)}, v_1^{(1)}, v_3^{(0)} , v_3^{(1)} \right) ,
\right]
\] $$
Given the information from the forward sweep, we have
$latex v_1^{(0)} =  0.5$$,
$latex v_3^{(0)} =  0.5$$,
$latex v_1^{(1)} =  1$$,
$latex v_3^{(1)} =  1$$,
and the fact that the partial of $latex f_5$$ with respect to
$latex v_5^{(0)}$$ is zero, we have
$latex \[
\begin{array}{rcll}
\D{f_4}{v_1^{(0)}}
& = & \D{f_5}{v_1^{(0)}}
  +   \D{f_5}{v_5^{(1)}} * \D{v_5^{(1)}}{v_1^{(0)}} 
& = 0.5
\\
\D{f_4}{v_1^{(1)}}
& = & \D{f_5}{v_1^{(1)}}
  +   \D{f_5}{v_5^{(1)}} * \D{v_5^{(1)}}{v_1^{(1)}} 
& = 0.25
\\
\D{f_4}{v_3^{(0)}}
& = & \D{f_5}{v_3^{(0)}}
  +   \D{f_5}{v_5^{(1)}} * \D{v_5^{(1)}}{v_3^{(0)}} 
& = 0.5
\\
\D{f_4}{v_3^{(1)}}
& = & \D{f_3}{v_1^{(1)}}
  +   \D{f_5}{v_5^{(1)}} * \D{v_5^{(1)}}{v_3^{(1)}} 
& = 0.25
\\
\D{f_4}{v_4^{(1)}}
& = & \D{f_5}{v_4^{(1)}}
& = 1
\end{array}
\] $$
All the other partial derivatives of $latex f_5$$ are zero.

$head Index 4: f_3$$
The previous operation has index 4,
$latex \[
\begin{array}{rcl}
	v_4^{(0)} = 1 + v_3^{(0)}
	\\
	v_4^{(1)} = v_3^{(1)}
\end{array}
\] $$
We define the function 
$latex f_3 \left( v_1^{(0)} , \ldots , v_3^{(1)} \right) $$
as equal to $latex f_4 $$
except that $latex v_4^{(0)}$$ and $latex v_4^{(1)}$$ are eliminated using 
this operation; i.e.
$latex \[
f_3 = 
f_4 \left[ v_1^{(0)} , \ldots , v_3^{(1)} ,
	v_4^{(0)} \left( v_3^{(0)} \right) ,
	v_4^{(1)} \left( v_3^{(1)} \right)  
\right]
\] $$
It follows that 
$latex \[
\begin{array}{rcll}
\D{f_3}{v_1^{(0)}} 
& = & \D{f_4}{v_1^{(0)}}
& =  0.5
\\
\D{f_3}{v_1^{(1)}} 
& = & \D{f_4}{v_1^{(1)}}
& =  0.25
\\
\D{f_3}{v_2^{(0)}} 
& = & \D{f_4}{v_2^{(0)}}  
& = 0
\\
\D{f_3}{v_2^{(1)}} 
& = & \D{f_4}{v_2^{(1)}}  
& = 0
\\
\D{f_3}{v_3^{(0)}} 
& = & \D{f_4}{v_3^{(0)}} 
  +   \D{f_4}{v_4^{(0)}} * \D{v_4^{(0)}}{v_3^{(0)}} 
& = 0.5
\\
\D{f_3}{v_3^{(1)}} 
& = & \D{f_4}{v_3^{(1)}} 
  +   \D{f_4}{v_4^{(1)}} * \D{v_4^{(1)}}{v_3^{(1)}} 
& = 1.25
\end{array}
\] $$


$head Index 3: f_2$$
The previous operation has index 3,
$latex \[
\begin{array}{rcl}
	v_3^{(0)} & = & v_2^{(0)} / 1
	\\
	v_3^{(1)} & = & v_2^{(1)} / 1
\end{array}
\] $$
We define the function 
$latex f_2 \left( v_1^{(0)} , \ldots , v_2^{(1)} \right) $$
as equal to $latex f_3 $$
except that $latex v_3^{(0)}$$ and $latex v_3^{(1)}$$ are eliminated using 
this operation; i.e.
$latex \[
f_2 = 
f_3 \left[ v_1^{(0)} , \ldots , v_2^{(1)} ,
	v_3^{(0)} \left( v_2^{(0)} \right) ,
	v_3^{(1)} \left( v_2^{(1)} \right)
\right]
\] $$
It follows that 
$latex \[
\begin{array}{rcll}
\D{f_2}{v_1^{(0)}} 
& = & \D{f_3}{v_1^{(0)}}
& =  0.5
\\
\D{f_2}{v_1^{(1)}} 
& = & \D{f_3}{v_1^{(1)}}
& =  0.25
\\
\D{f_2}{v_2^{(0)}} 
& = & \D{f_3}{v_2^{(0)}}  
  +   \D{f_3}{v_3^{(0)}} * \D{v_3^{(0)}}{v_2^{(0)}}
& = 0.5
\\
\D{f_2}{v_2^{(1)}} 
& = & \D{f_3}{v_2^{(1)}}  
  +   \D{f_3}{v_3^{(1)}} * \D{v_3^{(1)}}{v_2^{(0)}}
& = 1.25
\end{array}
\] $$

$head Index 2: f_1$$
The previous operation has index 1,
$latex \[
\begin{array}{rcl}
	v_2^{(0)} & = & 1 * v_1^{(0)}
	\\
	v_2^{(1)} & = & 1 * v_1^{(1)}
\end{array}
\] $$
We define the function 
$latex f_1 \left( v_1^{(0)} , v_1^{(1)} \right) $$
as equal to $latex f_2 $$
except that $latex v_2^{(0)}$$ and $latex v_2^{(1)}$$ are eliminated using 
this operation; i.e.
$latex \[
f_1 = 
f_2 \left[  v_1^{(0)} , v_1^{(1)} , 
	v_2^{(0)} \left( v_1^{(0)} \right)  ,
	v_2^{(1)} \left( v_1^{(1)} \right)  
\right]
\] $$
It follows that 
$latex \[
\begin{array}{rcll}
\D{f_1}{v_1^{(0)}} 
& = & \D{f_2}{v_1^{(0)}}
  +   \D{f_2}{v_2^{(0)}} * \D{v_2^{(0)}}{v_1^{(0)}}
& =  1
\\
\D{f_1}{v_1^{(1)}} 
& = & \D{f_2}{v_1^{(1)}}
  +   \D{f_2}{v_2^{(1)}} * \D{v_2^{(1)}}{v_1^{(1)}}
& = 1.5
\end{array}
\] $$
Note that $latex v_1$$ is equal to $latex x$$,
so the second partial derivative of 
$codei%exp_eps(%x%, %epsilon%)%$$ 
at $icode x$$ equal to .5 and $icode epsilon$$ equal .2 is 
$latex \[
\Dpow{2}{x} v_7^{(0)}
= \D{v_7^{(1)}}{x} 
= \D{f_1}{v_1^{(0)}}
= 1
\] $$
There is a theorem about algorithmic differentiation that explains why
the other partial of $latex f_1$$ is equal to the first partial of
$codei%exp_eps(%x%, %epsilon%)%$$ 
with respect to $latex x$$.


$children%
	introduction/exp_apx/exp_eps_rev2.cpp
%$$

$head Verification$$
The file $cref exp_eps_rev2.cpp$$ contains a routine 
that verifies the values computed above.
It returns true for success and false for failure.
It only tests the partial derivatives of
$latex f_j$$ that might not be equal to the corresponding
partials of $latex f_{j+1}$$; i.e., the
other partials of $latex f_j$$ must be equal to the corresponding
partials of $latex f_{j+1}$$.

$head Exercises$$
$list number$$
Consider the case where $latex x = .1$$
and we first preform a zero order forward mode sweep
for the operation sequence used above (in reverse order).
What are the results of a 
first order reverse mode sweep; i.e.,
what are the corresponding values for 
$latex \D{f_j}{v_k}$$ for all $latex j, k$$ such that
$latex \D{f_j}{v_k} \neq 0$$.
$lnext
Create a modified version of 
$cref exp_eps_rev2.cpp$$ 
that verifies the values you obtained for the previous exercise.
Also create and run a main program that reports the result
of calling the modified version of
$cref exp_eps_rev2.cpp$$.
$lend

$end
-----------------------------------------------------------------------------