\documentstyle{article}
\evensidemargin 0.25in
\oddsidemargin 0.25in
\textheight 8.7in
\textwidth 6in
\topmargin 0in
\floatsep 12pt plus 2pt minus 2pt
\textfloatsep 10pt plus 2pt minus 4pt % change separation of figures
\title{User's Guide for ACDC: An Automatic Continuation Code for Solving
Stiff Two-Point Boundary Value Problems}
\author{J.\ R.\ Cash\thanks{E-mail: j.cash@ic.ac.uk} $\;$ and
R.\ W.\ Wright\thanks{E-mail: r.wright@ic.ac.uk} \\
{\small \sl {Department of Mathematics, Imperial College,
South Kensington, London SW7 2BZ, England}}}
\date{}
\begin{document}
\def\norm#1{\Vert#1\Vert}
\def\real{\cal R}
\def\half {{\textstyle{1\over 2}}}
\def\ACDC{\small ACDC}
\def\TWPBVP{\small TWPBVP}
\maketitle
\section{Introduction}
The abbreviation {\ACDC} stands for Automatic Continuation with Deferred
Corrections. The package {\ACDC} (which is written in {\small FORTRAN} 77)
is designed to solve stiff two-point boundary value problems for ordinary
differential equations by using continuation.
We note that {\ACDC} is a modification of the package {\TWPBVP} of Cash and
M.\ H.\ Wright \cite{CaWr} and that many of the original subroutines used
in {\TWPBVP} remain unchanged in the new code. {\ACDC} has been adapted to
allow an automatic continuation strategy to be used \cite{CaMoWr1}.
Furthermore, the new code incorporates implicit Runge-Kutta formulae, based on Lobatto
points \cite{Si}, rather than the mono-implicit formulae used in the original code.
This code is a companion to the continuation code {\small COLMOD}, which implements
our continuation strategy together with a high-order collocation method.
The package solves first-order systems of ordinary differential equations involving
a small positive parameter, which we denote by $\epsilon$. The two-point boundary
conditions must be separated, thus we are interested in problems of the form
\begin{equation}
\label{eqn-prob1}
\begin{array}{c}
{\bf u}' = {\bf f}(x,{\bf u},\epsilon), \;\;\;\;\; a \le x \le b, \\
{\bf g}_1({\bf u}(a),\epsilon) = {\bf 0},\;\;\;\;\; {\bf g}_2({\bf u}(b),\epsilon) = {\bf 0},
\end{array}
\end{equation}
where $x\in\real$, ${\bf u},{\bf f}\in{\real}^n$, ${\bf g}_1 : {\real}^n \rightarrow
{\real}^p$ and ${\bf g}_2 : {\real}^n \rightarrow {\real}^q$ with $n=p+q$.
The functions ${\bf f}$, ${\bf g}_1$, and ${\bf g}_2$ are assumed to be differentiable.
The numerical method used in {\ACDC} is a deferred correction method based on Lobatto
Runge-Kutta formulae and adaptive mesh refinement. The fact that Lobatto
Runge-Kutta formulae can be expressed in a symmetric manner and have good stability
properties means that they are suitable candidates for solving very stiff problems (for
a discussion of this see \cite{Si}). The mesh refinement algorithm used in {\ACDC}
is the same as in {\TWPBVP} and is described in \cite{CW2}. The continuation algorithm used
is based upon the prediction of the behaviour of the monitor function (used for mesh
selection) from problem to problem, and is discussed in \cite{CaMoWr1}.
\subsection{Restriction on the Choice of $\epsilon$}
As previously stated, the type of problems that {\ACDC} is designed to solve involve
a small positive parameter $0 < \epsilon \ll 1$. As $\epsilon$ becomes progressively
smaller, the problem normally becomes increasingly difficult to approximate numerically
(e.g., due to the appearance of narrow transition layers in the profile of the
solution). The idea of continuation is to solve a chain of problems in which
the parameter $\epsilon$ decreases towards some desired value. That is,
we attempt to solve a sequence of problems
\begin{equation}
1 > \epsilon_s > \epsilon_1 > \epsilon_2 > \ldots > \epsilon_{min} > 0
\end{equation}
where $\epsilon_s$ is a user provided starting value and $\epsilon_{min}$ is a user
provided final value for the continuation parameter. Given $\epsilon_s$ and
$\epsilon_{min}$ the
code automatically selects the intermediate $\epsilon$ values and passes on meshes
and solutions (if solving a nonlinear problem) at each step. We note that the
intermediate problems are not necessarily solved to the user requested accuracy.
However, it is expected that the intermediate problems will,
in the worst cases, fail the user requested accuracy by only a relatively small
amount. For a detailed discussion of this see \cite{CaMoWr2}.
The dependence on a small positive parameter in not unduly restrictive. Certainly
the positive requirement does not pose any difficulty, and, furthermore,
problems involving a large parameter can simply be re-expressed as problems
involving the reciprocal of a small parameter. Our experience is that it is
possible to identify such a parameter in most stiff problems of practical
interest. The important feature is that the difficulty in obtaining a numerical
solution increases as the parameter decreases.
\subsection{Conversion to First-Order Form}
Two important aspects of the formulation (\ref{eqn-prob1}) should be noted, namely,
the problem must be posed as a first-order system and the boundary conditions must
be separated and specified at two points only. Standard techniques can be
applied to overcome these restrictions \cite{AsRu}. It is possible to convert
any $n$th-order ordinary differential equation to a system of $n$ first-order equations.
For example, the second-order problem
\[
\epsilon y'' = f(x,y,y'),\;\;\;\;\; 0\le x \le 1,\;\;\;\;\;
y(0) = \alpha,\;\;\; y(1) = \beta,
\]
can be converted to the following first-order system
\begin{eqnarray*}
\begin{array}{rcl}
u'_1 & = & u_2, \\
u'_2 & = & f(x,u_1,u_2)/\epsilon,
\end{array} & & \;\;\; u_1(0) = \alpha,\;\;\; u_1(1) = \beta.
\end{eqnarray*}
This technique extends naturally to equations of order greater than two.
With regard to the boundary conditions, we note that there exist various
techniques that enable non-separated and multi-point boundary conditions to
be converted to the separated form needed here. For a discussion of such
techniques the user is referred to \cite[pp. 4-7]{AMR},\cite{AsRu}.
\section{Formal parameters}
In what follows we describe the parameters used in the calling sequence for {\ACDC},
which is
\begin{verbatim}
Call Acdc(Ncomp, Nlbc, Nucol, Aleft, Aright, Nfxpnt, Fixpnt,
+ Ntol, Ltol, Tol, Linear, Givmsh, Giveu, Nmsh, Xx,
+ Nudim, U, Nmax, Lwrkfl, Wrk, Lwrkin, Iwrk, Giveps,
+ Eps, Epsmin, Fsub, Dfsub, Gsub, Dgsub, Iflbvp)
\end{verbatim}
\begin{description}
\item{\tt Ncomp -} Integer, input. {\tt Ncomp} is the number of
first-order differential equations ($n$ in (\ref{eqn-prob1})),
and is the number of components of {\bf u} at each mesh point.
{\tt Ncomp} must be positive and less than 200.
\item{\tt Nlbc -} Integer, input. {\tt Nlbc} is the number of
boundary conditions at the left endpoint ($p$ in (\ref{eqn-prob1})).
{\tt Nlbc} must be nonnegative and must
not exceed {\tt Ncomp}. If ${\tt Nlbc} = {\tt Ncomp}$, all the
boundary conditions occur at the left endpoint,
so the problem is an initial value problem.
If {\tt Nlbc} is zero, all the boundary conditions occur at
the right endpoint.
\item{\tt Nucol - } Integer, input. {\tt Nucol}
is the declared column dimension
of the two-dimensional array {\tt U} used to store the computed solution
(see the discussion below of the parameter {\tt U}). {\tt Nucol} must be
positive, and is an upper bound on {\tt Nmax}, the maximum allowed
number of mesh points. In the specification of {\tt Nmax}, below, the
actual formula for computing {\tt Nmax} is given. In order to make full
use of the floating-point workspace, the user should select {\tt Nucol}
equal to {\tt Nmax}.
\item{\tt Aleft - } Floating-point, input. The left endpoint of
the interval of integration ($a$ in (\ref{eqn-prob1})).
\item{\tt Aright - } Floating-point, input. The right endpoint of the
interval of integration ($b$ in (\ref{eqn-prob1})).
{\tt Aright} must strictly exceed {\tt Aleft}.
\item{\tt Nfxpnt - } Integer, input. The number of ``fixed points'', i.e.,
points, in addition to the endpoints $a$ and $b$, that must be included in
every mesh. {\tt Nfxpnt} must be
nonnegative, and may be zero. If ${\tt Nfxpnt} = 0$, only the
two endpoints are required to appear in every mesh.
\item{\tt Fixpnt - } Floating-point array of size at least {\tt Nfxpnt},
input. If ${\tt Nfxpnt} = 0$, the {\tt Fixpnt}
array must still be declared, say as {\tt Dimension Fixpnt(1)},
but is never accessed. If ${\tt Nfxpnt} > 0$,
the {\tt Fixpnt} array contains
{\tt Nfxpnt} fixed points that the user wishes to be included in
every mesh. ${\tt Fixpnt}(1)$ must strictly exceed {\tt Aleft};
for $1\le i \le {\tt Nfxpnt}-1$,
${\tt Fixpnt}(i+1)$ must strictly exceed ${\tt Fixpnt}(i)$;
and ${\tt Fixpnt}({\tt Nfxpnt})$ must be strictly less than {\tt Aright}.
\item{\tt Ntol - } Integer, input. The number of tolerances
used to determine termination of {\tt ACDC}, i.e., the
number of components whose estimated accuracy is to be tested.
{\tt Ntol} must be positive.
\item{\tt Ltol - } Integer array of size {\tt Ntol}, input.
For each $i$, ${\tt Ltol}(i)$ gives the index of the component of the
computed solution ${\bf u}$ controlled by the $i$th tolerance.
For example, if ${\tt Ntol} = 2$, ${\tt Ltol}(1) = 2$
and ${\tt Ltol}(2)=3$, then component $2$ of ${\bf u}$ is controlled by
${\tt Tol}(1)$ and component $3$ is controlled by ${\tt Tol}(2)$;
see below for a description of {\tt Tol}.
Each element of {\tt Ltol} must be an integer between $1$ and {\tt Ncomp}.
\item{\tt Tol - } Floating-point array of size {\tt Ntol}, input.
For each $i$, ${\tt Tol}(i)$ gives the $i$th error tolerance used
in performing termination tests. For each $i = 1,\dots,{\tt Ntol}$,
the code attempts at each mesh point $x_k$ to approximate the true
(unknown) solution ${\bf u}(x_k)$ by a quantity ${\bf u}_k$ such that
\begin{equation}
{{|u_{j,k} - u_j(x_k)|}\over{\max(1, |u_{j,k}|)}}
< {\tt Tol}\,(i)
\label{eqn-errortest}
\end{equation}
for each $i = 1,\dots, {\tt Ntol}$ and $j = {\tt Ltol}(i)$,
where $u_{j,k}$ denotes component $j$ of ${\bf u}_k$. Relation (\ref{eqn-errortest})
is a mixed relative/absolute error criterion of the type normally
used for solving differential equations.
\item{\tt Linear - } Logical, input. If {\tt Linear} is {\tt .true.},
the problem is treated as linear. If {\tt Linear} is {\tt .false.},
the problem is solved as nonlinear. Note that different algorithmic
strategies are used for linear and nonlinear problems; hence, if one
solves the same linear problem twice, with {\tt Linear} set to
{\tt .true.} and then to {\tt .false.}, the computed
solutions and meshes may well be different, although
both solutions should satisfy the same overall error criterion.
\item{\tt Givmsh - } Logical, input. If {\tt Givmsh}
is {\tt .true.}, the user must
define two parameters: {\tt Nmsh} and the {\tt Xx} array;
see below. If {\tt Givmsh} is {\tt true.},
{\tt Nmsh} must contain the number of initial
mesh points, and {\tt Xx} must contain these
mesh points. If {\tt Givmsh} is {\tt .false.}, the user need not specify
{\tt Nmsh} or {\tt Xx}, which are chosen by default; see the explanations
below of {\tt Nmsh} and {\tt Xx}.
\item{\tt Giveu - } Logical, input. If {\tt Giveu}
is {\tt .false.}, the code sets the
initial trial solution at all mesh points to the constant
value {\tt Uval0}, which is contained in the labeled
common area {\tt Algprs} (see section \ref{rel-par}); the default
value of {\tt Uval0}, set in a block data routine, is zero. To change
{\tt Uval0}, the user should include the labeled common area {\tt Algprs} in the
calling routine and set {\tt Uval0} to the desired value.
If {\tt Giveu} is {\tt .true.}, {\tt Givmsh} must also be set to {\tt .true.}
When {\tt Giveu} is {\tt .true.}, the user must set {\tt Nmsh}
to the initial number of mesh points, {\tt Xx} to the initial
array of mesh points, and ${\tt U}(i,j)$, $i=1, \dots, {\tt Ncomp}$ and
$j = 1, \dots, {\tt Nmsh}$, to the initial trial
solution at these mesh points. However, if the first Newton procedure
fails with these values for {\tt Xx} and {\tt U}, the code reverts
to setting all components of the initial trial solution to {\tt Uval0}
for the next mesh.
\item{\tt Nmsh - } Integer, optional input and output.
If the parameter {\tt Givmsh}
is {\tt .true.}, the user must set {\tt Nmsh} to the positive initial
number of mesh points (including the two endpoints).
If {\tt Givmsh} is {\tt .false.}, the user need not set {\tt Nmsh}.
If {\tt Givmsh} is {\tt .false.}, the initial value of {\tt Nmsh} is set
to the greater of {\tt Nfxpnt}+2 and {\tt Nminit}, an integer in
the labeled common area {\tt Algprs} (the default value of
{\tt Nminit} is set in a block data routine to 7).
To specify another initial value for {\tt Nmsh} without specifying the
initial mesh points, the user can include the labeled common
{\tt Algprs} in the calling routine and set {\tt Nminit} to the desired
value.
On output, {\tt Nmsh} contains the final number of mesh points.
\item{\tt Xx - } Floating-point array, of size {\tt Nmax} (see below;
{\tt Nmax} cannot exceed {\tt Nucol}), optional input and output.
When {\tt Givmsh} is {\tt .false.}, the initial mesh {\tt Xx}
is defined as follows.
If ${\tt Nfxpnt} = 0$, the initial mesh contains {\tt Nmsh} points equally
spaced in $[{\tt Aleft}, {\tt Aright}]$. If ${\tt Nfxpnt} > 0$, the
initial mesh contains (if possible) a total of {\tt Nmsh} points. These points
are equally spaced in each subinterval $[{\tt Aleft}, {\tt Fixpnt}(1)]$,
$[{\tt Fixpnt}(1), {\tt Fixpnt}(2)]$, \dots,
$[{\tt Fixpnt}({\tt Nfxpnt}), {\tt Aright}]$.
If {\tt Givmsh} is {\tt .true.}, the user must define the {\tt Xx} array
on input as an initial mesh of strictly increasing values,
with ${\tt Xx}(1) = {\tt Aleft}$ and ${\tt Xx}({\tt Nmsh}) = {\tt Aright}$.
If ${\tt Nfxpnt} > 0$
and the user sets the initial mesh, the desired fixed points
{\em must} be included in the {\tt Xx} array, since the code performs
no tests to check for their inclusion!
If {\tt Givmsh} is {\tt .false.}, {\tt Nmsh} is set to the maximum
of {\tt Nfxpnt}+2
and {\tt Nminit} as defined in the labeled common area {\tt Algprs}.
On output, {\tt Xx} contains the final array of {\tt Nmsh} mesh points.
\item{\tt Nudim - } Integer, input. {\tt Nudim} is the declared row
dimension of the array {\tt U}. {\tt Nudim} must be greater than
or equal to {\tt Ncomp}.
\item{\tt U - } Floating-point array, of declared size
{\tt (Nudim, Nucol)}, and
of conceptual size {\tt (Ncomp, Nmsh)}, where {\tt Ncomp} is the number
of components and {\tt Nmsh} is the number of mesh points.
The {\tt U} array is an optional input parameter, and an output parameter.
If {\tt Giveu} (see above) is {\tt .false.}, the {\tt U}
array need not be set by the
user.
If {\tt Giveu} is {\tt .true.}, the user must provide an initial
array ${\tt U}(i,j)$, $i=1,\dots {\tt Ncomp}$ and
$j = 1, \dots {\tt Nmsh}$, corresponding to the
desired initial trial solution, where {\tt Nmsh} is the user-specified
number of initial mesh points. In this case, ${\tt U}(*,1)$ corresponds
to the estimated solution at {\tt Aleft}, and ${\tt U}(*, {\tt Nmsh})$
corresponds to the estimated solution at {\tt Aright}.
\item{\tt Nmax - } Integer, output. {\tt Nmax} is the maximum number of mesh
points possible with the given values of {\tt Ncomp}, {\tt Ntol},
{\tt Lwrkfl} (size of floating-point workspace),
{\tt Lwrkin} (size of integer workspace) and {\tt Nucol}.
(See below for the descriptions
of {\tt Lwrkfl} and {\tt Lwrkin}.) {\tt Nmax} can be no larger than
the input parameter {\tt Nucol}.
When the value of {\tt Lwrkfl} is much greater than ${\tt Ncomp*Ncomp}$,
the maximum
number of mesh points allowed by the floating-point workspace limit is
\[
{{{\tt Lwrkfl} - 14({\tt Ncomp*Ncomp}) -2{\tt Ntol} - 13{\tt Ncomp}} \over
4({\tt Ncomp*Ncomp}) + 10{\tt Ncomp} + 5 + {\tt Iden}}
\]
where, for linear problems, ${\tt Iden} = 0$ and, for nonlinear problems,
${\tt Iden} = {\tt Ncomp}$. When {\tt Lwrkin} is much greater than {\tt Ncomp},
the maximum number of mesh points allowed by the integer workspace limit is
$({\tt Lwrkin} - {\tt 3Ncomp})/({\tt Ncomp} + 2)$.
The value of {\tt Nmax} is calculated in {\tt ACDC}, and is not allowed
to exceed {\tt Nucol}. The user can determine the exact maximum
number of mesh points corresponding to specified values of {\tt Ncomp},
{\tt Lwrkfl} and {\tt Lwrkin} by calling {\tt ACDC} with
${\tt Nucol} = 1$ and the parameter {\tt Iprint} set to $1$; see below
for a discussion of {\tt Iprint}.
\item{\tt Lwrkfl - } Integer, input. The size of the user-provided
floating-point workspace array {\tt Wrk}.
\item{\tt Wrk - } Floating-point array of size {\tt Lwrkfl}, input.
User-provided floating-point workspace, used to store intermediate
values.
\item{\tt Lwrkin - } Integer, input. The size of the user-provided integer
workspace array {\tt Iwrk}.
\item{\tt Iwrk - } Integer array of size {\tt Lwrkin}, input. User-provided
integer workspace, used to store intermediate values.
\item{\tt Giveps - } Logical, input. Indicates whether the initial value
of {\tt Eps} (see below) is provided by the user. If {\tt Giveps} is {\tt .true.},
the user must specify the initial {\tt Eps} value.
\item{\tt Eps - } Floating-point, optional input and output.
The initial value of the continuation parameter. The user must define {\tt Eps}
if {\tt Giveps} is {\tt .true.} (if {\tt Giveps} is {\tt .false.},
{\tt Eps} takes the default starting value of ${\tt Eps} = 0.5$). For many
singular perturbation type problems, the choice of $ 0.1 < {\tt Eps} < 1 $
represents a (fairly) easy problem. The user should attempt to specify an
initial problem that is not `too' challenging. The code assumes that
${\tt Eps} = 1$ represents an `easy' problem. If {\tt Giveps} is {\tt .true.}
then {\tt Eps} must be initialised strictly less than one and greater then zero.
On output, {\tt Eps} contains the value used when solving the final continuation
problem.
\item{\tt Epsmin - } Floating-point, input.
The final value of {\tt Eps} for which the user would like to solve the
problem. {\tt Epsmin} must be less than or equal to {\tt Eps}.
\item{\tt Fsub - } Name of user-provided subroutine. {\tt Fsub}
{\em must} be declared
{\tt External} in the calling routine. {\tt Fsub} defines the function
{\bf f} in the formulation (\ref{eqn-prob1}) of the system of
first-order differential equations.
{\tt Fsub} must have the following declaration:
\begin{description}
\item{$\null$} {\tt Subroutine Fsub(Ncomp, X, U, F, Eps)}
\item{$\null$} {\tt Ncomp} (input to {\tt Fsub})
is the number of components of {\tt U};
\item{$\null$} {\tt X} (input to {\tt Fsub}) is a floating-point scalar;
\item{$\null$} {\tt U} (input to {\tt Fsub}) is a floating-point array
of size {\tt Ncomp};
\item{$\null$} {\tt F} (output from {\tt Fsub}) is a floating-point array
of dimension {\tt Ncomp}. On exit from {\tt Fsub}, the array
{\tt F} must contain the {\tt Ncomp}-dimensional vector {\tt F}
whose $i$th component
is the value of the $i$th component of the vector {\bf f} of (\ref{eqn-prob1})
evaluated at {\tt X}, {\tt U} and {\tt Eps};
\item{$\null$} {\tt Eps} (input to {\tt Fsub}) is a floating-point scalar.
\end{description}
\item{\tt Dfsub - } Name of user-provided subroutine. {\tt Dfsub}
{\em must} be
declared {\tt External} in the calling routine. {\tt Dfsub} calculates
the Jacobian matrix of {\tt F} as defined by the subroutine {\tt Fsub}.
{\tt Dfsub} must have the following declaration:
\begin{description}
\item{$\null$} {\tt Subroutine Dfsub(Ncomp, X, U, Df, Eps)}
\item{$\null$} {\tt Ncomp} (input to {\tt Dfsub}) is the number of
components of {\tt U};
\item{$\null$} {\tt X} (input to {\tt Dfsub}) is a floating-point scalar;
\item{$\null$} {\tt U} (input to {\tt Dfsub}) is a floating-point
array of dimension {\tt Ncomp};
\item{$\null$} {\tt Df} (output from {\tt Dfsub}) is an
{\tt Ncomp} by {\tt Ncomp} floating-point
array whose declared row dimension in the routine {\tt Dfsub}
must be {\tt Ncomp}. On exit from {\tt Dfsub}, the
array {\tt Df} must contain the {\tt Ncomp} by {\tt Ncomp} Jacobian matrix
of {\bf f} from (\ref{eqn-prob1}) ({\tt F} of {\tt Fsub})
with respect to {\bf u}, namely ${\tt Df}(i,j)$ is the partial derivative
of the $i$th function $f_i$ with respect to the $j$th component
of {\bf u};
\item{$\null$} {\tt Eps} (input to {\tt Fsub}) is a floating-point scalar.
\end{description}
\item{\tt Gsub - } Name of user-provided subroutine. {\tt Gsub}
{\em must} be declared {\tt External} in the calling routine.
{\tt Gsub} is called {\tt Ncomp} times
each time the boundary conditions are calculated;
the $i$th call to {\tt Gsub} defines the $i$th function
($g_{1,i}(\cdot)$ or $g_{2,i}(\cdot)$) in the boundary conditions
of (\ref{eqn-prob1}). {\tt Gsub} must have the following declaration:
\begin{description}
\item{$\null$} {\tt Subroutine Gsub(I, Ncomp, U, G, Eps)}
\item{$\null$} {\tt I} (input to {\tt Gsub}) is an integer
ranging from 1 to {\tt Ncomp};
\item{$\null$} {\tt Ncomp} (input to {\tt Gsub}) is the
number of components of {\tt U};
\item{$\null$} {\tt U} (input to {\tt Gsub}) is a floating-point
array of dimension {\tt Ncomp};
\item{$\null$} {\tt G} (output from {\tt Gsub}) is a floating-point scalar.
On exit from the $i$th call to {\tt Gsub}, the value of {\tt G} must
contain the value of the function $g_{1,i}$ (if $i \leq p$) or
$g_{2,i}$ (if $i > p$) from (\ref{eqn-prob1})
that defines the $i$th boundary condition evaluated at {\bf u};
\item{$\null$} {\tt Eps} (input to {\tt Fsub}) is a floating-point scalar.
\end{description}
\item{\tt Dgsub - } Name of user-provided subroutine. {\tt Dgsub}
{\em must} be declared {\tt External} in the calling routine.
{\tt Dgsub} calculates the Jacobian matrices corresponding to the functions
$g_{1,i}$, $g_{2,i}$ of (\ref{eqn-prob1}) and {\tt Gsub} that define the
boundary conditions. {\tt Dgsub} must have the following declaration:
\begin{description}
\item{$\null$} {\tt Subroutine Dgsub(I, Ncomp, U, Dg, Eps)}
\item{$\null$} {\tt I} (input to {\tt Dgsub}) is an integer ranging from
1 to {\tt Ncomp};
\item{$\null$} {\tt Ncomp} (input to {\tt Dgsub}) is the number
of components of {\tt U};
\item{$\null$} {\tt U} (input to {\tt Dgsub}) is a floating-point
array of dimension {\tt Ncomp};
\item{$\null$} {\tt Dg} (output from {\tt Dgsub}) is a floating-point
array of dimension {\tt Ncomp}.
On exit from the $i$th call of {\tt Dgsub}, the
vector {\tt Dg} must contain the {\tt Ncomp} partial derivatives of the
$i$th function, $g_{1,i}$ or $g_{2,i}$, of (\ref{eqn-prob1}) with respect
to {\bf u};
\item{$\null$} {\tt Eps} (input to {\tt Fsub}) is a floating-point scalar.
\end{description}
\item{\tt Iflbvp - } Integer, output. {\tt Iflbvp} indicates the result of
{\tt ACDC}. If the routine has terminated with apparent success,
${\tt Iflbvp} = 0$. If one of the input parameters is invalid,
${\tt Iflbvp} = -1$. If the number of mesh points needed for the
next iteration would exceed {\tt Nmax}, then ${\tt Iflbvp} = 1$.
\end{description}
\section{Related parameters}\label{rel-par}
Some other parameters that may be of interest to the user, but do
not occur in the
formal declaration of {\tt ACDC}, are stored in the labeled common
area {\tt Algprs}, whose declaration is
\begin{verbatim}
Common/Algprs/ Nminit, Iprint, Maxcon, Itsaim, Uval0
\end{verbatim}
Any of the parameters in {\tt Algprs} may be changed by the user
by including this labeled common area in the calling routine
and setting the value as desired.
The value of the integer {\tt Nminit} is discussed above under the
formal parameter {\tt Nmsh}. {\tt Nminit}
specifies the default initial number of mesh points, and, if not
altered, is set to $7$.
{\tt Iprint} is an integer variable controlling the amount of
non-debug printout. Its default value is zero, which means that
some intermediate printing occurs (details of continuation steps,
number of Newton iterations, size of mesh). If {\tt Iprint} is set to $1$,
more printing occurs. If {\tt Iprint} is set to $-1$, no printing at
all occurs in {\tt ACDC}. Values of {\tt Iprint} other than $0$, $1$
and $-1$ are invalid.
{\tt Maxcon} is an integer variable which indicates the maximum number of
continuation steps to be taken when attempting to solve a particular problem.
The default value is ${\tt Maxcon} = 50$.
{\tt Itsaim} is an integer variable, used only for nonlinear problems.
The continuation steps are chosen with the aim that the number of
Newton iterations required for convergence on the first mesh, for each
continuation problem, is less than or equal to {\tt Itsaim} (see
\cite{CaMoWr2} for more details). The default value is ${\tt Itsaim} = 7$.
The user should note that small values of {\tt Itsaim} (e.g. ${\tt Itsaim} = 1,2$)
may restrict the size of the continuation steps significantly.
{\tt Uval0} is a floating-point value that defines the initial
value of the trial solution when {\tt Giveu} is {\tt .false.}, or in some
instances when an intermediate Newton process fails. Unless changed
by the user, the default value of {\tt Uval0} is zero. The user may
wish to change {\tt Uval0} if ${\bf u}={\bf 0}$ is inappropriate for some
reason---for example, the function {\bf f} in (\ref{eqn-prob1})
is undefined for ${\bf u}={\bf 0}$.
The user should also look at the routine {\tt D1mach} (which is provided
automatically via netlib). The variables specified in this routine
describe machine precision and may need to be changed depending on
which machine is being used.
\section{Sample problems}
\subsection{Mathematical formulation}
We consider two second-order boundary value problems, one linear and
one nonlinear, parameterized in terms of $\epsilon$. The linear problem
is
\begin{equation}
\label{eqn-samprob}
\begin{array}{c}
\epsilon y'' - y = -(\epsilon \pi^2 + 1) \cos(\pi x), \;\;\;\;\; -1 \leq x \leq 1, \\
y(-1) = 0, \;\;\; y(1) = 0.
\end{array}
\end{equation}
As $\epsilon$ decreases toward zero, (\ref{eqn-samprob}) becomes increasingly difficult
to solve numerically as boundary layers develop at $x=-1$ and $x=1$.
In order to apply {\ACDC} to (\ref{eqn-samprob}), it must be converted to a system
of two first-order equations: for example
\begin{eqnarray}
\label{eqn-newprob}
\begin{array}{rcl}
u'_1 & = & u_2, \\
u'_2 & = & (u_1 -(\epsilon \pi^2 + 1) \cos(\pi x))/ \epsilon,
\end{array} & & \;\;\; u_1(-1) = u_1(1) = 0.
\end{eqnarray}
The nonlinear problem is the Lagerstrom-Cole model problem \cite{Co}
\begin{equation}
\label{eqn-samprob1}
\begin{array}{c}
\epsilon y'' + yy' - y = 0, \;\;\;\;\; 0 \leq x \leq 1, \\
y(0) = 1, \;\;\; y(1) = -1/3.
\end{array}
\end{equation}
As $\epsilon$ decreases toward zero, the solution of (\ref{eqn-samprob1}) develops
boundary layers at $x=0$ and $x=1$. Problem (\ref{eqn-samprob1}) can be converted to
first-order form as follows
\begin{eqnarray}
\label{eqn-newprob1}
\begin{array}{rcl}
u'_1 & = & u_2, \\
u'_2 & = & (u_1 - u_1 u_2)/ \epsilon,
\end{array} & & \;\;\; u_1(0) = 1, \;\;\; u_1(1) = -1/3.
\end{eqnarray}
Suppose now that we wish to solve problems (\ref{eqn-newprob}) and
(\ref{eqn-newprob1}) with $\epsilon = 10^{-7}$, and to achieve
an accuracy of approximately $10^{-8}$ in the value of $u_1$ and
an accuracy of $10^{-4}$ in the value of $u_2$. We will not provide
an initial mesh nor an initial guess for the solution. The problems
are to be solved on a machine with IEEE arithmetic, and double precision
is used (approximately 16 decimal digits).
\subsection{Sample FORTRAN routines}
The following {\small FORTRAN} 77 main program calls {\tt ACDC} with the
user-specified parameters given above. The subroutines {\tt Fsub},
{\tt Dfsub}, {\tt Gsub} and {\tt Dgsub} define the functions {\bf f}
and the boundary conditions ${\bf g}_1$ and ${\bf g}_2$ for problems
(\ref{eqn-newprob}) and (\ref{eqn-newprob1}).
{\small
\begin{verbatim}
Program Runacdc
Implicit Double Precision(A-H,O-Z)
Parameter(Lwrkfl = 500000)
Parameter(Lwrkin = 50000)
Dimension Wrk(Lwrkfl),Iwrk(Lwrkin)
Dimension U(2,12200),Tol(2),Ltol(2),Xx(12200),Fixpnt(1)
Logical Linear, Giveu, Givmsh, Giveps
External Fsub, Dfsub, Gsub, Dgsub
Common /Prob/ Linnon
Common /Valpi/ Pi
Pi = 4.0d0*Atan(1.0d0)
C.... *****************************************************************
C.... This Driver Is Set Up To Run Two Problems, One Linear And One
C.... Nonlinear.
C.... The Linear Test Problem (Which Has Boundary Layers At X = -1
C.... And At X = 1) Is
C.... Eps*Y'' - Y = -(Eps*Pi*Pi + 1)*Cos(Pi*X), Y(-1) = Y(1) = 0.
C.... The Nonlinear Test Problem (Which Has Boundary Layers At X = 0
C.... And At X = 1) Is
C.... Eps*Y'' + Y*Y' - Y = 0, Y(0) = 1, Y(1) = -1/3.
C.... Acdc Solves First Order Systems Of Differential Equations, Thus
C.... Both Problems Are Converted To First Order Form In Subroutine
C.... Fsub Below.
C.... *****************************************************************
C.... Specify The Number of Components And The Desired Final Eps Value.
Ncomp = 2
Epsmin = 1.d-7
C.... Ntol Is The Number Of Tolerances
Ntol = 2
Tol(1) = 1.d-8
Tol(2) = 1.d-4
Ltol(1) = 1
Ltol(2) = 2
C.... The User May Choose A Linear Or Nonlinear Test Problem
C.... (0 = Linear, 1 = Nonlinear).
10 Write(*,1000)
Read*, Linnon
C.... Specify The Boundary Points
If (Linnon .eq. 1) Then
Aleft = 0.d0
Aright = 1.0d0
Else If (Linnon .eq. 0) Then
Aleft = -1.0d0
Aright = 1.0d0
Else
Write(*,2000)
Goto 10
Endif
If (Linnon .eq. 1) Then
Linear = .false.
Else
Linear = .true.
Endif
Nudim = 2
Nlbc = 1
Nfxpnt = 0
Nucol = 12200
Nmsh = 0
Giveu = .false.
Givmsh = .false.
Giveps = .false.
Call Acdc(Ncomp, Nlbc, Nucol, Aleft, Aright, Nfxpnt, Fixpnt,
+ Ntol, Ltol, Tol, Linear, Givmsh, Giveu, Nmsh, Xx,
+ Nudim, U, Nmax, Lwrkfl, Wrk, Lwrkin, Iwrk, Giveps,
+ Eps, Epsmin, Fsub, Dfsub, Gsub, Dgsub, Iflbvp)
C-----------------------------------------------------------------------
1000 Format(//,'Choose A Test Problem (0 = Linear, 1 = Nonlinear).')
2000 Format(/, '** Only 0 or 1 is allowed.')
C-----------------------------------------------------------------------
End
Subroutine Fsub(Ncomp,X,Z,F,Eps)
Implicit Double Precision(A-H,O-Z)
Dimension Z(*),F(*)
Common /Prob/ Linnon
Common /Valpi/ Pi
If (Linnon .eq. 0) Then
Pix = Pi*X
F(1) = Z(2)
F(2) = (Z(1)-Eps*Pi*Pi*Cos(Pix)-Cos(Pix))/Eps
Else
F(1) = Z(2)
F(2) = (Z(1)*(1.d0-Z(2)))/Eps
Endif
Return
End
Subroutine Dfsub(Ncomp,X,Z,Df,Eps)
Implicit Double Precision(A-H,O-Z)
Dimension Z(*),Df(Ncomp,*)
Common /Prob/ Linnon
If (Linnon .eq. 0) Then
Df(1,1) = 0.d0
Df(1,2) = 1.0d0
Df(2,1) = 1.0d0/Eps
Df(2,2) = 0.0d0
Else
Df(1,1) = 0.d0
Df(1,2) = 1.0d0
Df(2,1) = (1.d0-Z(2))/Eps
Df(2,2) = -Z(1)/Eps
Endif
Return
End
Subroutine Gsub(I,Ncomp,Z,G,Eps)
Implicit Double Precision(A-H,O-Z)
Dimension Z(*)
Common /Prob/ Linnon
If (Linnon .eq. 0) Then
G = Z(1)
Else
If (I .eq. 1) G = Z(1)-1.d0
If (I .eq. 2) G = Z(1)+1.d0/3.d0
Endif
Return
End
Subroutine Dgsub(I,Ncomp,Z,Dg,Eps)
Implicit Double Precision(A-H,O-Z)
Dimension Z(*),Dg(*)
Dg(1) = 1.d0
Dg(2) = 0.d0
Return
End
\end{verbatim} }
\subsection{Sample output}
The complete output produced by running the linear example on a Pentium
with 100 MHz clock speed, under Linux, with binary IEEE arithmetic, is
given next.
{\small
\begin{verbatim}
The Number Of (Linear) Differential Equations Is 2
Left Boundary Point = -0.1000E+01, Right Boundary Point = 0.1000E+01
Components Of U Requiring Tolerances - 1 2
Corresponding Error Tolerances - 0.10E-07 0.10E-03
The Initial Value Of Epsilon Is 0.0000E+00
The Desired Final Value Of Epsilon Is 0.1000E-06
**********************************************************************************
Continuation Step 1, Epsilon = .5000E+00
**********************************************************************************
The New Mesh Contains 7 Points.
The New Mesh Contains 19 Points.
**********************************************************************************
Continuation Step 2, Epsilon = .1172E+00
**********************************************************************************
The New Mesh Contains 19 Points.
The New Mesh Contains 29 Points.
**********************************************************************************
Continuation Step 3, Epsilon = .1156E-01
**********************************************************************************
The New Mesh Contains 29 Points.
The New Mesh Contains 47 Points.
**********************************************************************************
Continuation Step 4, Epsilon = .4674E-03
**********************************************************************************
The New Mesh Contains 49 Points.
The New Mesh Contains 97 Points.
**********************************************************************************
Continuation Step 5, Epsilon = .6238E-05
**********************************************************************************
The New Mesh Contains 99 Points.
The New Mesh Contains 163 Points.
**********************************************************************************
Continuation Step 6, Epsilon = .1000E-06
**********************************************************************************
The New Mesh Contains 170 Points.
The New Mesh Contains 265 Points.
$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$
Tolerances Satisfied For Final Problem Epsilon = .1000E-06
$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$
The Final Mesh And Solution Components Are:
I X(I) U( 1) U( 2)
1 -0.10000000E+01 0.00000000E+00 -0.31622777E+04
9 -0.99938272E+00 -0.85801161E+00 -0.44899467E+03
17 -0.99830247E+00 -0.99532263E+00 -0.14729424E+02
25 -0.99598765E+00 -0.99991747E+00 0.29835583E-01
33 -0.98148148E+00 -0.99830816E+00 0.18266737E+00
41 -0.94444444E+00 -0.98480775E+00 0.54553184E+00
49 -0.88194444E+00 -0.93200787E+00 0.11386329E+01
57 -0.82638889E+00 -0.85491187E+00 0.16297730E+01
65 -0.74074074E+00 -0.68624164E+00 0.22851119E+01
73 -0.66666667E+00 -0.50000000E+00 0.27206973E+01
81 -0.55555556E+00 -0.17364818E+00 0.30938655E+01
89 -0.44444444E+00 0.17364818E+00 0.30938655E+01
97 -0.33333333E+00 0.50000000E+00 0.27206994E+01
105 -0.25000000E+00 0.70710678E+00 0.22214416E+01
113 -0.19444444E+00 0.81915204E+00 0.18019435E+01
121 -0.12962963E+00 0.91821611E+00 0.12443210E+01
129 -0.55555556E-01 0.98480776E+00 0.54553370E+00
137 0.55555556E-01 0.98480776E+00 -0.54553370E+00
145 0.12962963E+00 0.91821611E+00 -0.12443210E+01
153 0.19444444E+00 0.81915204E+00 -0.18019435E+01
161 0.25000000E+00 0.70710678E+00 -0.22214416E+01
169 0.33333333E+00 0.50000000E+00 -0.27206994E+01
177 0.44444444E+00 0.17364818E+00 -0.30938655E+01
185 0.55555556E+00 -0.17364818E+00 -0.30938655E+01
193 0.66666667E+00 -0.50000000E+00 -0.27206973E+01
201 0.74074074E+00 -0.68624164E+00 -0.22851119E+01
209 0.82638889E+00 -0.85491187E+00 -0.16297730E+01
217 0.88194444E+00 -0.93200787E+00 -0.11386329E+01
225 0.94444444E+00 -0.98480775E+00 -0.54553184E+00
233 0.98148148E+00 -0.99830816E+00 -0.18266737E+00
241 0.99598765E+00 -0.99991747E+00 -0.29835583E-01
249 0.99830247E+00 -0.99532263E+00 0.14729424E+02
257 0.99938272E+00 -0.85801161E+00 0.44899467E+03
265 0.10000000E+01 -0.11102230E-15 0.31622777E+04
$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$
\end{verbatim}}
\noindent Finally, the complete output produced by running the nonlinear example
is given next.
{\small
\begin{verbatim}
The Number Of (Nonlinear) Differential Equations Is 2
Left Boundary Point = 0.0000E+00, Right Boundary Point = 0.1000E+01
Components Of U Requiring Tolerances - 1 2
Corresponding Error Tolerances - 0.10E-07 0.10E-03
The Initial Value Of Epsilon Is 0.0000E+00
The Desired Final Value Of Epsilon Is 0.1000E-06
**********************************************************************************
Continuation Step 1, Epsilon = .5000E+00
**********************************************************************************
The New Mesh Contains 7 Points.
Newton Converged After 4 Iterations.
The New Mesh Contains 14 Points.
Newton Converged After 2 Iterations.
**********************************************************************************
Continuation Step 2, Epsilon = .1088E+00
**********************************************************************************
The New Mesh Contains 14 Points.
Newton Converged After 4 Iterations.
The New Mesh Contains 25 Points.
Newton Converged After 2 Iterations.
**********************************************************************************
Continuation Step 3, Epsilon = .1454E-01
**********************************************************************************
The New Mesh Contains 25 Points.
Newton Converged After 5 Iterations.
The New Mesh Contains 45 Points.
Newton Converged After 3 Iterations.
**********************************************************************************
Continuation Step 4, Epsilon = .1512E-02
**********************************************************************************
The New Mesh Contains 52 Points.
Newton Converged After 5 Iterations.
The New Mesh Contains 93 Points.
Newton Converged After 3 Iterations.
**********************************************************************************
Continuation Step 5, Epsilon = .6297E-04
**********************************************************************************
The New Mesh Contains 97 Points.
Newton Converged After 7 Iterations.
The New Mesh Contains 137 Points.
Newton Converged After 4 Iterations.
**********************************************************************************
Continuation Step 6, Epsilon = .4135E-05
**********************************************************************************
The New Mesh Contains 136 Points.
Newton Converged After 7 Iterations.
The New Mesh Contains 148 Points.
Newton Converged After 4 Iterations.
**********************************************************************************
Continuation Step 7, Epsilon = .2242E-06
**********************************************************************************
The New Mesh Contains 144 Points.
Newton Converged After 8 Iterations.
The New Mesh Contains 160 Points.
Newton Converged After 4 Iterations.
**********************************************************************************
Continuation Step 8, Epsilon = .1000E-06
**********************************************************************************
The New Mesh Contains 155 Points.
Newton Converged After 5 Iterations.
The New Mesh Contains 155 Points.
Newton Converged After 2 Iterations.
$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$
Tolerances Satisfied For Final Problem Epsilon = .1000E-06
$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$
The Final Mesh And Solution Components Are:
I X(I) U( 1) U( 2)
1 0.00000000E+00 0.10000000E+01 -0.50000154E+07
6 0.89306127E-07 0.69130828E+00 -0.23895503E+07
11 0.23814967E-06 0.45646312E+00 -0.10418068E+07
16 0.53583676E-06 0.27179618E+00 -0.36937865E+06
21 0.10716735E-05 0.15726784E+00 -0.12367760E+06
26 0.21433471E-05 0.85339290E-01 -0.36424475E+05
31 0.35722451E-05 0.53005979E-01 -0.14057720E+05
36 0.58942044E-05 0.32799257E-01 -0.53875483E+04
41 0.96450617E-05 0.20287509E-01 -0.20655486E+04
46 0.17361111E-04 0.11346948E-01 -0.65024502E+03
51 0.32150206E-04 0.61182743E-02 -0.19243132E+03
56 0.64300412E-04 0.30018785E-02 -0.48967751E+02
61 0.13503086E-03 0.13337598E-02 -0.11413349E+02
66 0.38580247E-03 0.32177274E-03 -0.13882489E+01
71 0.96450617E-03 0.39815739E-04 -0.13124727E+00
76 0.23148148E-02 0.53445190E-06 -0.16910396E-02
81 0.12345679E-01 0.20663484E-10 0.70571492E-07
86 0.97916667E+00 0.11100243E-10 0.14394748E-06
91 0.99727183E+00 -0.14439046E-06 -0.45667229E-03
96 0.99872449E+00 -0.14488910E-04 -0.46520377E-01
101 0.99955357E+00 -0.24946212E-03 -0.10085896E+01
106 0.99982639E+00 -0.98683605E-03 -0.69413046E+01
111 0.99992560E+00 -0.25587118E-02 -0.36355512E+02
116 0.99996280E+00 -0.52196620E-02 -0.14118146E+03
121 0.99998140E+00 -0.10371396E-01 -0.54413033E+03
126 0.99998863E+00 -0.16680517E-01 -0.13984420E+04
131 0.99999339E+00 -0.27703369E-01 -0.38456383E+04
136 0.99999656E+00 -0.49434327E-01 -0.12228175E+05
141 0.99999816E+00 -0.82054068E-01 -0.33674775E+05
146 0.99999920E+00 -0.14246979E+00 -0.10149974E+06
151 0.99999977E+00 -0.24106495E+00 -0.29057413E+06
155 0.10000000E+01 -0.33333333E+00 -0.55556878E+06
$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$
\end{verbatim}}
\begin{thebibliography}{99}
\bibitem{AMR}
U.\ Ascher, R.\ M.\ M.\ Mattheij, and R.\ D.\ Russell,
{\it Numerical Solution of Boundary Value Problems for Ordinary
Differential Equations},
Prentice-Hall, Englewood Cliffs, NJ, 1988.
\bibitem{AsRu}
U.\ Ascher and R.\ D.\ Russell (1981),
Reformulation of boundary value problems into `standard' form,
{\sl SIAM Review}\ 23, 238-254.
\bibitem{CW2}
J.\ R.\ Cash and M.\ H.\ Wright (1991),
A deferred correction method for nonlinear two-point boundary
value problems: Implementation and numerical evaluation,
{\sl SIAM J.\ Sci.\ Stat.\ Comput.}\ 12, 971--989.
\bibitem{CaWr}
J.\ R.\ Cash and M.\ H.\ Wright (1995),
{\sl The code {\rm twpbvp.f} under the directory ode of netlib. The code can be
down-loaded from} {\tt http://www.netlib.no/netlib/ode/}.
\bibitem{CaMoWr1}
J.\ R.\ Cash, G.\ Moore and R.\ W.\ Wright (1995),
An automatic continuation strategy for the solution of singularly perturbed
linear two-point boundary value problems,
{\sl J.\ Comp.\ Phys.}\ 122, 266--279.
\bibitem{CaMoWr2}
J.\ R.\ Cash, G.\ Moore and R.\ W.\ Wright (1996),
An automatic continuation strategy for the solution of singularly perturbed
nonlinear two-point boundary value problems,
{\sl To appear}
\bibitem{Co}
J.\ D. Cole,
{\it Perturbation Methods in Applied Mathematics},
Blaisdell, Waltham, MA, 1968.
\bibitem{Si}
H.\ H.\ M.\ Silva,
{\it Iterated Deferred Correction Schemes for the Numerical Solution of
Two-Point Boundary Value Problems.}
PhD thesis, Imperial College, London, 1994.
\end{thebibliography}
\end{document}