Complexity of Bezout’s theorem. I: Geometric aspects. (English) Zbl 0821.65035
The paper deals with the complexity of homotopy methods for solving systems of polynomial equations. For general homotopy equations of the form \(f_ t (\zeta) = 0\), \(t \in [0,1]\), whose zeros are denoted by \(\zeta_ t\), the number \(l\) of steps (with \(0 = t_ 0 < t_ 1 < \cdots < t_ l = 1)\), that are necessary such that an approximate of the zero in the previous step is an appropriate starting point for Newton’s method in the next step, is estimated in terms of the distance of the curve \((f_ t, \zeta_ t)\) to the variety of ill-posed problems, the length of the curve \((f_ t)\), the maximum degree of the polynomials \(f_ t\) and a numerically known constant. The proof is based on a Kantorovich- type local convergence theorem for analytic functions.
Reviewer: W.Zulehner (Linz)
MSC:
65H10 | Numerical computation of solutions to systems of equations |
65H20 | Global methods, including homotopy approaches to the numerical solution of nonlinear equations |
12Y05 | Computational aspects of field theory and polynomials (MSC2010) |
26C10 | Real polynomials: location of zeros |
30C15 | Zeros of polynomials, rational functions, and other analytic functions of one complex variable (e.g., zeros of functions with bounded Dirichlet integral) |