Certified predictor-corrector tracking for Newton homotopies

摘要

We develop certified tracking procedures for Newton homotopies, which are homotopies for which only the constant terms are changed. For these homotopies, our certified procedures include using a constant predictor with Newton corrections, an Euler predictor with no corrections, and an Euler predictor with Newton corrections. In each case, the predictor is guaranteed to produce a point in the quadratic convergence basin of Newton's method. We analyze the complexity of a tracking procedure using a constant predictor with Newton corrections, with the number of steps bounded above by a constant multiple of the length of the path in the gamma-metric. Examples are included to compare the behavior of these certified tracking methods. (C) 2015 Elsevier Ltd. All rights reserved.