The function also returns a number whose absolute value is the final reference deviation (see Arguments). The function is an adaptation of Boothroyd (1967).

References

Boothroyd J B (1967) Algorithm 318 Comm. ACM 10 801

Stieffel E (1959) Numerical methods of Tchebycheff approximation On Numerical Approximation (ed R E Langer) 217–232 University of Wisconsin Press

Parameters

Compulsory Input Parameters

1: $x (n)$ – double array: The values of the $x$ coordinates, $x_{i}$ , for $i = 1, 2, \dots, n$ .

Constraint: $x_{1} < x_{2} < \dots < x_{n}$ .
2: $y (n)$ – double array: The values of the $y$ coordinates, $y_{i}$ , for $i = 1, 2, \dots, n$ .
3: $m$ – int64int32nag_int scalar: $m$ , where $m$ is the degree of the polynomial to be found.

Constraint: $0 \leq m < \min (100, n - 1)$ .

Optional Input Parameters

1: $n$ – int64int32nag_int scalar: Default: the dimension of the arrays x, y. (An error is raised if these dimensions are not equal.)
$n$ , the number of data points.

Constraint: $n \geq 1$ .

Output Parameters

1: $a (m + 1)$ – double array: The coefficients $a_{i}$ of the minimax polynomial, for $i = 0, 1, \dots, m$ .
2: $ref$ – double scalar: The final reference deviation, i.e., the maximum deviation of the computed polynomial evaluated at $x_{i}$ from the reference values $y_{i}$ , for $i = 1, 2, \dots, n$ . ref may return a negative value which indicates that the algorithm started to cycle due to round-off errors.
3: $ifail$ – int64int32nag_int scalar: $ifail = 0$ unless the function detects an error (see Error Indicators and Warnings).

Error Indicators and Warnings

Errors or warnings detected by the function:

$ifail = 1$: Constraint: $n \geq 1$ .

$ifail = 2$: Constraint: $m < 100$ .

Constraint: $m < n - 1$ .

Constraint: $m \geq 0$ .

$ifail = 3$: Constraint: $x (i + 1) > x (i)$ .

$ifail = - 99$: An unexpected error has been triggered by this routine. Please contact NAG.

$ifail = - 399$: Your licence key may have expired or may not have been installed correctly.

$ifail = - 999$: Dynamic memory allocation failed.

Accuracy

This is dependent on the given data points and on the degree of the polynomial. The data points should represent a fairly smooth function which does not contain regions with markedly different behaviours. For large numbers of data points (

n > 100

, say), rounding error will affect the computation regardless of the quality of the data; in this case, relatively small degree polynomials (

m ≪ \sqrt{n}

) may be used when this is consistent with the required approximation. A limit of

99

is placed on the degree of polynomial since it is known from experiment that a complete loss of accuracy often results from using such high degree polynomials in this form of the algorithm.

Further Comments

The time taken increases with

m

Example

This example calculates a minimax fit with a polynomial of degree

5

to the exponential function evaluated at

21

points over the interval

[0, 1]

. It then prints values of the function and the fitted polynomial.

Open in the MATLAB editor: e02al_example

function e02al_example


fprintf('e02al example results\n\n');

% Minimax polynomial of degree 5 that fits exp(x) on grid in [0,1].
x = [0:0.05:1];
y = exp(x);
m = int64(5);
[a, ref, ifail] = e02al(x, y, m);

fprintf('   Polynomial coefficients\n');
fprintf('        %7.4f\n',a(1:m+1));
fprintf('\n   Reference deviation = %8.2e\n\n', ref);
fprintf('   x     Fit      exp(x)   Residual\n');

xx = [0:0.1:1];
p  = a(m+1:-1:1);
s  = polyval(p,xx);
yy = exp(xx);

for i=1:11
  fprintf('%6.2f%9.4f%9.4f%11.2e\n',xx(i), s(i), yy(i), s(i) - yy(i));
end

e02al example results

   Polynomial coefficients
         1.0000
         1.0001
         0.4991
         0.1704
         0.0348
         0.0139

   Reference deviation = 1.09e-06

   x     Fit      exp(x)   Residual
  0.00   1.0000   1.0000  -1.09e-06
  0.10   1.1052   1.1052   9.74e-07
  0.20   1.2214   1.2214  -7.44e-07
  0.30   1.3499   1.3499  -9.18e-07
  0.40   1.4918   1.4918   2.99e-07
  0.50   1.6487   1.6487   1.09e-06
  0.60   1.8221   1.8221   4.59e-07
  0.70   2.0138   2.0138  -8.16e-07
  0.80   2.2255   2.2255  -8.42e-07
  0.90   2.4596   2.4596   8.75e-07
  1.00   2.7183   2.7183  -1.09e-06

PDF version (NAG web site, 64-bit version, 64-bit version)

Chapter Contents

Chapter Introduction

NAG Toolbox