Package edu.jas.root

Class RealRootsAbstract<C extends RingElem<C> & Rational>

java.lang.Object
edu.jas.root.RealRootsAbstract<C>
Type Parameters:
C - coefficient type.
All Implemented Interfaces:
RealRoots<C>, Serializable
Direct Known Subclasses:
RealRootsSturm

public abstract class RealRootsAbstract<C extends RingElem<C> & Rational> extends Object implements RealRoots<C>
Real roots abstract class.
See Also:
  • Field Details

    • logger

      private static final org.apache.logging.log4j.Logger logger
  • Constructor Details

    • RealRootsAbstract

      public RealRootsAbstract()
  • Method Details

    • realRootBound

      public C realRootBound(GenPolynomial<C> f)
      Real root bound. With f(-M) * f(M) != 0.
      Specified by:
      realRootBound in interface RealRoots<C extends RingElem<C> & Rational>
      Parameters:
      f - univariate polynomial.
      Returns:
      M such that -M < root(f) < M.
    • magnitudeBound

      public C magnitudeBound(Interval<C> iv, GenPolynomial<C> f)
      Magnitude bound.
      Parameters:
      iv - interval.
      f - univariate polynomial.
      Returns:
      B such that |f(c)| < B for c in iv.
    • realMinimalRootBound

      public C realMinimalRootBound(GenPolynomial<C> f)
      Real minimal root bound.
      Parameters:
      f - univariate polynomial.
      Returns:
      M such that abs(xi) > M for f(xi) == 0.
    • realMinimalRootSeparation

      public C realMinimalRootSeparation(GenPolynomial<C> f)
      Real minimal root separation.
      Parameters:
      f - univariate polynomial.
      Returns:
      M such that abs(xi-xj) > M for roots xi, xj of f.
    • bisectionPoint

      public C bisectionPoint(Interval<C> iv, GenPolynomial<C> f)
      Bi-section point.
      Parameters:
      iv - interval with f(left) * f(right) != 0.
      f - univariate polynomial, non-zero.
      Returns:
      a point c in the interval iv such that f(c) != 0.
    • realRoots

      public abstract List<Interval<C>> realRoots(GenPolynomial<C> f)
      Isolating intervals for the real roots.
      Specified by:
      realRoots in interface RealRoots<C extends RingElem<C> & Rational>
      Parameters:
      f - univariate polynomial.
      Returns:
      a list of isolating intervals for the real roots of f.
    • realRoots

      public List<Interval<C>> realRoots(GenPolynomial<C> f, C eps)
      Isolating intervals for the real roots.
      Specified by:
      realRoots in interface RealRoots<C extends RingElem<C> & Rational>
      Parameters:
      f - univariate polynomial.
      eps - requested intervals length.
      Returns:
      a list of isolating intervals v such that |v| < eps.
    • realRoots

      public List<Interval<C>> realRoots(GenPolynomial<C> f, BigRational eps)
      Isolating intervals for the real roots.
      Specified by:
      realRoots in interface RealRoots<C extends RingElem<C> & Rational>
      Parameters:
      f - univariate polynomial.
      eps - requested intervals length.
      Returns:
      a list of isolating intervals v such that |v| < eps.
    • signChange

      public boolean signChange(Interval<C> iv, GenPolynomial<C> f)
      Sign changes on interval bounds.
      Specified by:
      signChange in interface RealRoots<C extends RingElem<C> & Rational>
      Parameters:
      iv - root isolating interval with f(left) * f(right) != 0.
      f - univariate polynomial.
      Returns:
      true if f(left) * f(right) < 0, else false
    • realRootCount

      public abstract long realRootCount(Interval<C> iv, GenPolynomial<C> f)
      Number of real roots in interval.
      Specified by:
      realRootCount in interface RealRoots<C extends RingElem<C> & Rational>
      Parameters:
      iv - interval with f(left) * f(right) != 0.
      f - univariate polynomial.
      Returns:
      number of real roots of f in I.
    • halfInterval

      public Interval<C> halfInterval(Interval<C> iv, GenPolynomial<C> f)
      Half interval.
      Parameters:
      iv - root isolating interval with f(left) * f(right) < 0.
      f - univariate polynomial, non-zero.
      Returns:
      a new interval v such that |v| < |iv|/2.
    • refineInterval

      public Interval<C> refineInterval(Interval<C> iv, GenPolynomial<C> f, BigRational eps)
      Refine interval.
      Specified by:
      refineInterval in interface RealRoots<C extends RingElem<C> & Rational>
      Parameters:
      iv - root isolating interval with f(left) * f(right) < 0.
      f - univariate polynomial, non-zero.
      eps - requested interval length.
      Returns:
      a new interval v such that |v| < eps.
    • refineIntervals

      public List<Interval<C>> refineIntervals(List<Interval<C>> V, GenPolynomial<C> f, BigRational eps)
      Refine intervals.
      Specified by:
      refineIntervals in interface RealRoots<C extends RingElem<C> & Rational>
      Parameters:
      V - list of isolating intervals with f(left) * f(right) < 0.
      f - univariate polynomial, non-zero.
      eps - requested intervals length.
      Returns:
      a list of new intervals v such that |v| < eps.
    • invariantSignInterval

      public abstract Interval<C> invariantSignInterval(Interval<C> iv, GenPolynomial<C> f, GenPolynomial<C> g)
      Invariant interval for algebraic number sign.
      Parameters:
      iv - root isolating interval for f, with f(left) * f(right) < 0.
      f - univariate polynomial, non-zero.
      g - univariate polynomial, gcd(f,g) == 1.
      Returns:
      v with v a new interval contained in iv such that g(v) != 0.
    • realIntervalSign

      public int realIntervalSign(Interval<C> iv, GenPolynomial<C> f, GenPolynomial<C> g)
      Real algebraic number sign.
      Parameters:
      iv - root isolating interval for f, with f(left) * f(right) < 0, with iv such that g(iv) != 0.
      f - univariate polynomial, non-zero.
      g - univariate polynomial, gcd(f,g) == 1.
      Returns:
      sign(g(iv)) .
    • realSign

      public int realSign(Interval<C> iv, GenPolynomial<C> f, GenPolynomial<C> g)
      Real algebraic number sign.
      Specified by:
      realSign in interface RealRoots<C extends RingElem<C> & Rational>
      Parameters:
      iv - root isolating interval for f, with f(left) * f(right) < 0.
      f - univariate polynomial, non-zero.
      g - univariate polynomial, gcd(f,g) == 1.
      Returns:
      sign(g(v)), with v a new interval contained in iv such that g(v) != 0.
    • invariantMagnitudeInterval

      public Interval<C> invariantMagnitudeInterval(Interval<C> iv, GenPolynomial<C> f, GenPolynomial<C> g, BigRational eps)
      Invariant interval for algebraic number magnitude.
      Parameters:
      iv - root isolating interval for f, with f(left) * f(right) < 0.
      f - univariate polynomial, non-zero.
      g - univariate polynomial, gcd(f,g) == 1.
      eps - length limit for interval length.
      Returns:
      v with v a new interval contained in iv such that |g(a) - g(b)| < eps for a, b in v in iv.
    • realIntervalMagnitude

      public C realIntervalMagnitude(Interval<C> iv, GenPolynomial<C> f, GenPolynomial<C> g)
      Real algebraic number magnitude.
      Parameters:
      iv - root isolating interval for f, with f(left) * f(right) < 0, with iv such that |g(a) - g(b)| < eps for a, b in iv.
      f - univariate polynomial, non-zero.
      g - univariate polynomial, gcd(f,g) == 1.
      Returns:
      g(iv) .
    • realMagnitude

      public C realMagnitude(Interval<C> iv, GenPolynomial<C> f, GenPolynomial<C> g, BigRational eps)
      Real algebraic number magnitude.
      Specified by:
      realMagnitude in interface RealRoots<C extends RingElem<C> & Rational>
      Parameters:
      iv - root isolating interval for f, with f(left) * f(right) < 0.
      f - univariate polynomial, non-zero.
      g - univariate polynomial, gcd(f,g) == 1.
      eps - length limit for interval length.
      Returns:
      g(iv) .
    • realIntervalMagnitudeInterval

      public Interval<C> realIntervalMagnitudeInterval(Interval<C> iv, GenPolynomial<C> f, GenPolynomial<C> g)
      Real algebraic number magnitude.
      Parameters:
      iv - root isolating interval for f, with f(left) * f(right) < 0, with iv such that |g(a) - g(b)| < eps for a, b in iv.
      f - univariate polynomial, non-zero.
      g - univariate polynomial, gcd(f,g) == 1.
      Returns:
      Interval( g(iv.left), g(iv.right) ) .
    • approximateRoot

      public BigDecimal approximateRoot(Interval<C> iv, GenPolynomial<C> f, BigRational eps) throws NoConvergenceException
      Approximate real root.
      Parameters:
      iv - real root isolating interval with f(left) * f(right) < 0.
      f - univariate polynomial, non-zero.
      eps - requested interval length.
      Returns:
      a decimal approximation d such that |d-v| < eps, for f(v) = 0, v real.
      Throws:
      NoConvergenceException
    • approximateRoots

      public List<BigDecimal> approximateRoots(GenPolynomial<C> f, BigRational eps)
      Approximate real roots.
      Parameters:
      f - univariate polynomial, non-zero.
      eps - requested interval length.
      Returns:
      a list of decimal approximations d such that |d-v| < eps for all real v with f(v) = 0.
    • isApproximateRoot

      public boolean isApproximateRoot(BigDecimal x, GenPolynomial<C> f, C eps)
      Test if x is an approximate real root.
      Parameters:
      x - approximate real root.
      f - univariate polynomial, non-zero.
      eps - requested interval length.
      Returns:
      true if x is a decimal approximation of a real v with f(v) = 0 with |d-v| < eps, else false.
    • isApproximateRoot

      public boolean isApproximateRoot(BigDecimal x, GenPolynomial<BigDecimal> f, GenPolynomial<BigDecimal> fp, BigDecimal eps)
      Test if x is an approximate real root.
      Parameters:
      x - approximate real root.
      f - univariate polynomial, non-zero.
      fp - univariate polynomial, non-zero, derivative of f.
      eps - requested interval length.
      Returns:
      true if x is a decimal approximation of a real v with f(v) = 0 with |d-v| < eps, else false.
    • isApproximateRoot

      public boolean isApproximateRoot(List<BigDecimal> R, GenPolynomial<C> f, BigRational eps)
      Test if each x in R is an approximate real root.
      Parameters:
      R - ist of approximate real roots.
      f - univariate polynomial, non-zero.
      eps - requested interval length.
      Returns:
      true if each x in R is a decimal approximation of a real v with f(v) = 0 with |d-v| < eps, else false.
    • fourierSequence

      public List<GenPolynomial<C>> fourierSequence(GenPolynomial<C> f)
      Fourier sequence.
      Parameters:
      f - univariate polynomial.
      Returns:
      (f, f', ..., f(n)) a Fourier sequence for f.
    • signSequence

      public List<Integer> signSequence(GenPolynomial<C> f, Interval<C> v)
      Thom sign sequence.
      Parameters:
      f - univariate polynomial.
      v - interval for a real root, f(v.left) * f(v.right) < 0.
      Returns:
      (s1, s2, ..., sn) = (sign(f'(v)), .... sign(f(n)(v))) a Thom sign sequence for the real root in v of f.
    • realRootNumber

      public Long realRootNumber(GenPolynomial<C> f, Interval<C> v)
      Root number.
      Parameters:
      f - univariate polynomial.
      v - interval for a real root, f(v.left) * f(v.right) < 0.
      Returns:
      r the number of this root in the sequence a1 < a2 < ..., < am of all real roots of f