-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | Root-finding algorithms (1-dimensional)
--   
--   Framework for and a few implementations of (1-dimensional) numerical
--   root-finding algorithms.
@package roots
@version 0.1

module Math.Root.Finder

-- | General interface for numerical root finders.
class RootFinder r a b
initRootFinder :: RootFinder r a b => (a -> b) -> a -> a -> r a b
stepRootFinder :: RootFinder r a b => (a -> b) -> r a b -> r a b
estimateRoot :: RootFinder r a b => r a b -> a
estimateError :: RootFinder r a b => r a b -> a
converged :: (RootFinder r a b, Num a, Ord a) => a -> r a b -> Bool
defaultNSteps :: RootFinder r a b => Tagged (r a b) Int

-- | <tt>traceRoot f x0 x1 mbEps</tt> initializes a root finder and
--   repeatedly steps it, returning each step of the process in a list.
--   When the algorithm terminates or the <a>defaultNSteps</a> limit is
--   exceeded, the list ends. Termination criteria depends on
--   <tt>mbEps</tt>; if it is of the form <tt>Just eps</tt> then
--   convergence to <tt>eps</tt> is used (using the <tt>converged</tt>
--   method of the root finder). Otherwise, the trace is not terminated
--   until subsequent states are equal (according to <a>==</a>). This is a
--   stricter condition than convergence to 0; subsequent states may have
--   converged to zero but as long as any internal state changes the trace
--   will continue.
traceRoot :: (Eq (r a b), RootFinder r a b, Num a, Ord a) => (a -> b) -> a -> a -> Maybe a -> [r a b]

-- | <tt>findRoot f x0 x1 eps</tt> initializes a root finder and repeatedly
--   steps it. When the algorithm converges to <tt>eps</tt> or the
--   <a>defaultNSteps</a> limit is exceeded, the current best guess is
--   returned, with the <tt>Right</tt> constructor indicating successful
--   convergence or the <tt>Left</tt> constructor indicating failure to
--   converge.
findRoot :: (RootFinder r a b, Num a, Ord a) => (a -> b) -> a -> a -> a -> Either (r a b) (r a b)

-- | A useful constant: <a>eps</a> is (for most <a>RealFloat</a> types) the
--   smallest positive number such that <tt>1 + eps /= 1</tt>.
eps :: RealFloat a => a

module Math.Root.Finder.Bisection

-- | Bisect an interval in search of a root. At all times, <tt>f
--   (estimateRoot _)</tt> is less than or equal to 0 and <tt>f
--   (estimateRoot _ + estimateError _)</tt> is greater than or equal to 0.
data Bisect a b

-- | Using bisection, return a root of a function known to lie between x1
--   and x2. The root will be refined till its accuracy is +-xacc. If
--   convergence fails, returns the final state of the search.
bisection :: (Ord a, Fractional a, Ord b, Num b) => (a -> b) -> a -> a -> a -> Either (Bisect a b) a
instance (Eq a, Eq b) => Eq (Bisect a b)
instance (Ord a, Ord b) => Ord (Bisect a b)
instance (Show a, Show b) => Show (Bisect a b)
instance (Fractional a, Ord b, Num b) => RootFinder Bisect a b

module Math.Root.Finder.Dekker
data Dekker a b

-- | <tt>dekker f x1 x2 xacc</tt>: attempt to find a root of a function
--   known to lie between x1 and x2, using Dekker's method. The root will
--   be refined till its accuracy is +-xacc. If convergence fails, returns
--   the final state of the search.
dekker :: RealFloat a => (a -> a) -> a -> a -> a -> Either (Dekker a a) a
instance (Eq a, Eq b) => Eq (Dekker a b)
instance (Show a, Show b) => Show (Dekker a b)
instance (Fractional a, Ord a, Real b, Fractional b, Ord b) => RootFinder Dekker a b

module Math.Root.Finder.FalsePosition

-- | Iteratively refine a bracketing interval [x1, x2] of a root of f until
--   total convergence (which may or may not ever be achieved) using the
--   false-position method.
data FalsePosition a b

-- | <tt>falsePosition f x1 x2 xacc</tt>: Using the false-position method,
--   return a root of a function known to lie between x1 and x2. The root
--   is refined until its accuracy is += xacc.
falsePosition :: (Ord a, Fractional a) => (a -> a) -> a -> a -> a -> Either (FalsePosition a a) a
instance Eq a => Eq (FalsePosition a b)
instance Show a => Show (FalsePosition a b)
instance (Fractional a, Ord a) => RootFinder FalsePosition a a

module Math.Root.Finder.InverseQuadratic
data InverseQuadratic a b

-- | <tt>inverseQuadratic f x1 x2 xacc</tt>: attempt to find a root of a
--   function known to lie between x1 and x2, using the inverse quadratic
--   interpolation method. The root will be refined till its accuracy is
--   +-xacc. If convergence fails, returns the final state of the search.
inverseQuadratic :: RealFloat a => (a -> a) -> a -> a -> a -> Either (InverseQuadratic a a) a
instance (Eq a, Eq b) => Eq (InverseQuadratic a b)
instance (Show a, Show b) => Show (InverseQuadratic a b)
instance (Fractional a, Ord a, Real b, Fractional b) => RootFinder InverseQuadratic a b

module Math.Root.Finder.Newton
data Newton a b

-- | <tt>newton f x1 x2 xacc</tt>: using Newton's method, return a root of
--   a function known to lie between x1 and x2. The root is refined until
--   its accuracy is += xacc.
--   
--   The function passed should return a pair containing the value of the
--   function and its derivative, respectively.
newton :: (Ord a, Fractional a) => (a -> (a, a)) -> a -> a -> a -> Either (Newton a (a, a)) a
instance Eq a => Eq (Newton a b)
instance Show a => Show (Newton a b)
instance Fractional a => RootFinder Newton a (a, a)

module Math.Root.Finder.Ridders
data RiddersMethod a b

-- | <tt>ridders f x1 x2 xacc</tt>: attempt to find a root of a function
--   known to lie between x1 and x2, using Ridders' method. The root will
--   be refined till its accuracy is +-xacc. If convergence fails, returns
--   the final state of the search.
ridders :: (Ord a, Floating a) => (a -> a) -> a -> a -> a -> Either (RiddersMethod a a) a
instance (Eq a, Eq b) => Eq (RiddersMethod a b)
instance (Show a, Show b) => Show (RiddersMethod a b)
instance (Floating a, Ord a) => RootFinder RiddersMethod a a

module Math.Root.Finder.Secant

-- | Iteratively refine 2 estimates x1, x2 of a root of f until total
--   convergence (which may or may not ever be achieved) using the secant
--   method.
data SecantMethod a b

-- | <tt>secant f x1 x2 xacc</tt>: Using the secant method, return the root
--   of a function thought to lie between x1 and x2. The root is refined
--   until its accuracy is +-xacc.
secant :: (Ord a, Fractional a) => (a -> a) -> a -> a -> a -> Either (SecantMethod a a) a
instance (Eq a, Eq b) => Eq (SecantMethod a b)
instance (Show a, Show b) => Show (SecantMethod a b)
instance (Fractional a, Ord a) => RootFinder SecantMethod a a

module Math.Root.Bracket

-- | Predicate that returns <a>True</a> whenever the given pair of points
--   brackets a root of the given function.
brackets :: (Eq a, Num b) => (a -> b) -> (a, a) -> Bool

-- | <tt>bracket f x1 x2</tt>: Given a function and an initial guessed
--   range x1 to x2, this function expands the range geometrically until a
--   root is bracketed by the returned values, returning a list of the
--   successively expanded ranges. The list will be finite if and only if
--   the sequence yields a bracketing pair.
bracket :: (Fractional a, Num b, Ord b) => (a -> b) -> a -> a -> [(a, a)]

-- | <tt>subdivideAndBracket f x1 x2 n</tt>: Given a function defined on
--   the interval [x1,x2], subdivide the interval into n equally spaced
--   segments and search for zero crossings of the function. The returned
--   list will contain all bracketing pairs found.
subdivideAndBracket :: (Num b, Fractional a, Integral c) => (a -> b) -> a -> a -> c -> [(a, a)]

module Math.Root.Finder.Brent

-- | Working state for Brent's root-finding method.
data Brent a b

-- | <tt>brent f x1 x2 xacc</tt>: attempt to find a root of a function
--   known to lie between x1 and x2, using Brent's method. The root will be
--   refined till its accuracy is +-xacc. If convergence fails, returns the
--   final state of the search.
brent :: RealFloat a => (a -> a) -> a -> a -> a -> Either (Brent a a) a
instance (Eq a, Eq b) => Eq (Brent a b)
instance (Show a, Show b) => Show (Brent a b)
instance (RealFloat a, Real b, Fractional b) => RootFinder Brent a b