Effective topological degree computation based on interval arithmetic. (English) Zbl 1318.55002
The authors present a new numerical-combinatorial algorithm for the calculation of the topological degree for a continuous nonlinear map \(f: B \to \mathbb{R}^n\) with \(0 \notin F(\partial B),\) where \(B \subset \mathbb{R}^n\) is a box (the product of compact intervals) or an oriented cubical set (a finite union of well adjoining boxes). Some computational examples are given.
Reviewer: Valerii V. Obukhovskij (Voronezh)
MSC:
| 55-04 | Software, source code, etc. for problems pertaining to algebraic topology |
| 68-04 | Software, source code, etc. for problems pertaining to computer science |
| 55P15 | Classification of homotopy type |
| 55M25 | Degree, winding number |
| 65Q20 | Numerical methods for functional equations |
References:
| [1] | Aberth, Oliver, Computation of topological degree using interval arithmetic, and applications, Math. Comp., 62, 205, 171-178 (1994) · Zbl 0798.55002 · doi:10.2307/2153402 |
| [2] | Alefeld, G. E.; Potra, F. A.; Shen, Z., On the existence theorems of Kantorovich, Moore and Miranda. Topics in numerical analysis, Comput. Suppl. 15, 21-28 (2001), Springer, Vienna · Zbl 0995.65060 · doi:10.1007/978-3-7091-6217-0\_3 |
| [3] | Beelitz, Thomas; Frommer, Andreas; Lang, Bruno; Willems, Paul, A framework for existence tests based on the topological degree and homotopy, Numer. Math., 111, 4, 493-507 (2009) · Zbl 1163.65024 · doi:10.1007/s00211-008-0193-3 |
| [4] | Boult, T.; Sikorski, K., Complexity of computing topological degree of Lipschitz functions in \(n\) dimensions, J. Complexity, 2, 1, 44-59 (1986) · Zbl 0624.65043 · doi:10.1016/0885-064X(86)90022-1 |
| [5] | Brouwer, L. E. J., \"Uber Abbildung von Mannigfaltigkeiten, Math. Ann., 71, 1, 97-115 (1911) · JFM 42.0417.01 · doi:10.1007/BF01456931 |
| [6] | Brown, Robert F., A Topological Introduction to Nonlinear Analysis, xiv+184 pp. (2004), Birkh\"auser Boston Inc.: Boston, MA:Birkh\"auser Boston Inc. · Zbl 1061.47001 · doi:10.1007/978-0-8176-8124-1 |
| [7] | [Bruckner:1997] A. Bruckner, J. Bruckner, and B. Thomson, \newblockReal Analysis. \newblock Prentice Hall PTR, 1997. · Zbl 0872.26001 |
| [8] | Collins, Pieter, Computability and representations of the zero set. Proceedings of the Fifth International Conference on Computability and Complexity in Analysis (CCA 2008), Electron. Notes Theor. Comput. Sci. 221, 37-43 (2008), Elsevier Sci. B. V., Amsterdam · Zbl 1262.03134 · doi:10.1016/j.entcs.2008.12.005 |
| [9] | Cronin, Jane, Fixed Points and Topological Degree in Nonlinear Analysis, Mathematical Surveys, No. 11, xii+198 pp. (1964), American Mathematical Society: Providence, R.I.:American Mathematical Society · Zbl 0117.34803 |
| [10] | Dian, Jianwei; Kearfott, R. Baker, Existence verification for singular and nonsmooth zeros of real nonlinear systems, Math. Comp., 72, 242, 757-766 (2003) · Zbl 1025.65030 · doi:10.1090/S0025-5718-02-01427-8 |
| [11] | Dr{\'a}bek, Pavel; Milota, Jaroslav, Methods of Nonlinear Analysis, Birkh\`“auser Advanced Texts: Basler Lehrb\'”ucher. [Birkh\`“auser Advanced Texts: Basel Textbooks], xii+568 pp. (2007), Birkh\'”auser Verlag: Basel:Birkh\'”auser Verlag · Zbl 1176.35002 |
| [12] | Erdelsky, P. J., Computing the Brouwer degree in \(R^2\), Math. Comp., 27, 133-137 (1973) · Zbl 0385.65026 |
| [13] | Fonseca, Irene; Gangbo, Wilfrid, Degree Theory in Analysis and Applications, Oxford Lecture Series in Mathematics and its Applications 2, viii+211 pp. (1995), The Clarendon Press Oxford University Press: New York:The Clarendon Press Oxford University Press · Zbl 0852.47030 |
| [14] | [Franek:12] P. Franek, S. Ratschan, and P. Zgliczynski, \newblockQuasi-decidability of a fragment of the first-order theory of real numbers, \newblock\urlhttp://www2.cs.cas.cz/ ratschan/papers/quasidec_constr.pdf, 2012 \newblock(preprint). · Zbl 1437.03047 |
| [15] | Frommer, Andreas; Lang, Bruno, Existence tests for solutions of nonlinear equations using Borsuk’s theorem, SIAM J. Numer. Anal., 43, 3, 1348-1361 (electronic) (2005) · Zbl 1095.47057 · doi:10.1137/S0036142903438148 |
| [16] | Frommer, A.; Lang, B.; Schnurr, M., A comparison of the Moore and Miranda existence tests, Computing, 72, 3-4, 349-354 (2004) · Zbl 1069.47060 · doi:10.1007/s00607-004-0064-4 |
| [17] | Furi, Massimo; Pera, Maria Patrizia; Spadini, Marco, A set of axioms for the degree of a tangent vector field on differentiable manifolds, Fixed Point Theory Appl., Art. ID 845631, 11 pp. (2010) · Zbl 1196.57026 |
| [18] | [Hickey] T. J. Hickey. \newblock smathlib. \newblock\urlhttp://interval.sourceforge.net/interval/prolog/clip/clip/smath/README.html. |
| [19] | Hirsch, Morris W., Differential Topology, x+221 pp. (1976, Graduate Texts in Mathematics, No. 33), Springer-Verlag: New York:Springer-Verlag · Zbl 0356.57001 |
| [20] | Katok, Anatole; Hasselblatt, Boris, Introduction to the Modern Theory of Dynamical Systems, Encyclopedia of Mathematics and its Applications 54, xviii+802 pp. (1995), Cambridge University Press: Cambridge:Cambridge University Press · Zbl 0878.58020 |
| [21] | Kearfott, Baker, An efficient degree-computation method for a generalized method of bisection, Numer. Math., 32, 2, 109-127 (1979) · Zbl 0386.65016 · doi:10.1007/BF01404868 |
| [22] | Kearfott, R. Baker; Dian, Jianwei; Neumaier, A., Existence verification for singular zeros of complex nonlinear systems, SIAM J. Numer. Anal., 38, 2, 360-379 (2000) · Zbl 0986.65054 · doi:10.1137/S0036142999361074 |
| [23] | Kearfott, R. Baker; Dian, Jianwei, Existence verification for higher degree singular zeros of nonlinear systems, SIAM J. Numer. Anal., 41, 6, 2350-2373 (2003) · Zbl 1059.65045 · doi:10.1137/S0036142901386057 |
| [24] | Krawcewicz, Wieslaw; Wu, Jianhong, Theory of Degrees with Applications to Bifurcations and Differential Equations, Canadian Mathematical Society Series of Monographs and Advanced Texts, xvi+374 pp. (1997), John Wiley & Sons Inc.: New York:John Wiley & Sons Inc. · Zbl 0882.58001 |
| [25] | Mawhin, J., Topological Degree Methods in Nonlinear Boundary Value Problems, CBMS Regional Conference Series in Mathematics 40, v+122 pp. (1979), American Mathematical Society: Providence, R.I.:American Mathematical Society · Zbl 0414.34025 |
| [26] | Milnor, John W., Topology from the Differentiable Viewpoint, Princeton Landmarks in Mathematics, xii+64 pp. (1997), Princeton University Press: Princeton, NJ:Princeton University Press · Zbl 1025.57002 |
| [27] | Miranda, Carlo, Un’osservazione su un teorema di Brouwer, Boll. Un. Mat. Ital. (2), 3, 5-7 (1940) · Zbl 0024.02203 |
| [28] | Moore, Ramon E.; Kearfott, R. Baker; Cloud, Michael J., Introduction to Interval Analysis, xii+223 pp. (2009), Society for Industrial and Applied Mathematics (SIAM): Philadelphia, PA:Society for Industrial and Applied Mathematics (SIAM) · Zbl 1168.65002 · doi:10.1137/1.9780898717716 |
| [29] | [Murashige:06] K. Nakakura and S. Murashige, \newblockNumerical Computation of the Mapping Degree Using Computational Homology. \newblock In Proceedings of the 12th GAMM - IMACS International Symposium on Scientific Computing, Computer Arithmetic and Validated Numerics, SCAN ’06, page 34, Washington, DC, USA, 2006. IEEE Computer Society. |
| [30] | Neumaier, Arnold, Interval Methods for Systems of Equations, Encyclopedia of Mathematics and its Applications 37, xvi+255 pp. (1990), Cambridge University Press: Cambridge:Cambridge University Press · Zbl 0715.65030 |
| [31] | O’Neil, T.; Thomas, J. W., The calculation of the topological degree by quadrature, SIAM J. Numer. Anal., 12, 5, 673-680 (1975) · Zbl 0327.65044 |
| [32] | O’Regan, Donal; Cho, Yeol Je; Chen, Yu-Qing, Topological Degree Theory and Applications, Series in Mathematical Analysis and Applications 10, iv+221 pp. (2006), Chapman & Hall/CRC, Boca Raton, FL · Zbl 1095.47001 · doi:10.1201/9781420011487 |
| [33] | Rall, L. B., A comparison of the existence theorems of Kantorovich and Moore, SIAM J. Numer. Anal., 17, 1, 148-161 (1980) · Zbl 0441.65037 · doi:10.1137/0717015 |
| [34] | Rump, Siegfried M., Verification methods: rigorous results using floating-point arithmetic, Acta Numer., 19, 287-449 (2010) · Zbl 1323.65046 · doi:10.1017/S096249291000005X |
| [35] | [Sauvigny:06] F. Sauvigny, \newblockBrouwer’s degree of mapping with geometric applications. \newblock In Partial Differential Equations 1, Universitext, pages 175-214. Springer Berlin Heidelberg, 2006. · Zbl 1198.35001 |
| [36] | Stenger, Frank, Computing the topological degree of a mapping in \({\bf R}^n\), Numer. Math., 25, 1, 23-38 (1975/76) · Zbl 0316.55007 |
| [37] | Stynes, Martin, A simplification of Stenger’s topological degree formula, Numer. Math., 33, 2, 147-155 (1979) · Zbl 0387.65035 · doi:10.1007/BF01399550 |
| [38] | [Tietze:1915] H. Tietze, \newblock\`“Uber Funktionen, die auf einer abgeschlossenen Menge stetig sind, \newblockJournal f\'”ur Die Reine und Angewandte Mathematik, 145:9-14, 1915. \endbiblist · JFM 45.0628.03 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
