API

RootProblem(f::Function, search_region ; kwargs...)

Setup a RootProblem for searching the roots (also known as zeros) of the function f in the given search region.

search_region must be either an Interval if f is scalar or a vector of Intervals if f is vector-valued.

The returned RootProblem is an iterator that give access to the internal state of the search during the iteration, allowing to add callbacks and logging to the search.

Parameters

• contractor: Contractor used to determine the status of a region. Must be either Newton, Krawczyk, or Bisection. Bisection do not require to compute the derivative of the function, but can also never guarantee the existence of a root. Default: Newton.
• derivative: Explicit derivative of the function (or its jacobian for vector-valued functions) used by the Newton and Krawczyk contractors. Default: nothing (the derivative is computed automatically using ForwardDiff.jl).
• search_order: Order in which the sub-regions are searched. BreadthFirst (visit the largest regions first) and DepthFirst (visit the smallest regions first) are supported. Default: BreadthFirst.
• abstol: Absolute tolerance. The search is stopped when all dimensions of the remaining regions are smaller than abstol. Default: 1e-7.
• reltol: Relative tolerance. The search is stopped when all dimensions of the remaining regions are smaller than reltol * mag(interval). Default: 0.0`.
• max_iteration: The maximum number of iteration, which also corresponds to the maximum number of bisections allowed. Default: typemax(Int).
• where_bisect: Value used to bisect the region. It is used to avoid bisecting exactly on zero when starting with symmetrical regions, often leading to having a solution directly on the boundary of a region, which prevent the contractor to prove it's unicity. Default: 127/256.

roots(f::Function, search_region ; kwargs...)

Return the roots (also known as zeros) of the function f contained in the given search region (either an Interval for a scalar function or vector of Intervals for a vector valued function), together with a status.

The status of the returned regions can be either of

• :unique: the region provably contains exactly one root of f
• :unknown: the region may contain any number of roots (potentially none)

The parts of the search region that are not covered by any of the returned roots are guaranteed to contain no root of the function.

For information about the optional search parameters, see RootProblem.

Root

Object representing a possible root inside a given region. The field status is either :unknown or :unique. If status is :unique then we know that there is a unique root of the function in question inside the given region.

Internally the status may also be :empty for region guaranteed to contain no root, however such Roots are discarded by default and thus never returned by the roots function.

Fields

• region: a region (either Interval or SVector of interval representing an interval box) searched for roots.
• status: the status of the region, valid values are :empty, unknown and :unique.

isunique(rt)

Return whether a Root is unique.

root_region(rt)

Return the region associated to a Root.

root_status(rt)

Return the status of a Root.

AbstractContractor

Abstract type for contractors.

refine(root_problem::RootProblem, X::Root)

Refine a root.

Takes the derivative of a complex function and returns the real jacobian that implements it.

Solves the system of linear equations using Gaussian Elimination. Preconditioning is used when the precondition keyword argument is true.

REF: Luc Jaulin et al., Applied Interval Analysis, pg. 72

Using Base.`

Iteratively solves the system of interval linear equations and returns the solution set. Uses the Gauss-Seidel method (Hansen-Sengupta version) to solve the system. Keyword precondition to turn preconditioning off. Eldon Hansen and G. William Walster : Global Optimization Using Interval Analysis - Chapter 5 - Page 115

Preconditions the matrix A and b with the inverse of mid(A)

newton1d performs the interval Newton method on the given function f with its derivative f′ and initial interval x. Optional keyword arguments give the tolerances reltol and abstol. reltol is the tolerance on the relative error whereas abstol is the tolerance on |f(X)|, and a debug boolean argument that prints out diagnostic information.

newton1d performs the interval Newton method on the given function f and initial interval x. Optional keyword arguments give the tolerances reltol and abstol. reltol is the tolerance on the relative error whereas abstol is the tolerance on |f(X)|, and a debug boolean argument that prints out diagnostic information.

Helper function for quadratic_interval that computes roots of a real quadratic using interval arithmetic to bound rounding errors.

Function to solve a quadratic equation where the coefficients are intervals. Returns an array of intervals of the roots. Arguments a, b and c are interval coefficients of x², x and 1 respectively. The interval case differs from the non-interval case in that there might be three disjoint interval roots. In the third case, one interval root extends to −∞ and another extends to +∞. This algorithm finds the set of points where F.lo(x) ≥ 0 and the set of points where F.hi(x) ≤ 0 and takes the intersection of these two sets. Eldon Hansen and G. William Walster : Global Optimization Using Interval Analysis - Chapter 8