For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
A Sufficient Condition of A Priori Estimation for Computational Complexity of the Homotopy Method
Mitsunori MAKINO Masahide KASHIWAGI Shin'ichi OISHI Kazuo HORIUCHI
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 1993/05/25
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Neural Nets,Chaos and Numerics)
Category: Numerical Homotopy Method and Self-Validating Numerics
numerical methods, nonliner system analysis, homotopy method, computational complexity, monotone operator,
Full Text: PDF(625.9KB)>>
A priori estimation is presented for a computational complexity of the homotopy method applying to a certain class of strongly monotone nonlinear equations. In the present papers, a condition is presented for a certain class of uniquely solvable equations, under which an upper bound of a computational complexity of the Newton type homotopy method can be a priori estimated. In this paper, a condition is considered in a case of linear homotopy equations including the Newton type homotopy equations. In the first place, the homotopy algorithm based on the simplified Newton method is introduced. Then by using Urabe type theorem, which gives a sufficient condition guaranteeing the convergence of the simplified Newton method, a condition is presented under which an upper bound of a computational complexity of the algorithm can be a priori estimated, when it is applied to a certain class of strongly monotone nonlinear equations. The presented condition is demonstrated by numerical experiments.