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

Copyright (c) 2011 Bryan O'Sullivan 2018 Alexey Khudyakov BSD3 bos@serpentine.com experimental portable None Haskell2010

Numeric.RootFinding

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 #

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

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 #

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
 # Instance detailsDefined in Numeric.RootFinding Methods # Instance detailsDefined in Numeric.RootFinding Methodsgfoldl :: (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 #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 # # Instance detailsDefined in Numeric.RootFinding Methods # Instance detailsDefined in Numeric.RootFinding MethodsshowList :: [Tolerance] -> ShowS # # Instance detailsDefined in Numeric.RootFinding Associated Typestype Rep Tolerance :: Type -> Type # Methodsto :: Rep Tolerance x -> Tolerance # type Rep Tolerance # Instance detailsDefined in Numeric.RootFinding type Rep Tolerance = D1 (MetaData "Tolerance" "Numeric.RootFinding" "math-functions-0.3.1.0-A6eRLijTYgl8AtduwyT4ZN" 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)))

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 #

Type class for checking whether iteration converged already.

Methods

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

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

Instances
 # Instance detailsDefined in Numeric.RootFinding Methods # Instance detailsDefined in Numeric.RootFinding Methods

Arguments

 :: IterationStep a => Int Maximum -> Tolerance Error tolerance -> [a] -> Root Double

Find root in lazy list of iterations.

# Ridders algorithm

data RiddersParam #

Parameters for ridders root finding

Constructors

 RiddersParam FieldsriddersMaxIter :: !IntMaximum number of iterations. Default = 100riddersTol :: !ToleranceError tolerance for root approximation. Default is relative error 4·ε, where ε is machine precision.
Instances
 # Instance detailsDefined in Numeric.RootFinding Methods # Instance detailsDefined in Numeric.RootFinding Methodsgfoldl :: (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 #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 # # Instance detailsDefined in Numeric.RootFinding Methods # Instance detailsDefined in Numeric.RootFinding MethodsshowList :: [RiddersParam] -> ShowS # # Instance detailsDefined in Numeric.RootFinding Associated Typestype Rep RiddersParam :: Type -> Type # Methods # Instance detailsDefined in Numeric.RootFinding Methods type Rep RiddersParam # Instance detailsDefined in Numeric.RootFinding type Rep RiddersParam = D1 (MetaData "RiddersParam" "Numeric.RootFinding" "math-functions-0.3.1.0-A6eRLijTYgl8AtduwyT4ZN" False) (C1 (MetaCons "RiddersParam" PrefixI True) (S1 (MetaSel (Just "riddersMaxIter") NoSourceUnpackedness SourceStrict DecidedStrict) (Rec0 Int) :*: S1 (MetaSel (Just "riddersTol") NoSourceUnpackedness SourceStrict DecidedStrict) (Rec0 Tolerance)))

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

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

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

# Newton-Raphson algorithm

data NewtonParam #

Parameters for ridders root finding

Constructors

 NewtonParam FieldsnewtonMaxIter :: !IntMaximum number of iterations. Default = 50newtonTol :: !ToleranceError tolerance for root approximation. Default is relative error 4·ε, where ε is machine precision
Instances
 # Instance detailsDefined in Numeric.RootFinding Methods # Instance detailsDefined in Numeric.RootFinding Methodsgfoldl :: (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 #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 # # Instance detailsDefined in Numeric.RootFinding Methods # Instance detailsDefined in Numeric.RootFinding MethodsshowList :: [NewtonParam] -> ShowS # # Instance detailsDefined in Numeric.RootFinding Associated Typestype Rep NewtonParam :: Type -> Type # Methods # Instance detailsDefined in Numeric.RootFinding Methods type Rep NewtonParam # Instance detailsDefined in Numeric.RootFinding type Rep NewtonParam = D1 (MetaData "NewtonParam" "Numeric.RootFinding" "math-functions-0.3.1.0-A6eRLijTYgl8AtduwyT4ZN" False) (C1 (MetaCons "NewtonParam" PrefixI True) (S1 (MetaSel (Just "newtonMaxIter") NoSourceUnpackedness SourceStrict DecidedStrict) (Rec0 Int) :*: S1 (MetaSel (Just "newtonTol") NoSourceUnpackedness SourceStrict DecidedStrict) (Rec0 Tolerance)))

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

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

data NewtonStep #

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
 # Instance detailsDefined in Numeric.RootFinding Methods # Instance detailsDefined in Numeric.RootFinding Methodsgfoldl :: (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 #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 # # Instance detailsDefined in Numeric.RootFinding Methods # Instance detailsDefined in Numeric.RootFinding MethodsshowList :: [NewtonStep] -> ShowS # # Instance detailsDefined in Numeric.RootFinding Associated Typestype Rep NewtonStep :: Type -> Type # Methods # Instance detailsDefined in Numeric.RootFinding Methodsrnf :: NewtonStep -> () # # Instance detailsDefined in Numeric.RootFinding Methods type Rep NewtonStep # Instance detailsDefined in Numeric.RootFinding type Rep NewtonStep = D1 (MetaData "NewtonStep" "Numeric.RootFinding" "math-functions-0.3.1.0-A6eRLijTYgl8AtduwyT4ZN" False) ((C1 (MetaCons "NewtonStep" PrefixI False) (S1 (MetaSel (Nothing :: Maybe Symbol) NoSourceUnpackedness SourceStrict DecidedStrict) (Rec0 Double) :*: S1 (MetaSel (Nothing :: Maybe Symbol) NoSourceUnpackedness SourceStrict DecidedStrict) (Rec0 Double)) :+: C1 (MetaCons "NewtonBisection" PrefixI False) (S1 (MetaSel (Nothing :: Maybe Symbol) NoSourceUnpackedness SourceStrict DecidedStrict) (Rec0 Double) :*: S1 (MetaSel (Nothing :: Maybe Symbol) NoSourceUnpackedness SourceStrict DecidedStrict) (Rec0 Double))) :+: (C1 (MetaCons "NewtonRoot" PrefixI False) (S1 (MetaSel (Nothing :: Maybe Symbol) NoSourceUnpackedness SourceStrict DecidedStrict) (Rec0 Double)) :+: C1 (MetaCons "NewtonNoBracket" PrefixI False) (U1 :: Type -> Type)))

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