PDF version (NAG web site
, 64-bit version, 64-bit version)
NAG Toolbox: nag_fit_2dspline_ts_sctr (e02jd)
Purpose
nag_fit_2dspline_ts_sctr (e02jd) computes a spline approximation to a set of scattered data using a two-stage approximation method.
The computational complexity of the method grows linearly with the number of data points; hence large datasets are easily accommodated.
Syntax
[
coefs,
iopts,
opts,
ifail] = e02jd(
x,
y,
f,
lsminp,
lsmaxp,
nxcels,
nycels,
iopts,
opts, 'n',
n)
[
coefs,
iopts,
opts,
ifail] = nag_fit_2dspline_ts_sctr(
x,
y,
f,
lsminp,
lsmaxp,
nxcels,
nycels,
iopts,
opts, 'n',
n)
Before calling
nag_fit_2dspline_ts_sctr (e02jd),
nag_fit_opt_set (e02zk) must be called with
optstr set to
"Initialize = nag_fit_2dspline_ts_sctr (e02jd)". Settings for optional algorithmic arguments may be specified by calling
nag_fit_opt_set (e02zk) before a call to
nag_fit_2dspline_ts_sctr (e02jd).
Description
nag_fit_2dspline_ts_sctr (e02jd) determines a smooth bivariate spline approximation to a set of
data points
, for
.
Here, ‘smooth’ means
or
. (You may select the degree of smoothing using the optional parameter
Global Smoothing Level.)
The approximation domain is the bounding box , where (respectively ) and (respectively ) denote the lowest and highest data values of the (respectively ).
The spline is computed by local approximations on a uniform triangulation of the bounding box. These approximations are extended to a smooth spline representation of the surface over the domain. The local approximation scheme is controlled by the optional parameter
Local Method. The schemes provided are: by least squares polynomial approximation (
Davydov and Zeilfelder (2004)); by hybrid polynomial and radial basis function (RBF) approximation (
Davydov et al. (2006)); or by pure RBF approximation (
Davydov et al. (2005)).
The two-stage approximation method employed by nag_fit_2dspline_ts_sctr (e02jd) is derived from
the TSFIT package of O. Davydov and F. Zeilfelder.
Values of the computed spline can subsequently be computed by calling
nag_fit_2dspline_ts_evalv (e02je) or
nag_fit_2dspline_ts_evalm (e02jf).
References
Davydov O, Morandi R and Sestini A (2006) Local hybrid approximation for scattered data fitting with bivariate splines Comput. Aided Geom. Design 23 703–721
Davydov O, Sestini A and Morandi R (2005) Local RBF approximation for scattered data fitting with bivariate splines Trends and Applications in Constructive Approximation M. G. de Bruin, D. H. Mache, and J. Szabados, Eds ISNM Vol. 151 Birkhauser 91–102
Davydov O and Zeilfelder F (2004) Scattered data fitting by direct extension of local polynomials to bivariate splines Advances in Comp. Math. 21 223–271
Parameters
Compulsory Input Parameters
- 1:
– double array
- 2:
– double array
- 3:
– double array
-
The data values to be fitted.
Constraint:
for some and for some ; i.e., there are at least two distinct and values.
- 4:
– int64int32nag_int scalar
- 5:
– int64int32nag_int scalar
-
Are control parameters for the local approximations.
Each local approximation is computed on a local domain containing one of the
triangles in the discretization of the bounding box. The size of each local domain will be adaptively chosen such that if it contains fewer than
lsminp sample points it is expanded, else if it contains greater than
lsmaxp sample points a thinning method is applied.
lsmaxp mainly controls computational cost (in that working with a thinned set of points is cheaper and may be appropriate if the input data is densely distributed), while
lsminp allows handling of different types of scattered data.
Setting , and therefore forcing either expansion or thinning, may be useful for computing initial coarse approximations. In general smaller values for these arguments reduces cost.
A calibration procedure (experimenting with a small subset of the data to be fitted and validating the results) may be needed to choose the most appropriate values for
lsminp and
lsmaxp.
- 6:
– int64int32nag_int scalar
- 7:
– int64int32nag_int scalar
-
nxcels (respectively
nycels) is the number of cells in the
(respectively
) direction that will be used to create the triangulation of the bounding box of the domain of the function to be fitted.
Greater efficiency generally comes when
nxcels and
nycels are chosen to be of the same order of magnitude and are such that
n is
. Thus for a ‘square’ triangulation — when
— the quantities
and
nxcels should be of the same order of magnitude. See also
Further Comments.
- 8:
– int64int32nag_int array
-
Note: the dimension of this array is dictated by the requirements of associated functions that must have been previously called. This array
must be the same array passed as argument
iopts in the previous call to
nag_fit_opt_set (e02zk).
The contents of
iopts must not be modified in any way either directly or indirectly, by further calls to
nag_fit_opt_set (e02zk), before calling either or both of the evaluation routines
nag_fit_2dspline_ts_evalv (e02je) and
nag_fit_2dspline_ts_evalm (e02jf).
- 9:
– double array
-
Note: the dimension of this array is dictated by the requirements of associated functions that must have been previously called. This array
must be the same array passed as argument
opts in the previous call to
nag_fit_opt_set (e02zk).
The contents of
opts must not be modified in any way either directly or indirectly, by further calls to
nag_fit_opt_set (e02zk), before calling either or both of the evaluation routines
nag_fit_2dspline_ts_evalv (e02je) and
nag_fit_2dspline_ts_evalm (e02jf).
Optional Input Parameters
- 1:
– int64int32nag_int scalar
-
Default:
the dimension of the arrays
x,
y,
f. (An error is raised if these dimensions are not equal.)
, the number of data values to be fitted.
Constraint:
.
Output Parameters
- 1:
– double array
-
If
on exit,
coefs contains the computed spline coefficients.
- 2:
– int64int32nag_int array
-
Note: the dimension of this array is dictated by the requirements of associated functions that must have been previously called. This array
must be the same array passed as argument
iopts in the previous call to
nag_fit_opt_set (e02zk).
- 3:
– double array
-
Note: the dimension of this array is dictated by the requirements of associated functions that must have been previously called. This array
must be the same array passed as argument
opts in the previous call to
nag_fit_opt_set (e02zk).
- 4:
– int64int32nag_int scalar
unless the function detects an error (see
Error Indicators and Warnings).
Error Indicators and Warnings
Errors or warnings detected by the function:
-
-
Constraint: .
-
-
Constraint: .
-
-
Constraint: .
-
-
Constraint: .
-
-
Constraint: .
-
-
Constraint:
if ,
;
if ,
.
-
-
Option arrays are not initialized or are corrupted.
-
-
An unexpected algorithmic failure was encountered. Please contact
NAG.
-
-
On entry, all elements of
x or of
y are equal.
-
-
The selected radial basis function cannot be used with the RBF local method.
-
-
The value of optional parameter
Polynomial Starting Degree was invalid.
-
An unexpected error has been triggered by this routine. Please
contact
NAG.
-
Your licence key may have expired or may not have been installed correctly.
-
Dynamic memory allocation failed.
Accuracy
Local approximation by polynomials of degree
for
data points has optimal
approximation order
.
The improved approximation power of hybrid polynomial/RBF and of pure RBF approximations is shown in
Davydov et al. (2006) and
Davydov et al. (2005).
The approximation error for global smoothing is .
For smoothing the error is when and when .
Whether maximal accuracy is achieved depends on the distribution of the input data and the choices of the algorithmic parameters. The references above contain extensive numerical tests and further technical discussions of how best to configure the method.
Further Comments
-linear complexity and memory usage can be attained for sufficiently dense input data if the triangulation parameters
nxcels and
nycels are chosen as recommended in their descriptions above. For sparse input data on such triangulations, if many expansion steps are required (see
lsminp) the complexity may rise to be loglinear.
Parts of the pure RBF method used when have -quadratic memory usage.
Note that if
and an initial hybrid approximation is deemed unreliable (see the description of optional parameter
Minimum Singular Value LHA), a pure polynomial approximation will be used instead on that local domain.
Example
The Franke function
is widely used for testing surface-fitting methods. The example program randomly generates a number of points on this surface. From these a spline is computed and then evaluated at a vector of points and on a mesh.
Open in the MATLAB editor:
e02jd_example
function e02jd_example
fprintf('e02jd example results\n\n');
npts = 15;
xdata = [ 0.0; 0.5; 1; 1.5; 2; 2.5; 3; 4; ...
4.5; 5; 5.5; 6; 7; 7.5; 8];
ydata = [-1.1; -0.372; 0.431; 1.69; 2.11; 3.1; 4.23; 4.35; ...
4.81; 4.61; 4.79; 5.23; 6.35; 7.19; 7.97];
wdata = [1; 1; 1.5; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1];
cstart = 'c';
sfac = 0.001;
x = [6.5178; 7.2463; 1.0159; 7.3070; 5.0589; 0.7803; 2.2280; 4.3751; ...
7.6601; 7.7191; 1.2609; 7.7647; 7.6573; 3.8830; 6.4022; 1.1351; ...
3.3741; 7.3259; 6.3377; 7.6759];
nest = int64(npts + 4);
ixloc = zeros(numel(x), 1, 'int64');
wrk = zeros(4*npts + 16*nest + 41, 1);
iwrk1 = zeros(nest, 1, 'int64');
iwrk2 = zeros(3+3*numel(x), 1, 'int64');
lamda = zeros(nest, 1);
xord = int64(0);
start = int64(0);
deriv = int64(3);
[x, y, f, lsminp, lsmaxp, nxcels, nycels] = generate_data();
[iopts, opts] = handle_options();
[coefs, iopts, opts, ifail] = ...
e02jd(x, y, f, lsminp, lsmaxp, nxcels, nycels, iopts, opts);
pmin = [min(x); min(y)];
pmax = [max(x); max(y)];
evaluate_at_vector(coefs, iopts, opts, pmin, pmax);
evaluate_on_mesh(coefs, iopts, opts, pmin, pmax);
function [x, y, f, lsminp, lsmaxp, nxcels, nycels] = generate_data()
n = int64(100);
[state, ifail] = g05kf(int64(1), int64(0), int64(32958));
[state, x, ifail] = g05sa(n, state);
[state, y, ifail] = g05sa(n, state);
x(1) = 0;
y(1) = 0;
x(n) = 1;
y(n) = 1;
f = 0.75*exp(-((9*x(:)-2).^2 + (9*y(:)-2).^2)/4) + ...
0.75*exp(-((9*x(:)+ 1).^2/49 + (9*y(:)+1)/10)) + ...
0.50*exp(-((9*x(:)-7).^2 + (9*y(:)-3).^2)/4) - ...
0.20*exp(-((9*x(:)- 4).^2 + (9*y(:)-7).^2));
nxcels = int64(6);
nycels = int64(6);
fprintf(['\nComputing the coefficients of a C^1 spline',...
' approximation to Franke''s function\n']);
fprintf(' Using a %d by %d grid\n', nxcels, nycels);
lsminp = int64(3);
lsmaxp = int64(100);
function [iopts, opts] = handle_options()
opts = zeros(100, 1);
iopts = zeros(100, 1, 'int64');
[iopts, opts, ifail] = e02zk( ...
'Initialize = e02jd', iopts, opts);
optstr = strcat('Minimum Singular Value LPA = ', num2str(1/32));
[iopts, opts, ifail] = e02zk( ...
optstr, iopts, opts);
[iopts, opts, ifail] = e02zk( ...
'Polynomial Starting Degree = 3', iopts, opts);
[iopts, opts, ifail] = e02zk( ...
'Averaged Spline = Yes', iopts, opts);
[~, ~, cvalue, ~, ifail] = e02zl( ...
'Averaged Spline', iopts, opts);
if strcmp(cvalue, 'YES')
fprintf(' Using an averaged local approximation\n');
end
function evaluate_at_vector(coefs, iopts, opts, pmin, pmax)
xevalv = [0];
yevalv = [0];
for i = 1:numel(xevalv)
xevalv(i) = max(xevalv(i),pmin(1));
xevalv(i) = min(xevalv(i),pmax(1));
yevalv(i) = max(yevalv(i),pmin(2));
yevalv(i) = min(yevalv(i),pmax(2));
end
[fevalv, ifail] = e02je(xevalv, yevalv, coefs, iopts, opts);
fprintf('\n Values of computed spline at (x_i,y_i):\n\n');
fprintf(' x_i y_i f(x_i,y_i)\n');
for i = 1:numel(xevalv)
fprintf('%12.2f %12.2f %12.2f\n', xevalv(i),yevalv(i),fevalv(i));
end
function evaluate_on_mesh(coefs,iopts,opts,pmin,pmax)
nxeval = 101;
nyeval = 101;
ll_corner = [0; 0];
ur_corner = [1; 1];
h = [(ur_corner(1)-ll_corner(1))/(nxeval-1); ...
(ur_corner(2)-ll_corner(2))/(nyeval-1)];
xevalm = ll_corner(1) + [0:nxeval-1]*h(1);
yevalm = ll_corner(2) + [0:nyeval-1]*h(2);
xevalm = max(pmin(1), xevalm);
xevalm = min(pmax(1), xevalm);
yevalm = max(pmin(2), yevalm);
yevalm = min(pmax(2), yevalm);
[fevalm, ifail] = e02jf(xevalm, yevalm, coefs, iopts, opts);
print_mesh = false;
if print_mesh
fprintf('\nValues of computed spline at (x_i,y_j):\n\n');
fprintf(' x_i y_i f(x_i,y_i)\n');
for i = 1:nxeval
for j=1:nyeval
fprintf('%12.2f %12.2f %12.2f\n', xevalm(i),yevalm(j),fevalm(i, j));
end
end
else
fprintf('\nOutputting of the function values on the mesh is disabled\n');
end
fig1 = figure;
meshc(yevalm,xevalm,fevalm);
title({'Bivariate spline fit from scattered data', ...
'using two-stage approximation'});
xlabel('x');
ylabel('y');
view(22,28);
e02jd example results
Computing the coefficients of a C^1 spline approximation to Franke's function
Using a 6 by 6 grid
Using an averaged local approximation
Values of computed spline at (x_i,y_i):
x_i y_i f(x_i,y_i)
0.00 0.00 0.76
Outputting of the function values on the mesh is disabled
Optional Parameters
Several optional parameters in
nag_fit_2dspline_ts_sctr (e02jd) control aspects of the algorithm, methodology used, logic or output. Their values are contained in the arrays
iopts and
opts; these must be initialized before calling
nag_fit_2dspline_ts_sctr (e02jd) by first calling
nag_fit_opt_set (e02zk) with
optstr set to
"Initialize = nag_fit_2dspline_ts_sctr (e02jd)".
Each optional parameter has an associated default value; to set any of them to a non-default value, or to reset any of them to the default value, use
nag_fit_opt_set (e02zk). The current value of an optional parameter can be queried using
nag_fit_opt_get (e02zl).
The remainder of this section can be skipped if you wish to use the default values for all optional parameters.
The following is a list of the optional parameters available. A full description of each optional parameter is provided in
Description of the s.
Description of the Optional Parameters
For each option, we give a summary line, a description of the optional parameter and details of constraints.
The summary line contains:
- the keywords;
- a parameter value,
where the letters , and denote options that take character, integer and real values respectively;
- the default value.
Keywords and character values are case insensitive.
For
nag_fit_2dspline_ts_sctr (e02jd) the maximum length of the parameter
cvalue used by
nag_fit_opt_get (e02zl) is
.
Averaged Spline Default
When the bounding box is triangulated there are 8 equivalent configurations of the mesh. Setting will use the averaged value of the possible local polynomial approximations over each triangle in the mesh. This usually gives better results but at (about 8 times) higher computational cost.
Constraint: or .
Global Smoothing Level Default
The smoothness level for the global spline approximation.
- Will use piecewise cubics.
- Will use piecewise sextics.
Constraint:
or .
Interpolation Only RBF Default
If , each local RBF approximation is computed by interpolation.
If , each local RBF approximation is computed by a discrete least squares approach. This is likely to be more accurate and more expensive than interpolation.
If or , this option setting is ignored.
Constraint:
or .
Local Method Default
The local approximation scheme to use.
- Uses least squares polynomial approximations.
- Uses hybrid polynomial and RBF approximations.
- Uses pure RBF approximations.
In general is less computationally expensive than is less computationally expensive than with the reverse ordering holding for accuracy of results.
Constraint:
, or .
Minimum Singular Value LHA Default
A tolerance measure for accepting or rejecting a local hybrid approximation (LHA) as reliable.
The solution of a local least squares problem solved on each triangle subdomain is accepted as reliable if the minimum singular value of the collocation matrix (of polynomial and radial basis function terms) associated with the least squares problem satisfies .
In general the approximation power will be reduced as
Minimum Singular Value LHA is reduced. (A small
indicates that the local data has hidden redundancies which prevent it from carrying enough information for a good approximation to be made.) Setting
Minimum Singular Value LHA very large may have the detrimental effect that only approximations of low degree are deemed reliable.
A calibration procedure (experimenting with a small subset of the data to be fitted and validating the results) may be needed to choose the most appropriate value for this parameter.
If or , this option setting is ignored.
Constraint:
.
Minimum Singular Value LPA Default
A tolerance measure for accepting or rejecting a local polynomial approximation (LPA) as reliable. Clearly this setting is relevant when
, but it also may be used when
(see
Further Comments.)
The solution of a local least squares problem solved on each triangle subdomain is accepted as reliable if the minimum singular value of the matrix (of Bernstein polynomial values) associated with the least squares problem satisfies .
In general the approximation power will be reduced as
Minimum Singular Value LPA is reduced. (A small
indicates that the local data has hidden redundancies which prevent it from carrying enough information for a good approximation to be made.) Setting
Minimum Singular Value LPA very large may have the detrimental effect that only approximations of low degree are deemed reliable.
Minimum Singular Value LPA will have no effect if
, and it will have little effect if the input data is ‘smooth’ (e.g., from a known function).
A calibration procedure (experimenting with a small subset of the data to be fitted and validating the results) may be needed to choose the most appropriate value for this parameter.
If , this option setting is ignored.
Constraint:
.
Polynomial Starting Degree
Default if ,
Default otherwise
The degree to be used for the polynomial part in the initial step of each local approximation.
At this initial step the method will attempt to fit with a local approximation having polynomial part of degree
Polynomial Starting Degree. If
and the approximation is deemed unreliable (according to
Minimum Singular Value LPA), the degree will be decremented by one and a new local approximation computed, ending with a constant approximation if no other is reliable. If
and the approximation is deemed unreliable (according to
Minimum Singular Value LHA), a pure polynomial approximation of this degree will be tried instead. The method then proceeds as in the
case.
Polynomial Starting Degree is bounded from above by the maximum possible spline degree, which is
(when performing
global super-smoothing). Note that the best-case approximation error (see
Accuracy) for
smoothing with
is achieved for local polynomials of degree
; that is, for this level of global smoothing no further benefit is gained by setting
.
The default value gives a good compromise between efficiency and accuracy. In general the best approximation can be obtained by setting:
- If
- if , ;
- if ;
- if , ;
- otherwise .
- If , Polynomial Starting Degree as small as possible.
If , this option setting is ignored.
Constraints:
- if ,
- if , , or ,
;
- if or ,
;
- if or ,
;
- if ,
;
- otherwise ;
- if and ,
;
- otherwise .
Radial Basis Function Default
Scaling Coefficient RBF Default
Radial Basis Function selects the RBF to use in each local RBF approximation, while
Scaling Coefficient RBF selects the scale factor to use in its evaluation, as described below.
A calibration procedure (experimenting with a small subset of the data to be fitted and validating the results) may be needed to choose the most appropriate scale factor and RBF.
If , these option settings are ignored.
If or , the following (conditionally) positive definite functions may be chosen.
Define and .
| Gaussian |
| inverse multiquadric |
| inverse multiquadric |
| inverse multiquadric |
| inverse multiquadric |
| H. Wendland's function |
| H. Wendland's function |
| H. Wendland's function |
| M. Buhmann's function if , otherwise |
| multiquadric |
| multiquadric |
| polyharmonic spline |
| polyharmonic spline |
If
the following conditionally positive definite functions may also be chosen.
| multiquadric |
| multiquadric |
| thin plate spline |
| polyharmonic spline |
| thin plate spline |
| polyharmonic spline |
| thin plate spline |
| polyharmonic spline |
| polyharmonic spline |
Constraints:
- if , , or ,
and ;
- if or ,
and ;
- if or ,
and ;
- if ,
and ;
- .
Separation LRBFA Default
A knot-separation parameter used to control the condition number of the matrix used in each local RBF approximation (LRBFA). A smaller value may mean greater numerical stability but fewer knots.
If or , this option setting is ignored.
Constraint:
.
Supersmooth C2 Default
If , the spline is generated using additional smoothness constraints. This usually gives better results but at higher computational cost.
If this option setting is ignored.
Constraint:
or .
PDF version (NAG web site
, 64-bit version, 64-bit version)
© The Numerical Algorithms Group Ltd, Oxford, UK. 2009–2015