Options
Globally convergent, iterative path-following for algebraic equations
Publikationstyp
Journal Article
Date Issued
2010-12-01
Sprache
English
Author(s)
Institut
TORE-URI
Journal
Volume
4
Issue
4
Start Page
507
End Page
537
Citation
Mathematics in Computer Science 4 (4): 507-537 (2010-12-01)
Publisher DOI
Scopus ID
Homotopy methods are of great importance for the solution of systems of equations. It is a major problemto ensure well-defined iterations along the homotopy path. Many investigations have considered the complexityof path-following methods depending on the unknown distance of some given path to the variety of ill-posed problems. It is shown here that there exists a construction method for safe paths for a single algebraic equation. A safepath may be effectively determined with bounded effort. Special perturbation estimates for the zeros together withconvergence conditions for Newton's method in simultaneous mode allow our method to proceed on the safe path. This yields the first globally convergent, never-failing, uniformly iterative path-following algorithm. The maximumnumber of homotopy steps in our algorithm reaches a theoretical bound forecast by Shub and Smale i. e., the numberof steps is at most quadratic in the condition number. A constructive proof of the fundamental theorem of algebrameeting demands by Gauß, Kronecker and Weierstraß is a consequence of our algorithm.
DDC Class
004: Informatik