Finding zeroes of maps: homotopy methods that are constructive with probability one
Authors:
Shui Nee Chow, John MalletParet and James A. Yorke
Journal:
Math. Comp. 32 (1978), 887899
MSC:
Primary 55M25; Secondary 47H10, 65H10, 90C99
MathSciNet review:
492046
Fulltext 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 0242483
(39 #3814)
 [2]
B.
Curtis Eaves, An odd theorem, Proc. Amer. Math. Soc. 26 (1970), 509–513. MR 0270757
(42 #5645), http://dx.doi.org/10.1090/S00029939197002707572
 [3]
Harold
W. Kuhn, Simplicial approximation of fixed points, Proc. Nat.
Acad. Sci. U.S.A. 61 (1968), 1238–1242. MR 0488010
(58 #7589)
 [4]
B.
Curtis Eaves, Homotopies for computation of fixed points,
Math. Programming 3 (1972), 1–22. MR 0303953
(46 #3089)
 [5]
B.
Curtis Eaves and Romesh
Saigal, Homotopies for computation of fixed points on unbounded
regions, Math. Programming 3 (1972), 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. 133147.
 [8]
R.
B. Kellogg, T.
Y. Li, and J.
Yorke, A constructive proof of the Brouwer fixedpoint theorem and
computational results, SIAM J. Numer. Anal. 13
(1976), no. 4, 473–483. MR 0416010
(54 #4087)
 [9]
Steve
Smale, A convergent process of price adjustment and global Newton
methods, J. Math. Econom. 3 (1976), no. 2,
107–120. MR 0411577
(53 #15310)
 [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
(22 #5980)
 [12]
Morris
W. Hirsch, A proof of the nonretractibility of a
cell onto its boundary, Proc. Amer. Math.
Soc. 14 (1963),
364–365. MR 0145502
(26 #3033), http://dx.doi.org/10.1090/S00029939196301455028
 [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 0445792
(56 #4126)
 [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
(57 #14415)
 [17]
Ralph
Abraham and Joel
Robbin, Transversal mappings and flows, An appendix by Al
Kelley, W. A. Benjamin, Inc., New YorkAmsterdam, 1967. MR 0240836
(39 #2181)
 [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
(37 #2239)
 [19]
Andreu
MasColell, A note on a theorem of F. Browder, Math.
Programming 6 (1974), 229–233. MR 0341225
(49 #5975)
 [20]
Felix
E. Browder, On continuity of fixed points under deformations of
continuous mappings, Summa Brasil. Mat. 4 (1960),
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. 70 (1978), no. 1, 5–7. MR 487546
(80a:55002), http://dx.doi.org/10.1090/S00029939197804875463
 [23]
Shmuel
Friedland, Inverse eigenvalue problems, Linear Algebra and
Appl. 17 (1977), no. 1, 15–51. MR 0472861
(57 #12550)
 [24]
G. SCORZADRAGONI, "Sul problema dei valori ai limiti per i system di equazioni differenziali del secondo ordine," Boll. Un. Mat. Ital., v. 14, 1935, pp. 225230.
 [25]
A.
Lasota and James
A. Yorke, Existence of solutions of twopoint boundary value
problems for nonlinear systems, J. Differential Equations
11 (1972), 509–518. MR 0299867
(45 #8915)
 [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
(28 #2414)
 [27]
J.
M. Ortega and W.
C. Rheinboldt, Iterative solution of nonlinear equations in several
variables, Academic Press, New YorkLondon, 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]
Gunter
H. Meyer, On solving nonlinear equations with a oneparameter
operator imbedding., SIAM J. Numer. Anal. 5 (1968),
739–752. MR 0242366
(39 #3697)
 [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 0478138
(57 #17627), http://dx.doi.org/10.1090/S00029947197804781385
 [1]
 H. SCARF, "The approximation of fixed points of a continuous mapping," SIAM J. Appl. Math., v. 15, 1967, pp. 13281343. MR 0242483 (39:3814)
 [2]
 B. C. EAVES, "An odd theorem," Proc. Amer. Math. Soc., v. 26, 1970, pp. 509513. MR 0270757 (42:5645)
 [3]
 H. W. KUHN, "Simplicial approximation of fixed points," Proc. Nat. Acad. Sci. U.S.A., v. 61, 1968, pp. 12381242. MR 0488010 (58:7589)
 [4]
 B. C. EAVES, "Homotopies for the computation of fixed points," Math. Programming, v. 3, 1972, pp. 122. 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. 225237. 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. 133147.
 [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. 473483. MR 0416010 (54:4087)
 [9]
 S. SMALE, "A convergent process of price adjustment and global Newton methods," J. Math. Econom., v. 3, 1976, pp. 114. 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. 1114. 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. 364365. 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. 127. 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. MASCOLELL, "A note on a theorem of F. Browder," Math. Programming, v. 6, 1974, pp. 229233. 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. 183191. 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. 57. MR 487546 (80a:55002)
 [23]
 S. FRIEDLAND, "Inverse eigenvalue problems," Linear Algebra and Appl., v. 17, 1977, pp. 1551. MR 0472861 (57:12550)
 [24]
 G. SCORZADRAGONI, "Sul problema dei valori ai limiti per i system di equazioni differenziali del secondo ordine," Boll. Un. Mat. Ital., v. 14, 1935, pp. 225230.
 [25]
 A. LASOTA & J. A. YORKE, "Existence of solutions of twopoint boundary value problems for nonlinear systems," J. Differential Equations, v. 11, 1972, pp. 509518. 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 oneparameter operator imbedding," SIAM J. Numer. Anal., v. 5, 1968, pp. 739752. 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. 271284. MR 0478138 (57:17627)
Similar Articles
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:
http://dx.doi.org/10.1090/S00255718197804920469
PII:
S 00255718(1978)04920469
Keywords:
Brouwer Fixed Point Theorem,
constructive proof,
Transversality theorem,
degree theory,
vector fields on spheres
Article copyright:
© Copyright 1978
American Mathematical Society
