hide long namesshow long names
hide short namesshow short names
Integer type:  int32  int64  nag_int  show int32  show int32  show int64  show int64  show nag_int  show nag_int

PDF version (NAG web site, 64-bit version, 64-bit version)
Chapter Contents
Chapter Introduction
NAG Toolbox

NAG Toolbox Chapter Introduction

C02 — Zeros of Polynomials

Scope of the Chapter

This chapter is concerned with computing the zeros of a polynomial with real or complex coefficients.

Background to the Problems

Let f(z)f(z) be a polynomial of degree nn with complex coefficients aiai:
f(z)a0zn + a1zn1 + a2zn2 + + an1z + an,  a00.
f(z)a0zn+a1zn-1+a2zn-2++an-1z+an,  a00.
A complex number z1z1 is called a zero of f(z)f(z) (or equivalently a root of the equation f(z) = 0f(z)=0), if
f(z1) = 0.
f(z1)=0.
If z1z1 is a zero, then f(z)f(z) can be divided by a factor (zz1)(z-z1):
f(z) = (zz1)f1(z)
f(z)=(z-z1)f1(z)
(1)
where f1(z)f1(z) is a polynomial of degree n1n-1. By the Fundamental Theorem of Algebra, a polynomial f(z)f(z) always has a zero, and so the process of dividing out factors (zzi)(z-zi) can be continued until we have a complete factorization of f(z)f(z):
f(z)a0(zz1)(zz2)(zzn).
f(z)a0(z-z1)(z-z2)(z-zn).
Here the complex numbers z1,z2,,znz1,z2,,zn are the zeros of f(z)f(z); they may not all be distinct, so it is sometimes more convenient to write
f(z)a0(zz1)m1(zz2)m2(zzk)mk,  kn,
f(z)a0(z-z1)m1(z-z2)m2(z-zk)mk,  kn,
with distinct zeros z1,z2,,zkz1,z2,,zk and multiplicities mi1mi1. If mi = 1mi=1, zizi is called a simple or isolated zero; if mi > 1mi>1, zizi is called a multiple or repeated zero; a multiple zero is also a zero of the derivative of f(z)f(z).
If the coefficients of f(z)f(z) are all real, then the zeros of f(z)f(z) are either real or else occur as pairs of conjugate complex numbers x + iyx+iy and xiyx-iy. A pair of complex conjugate zeros are the zeros of a quadratic factor of f(z)f(z), (z2 + rz + s)(z2+rz+s), with real coefficients rr and ss.
Mathematicians are accustomed to thinking of polynomials as pleasantly simple functions to work with. However, the problem of numerically computing the zeros of an arbitrary polynomial is far from simple. A great variety of algorithms have been proposed, of which a number have been widely used in practice; for a fairly comprehensive survey, see Householder (1970). All general algorithms are iterative. Most converge to one zero at a time; the corresponding factor can then be divided out as in equation (1) above – this process is called deflation or, loosely, dividing out the zero – and the algorithm can be applied again to the polynomial f1(z)f1(z). A pair of complex conjugate zeros can be divided out together – this corresponds to dividing f(z)f(z) by a quadratic factor.
Whatever the theoretical basis of the algorithm, a number of practical problems arise; for a thorough discussion of some of them see Peters and Wilkinson (1971) and Chapter 2 of Wilkinson (1963). The most elementary point is that, even if z1z1 is mathematically an exact zero of f(z)f(z), because of the fundamental limitations of computer arithmetic the computed value of f(z1)f(z1) will not necessarily be exactly 0.00.0. In practice there is usually a small region of values of zz about the exact zero at which the computed value of f(z)f(z) becomes swamped by rounding errors. Moreover, in many algorithms this inaccuracy in the computed value of f(z)f(z) results in a similar inaccuracy in the computed step from one iterate to the next. This limits the precision with which any zero can be computed. Deflation is another potential cause of trouble, since, in the notation of equation (1), the computed coefficients of f1(z)f1(z) will not be completely accurate, especially if z1z1 is not an exact zero of f(z)f(z); so the zeros of the computed f1(z)f1(z) will deviate from the zeros of f(z)f(z).
A zero is called ill-conditioned if it is sensitive to small changes in the coefficients of the polynomial. An ill-conditioned zero is likewise sensitive to the computational inaccuracies just mentioned. Conversely a zero is called well-conditioned if it is comparatively insensitive to such perturbations. Roughly speaking a zero which is well separated from other zeros is well-conditioned, while zeros which are close together are ill-conditioned, but in talking about ‘closeness’ the decisive factor is not the absolute distance between neighbouring zeros but their ratio: if the ratio is close to one the zeros are ill-conditioned. In particular, multiple zeros are ill-conditioned. A multiple zero is usually split into a cluster of zeros by perturbations in the polynomial or computational inaccuracies.

Recommendations on Choice and Use of Available Functions

All zeros of cubic, 
    complex coefficients nag_zeros_cubic_complex (c02am)
    real coefficients nag_zeros_cubic_real (c02ak)
All zeros of polynomial, 
    complex coefficients, 
        modified Laguerre's method nag_zeros_poly_complex (c02af)
    real coefficients, 
        modified Laguerre's method nag_zeros_poly_real (c02ag)
All zeros of quadratic, 
    complex coefficients nag_zeros_quadratic_complex (c02ah)
    real coefficients nag_zeros_quadratic_real (c02aj)
All zeros of quartic, 
    complex coefficients nag_zeros_quartic_complex (c02an)
    real coefficients nag_zeros_quartic_real (c02al)

References

Householder A S (1970) The Numerical Treatment of a Single Nonlinear Equation McGraw–Hill
Peters G and Wilkinson J H (1971) Practical problems arising in the solution of polynomial equations J. Inst. Maths. Applics. 8 16–35
Thompson K W (1991) Error analysis for polynomial solvers Fortran Journal (Volume 3) 3 10–13
Wilkinson J H (1963) Rounding Errors in Algebraic Processes HMSO

PDF version (NAG web site, 64-bit version, 64-bit version)
Chapter Contents
Chapter Introduction
NAG Toolbox

© The Numerical Algorithms Group Ltd, Oxford, UK. 2009–2013