Documentation |
Isolate intervals containing real roots of a univariate function
This functionality does not run in MATLAB.
numeric::realroots(f(x), <x = a .. b>, <eps>, <Merge = c>)
numeric::realroots(f(x), x = a..b) searches for real roots of f(x) in the interval . It returns a list of subintervals in which real roots of f(x) may exist. It is guaranteed that there are no real roots in the interval lying outside the union of the returned subintervals.
With Merge = FALSE, all intervals returned by numeric::realroots have length b_{i} - a_{i} < eps with a default value eps = 0.01. The absolute precision of the root isolation may be redefined using the optional parameter eps.
Note: The intervals returned by numeric::realroots define a subset of that may contain real roots. For polynomial expressions f(x), each of the subintervals of returned by numeric::realroots is guaranteed to contain exactly one root. For non-polynomial expressions f(x), however, some of the subintervals may contain no root! Cf. Example 6. |
In any case, the complement of the subintervals returned by numeric::realroots is guaranteed to contain no real roots. In particular, from the return value [], one may positively conclude that no root exists in the search interval . Cf. Example 2.
Symbolic parameters in f(x) are not allowed: float(f(x)) must evaluate to a floating point number for all x from the interval .
Infinite intervals of the form x = -infinity..b are not refined if b ≤ - 10^{5}.
Infinite intervals of the form x = a..infinity are not refined if a ≥ 10^{5}.
Such intervals are returned directly if numeric::realroots thinks that they may contain roots. Cf. Example 5.
f(x) may contain complex expressions. Only the search parameter x is assumed to be real. For complex expressions f(x), the intervals are returned where both the real and the imaginary part of the expression vanish simultaneously.
Note: The expression f(x) must be suitable for interval arithmetic. In particular, MuPAD^{®} must be able to evaluate f(a...b). Note that not all MuPAD functions support this kind of arithmetic. |
Presently, the following special functions support interval arithmetic: abs, arccos, arccosh, arccoth, arccot, arccsc, arccsch, arcsec, arcsech, arcsin, arcsinh, arctan, arctanh, arg, beta, ceil, cos, cosh, cot, coth, csc, csch, dirac, exp, floor, gamma, Im, ln, Re, round, sec, sech, sin, sinh, sqrt, tan, tanh, trunc. Real roots can be searched for any expression that is built from these functions using the standard arithmetical operations +, -, *, /, ^.
The default value is eps = 0.01. User defined precision goals must satisfy .
The function is sensitive to the environment variable DIGITS, which determines the numerical working precision.
The following expression has integer zeros. The solutions in the specified interval are approximated to the default precision 0.01:
numeric::realroots(sin(PI*x), x = -2..sqrt(2))
The following equation is solved with an absolute precision of 7 digits:
numeric::realroots(x*sin(x) = exp(-x), x = -1..1, 10^(-7))
The following expression does not have a real root:
numeric::realroots(exp(x) + x^2, x = -100..100)
We demonstrate the option Merge. If interval arithmetic can not isolate roots to the desired precision eps (default 0.01), then adjacent intervals are produced, each of length smaller than eps. This happens in the following example:
numeric::realroots(ln(x^2 -2*x + 2) = 0, x = -10..10, Merge = FALSE)
[[0.869140625, 0.87890625], [0.87890625, 0.888671875], [0.888671875, 0.8984375], [0.8984375, 0.908203125], [0.908203125, 0.91796875], [0.91796875, 0.927734375], [0.927734375, 0.9375], [0.9375, 0.947265625], [0.947265625, 0.95703125], [0.95703125, 0.966796875], [0.966796875, 0.9765625], [0.9765625, 0.986328125], [0.986328125, 0.99609375], [0.99609375, 1.005859375], [1.005859375, 1.015625], [1.015625, 1.025390625], [1.025390625, 1.03515625], [1.03515625, 1.044921875], [1.044921875, 1.0546875], [1.0546875, 1.064453125], [1.064453125, 1.07421875], [1.07421875, 1.083984375], [1.083984375, 1.09375], [1.09375, 1.103515625], [1.103515625, 1.11328125], [1.11328125, 1.123046875], [1.123046875, 1.1328125], [1.1328125, 1.142578125]]
With Merge = TRUE, these intervals are combined to a single larger interval. Since Merge = TRUE is the default setting for non-polynomial functions, it suffices to omit the option Merge = FALSE:
numeric::realroots(ln(x^2 -2*x + 2) = 0, x = -10..10)
The following expression has infinitely many solutions with n = 1, 2, … in the search interval [0, 1]:
numeric::realroots(sin(PI/x), x = 0..1, 0.1, Merge = FALSE)
Omitting Merge = FALSE, adjacent intevals are merged to larger intervals. The first of the following intervals contains infinitely many roots:
numeric::realroots(sin(PI/x), x = 0..1, 0.1)
If no search interval is specified, the entire real line is considered:
numeric::realroots(x^3 = exp(x))
Apart from two finite intervals, numeric::realroots tells us that there may be a root close to infinity (but that there is positively no root close to -infinity). Analytically, it is clear that the subinterval cannot contain a root, since grows much faster than x^{3} as x goes to infinity. If a finite upper limit for the search interval is specified, this fact is detected:
numeric::realroots(x^3 = exp(x), x = -infinity .. 10^100)
We isolate the two finite roots more closely by specifying a precision goal of :
numeric::realroots(x^3 = exp(x), x = -infinity .. 10^100, 10^(-DIGITS))
The following equation has no root close to 0. However, interval arithmetic does not produce realistic values of for small intervals containing x = 0, so an isolating interval around 0 is returned:
numeric::realroots(sin(PI*x)/x = 0, x = -1..1.2)
A similar phenomenon occurs with in a neighbourhood of x = 0. An isolating interval around 0 is returned, although no solution exists there:
numeric::realroots(x^x*cos(PI*x) = tan(x), x = 0..1)
This cannot be cured by increasing the precision goal:
numeric::realroots(x^x*cos(PI*x) = tan(x), x = 0..1, 10^(-DIGITS))
f(x) |
An expression in one indeterminate x or a list, set, array, or matrix (Cat::Matrix) of expressions. Alternatively, equations in the form f_{1}(x) = f_{2}(x) equivalent to the expressions f_{1}(x) - f_{2}(x). |
x |
An identifier or an indexed identifier |
a, b |
Real numbers or numerical expressions satisfying a < b. Also - infinity and infinity may be used. |
eps |
A (small) positive real numerical value defining the precision goal. The default value is 0.01. |
Merge |
Option, specified as Merge = b b can be TRUE or FALSE. With Merge = FALSE, numeric::realroots returns subintervals of length not larger than eps. With Merge = TRUE, numeric::realroots merges adjacent subintervals to larger intervals, i.e., subintervals of length larger than eps may be returned. The default setting is Merge = FALSE for polynomial functions f(x). Otherwise, it is Merge = TRUE. numeric::realroots isolates intervals that may contain roots. Internally, all these intervals satisfy b_{i} - a_{i} < eps where eps is the precision goal. With Merge = FALSE, these intervals are returned. With Merge = TRUE, adjacent intervals with b_{i} = a_{i + 1} are combined to larger intervals . See Example 3 and Example 4. The default setting is Merge = FALSE for polynomial functions. Otherwise, it is Merge = TRUE. |
List [[a_{1}, b_{1}], [a_{2}, b_{2}], …] of disjoint floating-point intervals which may contain roots of f(x). The empty list is returned if no root exists in the search interval [a, b].
Let X be a subset of the real numbers. Interval arithmetic produces a set F(X) such that the set of image values is contained in F(X). The MuPAD domain DOM_INTERVAL facilitates this kind of arithmetic. The routine numeric::realroots computes for various subintervals of . If F does not contain zero, then this subinterval is eliminated from the search interval. Otherwise, the subinterval is returned as a candidate for containing zeros of f(x). However, one cannot conclude that F does indeed contain at least one zero, since F is usually larger than the true image set (‘overestimation').
For polynomials f(x), the routine polylib::realroots is called. Its results are intersected with the search interval . No interval arithmetic is used for polynomial expressions. For polynomial equations, each isolating interval returned by numeric::realroots is guaranteed to contain at least one root if Merge = TRUE is specified. With the default setting of Merge = FALSE for polynomials, each isolating interval is guaranteed to contain exactly one root.