-- Hoogle documentation, generated by Haddock -- See Hoogle, http://www.haskell.org/hoogle/ -- | Polynomials -- -- A type for representing polynomials, several functions for -- manipulating and evaluating them, and several interesting polynomial -- sequences. @package polynomial @version 0.5 module Math.Polynomial data Endianness -- | Big-Endian (head is highest-order term) BE :: Endianness -- | Little-Endian (head is const term) LE :: Endianness data Poly a -- | Make a Poly from a list of coefficients using the specified -- coefficient order. poly :: (Num a) => Endianness -> [a] -> Poly a -- | Get the coefficients of a a Poly in the specified order. polyCoeffs :: (Num a) => Endianness -> Poly a -> [a] polyIsZero :: (Num a) => Poly a -> Bool polyIsOne :: (Num a) => Poly a -> Bool zero :: (Num a) => Poly a one :: (Num a) => Poly a x :: (Num a) => Poly a scalePoly :: (Num a) => a -> Poly a -> Poly a negatePoly :: (Num a) => Poly a -> Poly a addPoly :: (Num a) => Poly a -> Poly a -> Poly a sumPolys :: (Num a) => [Poly a] -> Poly a multPoly :: (Num a) => Poly a -> Poly a -> Poly a powPoly :: (Num a, Integral b) => Poly a -> b -> Poly a quotRemPoly :: (Fractional a) => Poly a -> Poly a -> (Poly a, Poly a) quotPoly :: (Fractional a) => Poly a -> Poly a -> Poly a remPoly :: (Fractional a) => Poly a -> Poly a -> Poly a evalPoly :: (Num a) => Poly a -> a -> a evalPolyDeriv :: (Num a) => Poly a -> a -> (a, a) evalPolyDerivs :: (Num a) => Poly a -> a -> [a] -- | "Contract" a polynomial by attempting to divide out a root. -- -- contractPoly p a returns (q,r) such that q*(x-a) -- + r == p contractPoly :: (Num a) => Poly a -> a -> (Poly a, a) gcdPoly :: (Fractional a) => Poly a -> Poly a -> Poly a -- | Separate a polynomial into a set of factors none of which have -- multiple roots, and the product of which is the original polynomial. -- Note that if division is not exact, it may fail to separate roots. -- Rational coefficients is a good idea. -- -- Useful when applicable as a way to simplify root-finding problems. separateRoots :: (Fractional a) => Poly a -> [Poly a] polyDeriv :: (Num a) => Poly a -> Poly a polyIntegral :: (Fractional a) => Poly a -> Poly a module Math.Polynomial.Bernstein -- | The Bernstein basis polynomials. The nth inner list is a -- basis for the polynomials of order n or lower. The -- nth basis consists of n polynomials of order -- n which sum to 1, and have roots of varying -- multiplicities at 0 and 1. bernstein :: [[Poly Integer]] -- | evalBernstein n v x evaluates the v'th Bernstein -- polynomial of order n at the point x. evalBernstein :: (Integral a, Num b) => a -> a -> b -> b -- | bernsteinFit n f: Approximate a function f as a -- linear combination of Bernstein polynomials of order n. This -- approximation converges slowly but uniformly to f on the -- interval [0,1]. bernsteinFit :: (Fractional b, Integral a) => a -> (b -> b) -> [b] -- | Evaluate a polynomial given as a list of n coefficients for -- the nth Bernstein basis. Roughly: -- -- 
--   evalBernsteinSeries cs = sum (zipWith scalePoly cs (bernstein !! (length cs - 1)))
--
evalBernsteinSeries :: (Num a) => [a] -> a -> a -- | de Casteljau's algorithm, returning the whole tableau. Used both for -- evaluating and splitting polynomials in Bernstein form. deCasteljau :: (Num a) => [a] -> a -> [[a]] -- | Given a polynomial in Bernstein form (that is, a list of coefficients -- for a basis set from bernstein, such as is returned by -- bernsteinFit) and a parameter value x, split the -- polynomial into two halves, mapping [0,x] and [x,1] -- respectively onto [0,1]. -- -- A typical use for this operation would be to split a Bezier curve -- (inserting a new knot at x). splitBernsteinSeries :: (Num a) => [a] -> a -> ([a], [a]) module Math.Polynomial.Chebyshev -- | The Chebyshev polynomials of the first kind with Integer -- coefficients. ts :: [Poly Integer] us :: [Poly Integer] -- | Compute the coefficients of the n'th Chebyshev polynomial of the first -- kind. t :: (Num a) => Int -> Poly a -- | Compute the coefficients of the n'th Chebyshev polynomial of the -- second kind. u :: (Num a) => Int -> Poly a -- | Evaluate the n'th Chebyshev polynomial of the first kind at a point X. -- Both more efficient and more numerically stable than computing the -- coefficients and evaluating the polynomial. evalT :: (Num a) => Int -> a -> a -- | Evaluate all the Chebyshev polynomials of the first kind at a point X. evalTs :: (Num a) => a -> [a] -- | Evaluate the n'th Chebyshev polynomial of the second kind at a point -- X. Both more efficient and more numerically stable than computing the -- coefficients and evaluating the polynomial. evalU :: (Num a) => Int -> a -> a -- | Evaluate all the Chebyshev polynomials of the second kind at a point -- X. evalUs :: (Num a) => a -> [a] -- | Evaluate the n'th Chebyshev polynomials of both kinds at a point X. evalTU :: (Num a) => Int -> a -> (a, a) -- | Evaluate all the Chebyshev polynomials of the both kinds at a point X. evalTsUs :: (Num a) => a -> ([a], [a]) -- | Compute the roots of the n'th Chebyshev polynomial of the first kind. tRoots :: (Floating a) => Int -> [a] -- | Compute the extreme points of the n'th Chebyshev polynomial of the -- first kind. tExtrema :: (Floating a) => Int -> [a] -- | chebyshevFit n f returns a list of N coefficients cs -- such that f x ~= sum (zipWith (*) cs (evalTs x)) on -- the interval -1 < x < 1. -- -- The N roots of the N'th Chebyshev polynomial are the fitting points at -- which the function will be evaluated and at which the approximation -- will be exact. These points always lie within the interval -1 < x -- < 1. Outside this interval, the approximation will diverge quickly. -- -- This function deviates from most chebyshev-fit implementations in that -- it returns the first coefficient pre-scaled so that the series -- evaluation operation is a simple inner product, since in most other -- algorithms operating on chebyshev series, that factor is almost always -- a nuissance. chebyshevFit :: (Floating a) => Int -> (a -> a) -> [a] -- | Evaluate a Chebyshev series expansion with a finite number of terms. -- -- Note that this function expects the first coefficient to be pre-scaled -- by 1/2, which is what is produced by chebyshevFit. Thus, this -- computes a simple inner product of the given list with a -- matching-length sequence of chebyshev polynomials. evalChebyshevSeries :: (Num a) => [a] -> a -> a module Math.Polynomial.Lagrange -- | Returns the Lagrange basis set of polynomials associated with a set of -- points. This is the set of polynomials each of which is 1 at -- its corresponding point in the input list and 0 at all -- others. -- -- These polynomials are especially convenient, mathematically, for -- interpolation. The interpolating polynomial for a set of points -- (x,y) is given by using the ys as coefficients for -- the basis given by lagrangeBasis xs. Computationally, this is -- not an especially stable procedure though. -- Math.Polynomial.Interpolation.lagrangePolyFit implements a -- slightly better algorithm based on the same idea. -- -- Generally it is better to not compute the coefficients at all. -- Math.Polynomial.Interpolation.polyInterp evaluates the -- interpolating polynomial directly, and is both quicker and more stable -- than any method I know of that computes the coefficients. lagrangeBasis :: (Fractional a) => [a] -> [Poly a] -- | Construct the Lagrange master polynomial for the Lagrange -- barycentric form: That is, the monic polynomial with a root at each -- point in the input list. lagrange :: (Num a) => [a] -> Poly a -- | Compute the weights associated with each abscissa in the Lagrange -- barycentric form. lagrangeWeights :: (Fractional a) => [a] -> [a] module Math.Polynomial.Interpolation -- | Evaluate a polynomial passing through the specified set of points. The -- order of the interpolating polynomial will (at most) be one less than -- the number of points given. polyInterp :: (Fractional a) => [(a, a)] -> a -> a -- | Computes the tableau generated by Neville's algorithm. Each successive -- row of the table is a list of interpolants one order higher than the -- previous, using a range of input points starting at the same position -- in the input list as the interpolant's position in the output list. neville :: (Fractional a) => [(a, a)] -> a -> [[a]] -- | Computes the tableau generated by a modified form of Neville's -- algorithm described in Numerical Recipes, Ch. 3, Sec. 2, which records -- the differences between interpolants at each level. Each pair (c,d) is -- the amount to add to the previous level's interpolant at either the -- same or the subsequent position (respectively) in order to obtain the -- new level's interpolant. Mathematically, either sum yields the same -- value, but due to numerical errors they may differ slightly, and some -- "paths" through the table may yield more accurate final results than -- others. nevilleDiffs :: (Fractional a) => [(a, a)] -> a -> [[(a, a)]] -- | Fit a polynomial to a set of points by iteratively evaluating the -- interpolated polynomial (using polyInterp) at 0 to establish -- the constant coefficient and reducing the polynomial by subtracting -- that coefficient from all y's and dividing by their corresponding x's. -- -- Slower than lagrangePolyFit but stable under different sets of -- conditions. -- -- Note that computing the coefficients of a fitting polynomial is an -- inherently ill-conditioned problem. In most cases it is both faster -- and more accurate to use polyInterp or nevilleDiffs -- instead of evaluating a fitted polynomial. iterativePolyFit :: (Fractional a) => [(a, a)] -> Poly a -- | Fit a polynomial to a set of points using barycentric Lagrange -- polynomials. -- -- Note that computing the coefficients of a fitting polynomial is an -- inherently ill-conditioned problem. In most cases it is both faster -- and more accurate to use polyInterp or nevilleDiffs -- instead of evaluating a fitted polynomial. lagrangePolyFit :: (Fractional a) => [(a, a)] -> Poly a module Math.Polynomial.Legendre -- | The Legendre polynomials with Rational coefficients. These -- polynomials form an orthogonal basis of the space of all polynomials, -- relative to the L2 inner product on [-1,1] (which is given by -- integrating the product of 2 polynomials over that range). legendres :: [Poly Rational] -- | Compute the coefficients of the n'th Legendre polynomial. legendre :: (Fractional a) => Int -> Poly a -- | Evaluate the n'th Legendre polynomial at a point X. Both more -- efficient and more numerically stable than computing the coefficients -- and evaluating the polynomial. evalLegendre :: (Fractional a) => Int -> a -> a -- | Evaluate all the Legendre polynomials at a point X. evalLegendres :: (Fractional a) => a -> [a] -- | Evaluate the n'th Legendre polynomial and its derivative at a point X. -- Both more efficient and more numerically stable than computing the -- coefficients and evaluating the polynomial. evalLegendreDeriv :: (Fractional a) => Int -> a -> (a, a) -- | Zeroes of the n'th Legendre polynomial. legendreRoots :: (Fractional b, Ord b) => Int -> b -> [b] module Math.Polynomial.Newton -- | Returns the Newton basis set of polynomials associated with a set of -- abscissas. This is the set of monic polynomials each of which is -- 0 at all previous points in the input list. newtonBasis :: (Num a) => [a] -> [Poly a] -- | This module exports a Num instance for the Poly type. -- This instance does not implement all operations, because abs -- and signum are simply not definable, so I have placed it into a -- separate module so that I can make people read this caveat ;). -- -- Use at your own risk. module Math.Polynomial.NumInstance instance (Num a) => Num (Poly a)