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\(\bar H\) (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\(\bar H\) (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 is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
B.C. Eaves, “Homotopies for computation of fixed points”,Mathematical Programming 3 (1972) 1–22.
B.C. Eaves, “A short course in solving equations with PL homotopies”, Department of Operations Research, Stanford University, Stanford, CA (1975).
B.C. Eaves and R. Saigal, “Homotopies for computation of fixed points on unbounded regions”,Mathematical Programming 3 (1972) 225–237.
B.C. Eaves and H. Scarf, “The solution of systems of piecewise linear equations”,Mathematics of Operations Research 1 (1976) 1–27.
P. Henrici,Applied and computational complex analysis, Vol. 1 (Wiley, New York, 1974).
C.B. Garcia and W.I. Zangwill, “Determining all solutions to certain systems of nonlinear equations”, Report 7712, Dept. of Economics and Graduate School of Business, Univ. of Chicago (1977).
M. Kojima, “Studies on PL approximation of piecewise-C 1 mappings in fixed points and complementarity theory”,Mathematics of Operations Research 3 (1978) 17–36.
M. Kojima, H. Nishino and T. Sekine, “An extension of Lemke's method to the piecewise linear complementarity problem”,SIAM Journal on Applied Mathematics 31 (1976) 600–613.
H.W. Kuhn, “Simplicial approximation of fixed points”,Proceedings of National Adacemy of Science 61 (1968) 1238–1242.
H.W. Kuhn, “A new proof of the fundamental theorem of algebra”,Mathematical Programming Studies 1 (1974) 148–158.
H.W. Kuhn, “Finding roots of polynomials by pivoting”, in: S. Karamardian, ed.,Fixed points: algorithms and applications (Academic Press, New York, 1977).
J.M. Ortega and W. Rheinboldt,Iterative solutions of nonlinear equations in several variables (Academic Press, New York, 1970).
M.J. Todd, “On triangulations for computing fixed points”,Mathematical Programming 10 (1976) 322–346.
J.H.C. Whitehead, “OnC 1-complexes”,Annals of Mathematics 41 (1940) 809–824.
O.H. Merrill, “Applications and extensions of an algorithm that computes fixed points of certain upper semicontinuous point to set mappings”, Ph.D. Thesis, University of Michigan (Michigan, 1972).
Author information
Authors and Affiliations
Additional information
This work was supported by grants from Management Science Development Foundation and Takeda Science Foundation.
Rights and permissions
About this article
Cite this article
Kojima, M., Nishino, H. & Arima, N. A PL homotopy for finding all the roots of a polynomial. Mathematical Programming 16, 37–62 (1979). https://doi.org/10.1007/BF01582093
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01582093