edu.jas.root
Class RealRootAbstract<C extends RingElem<C> & Rational>

java.lang.Object
  edu.jas.root.RealRootAbstract<C>

Type Parameters:

C - coefficient type.

All Implemented Interfaces:

RealRoots<C>

Direct Known Subclasses:

RealRootsSturm

public abstract class RealRootAbstract<C extends RingElem<C> & Rational>
extends java.lang.Object
implements RealRoots<C>

Real roots abstract class.

Author:

Heinz Kredel

Constructor Summary

RealRootAbstract()

Method Summary

BigDecimal	approximateRoot(Interval<C> iv, GenPolynomial<C> f, C eps) Approximate real root.
java.util.List<BigDecimal>	approximateRoots(GenPolynomial<C> f, C eps) Approximate real roots.
C	bisectionPoint(Interval<C> iv, GenPolynomial<C> f) Bi-section point.
Interval<C>	halfInterval(Interval<C> iv, GenPolynomial<C> f) Half interval.
Interval<C>	invariantMagnitudeInterval(Interval<C> iv, GenPolynomial<C> f, GenPolynomial<C> g, C eps) Invariant interval for algebraic number magnitude.
abstract Interval<C>	invariantSignInterval(Interval<C> iv, GenPolynomial<C> f, GenPolynomial<C> g) Invariant interval for algebraic number sign.
boolean	isApproximateRoot(BigDecimal x, GenPolynomial<BigDecimal> f, GenPolynomial<BigDecimal> fp, BigDecimal eps) Test if x is an approximate real root.
boolean	isApproximateRoot(BigDecimal x, GenPolynomial<C> f, C eps) Test if x is an approximate real root.
boolean	isApproximateRoot(java.util.List<BigDecimal> R, GenPolynomial<C> f, C eps) Test if each x in R is an approximate real root.
C	magnitudeBound(Interval<C> iv, GenPolynomial<C> f) Magnitude bound.
C	realIntervalMagnitude(Interval<C> iv, GenPolynomial<C> f, GenPolynomial<C> g) Real algebraic number magnitude.
int	realIntervalSign(Interval<C> iv, GenPolynomial<C> f, GenPolynomial<C> g) Real algebraic number sign.
C	realMagnitude(Interval<C> iv, GenPolynomial<C> f, GenPolynomial<C> g, C eps) Real algebraic number magnitude.
C	realRootBound(GenPolynomial<C> f) Real root bound.
abstract long	realRootCount(Interval<C> iv, GenPolynomial<C> f) Number of real roots in interval.
abstract java.util.List<Interval<C>>	realRoots(GenPolynomial<C> f) Isolating intervals for the real roots.
java.util.List<Interval<C>>	realRoots(GenPolynomial<C> f, BigRational eps) Isolating intervals for the real roots.
java.util.List<Interval<C>>	realRoots(GenPolynomial<C> f, C eps) Isolating intervals for the real roots.
int	realSign(Interval<C> iv, GenPolynomial<C> f, GenPolynomial<C> g) Real algebraic number sign.
Interval<C>	refineInterval(Interval<C> iv, GenPolynomial<C> f, C eps) Refine interval.
java.util.List<Interval<C>>	refineIntervals(java.util.List<Interval<C>> V, GenPolynomial<C> f, C eps) Refine intervals.
boolean	signChange(Interval<C> iv, GenPolynomial<C> f) Sign changes on interval bounds.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

RealRootAbstract

public RealRootAbstract()

Method Detail

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.

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 java.util.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 intervalls for the real roots of f.

realRoots

public java.util.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 java.util.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,
                                  C 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 java.util.List<Interval<C>> refineIntervals(java.util.List<Interval<C>> V,
                                                   GenPolynomial<C> f,
                                                   C 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,
                                              C 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,
                       C 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) .

approximateRoot

public BigDecimal approximateRoot(Interval<C> iv,
                                  GenPolynomial<C> f,
                                  C 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 java.util.List<BigDecimal> approximateRoots(GenPolynomial<C> f,
                                                   C 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, deriviative 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(java.util.List<BigDecimal> R,
                                 GenPolynomial<C> f,
                                 C 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.