lines 710-1017 of file: introduction/exp_2.xrst

{xrst_begin exp_2_rev2}
{xrst_spell
   preform
   rcll
}

exp_2: Second Order Reverse Mode
################################

Purpose
*******
In general, a second order reverse sweep is given the
:ref:`exp_2_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.

Mathematical Form
*****************
Suppose that we use the algorithm :ref:`exp_2.hpp-name` to compute

.. math::

   f(x) = 1 + x + x^2 / 2

The corresponding second derivative is

.. math::

   \Dpow{2}{x} f (x) =   1

f_5
***
For our example, we chose to compute the derivative of :math:`v_5^{(1)}`
with respect to all the independent variable.
For the case computed for the
:ref:`first order sweep<exp_2_for1@Operation Sequence@Sweep>` ,
:math:`v_5^{(1)}` is the derivative
of the value returned by :ref:`exp_2.hpp-name` .
This the value computed will be the second derivative of
the value returned by  :ref:`exp_2.hpp-name` .
We begin with the function :math:`f_5` where :math:`v_5^{(1)}`
is both an argument and the value of the function; i.e.,

.. math::
   :nowrap:

   \begin{eqnarray}
   f_5 \left(
      v_1^{(0)}, v_1^{(1)} , \ldots  , v_5^{(0)} , v_5^{(1)}
   \right)
   & = & v_5^{(1)}
   \\
   \D{f_5}{v_5^{(1)}} & = & 1
   \end{eqnarray}

All the other partial derivatives of :math:`f_5` are zero.

Index 5: f_4
************
Second order reverse mode starts with the last operation in the sequence.
For the case in question, this is the operation with index 5.
The zero and first order sweep representations of this operation are

.. math::
   :nowrap:

   \begin{eqnarray}
      v_5^{(0)} & = & v_2^{(0)} + v_4^{(0)}
      \\
      v_5^{(1)} & = & v_2^{(1)} + v_4^{(1)}
   \end{eqnarray}

We define the function
:math:`f_4 \left( v_1^{(0)} , \ldots , v_4^{(1)} \right)`
as equal to :math:`f_5`
except that :math:`v_5^{(0)}` and :math:`v_5^{(1)}` are eliminated using
this operation; i.e.

.. math::

   f_4  =
   f_5 \left[   v_1^{(0)} , \ldots , v_4^{(1)} ,
      v_5^{(0)} \left( v_2^{(0)} , v_4^{(0)} \right) ,
      v_5^{(1)} \left( v_2^{(1)} , v_4^{(1)} \right)
   \right]

It follows that

.. math::

   \begin{array}{rcll}
   \D{f_4}{v_2^{(1)}}
   & = & \D{f_5}{v_2^{(1)}} +
      \D{f_5}{v_5^{(1)}} * \D{v_5^{(1)}}{v_2^{(1)}}
   & = 1
   \\
   \D{f_4}{v_4^{(1)}}
   & = & \D{f_5}{v_4^{(1)}} +
      \D{f_5}{v_5^{(1)}} * \D{v_5}{v_4^{(1)}}
   & = 1
   \end{array}

All the other partial derivatives of :math:`f_4` are zero.

Index 4: f_3
************
The next operation has index 4,

.. math::
   :nowrap:

   \begin{eqnarray}
      v_4^{(0)} & = & v_3^{(0)} / 2
      \\
      v_4^{(1)} & = & v_3^{(1)} / 2
   \end{eqnarray}

We define the function
:math:`f_3 \left(  v_1^{(0)} , \ldots , v_3^{(1)} \right)`
as equal to :math:`f_4`
except that :math:`v_4^{(0)}` and :math:`v_4^{(1)}`
are eliminated using this operation; i.e.,

.. math::

   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

.. math::

   \begin{array}{rcll}
   \D{f_3}{v_2^{(1)}}
   & = & \D{f_4}{v_2^{(1)}}
   & = 1
   \\
   \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)}}
   & = 0.5
   \end{array}

All the other partial derivatives of :math:`f_3` are zero.

Index 3: f_2
************
The next operation has index 3,

.. math::
   :nowrap:

   \begin{eqnarray}
      v_3^{(0)} & = & v_1^{(0)} * v_1^{(0)}
      \\
      v_3^{(1)} & = & 2 * v_1^{(0)} * v_1^{(1)}
   \end{eqnarray}

We define the function
:math:`f_2 \left(  v_1^{(0)} , \ldots , v_2^{(1)} \right)`
as equal to :math:`f_3`
except that :math:`v_3^{(0)}` and :math:`v_3^{(1)}` are
eliminated using this operation; i.e.,

.. math::

   f_2 =
   f_3 \left[ v_1^{(0)} , \ldots , v_2^{(1)} ,
      v_3^{(0)} ( v_1^{(0)} ) ,
      v_3^{(1)} ( v_1^{(0)} , v_1^{(1)} )
   \right]

Note that, from the
:ref:`first order forward sweep<exp_2_for1@Operation Sequence@Sweep>` ,
the value of :math:`v_1^{(0)}` is equal to :math:`.5`
and  :math:`v_1^{(1)}` is equal 1.
It follows that

.. math::

   \begin{array}{rcll}
   \D{f_2}{v_1^{(0)}}
   & = &
   \D{f_3}{v_1^{(0)}} +
      \D{f_3}{v_3^{(0)}} * \D{v_3^{(0)}}{v_1^{(0)}}  +
      \D{f_3}{v_3^{(1)}} * \D{v_3^{(1)}}{v_1^{(0)}}
   & = 1
   \\
   \D{f_2}{v_1^{(1)}}
   & = &
   \D{f_3}{v_1^{(1)}} +
      \D{f_3}{v_3^{(1)}} * \D{v_3^{(1)}}{v_1^{(1)}}
   & = 0.5
   \\
   \D{f_2}{v_2^{(0)}}
   & = & \D{f_3}{v_2^{(0)}}
   & = 0
   \\
   \D{f_2}{v_2^{(1)}}
   & = & \D{f_3}{v_2^{(1)}}
   & = 1
   \end{array}

Index 2: f_1
************
The next operation has index 2,

.. math::
   :nowrap:

   \begin{eqnarray}
      v_2^{(0)} & = & 1 + v_1^{(0)}
      \\
      v_2^{(1)} & = & v_1^{(1)}
   \end{eqnarray}

We define the function
:math:`f_1 ( v_1^{(0)} , v_1^{(1)} )`
as equal to :math:`f_2`
except that :math:`v_2^{(0)}` and  :math:`v_2^{(1)}`
are eliminated using this operation; i.e.,

.. math::

   f_1 =
   f_2 \left[ v_1^{(0)} , v_1^{(1)} ,
      v_2^{(0)} ( v_1^{(0)} )  ,
      v_2^{(1)} ( v_1^{(1)} )
   \right]

It follows that

.. math::

   \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 :math:`v_1` is equal to :math:`x`,
so the second derivative of
the function defined by :ref:`exp_2.hpp-name` at :math:`x = .5`
is given by

.. math::

   \Dpow{2}{x} v_5^{(0)}
   =
   \D{ v_5^{(1)} }{x}
   =
   \D{ v_5^{(1)} }{v_1^{(0)}}
   =
   \D{f_1}{v_1^{(0)}} = 1

There is a theorem about Algorithmic Differentiation that explains why
the other partial of :math:`f_1` is equal to the
first derivative of
the function defined by :ref:`exp_2.hpp-name` at :math:`x = .5`.
{xrst_toc_hidden
   introduction/exp_2_rev2.cpp
}
Verification
************
The file :ref:`exp_2_rev2.cpp-name` contains a routine
which verifies the values computed above.
It only tests the partial derivatives of
:math:`f_j` that might not be equal to the corresponding
partials of :math:`f_{j+1}`; i.e., the
other partials of :math:`f_j` must be equal to the corresponding
partials of :math:`f_{j+1}`.

Exercises
*********

#. Which statement in the routine defined by :ref:`exp_2_rev2.cpp-name` uses
   the values that are calculated by the routine
   defined by :ref:`exp_2_for0.cpp-name` ?
   Which statements use values that are calculate by the routine
   defined in :ref:`exp_2_for1.cpp-name` ?
#. Consider the case where :math:`x = .1`
   and we first preform a zero order forward sweep,
   then a first order sweep,
   for the operation sequence used above.
   What are the results of a
   second order reverse sweep; i.e.,
   what are the corresponding derivatives of
   :math:`f_5 , f_4 , \ldots , f_1`.
#. Create a modified version of
   :ref:`exp_2_rev2.cpp-name`
   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
   :ref:`exp_2_rev2.cpp-name` .

{xrst_end exp_2_rev2}