Computational Complexity of Calculating Solutions for a Certain Class of Uniquely Solvable Nonlinear Equation by Homotopy Method

Mitsunori MAKINO  Shin'ichi OISHI  Masahide KASHIWAGI  Kazuo HORIUCHI  

Publication
IEICE TRANSACTIONS (1976-1990)   Vol.E73   No.12   pp.1940-1947
Publication Date: 1990/12/25
Online ISSN: 
DOI: 
Print ISSN: 0000-0000
Type of Manuscript: Special Section PAPER (Special Issue on the 3rd Karuizawa Workshop on Circuits and Systems)
Category: Nonlinear Circuits and Simulation
Keyword: 


Full Text: PDF(520.4KB)
>>Buy this Article

Summary: 
A priori estimation is presented for a computational complexity of the homotopy method applying to a certain class of uniquely solvable nonlinear equations. In the first place, the reason is explained why a computational complexity of the homotopy method can not be a priori estimated in general. In this paper, the homotopy algorithm is considered in which a numerical path following algorithm is executed based on the simplified Newton method. Then by introducing Urabe's theorem, which gives a sufficient condition guaranteeing the convergence of the simplified Newton method, it is shown that a computational complexity of the algorithm can be a priori estimated, when it is applied to a certain class of uniquely solvable nonlinear equation. In this paper, two types of path following algorithms are considered, one with a numerical error estimation in the domain of a nonlinear operator and another with one in the range of the operator.