NAG Library Function Document

nag_numdiff_1d_real_eval (d04bac)

+− Contents

1 Purpose

2 Specification

3 Description

4 References

5 Arguments

6 Error Indicators and Warnings

7 Accuracy

8 Parallelism and Performance

9 Further Comments

+− 10 Example

10.1 Program Text

10.2 Program Data

10.3 Program Results

1 Purpose

nag_numdiff_1d_real_eval (d04bac) calculates a set of derivatives (up to order

14

) of a function at a point with respect to a single variable. A corresponding set of error estimates is also returned. Derivatives are calculated using an extension of the Neville algorithm. This function differs from nag_numdiff_1d_real (d04aac), in that the abscissae and corresponding function values must be calculated before this function is called. The abscissae may be generated using nag_numdiff_1d_real_absci (d04bbc).

2 Specification

#include <nag.h>

#include <nagd04.h>

void	nag_numdiff_1d_real_eval (const double xval[], const double fval[], double der[], double erest[], NagError *fail)

3 Description

nag_numdiff_1d_real_eval (d04bac) provides a set of approximations:

der [j - 1], j = 1, 2, \dots, 14

to the derivatives:

f^{(j)} (x_{0}), j = 1, 2, \dots, 14

of a real valued function

f (x)

at a real abscissa

x_{0}

, together with a set of error estimates:

erest [j - 1], j = 1, 2, \dots, 14

which hopefully satisfy:

|der [j - 1] - f^{(j)} (x_{0})| < erest [j - 1], j = 1, 2, \dots, 14 .

The results

der [j - 1]

and

erest [j - 1]

are based on

21

function values:

f (x_{0}), f (x_{0} \pm (2 i - 1) h), i = 1, 2, \dots, 10 .

The abscissae

x

and the corresponding function values

f (x)

should be passed into nag_numdiff_1d_real_eval (d04bac) as the vectors xval and fval respectively. The step size

h

is derived from the abscissae in xval. See Section 9 for a discussion of how the derived value of

h

may affect the results of nag_numdiff_1d_real_eval (d04bac). The order in which the abscissae and function values are stored in xval and fval is irrelevant, provided that the function value at any given index corresponds to the value of the abscissa at the same index. Abscissae may be automatically generated using nag_numdiff_1d_real_absci (d04bbc) if desired. For each derivative nag_numdiff_1d_real_eval (d04bac) employs an extension of the Neville Algorithm (see Lyness and Moler (1969)) to obtain a selection of approximations.

For example, for odd derivatives, this function calculates a set of numbers:

T_{k, p, s}, p = s, s + 1, \dots, 6, k = 0, 1, \dots, 9 - p

each of which is an approximation to

f^{(2 s + 1)} (x_{0}) / (2 s + 1)!

. A specific approximation

T_{k, p, s}

is of polynomial degree

2 p + 2

and is based on polynomial interpolation using function values

f (x_{0} \pm (2 i - 1) h)

, for

k = k, \dots, k + p

. In the absence of round-off error, the better approximations would be associated with the larger values of

p

and of

k

. However, round-off error in function values has an increasingly contaminating effect for successively larger values of

p

. This function proceeds to make a judicious choice between all the approximations in the following way.

For a specified value of

s

, let:

R_{p} = U_{p} - L_{p}, p = s, s + 1, \dots, 6

where

U_{p} = \max_{k} (T_{k, p, s})

and

L_{p} = \min_{k} (T_{k, p, s})

, for

k = 0, 1, \dots, 9 - p

, and let

\bar{p}

be such that

R_{\bar{p}} = \min_{p} (R_{p})

, for

p = s, \dots, 6

This function returns:

der [2 s] = \frac{1}{8 - \bar{p}} \times \{\sum_{k = 0}^{9 - \bar{p}} T_{k, \bar{p}, s} - U_{\bar{p}} - L_{\bar{p}}\} (2 s + 1)!

and

erest [2 s] = R_{\bar{p}} \times (2 s + 1)! \times K_{2 s + 1}

where

K_{j}

is a safety factor which has been assigned the values:

$K_{j} = 1$ ,	$j \leq 9$
$K_{j} = 1.5$ ,	$j = 10, 11$
$K_{j} = 2$	$j \geq 12$ ,

on the basis of performance statistics.

The even order derivatives are calculated in a precisely analogous manner.

4 References

Lyness J N and Moler C B (1969) Generalised Romberg methods for integrals of derivatives Numer. Math. 14 1–14

5 Arguments

1: xval[ $21$ ] – const doubleInput: On entry: the abscissae at which the function has been evaluated, as described in Section 3. These can be generated by calling nag_numdiff_1d_real_absci (d04bbc). The order of the abscissae is irrelevant.
Constraint: the values in xval must span the set $\{x_{0}, x_{0} \pm (2 j - 1) h\}$ , for $j = 1, 2, \dots, 10$ .
2: fval[ $21$ ] – const doubleInput: On entry: $fval [j - 1]$ must contain the function value at $xval [j - 1]$ , for $j = 1, 2, \dots, 21$ .
3: der[ $14$ ] – doubleOutput: On exit: the 14 derivative estimates.
4: erest[ $14$ ] – doubleOutput: On exit: the 14 error estimates for the derivatives.
5: fail – NagError *Input/Output: The NAG error argument (see Section 3.6 in the Essential Introduction).

6 Error Indicators and Warnings

NE_BAD_PARAM: On entry, argument $⟨value⟩$ had an illegal value.
NE_INTERNAL_ERROR: An internal error has occurred in this function. Check the function call and any array sizes. If the call is correct then please contact NAG for assistance.
NE_SPACING_INCORRECT: On entry, the values of xval are not correctly spaced.
Derived $h = ⟨value⟩$ .
NE_TOO_SMALL: The derived $h$ is below tolerance.
Derived $h > ⟨value⟩$ is required. Derived $h = ⟨value⟩$ .

7 Accuracy

The accuracy of the results is problem dependent. An estimate of the accuracy of each result

der [j - 1]

is returned in

erest [j - 1]

(see Sections 3, 5 and 9).

A basic feature of any floating-point function for numerical differentiation based on real function values on the real axis is that successively higher order derivative approximations are successively less accurate. It is expected that in most cases

der [13]

will be unusable. As an aid to this process, the sign of

erest [j - 1]

is set negative when the estimated absolute error is greater than the approximate derivative itself, i.e., when the approximate derivative may be so inaccurate that it may even have the wrong sign. It is also set negative in some other cases when information available to nag_numdiff_1d_real_eval (d04bac) indicates that the corresponding value of

der [j - 1]

is questionable.

The actual values in erest depend on the accuracy of the function values, the properties of the machine arithmetic, the analytic properties of the function being differentiated and the step length

h

(see Section 9). The only hard and fast rule is that for a given objective function and

h

, the values of

erest [j - 1]

increase with increasing

j

. The limit of

14

is dictated by experience. Only very rarely can one obtain meaningful approximations for higher order derivatives on conventional machines.

8 Parallelism and Performance

Not applicable.

9 Further Comments

The results depend very critically on the choice of the step length

h

. The overall accuracy is diminished as

h

becomes small (because of the effect of round-off error) and as

h

becomes large (because the discretization error also becomes large). If this function is used four or five times with different values of

h

one can find a reasonably good value. A process in which the value of

h

is successively halved (or doubled) is usually quite effective. Experience has shown that in cases in which the Taylor series for the objective function about

x_{0}

has a finite radius of convergence

R

, the choices of

h > R / 19

are not likely to lead to good results. In this case some function values lie outside the circle of convergence.

As mentioned, the order of the abscissae in xval does not matter, provided the corresponding values of fval are ordered identically. If the abscissae are generated by nag_numdiff_1d_real_absci (d04bbc), then they will be in ascending order. In particular, the target abscissa