Copyright | (c) Brent Yorgey 2010 |
---|---|
License | BSD-style (see LICENSE) |
Maintainer | byorgey@cis.upenn.edu |
Stability | experimental |
Safe Haskell | None |
Language | Haskell2010 |
The Newton-Raphson iterative method for computing with recursive
species. Any species T
which can be written in the form T =
X*R(T)
(the species of "R
-enriched rooted trees") may be
computed by a quadratically converging iterative process. In fact
we may also compute species of the form T = N + X*R(T)
for any
integer species N
, by iteratively computing T' = X*R(T' + N)
and then adding N
.
- newtonRaphsonIter :: Species s => s -> Integer -> s -> s
- newtonRaphson :: Species s => s -> Integer -> s
- newtonRaphsonRec :: (ASTFunctor f, Species s) => f -> Integer -> Maybe s
- solveForR :: (ASTFunctor f, Species s) => f -> Maybe (s, s)
Documentation
newtonRaphsonIter :: Species s => s -> Integer -> s -> s Source
A single iteration of the Newton-Raphson method.
newtonRaphsonIter r k a
assumes that a
is a species having
contact of order k
with species t = x
(that
is, *
(r ``o`` t)a
and t
agree on all label sets of size up to and
including k
), and returns a new species with contact of order
2k+2
with t
.
See BLL section 3.3.
newtonRaphson :: Species s => s -> Integer -> s Source
Given a species r
and a desired accuracy k
,
computes a species which has contact at least newtonRaphson
r kk
with the
species t = x
.*
(r ``o`` t)
newtonRaphsonRec :: (ASTFunctor f, Species s) => f -> Integer -> Maybe s Source
tries to compute the recursive species
represented by the code newtonRaphsonRec
f kf
up to order at least k
, using
Newton-Raphson iteration. Returns Nothing
if f
cannot be
written in the form f = X*R(f)
for some species R
.