A PL homotopy for finding all the roots of a polynomial |
| |
Authors: | Masakazu Kojima Hisakazu Nishino Naohiko Arima |
| |
Institution: | (1) Tokyo Institute of Technology, Tokyo, Japan;(2) Keio University, Yokohama, Japan |
| |
Abstract: | This paper presents a constructive method which gives, for any polynomialF(Z) of the degreen, approximate values of all the roots ofF(Z).. The point of the method is on the use of a piecewise linear function
(Z, t) which approximates a homotopyH(Z, t) betweenF(Z) and a polynomialG(Z) of the degreen withn known simple roots. It is shown that the set of solutions to
(Z, t) = 0 includesn distinct paths,m of which converges to a root ofF(Z) if and only if the root has the multiplicitym. Starting from givenn roots ofG(Z), a complementary pivot algorithm generates thosen paths.This work was supported by grants from Management Science Development Foundation and Takeda Science Foundation. |
| |
Keywords: | Roots of Polynomials Fixed Point Computing Methods Complementary Pivoting Methods Piecewise Linear Homotopy |
本文献已被 SpringerLink 等数据库收录! |
|