reduce-historical/r38/doc/manual2/roots.tex

\chapter{ROOTS: A REDUCE root finding package}
\label{ROOTS}
\typeout{{ROOTS: A REDUCE root finding package}}

{\footnotesize
\begin{center}
Stanley L. Kameny \\
Los Angeles, U.S.A.
\end{center}
}
\ttindex{ROOTS}

The root finding package is designed so that it can be used as an
independent package, or it can be integrated with and called by {\tt
SOLVE}.\index{SOLVE package ! with ROOTS package}

\section{Top Level Functions}

The top level functions can be called either as symbolic operators from
algebraic mode, or they can be called directly from symbolic mode with
symbolic mode arguments.  Outputs are expressed in forms that print out
correctly in algebraic mode.


\subsection{Functions that refer to real roots only}

The three functions \f{REALROOTS}, \f{ISOLATER} and \f{RLROOTNO} can
receive 1, 2 or 3 arguments.

The first argument is the polynomial p, that can be complex and can
have multiple or zero roots.  If arg2 and arg3 are not present, all real
roots are found.  If the additional arguments are present, they restrict
the region of consideration.

\begin{itemize}
\item If there are two arguments the second is either POSITIVE or NEGATIVE.
The function will only find positive or negative roots

\item If arguments are (p,arg2,arg3) then
\ttindex{EXCLUDE}\ttindex{POSITIVE}\ttindex{NEGATIVE}\ttindex{INFINITY}
Arg2 and Arg3 must be r (a real number) or  EXCLUDE r,  or a member of
the list POSITIVE, NEGATIVE, INFINITY, -INFINITY.  EXCLUDE r causes the
value r to be excluded from the region.  The order of the sequence
arg2, arg3 is unimportant.  Assuming that arg2 $\leq$ arg3 when both are
numeric, then

\begin{tabular}{l c l}
\{-INFINITY,INFINITY\} & (or \{\}) & all roots; \\
\{arg2,NEGATIVE\} & represents & $-\infty < r < arg2$; \\
\{arg2,POSITIVE\} & represents & $arg2 < r < \infty$;
\end{tabular}

In each of the following, replacing an {\em arg} with EXCLUDE {\em arg}
converts the corresponding inclusive $\leq$ to the exclusive $<$

\begin{tabular}{l c l}
\{arg2,-INFINITY\} & represents & $-\infty < r \leq arg2$; \\
\{arg2,INFINITY\} & represents & $arg2 \leq r < \infty$; \\
\{arg2,arg3\} & represents & $arg2 \leq r \leq arg3$;
\end{tabular}

\item If zero is in the interval the zero root is included.
\end{itemize}

\begin{description}
\ttindex{REALROOTS}
\item[REALROOTS] finds the real roots of the polynomial
p.  Precision of computation is guaranteed to be sufficient to
separate all real roots in the specified region.  (cf. MULTIROOT for
treatment of multiple roots.)

\ttindex{ISOLATER}
\item[ISOLATER] produces a list of rational intervals, each
containing a single real root of the polynomial p, within the specified
region, but does not find the roots.

\ttindex{RLROOTNO}
\item[RLROOTNO] computes the number of real roots of p in
the specified region, but does not find the roots.
\end{description}

\subsection{Functions that return both real and complex roots}

\begin{description}
\ttindex{ROOTS}
\item[ROOTS p;] This is the main top level function of the roots package.
It will find all roots, real and complex, of the polynomial p to an
accuracy that is sufficient to separate them and which is a minimum of 6
decimal places.  The value returned by ROOTS is a
list of equations for all roots.  In addition, ROOTS stores separate lists
of real roots and complex roots in the global variables ROOTSREAL and
ROOTSCOMPLEX.\ttindex{ROOTSREAL}\ttindex{ROOTSCOMPLEX}

The output of ROOTS is normally sorted into a standard order:
a root with smaller real part precedes a root with larger real part; roots
with identical real parts are sorted so that larger imaginary part
precedes smaller imaginary part.

However, when a polynomial has been factored algebraically then the
root sorting is applied to each factor separately.  This makes the
final resulting order less obvious.

\ttindex{ROOTS\_AT\_PREC}
\item[ROOTS\_AT\_PREC p;] Same as ROOTS except that roots values are
returned to a minimum of the number of decimal places equal to the current
system precision.

\ttindex{ROOT\_VAL}
\item[ROOT\_VAL p;] Same as ROOTS\_AT\_PREC, except that instead of
returning a list of equations for the roots, a list of the root value is
returned.  This is the function that SOLVE calls.

\ttindex{NEARESTROOT}
\item[NEARESTROOT(p,s);] This top level function finds the root to
which the method converges given the initial starting origin s, which
can be complex.  If there are several roots in the vicinity of s and s
is not significantly closer to one root than it is to all others, the
convergence could arrive at a root that is not truly the nearest root.
This function should therefore be used only when the user is certain
that there is only one root in the immediate vicinity of the
starting point s.

\ttindex{FIRSTROOT}
\item[FIRSTROOT p;] ROOTS is called, but only a single root is computed.
\end{description}


\subsection{Other top level functions}

\begin{description}
\ttindex{GETROOT}\ttindex{ROOTS}\ttindex{REALROOTS}\ttindex{NEARESTROOTS}
\item[GETROOT(n,rr);] If rr has the form of the output of ROOTS, REALROOTS,
or NEARESTROOTS; GETROOT returns the rational, real, or complex value of
the root equation.  An error occurs if $n<1$ or $n>$ the number of roots in
rr.

\ttindex{MKPOLY}
\item[MKPOLY rr;] This function can be used to reconstruct a polynomial
whose root equation list is rr and whose denominator is 1.  Thus one can
verify that if $rr := ROOTS~p$, and $rr1 := ROOTS~MKPOLY~rr$, then
$rr1 = rr$. (This will be true if {\tt MULTIROOT} and {\tt RATROOT} are ON,
and {\tt ROUNDED} is off.)
However, $MKPOLY~rr - NUM~p = 0$ will be true if and only if all roots of p
have been computed exactly.

\end{description}

\section{Switches Used in Input}

The input of polynomials in algebraic mode is sensitive to the switches
{\tt COMPLEX}, {\tt ROUNDED}, and {\tt ADJPREC}.  The correct choice of
input method is important since incorrect choices will result in
undesirable truncation or rounding of the input coefficients.

Truncation or rounding may occur if {\tt ROUNDED} is on and
one of the following is true:

\begin{enumerate}
\item a coefficient is entered in floating point form or rational form.
\item {\tt COMPLEX} is on and a coefficient is imaginary or complex.
\end{enumerate}

Therefore, to avoid undesirable truncation or rounding, then:

\begin{enumerate}
\item {\tt ROUNDED} should be off and input should be
in integer or rational form; or
\item {\tt ROUNDED} can be on if it is acceptable to truncate or round
input to the current value of system precision; or both {\tt ROUNDED} and
{\tt ADJPREC} can be on, in which case system precision will be adjusted
to accommodate the largest coefficient which is input; or \item if the
input contains complex coefficients with very different magnitude for the
real and imaginary parts, then all three switches {\tt ROUNDED}, {\tt
ADJPREC} and {\tt COMPLEX} must be on.
\end{enumerate}

\begin{description}
\item[integer and complex modes] (off {\tt ROUNDED}) any real
polynomial can be input using integer coefficients of any size; integer or
rational coefficients can be used to input any real or complex polynomial,
independent of the setting of the switch {\tt COMPLEX}.  These are the most
versatile input modes, since any real or complex polynomial can be input
exactly.

\item[modes rounded and complex-rounded] (on {\tt ROUNDED}) polynomials can be
input using
integer coefficients of any size.  Floating point coefficients will be
truncated or rounded, to a size dependent upon the system.  If complex
is on, real coefficients can be input to any precision using integer
form, but coefficients of imaginary parts of complex coefficients will
be rounded or truncated.
\end{description}

\section{Root Package Switches}

\begin{description}
\ttindex{RATROOT}
\item[RATROOT] (Default OFF) If {\tt RATROOT} is on all root equations are
output in rational form.  Assuming that the mode is {\tt COMPLEX}
({\em i.e.\ }
{\tt ROUNDED} is off,) the root equations are
guaranteed to be able to be input into \REDUCE\ without truncation or
rounding errors. (Cf. the function MKPOLY described above.)

\ttindex{MULTIROOT}
\item[MULTIROOT] (Default ON) Whenever the polynomial has complex
coefficients or has real coefficients and has multiple roots, as
\ttindex{SQFRF} determined by the Sturm function, the function {\tt SQFRF}
is called automatically to factor the polynomial into square-free factors.
If {\tt MULTIROOT} is on, the multiplicity of the roots will be indicated
in the output of ROOTS or REALROOTS by printing the root output
repeatedly, according to its multiplicity.  If {\tt MULTIROOT} is off,
each root will be printed once, and all roots should be normally be
distinct. (Two identical roots should not appear.  If the initial
precision of the computation or the accuracy of the output was
insufficient to separate two closely-spaced roots, the program attempts to
increase accuracy and/or precision if it detects equal roots.  If,
however, the initial accuracy specified was too low, and it was not
possible to separate the roots, the program will abort.)

\end{description}