NAG Library Routine Document
c02agf (poly_real)
1
Purpose
c02agf finds all the roots of a real polynomial equation, using a variant of Laguerre's method.
2
Specification
Fortran Interface
Integer, Intent (In)  ::  n  Integer, Intent (Inout)  ::  ifail  Real (Kind=nag_wp), Intent (In)  ::  a(n+1)  Real (Kind=nag_wp), Intent (Out)  ::  z(2,n), w(2*(n+1))  Logical, Intent (In)  ::  scal 

C Header Interface
#include <nagmk26.h>
void 
c02agf_ (const double a[], const Integer *n, const logical *scal, double z[], double w[], Integer *ifail) 

3
Description
c02agf attempts to find all the roots of the
$n$th degree real polynomial equation
The roots are located using a modified form of Laguerre's method, originally proposed by
Smith (1967).
The method of Laguerre (see
Wilkinson (1965)) can be described by the iterative scheme
where
$H\left({z}_{k}\right)=\left(n1\right)\left[\left(n1\right){\left({P}^{\prime}\left({z}_{k}\right)\right)}^{2}nP\left({z}_{k}\right){P}^{\prime \prime}\left({z}_{k}\right)\right]$ and
${z}_{0}$ is specified.
The sign in the denominator is chosen so that the modulus of the Laguerre step at ${z}_{k}$, viz. $\leftL\left({z}_{k}\right)\right$, is as small as possible. The method can be shown to be cubically convergent for isolated roots (real or complex) and linearly convergent for multiple roots.
The routine generates a sequence of iterates
${z}_{1},{z}_{2},{z}_{3},\dots \text{}$, such that
$\leftP\left({z}_{k+1}\right)\right<\leftP\left({z}_{k}\right)\right$ and ensures that
${z}_{k+1}+L\left({z}_{k+1}\right)$ ‘roughly’ lies inside a circular region of radius
$\leftF\right$ about
${z}_{k}$ known to contain a zero of
$P\left(z\right)$; that is,
$\leftL\left({z}_{k+1}\right)\right\le \leftF\right$, where
$F$ denotes the Fejér bound (see
Marden (1966)) at the point
${z}_{k}$. Following
Smith (1967),
$F$ is taken to be
$\mathrm{min}\phantom{\rule{0.125em}{0ex}}\left(B,1.445nR\right)$, where
$B$ is an upper bound for the magnitude of the smallest zero given by
${r}_{1}$ is the zero
$X$ of smaller magnitude of the quadratic equation
and the Cauchy lower bound
$R$ for the smallest zero is computed (using Newton's Method) as the positive root of the polynomial equation
Starting from the origin, successive iterates are generated according to the rule
${z}_{k+1}={z}_{k}+L\left({z}_{k}\right)$, for
$k=1,2,3,\dots \text{}$, and
$L\left({z}_{k}\right)$ is ‘adjusted’ so that
$\leftP\left({z}_{k+1}\right)\right<\leftP\left({z}_{k}\right)\right$ and
$\leftL\left({z}_{k+1}\right)\right\le \leftF\right$. The iterative procedure terminates if
$P\left({z}_{k+1}\right)$ is smaller in absolute value than the bound on the rounding error in
$P\left({z}_{k+1}\right)$ and the current iterate
${z}_{p}={z}_{k+1}$ is taken to be a zero of $P\left(z\right)$ (as is its conjugate
${\stackrel{}{z}}_{p}$ if ${z}_{p}$ is complex). The deflated polynomial
$\stackrel{~}{P}\left(z\right)=P\left(z\right)/\left(z{z}_{p}\right)$ of degree $n1$ if ${z}_{p}$ is real
($\stackrel{~}{P}\left(z\right)=P\left(z\right)/\left(\left(z{z}_{p}\right)\left(z{\stackrel{}{z}}_{p}\right)\right)$ of degree $n2$ if ${z}_{p}$ is complex) is then formed, and the above procedure is repeated on the deflated polynomial until $n<3$, whereupon the remaining roots are obtained via the ‘standard’ closed formulae for a linear ($n=1$) or quadratic ($n=2$) equation.
Note that
c02ajf,
c02akf and
c02alf can be used to obtain the roots of a quadratic, cubic (
$n=3$) and quartic (
$n=4$) polynomial, respectively.
4
References
Marden M (1966) Geometry of polynomials Mathematical Surveys 3 American Mathematical Society, Providence, RI
Smith B T (1967) ZERPOL: a zero finding algorithm for polynomials using Laguerre's method Technical Report Department of Computer Science, University of Toronto, Canada
Thompson K W (1991) Error analysis for polynomial solvers Fortran Journal (Volume 3) 3 10–13
Wilkinson J H (1965) The Algebraic Eigenvalue Problem Oxford University Press, Oxford
5
Arguments
 1: $\mathbf{a}\left({\mathbf{n}}+1\right)$ – Real (Kind=nag_wp) arrayInput

On entry: if
a is declared with bounds
$\left(0:{\mathbf{n}}\right)$,
${\mathbf{a}}\left(\mathit{i}\right)$ must contain
${a}_{\mathit{i}}$ (i.e., the coefficient of
${z}^{n\mathit{i}}$), for
$\mathit{i}=0,1,\dots ,n$.
Constraint:
${\mathbf{a}}\left(0\right)\ne 0.0$.
 2: $\mathbf{n}$ – IntegerInput

On entry: $n$, the degree of the polynomial.
Constraint:
${\mathbf{n}}\ge 1$.
 3: $\mathbf{scal}$ – LogicalInput

On entry: indicates whether or not the polynomial is to be scaled. See
Section 9 for advice on when it may be preferable to set
${\mathbf{scal}}=\mathrm{.FALSE.}$ and for a description of the scaling strategy.
Suggested value:
${\mathbf{scal}}=\mathrm{.TRUE.}$.
 4: $\mathbf{z}\left(2,{\mathbf{n}}\right)$ – Real (Kind=nag_wp) arrayOutput

On exit: the real and imaginary parts of the roots are stored in
${\mathbf{z}}\left(1,\mathit{i}\right)$ and
${\mathbf{z}}\left(2,\mathit{i}\right)$ respectively, for
$\mathit{i}=1,2,\dots ,n$. Complex conjugate pairs of roots are stored in consecutive pairs of elements of
z; that is,
${\mathbf{z}}\left(1,\mathit{i}+1\right)={\mathbf{z}}\left(1,i\right)$ and
${\mathbf{z}}\left(2,i+1\right)={\mathbf{z}}\left(2,i\right)$.
 5: $\mathbf{w}\left(2\times \left({\mathbf{n}}+1\right)\right)$ – Real (Kind=nag_wp) arrayWorkspace

 6: $\mathbf{ifail}$ – IntegerInput/Output

On entry:
ifail must be set to
$0$,
$1\text{or}1$. If you are unfamiliar with this argument you should refer to
Section 3.4 in How to Use the NAG Library and its Documentation for details.
For environments where it might be inappropriate to halt program execution when an error is detected, the value
$1\text{or}1$ is recommended. If the output of error messages is undesirable, then the value
$1$ is recommended. Otherwise, if you are not familiar with this argument, the recommended value is
$0$.
When the value $\mathbf{1}\text{or}\mathbf{1}$ is used it is essential to test the value of ifail on exit.
On exit:
${\mathbf{ifail}}={\mathbf{0}}$ unless the routine detects an error or a warning has been flagged (see
Section 6).
6
Error Indicators and Warnings
If on entry
${\mathbf{ifail}}=0$ or
$1$, explanatory error messages are output on the current error message unit (as defined by
x04aaf).
Errors or warnings detected by the routine:
 ${\mathbf{ifail}}=1$

On entry, ${\mathbf{a}}\left(0\right)=0.0$.
Constraint: ${\mathbf{a}}\left(0\right)\ne 0.0$.
On entry, ${\mathbf{n}}=\u2329\mathit{\text{value}}\u232a$.
Constraint: ${\mathbf{n}}\ge 1$.
 ${\mathbf{ifail}}=2$

The iterative procedure has failed to converge. This error is very unlikely to occur. If it does, please contact
NAG immediately, as some basic assumption for the arithmetic has been violated.
 ${\mathbf{ifail}}=3$

c02agf cannot evaluate
$P\left(z\right)$ near some of its zeros without overflow. If this message occurs please contact
NAG.
c02agf cannot evaluate
$P\left(z\right)$ near some of its zeros without underflow. If this message occurs please contact
NAG.
 ${\mathbf{ifail}}=99$
An unexpected error has been triggered by this routine. Please
contact
NAG.
See
Section 3.9 in How to Use the NAG Library and its Documentation for further information.
 ${\mathbf{ifail}}=399$
Your licence key may have expired or may not have been installed correctly.
See
Section 3.8 in How to Use the NAG Library and its Documentation for further information.
 ${\mathbf{ifail}}=999$
Dynamic memory allocation failed.
See
Section 3.7 in How to Use the NAG Library and its Documentation for further information.
7
Accuracy
All roots are evaluated as accurately as possible, but because of the inherent nature of the problem complete accuracy cannot be guaranteed.
See also
Section 10.
8
Parallelism and Performance
c02agf is not threaded in any implementation.
If
${\mathbf{scal}}=\mathrm{.TRUE.}$, then a scaling factor for the coefficients is chosen as a power of the base
$b$ of the machine so that the largest coefficient in magnitude approaches
$\mathit{thresh}={b}^{{e}_{\mathrm{max}}p}$. You should note that no scaling is performed if the largest coefficient in magnitude exceeds
$\mathit{thresh}$, even if
${\mathbf{scal}}=\mathrm{.TRUE.}$. (
$b$,
${e}_{\mathrm{max}}$ and
$p$ are defined in
Chapter X02.)
However, with
${\mathbf{scal}}=\mathrm{.TRUE.}$, overflow may be encountered when the input coefficients
${a}_{0},{a}_{1},{a}_{2},\dots ,{a}_{n}$ vary widely in magnitude, particularly on those machines for which
${b}^{\left(4p\right)}$ overflows. In such cases,
scal should be set to .FALSE. and the coefficients scaled so that the largest coefficient in magnitude does not exceed
${b}^{\left({e}_{\mathrm{max}}2p\right)}$.
Even so, the scaling strategy used by c02agf is sometimes insufficient to avoid overflow and/or underflow conditions. In such cases, you are recommended to scale the independent variable $\left(z\right)$ so that the disparity between the largest and smallest coefficient in magnitude is reduced. That is, use the routine to locate the zeros of the polynomial $dP\left(cz\right)$ for some suitable values of $c$ and $d$. For example, if the original polynomial was $P\left(z\right)={2}^{100}+{2}^{100}{z}^{20}$, then choosing $c={2}^{10}$ and $d={2}^{100}$, for instance, would yield the scaled polynomial $1+{z}^{20}$, which is wellbehaved relative to overflow and underflow and has zeros which are ${2}^{10}$ times those of $P\left(z\right)$.
If the routine fails with
${\mathbf{ifail}}={\mathbf{2}}$ or
${\mathbf{3}}$, then the real and imaginary parts of any roots obtained before the failure occurred are stored in
z in the reverse order in which they were found.
Let
${n}_{R}$ denote the number of roots found before the failure occurred. Then
${\mathbf{z}}\left(1,n\right)$ and
${\mathbf{z}}\left(2,n\right)$ contain the real and imaginary parts of the first root found,
${\mathbf{z}}\left(1,n1\right)$ and
${\mathbf{z}}\left(2,n1\right)$ contain the real and imaginary parts of the second root found,
$\dots ,{\mathbf{z}}\left(1,n{n}_{R}+1\right)$ and
${\mathbf{z}}\left(2,n{n}_{R}+1\right)$ contain the real and imaginary parts of the
${n}_{R}$th root found. After the failure has occurred, the remaining
$2\times \left(n{n}_{R}\right)$ elements of
z contain a large negative number (equal to
$1/\left({\mathbf{x02amf}}\left(\right)\times \sqrt{2}\right)$).
10
Example
For this routine two examples are presented. There is a single example program for c02agf, with a main program and the code to solve the two example problems given in the subroutines EX1 and EX2.
Example 1 (EX1)
This example finds the roots of the fifth degree polynomial
Example 2 (EX2)
This example solves the same problem as subroutine EX1, but in addition attempts to estimate the accuracy of the computed roots using a perturbation analysis. Further details can be found in
Thompson (1991).
10.1
Program Text
Program Text (c02agfe.f90)
10.2
Program Data
Program Data (c02agfe.d)
10.3
Program Results
Program Results (c02agfe.r)