Effective topological degree computation based on interval arithmetic

Franek, Peter; Ratschan, Stefan

doi:10.1090/S0025-5718-2014-02877-9

Effective topological degree computation based on interval arithmetic
HTML articles powered by AMS MathViewer

by Peter Franek and Stefan Ratschan PDF

Math. Comp. 84 (2015), 1265-1290 Request permission

Abstract:

We describe a new algorithm for calculating the topological degree $\mathrm {deg }(f,B,0)$ where $B\subseteq \mathbb {R}^n$ is a product of closed real intervals and $f:B\to \mathbb {R}^n$ is a real-valued continuous function given in the form of arithmetical expressions. The algorithm cleanly separates numerical from combinatorial computation. Based on this, the numerical part provably computes only the information that is strictly necessary for the following combinatorial part, and the combinatorial part may optimize its computation based on the numerical information computed before. We present computational experiments based on an implementation of the algorithm. In contrast to previous work, the algorithm does not assume knowledge of a Lipschitz constant of the function $f$, and works for arbitrary continuous functions for which some notion of interval arithmetic can be defined.

References

Oliver Aberth, Computation of topological degree using interval arithmetic, and applications, Math. Comp. 62 (1994), no. 205, 171–178. MR 1203731, DOI 10.1090/S0025-5718-1994-1203731-4
G. E. Alefeld, F. A. Potra, and Z. Shen, On the existence theorems of Kantorovich, Moore and Miranda, Topics in numerical analysis, Comput. Suppl., vol. 15, Springer, Vienna, 2001, pp. 21–28. MR 1874501, DOI 10.1007/978-3-7091-6217-0_{3}
Thomas Beelitz, Andreas Frommer, Bruno Lang, and Paul Willems, A framework for existence tests based on the topological degree and homotopy, Numer. Math. 111 (2009), no. 4, 493–507. MR 2471608, DOI 10.1007/s00211-008-0193-3
T. Boult and K. Sikorski, Complexity of computing topological degree of Lipschitz functions in $n$ dimensions, J. Complexity 2 (1986), no. 1, 44–59. MR 925343, DOI 10.1016/0885-064X(86)90022-1
L. E. J. Brouwer, Über Abbildung von Mannigfaltigkeiten, Math. Ann. 71 (1911), no. 1, 97–115 (German). MR 1511644, DOI 10.1007/BF01456931
Robert F. Brown, A topological introduction to nonlinear analysis, 2nd ed., Birkhäuser Boston, Inc., Boston, MA, 2004. MR 2020421, DOI 10.1007/978-0-8176-8124-1
A. Bruckner, J. Bruckner, and B. Thomson, Real Analysis. Prentice Hall PTR, 1997.
Pieter Collins, 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., vol. 221, Elsevier Sci. B. V., Amsterdam, 2008, pp. 37–43. MR 2873345, DOI 10.1016/j.entcs.2008.12.005
Jane Cronin, Fixed points and topological degree in nonlinear analysis, Mathematical Surveys, No. 11, American Mathematical Society, Providence, R.I., 1964. MR 0164101
Jianwei Dian and R. Baker Kearfott, Existence verification for singular and nonsmooth zeros of real nonlinear systems, Math. Comp. 72 (2003), no. 242, 757–766. MR 1954966, DOI 10.1090/S0025-5718-02-01427-8
Pavel Drábek and Jaroslav Milota, Methods of nonlinear analysis, Birkhäuser Advanced Texts: Basler Lehrbücher. [Birkhäuser Advanced Texts: Basel Textbooks], Birkhäuser Verlag, Basel, 2007. Applications to differential equations. MR 2323436
P. J. Erdelsky, Computing the Brouwer degree in $R^{2}$, Math. Comp. 27 (1973), 133–137. MR 326990, DOI 10.1090/S0025-5718-1973-0326990-5
Irene Fonseca and Wilfrid Gangbo, Degree theory in analysis and applications, Oxford Lecture Series in Mathematics and its Applications, vol. 2, The Clarendon Press, Oxford University Press, New York, 1995. Oxford Science Publications. MR 1373430
P. Franek, S. Ratschan, and P. Zgliczynski, Quasi-decidability of a fragment of the first-order theory of real numbers, http://www2.cs.cas.cz/~ratschan/papers/quasidec_constr.pdf, 2012 (preprint).
Andreas Frommer and Bruno Lang, Existence tests for solutions of nonlinear equations using Borsuk’s theorem, SIAM J. Numer. Anal. 43 (2005), no. 3, 1348–1361. MR 2177808, DOI 10.1137/S0036142903438148
A. Frommer, B. Lang, and M. Schnurr, A comparison of the Moore and Miranda existence tests, Computing 72 (2004), no. 3-4, 349–354. MR 2081828, DOI 10.1007/s00607-004-0064-4
Massimo Furi, Maria Patrizia Pera, and Marco Spadini, A set of axioms for the degree of a tangent vector field on differentiable manifolds, Fixed Point Theory Appl. , posted on (2010), Art. ID 845631, 11. MR 2645107, DOI 10.1155/2010/845631
T. J. Hickey. smathlib. http://interval.sourceforge.net/interval/prolog/clip/clip/smath/README.html.
Morris W. Hirsch, Differential topology, Graduate Texts in Mathematics, No. 33, Springer-Verlag, New York-Heidelberg, 1976. MR 0448362
Anatole Katok and Boris Hasselblatt, Introduction to the modern theory of dynamical systems, Encyclopedia of Mathematics and its Applications, vol. 54, Cambridge University Press, Cambridge, 1995. With a supplementary chapter by Katok and Leonardo Mendoza. MR 1326374, DOI 10.1017/CBO9780511809187
Baker Kearfott, An efficient degree-computation method for a generalized method of bisection, Numer. Math. 32 (1979), no. 2, 109–127. MR 529902, DOI 10.1007/BF01404868
R. Baker Kearfott, Jianwei Dian, and A. Neumaier, Existence verification for singular zeros of complex nonlinear systems, SIAM J. Numer. Anal. 38 (2000), no. 2, 360–379. MR 1770053, DOI 10.1137/S0036142999361074
R. Baker Kearfott and Jianwei Dian, Existence verification for higher degree singular zeros of nonlinear systems, SIAM J. Numer. Anal. 41 (2003), no. 6, 2350–2373. MR 2034619, DOI 10.1137/S0036142901386057
Wieslaw Krawcewicz and Jianhong Wu, Theory of degrees with applications to bifurcations and differential equations, Canadian Mathematical Society Series of Monographs and Advanced Texts, John Wiley & Sons, Inc., New York, 1997. A Wiley-Interscience Publication. MR 1426128
J. Mawhin, Topological degree methods in nonlinear boundary value problems, CBMS Regional Conference Series in Mathematics, vol. 40, American Mathematical Society, Providence, R.I., 1979. Expository lectures from the CBMS Regional Conference held at Harvey Mudd College, Claremont, Calif., June 9–15, 1977. MR 525202
John W. Milnor, Topology from the differentiable viewpoint, Princeton Landmarks in Mathematics, Princeton University Press, Princeton, NJ, 1997. Based on notes by David W. Weaver; Revised reprint of the 1965 original. MR 1487640
Carlo Miranda, Un’osservazione su un teorema di Brouwer, Boll. Un. Mat. Ital. (2) 3 (1940), 5–7 (Italian). MR 0004775
Ramon E. Moore, R. Baker Kearfott, and Michael J. Cloud, Introduction to interval analysis, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2009. MR 2482682, DOI 10.1137/1.9780898717716
K. Nakakura and S. Murashige, Numerical Computation of the Mapping Degree Using Computational Homology. 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.
Arnold Neumaier, Interval methods for systems of equations, Encyclopedia of Mathematics and its Applications, vol. 37, Cambridge University Press, Cambridge, 1990. MR 1100928
T. O’Neil and J. W. Thomas, The calculation of the topological degree by quadrature, SIAM J. Numer. Anal. 12 (1975), no. 5, 673–680. MR 411134, DOI 10.1137/0712050
Donal O’Regan, Yeol Je Cho, and Yu-Qing Chen, Topological degree theory and applications, Series in Mathematical Analysis and Applications, vol. 10, Chapman & Hall/CRC, Boca Raton, FL, 2006. MR 2223854, DOI 10.1201/9781420011487
L. B. Rall, A comparison of the existence theorems of Kantorovich and Moore, SIAM J. Numer. Anal. 17 (1980), no. 1, 148–161. MR 559469, DOI 10.1137/0717015
Siegfried M. Rump, Verification methods: rigorous results using floating-point arithmetic, Acta Numer. 19 (2010), 287–449. MR 2652784, DOI 10.1017/S096249291000005X
F. Sauvigny, Brouwer’s degree of mapping with geometric applications. In Partial Differential Equations 1, Universitext, pages 175–214. Springer Berlin Heidelberg, 2006.
Frank Stenger, Computing the topological degree of a mapping in $\textbf {R}^{n}$, Numer. Math. 25 (1975/76), no. 1, 23–38. MR 394639, DOI 10.1007/BF01419526
Martin Stynes, A simplification of Stenger’s topological degree formula, Numer. Math. 33 (1979), no. 2, 147–155. MR 549445, DOI 10.1007/BF01399550
H. Tietze, Über Funktionen, die auf einer abgeschlossenen Menge stetig sind, Journal für Die Reine und Angewandte Mathematik, 145:9–14, 1915.