NAG Library Function Document
nag_zeros_real_poly (c02agc)
1 Purpose
nag_zeros_real_poly (c02agc) finds all the roots of a real polynomial equation, using a variant of Laguerre's method.
2 Specification
#include <nag.h> |
#include <nagc02.h> |
void |
nag_zeros_real_poly (Integer n,
const double a[],
Nag_Boolean scale,
Complex z[],
NagError *fail) |
|
3 Description
nag_zeros_real_poly (c02agc) attempts to find all the roots of the
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
, and
is specified.
The sign in the denominator is chosen so that the modulus of the Laguerre step at , viz. , 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 function generates a sequence of iterates
such that
and ensures that
‘roughly’ lies inside a circular region of radius
about
known to contain a zero of
; that is,
, where
denotes the Fejér bound (see
Marden (1966)) at the point
. Following
Smith (1967),
is taken to be
, where
is an upper bound for the magnitude of the smallest zero given by
is the zero
of smaller magnitude of the quadratic equation
and the Cauchy lower bound
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
, for
, and
is ‘adjusted’ so that
and
. The iterative procedure terminates if
is smaller in absolute value than the bound on the rounding error in
and the current iterate
is taken to be a zero of
(as is its conjugate
if
is complex). The deflated polynomial
of degree
if
is real (
of degree
if
is complex) is then formed, and the above procedure is repeated on the deflated polynomial until
, whereupon the remaining roots are obtained via the ‘standard’ closed formulae for a linear (
) or quadratic (
) equation.
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
Wilkinson J H (1965) The Algebraic Eigenvalue Problem Oxford University Press, Oxford
5 Arguments
- 1:
n – IntegerInput
On entry: , the degree of the polynomial.
Constraint:
.
- 2:
a[] – const doubleInput
-
On entry: must contain (i.e., the coefficient of ), for .
Constraint:
.
- 3:
scale – Nag_BooleanInput
-
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
and for a description of the scaling strategy.
Suggested value:
.
- 4:
z[n] – ComplexOutput
-
On exit: the real and imaginary parts of the roots are stored in
and
respectively, for
. Complex conjugate pairs of roots are stored in consecutive pairs of
z; that is,
and
- 5:
fail – NagError *Input/Output
-
The NAG error argument (see
Section 3.6 in the Essential Introduction).
6 Error Indicators and Warnings
- NE_ALLOC_FAIL
-
Dynamic memory allocation failed.
- NE_BAD_PARAM
-
On entry, argument had an illegal value.
- NE_INT_ARG_LT
-
On entry, .
Constraint: .
- NE_INTERNAL_ERROR
-
An internal error has occurred in this function. Check the function call
and any array sizes. If the call is correct then please contact
NAG for
assistance.
- NE_POLY_NOT_CONV
-
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.
- NE_POLY_OVFLOW
-
The function cannot evaluate
near some of its zeros without overflow. Please contact
NAG immediately.
- NE_POLY_UNFLOW
-
The function cannot evaluate
near some of its zeros without underflow. Please contact
NAG immediately.
- NE_REAL_ARG_EQ
-
On entry, .
Constraint: .
7 Accuracy
All roots are evaluated as accurately as possible, but because of the inherent nature of the problem complete accuracy cannot be guaranteed.
8 Parallelism and Performance
Not applicable.
If
, then a scaling factor for the coefficients is chosen as a power of the base
of the machine so that the largest coefficient in magnitude approaches
. You should note that no scaling is performed if the largest coefficient in magnitude exceeds
, even if
. (
,
and
are defined in
Chapter x02.)
However, with
, overflow may be encountered when the input coefficients
vary widely in magnitude, particularly on those machines for which
overflows. In such cases,
scale should be set to Nag_FALSE and the coefficients scaled so that the largest coefficient in magnitude does not exceed
.
Even so, the scaling strategy used in nag_zeros_real_poly (c02agc) is sometimes insufficient to avoid overflow and/or underflow conditions. In such cases, you are recommended to scale the independent variable so that the disparity between the largest and smallest coefficient in magnitude is reduced. That is, use the function to locate the zeros of the polynomial for some suitable values of and . For example, if the original polynomial was , then choosing and , for instance, would yield the scaled polynomial , which is well-behaved relative to overflow and underflow and has zeros which are times those of .
If the function fails with
NE_POLY_NOT_CONV,
NE_POLY_UNFLOW or
NE_POLY_OVFLOW, 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. More precisely,
and
contain the real and imaginary parts of the 1st root found,
and
contain the real and imaginary parts of the 2nd root found, and so on. The real and imaginary parts of any roots not found will be set to a large negative number, specifically
.
10 Example
To find the roots of the 5th degree polynomial .
10.1 Program Text
Program Text (c02agce.c)
10.2 Program Data
Program Data (c02agce.d)
10.3 Program Results
Program Results (c02agce.r)