This chapter is concerned with computing the zeros of a polynomial with real or complex coefficients.
Let
be a polynomial of degree
with complex coefficients
:
A complex number
is called a
zero of
(or equivalently a
root of the
equation
), if
If
is a zero, then
can be divided by a factor
:
where
is a polynomial of degree
. By the Fundamental Theorem of Algebra, a polynomial
always has a zero, and so the process of dividing out factors
can be continued until we have a complete
factorization of
:
Here the complex numbers
are the zeros of
; they may not all be distinct, so it is sometimes more convenient to write
with distinct zeros
and multiplicities
. If
,
is called a
simple or
isolated zero; if
,
is called a
multiple or
repeated zero; a multiple zero is also a zero of the derivative of
.
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
. A pair of complex conjugate zeros can be divided out together – this corresponds to dividing
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
is mathematically an exact zero of
, because of the fundamental limitations of computer arithmetic the
computed value of
will not necessarily be exactly
. In practice there is usually a small region of values of
about the exact zero at which the computed value of
becomes swamped by rounding errors. Moreover, in many algorithms this inaccuracy in the computed value of
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
will not be completely accurate, especially if
is not an exact zero of
; so the zeros of the computed
will deviate from the zeros of
.
None.
None.
Peters G and Wilkinson J H (1971) Practical problems arising in the solution of polynomial equations J. Inst. Maths. Applics. 8 16–35