Euclidian division

The procedure:

 
void ALIAS_Euclidian_Division(int Degree,INTERVAL_VECTOR &Coeff1,
     INTERVAL_VECTOR &Coeff2,INTERVAL &Residu,INTERVAL &a)

computes the division of the polynomial P with interval coefficients Coeff1 by x-a and returns the polynomial P1 with coefficients Coeff2 such that P=(x-a)P1+Residu

Another procedure that perform the same process if a is a double is

 
void Divide_Single(int Degree,INTERVAL_VECTOR &Coeff1,double a, 
                   INTERVAL_VECTOR &Coeff2, INTERVAL &Residu)

For dividing a polynomial $P$ by the product of polynomials of type $(x-a_1)(x-a_2)\ldots(x-a_n)$ so that

$$P(x)=(x-a_1)(x-a_2)\ldots(x-a_n)Q(x)+R(x)$$

and evaluating the polynomial under this form for some interval $X$ for $x$ you may use

 
INTERVAL Divide_Evaluate_Multiple(int Degree,INTERVAL_VECTOR &Coeff1,
                                  int n,double *a,INTERVAL_VECTOR &X)

where

• n: the number of terms $a_i$
• a: the value of $a_1,\ldots,a_n$

The interval returned by this procedure is the the interval evaluation of $P$ for $x$ having the the interval value $X(1)$.

For the Euclidian division by an arbitrary polynomial you may use

 
int Divide_Polynom(int Degree,INTERVAL_VECTOR &Coeff,int DegreeDivisor,
                   INTERVAL_VECTOR &CoeffDivisor,
		   INTERVAL_VECTOR &CoeffQuo, INTERVAL_VECTOR &CoeffRem)

The polynomial $P$ of degree Degree with cofficients Coeff will be divided by the polynomial $S$ of degree DegreeDivisor with coefficients CoeffDivisor so that the coefficient will be a polynomial $Q$ of degree Degree-DegreeDivisor with coefficients CoeffQuo with a reminder which is a polynomial of degree DegreeDivisor and coefficients CoeffRem. This procedure returns 0 if the division is not possible (the interval coefficient of the leading term of $S$ includes 0) or if the degree of $S$ is greater than the degree of $P$. If the division has been performed this procedure will return 1.

Note that Divide_Polynom and Divide_Evaluate_Multiple may be used to perform the deflation of an univariate polynomial as soon as approximate roots for the polynomial have been found. This may be useful to decrease the computation time for solving a polynomial or for numerically instable polynomial such as the Wilkinson polynomial. A combination of Rouche filtering and of deflation allows to solve Wilkinson polynomial of order 18, while the general solving procedure will fail starting at order 13.

A special Euclidian division is the division of a polynomial $P$ by its derivative. This can be done with

 
void Quotient_UP_Derivative(int Degree,VECTOR &Coeff,VECTOR &CoeffD,VECTOR &Quo,
                            VECTOR &Rem)

where $P$ has coefficients Coeff, its derivative CoeffD and the coefficient of the division is Quo (the quotient is a polynomial of degree 1) while the coefficients of the remainder are stored in Rem