# Mathematical Limitations of Computer Experiments

One problem that has always bothered me is the limitations of computers in studying math. With a chaotic dynamical system, for example, we know mathematically that they possess trajectories that never repeat themselves. But computationally, it seems that such an orbit can never be realized (since given the finite number of values that a computer can work with, periodicity seems inevitable). Yet, people study chaos with computers. They use mathematics of course, but considering the role that computers play in helping us gain intuition of complex systems, I wonder if there are aspects of a system we might totally miss by using computers in such a fashion.

Thanks, Jack

• Isn't that kind of like saying irrational numbers can't exist because you only have 10 digits to work with? It takes more than coming back to the same value to make something periodic. Why can't chaos exist in a finite space? – Robert Mastragostino Mar 18 '13 at 16:26
• First, we need to make sure we are on the same page. So question one: are there things mathematically that we can't observe on a computer? It seems to me there are. – Jack Zega Mar 18 '13 at 16:29
• Secondly, I don't see why it takes more than coming back to the same value to be periodic. The definition of periodic wrt a computer simulation whose output at the nth step is f(n), would be that there exists a N in the natural numbers such that f(n+N)=f(n) for all natural numbers n. – Jack Zega Mar 18 '13 at 16:36
• Sure. There will always be integers larger than a particular fixed memory size. I didn't mean to dispute the fundamental idea. My point is just that the issue of concern is that the number of internal states is bounded, not that the number of output states is. – Robert Mastragostino Mar 18 '13 at 16:56
• Sure, as the computer has finite state, it has to return to a state already visited sometime, and so it's behaviour is eventually periodic. Won't be soon... – vonbrand Mar 18 '13 at 18:58

## 3 Answers

Numerical simulation of dynamic systems is indeed hard.

One difficulty is that it is implemented using floating-point arithmetic, which is subject to rounding errors. For chaotic dynamical systems, the ones that have strange attractors, rounding errors are potentially serious, because orbits starting at nearby points can diverge from each other exponentially. Sometimes, this strong sensitivity to initial conditions does not affect the overall picture, because numerically computed orbits are shadowed by exact orbits that capture the typical behavior of the system. However, the truth is that rounding errors affect numerical simulations of dynamical systems in very complex ways [1]. Well-conditioned dynamical systems may display chaotic numerical behavior [2,3]. Conversely, numerical methods can suppress chaos in some chaotic dynamical systems [3]. (Text extracted from [4].)

Nevertheless, there are computational methods for studying dynamical systems that work reliably even in the presence of rounding errors. See the work of Warwick Tucker, Zbigniew Galias, Pawel Pilarczyk, and others.

[1] Corless, What good are numerical simulations of chaotic dynamical systems? Comput. Math. Appl. 28 (1994) 107–121. MR1300684

[2] Adams et al., Computational chaos may be due to a single local error. J. Comput. Phys. 104 (1993) 241–250. MR1198231

[3] Corless et al., Numerical methods can suppress chaos, Physics Letters A 157 (1991) 127-36. DOI 10.1016/0375-9601(91)90404-V

[4] Paiva et al., Robust visualization of strange attractors using affine arithmetic, Computers & Graphics 30 (2006), no. 6, 1020-1026. DOI 10.1016/j.cag.2006.08.016

• Thank you for your thoughts and the references! Like everyone here, I would try to use a rigorous mathematical analysis first, but it is a problem because sometimes this is not possible b/c the theory of dynamical systems is still somewhat limited in what we know. I'm talking beyond my level of knowledge, but I've heard it said that there are computational tools one can use from topology (and here I am thinking specifically of "Conley index theory") that addresses some of these concerns. Is this true? – Jack Zega Mar 18 '13 at 19:46
• The notion of 'shadowing of orbits' is probably the point most worth fleshing out - it's the first thing that came to mind for me, and it's likely to be the most fruitful search term for hunting down more information on the topic. – Steven Stadnicki Mar 18 '13 at 19:48
• Thank you Steven and lhf for the information! To me, it is a fascinating problem, but I had never heard of anyone who had addressed it before (but then again, I'm only at the Masters level in maths). – Jack Zega Mar 18 '13 at 20:43

It's a valid concern, and I have a historical anecdote to match it. When Mandelbrot published the first picture of the Mandelbrot set, the image was of poor quality due to the state of informatics back then. Seeing what he thought where "speck of dusts" on the picture, his editor erased them. Since then we obtained much better pictures of course, and we know that these specks of dust are "islands" that are linked to the main body of the Mandelbrot set by "hairs" of empty interior (which were not very visible in Mandelbrot's picture).

The point is, computers are a tool to guide your intuition but you should not rely solely on them. Think of imperfect computer pictures/simulation as drawing a surface instead of a n-manifold : it helps understanding what is going on, but it works together with a more rigorous understanding of the objects you are manipulating. Otherwise you are indeed bound to make mistakes.

• This is my general take on the matter, too. I'll tell you the genesis of my question. I developed a numerical iterative method for finding the maximum likelihood estimator for some problem. It was very difficult to prove whether or not the method converged for all reals, but it always converged whatever starting point I used on the computer. I always wondered, could there exist a set of numbers which I could do not work with computationally for which this method does not converge. This is an example of a problem where we might totally miss a result using the computer. – Jack Zega Mar 18 '13 at 16:48
• @JackZega I agree – Glougloubarbaki Mar 18 '13 at 16:56
• There are infinite examples of mathematical truths that a computer cannot answer either. Many are related with the halting problem. For instance, a computer cannot compute the well defined Chaitin's $\Omega$ number, which is not computable – Wolphram jonny Mar 18 '13 at 18:23

The set of nonlinear systems that can be understood analytically is a measure zero set. Numerical experiments, and numerical algorithms, are a necessary tool in the study of these systems. But I agree that there is a need for more robust numerical tools for studying complex systems.

Anyways, regarding chaotic sets, the "set-oriented" Perron-Frobenius operator-theoretic approach to numerically studying the densities and probability distributions on these systems rather than individual trajectories has been quite successful. See work by G.Froyland, M. Dellnitz, I. Mezic etc. On the other hand, topological quantities such as topological entropy are robust to numerical errors and don't rely on exact computation of trajectories, e.g. see work by P. Boyland etc. So there are other ways of understanding these systems than just numerically tracking individual trajectories.

• Thank you very much for the information. These are terms which I would never know to look for. I want to go on and get my PhD in math, and this is a problem I find singularly interesting, so I'll play around and see what I can found out. – Jack Zega Mar 18 '13 at 20:40