minimaxApprox {minimaxApprox} | R Documentation |
Calculates minimax approximations to functions. Polynomial approximation uses the Remez (1962) algorithm. Rational approximation uses the Cody-Fraser-Hart (Cody et al., 1968) version of the algorithm. Polynomial evaluation uses the Compensated Horner Scheme of Langlois et al. (2006).
minimaxApprox(fn, lower, upper, degree, relErr = FALSE, xi = NULL,
opts = list())
fn |
function; A vectorized univariate function having |
lower |
numeric; The lower bound of the approximation interval. |
upper |
numeric; The upper bound of the approximation interval. |
degree |
integer; Either a single value representing the requested degree for polynomial approximation or a vector of length 2 representing the requested degrees of the numerator and denominator for rational approximation. |
relErr |
logical; If |
xi |
numeric; For rational approximation, a vector of initial points of
the correct length— |
opts |
list; Configuration options including:
|
The function implements the Remez algorithm using linear approximation, chiefly as described by Cody et al. (1968). Convergence is considered achieved when all three of the following criteria are met:
The observed error magnitudes are within tolerance of the expected error (Distance Test).
The observed error magnitudes are within tolerance of each other (Magnitude Test).
The observed error signs oscillate (Oscillating Test).
“Within tolerance” can be met in one of two ways:
The difference between the absolute magnitudes is less than or
equal to tol
.
The ratio between the larger and smaller is less than or equal to
convRatio
.
For efficiency, the Distance Test is taken between the absolute value of the
largest observed error and the absolute value of the expected error. Similarly,
the Magnitude Test is taken between the absolute value of the largest observed
error and the absolute value of the smallest observed error. Both the Magnitude
Test and the Distance Test can be passed by either being within
tol
or convRatio
as described above.
When too high of a degree is requested for the tolerance of the algorithm, it often fails with a singular matrix error.
The polynomials are evaluated using the Compensated Horner Scheme of Langlois et al. (2006) to enhance both stability and precision at the expense of some speed.
minimaxApprox
returns an object of class "minimaxApprox"
which inherits from the class list.
The generic accessor function coef
will extract the numerator and
denominator vectors. There are also default print
and plot
methods.
An object of class "minimaxApprox"
is a list containing the following
components:
a |
The polynomial coefficients or the rational numerator coefficients. |
b |
The rational denominator coefficients. Missing for polynomial approximation. |
EE |
The absolute value of the expected error as calculated by the Remez algorithms. |
OE |
The absolute value of largest observed error between the function and the approximation at the extremal basis points. |
iterations |
The number of iterations of the algorithm. This does not include any iterations required to converge the error value in rational approximation. |
x |
The basis points at which the minimax error was achieved. |
Warning |
A logical flag indicating if any warnings were thrown. |
At present, the algorithms are implemented using machine double precision, which means that the approximations are at best slightly worse. Research proceeds on more precise, stable, and efficient implementations. So long as the package remains in an experimental state—noted by a 0 major version—the API may change at any time.
Future developments may include moving the evaluation into a compiled language to take advantage of the speed and precision gains of using fused-multiply-add (FMA) instructions, possible use of arbitrary-precision math, or using barycentric representations instead of monomials.
Avraham Adler Avraham.Adler@gmail.com
Remez, E. I. (1962) General computational methods of Chebyshev approximation: The problems with linear real parameters. US Atomic Energy Commission, Division of Technical Information. AEC-tr-4491
Fraser W. and Hart J. F. (1962) “On the computation of rational approximations to continuous functions”, Communications of the ACM, 5(7), 401–403, doi:10.1145/368273.368578
Cody, W. J. and Fraser W. and Hart J. F. (1968) “Rational Chebyshev approximation using linear equations”, Numerische Mathematik, 12, 242–251, doi:10.1007/BF02162506
Langlois, P. and Graillat, S. and Louvet, N. (2006) “Compensated Horner Scheme”, in Algebraic and Numerical Algorithms and Computer-assisted Proofs. Dagstuhl Seminar Proceedings, 5391, doi:10.4230/DagSemProc.05391.3
minimaxEval
for a convenience function to calculate approximation
values and Pade
for a function to calculate
Padé coefficients given suitable Taylor series coefficients.
minimaxApprox(exp, 0, 1, 5) # Built-in & polynomial
fn <- function(x) sin(x) ^ 2 + cosh(x) # Pre-defined
minimaxApprox(fn, 0, 1, c(2, 3)) # Rational
minimaxApprox(function(x) x ^ 3 / sin(x), 0.7, 1.6, 6L) # Anonymous
fn <- function(x) besselJ(x, nu = 0) # More than one input
b0 <- 0.893576966279167522 # Zero of besselY
minimaxApprox(fn, 0, b0, c(3L, 3L)) # Cf. DLMF 3.11.19