# NAG Library Routine Document

## 1Purpose

d05baf computes the solution of a nonlinear convolution Volterra integral equation of the second kind using a reducible linear multi-step method.

## 2Specification

Fortran Interface
 Subroutine d05baf ( ck, cg, cf, alim, tlim, yn, tol, work, lwk,
 Integer, Intent (In) :: iorder, nmesh, lwk Integer, Intent (Inout) :: ifail Real (Kind=nag_wp), External :: ck, cg, cf Real (Kind=nag_wp), Intent (In) :: alim, tlim, tol, thresh Real (Kind=nag_wp), Intent (Out) :: yn(nmesh), errest(nmesh), work(lwk) Character (1), Intent (In) :: method
#include nagmk26.h
 void d05baf_ (double (NAG_CALL *ck)(const double *t),double (NAG_CALL *cg)(const double *s, const double *y),double (NAG_CALL *cf)(const double *t),const char *method, const Integer *iorder, const double *alim, const double *tlim, double yn[], double errest[], const Integer *nmesh, const double *tol, const double *thresh, double work[], const Integer *lwk, Integer *ifail, const Charlen length_method)

## 3Description

d05baf computes the numerical solution of the nonlinear convolution Volterra integral equation of the second kind
 $yt=ft+∫atkt-sgs,ysds, a≤t≤T.$ (1)
It is assumed that the functions involved in (1) are sufficiently smooth. The routine uses a reducible linear multi-step formula selected by you to generate a family of quadrature rules. The reducible formulae available in d05baf are the Adams–Moulton formulae of orders $3$ to $6$, and the backward differentiation formulae (BDF) of orders $2$ to $5$. For more information about the behaviour and the construction of these rules we refer to Lubich (1983) and Wolkenfelt (1982).
The algorithm is based on computing the solution in a step-by-step fashion on a mesh of equispaced points. The initial step size which is given by $\left(T-a\right)/N$, $N$ being the number of points at which the solution is sought, is halved and another approximation to the solution is computed. This extrapolation procedure is repeated until successive approximations satisfy a user-specified error requirement.
The above methods require some starting values. For the Adams' formula of order greater than $3$ and the BDF of order greater than $2$ we employ an explicit Dormand–Prince–Shampine Runge–Kutta method (see Shampine (1986)). The above scheme avoids the calculation of the kernel, $k\left(t\right)$, on the negative real line.
Lubich Ch (1983) On the stability of linear multi-step methods for Volterra convolution equations IMA J. Numer. Anal. 3 439–465
Shampine L F (1986) Some practical Runge–Kutta formulas Math. Comput. 46(173) 135–150
Wolkenfelt P H M (1982) The construction of reducible quadrature rules for Volterra integral and integro-differential equations IMA J. Numer. Anal. 2 131–152

## 5Arguments

1:     $\mathbf{ck}$ – real (Kind=nag_wp) Function, supplied by the user.External Procedure
ck must evaluate the kernel $k\left(t\right)$ of the integral equation (1).
The specification of ck is:
Fortran Interface
 Function ck ( t)
 Real (Kind=nag_wp) :: ck Real (Kind=nag_wp), Intent (In) :: t
#include nagmk26.h
 double ck (const double *t)
1:     $\mathbf{t}$ – Real (Kind=nag_wp)Input
On entry: $t$, the value of the independent variable.
ck must either be a module subprogram USEd by, or declared as EXTERNAL in, the (sub)program from which d05baf is called. Arguments denoted as Input must not be changed by this procedure.
Note: ck should not return floating-point NaN (Not a Number) or infinity values, since these are not handled by d05baf. If your code inadvertently does return any NaNs or infinities, d05baf is likely to produce unexpected results.
2:     $\mathbf{cg}$ – real (Kind=nag_wp) Function, supplied by the user.External Procedure
cg must evaluate the function $g\left(s,y\left(s\right)\right)$ in (1).
The specification of cg is:
Fortran Interface
 Function cg ( s, y)
 Real (Kind=nag_wp) :: cg Real (Kind=nag_wp), Intent (In) :: s, y
#include nagmk26.h
 double cg (const double *s, const double *y)
1:     $\mathbf{s}$ – Real (Kind=nag_wp)Input
On entry: $s$, the value of the independent variable.
2:     $\mathbf{y}$ – Real (Kind=nag_wp)Input
On entry: the value of the solution $y$ at the point s.
cg must either be a module subprogram USEd by, or declared as EXTERNAL in, the (sub)program from which d05baf is called. Arguments denoted as Input must not be changed by this procedure.
Note: cg should not return floating-point NaN (Not a Number) or infinity values, since these are not handled by d05baf. If your code inadvertently does return any NaNs or infinities, d05baf is likely to produce unexpected results.
3:     $\mathbf{cf}$ – real (Kind=nag_wp) Function, supplied by the user.External Procedure
cf must evaluate the function $f\left(t\right)$ in (1).
The specification of cf is:
Fortran Interface
 Function cf ( t)
 Real (Kind=nag_wp) :: cf Real (Kind=nag_wp), Intent (In) :: t
#include nagmk26.h
 double cf (const double *t)
1:     $\mathbf{t}$ – Real (Kind=nag_wp)Input
On entry: $t$, the value of the independent variable.
cf must either be a module subprogram USEd by, or declared as EXTERNAL in, the (sub)program from which d05baf is called. Arguments denoted as Input must not be changed by this procedure.
Note: cf should not return floating-point NaN (Not a Number) or infinity values, since these are not handled by d05baf. If your code inadvertently does return any NaNs or infinities, d05baf is likely to produce unexpected results.
4:     $\mathbf{method}$ – Character(1)Input
On entry: the type of method which you wish to employ.
${\mathbf{method}}=\text{'A'}$
${\mathbf{method}}=\text{'B'}$
For backward differentiation formulae.
Constraint: ${\mathbf{method}}=\text{'A'}$ or $\text{'B'}$.
5:     $\mathbf{iorder}$ – IntegerInput
On entry: the order of the method to be used.
Constraints:
• if ${\mathbf{method}}=\text{'A'}$, $3\le {\mathbf{iorder}}\le 6$;
• if ${\mathbf{method}}=\text{'B'}$, $2\le {\mathbf{iorder}}\le 5$.
6:     $\mathbf{alim}$ – Real (Kind=nag_wp)Input
On entry: $a$, the lower limit of the integration interval.
Constraint: ${\mathbf{alim}}\ge 0.0$.
7:     $\mathbf{tlim}$ – Real (Kind=nag_wp)Input
On entry: the final point of the integration interval, $T$.
Constraint: ${\mathbf{tlim}}>{\mathbf{alim}}$.
8:     $\mathbf{yn}\left({\mathbf{nmesh}}\right)$ – Real (Kind=nag_wp) arrayOutput
On exit: ${\mathbf{yn}}\left(\mathit{i}\right)$ contains the most recent approximation of the true solution $y\left(t\right)$ at the specified point $t={\mathbf{alim}}+\mathit{i}×H$, for $\mathit{i}=1,2,\dots ,{\mathbf{nmesh}}$, where $H=\left({\mathbf{tlim}}-{\mathbf{alim}}\right)/{\mathbf{nmesh}}$.
9:     $\mathbf{errest}\left({\mathbf{nmesh}}\right)$ – Real (Kind=nag_wp) arrayOutput
On exit: ${\mathbf{errest}}\left(\mathit{i}\right)$ contains the most recent approximation of the relative error in the computed solution at the point $t={\mathbf{alim}}+\mathit{i}×H$, for $\mathit{i}=1,2,\dots ,{\mathbf{nmesh}}$, where $H=\left({\mathbf{tlim}}-{\mathbf{alim}}\right)/{\mathbf{nmesh}}$.
10:   $\mathbf{nmesh}$ – IntegerInput
On entry: the number of equidistant points at which the solution is sought.
Constraints:
• if ${\mathbf{method}}=\text{'A'}$, ${\mathbf{nmesh}}\ge {\mathbf{iorder}}-1$;
• if ${\mathbf{method}}=\text{'B'}$, ${\mathbf{nmesh}}\ge {\mathbf{iorder}}$.
11:   $\mathbf{tol}$ – Real (Kind=nag_wp)Input
On entry: the relative accuracy required in the computed values of the solution.
Constraint: $\sqrt{\epsilon }\le {\mathbf{tol}}\le 1.0$, where $\epsilon$ is the machine precision.
12:   $\mathbf{thresh}$ – Real (Kind=nag_wp)Input
On entry: the threshold value for use in the evaluation of the estimated relative errors. For two successive meshes the following condition must hold at each point of the coarser mesh
 $Y1-Y2 maxY1,Y2,thresh ≤tol,$
where ${Y}_{1}$ is the computed solution on the coarser mesh and ${Y}_{2}$ is the computed solution at the corresponding point in the finer mesh. If this condition is not satisfied then the step size is halved and the solution is recomputed.
Note: thresh can be used to effect a relative, absolute or mixed error test. If ${\mathbf{thresh}}=0.0$ then pure relative error is measured and, if the computed solution is small and ${\mathbf{thresh}}=1.0$, absolute error is measured.
13:   $\mathbf{work}\left({\mathbf{lwk}}\right)$ – Real (Kind=nag_wp) arrayOutput
14:   $\mathbf{lwk}$ – IntegerInput
On entry: the dimension of the array work as declared in the (sub)program from which d05baf is called.
Constraint: ${\mathbf{lwk}}\ge 10×{\mathbf{nmesh}}+6$.
Note: the above value of lwk is sufficient for d05baf to perform only one extrapolation on the initial mesh as defined by nmesh. In general much more workspace is required and in the case when a large step size is supplied (i.e., nmesh is small), you must provide a considerably larger workspace.
On exit: if ${\mathbf{ifail}}={\mathbf{5}}$ or ${\mathbf{6}}$, ${\mathbf{work}}\left(1\right)$ contains the size of lwk required for the algorithm to proceed further.
15:   $\mathbf{ifail}$ – IntegerInput/Output
On entry: ifail must be set to $0$, $-1\text{​ or ​}1$. If you are unfamiliar with this argument you should refer to Section 3.4 in How to Use the NAG Library and its Documentation for details.
For environments where it might be inappropriate to halt program execution when an error is detected, the value $-1\text{​ or ​}1$ is recommended. If the output of error messages is undesirable, then the value $1$ is recommended. Otherwise, if you are not familiar with this argument, the recommended value is $0$. When the value $-\mathbf{1}\text{​ or ​}\mathbf{1}$ is used it is essential to test the value of ifail on exit.
On exit: ${\mathbf{ifail}}={\mathbf{0}}$ unless the routine detects an error or a warning has been flagged (see Section 6).

## 6Error Indicators and Warnings

If on entry ${\mathbf{ifail}}=0$ or $-1$, explanatory error messages are output on the current error message unit (as defined by x04aaf).
Errors or warnings detected by the routine:
${\mathbf{ifail}}=1$
 On entry, ${\mathbf{method}}\ne \text{'A'}$ or $\text{'B'}$, or ${\mathbf{iorder}}<2$ or ${\mathbf{iorder}}>6$, or ${\mathbf{method}}=\text{'A'}$ and ${\mathbf{iorder}}=2$, or ${\mathbf{method}}=\text{'B'}$ and ${\mathbf{iorder}}=6$, or ${\mathbf{alim}}<0.0$, or ${\mathbf{tlim}}\le {\mathbf{alim}}$, or ${\mathbf{tol}}<\sqrt{\epsilon }$ or ${\mathbf{tol}}>1.0$, where $\epsilon$ is the machine precision.
${\mathbf{ifail}}=2$
 On entry, ${\mathbf{nmesh}}\le {\mathbf{iorder}}-2$, when ${\mathbf{method}}=\text{'A'}$, or ${\mathbf{nmesh}}\le {\mathbf{iorder}}-1$, when ${\mathbf{method}}=\text{'B'}$.
${\mathbf{ifail}}=3$
 On entry, ${\mathbf{lwk}}<10×{\mathbf{nmesh}}+6$.
${\mathbf{ifail}}=4$
The solution of the nonlinear equation (2) (see Section 9 for further details) could not be computed by c05avf and c05azf.
${\mathbf{ifail}}=5$
The size of the workspace lwk is too small for the required accuracy. The computation has failed in its initial phase (see Section 9 for further details).
${\mathbf{ifail}}=6$
The size of the workspace lwk is too small for the required accuracy on the interval $\left[{\mathbf{alim}},{\mathbf{tlim}}\right]$ (see Section 9 for further details).
${\mathbf{ifail}}=-99$
See Section 3.9 in How to Use the NAG Library and its Documentation for further information.
${\mathbf{ifail}}=-399$
Your licence key may have expired or may not have been installed correctly.
See Section 3.8 in How to Use the NAG Library and its Documentation for further information.
${\mathbf{ifail}}=-999$
Dynamic memory allocation failed.
See Section 3.7 in How to Use the NAG Library and its Documentation for further information.

## 7Accuracy

The accuracy depends on tol, the theoretical behaviour of the solution of the integral equation, the interval of integration and on the method being used. It can be controlled by varying tol and thresh; you are recommended to choose a smaller value for tol, the larger the value of iorder.
You are warned not to supply a very small tol, because the required accuracy may never be achieved. This will usually force an error exit with ${\mathbf{ifail}}={\mathbf{5}}$ or ${\mathbf{6}}$.
In general, the higher the order of the method, the faster the required accuracy is achieved with less workspace. For non-stiff problems (see Section 9) you are recommended to use the Adams' method (${\mathbf{method}}=\text{'A'}$) of order greater than $4$ (${\mathbf{iorder}}>4$).

## 8Parallelism and Performance

d05baf makes calls to BLAS and/or LAPACK routines, which may be threaded within the vendor library used by this implementation. Consult the documentation for the vendor library for further information.
Please consult the X06 Chapter Introduction for information on how to control and interrogate the OpenMP environment used within this routine. Please also consult the Users' Note for your implementation for any additional implementation-specific information.

When solving (1), the solution of a nonlinear equation of the form
 $Yn-αgtn,Yn-Ψn=0,$ (2)
is required, where ${\Psi }_{n}$ and $\alpha$ are constants. d05baf calls c05avf to find an interval for the zero of this equation followed by c05azf to find its zero.
There is an initial phase of the algorithm where the solution is computed only for the first few points of the mesh. The exact number of these points depends on iorder and method. The step size is halved until the accuracy requirements are satisfied on these points and only then the solution on the whole mesh is computed. During this initial phase, if lwk is too small, d05baf will exit with ${\mathbf{ifail}}={\mathbf{5}}$.
In the case ${\mathbf{ifail}}={\mathbf{4}}$ or ${\mathbf{5}}$, you may be dealing with a ‘stiff’ equation; an equation where the Lipschitz constant $L$ of the function $g\left(t,y\right)$ in (1) with respect to its second argument is large, viz,
 $gt,u-gt,v≤Lu-v.$ (3)
In this case, if a BDF method (${\mathbf{method}}=\text{'B'}$) has been used, you are recommended to choose a smaller step size by increasing the value of nmesh, or provide a larger workspace. But, if an Adams' method (${\mathbf{method}}=\text{'A'}$) has been selected, you are recommended to switch to a BDF method instead.
In the case ${\mathbf{ifail}}={\mathbf{6}}$, the specified accuracy has not been attained but yn and errest contain the most recent approximation to the computed solution and the corresponding error estimate. In this case, the error message informs you of the number of extrapolations performed and the size of lwk required for the algorithm to proceed further. The latter quantity will also be available in ${\mathbf{work}}\left(1\right)$.

## 10Example

Consider the following integral equation
 $yt=e-t+∫0te-t-sys+e-ysds, 0≤t≤20$ (4)
with the solution $y\left(t\right)=\mathrm{ln}\left(t+e\right)$. In this example, the Adams' method of order $6$ is used to solve this equation with ${\mathbf{tol}}=\text{1.E−4}$.

### 10.1Program Text

Program Text (d05bafe.f90)

None.

### 10.3Program Results

Program Results (d05bafe.r)

© The Numerical Algorithms Group Ltd, Oxford, UK. 2017