RegularChains[SemiAlgebraicSetTools][RealRootIsolate] - isolate real roots
RegularChains[SemiAlgebraicSetTools][BoxValues] - extract values from a box
|
Calling Sequence
|
|
RealRootIsolate(F, N, P, H, R, opts)
RealRootIsolate(rc, R, opts)
BoxValues(box, R)
|
|
Parameters
|
|
R
|
-
|
polynomial ring
|
F
|
-
|
list of polynomials of R
|
N
|
-
|
list of polynomials of R
|
P
|
-
|
list of polynomials of R
|
H
|
-
|
list of polynomials of R
|
rc
|
-
|
regular chain of R
|
opts
|
-
|
(optional) equation(s) of the form keyword=value where keyword is one of 'abserr', 'rerr', 'constraints', or 'method'.
|
box
|
-
|
box isolating a root
|
|
|
|
|
Description
|
|
•
|
The RealRootIsolate command returns a list of boxes. Each box isolates exactly one real root of the regular chain rc or semi-algebraic system whose polynomial equations, non-negative polynomial inequalities, (strictly) positive polynomial inequalities and polynomial inequations are given respectively by F, N, P, and H. Moreover, it is guaranteed that all real solutions are found. The regular chain rc or semi-algebraic system has to be zero-dimensional (see IsZeroDimensional). Furthermore, rc must be square-free (see Squarefree and the radical option of Triangularize).
|
•
|
The options 'abserr'=avalue and 'rerr'=rvalue can be used to specify the maximal size of the returned boxes. When one of these options is provided, avalue or rvalue should be a positive rational number. In the first case, all boxes returned by the RealRootIsolate will have a width smaller than or equal to avalue; in the second case, the ratio of the width and the absolute value of the encoded non-zero real algebraic number is smaller than or equal to rvalue, where the width of a box is defined as the maximum of the widths of the intervals of box.
|
•
|
You can specify the algorithm using the option 'method' = 'VincentCollinsAkritas' or 'Discoverer'. The first one is a generalization of the Vincent-Collins-Akritas algorithm which isolates real roots for univariate polynomials. The techniques are very close to the ones used by Renaud Rioboo in his ISSAC 1992 paper (see reference below). The other one implements the algorithm of the paper "Real Solution Isolation Using Interval Arithmetic" by B. Xia and T. Zhang. By default, the first one is used. However, the second one can often do better on large input data.
|
|
|
Examples
|
|
>
|
|
>
|
|
>
|
|
>
|
|
| (1) |
>
|
|
| (2) |
Note that the constraints option is not supported in this calling sequence with four polynomial sets F, N, P and H. Other examples hereafter illustrate the use of the constraints option.
>
|
|
| (3) |
>
|
|
| (4) |
>
|
|
| (5) |
>
|
|
| (6) |
>
|
|
| (7) |
>
|
|
| (8) |
>
|
|
| (9) |
>
|
|
| (10) |
>
|
|
| (11) |
Build a simple regular chain:
>
|
|
| (12) |
>
|
|
| (13) |
Retrieve the box values:
>
|
|
| (14) |
Using the 'abserr' option:
>
|
|
| (15) |
>
|
|
| (16) |
Using the 'constraints' option:
>
|
|
| (17) |
>
|
|
| (18) |
>
|
|
| (19) |
>
|
|
| (20) |
>
|
|
| (21) |
>
|
|
| (22) |
>
|
|
| (23) |
>
|
|
| (24) |
>
|
|
| (25) |
>
|
|
| (26) |
>
|
|
| (27) |
>
|
|
| (28) |
>
|
|
| (29) |
>
|
|
| (30) |
|
|
References
|
|
|
F. Boulier, C. Chen, F. Lemaire, M. Moreno Maza "Real root isolation of regular chains." ASCM'2009, Math-for-Industry, Lecture Note Series Vol. 22.
|
|
R. Rioboo "Computation of the real closure of an ordered field." ISSAC'92, Academic Press, San Francisco.
|
|
L. Yang, K. Hou, B. Xia "A complete algorithm for automated discovering of a class of inequality-type theorems." Sci. China Ser. F, Vol. 44 (2001): 33-49.
|
|
B. Xia, L. Yang "An Algorithm for Isolating the Real Solutions of Semi-algebraic Systems." J. Symb. Comput. , Vol. 34, Num. 5 (2002): 461-477.
|
|
B. Xia, T. Zhang "Real Solution Isolation Using Interval Arithmetic." Computers and Mathematics with Applications, Vol. 52, (2006): 853-860.
|
|
|