minimaxApprox {minimaxApprox} | R Documentation |
Minimax Approximation of Functions
Description
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. When using monomials as the polynomial basis, the Compensated Horner Scheme of Langlois et al. (2006) is used.
Usage
minimaxApprox(fn, lower, upper, degree, relErr = FALSE, basis ="Chebyshev",
xi = NULL, opts = list())
Arguments
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 |
basis |
character; Which polynomial basis to use in the analysis.
|
xi |
numeric; For rational approximation, a vector of initial points of
the correct length— |
opts |
list; Configuration options including:
|
Details
Convergence
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—the Distance Test.
The observed error magnitudes are within tolerance of each other—the Magnitude Test.
The observed error signs oscillate—the Oscillation Test.
“Within tolerance” can be met in one of two ways:
-
Difference: The difference between the absolute magnitudes is less than or equal to
tol
. -
Ratio: The ratio between the absolute magnitudes of the larger and smaller is less than or equal to
convrat
.
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 tests can be passed by either being within tol
or
convrat
as described above. However, when the Difference test
returns values less than machine precision, it is ignored in favor of the
Ratio test.
When the error values remain within tolerance of each other over conviter
iterations, the algorithm will stop, as it is expected that no further precision
will be gained by continued iterations.
Polynomial Evaluation
Monomial polynomials are evaluated using the Compensated Horner Scheme of Langlois et al. (2006) to enhance both stability and precision. Chebyshev polynomials are evaluated normally. There may be cases where the algorithm will fail using the monomial basis but succeed using Chebyshev polynomials and vice versa. The default is to use the Chebyshev polynomials.
Polynomial Algorithm “Singular Error” Response
When too high of a degree is requested for the tolerance of the algorithm, it
often fails with a singular matrix error. In this case, for the
polynomial version, the algorithm will try looking for an approximation
of degree n + 1
. If it finds one, and the contribution of that
coefficient to the approximation is \le
tailtol
, it will ignore
that coefficient and return the resulting degree n
polynomial, as the
largest coefficient is effectively 0. The contribution is measured by
multiplying that coefficient by the endpoint with the larger absolute magnitude
raised to the n + 1
power. This is done to prevent errors in cases where
a very small coefficient is found on a range with very large absolute values and
the resulting contribution to the approximation is not
de minimis. Setting tailtol
to NULL
will skip the
n + 1
test completely.
Close-to-Zero Tolerance
For each step of the algorithms' iterations, the contribution of the found
coefficient to the total sum (as measured in the above section) is compared to
the ztol
option. When less than or equal to ztol
, that coefficient
is set to 0. Setting ztol
to NULL
skips the test completely. For
intervals near or containing zero, setting this option to anything other than
NULL
may result in either non-convergence or poor results. It is
recommended to keep it as NULL
, although there are edge cases where
it may allow convergence where a standard call may fail.
Value
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 or rational numerator coefficients. When using
Chebyshev polynomials, these are the coefficients for |
b |
The rational denominator coefficients. When using Chebyshev
polynomials, these are the coefficients for |
aMono |
When using Chebyshev polynomials, these are the polynomial or
rational numerator coefficients for monomial expansion in |
bMono |
When using Chebyshev polynomials, these are the rational
denominator coefficients for monomial expansion in |
ExpErr |
The absolute value of the expected error as calculated by the Remez algorithms. |
ObsErr |
The absolute value of largest observed error between the function and the approximation at the extremal points. |
iterations |
The number of iterations of the algorithm. This does not include any iterations required to converge the error value in rational approximation. |
Extrema |
The extrema at which the minimax error was achieved. |
Warning |
A logical flag indicating if any warnings were thrown. |
The object also contains the following attributes:
type |
"Rational" or "Polynomial". |
basis |
"Monomial" or "Chebyshev". |
func |
The function being approximated. |
range |
The range on which the function is being approximated. |
relErr |
A logical indicating that relative error was used. If
|
tol |
The tolerance used for the Distance Test. |
convrat |
The tolerance used for the Magnitude Test. |
Note
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.
Author(s)
Avraham Adler Avraham.Adler@gmail.com
References
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
See Also
Examples
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), basis = "m") # 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