Copyright | (c) Edward Kmett 2010-2015 |
---|---|

License | BSD3 |

Maintainer | ekmett@gmail.com |

Stability | experimental |

Portability | GHC only |

Safe Haskell | None |

Language | Haskell2010 |

Root finding using Halley's rational method (the second in the class of Householder methods). Assumes the function is three times continuously differentiable and converges cubically when progress can be made.

## Synopsis

- findZero :: (Fractional a, Eq a) => (forall s. AD s (Tower a) -> AD s (Tower a)) -> a -> [a]
- findZeroNoEq :: Fractional a => (forall s. AD s (Tower a) -> AD s (Tower a)) -> a -> [a]
- inverse :: (Fractional a, Eq a) => (forall s. AD s (Tower a) -> AD s (Tower a)) -> a -> a -> [a]
- inverseNoEq :: Fractional a => (forall s. AD s (Tower a) -> AD s (Tower a)) -> a -> a -> [a]
- fixedPoint :: (Fractional a, Eq a) => (forall s. AD s (Tower a) -> AD s (Tower a)) -> a -> [a]
- fixedPointNoEq :: Fractional a => (forall s. AD s (Tower a) -> AD s (Tower a)) -> a -> [a]
- extremum :: (Fractional a, Eq a) => (forall s. AD s (On (Forward (Tower a))) -> AD s (On (Forward (Tower a)))) -> a -> [a]
- extremumNoEq :: Fractional a => (forall s. AD s (On (Forward (Tower a))) -> AD s (On (Forward (Tower a)))) -> a -> [a]

# Halley's Method (Tower AD)

findZero :: (Fractional a, Eq a) => (forall s. AD s (Tower a) -> AD s (Tower a)) -> a -> [a] Source #

The `findZero`

function finds a zero of a scalar function using
Halley's method; its output is a stream of increasingly accurate
results. (Modulo the usual caveats.) If the stream becomes constant
("it converges"), no further elements are returned.

Examples:

`>>>`

[1.0,1.8571428571428572,1.9997967892704736,1.9999999999994755,2.0]`take 10 $ findZero (\x->x^2-4) 1`

`>>>`

0.0 :+ 1.0`last $ take 10 $ findZero ((+1).(^2)) (1 :+ 1)`

findZeroNoEq :: Fractional a => (forall s. AD s (Tower a) -> AD s (Tower a)) -> a -> [a] Source #

The `findZeroNoEq`

function behaves the same as `findZero`

except that it
doesn't truncate the list once the results become constant. This means it
can be used with types without an `Eq`

instance.

inverse :: (Fractional a, Eq a) => (forall s. AD s (Tower a) -> AD s (Tower a)) -> a -> a -> [a] Source #

The `inverse`

function inverts a scalar function using
Halley's method; its output is a stream of increasingly accurate
results. (Modulo the usual caveats.) If the stream becomes constant
("it converges"), no further elements are returned.

Note: the `take 10 $ inverse sqrt 1 (sqrt 10)`

example that works for Newton's method
fails with Halley's method because the preconditions do not hold!

inverseNoEq :: Fractional a => (forall s. AD s (Tower a) -> AD s (Tower a)) -> a -> a -> [a] Source #

The `inverseNoEq`

function behaves the same as `inverse`

except that it
doesn't truncate the list once the results become constant. This means it
can be used with types without an `Eq`

instance.

fixedPoint :: (Fractional a, Eq a) => (forall s. AD s (Tower a) -> AD s (Tower a)) -> a -> [a] Source #

The `fixedPoint`

function find a fixedpoint of a scalar
function using Halley's method; its output is a stream of
increasingly accurate results. (Modulo the usual caveats.)

If the stream becomes constant ("it converges"), no further elements are returned.

`>>>`

0.7390851332151607`last $ take 10 $ fixedPoint cos 1`

fixedPointNoEq :: Fractional a => (forall s. AD s (Tower a) -> AD s (Tower a)) -> a -> [a] Source #

The `fixedPointNoEq`

function behaves the same as `fixedPoint`

except that
it doesn't truncate the list once the results become constant. This means it
can be used with types without an `Eq`

instance.

extremum :: (Fractional a, Eq a) => (forall s. AD s (On (Forward (Tower a))) -> AD s (On (Forward (Tower a)))) -> a -> [a] Source #

The `extremum`

function finds an extremum of a scalar
function using Halley's method; produces a stream of increasingly
accurate results. (Modulo the usual caveats.) If the stream becomes
constant ("it converges"), no further elements are returned.

`>>>`

[1.0,0.29616942658570555,4.59979519460002e-3,1.6220740159042513e-8,0.0]`take 10 $ extremum cos 1`

extremumNoEq :: Fractional a => (forall s. AD s (On (Forward (Tower a))) -> AD s (On (Forward (Tower a)))) -> a -> [a] Source #

The `extremumNoEq`

function behaves the same as `extremum`

except that it
doesn't truncate the list once the results become constant. This means it
can be used with types without an `Eq`

instance.