Finding zeroes of maps: homotopy methods that are constructive with probability one

Authors:
Shui Nee Chow, John Mallet-Paret and James A. Yorke

Journal:
Math. Comp. **32** (1978), 887-899

MSC:
Primary 55M25; Secondary 47H10, 65H10, 90C99

DOI:
https://doi.org/10.1090/S0025-5718-1978-0492046-9

MathSciNet review:
492046

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We illustrate that most existence theorems using degree theory are in principle relatively constructive. The first one presented here is the Brouwer Fixed Point Theorem. Our method is "constructive with probability one" and can be implemented by computer. Other existence theorems are also proved by the same method. The approach is based on a transversality theorem.

**[1]**Herbert Scarf,*The approximation of fixed points of a continuous mapping*, SIAM J. Appl. Math.**15**(1967), 1328–1343. MR**242483**, https://doi.org/10.1137/0115116**[2]**B. Curtis Eaves,*An odd theorem*, Proc. Amer. Math. Soc.**26**(1970), 509–513. MR**270757**, https://doi.org/10.1090/S0002-9939-1970-0270757-2**[3]**Harold W. Kuhn,*Simplicial approximation of fixed points*, Proc. Nat. Acad. Sci. U.S.A.**61**(1968), 1238–1242. MR**488010**, https://doi.org/10.1073/pnas.61.4.1238**[4]**B. Curtis Eaves,*Homotopies for computation of fixed points*, Math. Programming**3**(1972), 1–22. MR**303953**, https://doi.org/10.1007/BF01584975**[5]**B. Curtis Eaves and Romesh Saigal,*Homotopies for computation of fixed points on unbounded regions*, Math. Programming**3**(1972), 225–237. MR**314028**, https://doi.org/10.1007/BF01584991**[6]**R. T. WILLMUTH,*The Computation of Fixed Points*, Ph. D. Thesis, Dept. of Operations Research, Stanford University, 1973.**[7]**R. B. KELLOGG, T. Y. LI & J. A. YORKE, "A method of continuation for calculating a Brouwer fixed point,"*Computing Fixed Points with Applications*(Proc. Conf., Clemson Univ., 1974), S. Karamadian (editor), Academic Press, New York, 1977, pp. 133-147.**[8]**R. B. Kellogg, T. Y. Li, and J. Yorke,*A constructive proof of the Brouwer fixed-point theorem and computational results*, SIAM J. Numer. Anal.**13**(1976), no. 4, 473–483. MR**416010**, https://doi.org/10.1137/0713041**[9]**Steve Smale,*A convergent process of price adjustment and global Newton methods*, J. Math. Econom.**3**(1976), no. 2, 107–120. MR**411577**, https://doi.org/10.1016/0304-4068(76)90019-7**[10]**M. HIRSCH & S. SMALE, Personal communication.**[11]**L. S. Pontryagin,*Smooth manifolds and their applications in homotopy theory*, American Mathematical Society Translations, Ser. 2, Vol. 11, American Mathematical Society, Providence, R.I., 1959, pp. 1–114. MR**0115178****[12]**Morris W. Hirsch,*A proof of the nonretractibility of a cell onto its boundary*, Proc. Amer. Math. Soc.**14**(1963), 364–365. MR**145502**, https://doi.org/10.1090/S0002-9939-1963-0145502-8**[13]**T. Y. LI, "A rigorous algorithm for fixed point computation." (To appear.)**[14]**L. WATSON, "Finding fixed points of maps by using homotopy methods,"*Computation and Appl. Math.*(To appear.)**[15]**B. Curtis Eaves and Herbert Scarf,*The solution of systems of piecewise linear equations*, Math. Oper. Res.**1**(1976), no. 1, 1–27. MR**445792**, https://doi.org/10.1287/moor.1.1.1**[16]**Werner C. Rheinboldt,*Numerical continuation methods for finite element applications*, Formulations and computational algorithms in finite element analysis (U.S.-Germany Sympos., Mass. Inst. Tech., Cambridge, Mass., 1976) M.I.T. Press, Cambridge, Mass., 1977, pp. 599–631. MR**0474782****[17]**Ralph Abraham and Joel Robbin,*Transversal mappings and flows*, An appendix by Al Kelley, W. A. Benjamin, Inc., New York-Amsterdam, 1967. MR**0240836****[18]**John W. Milnor,*Topology from the differentiable viewpoint*, Based on notes by David W. Weaver, The University Press of Virginia, Charlottesville, Va., 1965. MR**0226651****[19]**Andreu Mas-Colell,*A note on a theorem of F. Browder*, Math. Programming**6**(1974), 229–233. MR**341225**, https://doi.org/10.1007/BF01580239**[20]**Felix E. Browder,*On continuity of fixed points under deformations of continuous mappings*, Summa Brasil. Math.**4**(1960), 183–191. MR**130683****[21]**J. L. LIONS,*Quelques Méthodes de Résolution des Problèmes aux Limites Non Linéaires*, Dunod, Paris, 1969.**[22]**J. C. Alexander,*The additive inverse eigenvalue problem and topological degree*, Proc. Amer. Math. Soc.**70**(1978), no. 1, 5–7. MR**487546**, https://doi.org/10.1090/S0002-9939-1978-0487546-3**[23]**Shmuel Friedland,*Inverse eigenvalue problems*, Linear Algebra Appl.**17**(1977), no. 1, 15–51. MR**472861**, https://doi.org/10.1016/0024-3795(77)90039-8**[24]**G. SCORZA-DRAGONI, "Sul problema dei valori ai limiti per i system di equazioni differenziali del secondo ordine,"*Boll. Un. Mat. Ital.*, v. 14, 1935, pp. 225-230.**[25]**A. Lasota and James A. Yorke,*Existence of solutions of two-point boundary value problems for nonlinear systems*, J. Differential Equations**11**(1972), 509–518. MR**299867**, https://doi.org/10.1016/0022-0396(72)90063-0**[26]**M. A. Krasnosel’skii,*Topological methods in the theory of nonlinear integral equations*, Translated by A. H. Armstrong; translation edited by J. Burlak. A Pergamon Press Book, The Macmillan Co., New York, 1964. MR**0159197****[27]**J. M. Ortega and W. C. Rheinboldt,*Iterative solution of nonlinear equations in several variables*, Academic Press, New York-London, 1970. MR**0273810****[28]**J. DAVIS,*The Solution of Nonlinear Operator Equations with Critical Points*, Ph. D. thesis, Oregon State Univ., 1966.**[29]**Gunter H. Meyer,*On solving nonlinear equations with a one-parameter operator imbedding*, SIAM J. Numer. Anal.**5**(1968), 739–752. MR**242366**, https://doi.org/10.1137/0705057**[30]**J. C. Alexander and James A. Yorke,*The homotopy continuation method: numerically implementable topological procedures*, Trans. Amer. Math. Soc.**242**(1978), 271–284. MR**478138**, https://doi.org/10.1090/S0002-9947-1978-0478138-5

Retrieve articles in *Mathematics of Computation*
with MSC:
55M25,
47H10,
65H10,
90C99

Retrieve articles in all journals with MSC: 55M25, 47H10, 65H10, 90C99

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1978-0492046-9

Keywords:
Brouwer Fixed Point Theorem,
constructive proof,
Transversality theorem,
degree theory,
vector fields on spheres

Article copyright:
© Copyright 1978
American Mathematical Society