rdb@scs.carleton.ca (Robert D. Black) (06/21/91)
I recently read that the chaotic logistic equation
u(t+1) = 4u(t)(1-u(t)) u(0) in 0..1,
t = 0,1,2,...
has an ANALYTIC SOLUTION:
u(t) = sin**2 (2**(t-1) arccos(1-2u(0)))
Reference "Differential Equations" by Walter G. Kelly and
Alan C. Peterson, Academic Press 1991, p184.
This is CONFUSING! Wasn't it the case that solvable systems
are by definition predictable and hence not chaotic? Here you
can find the value of the system at any time t without computing
intermediate values. Yet the logistic equation above is said to be
chaotic!
What's going on here?
--
--
Robert Black rdb@scs.carleton.ca
School of Computer Science
Carleton University, Ottawa, Canadamroussel@alchemy.chem.utoronto.ca (Marc Roussel) (06/21/91)
In article <1991Jun20.194552.15875@cunews.carleton.ca> rdb@scs.carleton.ca (Robert D. Black) writes: >I recently read that the chaotic logistic equation > u(t+1) = 4u(t)(1-u(t)) u(0) in 0..1, > t = 0,1,2,... >has an ANALYTIC SOLUTION: > u(t) = sin**2 (2**(t-1) arccos(1-2u(0))) > > Reference "Differential Equations" by Walter G. Kelly and > Alan C. Peterson, Academic Press 1991, p184. > >This is CONFUSING! Wasn't it the case that solvable systems >are by definition predictable and hence not chaotic? Here you >can find the value of the system at any time t without computing >intermediate values. The problem with the term "chaos" is that it has a substantially different technical meaning from its common meaning. Chaotic systems are defined as systems whose long-term properties are unpredictable given some initial condition, except perhaps in a statistical sense. If you stuck some initial condition u(0) into your analytic solution and found (say) u(10000) in single precision and then in double precision, I'll wager that the two answers would be substantially different. Analogously (and perhaps more importantly), if you took some u(0) and another initial condition u(0)+du, where du is very small, you would more than likely find significant differences in u(10000). Look at the way t enters into the solution. Small differences in u(0) (or differences in the precision of the arithmetic used) will be greatly amplified by the 2**(t-1) term. The unpredictability in chaotic dynamical systems is quite apparent. Given an initial condition specified to finite accuracy, you can't say where exactly you'll wind up after a very long time. Marc R. Roussel mroussel@alchemy.chem.utoronto.ca
rdb@scs.carleton.ca (Robert D. Black) (06/21/91)
In article <1991Jun20.203628.14343@alchemy.chem.utoronto.ca> mroussel@alchemy.chem.utoronto.ca (Marc Roussel) writes: > >If you stuck some initial condition u(0) into your analytic solution and >found (say) u(10000) in single precision and then in double precision, >I'll wager that the two answers would be substantially different. True, but differences in single vs double precision would be true of most any calculation (square root for example). Chaos enters into an *iterative* process through the rapid growth of errors in the initial condition, or from errors resulting from finite precision arithmetic. Because there is a general solution to the difference equation, we can simply compute U(10000) without computing the first N-1 values (and suffering accumulated round-off error). The value of U(10000) is a close approximation to the theoretical value at time 10000. The value of U(10001) is independent and would not be affected by any error in U(10000). > ... Small differences in u(0) (or differences in the precision >of the arithmetic used) will be greatly amplified by the 2**(t-1) term. Agreed, if your initial condition is not exact, then you quickly lose accuracy as you go to larger times. However, if we assume the initial condition is exact (0.75 say), then we can plug this exact value into the general formula, and get a close approximation to the theoretical value at that time (even for large t). -- -- Robert Black rdb@scs.carleton.ca School of Computer Science Carleton University, Ottawa, Canada
kmc@netcom.COM (Kevin McCarty) (06/21/91)
rdb@scs.carleton.ca (Robert D. Black) writes: >In article <1991Jun20.203628.14343@alchemy.chem.utoronto.ca> mroussel@alchemy.chem.utoronto.ca (Marc Roussel) writes: >> >>If you stuck some initial condition u(0) into your analytic solution and >>found (say) u(10000) in single precision and then in double precision, >>I'll wager that the two answers would be substantially different. >True, but differences in single vs double precision would be true >of most any calculation (square root for example). Chaos enters >into an *iterative* process through the rapid growth of errors in >the initial condition, or from errors resulting from finite >precision arithmetic. Take a closer look at the so-called predictive solution to your formula! Look at its behavior as a function of t. You're taking your initial condition (or a nice, uniformly continuous function of it-- arccos), and you're multiplying it by 2**(t-1), and then you're taking the sine of that. So tell us, what happens to precision when you increment t by 1? You *double* the argument value of the sine. In order to get an answer with one bit of accuracy (e.g., whether the result is closer to 1.0 than 0.0) you need one additional bit of input precision per unit time step. Another way to look at it is that the absolute output error roughly *doubles* with each passing unit of time. In this respect it is no different from f(x) = 2x mod 1. Points initially close together diverge exponentially over time. Compare this with your other example, f(x) = sqrt(x) (on the unit interval [0,1] say). Note that you need hardly any precision at all in the initial condition in order to predict to a pretty good precision the result of iterating f(x) a number of times. In fact, sqrt(x) has an attracting fixed point for almost all initial values. >Because there is a general solution to the difference equation, >we can simply compute U(10000) without computing the first N-1 >values (and suffering accumulated round-off error). The value of >U(10000) is a close approximation to the theoretical value at time >10000. The value of U(10001) is independent and would not be affected >by any error in U(10000). >> ... Small differences in u(0) (or differences in the precision >>of the arithmetic used) will be greatly amplified by the 2**(t-1) term. >Agreed, if your initial condition is not exact, then you quickly >lose accuracy as you go to larger times. However, if we assume The whole point is how fast you lose accuracy. Consider three different dynamical laws described by f(x) = sin**2( 2x ) g(x) = (x + a) mod 1, (0 < a < 1) h(x) = x/2 Analyze the precision to which the n'th iterate is known, as a function of the precision in the initial value of x and the number of iterates. Only f(x) has chaotic behavior. >the initial condition is exact (0.75 say), then we can plug this >exact value into the general formula, and get a close approximation >to the theoretical value at that time (even for large t). If you have an exact value to plug in, then you get better than merely a close approximation to the theoretical output value, you have the *exact* theoretical value, right? However, the promise of classical mechanics that motion is deterministic is an empty promise because it only works for exact initial values. In practical problems using numerical computations, this is never the case. >-- >-- >Robert Black rdb@scs.carleton.ca >School of Computer Science >Carleton University, Ottawa, Canada -- Kevin McCarty kmc@netcom.COM netcom!kmc@apple.com {apple,amdahl,claris}!netcom!kmc
scavo@cie.uoregon.edu (Tom Scavo) (06/21/91)
In article <1991Jun20.194552.15875@cunews.carleton.ca> rdb@scs.carleton.ca (Robert D. Black) writes: >I recently read that the chaotic logistic equation > > u(t+1) = 4u(t)(1-u(t)) u(0) in 0..1, > t = 0,1,2,... >has an ANALYTIC SOLUTION: > > u(t) = sin**2 (2**(t-1) arccos(1-2u(0))) > > Reference "Differential Equations" by Walter G. Kelly and ^^^^^^^^^^^^ > Alan C. Peterson, Academic Press 1991, p184. A small correction: the title of the referenced book is "Difference Equations" which can be guessed by the above example. Just wanted to set the record straight... -- Tom Scavo scavo@cie.uoregon.edu
rdb@scs.carleton.ca (Robert D. Black) (06/22/91)
In article <1991Jun21.064503.8325@netcom.COM> kmc@netcom.COM (Kevin McCarty) writes: > >... Another way to look at it is that the absolute output error >roughly *doubles* with each passing unit of time... > Agreed. >Compare this with your other example, f(x) = sqrt(x)... > Bad choice of example on my part. I wasn't suggesting that sqrt has sensitivity to initial conditions. I was suggesting that IF we knew the initial condition exactly, then the only source of error in the computation would come from calculating the inverse cosine and the sine squared. That alone would not contribute very much error -- about as much error as any other common function like sqrt for example. >... However, the promise of classical mechanics that motion is >deterministic is an empty promise because it only works for >exact initial values. In practical problems using numerical >computations, this is never the case. True. My confusion was on the theoretical side. It was my impression that chaotic systems did not admit closed form solutions and were necessarily unpredictable, even in theory. I guess not! :-) Robert Black -- -- Robert Black rdb@scs.carleton.ca School of Computer Science Carleton University, Ottawa, Canada
alain@elevia.UUCP (W.A.Simon) (06/22/91)
In <1991Jun20.194552.15875@cunews.carleton.ca> rdb@scs.carleton.ca (Robert D. Black) writes: > I recently read that the chaotic logistic equation > u(t+1) = 4u(t)(1-u(t)) u(0) in 0..1, > has an ANALYTIC SOLUTION: > u(t) = sin**2 (2**(t-1) arccos(1-2u(0))) > This is CONFUSING! Wasn't it the case that solvable systems > are by definition predictable and hence not chaotic? Here you > can find the value of the system at any time t without computing > intermediate values. Yet the logistic equation above is said to be > chaotic! Would it be that your equation has just been proven to be non chaotic, or would it be that chaos-order is a continuum, and that Laplace was right? What we perceive as chaos is just a weakness in our instrumentation... or computing power. Half of a |8-) My interest in chaotic sequences is due to the belief that Poincare could be right, and therefore I could use such a sequence to generate cryptanalytically strong keys. Half of a |8-( Which brings me back to the Ulam sequences we discussed the other day (aka hailstone numbers). Are the odd/even transitions in the sequences known to contain identifiable patterns? In other words, would a string of 0's and 1's matching, respectively, even numbers and odd numbers in the sequence, be considered to be a random bit stream? > Robert Black -- William "Alain" Simon UUCP: alain@elevia.UUCP
alain@elevia.UUCP (W.A.Simon) (06/22/91)
In <1991Jun22.133638.3258@elevia.UUCP> alain@elevia.UUCP (W.A.Simon) writes: > Which brings me back to the Ulam sequences we discussed the > other day (aka hailstone numbers). Are the odd/even transitions > in the sequences known to contain identifiable patterns? In > other words, would a string of 0's and 1's matching, respectively, > even numbers and odd numbers in the sequence, be considered to be > a random bit stream? Before I get skewered on a Hilbert curve, let me rephrase this. Would the tools of statistical analysis (Chi-Square, etc...) identify that this sequence is not random ? -- William "Alain" Simon UUCP: alain@elevia.UUCP
hrubin@pop.stat.purdue.edu (Herman Rubin) (06/23/91)
In article <1991Jun22.140127.3984@elevia.UUCP>, alain@elevia.UUCP (W.A.Simon) writes: > In <1991Jun22.133638.3258@elevia.UUCP> alain@elevia.UUCP (W.A.Simon) writes: .................... > Before I get skewered on a Hilbert curve, let me rephrase > this. Would the tools of statistical analysis (Chi-Square, > etc...) identify that this sequence is not random ? If you ask whether the marginal distribution approaches the limiting one, Beta(.5,.5) for the particular example, the answer is yes. If you actually tested it using a two-sided test, you would even find the sample distribution converged too fast, but it would take quite a large sample to detect that. But if you looked at pairs, they all lie on a very simple curve, which is very obvious. The chaotic nature is that a slight difference at one point makes a big difference a considerable time in the future. -- Herman Rubin, Dept. of Statistics, Purdue Univ., West Lafayette IN47907-1399 Phone: (317)494-6054 hrubin@l.cc.purdue.edu (Internet, bitnet) {purdue,pur-ee}!l.cc!hrubin(UUCP)
scavo@cie.uoregon.edu (Tom Scavo) (06/23/91)
[Sorry if this is a repeat, but I have reason to believe it didn't get through the first time.] In article <1991Jun21.064503.8325@netcom.COM> kmc@netcom.COM (Kevin McCarty) writes: [much of an excellent article deleted] >So tell us, what happens to precision when you increment t by 1? You >*double* the argument value of the sine. In order to get an answer >with one bit of accuracy (e.g., whether the result is closer to 1.0 >than 0.0) you need one additional bit of input precision per unit time >step. Another way to look at it is that the absolute output error >roughly *doubles* with each passing unit of time. In this respect >it is no different from f(x) = 2x mod 1. Points initially close >together diverge exponentially over time. In fact, D(x) = 2x mod 1 is (semi-)conjugate to F(x) = 4x(1-x) via the two-to-one map S(x) = [sin(pi x)]^2 . I believe this is where the closed form solution to F^n(x) (where F^n is the nth iterate of F ) comes from since D^n(x) = 2^n x mod 1 . ... >Compare this with your other example, f(x) = sqrt(x) (on the unit >interval [0,1] say). Note that you need hardly any precision at all >in the initial condition in order to predict to a pretty good precision >the result of iterating f(x) a number of times. In fact, sqrt(x) has >an attracting fixed point for almost all initial values. The fixed point x = 1 attracts the orbits of ALL points in the function's domain of definition. ... >Consider three different dynamical laws described by >f(x) = sin**2( 2x ) >g(x) = (x + a) mod 1, (0 < a < 1) >h(x) = x/2 >Analyze the precision to which the n'th iterate is known, as a function >of the precision in the initial value of x and the number of iterates. >Only f(x) has chaotic behavior. Can you prove this? Can you find a conjugacy from f to some other map (like D , F , Q(x) = x^2 - 2 , or the tent map) that is known to be chaotic? The map g has quite interesting (but atypical) dynamics which I've yet to completely analyze, and of course h has the origin as a globally attracting fixed point. -- Tom Scavo scavo@cie.uoregon.edu
edgar@function.mps.ohio-state.edu (Gerald Edgar) (06/24/91)
The new issue (June-July) of the American Matheamtical Monthly has an article, "An analytical description of some simple cases of chaotic behovior" by James Whittaker. The 4 x (1-x) case is the simplest one discussed. -- Gerald A. Edgar Internet: edgar@mps.ohio-state.edu Department of Mathematics Bitnet: EDGAR@OHSTPY The Ohio State University telephone: 614-292-0395 (Office) Columbus, OH 43210 -292-4975 (Math. Dept.) -292-1479 (Dept. Fax)