A Sufficient Condition of A Priori Estimation for Computational Complexity of the Homotopy Method
Summary :
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.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E76-A No.5 pp.786-794
- Publication Date
- 1993/05/25
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- Special Section PAPER (Special Section on Neural Nets,Chaos and Numerics)
- Category
- Numerical Homotopy Method and Self-Validating Numerics
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Mitsunori MAKINO, Masahide KASHIWAGI, Shin'ichi OISHI, Kazuo HORIUCHI, "A Sufficient Condition of A Priori Estimation for Computational Complexity of the Homotopy Method" in IEICE TRANSACTIONS on Fundamentals,
vol. E76-A, no. 5, pp. 786-794, May 1993, doi: .
Abstract: 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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e76-a_5_786/_p
Copy
@ARTICLE{e76-a_5_786,
author={Mitsunori MAKINO, Masahide KASHIWAGI, Shin'ichi OISHI, Kazuo HORIUCHI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={A Sufficient Condition of A Priori Estimation for Computational Complexity of the Homotopy Method},
year={1993},
volume={E76-A},
number={5},
pages={786-794},
abstract={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.},
keywords={},
doi={},
ISSN={},
month={May},}
Copy
TY - JOUR
TI - A Sufficient Condition of A Priori Estimation for Computational Complexity of the Homotopy Method
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 786
EP - 794
AU - Mitsunori MAKINO
AU - Masahide KASHIWAGI
AU - Shin'ichi OISHI
AU - Kazuo HORIUCHI
PY - 1993
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E76-A
IS - 5
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - May 1993
AB - 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.
ER -
English
