** Next:** Expansion of
** Up:** Utilities
** Previous:** Derivative of a polynomial
** Contents**

##

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 by the product of polynomials of type
so that

and evaluating the polynomial under this form for some interval for
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`: the value of

The interval returned by this procedure is the the interval evaluation
of for having the the interval value .
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 of degree `Degree` with cofficients `Coeff`
will be divided by the polynomial of degree `DegreeDivisor`
with coefficients `CoeffDivisor` so that the coefficient will be a
polynomial 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 includes 0) or if the degree of
is greater than the degree of . 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 by
its derivative. This can be done with

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

where 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`

** Next:** Expansion of
** Up:** Utilities
** Previous:** Derivative of a polynomial
** Contents**
Jean-Pierre Merlet
2012-12-20