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.
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
BoundUP(Func,Vars,name) BoundUP(x^3-6*x^2+11*x-6,x,"SIMP"); `ALIAS/ID`:="nd": BoundUP(y*x^3-6*x^2+11*x*y-6,[x,y],"SIMP");where
[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 to 1 and ALIAS_Flag 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 is the polynomial
`ALIAS/ID`:="1": BoundUP(y^3*x^3-6*x^2+11*x*y-6,x,"SIMP1",[x,y]); `ALIAS/ID`:="2": BoundUP(y^3*x^3-6*x^2+11*x*y-6,y,"SIMP2",[x,y]);will create the simplification SIMP1 that consider as a polynomial in x while SIMP2 consider 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.
The procedure DeflationUP will create a simplification procedure
based on a re-writting of the univariate polynomial of degree . Let us assume
that approximate roots
of the polynomial has been
found. Then the polynomial may be written as
The syntax of this procedure is:
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 with coefficients but not as a polynomial in . The procedure Decompose_Algebraic will provide such decomposition. The call Decompose_Algebraic(eq,x) will return
AA1*x^2+AA2*x+AA3*xNote 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.
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:
Routh(x1+(x1+x2)*s+x2^2*s^2,[s,x1,x2],0,0); [ 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 . Hence a necessary condition for the polynomial for not having root with real part positive is that . Hence writing:
Routh(x1+(x1+x2)*s+x2^2*s^2,[s,x1,x2],[2,[2,x1,x2]],0,"ROUTH");will imply that the simplification procedure will use the simplification rules and . If x1=[-5,5] and x2=[0,4] will imply which leads to the new range [-4,5] for
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:
KharitonovConsistency(Func,Vars,Gradient,procname)with the following parameters:
Let be a polynomial and be maxroot the maximal modulus of the root of . From we may derive a the unitary polynomial such that the roots of have a modulus lower or equal to 1 and if is a root of then maxroot is a root of .
Let which may also be written as where is some fixed point.
Let a range for and let be the mid point of the
range. We consider the square in the complex plane centered at
and whose edge length is . Let be the length of the
half-diagonal of this square.
WeylFilter(Func,Vars,FullVars,MaxRoot,TypeB,name)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 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.
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 and Seuil 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:
MinMax_Char_Poly(Func,Vars,Init,Type,Solve,Rand,Points,Min,Pm,Max,PM) MinMax_Char_Poly_Gradient(Func,Vars,Init,Type,Solve,Rand,Points,Min,Pm,Max,PM)which has the same argument that the previous procedures except that the last argument of Func must be a matrix.
It is possible to determine an approximation of the region of the parameters space (a dimensional space where each of the dimension corresponds to one of the 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 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:
[`ALIAS/opt_sol_min`,`ALIAS/opt_sol_max`]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:
MinMax_Square_Polynom_Gradient(Func,Grad,Vars,Range,Init,Rand,Points,Center,Edge)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`
The condition number of a polynomial may be defined either as the ratio lowest root over largest root or as the ratio over where 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:
MinMax_Condition_Number_Gradient(Func,Vars,Init,Type,Absolute,Rand,Min,Pm,Max,PM)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.
The following variables play a role in the procedures involving a parametric polynomial:
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; Verify_Problem_Expression(Coeff,Vars,"ALIAS_Coeff","ALIAS_Coeff");
Finally the above procedures may use the simplification procedure BoundUP, see section 18.104.22.168, that uses general roots bound algorithms for determining if a polynomial may have a root within a given interval.