math-functions-0.3.3.0: Collection of tools for numeric computations

Copyright(c) 2011 Bryan O'Sullivan 2018 Alexey Khudyakov
LicenseBSD3
Maintainerbos@serpentine.com
Stabilityexperimental
Portabilityportable
Safe HaskellNone
LanguageHaskell2010

Numeric.RootFinding

Contents

Description

Haskell functions for finding the roots of real functions of real arguments. These algorithms are iterative so we provide both function returning root (or failure to find root) and list of iterations.

Synopsis

Data types

data Root a Source #

The result of searching for a root of a mathematical function.

Constructors

NotBracketed

The function does not have opposite signs when evaluated at the lower and upper bounds of the search.

SearchFailed

The search failed to converge to within the given error tolerance after the given number of iterations.

Root !a

A root was successfully found.

Instances
Monad Root Source # 
Instance details

Defined in Numeric.RootFinding

Methods

(>>=) :: Root a -> (a -> Root b) -> Root b #

(>>) :: Root a -> Root b -> Root b #

return :: a -> Root a #

fail :: String -> Root a #

Functor Root Source # 
Instance details

Defined in Numeric.RootFinding

Methods

fmap :: (a -> b) -> Root a -> Root b #

(<$) :: a -> Root b -> Root a #

Applicative Root Source # 
Instance details

Defined in Numeric.RootFinding

Methods

pure :: a -> Root a #

(<*>) :: Root (a -> b) -> Root a -> Root b #

liftA2 :: (a -> b -> c) -> Root a -> Root b -> Root c #

(*>) :: Root a -> Root b -> Root b #

(<*) :: Root a -> Root b -> Root a #

Foldable Root Source # 
Instance details

Defined in Numeric.RootFinding

Methods

fold :: Monoid m => Root m -> m #

foldMap :: Monoid m => (a -> m) -> Root a -> m #

foldr :: (a -> b -> b) -> b -> Root a -> b #

foldr' :: (a -> b -> b) -> b -> Root a -> b #

foldl :: (b -> a -> b) -> b -> Root a -> b #

foldl' :: (b -> a -> b) -> b -> Root a -> b #

foldr1 :: (a -> a -> a) -> Root a -> a #

foldl1 :: (a -> a -> a) -> Root a -> a #

toList :: Root a -> [a] #

null :: Root a -> Bool #

length :: Root a -> Int #

elem :: Eq a => a -> Root a -> Bool #

maximum :: Ord a => Root a -> a #

minimum :: Ord a => Root a -> a #

sum :: Num a => Root a -> a #

product :: Num a => Root a -> a #

Traversable Root Source # 
Instance details

Defined in Numeric.RootFinding

Methods

traverse :: Applicative f => (a -> f b) -> Root a -> f (Root b) #

sequenceA :: Applicative f => Root (f a) -> f (Root a) #

mapM :: Monad m => (a -> m b) -> Root a -> m (Root b) #

sequence :: Monad m => Root (m a) -> m (Root a) #

Alternative Root Source # 
Instance details

Defined in Numeric.RootFinding

Methods

empty :: Root a #

(<|>) :: Root a -> Root a -> Root a #

some :: Root a -> Root [a] #

many :: Root a -> Root [a] #

MonadPlus Root Source # 
Instance details

Defined in Numeric.RootFinding

Methods

mzero :: Root a #

mplus :: Root a -> Root a -> Root a #

Eq a => Eq (Root a) Source # 
Instance details

Defined in Numeric.RootFinding

Methods

(==) :: Root a -> Root a -> Bool #

(/=) :: Root a -> Root a -> Bool #

Data a => Data (Root a) Source # 
Instance details

Defined in Numeric.RootFinding

Methods

gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> Root a -> c (Root a) #

gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (Root a) #

toConstr :: Root a -> Constr #

dataTypeOf :: Root a -> DataType #

dataCast1 :: Typeable t => (forall d. Data d => c (t d)) -> Maybe (c (Root a)) #

dataCast2 :: Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (Root a)) #

gmapT :: (forall b. Data b => b -> b) -> Root a -> Root a #

gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> Root a -> r #

gmapQr :: (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> Root a -> r #

gmapQ :: (forall d. Data d => d -> u) -> Root a -> [u] #

gmapQi :: Int -> (forall d. Data d => d -> u) -> Root a -> u #

gmapM :: Monad m => (forall d. Data d => d -> m d) -> Root a -> m (Root a) #

gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> Root a -> m (Root a) #

gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> Root a -> m (Root a) #

Read a => Read (Root a) Source # 
Instance details

Defined in Numeric.RootFinding

Show a => Show (Root a) Source # 
Instance details

Defined in Numeric.RootFinding

Methods

showsPrec :: Int -> Root a -> ShowS #

show :: Root a -> String #

showList :: [Root a] -> ShowS #

Generic (Root a) Source # 
Instance details

Defined in Numeric.RootFinding

Associated Types

type Rep (Root a) :: Type -> Type #

Methods

from :: Root a -> Rep (Root a) x #

to :: Rep (Root a) x -> Root a #

NFData a => NFData (Root a) Source # 
Instance details

Defined in Numeric.RootFinding

Methods

rnf :: Root a -> () #

type Rep (Root a) Source # 
Instance details

Defined in Numeric.RootFinding

type Rep (Root a) = D1 (MetaData "Root" "Numeric.RootFinding" "math-functions-0.3.3.0-IXXnY73FfYPFs5Xokjv7oq" False) (C1 (MetaCons "NotBracketed" PrefixI False) (U1 :: Type -> Type) :+: (C1 (MetaCons "SearchFailed" PrefixI False) (U1 :: Type -> Type) :+: C1 (MetaCons "Root" PrefixI False) (S1 (MetaSel (Nothing :: Maybe Symbol) NoSourceUnpackedness SourceStrict DecidedStrict) (Rec0 a))))

fromRoot Source #

Arguments

:: a

Default value.

-> Root a

Result of search for a root.

-> a 

Returns either the result of a search for a root, or the default value if the search failed.

data Tolerance Source #

Error tolerance for finding root. It describes when root finding algorithm should stop trying to improve approximation.

Constructors

RelTol !Double

Relative error tolerance. Given RelTol ε two values are considered approximately equal if \[ \frac{|a - b|}{|\operatorname{max}(a,b)} < \varepsilon \]

AbsTol !Double

Absolute error tolerance. Given AbsTol δ two values are considered approximately equal if \[ |a - b| < \delta \]. Note that AbsTol 0 could be used to require to find approximation within machine precision.

Instances
Eq Tolerance Source # 
Instance details

Defined in Numeric.RootFinding

Data Tolerance Source # 
Instance details

Defined in Numeric.RootFinding

Methods

gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> Tolerance -> c Tolerance #

gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c Tolerance #

toConstr :: Tolerance -> Constr #

dataTypeOf :: Tolerance -> DataType #

dataCast1 :: Typeable t => (forall d. Data d => c (t d)) -> Maybe (c Tolerance) #

dataCast2 :: Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c Tolerance) #

gmapT :: (forall b. Data b => b -> b) -> Tolerance -> Tolerance #

gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> Tolerance -> r #

gmapQr :: (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> Tolerance -> r #

gmapQ :: (forall d. Data d => d -> u) -> Tolerance -> [u] #

gmapQi :: Int -> (forall d. Data d => d -> u) -> Tolerance -> u #

gmapM :: Monad m => (forall d. Data d => d -> m d) -> Tolerance -> m Tolerance #

gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> Tolerance -> m Tolerance #

gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> Tolerance -> m Tolerance #

Read Tolerance Source # 
Instance details

Defined in Numeric.RootFinding

Show Tolerance Source # 
Instance details

Defined in Numeric.RootFinding

Generic Tolerance Source # 
Instance details

Defined in Numeric.RootFinding

Associated Types

type Rep Tolerance :: Type -> Type #

type Rep Tolerance Source # 
Instance details

Defined in Numeric.RootFinding

type Rep Tolerance = D1 (MetaData "Tolerance" "Numeric.RootFinding" "math-functions-0.3.3.0-IXXnY73FfYPFs5Xokjv7oq" False) (C1 (MetaCons "RelTol" PrefixI False) (S1 (MetaSel (Nothing :: Maybe Symbol) NoSourceUnpackedness SourceStrict DecidedStrict) (Rec0 Double)) :+: C1 (MetaCons "AbsTol" PrefixI False) (S1 (MetaSel (Nothing :: Maybe Symbol) NoSourceUnpackedness SourceStrict DecidedStrict) (Rec0 Double)))

withinTolerance :: Tolerance -> Double -> Double -> Bool Source #

Check that two values are approximately equal. In addition to specification values are considered equal if they're within 1ulp of precision. No further improvement could be done anyway.

class IterationStep a where Source #

Type class for checking whether iteration converged already.

Methods

matchRoot :: Tolerance -> a -> Maybe (Root Double) Source #

Return Just root is current iteration converged within required error tolerance. Returns Nothing otherwise.

findRoot Source #

Arguments

:: IterationStep a 
=> Int

Maximum

-> Tolerance

Error tolerance

-> [a] 
-> Root Double 

Find root in lazy list of iterations.

Ridders algorithm

data RiddersParam Source #

Parameters for ridders root finding

Constructors

RiddersParam 

Fields

  • riddersMaxIter :: !Int

    Maximum number of iterations. Default = 100

  • riddersTol :: !Tolerance

    Error tolerance for root approximation. Default is relative error 4·ε, where ε is machine precision.

Instances
Eq RiddersParam Source # 
Instance details

Defined in Numeric.RootFinding

Data RiddersParam Source # 
Instance details

Defined in Numeric.RootFinding

Methods

gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> RiddersParam -> c RiddersParam #

gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c RiddersParam #

toConstr :: RiddersParam -> Constr #

dataTypeOf :: RiddersParam -> DataType #

dataCast1 :: Typeable t => (forall d. Data d => c (t d)) -> Maybe (c RiddersParam) #

dataCast2 :: Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c RiddersParam) #

gmapT :: (forall b. Data b => b -> b) -> RiddersParam -> RiddersParam #

gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> RiddersParam -> r #

gmapQr :: (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> RiddersParam -> r #

gmapQ :: (forall d. Data d => d -> u) -> RiddersParam -> [u] #

gmapQi :: Int -> (forall d. Data d => d -> u) -> RiddersParam -> u #

gmapM :: Monad m => (forall d. Data d => d -> m d) -> RiddersParam -> m RiddersParam #

gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> RiddersParam -> m RiddersParam #

gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> RiddersParam -> m RiddersParam #

Read RiddersParam Source # 
Instance details

Defined in Numeric.RootFinding

Show RiddersParam Source # 
Instance details

Defined in Numeric.RootFinding

Generic RiddersParam Source # 
Instance details

Defined in Numeric.RootFinding

Associated Types

type Rep RiddersParam :: Type -> Type #

Default RiddersParam Source # 
Instance details

Defined in Numeric.RootFinding

Methods

def :: RiddersParam #

type Rep RiddersParam Source # 
Instance details

Defined in Numeric.RootFinding

type Rep RiddersParam = D1 (MetaData "RiddersParam" "Numeric.RootFinding" "math-functions-0.3.3.0-IXXnY73FfYPFs5Xokjv7oq" False) (C1 (MetaCons "RiddersParam" PrefixI True) (S1 (MetaSel (Just "riddersMaxIter") NoSourceUnpackedness SourceStrict DecidedStrict) (Rec0 Int) :*: S1 (MetaSel (Just "riddersTol") NoSourceUnpackedness SourceStrict DecidedStrict) (Rec0 Tolerance)))

ridders Source #

Arguments

:: RiddersParam

Parameters for algorithms. def provides reasonable defaults

-> (Double, Double)

Bracket for root

-> (Double -> Double)

Function to find roots

-> Root Double 

Use the method of Ridders[Ridders1979] to compute a root of a function. It doesn't require derivative and provide quadratic convergence (number of significant digits grows quadratically with number of iterations).

The function must have opposite signs when evaluated at the lower and upper bounds of the search (i.e. the root must be bracketed). If there's more that one root in the bracket iteration will converge to some root in the bracket.

riddersIterations :: (Double, Double) -> (Double -> Double) -> [RiddersStep] Source #

List of iterations for Ridders methods. See ridders for documentation of parameters

data RiddersStep Source #

Single Ridders step. It's a bracket of root

Constructors

RiddersStep !Double !Double

Ridders step. Parameters are bracket for the root

RiddersBisect !Double !Double

Bisection step. It's fallback which is taken when Ridders update takes us out of bracket

RiddersRoot !Double

Root found

RiddersNoBracket

Root is not bracketed

Instances
Eq RiddersStep Source # 
Instance details

Defined in Numeric.RootFinding

Data RiddersStep Source # 
Instance details

Defined in Numeric.RootFinding

Methods

gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> RiddersStep -> c RiddersStep #

gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c RiddersStep #

toConstr :: RiddersStep -> Constr #

dataTypeOf :: RiddersStep -> DataType #

dataCast1 :: Typeable t => (forall d. Data d => c (t d)) -> Maybe (c RiddersStep) #

dataCast2 :: Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c RiddersStep) #

gmapT :: (forall b. Data b => b -> b) -> RiddersStep -> RiddersStep #

gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> RiddersStep -> r #

gmapQr :: (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> RiddersStep -> r #

gmapQ :: (forall d. Data d => d -> u) -> RiddersStep -> [u] #

gmapQi :: Int -> (forall d. Data d => d -> u) -> RiddersStep -> u #

gmapM :: Monad m => (forall d. Data d => d -> m d) -> RiddersStep -> m RiddersStep #

gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> RiddersStep -> m RiddersStep #

gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> RiddersStep -> m RiddersStep #

Read RiddersStep Source # 
Instance details

Defined in Numeric.RootFinding

Show RiddersStep Source # 
Instance details

Defined in Numeric.RootFinding

Generic RiddersStep Source # 
Instance details

Defined in Numeric.RootFinding

Associated Types

type Rep RiddersStep :: Type -> Type #

NFData RiddersStep Source # 
Instance details

Defined in Numeric.RootFinding

Methods

rnf :: RiddersStep -> () #

IterationStep RiddersStep Source # 
Instance details

Defined in Numeric.RootFinding

type Rep RiddersStep Source # 
Instance details

Defined in Numeric.RootFinding

Newton-Raphson algorithm

data NewtonParam Source #

Parameters for ridders root finding

Constructors

NewtonParam 

Fields

  • newtonMaxIter :: !Int

    Maximum number of iterations. Default = 50

  • newtonTol :: !Tolerance

    Error tolerance for root approximation. Default is relative error 4·ε, where ε is machine precision

Instances
Eq NewtonParam Source # 
Instance details

Defined in Numeric.RootFinding

Data NewtonParam Source # 
Instance details

Defined in Numeric.RootFinding

Methods

gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> NewtonParam -> c NewtonParam #

gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c NewtonParam #

toConstr :: NewtonParam -> Constr #

dataTypeOf :: NewtonParam -> DataType #

dataCast1 :: Typeable t => (forall d. Data d => c (t d)) -> Maybe (c NewtonParam) #

dataCast2 :: Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c NewtonParam) #

gmapT :: (forall b. Data b => b -> b) -> NewtonParam -> NewtonParam #

gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> NewtonParam -> r #

gmapQr :: (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> NewtonParam -> r #

gmapQ :: (forall d. Data d => d -> u) -> NewtonParam -> [u] #

gmapQi :: Int -> (forall d. Data d => d -> u) -> NewtonParam -> u #

gmapM :: Monad m => (forall d. Data d => d -> m d) -> NewtonParam -> m NewtonParam #

gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> NewtonParam -> m NewtonParam #

gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> NewtonParam -> m NewtonParam #

Read NewtonParam Source # 
Instance details

Defined in Numeric.RootFinding

Show NewtonParam Source # 
Instance details

Defined in Numeric.RootFinding

Generic NewtonParam Source # 
Instance details

Defined in Numeric.RootFinding

Associated Types

type Rep NewtonParam :: Type -> Type #

Default NewtonParam Source # 
Instance details

Defined in Numeric.RootFinding

Methods

def :: NewtonParam #

type Rep NewtonParam Source # 
Instance details

Defined in Numeric.RootFinding

type Rep NewtonParam = D1 (MetaData "NewtonParam" "Numeric.RootFinding" "math-functions-0.3.3.0-IXXnY73FfYPFs5Xokjv7oq" False) (C1 (MetaCons "NewtonParam" PrefixI True) (S1 (MetaSel (Just "newtonMaxIter") NoSourceUnpackedness SourceStrict DecidedStrict) (Rec0 Int) :*: S1 (MetaSel (Just "newtonTol") NoSourceUnpackedness SourceStrict DecidedStrict) (Rec0 Tolerance)))

newtonRaphson Source #

Arguments

:: NewtonParam

Parameters for algorithm. def provide reasonable defaults.

-> (Double, Double, Double)

Triple of (low bound, initial guess, upper bound). If initial guess if out of bracket middle of bracket is taken as approximation

-> (Double -> (Double, Double))

Function to find root of. It returns pair of function value and its first derivative

-> Root Double 

Solve equation using Newton-Raphson iterations.

This method require both initial guess and bounds for root. If Newton step takes us out of bounds on root function reverts to bisection.

newtonRaphsonIterations :: (Double, Double, Double) -> (Double -> (Double, Double)) -> [NewtonStep] Source #

List of iteration for Newton-Raphson algorithm. See documentation for newtonRaphson for meaning of parameters.

data NewtonStep Source #

Steps for Newton iterations

Constructors

NewtonStep !Double !Double

Normal Newton-Raphson update. Parameters are: old guess, new guess

NewtonBisection !Double !Double

Bisection fallback when Newton-Raphson iteration doesn't work. Parameters are bracket on root

NewtonRoot !Double

Root is found

NewtonNoBracket

Root is not bracketed

Instances
Eq NewtonStep Source # 
Instance details

Defined in Numeric.RootFinding

Data NewtonStep Source # 
Instance details

Defined in Numeric.RootFinding

Methods

gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> NewtonStep -> c NewtonStep #

gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c NewtonStep #

toConstr :: NewtonStep -> Constr #

dataTypeOf :: NewtonStep -> DataType #

dataCast1 :: Typeable t => (forall d. Data d => c (t d)) -> Maybe (c NewtonStep) #

dataCast2 :: Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c NewtonStep) #

gmapT :: (forall b. Data b => b -> b) -> NewtonStep -> NewtonStep #

gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> NewtonStep -> r #

gmapQr :: (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> NewtonStep -> r #

gmapQ :: (forall d. Data d => d -> u) -> NewtonStep -> [u] #

gmapQi :: Int -> (forall d. Data d => d -> u) -> NewtonStep -> u #

gmapM :: Monad m => (forall d. Data d => d -> m d) -> NewtonStep -> m NewtonStep #

gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> NewtonStep -> m NewtonStep #

gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> NewtonStep -> m NewtonStep #

Read NewtonStep Source # 
Instance details

Defined in Numeric.RootFinding

Show NewtonStep Source # 
Instance details

Defined in Numeric.RootFinding

Generic NewtonStep Source # 
Instance details

Defined in Numeric.RootFinding

Associated Types

type Rep NewtonStep :: Type -> Type #

NFData NewtonStep Source # 
Instance details

Defined in Numeric.RootFinding

Methods

rnf :: NewtonStep -> () #

IterationStep NewtonStep Source # 
Instance details

Defined in Numeric.RootFinding

type Rep NewtonStep Source # 
Instance details

Defined in Numeric.RootFinding

References

  • Ridders, C.F.J. (1979) A new algorithm for computing a single root of a real continuous function. IEEE Transactions on Circuits and Systems 26:979–980.
  • Press W.H.; Teukolsky S.A.; Vetterling W.T.; Flannery B.P. (2007). "Section 9.2.1. Ridders' Method". /Numerical Recipes: The Art of Scientific Computing (3rd ed.)./ New York: Cambridge University Press. ISBN 978-0-521-88068-8.