Topological complexity of zero-finding
A paper with this title appeared in the J. Complexity 12 (1996), 380-400.
Authors are Erich Novak and Henryk Wozniakowski.
Abstract
The topological complexity of zero-finding is studied using a
BSS machine over the reals with an information node.
The topological complexity depends on the class of functions,
the class of arithmetic operations, and on the error criterion.
For the root error criterion the following results are established.
If only Hoelder operations are permitted as arithmetic operations then
the topological complexity is roughly -\log_2 eps and bisection is
optimal. This holds even for the small class
of linear functions. On the other hand, for the class of all increasing
functions, if we allow the sign function or division together with
log and exp, then the topological complexity drops to zero.
For the residual error criterion, results can be totally different than
for the root error criterion. For example, the topological complexity can be
zero for the residual error criterion, and roughly -\log_2 eps for
the root error criterion.
Introduction
Our interest in the topological complexity is motivated by the recent
work of Smale (1987) and Vassiliev (1992). In particular, they consider
zero-finding for univariate polynomials of degree d with
complex coefficients whose absolute value is at most one.
They prove that the total number of comparison nodes
in the computational
graph is independent of an error parameter eps and is roughly d
for small eps.
In this paper we deal with zero-finding for univariate functions
defined on the interval [0,1], and by the topological
complexity we mean the depth of the computational graph.
Some references
P. Hertling (1996): Unstetigkeitsgrade von Funktionen in der
effektiven Analysis.
Fernuniversitaet Hagen, Informatik-Berichte
208, November 1996.
Ph.D. thesis, 157 pages.
P. Hertling (1996):
Topological complexity with continuous operations.
J. Complexity 12 (1996), 315-338.
E. Novak, K. Ritter, H. Wozniakowski (1995):
Average Case Optimality of a Hybrid Secant-Bisection Method.
Math. Computation 64, 1517-1539, 1995.
S. Smale (1987):
On the topology of algorithms. J. Complexity 3, 81-89.
V. A. Vassiliev (1992):
Complements of discriminants of smooth maps:
topology and applications.
Transl. of Math. Monographs 98, 1992, revised 1994,
Amer. Math. Soc., Providence, R.I.
V. A. Vassiliev (1996):
Topological complexity of root-finding algorithms.
In: The Mathematics of Numerical Analysis,
J. Renegar, M. Shub, S. Smale (eds.),
Lectures in Applied Mathematics 32, AMS, 1996,
831-856.