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

  • Full Text Views

    0

  • Cite this

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.

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

Authors

Keyword

FlyerIEICE has prepared a flyer regarding multilingual services. Please use the one in your native language.