E02 Chapter Contents
E02 Chapter Introduction
NAG Library Manual

# NAG Library Routine DocumentE02BFF

Note:  before using this routine, please read the Users' Note for your implementation to check the interpretation of bold italicised terms and other implementation-dependent details.

## 1  Purpose

E02BFF evaluates a cubic spline and up to its first three derivatives from its B-spline representation at a vector of points. E02BFF can be used to compute the values and derivatives of cubic spline fits and interpolants produced by E02BAF and E02BEF.

## 2  Specification

 SUBROUTINE E02BFF ( START, NCAP7, LAMDA, C, DERIV, XORD, X, IXLOC, NX, S, LDS, IWRK, LIWRK, IFAIL)
 INTEGER START, NCAP7, DERIV, XORD, IXLOC(NX), NX, LDS, IWRK(LIWRK), LIWRK, IFAIL REAL (KIND=nag_wp) LAMDA(NCAP7), C(NCAP7), X(NX), S(LDS,*)

## 3  Description

E02BFF evaluates the cubic spline $s\left(x\right)$ and optionally derivatives up to order $3$ for a vector of points ${x}_{\mathit{j}}$, for $\mathit{j}=1,2,\dots ,{n}_{x}$. It is assumed that $s\left(x\right)$ is represented in terms of its B-spline coefficients ${c}_{\mathit{i}}$, for $\mathit{i}=1,2,\dots ,\stackrel{-}{n}+3$, and (augmented) ordered knot set ${\lambda }_{\mathit{i}}$, for $\mathit{i}=1,2,\dots ,\stackrel{-}{n}+7$, (see E02BAF and E02BEF), i.e.,
 $sx = ∑ i=1q ci Nix .$
Here $q=\stackrel{-}{n}+3$, $\stackrel{-}{n}$ is the number of intervals of the spline and ${N}_{i}\left(x\right)$ denotes the normalized B-spline of degree $3$ (order $4$) defined upon the knots ${\lambda }_{i},{\lambda }_{i+1},\dots ,{\lambda }_{i+4}$.
Only abscissae satisfying,
 $λ4 ≤ xj ≤ λn-+4 ,$
will be evaluated. At a simple knot ${\lambda }_{i}$ (i.e., one satisfying ${\lambda }_{i-1}<{\lambda }_{i}<{\lambda }_{i+1}$), the third derivative of the spline is, in general, discontinuous. At a multiple knot (i.e., two or more knots with the same value), lower derivatives, and even the spline itself, may be discontinuous. Specifically, at a point $x=u$ where (exactly) $r$ knots coincide (such a point is termed a knot of multiplicity $r$), the values of the derivatives of order $4-\mathit{j}$, for $\mathit{j}=1,2,\dots ,r$, are, in general, discontinuous. (Here $1\le r\le 4$; $r>4$ is not meaningful.) The maximum order of the derivatives to be evaluated must be specified ($\left|{\mathbf{DERIV}}\right|$), as must their left- (${\mathbf{DERIV}}<0$) or right- (${\mathbf{DERIV}}>0$) handedness when evaluated at the knots.
Each abscissa (point at which the spline is to be evaluated) ${x}_{j}$ contained in X has an associated enclosing interval number, ${\mathit{ixloc}}_{j}$ either supplied or returned in IXLOC (see START). A simple call to E02BFF would set START to zero and the contents of IXLOC need never be set nor referenced, and the following description on modes of operation can be ignored. However, where efficiency is an important consideration, the following description will help to choose the appropriate mode of operation.
The interval numbers are used to determine which B-splines must be evaluated for a given abscissa, and are defined as
 $ixlocj = ≤0 xj < λ1 4 λ4 = xj k λk < xj < λk+1 k λ4 < λk = xj DERIV<0 k xj = λk+1 < λ n-+4 DERIV≥0 n-+4 λn-+4 = xj >n-+7 xj > λn-+7$ (1)
The algorithm has two modes of vectorization, termed here sorted and unsorted, which are selectable by the parameter START. The sorted mode has two phases, a sorting phase and an evaluation phase. This mode is recommended if there are many abscissae to evaluate relative to the number of intervals of the spline, or the abscissae are distributed relatively densely over a subsection of the spline. In the first phase, ${\mathit{ixloc}}_{j}$ is determined for each ${x}_{j}$ and a permutation is calculated to sort the ${x}_{j}$ by interval number. The first phase may be either partially or completely by-passed using the parameter START if the enclosing segments and/or the subsequent ordering are already known a priori, for example if multiple spline coefficients C are to be evaluated over the same set of knots LAMDA.
In the second phase of the sorted mode, spline approximations are evaluated by segment, so that non-abscissae dependent calculations over a segment may be reused in the evaluation for all abscissa belonging to a specific segment. For example, all third derivatives of all abscissae in the same segment will be identical.
In the unsorted mode of vectorization, no a priori segment sorting is performed, and the evaluation at an abscissa is independent of evaluations at other abscissae; also non-abscissae dependent calculations over a segment will be repeated for each abscissa in a segment. This may be quicker if the number of absicssae is small in comparison to the number of knots in the spline, and they are distributed sparsely throughout the domain of the spline. This is effectively a direct vectorization of E02BBF and E02BCF, although if the enclosing interval numbers ${\mathit{ixloc}}_{j}$ are known, these may again be provided.
If no derivatives are required, the spline evaluation is calculated by taking convex combinations due to de Boor (1972). Otherwise, the calculation of $s\left(x\right)$ and its derivatives is based upon,
 (i) evaluating the nonzero B-splines of orders $1$, $2$, $3$ and $4$ by recurrence (see Cox (1972) and Cox (1978)), (ii) computing all derivatives of the B-splines of order $4$ by applying a second recurrence to these computed B-spline values (see de Boor (1972)), (iii) multiplying the fourth-order B-spline values and their derivative by the appropriate B-spline coefficients, and summing, to yield the values of $s\left(x\right)$ and its derivatives.
The method of convex combinations is significantly faster than the recurrence based method. If higher derivatives of order $2$ or $3$ are not required, as much computation as possible is avoided.

## 4  References

Cox M G (1972) The numerical evaluation of B-splines J. Inst. Math. Appl. 10 134–149
Cox M G (1978) The numerical evaluation of a spline from its B-spline representation J. Inst. Math. Appl. 21 135–143
de Boor C (1972) On calculating with B-splines J. Approx. Theory 6 50–62

## 5  Parameters

1:     START – INTEGERInput
On entry: indicates the completion state of the first phase of the algorithm.
${\mathbf{START}}=0$
The enclosing interval numbers ${\mathit{ixloc}}_{j}$ for the abscissae ${x}_{j}$ contained in X have not been determined, and you wish to use the sorted mode of vectorization.
${\mathbf{START}}=1$
The enclosing interval numbers ${\mathit{ixloc}}_{j}$ have been determined and are provided in IXLOC, however the required permutation and interval related information has not been determined and you wish to use the sorted mode of vectorization.
${\mathbf{START}}=2$
You wish to use the sorted mode of vectorization, and the entire first phase has been completed, with the enclosing interval numbers supplied in IXLOC, and the required permutation and interval related information provided in IWRK (from a previous call to E02BFF).
${\mathbf{START}}=10$
The enclosing interval numbers ${\mathit{ixloc}}_{j}$ for the abscissae ${x}_{j}$ contained in X have not been determined, and you wish to use the unsorted mode of vectorization.
${\mathbf{START}}=11$
The enclosing interval numbers ${\mathit{ixloc}}_{j}$ for the abscissae ${x}_{j}$ contained in X have been supplied in IXLOC, and you wish to use the unsorted mode of vectorization.
Constraint: ${\mathbf{START}}=0$, $1$, $2$, $10$ or $11$.
Additional: ${\mathbf{START}}=0$ or $10$ should be used unless you are sure that the knot set is unchanged between calls.
2:     NCAP7 – INTEGERInput
On entry: $\stackrel{-}{n}+7$, where $\stackrel{-}{n}$ is the number of intervals of the spline (which is one greater than the number of interior knots, i.e., the knots strictly within the range ${\lambda }_{4}$ to ${\lambda }_{\stackrel{-}{n}+4}$ over which the spline is defined). Note that if E02BEF was used to generate the knots and spline coefficients then NCAP7 should contain the same value as returned in N by E02BEF.
Constraint: ${\mathbf{NCAP7}}\ge 8$.
3:     LAMDA(NCAP7) – REAL (KIND=nag_wp) arrayInput
On entry: ${\mathbf{LAMDA}}\left(\mathit{j}\right)$ must be set to the value of the $\mathit{j}$th member of the complete set of knots, ${\lambda }_{\mathit{j}}$, for $\mathit{j}=1,2,\dots ,\stackrel{-}{n}+7$.
Constraint: the ${\mathbf{LAMDA}}\left(j\right)$ must be in nondecreasing order with ${\mathbf{LAMDA}}\left({\mathbf{NCAP7}}-3\right)>{\mathbf{LAMDA}}\left(4\right)$.
4:     C(NCAP7) – REAL (KIND=nag_wp) arrayInput
On entry: the coefficient ${c}_{\mathit{i}}$ of the B-spline ${N}_{\mathit{i}}\left(x\right)$, for $\mathit{i}=1,2,\dots ,\stackrel{-}{n}+3$. The remaining elements of the array are not referenced.
5:     DERIV – INTEGERInput
On entry: the order of derivatives required.
If ${\mathbf{DERIV}}<0$ left derivatives are calculated, otherwise right derivatives are calculated. For abscissae satisfying ${x}_{j}={\lambda }_{4}$ or ${x}_{j}={\lambda }_{\stackrel{-}{n}+4}$ only right or left derivatives will be computed respectively. For abscissae which do not coincide exactly with a knot, the sign of DERIV is immaterial.
${\mathbf{DERIV}}=0$
No derivatives required.
${\mathbf{DERIV}}=±1$
Only $s\left(x\right)$ and its first derivative are required.
${\mathbf{DERIV}}=±2$
Only $s\left(x\right)$ and its first and second derivatives are required.
${\mathbf{DERIV}}=±3$
$s\left(x\right)$ and its first, second and third derivatives are required.
Note: if $\left|{\mathbf{DERIV}}\right|$ is greater than $3$ only the derivatives up to and including $3$ will be returned.
6:     XORD – INTEGERInput
On entry: indicates whether X is supplied in a sufficiently ordered manner. If X is sufficiently ordered E02BFF will complete faster.
${\mathbf{XORD}}=1$
The abscissae in X are ordered at least by interval, in that any two abscissae contained in the same interval are only separated by abscissae in the same interval. For example, ${x}_{j}<{x}_{\mathit{j}+1}$, for $\mathit{j}=1,2,\dots ,{\mathbf{NX}}-1$.
${\mathbf{XORD}}\ne 1$
The abscissae in X are not sufficiently ordered.
7:     X(NX) – REAL (KIND=nag_wp) arrayInput
On entry: the abscissae ${x}_{\mathit{j}}$, for $\mathit{j}=1,2,\dots ,{n}_{x}$. Evaluations will only be performed for those ${x}_{j}$ satisfying ${\lambda }_{4}\le {x}_{j}\le {\lambda }_{\stackrel{~}{n}+4}$.
Constraint: at least one abscissa must fall between ${\mathbf{LAMDA}}\left(4\right)$ and ${\mathbf{LAMDA}}\left({\mathbf{NCAP7}}-3\right)$.
8:     IXLOC(NX) – INTEGER arrayInput/Output
On entry: if ${\mathbf{START}}=1$, $2$ or $11$, if you wish ${x}_{j}$ to be evaluated, ${\mathbf{IXLOC}}\left(j\right)$ must be the enclosing interval number ${\mathit{ixloc}}_{j}$ of the abscissae ${x}_{j}$ (see (1)). If you do not wish ${x}_{j}$ to be evaluated, you may set the interval number to be either less than $4$ or greater than $\stackrel{-}{n}+4$.
Otherwise, IXLOC need not be set.
On exit: if ${\mathbf{START}}=1$, $2$ or $11$, IXLOC is unchanged on exit.
Otherwise, ${\mathbf{IXLOC}}\left(\mathit{j}\right)$, for $\mathit{j}=1,2,\dots ,{n}_{x}$, contains the enclosing interval number ${\mathit{ixloc}}_{\mathit{j}}$, supplied in X, for $\mathit{j}=1,2,\dots ,{n}_{x}$. Evaluations will only take place for abscissae ${x}_{j}$ with $4\le {\mathit{ixloc}}_{j}\le \stackrel{-}{n}+4$.
Constraint: if ${\mathbf{START}}=1$, $2$ or $11$, at least one element of IXLOC must be between $4$ and ${\mathbf{NCAP7}}–3$.
9:     NX – INTEGERInput
On entry: ${n}_{x}$, the total number of abscissae contained in X, including any that will not be evaluated.
Constraint: ${\mathbf{NX}}\ge 1$.
10:   S(LDS,$*$) – REAL (KIND=nag_wp) arrayOutput
Note: the second dimension of the array S must be at least $\mathrm{min}\phantom{\rule{0.125em}{0ex}}\left(\left|{\mathbf{DERIV}}\right|,3\right)+1$.
On exit: if ${x}_{j}$ is valid, ${\mathbf{S}}\left(\mathit{j},\mathit{d}\right)$ will contain the ($\mathit{d}-1$)th derivative of $s\left(x\right)$, for $\mathit{d}=1,2,\dots ,\mathrm{min}\phantom{\rule{0.125em}{0ex}}\left(\left|{\mathbf{DERIV}}\right|,3\right)+1$ and $\mathit{j}=1,2,\dots ,{n}_{x}$. In particular, ${\mathbf{S}}\left(j,1\right)$ will contain the approximation of $s\left({x}_{j}\right)$ for all legal values in X.
11:   LDS – INTEGERInput
On entry: the first dimension of the array S as declared in the (sub)program from which E02BFF is called.
Constraint: ${\mathbf{LDS}}\ge {\mathbf{NX}}$, regardless of the acceptability of the elements of X.
12:   IWRK(LIWRK) – INTEGER arrayInput/Output
On entry: if ${\mathbf{START}}=2$, IWRK must be unchanged from a previous call to E02BFF with ${\mathbf{START}}=0$ or $1$.
Otherwise, IWRK need not be set.
On exit: if ${\mathbf{START}}\ge 2$, IWRK is unchanged on exit.
Otherwise, IWRK contains the required permutation of elements of X, if any, and information related to the division of the abscissae ${x}_{j}$ between the intervals derived from LAMDA.
13:   LIWRK – INTEGERInput
On entry: the dimension of the array IWRK as declared in the (sub)program from which E02BFF is called.
Constraint: ${\mathbf{LIWRK}}\ge 3+3×{\mathbf{NX}}$.
14:   IFAIL – INTEGERInput/Output
On entry: IFAIL must be set to $0$, $-1\text{​ or ​}1$. If you are unfamiliar with this parameter you should refer to Section 3.3 in the Essential Introduction 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, because for this routine the values of the output parameters may be useful even if ${\mathbf{IFAIL}}\ne {\mathbf{0}}$ on exit, the recommended value is $-1$. When the value $-\mathbf{1}\text{​ or ​}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).

## 6  Error Indicators and Warnings

If on entry ${\mathbf{IFAIL}}={\mathbf{0}}$ or $-{\mathbf{1}}$, explanatory error messages are output on the current error message unit (as defined by X04AAF).
Note: E02BFF may return useful information for one or more of the following detected errors or warnings.
Errors or warnings detected by the routine:
${\mathbf{IFAIL}}=1$
On entry, at least one element of X has an enclosing interval number in IXLOC outside the set allowed by the provided spline.
$⟨\mathit{\text{value}}⟩$ entries of X were indexed below the lower bound $⟨\mathit{\text{value}}⟩$.
$⟨\mathit{\text{value}}⟩$ entries of X were indexed above the upper bound $⟨\mathit{\text{value}}⟩$.
${\mathbf{IFAIL}}=2$
On entry, all elements of X had enclosing interval numbers in IXLOC outside the domain allowed by the provided spline.
$⟨\mathit{\text{value}}⟩$ entries of X were indexed below the lower bound $⟨\mathit{\text{value}}⟩$.
$⟨\mathit{\text{value}}⟩$ entries of X were indexed above the upper bound $⟨\mathit{\text{value}}⟩$.
${\mathbf{IFAIL}}=11$
On entry, ${\mathbf{START}}=⟨\mathit{\text{value}}⟩$.
Constraint: ${\mathbf{START}}=0$, $1$, $2$, $10$ or $11$.
${\mathbf{IFAIL}}=12$
On entry, ${\mathbf{START}}=2$ and NX is not consistent with the previous call to E02BFF.
On entry, ${\mathbf{NX}}=⟨\mathit{\text{value}}⟩$.
Constraint: ${\mathbf{NX}}=⟨\mathit{\text{value}}⟩$.
${\mathbf{IFAIL}}=21$
On entry, ${\mathbf{NCAP7}}=⟨\mathit{\text{value}}⟩$.
Constraint: ${\mathbf{NCAP7}}\ge 8$.
${\mathbf{IFAIL}}=31$
On entry, ${\mathbf{LAMDA}}\left(4\right)=⟨\mathit{\text{value}}⟩$, ${\mathbf{NCAP7}}=⟨\mathit{\text{value}}⟩$ and ${\mathbf{LAMDA}}\left({\mathbf{NCAP7}}-3\right)=⟨\mathit{\text{value}}⟩$.
Constraint: ${\mathbf{LAMDA}}\left(4\right)<{\mathbf{LAMDA}}\left({\mathbf{NCAP7}}-3\right)$.
${\mathbf{IFAIL}}=91$
On entry, ${\mathbf{NX}}=⟨\mathit{\text{value}}⟩$.
Constraint: ${\mathbf{NX}}\ge 1$.
${\mathbf{IFAIL}}=111$
On entry, ${\mathbf{LDS}}=⟨\mathit{\text{value}}⟩$.
Constraint: ${\mathbf{LDS}}\ge {\mathbf{NX}}=⟨\mathit{\text{value}}⟩$.
${\mathbf{IFAIL}}=131$
On entry, ${\mathbf{LIWRK}}=⟨\mathit{\text{value}}⟩$.
Constraint: ${\mathbf{LIWRK}}\ge 3×{\mathbf{NX}}+3=⟨\mathit{\text{value}}⟩$.

## 7  Accuracy

The computed value of $s\left(x\right)$ has negligible error in most practical situations. Specifically, this value has an absolute error bounded in modulus by , where $\mathit{cmax}$ is the largest in modulus of ${c}_{j}$, ${c}_{j}+1$, ${c}_{j}+2$ and ${c}_{j}+3$, and $j$ is an integer such that ${\lambda }_{j}+3. If ${c}_{j}$, ${c}_{j}+1$, ${c}_{j}+2$ and ${c}_{j}+3$ are all of the same sign, then the computed value of $s\left(x\right)$ has relative error bounded by . For full details see Cox (1978).
No complete error analysis is available for the computation of the derivatives of $s\left(x\right)$. However, for most practical purposes the absolute errors in the computed derivatives should be small. Note that this is in comparison to the derivatives of the spline, which may or may not be comparable to the derivatives of the function that has been approximated by the spline.

## 8  Further Comments

If using the sorted mode of vectorization, the time required for the first phase to determine the enclosing intervals is approximately proportional to $\mathit{O}\left({n}_{x}\mathrm{log}\left(\stackrel{-}{n}\right)\right)$. The time required to then generate the required permutations and interval information is $\mathit{O}\left({n}_{x}\right)$ if X is ordered sufficiently, or at worst $\mathit{O}\left({n}_{x}\mathrm{min}\phantom{\rule{0.125em}{0ex}}\left({n}_{x},\stackrel{-}{n}\right)\mathrm{log}\left(\mathrm{min}\phantom{\rule{0.125em}{0ex}}\left({n}_{x},\stackrel{-}{n}\right)\right)\right)$ if X is not ordered. The time required by the second phase is then proportional to $\mathit{O}\left({n}_{x}\right)$.
If using the unsorted mode of vectorization, the time required is proportional to $\mathit{O}\left({n}_{x}\mathrm{log}\left(\stackrel{-}{n}\right)\right)$ if the enclosing interval numbers are not provided, or $\mathit{O}\left({n}_{x}\right)$ if they are provided. However, the repeated calculation of various quantities will typically make this slower than the sorted mode when the ratio of abscissae to knots is high, or the abscissae are densely distributed over a relatively small subset of the intervals of the spline.
Note: the routine does not test all the conditions on the knots given in the description of LAMDA in Section 5, since to do this would result in a computation time with a linear dependency upon $\stackrel{-}{n}$ instead of $\mathrm{log}\left(\stackrel{-}{n}\right)$. All the conditions are tested in E02BAF and E02BEF, however.

## 9  Example

This example fits a spline through a set of data points using E02BEF and then evaluates the spline at a set of supplied abscissae.

### 9.1  Program Text

Program Text (e02bffe.f90)

### 9.2  Program Data

Program Data (e02bffe.d)

### 9.3  Program Results

Program Results (e02bffe.r)