Next: Verbose
mode flag Up: Commands
Previous: Symbolic
matrix manipulation
As mentionned in the previous section, ADIV let you easily compute the exact solutions of a system of linear equations. Solving a system of nonlinear equations is usually much harder. Even a single univariate equation of degree greater than four cannot in general be explicitely solved in terms of rational numbers and radicals. It is however possible, using a root finder program (like the command ROOT or PROOT of the HP48), to compute good approximate numerical solutions of a nonlinear univariate equation. We can therefore consider that a system of nonlinear equations is solved if we have reduced it into an equivalent form in which the roots can be obtained easily with a root finder program.
Solving a linear system typically involves ``eliminating''
unknowns from equations to obtain an equivalent triangularized
system which is then easy to solve. This process is known as
Gaussian elimination. Gröbner bases generalize this approach to
solve systems of nonlinear polynomial equations. The Gröbner
basis of a system of polynomial equations is a set of equations
that has the same solutions as the original system but that is
simpler, in a mathematically well-defined way, than the original
system. For example, consider the
following system of nonlinear equations,
which is represented in ALG48 by a list containing three symbolic equations. Its Gröbner basis computed by the command GBASIS is
where the missing right-hand-side of the equations are implicitly understood to be zero. Even though this new system might look at first more complex than the original one, it is actually much easier to solve because it is triangularized. The last equation depends on z alone, the second equation depends only on y and z, and the first equation depends only on x and z. Thus, using a root finder program, you can easily compute the (eight) solutions for z from the last equations, and then, by backsubstitution, the corresponding solutions for y and x.
It is well known that the existence and number of solutions of a system of linear equations can be neatly characterized in terms of the number of variables and independent equations of the system. There is no such simple characterization for nonlinear systems. In general the Gröbner basis for a system of nonlinear equations can have fewer or more equations than the original system. If there are as many equations as there are variables, and if the equations are sorted according to their leading term, the basis will often, but not always, be in triangular form suitable for backsubstitution. Moreover, if the system has no solution then the basis will include a constant and will reduce to 1. E.g.,
Even though Gröbner bases are in a sense minimal, they are not unique, and a system of equations can have several different (though equivalent) bases. The basis depends in particular on the order of the terms in the polynomials and on the order in which the variables are ``eliminated''. ALG48 always uses a lexicographic ordering for the terms (see Section 4.3) and all the Gröbner commands expect a list of variables on Stack Level 1 that specifies the order of the variables. The list of variables also specifies which variables are main variables (as opposed to coefficients) for the output format, like in the command RORD. For instance, in the example below, x, y and z are the main variables, and c is treated as a parameter,
A different and much more complicated basis would have been obtained if the regular lexicographic order, with c first, had been used.
Beside GBASIS, there are two additional Gröbner commands in ALG48: GSOLVE and GSIMP. The command GSOLVE computes the Gröbner basis of a system of polynomial equations and then factors the basis as much as possible to determine independent sets of solutions. Each set of solutions is represented by its own set of equations, and the number of independent sets of solutions is return on Stack Level 1. For instance,
returns the real number 3 on Stack Level 1, and the following three systems of equations on Stack Level 2, 3 and 4, respectively:
This means that the system has three independent sets of
solutions: the point x=1/3,y=1/6; the line x=1-y;
and the line x=0. Incidentally, the equations in this
example are the partial derivatives, with respect to x
and y, of the bivariate function . Hence, the solutions found correspond to the
critical points and singularity lines of f.
Section 2 provides an other example of GSOLVE. There the system has two independent sets of solution, one corresponding to x=0, y=1, the other given by the system
Using for instance the command QUAD or PROOT
of the HP48 it is easy to determine the two complex
solutions corresponding to that latter system: and their conjugates.
The command GSIMP computes the Gröbner basis for a given system of polynomial equations and then reduces an equation with respect to that system. The equation to reduce is given on Stack Level 3, the system of equations on Level 2, and the list of variables on Level 1. GSIMP lets you answer questions of the form what is the value of this equation, given that these side relations hold. For instance, consider the following problem from the Dutch Mathematics Olympiad of 1991:
Let a, b, c be real numbers such that a+b+c=3,
, and
. Compute
.
With GSIMP you immediatly get the solution.
Note that if we had computed the solutions for a, b,
and c using for instance GBASIS or GSOLVE
we would have obtained an irreducible third degree polynomial
(with 3 real roots). Hence, computing the actual values for a,
b, c and then substituting them back into would have involved considerably more
work than with GSIMP.
Next: Verbose
mode flag Up: Commands
Previous: Symbolic
matrix manipulation