e02 Chapter Contents
e02 Chapter Introduction
NAG Library Manual

# NAG Library Function Documentnag_1d_minimax_polynomial (e02alc)

## 1  Purpose

nag_1d_minimax_polynomial (e02alc) calculates a minimax polynomial fit to a set of data points.

## 2  Specification

 #include #include
 void nag_1d_minimax_polynomial (Integer n, const double x[], const double y[], Integer m, double a[], double *ref, NagError *fail)

## 3  Description

Given a set of data points $\left({x}_{i},{y}_{i}\right)$, for $\mathit{i}=1,2,\dots ,n$, nag_1d_minimax_polynomial (e02alc) uses the exchange algorithm to compute an $m$th-degree polynomial
 $Px = a0 + a1x + a2 x2 + ⋯ + am xm$
such that $\underset{i}{\mathrm{max}}\phantom{\rule{0.25em}{0ex}}\left|\mathrm{P}\left({x}_{i}\right)-{y}_{i}\right|$ is a minimum.
The function also returns a number whose absolute value is the final reference deviation (see Section 5). The function is an adaptation of Boothroyd (1967).
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

## 5  Arguments

1:     nIntegerInput
On entry: $n$, the number of data points.
Constraint: ${\mathbf{n}}\ge 1$.
2:     x[n]const doubleInput
On entry: the values of the $x$ coordinates, ${x}_{i}$, for $\mathit{i}=1,2,\dots ,n$.
Constraint: ${x}_{1}<{x}_{2}<\dots <{x}_{n}$.
3:     y[n]const doubleInput
On entry: the values of the $y$ coordinates, ${y}_{i}$, for $\mathit{i}=1,2,\dots ,n$.
4:     mIntegerInput
On entry: $m$, where $m$ is the degree of the polynomial to be found.
Constraint: $0\le {\mathbf{m}}<\mathrm{min}\phantom{\rule{0.125em}{0ex}}\left(100,{\mathbf{n}}-1\right)$.
5:     a[${\mathbf{m}}+1$]doubleOutput
On exit: the coefficients ${a}_{i}$ of the minimax polynomial, for $\mathit{i}=0,1,\dots ,m$.
6:     refdouble *Output
On exit: the final reference deviation, i.e., the maximum deviation of the computed polynomial evaluated at ${x}_{\mathit{i}}$ from the reference values ${y}_{\mathit{i}}$, for $\mathit{i}=1,2,\dots ,n$. ref may return a negative value which indicates that the algorithm started to cycle due to round-off errors.
7:     failNagError *Input/Output
The NAG error argument (see Section 3.6 in the Essential Introduction).

## 6  Error Indicators and Warnings

NE_ALLOC_FAIL
Dynamic memory allocation failed.
On entry, argument $⟨\mathit{\text{value}}⟩$ had an illegal value.
NE_INT
On entry, ${\mathbf{m}}=⟨\mathit{\text{value}}⟩$.
Constraint: ${\mathbf{m}}<100$.
On entry, ${\mathbf{m}}=⟨\mathit{\text{value}}⟩$.
Constraint: ${\mathbf{m}}\ge 0$.
On entry, ${\mathbf{n}}=⟨\mathit{\text{value}}⟩$.
Constraint: ${\mathbf{n}}\ge 1$.
NE_INT_2
On entry, ${\mathbf{m}}=⟨\mathit{\text{value}}⟩$ and ${\mathbf{n}}=⟨\mathit{\text{value}}⟩$.
Constraint: ${\mathbf{m}}<{\mathbf{n}}-1$.
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_NOT_STRICTLY_INCREASING
On entry, $\mathit{i}=⟨\mathit{\text{value}}⟩$, ${\mathbf{x}}\left[\mathit{i}\right]=⟨\mathit{\text{value}}⟩$ and ${\mathbf{x}}\left[\mathit{i}-1\right]=⟨\mathit{\text{value}}⟩$.
Constraint: ${\mathbf{x}}\left[\mathit{i}\right]>{\mathbf{x}}\left[\mathit{i}-1\right]$.

## 7  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 (${\mathbf{n}}>100$, say), rounding error will affect the computation regardless of the quality of the data; in this case, relatively small degree polynomials (${\mathbf{m}}\ll \sqrt{{\mathbf{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.

## 8  Parallelism and Performance

nag_1d_minimax_polynomial (e02alc) is not threaded by NAG in any implementation.
nag_1d_minimax_polynomial (e02alc) 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.

The time taken increases with $m$.

## 10  Example

This example calculates a minimax fit with a polynomial of degree $5$ to the exponential function evaluated at $21$ points over the interval $\left[0,1\right]$. It then prints values of the function and the fitted polynomial.

### 10.1  Program Text

Program Text (e02alce.c)

### 10.2  Program Data

Program Data (e02alce.d)

### 10.3  Program Results

Program Results (e02alce.r)