reduce-historical/r37/doc/manual/solve.tex

\section{SOLVE Operator}\ttindex{SOLVE}
SOLVE is an operator for solving one or more simultaneous algebraic
equations. It is used with the syntax:
\begin{verbatim}
  SOLVE(EXPRN:algebraic[,VAR:kernel|,VARLIST:list of kernels])
         :list.
\end{verbatim}
{\tt EXPRN} is of the form {\tt <expression>} or
\{ {\tt <expression1>},{\tt <expression2>}, \dots \}.  Each expression is an
algebraic equation, or is the difference of the two sides of the equation.
The second argument is either a kernel or a list of kernels representing
the unknowns in the system.  This argument may be omitted if the number of
distinct, non-constant, top-level kernels equals the number of unknowns,
in which case these kernels are presumed to be the unknowns.

For one equation, {\tt SOLVE}\ttindex{SOLVE} recursively uses
factorization and decomposition, together with the known inverses of
{\tt LOG}, {\tt SIN}, {\tt COS}, {\tt \verb|^|}, {\tt ACOS}, {\tt ASIN}, and
linear, quadratic, cubic, quartic, or binomial factors. Solutions
of equations built with exponentials or logarithms are often
expressed in terms of Lambert's {\tt W} function.\index{Lambert's W}
This function is (partially) implemented in the special functions package.

Linear equations are solved by the multi-step elimination method due to
Bareiss, unless the switch {\tt CRAMER}\ttindex{CRAMER} is on, in which
case Cramer's method is used.  The Bareiss method is usually more
efficient unless the system is large and dense.

Non-linear equations are solved using the Groebner basis package.
\index{Groebner} Users should note that this can be quite a
time consuming process.

{\it Examples:}
\begin{verbatim}
            solve(log(sin(x+3))^5 = 8,x);
            solve(a*log(sin(x+3))^5 - b, sin(x+3));
            solve({a*x+y=3,y=-2},{x,y});
\end{verbatim}

{\tt SOLVE} returns a list of solutions.  If there is one unknown, each
solution is an equation for the unknown.  If a complete solution was
found, the unknown will appear by itself on the left-hand side of the
equation.  On the other hand, if the solve package could not find a
solution, the ``solution'' will be an equation for the unknown in terms
of the operator {\tt ROOT\_OF}\ttindex{ROOT\_OF}. If there
are several unknowns, each solution will be a list of equations for the
unknowns.  For example,
\begin{verbatim}
     solve(x^2=1,x);             -> {X=-1,X=1}

     solve(x^7-x^6+x^2=1,x)
                            6
            -> {X=ROOT_OF(X_  + X_ + 1,X_,TAG_1),X=1}

     solve({x+3y=7,y-x=1},{x,y}) -> {{X=1,Y=2}}.
\end{verbatim}
The TAG argument is used to uniquely identify those particular solutions.
Solution multiplicities are stored in the global variable {\tt
ROOT\_MULTIPLICITIES} rather than the solution list.  The value of this
variable is a list of the multiplicities of the solutions for the last
call of {\tt SOLVE}. \ttindex{SOLVE} For example,
\begin{verbatim}
       solve(x^2=2x-1,x); root_multiplicities;
\end{verbatim}
gives the results
\begin{verbatim}
        {X=1}

        {2}
\end{verbatim}

If you want the multiplicities explicitly displayed, the switch
{\tt MULTIPLICITIES}\ttindex{MULTIPLICITIES} can be turned on. For example
\begin{verbatim}
        on multiplicities; solve(x^2=2x-1,x);
\end{verbatim}
yields the result
\begin{verbatim}
        {X=1,X=1}
\end{verbatim}

\subsection{Handling of Undetermined Solutions}
When {\tt SOLVE} cannot find a solution to an equation, it normally
returns an equation for the relevant indeterminates in terms of the
operator {\tt ROOT\_OF}.\ttindex{ROOT\_OF}  For example, the expression
\begin{verbatim}
        solve(cos(x) + log(x),x);
\end{verbatim}
returns the result
\begin{verbatim}
       {X=ROOT_OF(COS(X_) + LOG(X_),X_,TAG_1)} .
\end{verbatim}

An expression with a top-level {\tt ROOT\_OF} operator is implicitly a
list with an unknown number of elements (since we don't always know how
many solutions an equation has).  If a substitution is made into such an
expression, closed form solutions can emerge.  If this occurs, the {\tt
ROOT\_OF} construct is replaced by an operator {\tt ONE\_OF}.\ttindex{ONE\_OF}
At this point it is of course possible to transform the result of the
original {\tt SOLVE} operator expression into a standard {\tt SOLVE}
solution.  To effect this, the operator {\tt EXPAND\_CASES}
\ttindex{EXPAND\_CASES} can be used.

The following example shows the use of these facilities:
\extendedmanual{\newpage}
\begin{verbatim}
solve(-a*x^3+a*x^2+x^4-x^3-4*x^2+4,x);
              2     3
{X=ROOT_OF(A*X_  - X_  + 4*X_ + 4,X_,TAG_2),X=1}

sub(a=-1,ws);

{X=ONE_OF({2,-1,-2},TAG_2),X=1}

expand_cases ws;

{X=2,X=-1,X=-2,X=1}
\end{verbatim}

\subsection{Solutions of Equations Involving Cubics and Quartics}

Since roots of cubics and quartics can often be very messy, a switch
{\tt FULLROOTS}\ttindex{FULLROOTS} is available, that, when off (the
default), will prevent the production of a result in closed form.  The
{\tt ROOT\_OF} construct will be used in this case instead.

In constructing the solutions of cubics and quartics, trigonometrical
forms are used where appropriate.  This option is under the control of a
switch {\tt TRIGFORM},\ttindex{TRIGFORM} which is normally on.

The following example illustrates the use of these facilities:
\begin{verbatim}
let xx = solve(x^3+x+1,x);

xx;
             3
{X=ROOT_OF(X_  + X_ + 1,X_)}

on fullroots;

xx;

                           - SQRT(31)*I
                    ATAN(---------------)
                            3*SQRT(3)
{X=(I*(SQRT(3)*SIN(-----------------------)
                              3
\end{verbatim}
\newpage
\begin{verbatim}
                      - SQRT(31)*I
               ATAN(---------------)
                       3*SQRT(3)
        - COS(-----------------------)))/SQRT(3),
                         3

                              - SQRT(31)*I
                       ATAN(---------------)
                               3*SQRT(3)
 X=( - I*(SQRT(3)*SIN(-----------------------)
                                 3

                         - SQRT(31)*I
                  ATAN(---------------)
                          3*SQRT(3)
           + COS(-----------------------)))/SQRT(
                            3

      3),

                  - SQRT(31)*I
           ATAN(---------------)
                   3*SQRT(3)
    2*COS(-----------------------)*I
                     3
 X=----------------------------------}
                SQRT(3)

off trigform;

xx;
                             2/3
{X=( - (SQRT(31) - 3*SQRT(3))   *SQRT(3)*I

                             2/3    2/3
     - (SQRT(31) - 3*SQRT(3))    - 2   *SQRT(3)*I

        2/3                           1/3  1/3
     + 2   )/(2*(SQRT(31) - 3*SQRT(3))   *6

                1/6
              *3   ),

                          2/3
 X=((SQRT(31) - 3*SQRT(3))   *SQRT(3)*I

                             2/3    2/3
     - (SQRT(31) - 3*SQRT(3))    + 2   *SQRT(3)*I

        2/3                           1/3  1/3
     + 2   )/(2*(SQRT(31) - 3*SQRT(3))   *6

                1/6
              *3   ),

                           2/3    2/3
     (SQRT(31) - 3*SQRT(3))    - 2
 X=-------------------------------------}
                          1/3  1/3  1/6
    (SQRT(31) - 3*SQRT(3))   *6   *3
\end{verbatim}

\subsection{Other Options}

If {\tt SOLVESINGULAR}\ttindex{SOLVESINGULAR} is on (the default setting),
degenerate systems such as {\tt x+y=0}, {\tt 2x+2y=0} will be solved by
introducing appropriate arbitrary constants.
The consistent singular equation 0=0 or equations involving functions with
multiple inverses may introduce unique new indeterminant kernels
{\tt ARBCOMPLEX(j)}, or {\tt ARBINT(j)}, ($j$=1,2,...),  % {\tt ARBREAL(j)},
representing arbitrary complex or integer numbers respectively.  To
automatically select the principal branches, do {\tt off allbranch;} .
\ttindex{ALLBRANCH} To avoid the introduction of new indeterminant kernels
do {\tt OFF ARBVARS}\ttindex{ARBVARS} -- then no equations are generated for the free
variables and their original names are used to express the solution forms.
To suppress solutions of consistent singular equations do
{\tt OFF SOLVESINGULAR}.

To incorporate additional inverse functions do, for example:
\begin{verbatim}
        put('sinh,'inverse,'asinh);
        put('asinh,'inverse,'sinh);
\end{verbatim}
together with any desired simplification rules such as
\begin{verbatim}
        for all x let sinh(asinh(x))=x, asinh(sinh(x))=x;
\end{verbatim}
For completeness, functions with non-unique inverses should be treated as
{\tt \verb|^|}, {\tt SIN}, and {\tt COS} are in the {\tt SOLVE}
\ttindex{SOLVE} module source.

Arguments of {\tt ASIN} and {\tt ACOS} are not checked to ensure that the
absolute value of the real part does not exceed 1; and arguments of
{\tt LOG} are not checked to  ensure that the absolute value of the imaginary
part does not exceed $\pi$; but checks (perhaps involving user response
for non-numerical arguments) could be introduced using
{\tt LET}\ttindex{LET} statements for these operators.

\subsection{Parameters and Variable Dependency}

The proper design of a variable sequence
supplied as a second argument to {\tt SOLVE} is important
for the structure of the solution of an equation system.
Any unknown in the system
not in this list is considered totally free. E.g.\  the call
\begin{verbatim}
    solve({x=2*z,z=2*y},{z});
\end{verbatim}
produces an empty list as a result because there is no function
$z=z(x,y)$ which fulfills both equations for arbitrary $x$ and $y$ values.
In such a case the share variable {\tt requirements}\ttindex{requirements}
displays a set of restrictions for the parameters of the system:
\begin{verbatim}
    requirements;

    {x - 4*y}
\end{verbatim}
The non-existence of a formal solution is caused by a 
contradiction which disappears only if the parameters
of the initial system are set such that all members
of the requirements list take the value zero.
For a linear system the set is complete: a solution
of the requirements list makes the initial
system solvable. E.g.\  in the above case a substitution
$x=4y$ makes the equation set consistent. For a non-linear
system only one inconsistency is detected. If such a system
has more than one inconsistency, you must reduce them
one after the other. 
\footnote{
The difference between linear and non--linear
inconsistent systems is based on the algorithms which
produce this information as a side effect when attempting
to find a formal solution; example:
$solve(\{x=a,x=b,y=c,y=d\},\{x,y\}$ gives a set $\{a-b,c-d\}$
while $solve(\{x^2=a,x^2=b,y^2=c,y^2=d\},\{x,y\}$ leads to $\{a-b\}$.
}
The  set shows you also the dependency among the parameters: here
one of $x$ and $y$ is free and a formal solution of the system can be
computed by adding it to the variable list of {\tt solve}. 
The requirement set is not unique -- there may be other such sets.


A system  with parameters may have a formal solution, e.g.\
\begin{verbatim}
     solve({x=a*z+1,0=b*z-y},{z,x});

        y     a*y + b
   {{z=---,x=---------}}
        b        b
\end{verbatim}
which is not valid for all possible values of the parameters.
The variable {\tt assumptions}\ttindex{assumptions} contains then a list of
restrictions: the solutions are valid only as long
as none of these expressions vanishes. Any zero of one of them
represents a special case that is not covered by the
formal solution. In the above case the value is
\extendedmanual{\newpage}
\begin{verbatim}
    assumptions;

    {b}
\end{verbatim}
which excludes formally the case $b=0$; obviously this special 
parameter value makes the system singular. The set of assumptions
is complete for both, linear and non--linear systems.
    

{\tt SOLVE} rearranges the variable sequence
to reduce the (expected) computing time. This behavior is controlled
by the switch {\tt varopt}\ttindex{varopt}, which is on by default.
If it is turned off, the supplied variable sequence is used
or the system kernel ordering is taken if the variable
list is omitted. The effect is demonstrated by an example:
\begin{verbatim}
   s:= {y^3+3x=0,x^2+y^2=1};

   solve(s,{y,x});

                  6       2
   {{y=root_of(y_  + 9*y_  - 9,y_),

            3
         - y
     x=-------}}
          3
 
   off varopt; solve(s,{y,x});

                  6       4        2
   {{x=root_of(x_  - 3*x_  + 12*x_  - 1,x_),

               4      2
        x*( - x  + 2*x  - 10)
     y=-----------------------}}
                  3

\end{verbatim}
In the first case, {\tt solve} forms the solution as a set of
pairs $(y_i,x(y_i))$ because the degree of $x$ is higher -- 
such a rearrangement makes the internal computation of the Gr\"obner basis
generally faster. For the second case the explicitly given variable sequence
is used such that the solution has now the form $(x_i,y(x_i))$.
Controlling the variable sequence is especially important if
the system has one or more free variables.
As an alternative to turning off {\tt varopt}, a partial dependency among
the variables can be declared using the {\tt depend}\index{depend}
statement: {\tt solve} then rearranges the variable sequence but keeps any
variable ahead of those on which it depends.
\extendedmanual{\newpage}
\begin{verbatim}
   on varopt;
   s:={a^3+b,b^2+c}$
   solve(s,{a,b,c});

                           3       6
   {{a=arbcomplex(1),b= - a ,c= - a }}

   depend a,c; depend b,c; solve(s,{a,b,c});

   {{c=arbcomplex(2),

                 6
     a=root_of(a_  + c,a_),

           3
     b= - a }}
\end{verbatim}
Here {\tt solve} is forced to put $c$ after $a$ and after $b$, but
there is no obstacle to interchanging $a$ and $b$.