Adaptive Step Size Selection for Homotopy Methods to Solve Polynomial Equations

JEAN-PIERRE DEDIEU,GREGORIO MLAJOVICH, MICHAEL SHUB

Institute of Mathematics and its ApplicationsJournal of Numerical Analysis

Oxford University Press

Lugar: Oxford; Año: 2012 vol. 32 p. 1 - 25

0272-4979

Given a $C^1$ path of systems of homogeneous polynomial equations $f_t$, $t \in [a,b]$ and an approximation $x_a$ to a zero $\zeta_a$ of the initial system $f_a$, we show how to adaptively choose the step size for a Newton based homotopy method so that we approximate the lifted path $(f_t,\zeta_t)$ in the space of $(problems, solutions)$ pairs. The total number of Newton iterations is bounded in terms of the length of the lifted path in the condition metric.