001/* 002 * $Id: RealRoots.java 3989 2012-07-14 12:39:14Z kredel $ 003 */ 004 005package edu.jas.root; 006 007 008import java.io.Serializable; 009import java.util.List; 010 011import edu.jas.arith.Rational; 012import edu.jas.arith.BigRational; 013import edu.jas.poly.GenPolynomial; 014import edu.jas.structure.RingElem; 015import edu.jas.structure.GcdRingElem; 016 017 018/** 019 * Real roots interface. 020 * @param <C> coefficient type. 021 * @author Heinz Kredel 022 */ 023public interface RealRoots<C extends RingElem<C> & Rational> extends Serializable { 024 025 026 /** 027 * Real root bound. With f(M) * f(-M) != 0. 028 * @param f univariate polynomial. 029 * @return M such that -M < root(f) > M. 030 */ 031 public C realRootBound(GenPolynomial<C> f); 032 033 034 /** 035 * Isolating intervals for the real roots. 036 * @param f univariate polynomial. 037 * @return a list of isolating intervalls for the real roots of f. 038 */ 039 public List<Interval<C>> realRoots(GenPolynomial<C> f); 040 041 042 /** 043 * Isolating intervals for the real roots. 044 * @param f univariate polynomial. 045 * @param eps requested intervals length. 046 * @return a list of isolating intervals v such that |v| < eps. 047 */ 048 public List<Interval<C>> realRoots(GenPolynomial<C> f, C eps); 049 050 051 /** 052 * Isolating intervals for the real roots. 053 * @param f univariate polynomial. 054 * @param eps requested intervals length. 055 * @return a list of isolating intervals v such that |v| < eps. 056 */ 057 public List<Interval<C>> realRoots(GenPolynomial<C> f, BigRational eps); 058 059 060 /** 061 * Sign changes on interval bounds. 062 * @param iv root isolating interval with f(left) * f(right) != 0. 063 * @param f univariate polynomial. 064 * @return true if f(left) * f(right) < 0, else false 065 */ 066 public boolean signChange(Interval<C> iv, GenPolynomial<C> f); 067 068 069 /** 070 * Number of real roots in interval. 071 * @param iv interval with f(left) * f(right) != 0. 072 * @param f univariate polynomial. 073 * @return number of real roots of f in I. 074 */ 075 public long realRootCount(Interval<C> iv, GenPolynomial<C> f); 076 077 078 /** 079 * Refine interval. 080 * @param iv root isolating interval with f(left) * f(right) < 0. 081 * @param f univariate polynomial, non-zero. 082 * @param eps requested interval length. 083 * @return a new interval v such that |v| < eps. 084 */ 085 public Interval<C> refineInterval(Interval<C> iv, GenPolynomial<C> f, C eps); 086 087 088 /** 089 * Refine intervals. 090 * @param V list of isolating intervals with f(left) * f(right) < 0. 091 * @param f univariate polynomial, non-zero. 092 * @param eps requested intervals length. 093 * @return a list of new intervals v such that |v| < eps. 094 */ 095 public List<Interval<C>> refineIntervals(List<Interval<C>> V, GenPolynomial<C> f, C eps); 096 097 098 /** 099 * Real algebraic number sign. 100 * @param iv root isolating interval for f, with f(left) * f(right) < 0. 101 * @param f univariate polynomial, non-zero. 102 * @param g univariate polynomial, gcd(f,g) == 1. 103 * @return sign(g(v)), with v a new interval contained in iv such that g(v) != 104 * 0. 105 */ 106 public int realSign(Interval<C> iv, GenPolynomial<C> f, GenPolynomial<C> g); 107 108 109 /** 110 * Real algebraic number magnitude. 111 * @param iv root isolating interval for f, with f(left) * f(right) < 0. 112 * @param f univariate polynomial, non-zero. 113 * @param g univariate polynomial, gcd(f,g) == 1. 114 * @param eps length limit for interval length. 115 * @return g(iv). 116 */ 117 public C realMagnitude(Interval<C> iv, GenPolynomial<C> f, GenPolynomial<C> g, C eps); 118 119}