next up previous Next: Utilities procedures of ALIAS-Maple Up: ALIAS-Maple Previous: Continuation for one-dimensional system

  • La page de J-P. Merlet
  • J-P. Merlet home page
  • La page Présentation de HEPHAISTOS
  • HEPHAISTOS home page
  • La page "Présentation" de l'INRIA
  • INRIA home page


    Univariate and parametric polynomial

    Univariate polynomials

    Although Maple can deal efficiently with univariate polynomials we still provide some utilities that may help to design a C++ program to solve and manage univariate polynomial.


    Bounds for the real roots

    The procedure BoundUP allows one to create a C++ program that will determine bounds for the real roots of an univariate polynomial. Its syntax is

    where The C++ program will take as input an interval vector which will represent the range for all variables in Vars. The program will then possibly update the ranges
    [AA_low_pos, AA_high_pos]
    [AA_low_neg, AA_high_neg]
    that will contain respectively the ranges for the positive and negative real roots of the polynomial. If the program has been able to update the range for the positive roots it will set the global flag AA_Flag[0] to 1 and ALIAS_Flag[1] for the negative roots.

    Note that several such procedures may be used as soon as a different `ALIAS/ID` are given between the procedure: if `ALIAS/ID` is not an empty string all global variables AA, ALIAS_Flag will have `ALIAS/ID` appended to their names. Hence in the second above example the lower bound for the positive roots will be AA_low_posnd.

    An optional 4th argument may be a list of variable name. In that case Vars must be a single variable name. This will allow to create multiple simplification procedures for a parametric polynomial. For example if $P$ is the polynomial


    will create the simplification SIMP1 that consider $P$ as a polynomial in x while SIMP2 consider $P$ as a polynomial in y. This allows to have a single list of variable names, as required by the solving procedure, but still to generate multiple simplification procedures.

    Simplification procedures


    The procedure DeflationUP will create a simplification procedure based on a re-writting of the univariate polynomial $P(x)$ of degree $n$. Let us assume that approximate roots $x_1,\ldots x_m$ of the polynomial $P$ has been found. Then the polynomial may be written as


    where $Q(x)$ has degree $n-m$. In the generated simplification procedure a C++ program will use the ALIAS_Nb_Solution approximate roots stored in the interval matrix ALIAS_Solution to compute safely $Q,R$ and will then use the above form of $P$ to compute the interval evaluation of $P$ for the current box. If this evaluation does not include 0, then the simplification procedure will return -1, allowing the current box to be discarded.

    The syntax of this procedure is:

    where To be used the coefficients of $P$ must be either real numeric or intervals.

    Parametric polynomial

    A parametric polynomial is a polynomial whose coefficients are functions of a set of parameters (in other words it is a set of polynomials).



    Being given an expression it may be interesting to determine if it can be written as a polynomial in one variable. For example

    eq:=x^2*sin(x)+x/sin(y)+ x*exp(x):
    may be considered as a second order polynomial in $x$ with coefficients $\sin(x), 1/\sin(y),exp(x)$ but not as a polynomial in $y$. The procedure Decompose_Algebraic will provide such decomposition. The call Decompose_Algebraic(eq,x) will return
    Note that the coefficients are not collected. while the global variable ALIAS_TERMS will contain the value of the AA. If the returned polynomial has degree 0 in the variable, then the expression is not a polynomial in this variable.

    Simplification procedures

    Routh table: Routh

    The Routh table allows one to determine if all the roots of a polynomial have a negative real part. The number of sign changes in the first column of the table is the number of roots with positive real parts. The Routh table has n+1 rows, where n is the degree of the polynomial.

    The syntax of this procedure is:

    where: Type allows to control the output of this procedure: Consider the polynomial $x1+(x1+x2)*s+x2^2*s^2$ in the variable $s$. Its Routh table at 0 is:
                       [    2             ]
                       [  x2       x1    0]
                       [                  ]
                       [x1 + x2    0     0]
                       [                  ]
                       [  x1       0     0]
    The first element of the Routh table is positive and the second element of the first row is $x1+x2$. Hence a necessary condition for the polynomial for not having root with real part positive is that $x1+x2>0$. Hence writing:
    will imply that the simplification procedure will use the simplification rules $x1> -x2$ and $x2>-x1$. If x1=[-5,5] and x2=[0,4] $x1> -x2$ will imply $[-5,5]>[-4,0]$ which leads to the new range [-4,5] for $x1$

    The KharitonovConsistency procedure

    This procedure may be used when dealing with the problem of determining if the roots of a parametric polynomial all lie within a given range.

    For a parametric polynomial there is usually four Kharitonov polynomials i.e. polynomials have that have constant coefficients. It can be shown that if all the Kharitonov polynomials have the real parts of their roots of the same sign, then all the polynomials in the set will have the real part of their of the same sign. The following procedure allows to use the Kharitonov polynomials to test if there they may be roots of a parametric polynomial within a given range. Its syntax is:

    with the following parameters: This procedure will calculate for the polynomial $P(x)$ the coefficients of the polynomial $P(x-a)$. Then the simplification procedure will consider that its input box has as first element a range for $x$ and update $a$ so that the Kharitonov polynomial will indicate if the polynomial may have a root larger than the lower bound of the first element of the box or lower than the upper bound of this interval. This procedure is intended to be used in conjunction with the procedure dealing with parametric polynomials.

    The WeylFilter procedure

    Let $P$ be a polynomial and be maxroot the maximal modulus of the root of $P$. From $P$ we may derive a the unitary polynomial $Q$ such that the roots of $Q$ have a modulus lower or equal to 1 and if $w$ is a root of $Q$ then maxroot$w$ is a root of $P$.

    Let $Q=sum_{i=0}^{i=n} a_i x^i$ which may also be written as $sum_{i=0}^{i=n} b_i(x-a)^i$ where $a$ is some fixed point.

    Let a range $[a,b]$ for $x$ and let $z_0$ be the mid point of the range. We consider the square in the complex plane centered at $z_0$ and whose edge length is $b-a$. Let $\delta$ be the length of the half-diagonal of this square. If

\vert b_0\vert> \sum_{j=1}^{j=n} \vert b_j\vert\delta^j

    then the polynomial has no root in the square. For a given list of equations we consider in turn each equation and determine if it may be considered as a parametric polynomial. For example the equation $x^2\sin(x)+x\sin(y)+ x~exp(x)$ will be considered as a second order polynomial in $x$ with coefficients $\sin(x), \sin(y)+exp(x)$ (but not a polynomial in $y$). The procedure
    will consider each equation in the list Func and examine if it may considered as a parametric polynomial successively in each variable in the list Vars. If yes the Weyl filter will be used on the polynomial whose coefficients are functions of the variables in the list FullVars (all variables in Vars must be a member of FullVars). MaxRoot is a list which indicates for each variable in Vars what is the maximum modulus of the roots of all parametric polynomials in this variable. An element of MaxRoot may be a numerical value of the key-word "automatic" which indicates that the C++ program will try to determine the maximal modulus. The list TypeB indicates for each variable in Vars how are computed the $b_i$ i.e. numerically with the keyword "numeric", or symbolically (which is usually more efficient) with the keyword "symbolic". The simplification procedure will be named name and be written in the file name.C. For the previous example the procedure will be
    WeylFilter([x^2*sin(x)+x*sin(y)+ x*exp(x)],[x],[x,y],["automatic"],["symbolic"],"SIMP");
    Another example of the use of this procedure is presented in section 12.3.

    Minimal and maximal real roots of a parametric polynomial

    The basic procedures for computing the minimal and maximal roots of a parametric polynomial are:


    The difference between these two procedures is that the second one uses the derivatives of the polynomial with respect to the variables together with the derivative of the coefficients of the polynomial.

    For these procedures the flag `ALIAS/stop_opt_sol`, `ALIAS/opt_sol_max` will play the same role than Stop, Seuil[0] and Seuil[1] of the C++ procedure ALIAS_Min_Max_EigenValues, see the ALIAS-C++ reference manual.

    In the special case where the polynomial is the characteristic polynomial it may be interesting to use the specific procedures:

    which has the same argument that the previous procedures except that the last argument of Func must be a matrix.

    Possible parameters values for a given range for the roots

    It is possible to determine an approximation of the region of the parameters space (a $n$ dimensional space where each of the dimension corresponds to one of the $n$ parameters) that contain all the possible values of the parameters such that the corresponding polynomial has all its roots in a given range. This approximation will be constituted of a set of $n$ dimensional boxes written in a file. The procedure to be used is:


    Strong is a list of two elements: the first element may be 1 or 2. If it is 2 the derivative of the coefficients of the polynomial will be used. This algorithm uses a secondary bisection process and the second element of Strong gives the maximum number of boxes that can be used for the secondary algorithm.

    The range for the real roots of the polynomial is defined as:

    It is possible to improve incrementally the quality of the approximation. During the first run the flag `ALIAS/ND` will be set to 1 and the neglected boxes will be written in the file `ALIAS/ND_file`. During the next run Lim has to decreased and the flag `ALIAS/ND` has to be set to 2. This has the effect that the initial box considered by the algorithm will not be Init but the set of boxes stored in `ALIAS/ND_file`. In this run the neglected boxes will still be stored in the file, thereby allowing another run of the algorithm with a lower Lim.

    The largest square enclosed in the parameters space such that the polynomials defined by parameter values within the square have all their real roots within a given range can be computed using:

    where Center will be the center of the largest square while Edge will be the lengths of the edge of the square. If you have imperative constraint you may use the variable `ALIAS/Imperatif` as a list with 0 for non imperative constraints and 1 for imperative constraints. Note that this algorithm uses a main algorithm for getting the largest square and a secondary algorithm for calculating the minimal and maximal root of the polynomial in a given square. You may specify two different bisection mode, one for the main algorithm (`ALIAS/single_bisectiong`) and one for for the secondary algorithm (`ALIAS/single_bisection). Similarly the maximal number of boxes used by the main algorithm may be specified by `ALIAS/maxboxg` while the number of boxes used by the secondary algorithm is specified by `ALIAS/maxbox`

    Condition number

    The condition number of a polynomial may be defined either as the ratio lowest root over largest root or as the ratio ${\rm
Min}(\vert x_i\vert)$ over ${\rm Max}(\vert x_i\vert)$ where $x_i$ are the roots of the polynomial. In the later case the condition number has a value between 0 and 1. The minimal and maximal values of the condition number of a parametric polynomial in both form may be calculated using the procedure:

    where Absolute has to be set to 0 if looking for the ratio minimal root over maximal root or 1 if looking for the ratio in absolute value. The parametric polynomial should appear as last argument of Func. Note that is this last element is a matrix then the considered polynomial will be the characteristic polynomial of the matrix. This procedure may hence be used to compute the minimal and maximal value of the condition number of a matrix. Note here that the derivatives of the polynomial and of its coefficients must be available.

    Specificity for the analysis of parametric polynomials

    The following variables play a role in the procedures involving a parametric polynomial:

    For the evaluation of the coefficient of the polynomial there may be evaluation problem (for example one coefficient involves a division by an expression whose interval evaluation may include 0). To deal with this case a procedure similar to what is done for MakeF can be used:

    To create the procedure ALIAS_Coeff we may also use the Problem_Expression package (see section 2.1.5). The procedure ALIAS_Coeff will be obtained from a list of coefficients Coeff in the variable Vars with the following maple code:

    `ALIAS/low_value_expr_violated`:= -1e20;
    `ALIAS/high_value_expr_violated`:= 1e20;

    Finally the above procedures may use the simplification procedure BoundUP, see section, that uses general roots bound algorithms for determining if a polynomial may have a root within a given interval.

    next up previous Next: Utilities procedures of ALIAS-Maple Up: ALIAS-Maple Previous: Continuation for one-dimensional system
  • J-P. Merlet home page
  • La page Présentation de HEPHAISTOS
  • HEPHAISTOS home page
  • La page "Présentation" de l'INRIA
  • INRIA home page

    jean-pierre merlet