Solving nonlinear equations by adaptive homotopy continuation

摘要

Standard homotopy continuation methods for solving systems of nonlinear equations require the continuation parameter to move from 0 to 1 along the real line. Difficulties can occur, however, if a point of singularity is encountered during the course of the integration. To ameliorate these difficulties, this paper proposes extending the continuation parameter to complex values and adaptively computing a continuation path in the complex plane that avoids points giving rise to singularities. Specifically, it is proposed that the continuation parameter move from 0 + 0i to 1 + 0i along a spider-web grid centered at 1 + 0i in the complex plane. The actual path through the grid is determined step by step in accordance with two objectives: short path length, and avoidance of singular points. A two-phase homotopy continuation is used to study the implementation of this idea. Numerical examples are presented which indicate the effectiveness of the approach.