Iterative methods for simultaneous inclusion of polynomial zeros (Q1801245)

This book collects, reviews, unifies and augments many interesting developments in the solution of polynomial equations. Galois' famous theorem concerning polynomial zeros states that a general direct method in terms of explicit formulas exist only for polynomials of degree less than five. Because of that, for finding zeros of higher degree polynomials one has to apply numerical methods. These methods, which generally take the form of an iterative process, give rise to the questions: How close is the current iterate to the solution, how fast does the iteration converge, can we trust the computed numbers? Consider a polynomial \(p(z)=a_ 0+a_ 1z...a_ nz^ n\) with \(a_ n\neq 0\) having k zeros \(\xi_ 1,...,\xi_ k\) with multiplicities \(\mu_ 1,...,\mu_ k\). Let us pose the task: For given \(a_ 0,...,a_ n\) and given \(\epsilon >0\) compute the number k, compute complex numbers \(z_ 1,...,z_ k\) such that \(| z_ i-\xi_ i| \leq \epsilon\) for \(i=1,...,k\), and compute \(\mu_ 1,...,\mu_ k\). There seems to exist no software package that does the job, although (1) the mathematics concerning polynomials is well understood, (2) the numerical analysis literature abounds with polynomial zero finders, (3) nowadays PC's and mainframes facilitate tremendous power, and (4) the problem is of far reaching relevance for practical purposes. The book under consideration presents quite a lot of iterative methods aiming at the task stated. The condition \(| z_ i-\xi_ i| \leq \epsilon\) leads to the use of disks. The typical step in the total step methods is: From a collection of k disks \(Z_ 1,...,Z_ k\) with \(\xi_ i\in Z_ i\) a new collection of k disks \(Z^*_ 1,...,Z^*_ k\) is constructed, \[ Z^*_ i:=F_ i(Z_ 1,...,Z_ k) \] for \(i=1,...,k,\) such that \(\xi_ i\in Z^*_ i.\) The corresponding single step methods have the form \[ Z^*_ i:=F_ i(Z^*_ i,...,Z^*_{i-1},Z_ i,...,Z_ k) \] for \(i=1,...,k.\) Convergence conditions and the order of convergence are investigated intensively. Most of the methods are illustrated by examples. Further topics are: use of rectangular intervals, clusters of zeros, methods combining point iteration and disk iteration, test for existence of a zero in a given region, numerical stability, computational efficiency. In the final chapter, the author reports on extensive numerical tests, comparing various methods on four types of computers. A significant part of the book stems from the author's own research.