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

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]**H. SCARF, "The approximation of fixed points of a continuous mapping,"*SIAM J. Appl. Math.*, v. 15, 1967, pp. 1328-1343. MR**0242483 (39:3814)****[2]**B. C. EAVES, "An odd theorem,"*Proc. Amer. Math. Soc.*, v. 26, 1970, pp. 509-513. MR**0270757 (42:5645)****[3]**H. W. KUHN, "Simplicial approximation of fixed points,"*Proc. Nat. Acad. Sci. U.S.A.*, v. 61, 1968, pp. 1238-1242. MR**0488010 (58:7589)****[4]**B. C. EAVES, "Homotopies for the computation of fixed points,"*Math. Programming*, v. 3, 1972, pp. 1-22. MR**0303953 (46:3089)****[5]**B. C. EAVES & R. SAIGAL, "Homotopies for the computation of fixed points on unbounded regions,"*Math. Programming*, v. 3, 1972, pp. 225-237. MR**0314028 (47:2580)****[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 & J. A. YORKE, "A constructive proof of the Brouwer Fixed Point Theorem and computational results,"*SIAM J. Numer. Anal.*, v. 13, 1976, pp. 473-483. MR**0416010 (54:4087)****[9]**S. SMALE, "A convergent process of price adjustment and global Newton methods,"*J. Math. Econom.*, v. 3, 1976, pp. 1-14. MR**0411577 (53:15310)****[10]**M. HIRSCH & S. SMALE, Personal communication.**[11]**L. S. PONTRJAGIN, "Smooth manifolds and their applications in homotopy theory,"*Trudy Mat. Inst. Steklov.*, v. 45, 1955; English transl.,*Amer. Math. Soc. Transl*. (2), v. 11, 1959, pp. 1-114. MR**0115178 (22:5980)****[12]**M. HIRSCH, "A proof of nonretractability of a cell onto its boundary,"*Proc. Amer. Math. Soc.*, v. 14, 1963, pp. 364-365. MR**0145502 (26:3033)****[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. C. EAVES & H. SCARF, "The solution of systems of piecewise linear equations,"*Math. of Oper. Res.*, v. 1, 1976, pp. 1-27. MR**0445792 (56:4126)****[16]**W. C. RHEINBOLDT, "Numerical continuation methods for finite element applications,"*Formulation and Computational Algorithms in Finite Element Analysis*, (Proc. U. S.-German Sympos.), M.I.T. Press, Cambridge, Mass. (To appear.) MR**0474782 (57:14415)****[17]**R. ABRAHAM & J. ROBBIN,*Transversal Mappings and Flows*, Benjamin, New York, 1967. MR**0240836 (39:2181)****[18]**J. MILNOR,*Topology from the Differentiate Viewpoint*, Univ. of Virginia Press, Charlottesville, Va., 1965. MR**0226651 (37:2239)****[19]**A. MAS-COLELL, "A note on a theorem of F. Browder,"*Math. Programming*, v. 6, 1974, pp. 229-233. MR**0341225 (49:5975)****[20]**F. E. BROWDER, "On the continuity of fixed points under deformations of continuous mappings,"*Summa Brasil. Math.*, v. 4, 1960, pp. 183-191. MR**0130683 (24:A543)****[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.*, v. 70, 1978, pp. 5-7. MR**487546 (80a:55002)****[23]**S. FRIEDLAND, "Inverse eigenvalue problems,"*Linear Algebra and Appl.*, v. 17, 1977, pp. 15-51. MR**0472861 (57:12550)****[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 & J. A. YORKE, "Existence of solutions of two-point boundary value problems for non-linear systems,"*J. Differential Equations*, v. 11, 1972, pp. 509-518. MR**0299867 (45:8915)****[26]**M. A. KRASNOSELSKII,*Topological Methods in the Theory of Nonlinear Integral Equations*, Pergamon Press, New York, 1964. MR**0159197 (28:2414)****[27]**J. M. ORTEGA & W. C. RHEINBOLDT,*Iterative Solution of Nonlinear Equations in Several Variables*, Academic Press, New York, 1970. MR**0273810 (42:8686)****[28]**J. DAVIS,*The Solution of Nonlinear Operator Equations with Critical Points*, Ph. D. thesis, Oregon State Univ., 1966.**[29]**G. MEYER, "On solving nonlinear equations with a one-parameter operator imbedding,"*SIAM J. Numer. Anal.*, v. 5, 1968, pp. 739-752. MR**0242366 (39:3697)****[30]**J. ALEXANDER & J. A. YORKE, "The homotopy continuation method: Numerically implementable topological procedures,"*Trans. Amer. Math. Soc.*, v. 242, 1978, pp. 271-284. MR**0478138 (57:17627)**

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