Peter Kravanja
On Computing Zeros of Analytic Functions and Related
Problems in Structured Numerical Linear Algebra
(9 March 1999)
Promotors: A. Haegemans and M. Van Barel
This thesis is a blend of computational complex analysis and
numerical linear algebra.
We study the problem of computing all the zeros of an analytic function
that lie inside a Jordan curve. The algorithm that we present computes
not only approximations for the zeros but also their respective
multiplicities. It does not require initial approximations for the zeros
and we have found that it gives accurate results. A Fortran 90
implementation is available (the package ZEAL). Our approach is based
on numerical integration and the theory of formal orthogonal polynomials.
We show how it can be used to locate clusters of zeros of analytic
functions. In this context we also present an alternative approach,
based on rational interpolation at roots of unity. Next we consider the
related problem of computing all the zeros and poles of a meromorphic
function that lie inside a Jordan curve and that of computing all the
zeros of an analytic mapping (in other words, all the roots of a system
of analytic equations) that lie in a polydisk.
We also consider analytic functions whose zeros are known to be simple,
in particular Bessel functions (the package ZEBEC) and certain combinations
of Bessel functions.
Next we propose a modification of Newton's method for computing multiple
zeros of analytic mappings. Under mild assumptions our iteration
converges quadratically. It involves certain constants whose product
is a lower bound for the multiplicity of the zero. As these constants
are usually not known in advance, we devise an iteration in which not
only an approximation for the zero is refined, but also approximations
for these constants.
In the last part of this thesis we develop stabilized fast and superfast
algorithms for rational interpolation at roots of unity.
These algorithms lead to fast and superfast solvers for (indefinite)
linear systems of equations that have Hankel or Toeplitz structure.