IntervalRootFinding.jl API

Externals

Types

Root  - Type
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

  • interval: a region (either Interval of IntervalBox) searched for roots.

  • status: the status of the region, valid values are :empty, unkown and :unique.

Methods

isunique  - Function
isunique(rt)

Return whether a Root is unique.

roots  - Function
roots(f, X, contractor=Newton, strategy=BreadthFirstSearch, tol=1e-15)
roots(f, deriv, X, contractor=Newton, strategy=BreadthFirstSearch, tol=1e-15)
roots(f, X, contractor, tol)
roots(f, deriv, X, contractor, tol)

Uses a generic branch and prune routine to find in principle all isolated roots of a function f:R^n → R^n in a region X, if the number of roots is finite.

Inputs:

  • f: function whose roots will be found

  • X: Interval or IntervalBox in which roots are searched

  • contractor: function that, when applied to the function f, determines the status of a given box X. It returns the new box and a symbol indicating the status. Current possible values are Bisection, Newton and Krawczyk

  • deriv: explicit derivative of f for Newton and Krawczyk

  • strategy: SearchStrategy determining the order in which regions are processed.

  • tol: Absolute tolerance. If a region has a diameter smaller than tol, it is returned with status :unknown.

quadratic_roots  - Function

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

root_status  - Function
root_status(rt)

Return the status of a Root.

Internals

Types

BBSearch  - Type
BBSearch{DATA}

Branch and bound search interface in element of type DATA.

This interface provide an iterable that perform the search.

There is currently three types of search supported BreadFirstBBSearch, DepthFirstBBSearch and KeyBBSearch, each one processing the element of the tree in a different order. When subtyping one of these, the following methods must be implemented:

  • root_element(::BBSearch): return the element with which the search is started

  • process(::BBSearch, elem::DATA): return a symbol representing the action to perform with the element elem and an object of type DATA reprensenting the state of the element after processing (may return elem unchanged).

  • bisect(::BBSearch, elem::DATA): return two elements of type DATA build by bisecting elem

Subtyping BBSearch directly allows to have control over the order in which the elements are process. To do this the following methods must be implemented:

  • root_element(::BBSearch): return the first element to be processed. Use to build the initial tree.

  • get_leaf_id!(::BBSearch, wt::BBTree): return the id of the next leaf that will be processed and remove it from the list of working leaves of wt.

  • insert_leaf!(::BBSearch, wt::BBTree, leaf::BBLeaf): insert a leaf in the list of working leaves.

Valid symbols returned by the process function

  • :store: the element is considered as final and is stored, it will not be further processed

  • :bisect: the element is bisected and each of the two resulting part will be processed

  • :discard: the element is discarded from the tree, allowing to free memory

Bisection  - Type
Bisection{F} <: Contractor{F}

Contractor type for the bisection method.

BreadthFirstSearch <: BreadthFirstBBSearch

Type implementing the BreadthFirstBBSearch interface for interval roots finding.

Fields

  • initial: region (as a Root object) in which roots are searched.

  • contractor: contractor to use (Bisection, Newton or Krawczyk)

  • tol: tolerance of the search

Contractor  - Type
Contractor{F}

Abstract type for contractors.

DepthFirstSearch <: DepthFirstBBSearch

Type implementing the DepthFirstBBSearch interface for interval roots finding.

Fields

  • initial: region (as a Root object) in which roots are searched.

  • contractor: contractor to use (Bisection, Newton or Krawczyk)

  • tol: tolerance of the search

Krawczyk  - Type
Krawczyk{F, FP} <: Contractor{F}

Contractor type for the Krawczyk method.

Fields

  • f::F: function whose roots are searched

  • f::FP: derivative or jacobian of f


(C::Krawczyk)(X, tol, α=where_bisect)

Contract an interval X using Krawczyk operator and return the contracted interval together with its status.

Inputs

  • R: Root object containing the interval to contract.

  • tol: Precision to which unique solutions are refined.

  • α: Point of bisection of intervals.

Newton  - Type
Newton{F, FP} <: Contractor{F}

Contractor type for the Newton method.

Fields

  • f::F: function whose roots are searched

  • f::FP: derivative or jacobian of f


(C::Newton)(X, tol, α=where_bisect)

Contract an interval X using Newton operator and return the contracted interval together with its status.

Inputs

  • R: Root object containing the interval to contract.

  • tol: Precision to which unique solutions are refined.

  • α: Point of bisection of intervals.

Methods

branch_and_prune  - Function
branch_and_prune(X, contractor, strategy, tol)

Generic branch and prune routine for finding isolated roots using the given contractor to determine the status of a given box X.

See the documentation of the roots function for explanation of the other arguments.

data  - Function
data(leaf::BBLeaf)

Return the data stored in the leaf.

data(wt::BBTree)

Return all the data stored in a BBTree as a list. The ordering of the elements is arbitrary.

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

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

newton1d  - Function

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.