## `numeric::realroots` -- isolate intervals containing real roots of an expression

#### Introduction

`numeric::realroots``(f(x), ..)` returns a list of intervals in which real roots of `f(x)` may exist.

#### Call(s)

`numeric::realroots(f(x), x = a..b <, eps> <, Merge>)`

#### Parameters

`f(x)` | - | an expression in one indeterminate `x`. Alternatively, an equation `f1(x)=f2(x)` equivalent to `f(x)=f1(x)-f2(x)`.
`x` | - | an identifier or an indexed identifier
`a, b` | - | finite real numbers or numerical expressions satisfying a<b

#### Options

``eps`` | - | a (small) positive real numerical value defining the precision goal
`Merge` | - | makes `numeric::realroots` merge adjacent intervals to larger intervals

#### Returns

a list [[a1,b1],[a2,b2],..] of distinct floating point intervals [a.i,b.i] of [a,b] which may contain roots of f(x). The empty list is returned, if no root exists in the search interval.

#### Side Effects

The function is sensitive to the environment variable `DIGITS`, which determines the numerical working precision.

#### Related Functions

`Dom::Interval`, `numeric::fsolve`, `numeric::polyroots`, `numeric::realroot`, `polylib::realroots`, `solve`

#### Details

- All intervals returned by `numeric::realroots` have length b.i-a.i<eps with a default value eps=0.01. The absolute precision eps of the root isolation may be redefined using the optional parameter `eps`.

- The intervals returned by `numeric::realroots` may contain roots. However, this is not conclusive: some intervals may contain no root. Cf. example 5.

- The complement [a,b] minus (_union([a.i,b.i])) of the subintervals [a.i,b.i] returned by `numeric::realroots` is guaranteed not to contain any real roots. In particular, from the return value [] one may positively conclude that no root exists in the search interval [a,b]. 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 [a,b]. Also `float(a)` and `float(b)` must produce floating point numbers.

- f(x) must not produce non-real values for real input x from the interval [a,b]. Note that this may happen, if f(x) involves non-integer powers (such as sqare roots) or logarithms.

- The expression `f(x)` must be suitable for interval arithmetic. In particular, MuPAD must be able to evaluate `f(Dom::Interval([a,b]))`. Note that not all MuPAD functions support this kind of arithmetic.

- For non-polynomial expressions f(x) this routine is rather slow. It is fast for polynomial expressions.

#### Option: `eps`

- The default value is `eps`=0.01. User defined precision goals must satisfy `eps`>= 10^(-DIGITS).

- For non-polynomial expressions computations with small precision goals may need some time!

#### Option: Merge

- By default all isolating intervals [a.i,b.i] satisfy b.i-a.i<eps where eps is the precision goal. However, adjacent intervals [a.i,b.i],[a.(i+1),b.(i+1)] with b.i=a.(i+1) may be produced. This option combines such intervals to larger intervals [a.i,b.(i+1)]. Cf. examples 3 and 4.

#### Example 1

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))

          [[-2.0, -1.99], [-1.005969517, -0.9993206625],

             [-0.001992470411, 0.004656384203],

             [0.9953357217, 1.001984576]]

The following equation is solved with an absolute precision of 4 digits:

    >> numeric::realroots(x*sin(x) = exp(-x), x = -1..1, 0.001)

                            [[0.7265625, 0.7275390625]]

#### Example 2

The following expression does not have a real root:

    >> numeric::realroots(exp(x) + x^2, x = -100..100)

                                        []

#### Example 3

We demonstrate the option Merge. If interval arithmetic can not isolate roots to the desired precision eps (default 0.01), then adjacent intervals are returned, each of length smaller than eps. This happens in the following example:

    >> numeric::realroots(ln(x^2 -2*x + 2) = 0, x = -10..10)

          [[0.869140625, 0.87890625], [0.87890625, 0.888671875],

             [0.888671875, 0.8984375], ...,

             [1.123046875, 1.1328125], [1.1328125, 1.142578125]]

With the option Merge these intervals are combined to a single larger interval:

    >> numeric::realroots(ln(x^2 -2*x + 2) = 0, x = -10..10, Merge)

                           [[0.869140625, 1.142578125]]

#### Example 4

The following expression has infinitely many solutions x=1/n with n=1,2,.. in the search interval [0,1]:

    >> numeric::realroots(sin(PI/x), x = 0..1, 0.1)

          [[0.0, 0.05625], [0.05625, 0.1125], [0.1125, 0.16875],

             [0.16875, 0.225], [0.225, 0.28125], [0.28125, 0.3375],

             [0.45, 0.50625], [0.9, 1.0]]

The first of the following intervals contains infinitely many roots:

    >> numeric::realroots(sin(PI/x), x = 0..1, 0.1, Merge)

                   [[0.0, 0.3375], [0.45, 0.50625], [0.9, 1.0]]

#### Example 5

The following equation has no root close to 0. However, interval arithmetic does not produce realistic values of sin(PI*x)/x for small intervals containing 0, so an isolating interval around 0 is returned:

    >> numeric::realroots(sin(PI*x)/x = 0, x = -1..1.2)

          [[-1.0, -0.99], [-0.0062109375, 0.00234375],

             [0.9946875, 1.003242188]]

A similar phenomenon occurs with x^x (=exp(x*ln(x)) 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)

                     [[0.0, 0.0078125], [0.328125, 0.3359375]]

This cannot be cured by increasing the precision goal:

    >> numeric::realroots(x^x*cos(PI*x) = tan(x), x = 0..1,
                          10^(-DIGITS))

              [[0.0, 5.820766091e-11], [0.3334737903, 0.3334737903]]

#### Background

- Let X be a subset of the real numbers. Interval arithmetic produces a set f(X) such that the set of image values f(x); x in X is contained in f(X). The MuPAD domain `Dom::Interval` facilitates this kind of arithmetic. The routine `numeric::realroots` computes `F:=f(Dom::Interval([a.i,b.i]))` for various subintervals [a.i,b.i] of [a,b]. 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 larger than the true image set f(x); x in [a.i,b.i].
- For polynomials f(x) the routine `polylib::realroots` is called. Its results are intersected with the search interval [a,b]. No interval arithmetic is used.

#### Changes

- used to be called `numeric::fsolve`
- The search interval is now specified by `x=a..b`. Merging of intervals used to be the default. It now must be requested by the option Merge.
- The option `eps` for controlling the precision goal was introduced. The new option Merge controls merging of the return intervals.

Do you have questions or comments?
Copyright © SciFace Software GmbH & Co. KG 2000