Dynamical Systems and Fractals: Computer Graphics Experiments with Pascal

Dynamical systems and fractals Computer graphics experiments in Pascal

Published by the Press Syndicate of the University of Cambridge The Pitt Building, Trumpington Street, Cambridge CB2 1RP 40 West 20th Street, New York, NY lOOllL4211, USA 10 Stamford Road, Oakleigh, Melbourne 3166, Australia Originally published in German as Computergrafische Experimente mit Pascal: Chaos und Ordnung in Dynamischen Systemen by Friedr. Vieweg & Sohn, Braunschweig 1986, second edition 1988, and 0 Friedr. Vieweg & Sohn Verlagsgesellschaft mbH, Braunschweig 1986, 1988 First published in English 1989 Reprinted 1990 (three times) English translation 0 Cambridge University Press 1989 Printed in Great Britain at the University Press, Cambridge Library of Congress cataloguing in publication data available British Library cataloguing in publication data Becker, Karl-Heinze Dynamical systems and fractals 1. Mathematics. Applications of computer graphics I. Title II. Doffler, Michael III. Computergrafische Experimente mit Pascal. English 5 lo’.28566 ISBN 0 521 36025 0 hardback ISBN 0 521 3 6 9 1 0 X paperback

Dynamical systems and fractals Computer graphics experiments in Pascal Karl-Heinz Becker Michael Diirfler

Translated by Ian Stewart

CAMBRIDGE UNIVERSITY PRESS Cambridge New York Port Chester Melbourne Sydney

Contents Foreword New Directions in Computer Graphics : Experimental Mathematics Preface to the German Edition

vii xi

Researchers Discover Chaos Chaos and Dynamical Systems - What Are They? 1.1 1.2 Computer Graphics Experiments and Art

3 6

1

2

Between 2.1 2.1.1 2.1.2 2.2 2.2.1 2.2.2 2.2.3 2.3

Order and Chaos: Feigenbaum Diagrams First Experiments It’s Prettier with Graphics GraphicalIteration Fig-trees Forever Bifurcation Scenario - the Magic Number ‘Delta Attractors and Frontiers FeigenbaumLandscapes Chaos - Two Sides to the Same Coin

17 18 27 34 37 46 48 51 53

3

Strange 3.1 3.2 3.3

Attractors The Strange Attractor The Henon Attractor The Lorenz Attractor

55 56 62 64

4

Greetings 4.1 4.2 4.3

from Sir Isaac Newton’s Method Complex Is Not Complicated Carl Friedrich Gauss meets Isaac Newton

71 72 81 86

5

Complex Frontiers 5.1 Julia and His Boundaries Simple Formulas give Interesting Boundaries 5.2

91 92 108

6

Encounter with the Gingerbread Man A Superstar with Frills 6.1 Tomogram of the Gingerbread Man 6.2 Fig-tree and Gingerbread Man 6.3 Metamorphoses 6.4

127 128 145 159 167

Dynamical Systems and Fractals

vi

7

New Sights - new Insights Up Hill and Down Dale 7.1 7.2 Invert It - It’s Worth It! The World is Round 7.3 Inside Story 7.4

179 186 186 192 199

8

Fractal Computer Graphics All Kinds of Fractal Curves 8.1 Landscapes: Trees, Grass, Clouds, Mountains, and Lakes 8.2 8.3 Graftals RepetitiveDesigns 8.4

203 204 211 216 224

9

Step by Step into Chaos

231

10 Journey to the Land of Infinite Structures

247

11 Building 11.1 11.2 11.3 11.4 11.5 11.6

257 258 267 281 288 303 319

Blocks for Graphics Experiments The Fundamental Algorithms FractalsRevisited Ready, Steady, Go! The Loneliness of the Long-distance Reckoner What You See Is What You Get A Picture Takes a Trip

12 Pascal and the Fig-trees Some Are More Equal Than Others - Graphics on 12.1 Other Systems 12.2 MS-DOS and PS/2 Systems UNIX Systems 12.3 Macintosh Systems 12.4 Atari Systems 12.5 Apple II Systems 12.6 ‘Kermit Here’ - Communications 12.7

328 328 337 347 361 366 374

13 Appendices 13.1 Data for Selected Computer Graphics 13.2 Figure Index 13.3 Program Index Bibliography 13.4 13.5 Acknowledgements

379 380 383 388 391 393

Index

395

327

Foreword New Directions in Computer Graphics: Experimental Mathematics As a mathematician one is accustomed to many things. Hardly any other academics encounter as much prejudice as we do. To most people, mathematics is the most colourless of all school subjects - incomprehensible, boring, or just terribly dry. And presumably, we mathematicians must be the same, or at least somewhat strange. We deal with a subject that (as everyone knows) is actually complete. Can there still be anything left to find out? And if yes, then surely it must be totally uninteresting, or even superfluous. Thus it is for us quite unaccustomed that our work should so suddenly be confronted with so much public interest. In a way, a star has risen on the horizon of scientific knowledge, that everyone sees in their path. Experimental mathematics, a child of our ‘Computer Age’, allows us glimpses into the world of numbers that are breathtaking, not just to mathematicians. Abstract concepts, until recently known only to specialists - for example Feigenbaum diagrams or Julia sets - are becoming vivid objects, which even renew the motivation of students. Beauty and mathematics: they belong together visibly, and not just in the eyes of mathematicians. Experimental mathematics: that sounds almost like a self-contradiction! Mathematics is supposed to be founded on purely abstract, logically provable relationships. Experiments seem to have no place here. But in reality, mathematicians, by nature, have always experimented: with pencil and paper, or whatever equivalent was Even the relationship a%@=~?, well-known to all school pupils, for the available. sides of a right-angled triangle, didn’t just fall into Pythagoras’ lap out of the blue. The proof of this equation came after knowledge of many examples. The working out of examples is a‘typical part of mathematical work. Intuition develops from examples. Conjectures are formed, and perhaps afterwards a provable relationship is discerned. But it may also demonstrate that a conjecture was wrong: a single counter-example suffices. Computers and computer graphics have lent a new quality to the working out of examples. The enormous calculating power of modem computers makes it possible to study problems that could never be assaulted with pencil and paper. This results in gigantic data sets, which describe the results of the particular calculation. Computer graphics enable us to handle these data sets: they become visible. And so, we are currently gaining insights into mathematical structures of such infinite complexity that we could not even have dreamed of it until recently. Some years ago the Institute for Dynamical Systems of the University of Bremen was able to begin the installation of an extensive computer laboratory, enabling its

. ..

Vlll

Dynamical

Systems

and Fmctals

members to carry out far more complicated mathematical experiments. Complex dynamical systems are studied here; in particular mathematical models of changing or self-modifying systems that arise from physics, chemistry, or biology (planetary orbits, chemical reactions, or population development). In 1983 one of the Institute’s research groups concerned itself with so-called Julia sets. The bizarre beauty of these objects lent wings to fantasy, and suddenly was born the idea of displaying the resulting pictures as a public exhibition. Such a step down from the ‘ivory tower’ of science, is of course not easy. Nevertheless, the stone began to roll. The action group ‘Bremen and its University’, as well as the generous support of Bremen Savings Bank, ultimately made it possible: in January 1984 the exhibition Harmony in Chaos and Cosmos opened in the large bank lobby. After the hectic preparation for the exhibition, and the last-minute completion of a programme catalogue, we now thought we could dot the i’s and cross the last t’s. But something different happened: ever louder became the cry to present the results of our experiments outside Bremen, too. And so, within a few months, the almost completely new exhibition Morphology of Complex Boundan’es took shape. Its journey through many universities and German institutes began in the Max Planck Institute for Biophysical Chemistry (Gottingen) and the Max Planck Institute for Mathematics (in Bonn Savings Bank). An avalanche had broken loose. The boundaries within which we were able to present our experiments and the theory of dynamical systems became ever wider. Even in (for us) completely unaccustomed media, such as the magazine Gw on ZDF television, word was spread. Finally, even the Goethe Institute opted for a world-wide exhibition of our computer graphics. So we began a third time (which is everyone’s right, as they say in Bremen), equipped with fairly extensive experience. Graphics, which had become for us a bit too brightly coloured, were worked over once more. Naturally, the results of our latest experiments were added as well. The premiere was celebrated in May 1985 in the ‘BGttcherstrasse Gallery’. The exhibition SchSnheit im Chaos/Frontiers of Chaos has been travelling throughout the world ever since, and is constantly booked. Mostly, it is shown in natural science museums. It’s no wonder that every day we receive many enquiries about computer graphics, exhibition catalogues (which by the way were all sold out) and even programming instructions for the experiments. Naturally, one can’t answer all enquiries personally. But what are books for? The Beauty of Fractals, that is to say the book about the exhibition, became a prizewinner and the greatest success of the scientific publishing company Springer-Verlag. Experts can enlighten themselves over the technical details in The Science of Fractal Images, and with The Game of FractaJ Images lucky Macintosh II owners, even without any further knowledge, can boot up their computers and go on a journey of discovery at once. But what about all the many home computer fans, who themselves like to program, and thus would like simple, but exact. information? The book lying in front of you by Karl-Heinz Becker and Michael DGrfler fills a gap that has

Foreword

ix

too long been open. The two authors of this book became aware of our experiments in 1984, and through our exhibitions have taken wing with their own experiments. After didactic preparation they now provide, in this book, a quasi-experimental introduction to our field of research. A veritable kaleidoscope is laid out: dynamical systems are introduced, bifurcation diagrams are computed, chaos is produced, Julia sets unfold, and over it all looms the ‘Gingerbread Man’ (the nickname for the Mandelbrot set). For all of these, there are innumerable experiments, some of which enable us to create fantastic computer graphics for ourselves. Naturally, a lot of mathematical theory lies behind it all, and is needed to understand the problems in full detail. But in order to experiment oneself (even if in perhaps not quite as streetwise a fashion as a mathematician) the theory is luckily not essential. And so every home computer fan can easily enjoy the astonishing results of his or her experiments. But perhaps one or the other of these will let themselves get really curious. Now that person can be helped, for that is why it exists: the study of mathematics. But next, our research group wishes you lots of fun studying this book, and great success in your own experiments. And please, be patient: a home computer is no ‘express train’ (or, more accurately, no supercomputer). Consequently some of the experiments may tax the ‘little ones’ quite nicely. Sometimes, we also have the same problems in our computer laboratory. But we console ourselves: as always, next year there will be a newer, faster, and simultaneously cheaper computer. Maybe even for Christmas... but please with colour graphics, because then the fun really starts. Research Group in Complex Dynamics University of Bremen

Hartmut Jikgens

Preface to the German Edition Today the ‘theory of complex dynamical systems’ is often referred to as a revolution, illuminating all of science. Computer-graphical methods and experiments today define the methodology of a new branch of mathematics: ‘experimental mathematics’. Its content is above all the theory of complex dynamical systems. ‘Experimental’ here refers primarily to computers and computer graphics. In contrast to the experiments are ‘mathematical cross-connections’, analysed with the aid of computers, whose examples were discovered using computer-graphical methods. The mysterious structure of these computer graphics conceals secrets which still remain unknown, and lie at the frontiers of thought in several areas of science. If what we now know amounts to a revolution, then we must expect further revolutions to occur. . The groundwork must therefore be prepared, and . people must be found who can communicate the new knowledge. We believe that the current favourable research situation has been created by the growing power and cheapness of computers. More and more they are being used as research tools. But science’s achievement has always been to do what can be done. Here we should mention the name of Benoi§t B. Mandelbrot, a scientific outsider who worked for many years to develop the fundamental mathematical concept of a fractal and to bring it to life. Other research teams have developed special graphical techniques. At the University of Bremen fruitful interaction of mathematicians and physicists has led to results which have been presented to a wide public. In this context the unprecedented popular writings of the group working under Professors Heinz-Otto Peitgen and Peter H. Richter must be mentioned. They brought computer graphics to an interested public in many fantastic exhibitions. The questions formulated were explained non-technically in the accompanying programmes and exhibition catalogues and were thus made accessible to laymen. They recognised a further challenge, to emerge from the ‘Ivory Tower’ of science, so that scientific reports and congresses were arranged not only in the university. More broadly, the research group presented its results in the magazine Geo, on ZDF television programmes, and in worldwide exhibitions arranged by the Goethe Institute. We know of no other instance where the bridge from the foremost frontier of research to a wide lay public has been built in such a short time. In our own way we hope to extend that effort in this book. We hope, while dealing with the discoveries of the research group, to open for many readers the path to their own experiments. Perhaps in this way we can lead them towards a deeper understanding of the problems connected with mathematical feedback. Our book is intended for everyone who has a computer system at their disposal and who enjoys experimenting with computer graphics. The necessary mathematical formulas are so simple that they can easily be understood or used in simple ways. The reader will rapidly be brought into contact with a frontier of today’s scientific research, in which

Xii

Dynamical Systems and Fractals

hardly any insight would be possible without the use of computer systems and graphical data processing. This book divides into two main parts. In the first part (Chapters 1 -lo), the reader is introduced to interesting problems and sometimes a solution in the form of a program fragment. A large number of exercises lead to individual experimental work and independent study. The fist part closes with a survey of ‘possible’ applications of this new theory. In the second part (from Chapter 11 onwards) the modular concept of our program fragments is introduced in connection with selected problem solutions. In particular, readers who have never before worked with Pascal will find in Chapter 11 - and indeed throughout the entire book - a great number of program fragments, with whose aid independent computer experimentation can be carried out. Chapter 12 provides reference programs and special tips for dealing with graphics in different operating systems and programming languages. The contents apply to MS-DOS systems with Turbo Pascal and UNIX 4.2 BSD systems, with hints on Berkeley Pascal and C. Further example programs, which show how the graphics routines fit together, are given for Macintosh systems (Turbo Pascal, Lightspeed Pascal, Lightspeed C), the Atari (ST Pascal Plus), the Apple IIe (UCSD Pascal), and the Apple IIGS (TML Pascal). We are grateful to the Bremen research group and the Vieweg Company for extensive advice and assistance. And, not least, to our readers. Your letters and hints have convinced us to rewrite the fist edition so much that the result is virtually a new book - which, we hope, is more beautiful, better, more detailed, and has many new ideas for computer graphics experiments. Bremen

Karl-Heinz Becker

Michael Dbffler

1 Researchers Discover Chaos

2

Dynamical Systems and Fractals

The story which today so fascinates researchers, and which is associated with chaos theory and experimental mathematics, came to our attention around 1983 in Bremen. A t that time a research group in dynamical systems under the leadership of Professors Peitgen and Richter was founded at Bremen University. This starting-point led to a collaboration lasting many years with members of the Computer Graphics Laboratory at the University of Utah in the USA. Equipped with a variety of research expertise, the research group began to install its own computer graphics laboratory. In January and February of 1984 they made their results public. These results were startling and caused a great sensation. For what they exhibited was beautiful, coloured computer graphics reminiscent of artistic paintings. The first exhibition, Harmony in Chaos and Cosmos, was followed by the exhibition Moqhology of Complex Frontiers. With the next exhibition the results became internationally known. In 1985 and 1986, under the title Frontiers of Chaos and with assistance from the Goethe Institute, this third exhibition was shown in the UK and the USA. Since then the computer graphics have appeared in many magazines and on television, a witches’ brew of computer-graphic simulations of dynamical systems. What is so stimulating about it? Why did these pictures cause so great a sensation? We think that these new directions in research are fascinating on several grounds. It seems that we are observing a ’ celestial conjunction’ - a conjunction as brilliant as that which occurs when Jupiter and Saturn pass close together in the sky, something that happens only once a century. Similar events have happened from time to time in the history of science. When new theories overturn or change previous knowledge, we. speak of a paradigm change. 1 The implications of such a paradigm change are influenced by science and society. We think that may also be the case here. At any rate, from the scientific viewpoint, this much is clear: . A new theory, the so-called chaos theory, has shattered the scientific worldview. We will discuss it shortly. . New techniques are changing the traditional methods of work of mathematics and lead to the concept of experimental mathematics. For centuries mathematicians have stuck to their traditional tools and methods such as paper, pen, and simple calculating machines, so that the typical means of progress in mathematics have been proofs and logical deductions. Now for the first time some mathematicians are working like engineers and physicists. The mathematical problem under investigation is planned and carried out like an experiment. The experimental apparatus for this investigatory mathematics is the computer. Without it, research in this field would be impossible. The mathematical processes that we wish to understand are ‘Paradigm = ‘example’. By a paradigm we mean a basic Point of view, a fundamental unstated assumption, a dogma, through which scientists direct their investigations.

Discovering Chaos

3

visual&d in the form of computer graphics. From the graphics we draw conclusions about the mathematics. The outcome is changed and improved, the experiment carried out with the new data. And the cycle starts anew. . Two previously separate disciplines, mathematics and computer graphics, are growing together to create something qualitatively new. Even here a further connection with the experimental method of the physicist can be seen. In physics, bubble-chambers and semiconductor detectors are instruments for visualising the microscopically small processes of nuclear physics. Thus these processes become representable and accessible to experience. Computer graphics, in the area of dynamical systems, are similar to bubble-chamber photographs, making dynamical processes visible. Above all, this direction of research seems to us to have social significance: . The ‘ivory tower’ of science is becoming transparent. In this connection you must realise that the research group is interdisciplinary. Mathematicians and physicists work together, to uncover the mysteries of this new discipline. In our experience it has seldom previously been the case that scientists have emerged from their own ‘closed’ realm of thought, and made their research results known to a broad lay public. That occurs typically here. l These computer graphics, the results of mathematical research, are very surprising and have once more raised the question of what ‘art’ really is. Are these computer graphics to become a symbol of our ‘hi-tech’ age? b For the first time in the history of science the distance between the utmost frontiers of research, and what can be understood by the ‘man in the street’, has become vanishingly small. Normally the distance between mathematical research, and what is taught in schools, is almost infinitely large. But here the concerns of a part of today’s mathematical research can be made transparent. That has not been possible for a long time. Anyone can join in the main events of this new research area, and come to a basic understanding of mathematics. The central figure in the theory of dynamical systems, the Mandelbrot set - the so-called ‘Gingerbread Man’ - was discovered only in 1980. Today, virtually anyone who owns a computer can generate this computer graphic for themselves, and investigate how its hidden structures unravel.

1 .l Chaos and Dynamical Systems - What Are They? An old farmer’s saying runs like this: ‘When the cock crows on the dungheap, the weather will either change, or stay as it is.’ Everyone can be 100 per cent correct with this weather forecast. We obtain a success rate of 60 per cent if we use the rule that tomorrow’s weather will be the same as today’s. Despite satellite photos, worldwide measuring networks for weather data, and supercomputers, the success rate of computer-generated predictions stands no higher than 80 per cent. Why is it not better?

4

Dynamical

Systems and Ftactals

Why does the computer - the very incarnation of exactitude - find its limitations here? Let us take a look at how meteorologists, with the aid of computers, make their predictions. The assumptions of the meteorologist are based on the causality principle. This states that equal causes produce equal effects - which nobody would seriously doubt. Therefore the knowledge of all weather data must make an exact prediction Of course this cannot be achieved in practice, because we cannot set up possible. measuring stations for collecting weather data in an arbitrarily large number of places. For this reason the meteorologists appeal to the strong causality principle, which holds that similar causes produce similar effects. In recent decades theoretical models for the changes in weather have been derived from this assumption.

Data: Air-pressure Temperature Cloud-cover Wind-direction Wind-speed

Parameters: Time of year Vegetation Snow Sunshine

Innut

Mathematical formulas

- I 1 1 represZt~ Situation at 12.00

~~atkZaviour

i

piii5

for 06.00 Figure 1.1-i Feedback cycle of weather research. Such models, in the form of complicated mathematical equations, are calculated with the aid of the computer and used for weather prediction. In practice weather data from the worldwide network of measuring stations, such as pressure, temperature, wind direction, and many other quantities, are entered into the computer system, which calculates the resulting weather with the aid of the underlying model. For example, in principle the method for predicting weather 6 hours ahead is illustrated in Figure 1.1-l. The 24hour forecast can easily be obtained, by feeding the data for the l&hour computation back into the model. In other words, the computer system generates output data with the aid of the weather forecasting program. The data thus obtained are fed back in again as input data. They produce new output data, which can again be treated as input data. The data are thus repeatedly fed back into the program.

Discovering

Chaos

5

One might imagine that the results thus obtained become ever more accurate. The opposite can often be the case. The computed weather forecast, which for several days has matched the weather very well, can on the following day lead to a catastrophically false prognosis. Even if the ‘model system weather’ gets into a ‘harmonious’ relation to the predictions, it can sometimes appear to behave ‘chaotically’. The stability of the computed weather forecast is severely over-estimated, if the weather can change in unpredictable ways. For meteorologists, no more stability or order is detectable in such behaviour. The model system ‘weather’ breaks down in apparent disorder, in ‘chaos’. This phenomenon of unpredictablity is characteristic of complex systems. In the transition from ‘harmony’ (predictability) into ‘chaos’ (unpredictability) is concealed the secret for understanding both concepts. The concepts ‘chaos’ and ‘chaos theory’ are ambiguous. At the moment we agree to speak of chaos only when ‘predictability breaks down’. As with the weather (whose correct prediction we classify as an ‘ordered’ result), we describe the meteorologists often unfairly - as ‘chaotic’, when yet again they get it wrong. Such concepts as ‘order’ and ‘chaos’ must remain unclear at the start of our investigation. To understand them we will soon carry out our own experiments. For this purpose we must clarify the many-sided concept of a dynamical system. In general by a system we understand a collection of elements and their effects on each other. That seems rather abstract. But in fact we are surrounded by systems. The weather, a wood, the global economy, a crowd of people in a football stadium, biological populations such as the totality of all fish in a pond, a nuclear power station: these are all systems, whose ‘behaviour’ can change very rapidly. The elements of the dynamical system ‘football stadium’, for example, are people: their relations with each other can be very different and of a multifaceted kind. Real systems signal their presence through three factors: l They are dynamic, that is, subject to lasting changes. l They are complex, that is, depend on many parameters. . They are iterative, that is, the laws that govern their behaviour can be described by feedback. Today nobody can completely describe the interactions of such a system through mathematical formulas, nor predict the behaviour of people in a football stadium. Despite this, scientists try to investigate the regularities that form the basis of such dynamical systems. In particular one exercise is to find simple mathematical models, with whose help one can simulate the behaviour of such a system. We can represent this in schematic form as in Figure 1.1-2. Of course in a system such as the weather, the transition from order to chaos is hard to predict. The cause of ‘chaotic’ behaviour is based on the fact that negligible changes to quantities that are coupled by feedback can produce unexpected chaotic effects. This is an apparently astonishing phenomenon, which scientists of many disciplines have studied with great excitement. It applies in particular to a range of problems that might bring into question recognised theories or stimulate new formulations, in biology, physics,

Dynamical Systems

6

and

Fractals

chemistry and mathematics, and also in economic areas. The research area of dynamical systems theory is manifestly interdisciplinary. The theory that causes this excitement is still quite young and - initially - so simple mathematically that anyone who has a computer system and can carry out elementary programming tasks can appreciate its startling results.

Possible Parameters

Initial Value

Specification of a process

I, R e s u l t

Feedback Figure 1.1-2 General feedback scheme. The aim of chaos research is to understand in general how the transition from order to chaos takes place. An important possibility for investigating the sensitivity of chaotic systems is to represent their behaviour by computer graphics. Above all, graphical representation of the results and independent experimentation has considerable aesthetic appeal, and is exciting. In the following chapters we will introduce you to such experiments with different dynamical systems and their graphical representation. At the same time we will give you - a bit at a time - a vivid introduction to the conceptual world of this new research area.

1.2 Computer Graphics Experiments and Art In their work, scientists distinguish two important phases. In the ideal case they alternate between experimental and theoretical phases. When scientists carry out an experiment, they pose a particular question to Nature. As a rule they offer a definite point of departure: this might be a chemical substance or a piece of technical apparatus, with which the experiment should be performed. They look for theoretical interpretations of the answers, which they mostly obtain by making measurements with their instruments. For mathematicians, this procedure is relatively new. In their case the apparatus or

Discovering

Chaos

7

measuring instrument is a computer. The questions are presented as formulas, representing a series of steps in an investigation. The results of measurement are numbers, which must be interpreted. To be able to grasp this multitude of numbers, they must be represented clearly. Often graphical methods are used to achieve this. Barcharts and pie-charts, as well as coordinate systems with curves, are widespread examples. In most cases not only is a picture ‘worth a thousand words’: the picture is perhaps the only way to show the precise state of affairs. Over the last few years experimental mathematics has become an exciting area, not just for professional researchers, but for the interested layman. With the availability of efficient personal computers, anyone can explore the new territory for himself. The results of such computer graphics experiments are not just very attractive visually - in general they have never been produced by anyone else before. In this book we will provide programs to make the different questions from this area of mathematics accessible. At first we will give the programs at full length; but later - following the building-block principle - we shall give only the new parts that have not occurred repeatedly. Before we clarify the connection between experimental mathematics and computer graphics, we will show you some of these computer graphics. Soon you will be producing these, or similar, graphics for yourself. Whether they can be described as computer art you must decide for yourself.

Figure 1.2-l Rough Diamond.

Dynamical Systems and

Figure 1.2-2

Vulcan’s Eye.

l%ctah

Discovering Chaos

Figure 1.2-3 Gingerbread Man.

10

Dynamical Systems and Fractals

Figure 1.2-4 Tornado Convention.2

2Tbis picture was christened by Prof. K. Kenkel of Dartmouth College.

Discovering

Chaos

Figure 1.2-5 Quadruple Alliance.

I&*

Figure 1.2-6 Seahorse Roundelay.

Discovering

Chaos

Figure 1.2-7 Julia Propeller.

14

Dynamical

Figure 1.2-8 Variation 1.

Figure 1.2-9 Variation 2.

Systems and Fractals

15

Discovering Chaos

Figure 1.2-10 Variation 3.

Figure 1.2- 11

Explosion.

16

Figure 1.2-12

Dynamical Systems and Fractals

Mach 10.

Computer graphics in, computer art out. In the next chapter we will explain the relation between experimental mathematics and computer graphics. We will generate our own graphics and experiment for ourselves.

2 Between Order and Chaos: Feigenbaum Diagrams

18

2.1

Dynamical Systems and Fractals

First

Experiments

One of the most exciting experiments, in which we all take part, is one which Nature carries out upon us. This experiment is called life. The rules am the presumed laws of Nature, the materials are chemical compounds, and the results are extremely varied and surprising. And something else is worth noting: if we view the ingredients and the product as equals, then each year (each day, each generation) begins with exactly what the previous year (day, generation) has left as the starting-point for the next stage. That development is possible in such circumstances is something we observe every day. If we translate the above experiment into a mathematical one, then this is what we get: a fixed rule, which transforms input into output; that is, a rule for calculating the output by applying it to the input. The result is the input value for the second stage, whose result becomes the input for the third stage, and so on. This mathematical principle of re-inserting a result into its own method of computation is called feedback (see Chapter 1). We will show by a simple example that such feedback is not only easy to program, but it leads to surprising results. Like any good experiment, it raises ten times as many new questions as it answers. The rules that will concern us are mathematical formulas. The values that we obtain will be real numbers between 0 and 1. One possible meaning for numbers between 0 and 1 is as percentages: 0% I p I 100%. Many of the rules that we describe in this book arise only from the mathematician’s imagination. The rule described here originated when researchers tried to apply mathematical methods to growth, employing an interesting and widespread model. We will use the following as an example, taking care to remember that not everything in the model is completely realistic. There has been an outbreak of measles in a children’s home. Every day the number of sick children is recorded, because it is impossible to avoid sick and well children coming into contact with each other. How does the number change? This problem corresponds to a typical dynamical system - naturally a very simple one. We will develop a mathematical model for it, which we can use to simulate an epidemic process, to understand the behaviour and regularities of such a system. If, for example, 30% of the children are already sick, we represent this fact by the formula p = 0.3. The question arises, how many children will become ill the next day? The rule that describes the spread of disease is denoted mathematically by gP). The epidemic can then be described by the following equation: fc.Pl = P+z. That is, to the original p we add a growth z. The value of z, the increase in the number of sick children, depends on the number p of children who are already sick. Mathematically we can write this dependence as z= p, saying that ‘z is proportional to p’. By this proportionality expression we mean that z may depend upon other quantities than p. We can predict that z depends also upon the number of well children, because there can be no increase if all the children

Between Order and Chaos: Feigenbaum Diagrams

19

are already sick in bed. If 30% are ill, then there must be 100% - 30% = 70% who are well. In general there will be 100%-p = 1 -p well children, so we also have z = (l-p). We have thus decided that z = p and z = (l-p). Combining these, we get a growth term z = p*( 1 -p). But because not all children meet each other, and not every contact leads to an infection, we should include in the formula an infection rate k. Putting all this together into a single formula we find that: z = k*p*(l-p), so that fly) = pt-k*p*(I-P).

In our investigation we will apply this formula on many successive days. In order to distinguish the numbers for a given day, we will attach an index top. The initial value is po, after one day we have ~1, and so on. The result gp> becomes the initial value for the next stage, so we get the following scheme: 00) = po+k*pg*(l-pg) = PI tip11 = pl+k*pl*(l-pi) = ~2

II&) = fi+k*pz*(l-pi)

=B

f-W = n+k*p3*(l-m)

= ~4

and so on. In general we have KP,,) = pn+k*pn*(l

-P,J = pn+1.

Parameter k

or p. = 0.3 + p n+l = Pn+k*Pn* C1 -Pn> + Table Graphic

Feedback Figure 2.1-1 Feedback scheme for ‘Measles’. In other words this means nothing more than that the new values are computed from the old ones by applying the given rule. This process is called mathematical feedback or iteration. We have already spoken of this iterative procedure in our fundamental considerations in Chapter 1. For any particular fixed value of k we can calculate the development of the disease from a given starting value po. Using a pocket calculator, or mental arithmetic, we find that these function values more or less quickly approach the limit I; that is, all children fall sick. We would naturally expect this to occur faster, the larger the factor k is.

Dynamical Systems

and

Fractals

Figure 2.1-2 Development of the disease for po = 0.3 and k = 0.5.

Figure 2.1-3 Development of the disease for po = 0.3 and k = 1 .O. In order to get a feeling for the method of calculation, get out your pocket calculator. Work out the results first yourself, for the k-values k, = 0.5, k2 = 1, k3 = 1.5, k4 = 2, k5 = 2.5, k = 3 using the formula f&,1 = p,,+k*p,,*(l-pd = P,,+I to work out pt up to ~5. Take po = 0.3 in each case. So that you can check your results, we have given the calculation in the form of six tables (see Figures 2.1-2 to 2.1-7). In each table ten values per column are shown. In column A are the values pi, in CO~UIWI E the values pi+l.

Between

Order and Chaos: Feigenbaum Diagrams

Figure 2.1-4 Development of the disease for po = 0.3 and k = 1.5.

Figure 2.1-5 Development of the disease for po = 0.3 and k = 2.0.

Figure 2.1-6 Development of the disease for po = 0.3 and k = 2.5.

21

22

Dynamical Systems and Fmctals

Figure 2.1-7

Development of the disease for po = 0.3 and k = 3.0.

The tables were computed using the spreadsheet program ‘Excel’ on a Macintosh. Other spreadsheets, for example ‘Multiplan’, can also be used for this kind of investigation. For those interested, the program is given in Figure 2.1-8, together with the linking formulas. All diagrams involve the mathematical feedback process. The result of field E2 provides the starting value for A3, the result of E3 is the initial value for A4, and so on.

. ..................../.. .. .. . . . . . . . . . .. . . . . . . . . i .F..U . . . . . . . . . . . . . . . . . . . . . . . . k.87 . . . . . . . . . . . . . . . . . . . . . . . . . . l.:!..2!8 . . . . . . . . . . . . . . . . . . . . . . 2TtM!.~!.8.~~.8 . . . . . . . . . . . . . i.:Pl!.+.r .%8 . .. .. . . ... .. . . . . ... . .. .. . I.?!! . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.:.!..:A@. . . . . . . . . . . . . . . . . . . . . j.?.E?.“AS”C? . . . . . . . . . . . . . . $???D? i=l-AlO i=BlO*AlO*ClO i=AlO+DlO

Figure 2.1-8 List of formulas. Now represent your calculations graphically. You have six individual calculations to deal with. Each diagram, in a suitable coordinate system, contains a number of points generated by feedback.

Between Order and Chaos: Feigenbaum Diagrams

23

I

P 4

: I

. .

.! . . . . .

I.

.

i .

.

.

. *

I

0.5

I

1.0

.

I

I

1.5

2.0

I I

. .

215

3.0

I

-k

Figure 2.1-9 Discrete series of 6 (ki , p;)-values after 10 iterations. We can combine all six diagrams into one, where for each kj -value (kj = 0.5, 1.0, 1.5, 2.0,2.5, 3.0) we show the corresponding pi -values (Figure 2.1-g). You must have noticed how laborious all this is. Further, very little can be deduced from this picture. To gain an understanding of this dynamical system, it is not sufficient to carry out the feedback process for just 6 k-values. We must do more: for each kj -value 0 I kj < 3 that can be distinguished in the picture, we must run continuously through the entire range of the k-axis, and draw in the corresponding p-values.

That is a tolerably heavy computation. No wonder that it took until the middle of this century before even such simple formulas were studied, with the help of newfangled computers. A computer will also help us investigate the ‘measles problem’. It carries out the same tedious, stupid calculation over and over again, always using the same formula. When we go on to write a program in Pascal, it will be useful for more than just this problem. We construct it so that we can use large parts of it in other problems. N e w programs will be developed from this one, in which parts are inserted or removed. W e just have to make sure that they fit together properly (see Chapter 11). For this problem we have developed a Pascal program, in which only the main part of the problem is solved. Any of you who cannot finish the present problem, given the program, will find a complete solution in Chapters 1 lff. Program 2.1-1 PROGRAM MeaslesNumber; VAR Population, Feedback

:

real;

DynamicalSystemsandFractals

24

MaximalIteration : integer; (*----------------------------------------------------*) procedures *) BEGIN : Problem-specific (" FUNCTION f (p, k : real) : real; BEGIN f:=p+k*p*(l-p); END; PROCEDURE MeaslesValue; VAR i : integer; BEGIN DO FOR i := 1 to MaximalIteration BEGIN Population := f(Population, Feedback); writeln('After' , i , 'Iterations p has the value :I, Population : 6 : 4); END; END; (* END Problem-specific procedures *) --------------------*) (X ____--___-----_-----~~~~~~~--(* BEGIN: Useful subroutines *) (* see Chapter 11.2 *) : Useful subroutines *) c* END (*

BEGIN : Procedures of main program *) PROCEDURE Hello; BEGIN InfoOutput ('Calculation of Measles-Values'); Infooutput ('---------------------------I) ; Newlines CarryOn Newlines E-NJ;

(2); ('Start : '); (2);

PROCEDURE Application; BEGIN ReadReal ('Initial Population p (0 to 1) >I, Population); ReadReal ('Feedback Parameter k (0 to 3) >I,

Between Order and Chaos: Feigenbaurn

Diagrams

25

Feedback); ReadInteger ('Max. Iteration Number >', MaximalIteration); END; PROCEDURE ComputeAndDisplay; BEGIN MeaslesValues; END; PROCEDURE Goodbye; BEGIN CarryOn ('To stop : '); END; (* END : Procedures of Main Program)

BEGIN (* Main Program *) Hello; Application; ComputeAndDisplay; Goodbye; END. We have here written out only the main part of the program. The ‘useful subroutines’ are particular procedures to read in numbers or to output text to the screen (see Chapters 1 Iff.). When we type in this Pascal program and run it, it gives an output like Figure 2.1-10. In Figure 2.1-10 not all iterations are shown. In particular the interesting values are missing. You should now experiment yourself: we invite you to do so before reading on. Only in this way can you appreciate blow by blow the world of computer simulation. We have now built our first measuring instrument, and we can use it to make systematic investigations. What we have previously accomplished with tedious computations on a pocket calculator, have listed in tables, and drawn graphically (Figure 2.1-9) can now be done much more easily. We can carry out the calculations on a We recommend that you now go to your computer and do some computer. experimenting with Pascal program 2. l- 1. A final word about our ‘measuring instrument’. The basic structure of the program, the main program, will not be changed much. It is a kind of standard tool, which we always construct. The useful subroutines are like machine parts or building blocks,

26

Dynamical Systems and Fracrals

which we can use in future, without worrying further. For those of you who do not feel so sure of yourselves we have an additional offer: complete tested programs and parts of programs. These are systematically collected together in Chapter 11. Initial Population p (0 to 1) Feedback Parameter k (0 to 3) Max. Iteration No.

>0.5 >2.3 >20

After1 Iterations p has the value : 1.0750 After2 Iterations p has the value : 0.8896 After3 Iterations p has the value : 1.1155 Afiter4 Iterations p has the value : 0.8191 After5 Iterations p has the value : 1.1599 AfTer6 Iterations p has the value : 0.7334 AfIter7 Iterations p has the value : 1.1831 AfYzer8 Iterations p has the value : 0.6848 Af'ter 9 Iterations p has the value : 1.1813 Afiter 10 Iterations p has the value : 0.6888 Afiterll Iterations p has the value : 1.1818 After12 Iterations p has the value : 0.6876 Afiter13 Iterations p has the value : 1.1817 After14 Iterations p has the value : 0.6880 After15 Iterations p has the value : 1.1817 After16 Iterations p has the value : 0.6879 Afiter17 Iterations p has the value : 1.1817 AfTer18 Iterations p has the value : 1.6879 Afiter19 Iterations p has the value : 1.1817 AfYer20 Iterations p has the value : 0.6879 Figure 2.1- 10

Calculation

of

measles

values.

Computer Graphics Experiments and Exercises for $2.1 Exercise 2.1.-l Implement the measles formula using a spreadsheet program. Generate similar tables to those shown in Figures 2.1- 1 to 2.1-7. Check your values against the tables. Exercise 2.1-2 Implement Program 2.1-1 on your computer. Carry out 30 iterations with 6 data sets. For a fixed initial value po = 0.3 let k take values from 0 to 3 in steps of 0.5.

Between Order and Chaos: Feigenbaum Diagrams

27

Exercise 2.1-3 Now experiment with other initial values of p, vary k, etc. Once you’ve got the program Meas 1esNumber running, you have your fist measuring instrument. Find out for which values of k and which initial values of p the resulting series of p-values is (a) simple (convergence top = I), (b) interesting, and (c) dangerous. We call a series ’ dangerous’ when the values get larger and larger - so the danger is that they exceed what the computer can handle. For many implementations of Pascal the following range of values is not dangerous: lo-37 < I x I < 1038 for numbers x of type real. By the interesting range of k we mean the interval from k = 1.8 to k= 3.0. Above this range it is dangerous; below, it is boring. Exercise 2.14 Now that we have delineated the boundaries of the k-regions, we can present the above results acoustically. To do this you must change the program a little. Rewrite Program 2.1- 1 so that the series of numerical values becomes audible as a series of musical tones. Exercise 2.1-S What do you observe as a result of your experiments?

2.1.1 It’s Prettier with Graphics It can definitely happen that for some k-values no regularity can be seen in the series of numbers produced: the p-values seem to bc more or less disordered. The experiment of Exercise 2.1-4 yields a regular occurrence of similar tone sequences only for certain values of p and k. So we will now make the computer sketch the results of our experiments, because we cannot find our way about this ‘numerical salad’ in any other manner. To do that we must first solve the problem of relating a Cartesian coordinate system with coordinates x,y or k,p to the screen coordinates. Consider Figure 2.1.1-1 below. Our graphical representations must be transformed in such a way that they can all be drawn on the same screen. In the jargon of computer graphics we refer to our mathematical coordinate system as the universal cuordinate system. With the aid of a transformation equation we can convert the universal coordinates into screen coordinates. Figure 2.1.1-I shows the general case, in which we wish to map a window, or rectangular section of the screen, onto a projection surface, representing part of the screen. The capital letter Urepresents the universal coordinate system, and S the screen

Dynamical Systems and Fractals

28

‘YT--

SYT --

‘YB-IX

I

U xR

UXL

%B--

Projection Screen

surface SxR

Figure 2.1.1-1 Two coordinate systems. coordinate system. The following transformation equations hold: %R-%L

xs = u

XR

_ u (xu-UXL) + SXL 9 XL

syT-syB

ys = u

-u

YT

(~u-Uy~)+sy~

YB

Here L, R, B, T are the initials of ‘left’, ‘right’, ‘bottom’, ‘top’. We want to express the transformation equation as simply as possible. To do this, we assume that we wish to map the window onto the entire screen. Then we can make the following definitions: . ,$,T’ Yscreen and UyT= Top . s,B = 0 U$= Bottom and . s,= 0 Uti=Left a n d + Sfi = Xscreen. and U,= Right This simplifies the transformation equation: xs = $;;yft (x,-l-m

Y screen (yu-Bottom) ys = Top-Bottom

.

On the basis of this formula we will write a program that is suitable for displaying the

Between Order and Chaos: Feigenbanm Diagrams

measles values. Observe its similar structure to that of Program 2.1- 1. Program 2.1.1-1 PROGRAM MeaslesGraphic; (* Possible declaration of graphics library *) (* Insert in a suitable place *) CONST Xscreen = 320; (* e.g. 320 pixels in x-direction *) Yscreen = 200; (* e.g. 200 pixels in y-direction *) VAR Left, Right, Top, Bottom, Feedback : real; IterationNo : Integer; (* BEGIN: Graphics Procedures *) PROCEDURE SetPoint (xs, ys : integer); BEGIN (* Insert machine-specific graphics commands here*) m; PROCEDURE SetUniversalPoint (xu, yu: real); VAR xs, ys : real; BEGIN xs := (xu - Left) * Xscreen / (Right - Left); YS := (yu - Bottom) * Yscreen / (Top - Bottom); SetPoint (round(xs), round(ys)); END; PROCEDURE TextMode; BEGIN (* Insert machine-specific commands: see hints *) (* in Chapter 11 *) END; PROCEDURE GraphicsMode; BEGIN (* Insert machine-specific commands: see hints (* Chapter 11 *) END; PROCEDURE EnterGraphics; (* various actions to initia lise the graph its *) (* such as GraphicsMode etc. GraphicsMode;

*) in

*)

30

Dynamical Systems and Fmctals

END;

PROCEDURE ExitGraphics; BEGIN (* Actions to end the graphics, e.g. : *) REPEAT (* Button is a machine-specific procedure *) UNTIL Button; TextMode; m; (* END: Graphics Procedures *) (*

____________-----------------------------------------

(* BEGIN : Problem-specific Procedures FUNCTION f (p, k : real) : real; BEGIN f:=p+k*p* (l-p); END;

*)

PROCE:DURE MeaslesIteration; VAR range, i: integer population : real deltaxPerPixe1: real; BEGIN deltaxPerPixe1 := (Right - Left) / Xscreen; FOR range := 0 TO Xscreen DO BEGIN Feedback := Left + range * deltaxPerPixe1; population := 0.3 FOR i := 0 to IterationNo DO BEGIN SetUniversalPoint (Feedback, population); population := f ( population, Feedback ); END; END; END; (* END: Problem-specific Procedures *) (*---------------------------------------------------*)

(* (* (* (*

BEGIN Useful Subroutines *) See Program 2.1-1, not given here *) END : Useful Subroutines *) BEGIN: Procedures of Main Program *)

“)

31

Between Order and Chaos: Feigenbaum Diagrams

PROCEDURE Hello; BEGIN TextMode; InfoOutput ('Diagram of the Measles Problem'); Infooutput ('-----------------------------I); Newlines CarryOn Newlines END;

(2); ('Start : '); (2);

PROCEDURE Initialise; BEGIN ReadReal ('Left ReadReal ('Right ReadReal ('Top ReadReal ('Bottom ReadInteger (Iteration Number END:

>'r >'r >'r 'I, >'r

Left); Right); Top); Bottom); IterationNo);

PROCEDURE ComputeAndDisplay; BEGIN EnterGraphics; MeaslesIteration; ExitGraphics; END; PROCEDURE Goodbye; BEGIN CarryOn ('To end : '); END (*END : Procedures of Main Program *) BEGIN (* Main Program *) Hello; Initialise; ComputeAndDisplay; Goodbye; END. We suggest that you now formulate Program 2.1.1- 1 as a complete Pascal program and enter it into your machine. The description above may help, but you may have developed your own programming style, in which case you can do everything differently if you

32

Dynamical Systems and Fmctals

wish. Basically Program 2.1.1-l solves the ‘algorithmic heart’ of the problem. The machine-specific components are discussed in Chapter 12 in the form of reference programs with the appropriate graphics commands included. TextMode, GraphicsMode, and Button are machine-specific procedures. In implementations,TextMode and GraphicsMode are system procedures. This is the case for Turbo Pascal on MS-DOS machines and for UCSD Pascal (see Chapter 12). Button corresponds to the Keypressed function of Turbo Pascal. The ‘useful subroutines’ have already been described in Program 2.2-l. By comparing Programs 2.1-I and 2.1 .I -1 you will see that we have converted our original ‘numerical’ measuring-instrument into a ‘graphical’ one. Now we can visualise the number flow more easily. The development of the program mostly concerns the graphics: the basic structure remains unchanged. Something new, which we must clarify, occurs in the procedure MeaslesIteration (see Program2.1.1-1): deltaxPerPixe1 := (Right - Left) / Xscreen; FOR range := 0 TO Xscreen DO BEGIN Feedback := Left + range * deltaxPerPixe1; ... Compare this with the transformation formula: xs = P-J;;;e,nft(xu-Left) Solve this equation for x9 When we give the screen coordinate xs the value 0, then the universal coordinate must becomeLeft. Setting the value Xscreen for the maximal screen coordinate x, we get the value Right. Every other screen coordinate corresponds to a universal CoordinatebetweenLeft and Right. The smallest unit of size that can be distinguished on the screen is one pixel. The corresponding smallest unit of size in universal coordinatesis thusdeltaxPerPixel. After this brief explanation of the graphical representations of the measles data with the aid of Program 2.1.1-1, we will describe the result, produced by the computer program in the form of a graphic. See Figure 2.1.1-2, to which we have added the coordinate axes. How do we interpret this graphic? From right to left the factor k changes in the range 0 to 3. For small values of k (in particular k = 0) the value of p changes by little or nothing. For k-values in the region of 1 we see the expected result: p takes the value 1 and no further changes occur. The interpretation for the model is thus: if the infection rate k is sufficiently large, then soon all children become ill (p = 100%). This occurs more rapidly, the larger k is.

33

Between Order and Chaos: Feigenbaum Diagrams

P

3.0

Figure 2.1.1-2 Representation of the measles epidemic on the screen, IterationNo= 10. You can also see this result using the values computed by pocket calculator, e.g. Figures 2.1-1 to 2.1-7. For k-values greater than 1 something surprising and unexpected happens: p can become larger than I! Mathematically, that’s still meaningful. Using the formula you can check that the calculation has proceeded correctly. Unfortunately it illustrates a restriction on our measles example, because more than 100% of the children cannot become ill. The picture shows quite different results here. Might something abnormal be going on? Here we find ourselves in a typical experimental situation: the experiment has to some extent confirmed our expectations, but has also led to unexpected results. That suggests new questions, which possess their own momentum. Even though we can’t make sense of the statement that ‘more than 100% of children become sick’, the following question starts to look interesting: how does p behave, if k gets bigger than 2? Figure 2.1.1-2 provides a hint: p certainly does not, as previously, tend to the constant value p = 1. Apparently there is no fixed value which p approaches, or, as mathematicians say, towards which the sequence p converges. It is also worth noting that the sequence does not diverge either. Then p would increase beyond all bounds and tend towards +co or -03. In fact the values of p jump about ‘chaotically’, to and fro, in a range of p between p = 0 and p = 1.5. It does not seem to settle down to any particular value, as we might have expected, but to many. What does that mean? In order better to understand the number sequences for the population p, we will now take a quick look at the screen print-out of Figure 2.1-10 (calculation of measles values) from Chapter 2.1. We can use the program again in Exercises 2.1- 1 to 2.1-4, which we have already given, letting us display the results once more on the screen (see Figure 2.1-10). As an

34

Dynamical Systems and Fractals

additional luxury we can also make the results audible as a series of musical tones. The melody is not important. You can easily tell whether the curve tends towards a single value or many. If we experiment on the MeaslesNumber program with k = 2.3, we find an ’ oscillating phase’ jumping to and fro between two values (see Figure 1.2-10). One value is > 1, and the other c 1. For k = 2.5 it is even more interesting. At this point you should stop hiding behind the skirts of our book, and we therefore suggest that, if you have not done so already, you write your first program and carry out your fist experiment now. We will once more formulate the task precisely:

Computer Graphics Experiments and Exercises for $2.1 .l Exercise 2.1.1-l Derive the general transformation equations for yourself with the aid of Figure 2.1. l-l. Check that the simplified equation follows from the general one. Explain the relation between them. Exercise 2.1.1-2 Implement the Pascal programMeaslesGraphic on your computer. Check that you obtain the same graphic displays as in Figure 2.1.1-2. That shows you are on the right track. Exercise 2.1.1.3 Establish the connection between the special transformation formula and the expression for delt axPerP ixe 1. Exercise 2.1.1-4 Use the program Meas 1esGraphic to carry out the same investigations as in Exercise 2.1-3 (see Chapter 2.1) - this time with graphical representation of the results.

2.1.2 Graphical Iteration It may perhaps have occurred to you that the function f(x) = x+k* x* (l-x) - for so we can also write the equation - is nothing other than the function for a parabola fix)= -k*xz+(k+l)*x

This is the equation of a downward-opening parabola through the origin with its vertex in the first quadrant. It is clear that for different values of k we get different parabolas. We can also study the ‘feedback effect’ of this parabola equation by graphicaliteration. Let us explain this important concept. Feedback means that the result of a calculation is replaced into the same equation as

35

Between Order and Chaos: Feigenbaum Diagrams

a new initial condition. After many such feedbacks (iterations) we establish that the results run through certain fixed values. By graphical feedback we refer to the picture of the function in an x,y-coordinate system (x stands for p, y for f(x) or f(p)). Graphical iteration takes place in the following way. Beginning with an x-value, move vertically up or down in the picture until you hit the parabola. You can read off fix) on the y-axis. This is the initial value for the next stage of the feedback. The value must be carried across to the x-axis. For this purpose we use the diagonal, with equation y = x. From the point on the parabola (with coordinates (x, f(x)) we draw a line horizontally to the right (or left), until we encounter the diagonal (at the coordinates (f(x), f(x))). Then we draw another vertical to meet the parabola, a horizontal to meet the diagonal, and so on. This procedure will be explained further in the program and the pictures that follow it. Program Fragment 2.1.2-1 (” _________---------------------------------------

*)

(* BEGIN : Problem-specific Procedures *) FUNCTION f (p, k : real) : real; BEGIN f := p + k * p * (1 - p); END; PROCEDURE ParabolaAndDiagonal(population,feedback : real) ; VAR xcoord, deltaxPerPixe1 : real; BEGIN DeltaxPerPixel : = (Right - Left) / Xscreen; SetUniversalPoint (Left, Bottom); DrawUniversalLine (Right, Top); DrawUniversalLine (Left, Bottom); xCoord := Left; REPEAT DrawUniversalLine (xCoord, f(xCoord, feedback)); xCoord := xCoord + deltaxPerPixe1; UNTIL (xCoord > Right); GoToUniversalPoint (population, Bottom); END; PROCEDURE GraphicalIteration; (* Version for graphical iteration *) Km

36

Dynamical Systems and Fractals

previousPopulation : real; BEGIN ParabolaAndDiagonal (population, feedback); FUWiAT DrawUniversalLine (population, population); previousPopulation := population; feedback); population := f(population, DrawUniversalLine (previousPopulation, popu.lation) UNTIL Button; END; (* END : (X

Problem-specific

Procedures

*)

-------------------------------------------------

“)

(* DrawUniversalLine (x,y) draws a line from the *) (* current position to the point with universal coordinates by) . ")

Graphical

Iteration

Start: hit



Left Right Bottom Top Population Feedback

>o >1.5 >o

key

>1.5

>O.l >1.99

End: hit key

Figure 2.1.2-l

Initial value p = 0.1, k = 1.99, a limit point, with screen dialogue.

For each given k-value we get distinct pictures. If the final value is the point flp) = 1, we obtain a spiral track (Figure 2.1.2-1). In all other cases the horizontal and vertical lines tend towards segments of the original curve, which correspond to limiting p-values. Clearly the two vertical lines in Figure 2.1.2-2 represent two different p-values.

Behveen

Order and Chaos: Feigenbaum Diagrams

37

Graphical Start:

hit

Left Right Bottom Top Population Feedback

Iteration

key

>o >1.5 >o >1.5 >O.l >2.4

End: hit key Figure 2.1.2-2

Initialvaluep = 0.1, k = 2.4, two limiting points.

The distinct cases (limiting value 1, or n-fold cycles, Figures 2.1.2-1, 2.1.2-2) are thus made manifest. For an overview it can be useful to carry out the first 50 iterations without drawing them, after which 50 iterations are carried out and drawn. This process of graphical iteration can also be applied to other functions. In this way we obtain rules, about the form of the graph of a function, telling us which of the above two effects it will produce.

Computer Graphics Experiments and Exercises for $2.1.2 Exercise 2.1.2-1 Develop a program for graphical iteration. Try to generate Figures 2.1.2-1 and 2.1.2-2. Experiment with the initial value p = 0.1 and k = 2.5, 3.0. How many limiting values do you get? Exercise 2.1.2-2 Devise some other functions and apply graphical iteration to them.

2.2 Fig-trees Forever In our experiments with the program MeaslesGraphic you must surely have noticed that the lines in the range 0 I k I 1 get closer and closer together, if we increase the number of iterations (see Program 2.1 .1-l). Until now we have computed with small values, in order not to occupy too much of the computer’s time. But now we will make our first survey of the entire range. Figure 2.2.-l shows the result of 50 iterations for comparison with Figure 2.1.1-2.

38

Dynamical Systems

and

Fractals

Figure 2.2--l Situation after the onset of oscillations, iteration number = 50. Obviously some structure comes to light when we increase the accuracy of our measurements (that is, the number of iterations). And it is also clear that the extra lines in the range 0 I k 5 1 are transient effects. If we first carry out the iteration procedure for a while (say 50 iterations) without drawing points, and then continue to iterate while plotting the resulting points, the lines will disappear. The above remarks are in complete agreement with our fundamental ideas in the simulation of dynamical systems. We are interested in the ‘long-term behaviour’ of a system under feedback (see Chapter 1). Program 2.2.-l shows how easily we can modify our program MeaslesGraphic, in order to represent the long-term behaviour more clearly. Program Fragment 2.2-l Problem-specific procedures *) t* BEGIN: FUNCTION f (p, k : real) : real; BEGIN f:=p+k*p* (l-p); END; PROCE:DURE FeigenbaumIteration; VPR range, i zinteger; population, deltaxPerPixe1 : real; BEGIN deltaxPerPixe1 := (Right - Left) / Xscreen; FOR range := 0 TO Xscreen DO

40

Dynamical Systems and Fractals

Figure

l

l

2.2-2

Print-out from Program 2.2-l.

The name ‘Feigenbaum’ is in honour of the physicist Mitchell Feigenbaum, 2 who carried out the pioneering research described in this chapter. We shall call any picture like Figure 2.2-l a Feigenbaumdiagram. In the program fragment we introduce two new variables I nv i s i b 1 e and Visible, which in the example are given the value 50.

The results show a certain independence of the initial value for p, provided we do not start with p = 0 or p = 1. You will probably have discovered that already. What interests us here is just the results of a large number of iterations. To stop the picture looking unsightly, the first 50 iterations run ‘in the dark’. That is, we do not plot the results k,p. After that, a further 50 (or 100 or 200) iterations are made visible. In order to facilitate comparison with Figure 2.2- 1, you can set the variables in Program 2.2-l as follows:

Invisible

:=

0;

Visible :=

10;

As regards the working of the program, the following remarks should be made: Input data are read from the keyboard and assigned to the corresponding variables intheprocedure Initialise. It is then easy to set up arbitary values from the keyboard, However, the program must then be initialised on each run. The type of input ZTmnsJafor’s

note: It is also Geman for ’ fig-tree’ , hence the section title.

BetweenOrderandChaos:FeigenbaumDiagrams

39

BEGIN Feedback := Left + range*deltaxPerPixel; population := 0.3; FOR i := 0 to Invisible DO BEGIN population := f(population,

Feedback);

END

FOR i := 0 TO Visible DO BEGIN SetUniversalPoint (Feedback, population); population := f(population, Feedback); END; END; END; (* END: Problem-specific procedures *) (* -----------------------------------------------------*) PROCEDURE Initialise; BEGIN ReadReal ('Left ReadReal ('Right ReadReal ('Bottom ReadReal ('Top ReadInteger ('Invisible ReadInteger ('Visible END;

>'r >'I >'r >'r

Left); Right); Bottom); Top) ; >'r Invisible); >'I, Visible);

PROCEDURE ComputeAndDisplay; BEGIN EnterGraphics; FeigenbaumIteration; ExitGraphics; END; The new or modified parts of the program are shown in bold type. If we type in and run this progam then it gives a print-out as in Figure 2.2.-2. It shows for the ‘interesting’ range k > 1.5 a piece of the so-called Feigenbaum diagram.1 This program and picture will keep us busy for a while.

1 Transla~or’s

nofez This is more commonly known as a bifurcation diagram.

42

Dynamical Systems and Fractals

Program Fragment 2.2-2 ..... deltaxPerPixe1 := (Right - Left) / Xscreen; FOR range := 0 to Xscreen DO BE:GIN Feedback := Left + range * deltaxPerPixe1; DisplayFeedback (Feedback); population := 0.3;

Elsewherewewillintroduce aprocedureDisplayFeedback, and thereby enlarge ourexperimentalpossibilities. DisplayFeedback displays the current value of k in the lower left comer of the screen. It will be useful later, to establish more accurately the boundaries of interesting regions in the Feigenbaum diagram. To display text on the graphics screen some computers (such as the Apple II) require a special procedure. Other computers have the ability to display numbers of type re a 1 directly on the graphics screen, or to display text and graphics simultaneously in different windows. TheprocedureDisplayFeedback can also be omitted if it is not desired to display numerical values on the screen. In this case DisplayFeedback must be deleted from the initial part of the main program, and also in the procedure FeigenbaumIterationwhichca& it. When the program runs correctly, you should use it to draw sections of the Feigenbaum diagram. By choosing the boundaries of the windows suitably you can plot pictures whose fine detail can scarcely be distinguished in the full diagram. A tiny part of the picture can already contain the form of the whole. This astonishing property of the Feigenbaum diagram, containing itself, is called self-similarity. Look for yourself for further examples of self-similarity in the Feigenbaum diagram. We should describe how the above program works in practice. Instructions appear on the screen for the input of the necessary data. The data are always input by using the key. The dialogue might, for example, go like this: = 1.8) Left Right (<= 3) Bottom (>= 0) (<= 1.5) Top Invisible (>= 50) Visible (>= 50)

key >2.5 >2.8 >0.9 >I.4 >50 >50

The picture that arises from this choice of input data is shown in Figure 2.2-3.

Between Order and Chaos: Feigenbaum Diagrams

41

procedure used depends on the purpose of the program. With keyboard input, typing errors are possible. Sometimes it is useful to insert fixed values into the program. To draw Figure 2.2-2 on the screen on an g-bit home computer takes about 5-10 minutes. With more efficient machines (Macintosh, IBM, VAX, SUN, etc.) it is quicker. It is harder to describe these astonishing pictures than it is to produce them slowly on the screen. What for small k converges so regularly to the number 1, cannot continue to do so for larger values of k because of the increased growth-rate. The We have discovered this curve splits into two branches, then 4, then 8, 16, and so on. effect of 2, 4, or more branches (limiting values) by graphical iteration. This phenomenon is called a period-doublingcascade, (Peitgen and Richter 1986, p.7). When k > 2.570 we see behaviour that can only be described by a new concept: chaos. There are unpredictable ‘flashes’ of points on the screen, and no visible regularity. As we develop our investigations we will show that we have not blundered into chaos by accident. We have witnessed the crossing of a frontier. Up to the point k = 2 our mathematical world is still ordered. But if we work with the same formula and without rounding errors, for higher values of k it is virtually impossible to predict the outcome of the computation. A series of iterations beginning with the value p = 0.1, and one beginning with p = 0.11, can after a few iterations become completely independent, exhibiting totally different behaviour. A small change in the initial state can have unexpected consequences. ‘Small cause, large effect’: this statement moreover holds in a noticeably large region. For our Feigenbaum formula the value k = 2.57 divides ‘order and chaos’ from each other. On the right-hand-side of Figure 2.2-2 there is no order to be found. But this chaos is rather interesting - it contains structure! Figure 2.2-2 appears to have been drawn by accident. As an example, let us consider the neighbourhood of the k-value 2.84. Here there is a region in which points are very densely packed. On the other hand, there are also places nearby with hardly any points at all. By looking carefully we can discover interesting structures, in which branching again plays a role. In order to search for finer detail, we must ‘magnify’ the picture. On a computer this means that we want to display a window, or section, from the full picture 2.2-2 on the screen.3 To do this we give suitable values to the variables Right, Left, Bottom, and Top. The program user can input values from the keyboard. In that way it is possible to change the window at will, to investigate interesting regions. If the picture is expanded a large amount in the y-direction it becomes very ‘thin’, because the majority of points lead outside the window. It then makes sense, by changing the variable Visible, to increase the total number of points plotted. We now investigate the precise construction of the Feigenbaum diagram, with the aid of a new program. It is derived by a small modification of Program Fragment 2.2- 1. 31n the choice of a window there is often a problem, to find out the values for the edges. As a simple tid we construct a bansparent grid, which divides the screen into ten parts in each direction.

Dynamical Systems

Figure 2.2-4

Figure 2.2-5

and

Fractals

Fig-tree with data: 2.5,2.8,0.9, 1.4,50, 100.

Fig-tree with data: 2.83,2.87,0.5,0.8,50,

100.

Exercise 2.2-3 Find regions in the Feigenbaum diagram around k = 2.8, where self-similarity can be found. Exercise 2.2-4 Try to discover ‘hidden structure’, when you increase the iteration number in interesting regions. Think about taking small regions (and magnifying them).

43

Between Order and Chaos: Feigenbaum Diagrams .............................................................. .............................. .............................. .................... .................... ._--_ .. .. . .. ......... .......... ................... ....................... . ............................................... ............. . . . . . . . . . . . . . . . . . . .... . . ... . . ... . . . .

Figure

2.2-3 Section from the Feigenbaum diagram (see the following figures).

Figures 2.2-4 and 2.2-S represent such sections from the Feigenbaum diagram, as drawn in Figure 2.2-3. We also suggest that you try equations other than the Feigenbaum equation. Surprisingly, you will find that quite similar pictures appear! In many cases we find that the picture again begins with a line, and splits into 2,4, 8,... twigs. There is also another common feature, which we do not wish to discuss further at this stage. The stated values in Figures 2.2-4 and 2.2-5 are just examples of possible inputs. Try to find other interesting places for yourself.

Computer Graphics Experiments and Exercises for $2.2 Exercise 2.2-l Implement Program 2.2-l on your computer. Experiment with different values of thevariablesvisible and Invisible. Exercise 2.2-2 Extend the program toincludeaprocedureDisplayFeeclback, running of the program can ‘measure’ the k-values.

which during the

46

Dynamical Systems and Fractals

f (pn)

:= pn + 1/2*k*(3*pnMinuslX(1-pnMinusl)pnMinus2*(1-pnMinus2));

Exercise 2.2-8 Investigate at which k+alues

2.2.1

Bifurcation

branches occur.

Scenario - the Magic Number ‘Delta’

The splittings in the Feigenbaum diagram, which by now you have seen repeatedly in your experiments, are called bifurcations. In the Feigenbaum diagram illustrated above, some points, the branch points, play a special role. We use the notation ki for these: kl, k2, and so on. We can read off from the figures that k, = 2, k2 = 2.45, and k3 = 2.544. You can obtain these results with some effort from Exercise 2.2-8. It was the great discovery of Mitchell Feigenbaum to have found a connection between these numbers. He realised that the sequence kn-kn-1 -, for n = 2,3, . . . k n+l -k” converges to a constant value 6 (the Greek letter ‘delta’) when n tends to 00. Its decimal expansion begins 6 = 4.669 . . . . We have formulated a series of interesting exercises about this number 6 (Exercises 2.2.1-lff. at the end of this section). They are particularly recommended if you enjoy number games and are interested in ‘magic numbers’. Incidentally, you will then have shown that 6 is a genuinely significant mathematical constant, which appears in several This same number arises in many different processes involving dynamical contexts. systems. For bifurcation problems it is as characteristic as the number K is for the area

Figure

2.2.1-1 Logarithmic representation from k = 1.6 to k = 2.569.

Between Order and Chaos: Feigenbaum Diagrams

45

Exercise 2.2-S As regards the chaotic phenomena of Feigenbaum iteration, much more can be said. ‘The initial value leads to unpredictable behaviour, but on average there is a definite result.’ Test this hypothesis by displaying the average value of a large number of results as a graph, for k-values in the chaotic region. See if you can confirm this hypothesis, or perhaps the contrary: ‘Chaos is so fundamental that even the averages for k-values taken close together get spread out.’ Exercises 2.2-6 That after these explanations our investigation of the ‘fig-tree’ has not revealed all its secrets, is shown by the following consideration: Why must the result of the function f always depend only on the previous p-value? It is possible to imagine that the progenitors of this value ‘have a say in the matter’. The value fn for the nth iteration would then depend not only on fn-l, but also on It would be sensible if ‘older generations’ had somewhat less effect. In a fn-2, etc. program you can, for example, store the most recent value as pn, the previous one as pnMinus1, and the one before that as pnMinus2. The function fcan then be viewed as follows. We give two examples in Pascal notation. := pn + 1/2*k* (3*pn* (l-pn) f (pn) pnMinusl* (1-pnMinus1) ) ; or := pn +1/2*k* (3*pnMinusl-pnMinus2) * f (pn) (1-3*pnMinusl-pnMinus2 ); To start, pn, pnMinus 1, etc. should be given sensible values such as 0.3, and at each stage they should obviously be given their new values. The k-values must lie in a rather different range than previously. Try it out! In the above print-out it goes without saying that other factors such as -1 and 3 and other summands are possible. The equations under consideration no longer have anything to do with the original ‘measles’ problem. They are not entirely unknown to mathematicians: they appear in a similar form in approximation methods for the solution of differential equations. Exercise 2.2-l In summary we might say that we always obtain a Feigenbaum diagram if the recursion equation is nonlinear. In other words, the underlying graph must be curved. The diagrams appear especially unusual, if more generations of values are made visible. This gives rise to a new set of functions to investigate, for which we can change the series, in which we ‘worry about the important bend in the curve’ - which happens to be the term expression* (1 - expression) intowhichwe substitute theprevious value:

48

Dynamical Systems and Fractals

powers of 10) into 60 parts, and draw three decades on the screen, there will be a figure 180 points wide. If you also expand the scale in the vertical direction, you will have a good measuring instrument to develop the computation of the kj-values. Exercise 2.2.1-3 With a lot of patience you can set loose the ‘order within chaos’ - investigate the region around k = 2.84. Convince yourself that 6 has the same value as in the range k < 2.57.

Exercise 2.2.1-4 Develop a program to search for the kj-values automatically, which works not graphically, but numerically. Bear in mind that numerical calculations in Pascal rapidly run into limitations. The internal binary representation for a floating-point number uses 23 bits, which corresponds to about 6 or 7 decimal places. This restriction clearly did not put Feigenbaum off - he evaluated the aforementioned constant 6 as 4.669 201660 910 299 097 . . . . On some computers it is possible to represent numbers more accurately. Look it up in the manual. Exercise 2.2.1-5 Feigenbaum’s amazing constant arises not only when we follow the branching from left to right (small k-values to large ones). The ‘bands of chaos’, which are densely filled with points, also split when we go from large k-values to small ones. A single connected band splits into 2, then 4, then 8, . . . . Compute the k-values where this occurs. Show that the constant 6 appears here too.

2.2.2 Attractors and Frontiers The mathematical equation which lies at the basis of our first experiment was formulated by Verhulst as early as 1845. He studied the growth of a group of animals, for which a restricted living space is available. In this interpretation it becomes clear what a value p > 1 means. p = 100% means that every animal has the optimum living space available. More than 100% corresponds to overpopulation. The simple calculations we have performed for the measles problem already show how the population then develops. For normal values of k the population is cut back until the value 1 is reached. However, the behaviour is different if we start with negative or large numbers. Even after many steps the population no longer manages to reach 1. Mathematicians, like other scientists, habitually develop new ideas in order to attack new and interesting phenomena. This takes us a little way into the imposing framework of technical jargon. With clearly defined concepts it is possible to describe clearly

Between Order and Chaos: Feigenbawn Diagrams

41

and circumference of a circle. We call this number the Feigenbazun number. Mitchell Feigenbaum demonstrated its universality in many computer experiments. 4 The higher symmetry and proportion that lies behind the above is especially significant if we do not choose a linear scale on the k-axis. Once the limiting value k, of the sequence k,, k2, k3, . . . is known, a logarithmic scale is preferable.

Computer Graphics Experiments and Exercises for $2.2.1 Exercise 2.2.1- 1 The Feigenbaum constant 6 has proved to be a natural constant, which occurs in situations other than that in which Feigenbaum first discovered it. Compute this natural constant as accurately as possible: kIl-k”-l 6=lim IHcm k n+l -k II ’ In order to work out 6, the values kj must be calculated as accurately as possible. Using Program Fragments 2.2-l and 2.2-2 you can look at the interesting intervals of k and p, and pursue the branching of the lines. By repeatedly magnifying windows taken from the diagram you can compute the k-values. Near the branch-points, convergence is very bad. It can happen that even after 100 iterations we cannot decide whether branching has taken place. We should henceforth make tiny changes to the program l to make the point being worked on flash, and l to avoid choosing a fixed iteration number at the start. It is easy to make a point flash by changing its colour repeatedly from black to white and back again. We can change the iteration number by using a different loop construction. Instead of FOR counter := 1 to Visible DO we introduce a construction of the form REPEAT UNTIL Button;5 Exercise 2.2.1-2 Change the Feigenbaum program so that it uses a logarithmic scale for the k-axis instead of a linear one. Positions k should be replaced by -ln(k,-k) measured from the right.

For the usual Feigenbaum diagram the limit k, of the sequence kl, k2, k3, . . . has the value 2.570. If, for example, we divide each decade (interval between successive 4Tbe universality was proved mathematically by Pierre Collet, Jean-Pierre Eckmann, and Oscar Lanford (1980).

51nTurboPascalyoumustuse REPEAT UNTIL Keypressed;

50

Dynamical Systems

and Fractak

attraction, of the strange attractor. We will see that these boundaries do not always take

such a smooth and simple form. And they cannot always, as in the Feigenbaum diagram, be described by simple equations. The problem of the boundaries between attracting regions, and how to draw these boundaries, will concern us in the next chapter. In Figure 2.2.2- 1 we again show the Feigenbaum diagram for the fist quadrant of the coordinate system. We have superimposed the basin of attraction of the attractor.

kl

k2 k3

Figure 2.2.2-l Basin of attraction for the Feigenbaum diagram. If you are interested in how the attractor looks and what its boundaries are when k is less than 0, try Exercise 2.2.2-2 at the end of this section.

Computer Graphics Experiments and Exercises for $2.2.2 Exercise 2.2.2-l Show that ~+k*p*(l-p) > 0, p # 0, k # 0 implies that p < (k+l)/k. Exercise 2.2.2-2 So far we have described all phenomena in the case k > 0. What happens for k I 0 the reader/experimentalist must determine. To that end, three types of problem must be analysed: l In which k,p-regions do we find stable solutions (that is, solutions not tending to -w)?

Between Order and Chaos: Feigenbaum Diagrams

49

defined circumstances. We will now encounter one such concept. In the absence of anything better, mathematicians have developed a concept to capture the behaviour of the numbers in the Feigenbaum scenario. The final value p = 1 is called an attractor, because it ‘pulls the solutions of the equations’ towards itself. This can be clearly seen on the left-hand side of Figure 2.1.1-2. However many times we feed back the results p,, into the Feigenbaum equation, all the results tend towards the magic final value 1. The p-values are drawn towards the attractor 1. What you may perhaps have noticed already in your experiments is another attractor, -00 (minus infinity). At higher values (k > 2) of the feedback constant, the finite attractor is not just the value 1. Consider the picture of the Feigenbaum diagram: the whole figure is the attractor! Each sequence of p-values which starts near the attractor invariably ends with a sequence of numbers that belong to the attractor, that is, the entire figure. An example will clarify this. IntheprogramMeaslesNumber start with p = 0.1 and k = 2.5. After about 30 iterations the program stops. From the 20th iteration on we see these numbers over and over again: . . . 1.2250, 0.5359, 1.1577, 0.7012, 1.2250, 0.5359, 1.1577,0.7012, . . . etc. It is certainly not easy to understand why this happens, but from the definition it is undeniable that these four successive values determine the attractor for k = 2.5. The attractor is thus the set of those function values which emerge after a sufficiently large number of iterations. A set like that illustrated in Figure 2.2-2 is called a strange attractor. In the region k > 3 there is just the attractor -00. Whenever a function has several attractors, new questions are raised: . Which regions of the kq-plane belong to which attractor? That is, with which value p must I start, so that I am certain to reach a given objective - such as landing on the attractor l? . With which values should I start, if I do not wish to end at -m? Because each sequence of numbers is uniquely determined, this question has a unique answer. Thus the k,p-plane is divided into clearly distinguished regions, whose boundaries are of considerable interest. For the Feigenbaum diagram this problem can be solved in a relatively simple and clear fashion. But other cases, which we will encounter later, lead to surprising results. For the above function fW = p+k*p*(l-P)

we can calculate the boundaries mathematically. Experimenting with the program MeaslesNumber should make it apparent that it is best to take negative p-values. Only then is there a chance of landing on the attractor. This means that gP) must be > 0. From the equation (see Exercise 2.2.2-l at the end of this section) this condition holds when p < (k+l)/k. Thus near p = 0 we have found the two boundaries for the catchment area, or basin of

52

Figure 2.2.3-l

Dynamical Systems and Fractals

Feigenbaum landscape with the data 0, 3,0, 1.4, 50, 500.

The box-number is counted from the right and the contents are drawn upwards, joining neighbouring values by a line. The result is a curve resembling a mountain range, which describes the distribution of p-values for a given k-value. To draw a picture with several k-values, we combine several such curves in one picture. Each successive curve is displaced two pixels upwards and one pixel to the right. In this way we obtain a ‘pseudo-three-dimensional’ effect. Of course the horizontal displacement can be to the left instead. In Figure 2.2.3-3 ten such curves are drawn. To improve the visibility, the individual curves must be combined into a unified picture. To achieve this, we do not draw the curves straight away. Instead, for each horizontal screen coordinate (x-axis) we record in another field (in Pascal it is an array, just like the ‘boxes’) whichever of the previous vertical y-coordinates has the largest value. Only this maximal value is actually drawn. With these hints you should be in a position to develop the program yourself. A solution is of course given in 3 11.3.

Between Order and Chaos: Feigenbaum Diagrams

I

I

51

What form does the attractor have? Where are the boundaries of the basins of attraction?

Exercise 2.2.2-3 We obtain a further extension of the regions to be examined, and hence extra questions to be answered, if we work with a different equation from that of Verhulst. One possibility is that we simplify the previous formula for f(p) to f(p) = k*p*(p-I). This is just the term that describes the change from one generation to the next in the Verhulst equation. Investigate, for this example in particular, the basins of attraction and the value of 6. Exercise 2.2.2-4 With enough courage, you can now try other equations. The results cannot be anticipated in advance, but they tend to be startling. Examples which provide attractive pictures and interesting insights are: l f(p) = k*p+p*(l -p) in the region 4 5 k I 7, f(p) = k*p*(l-p*p) and other powers, + l f(p) = k*sin(p)*cos(p) or square (cube, nth) root functions, m f(p) = k*(l - 2*1 p-O.5 I) where 1x Imeans the absolute value of x.

2.2.3 Feigenbaum Landscapes Even the simple fig-tree poses several puzzles. In the ‘chaotic regime’ we can see zones where points lie more thickly than in others. You can get a nice overview by representing the frequency with which the p-values fall inside a given interval. By putting the results together for different k-values, you will get a Feigenbaum landscape (Figures 2.2.3-l and 2.2.3-2). These Feigenbaum landscapes can be made to reveal further interesting structure. We suggest you experiment for yourself. It is naturally best if you develop the program yourself too, or at least try it out with your own parameter values. To help you in this task, we now provide some tips for the development of a Feigenbaum landscape program. The appropriate range of values from 0 to 1.4 for f@) must be divided into a certain number of intervals. This number of course depends on the size of the screen display, which we have set using the constants xscreen and ~screen. In the program, for example, we have 280 ‘boxes’, one for each interval. For a given k-value the Feigenbaum program begins as usual. When a value of After a fTp) falls within a given interval, this is noted in the corresponding box. sufficiently large number of iterations we stop the computation. Finally the results are displayed.

54

Dynamical Systems and Fmctals

The interesting cases are those in which the results of our computations do not tend to m or -m. + The set of all results that can be obtained after sufficiently many iterations is called an anractor. l The graphical representation of attractors leads to pictures, which contain smaller copies of themselves. . Three new concepts - attractor, frontier, and bifurcation - are connected with these mathematical features. We began with the central idea of ‘experimental mathematics’: . These important concepts in the theory of dynamical systems are based on taking an arbitrary mathematical equation and ‘feeding it back’ its own results again and again. By choosing different starting values we repeatedly find the same results upon iteration. With the same initial values we always obtain the same results. There are however some deep and remarkable facts to be observed: In the Feigenbaum diagram we can distinguish three regions: + k< 2 (Order); . 2 c k < 2.57 (Period doubling cascade: 0 I p 5 1.5); . k 2 2.57 (Chaos). Under certain conditions, moreover, we cannot predict what will happen at all. Insignificant differences in the initial value lead to totally different behaviour, giving virtually unpredictable results. This ‘breakdown of computability’ happens around k = 2.57. This is the ‘point of no return’ , dividing the region of order from that of chaos. To avoid misunderstandings, we must again emphasise that the above remarks refer to a completely deterministic system. But - from a practical point of view - the chaos effect produces the bitter aftertaste of indeterminacy. Mathematicians try to find models that can describe the ‘long-term behaviour’ of a system. The Feigenbaum scenario exemplifies the behaviour of the simplest nonlinear system. The message is that any nonlinear system may exhibit similar phenomena. Complex systems, depending on many parameters, can under certain conditions switch from stable conditions to instability. We speak of chaos. Of course we want to keep on the track of this essentially philosophical question. It seems that there is some deep connection between order and chaos, which we cannot yet makeexplicit. One thing is certain. As a result of our previous investigations, order and chaos are two sides to the same coin - a parameter-sensitive classification. Enough theory! In the following chapter we will return to the question. But now you must try out some exercises for yourself. Good luck with your experiments!

l

53

Between Order and Chaos: Feigenbaum Diagrams

Figure 2.2.3-2

Feigenbaum landscape with the data 3, 2.4, 1.4, 0, 50, 500.

Computer Graphics Experiments and Exercises for $2.2.3 Exercise 2.2.3-l Develop a program to draw Feigenbaum landscapes. Use the resulting ‘three-dimensional measuring instrument’ to investigate interesting sections of the Feigenbaum diagram. We have already given hints for the main steps above. Exercise 2.2.3-2 Ceneralise the pseudo-three-dimensional can be represented in the same way.

landscape

method,

so

that

other

formulas

2.3 Chaos - Two Sides to the Same Coin In the previous chapter you were confronted with many new concepts. Furthermore, your own experiments will certainly have given you more to think about, so We will that the basic idea of the first chapter may have been somewhat obscured. therefore discuss the initial consequences of our investigations, before we embark on new adventures. What have we discovered?

56

Dynamical Systems and Fractals

3.1 The Strange Attractor Because of its aesthetic qualities, the Feigenbaum diagram has acquired the nature of a symbol. Out of allegedly dry mathematics, a fundamental form arises. It describes the connection between two concepts, which have hitherto seemed quite distinct: order and chaos, differing from each other only by the values of a parameter. Indeed the two All nonlinear systems can display this typical are opposite sides of the same coin. transition. In general we speak of the Feigenbaumscenario (see Chapter 9). Indeed the fig-tree, although we have considered it from different directions, is an entirely static picture. The development in time appears only when we see the picture build up on the screen. We will now attempt to understand the development of the attractor from a rather different point of view, using the two dimensions that we can set up in a Cartesian coordinate system. The feedback parameter k will no longer appear in the graphical representation, although as before it will run continuously through the range That is, we replace the independent variable k in our previous OIk 13. (k,p)-coordinate system by another quantity, because we want to investigate other mathematical phenomena. This trick, of playing off different parameters against .each other in a coordinate system, will frequently be useful. From the previous chapter we know that it is enough to choose k between 0 and 3. There are values between k = 1.8 and k = 3 at which we can observe the perioddoubling cascade and chaos. In order to investigate the development of the Feigenbaum diagram in terms of the sequence pm1 = p,i+k*pn*U-PA

we choose as coordinate system the population values p,, and p,,+l which follow each other in the sequence. To the right we draw the final value pn of the previous iteration, and we draw the result p,,+l = f&J vertically. We know this construction already from graphical iteration (see Chapter 2.1.2). If you have already set up the program Feigenbaum then the modifications required are relatively easy. They relate solely to the part that does the drawing. Instead of the coordinates (k,p) we must now display (p, qP,k)) on the screen. In the program fragment only the following part changes: FOR i = 0 to Visible DO BEGIN SetUniversalPoint (population, f(population, Feedback)); population := f(population, Feedback); END; Nothing else need be altered. You should make this modification to your existing program and see what happens. The final result (Figure 3.1-1) can only convey an incomplete impression of the dynamical development that occurs during its generation. You are advised to observe the gradual growth of this figure on the screen. If we choose the same scale on both axes the picture begins (for k a little larger than 0) in a less than spectacular way. The diagonal

3 Strange Attractors

‘< . . . . .-...

. .*

58

DynamicalSystemsandFractals

For small k-values we soon run into a boundary, which of course lies on the diagonal of the @,Q))-coordinate system. We can observe the periods 2, 4, 8, etc. When we reach the chaos-value k= 1.6 things get very exciting. At the first instant a parabola suddenly appears. Furthermore, it is not evenly filled, as we have seen already. It has an ‘internal structure’. Let us once more collect our conclusions together. The geometric form of the attractor arises because we draw the elements of a sequence in a coordinate system. T o do this we represent the starting value p in one direction, and in the other the result gP) of the iteration for a fixed value of k. We first notice that the values for 0) do not leave a certain range between 0 and 1.4. Furthermore, we notice genuine chaos, revealing either no periodicity at all or a very long period. Here we know that more and more points appear in a completely unpredictable way. These points form lines or hint at their presence. Under careful observation the attractor seems to sit on a parabolic curve, defined by numerous thin lines. We want to take a closer look at that!

Figure 3.1-2

The Verhulst attractor for k = 1.60.

The changes in our previous program that are needed to generate the Verhulst attractor are again very simple: Program Fragment 3.1-1 (* BEGIN: problem-specific PROCEDURE VerhulstAttractor; VARi : integer;

procedures

*)

Strange

Attractors

57

straight lime, which fit appears, expresses the fact that the underlying value is tending to a constant. Then p = 0). After k = 2 we obtain two alternating underlying values.

Data: 0,3,0, 1.4,50,50 for 0 I k I 3 Figure 3.1-1

Trace’ of the parabola-attractor in the p&)-plane.

The figure grows in two directions. Low starting values for the formula produce a higher result and then return. The curious picture here has the form of a thin curved line and runs roughly perpendicular to the original bisector. For periods 4 and 8 - when the figure grows in 4 or 8 places - it is also easy to see how the starting value p and the result RJJ) are connected Thus we have built ourselves yet another measuring or observing instrument, with which we can watch the temporal development of perioddoubling. As soon as we enter the chaotic region, a well-known mathematical object appears: the parabola. If you want to draw this and similar pictures, please take a look at Exercises 3-l and 3-2 at the end of this chapter. However, you will need a certain amount of patience, because in Figure 3.1- 1 it takes some time, after the diagonal line is drawn, before points scatter on to the parabola. In order to delve more deeply into the ‘history’ of the sequence, it is necessary to link together the results not just of one, but of several previous values. The investigation of the so-called Verhulst attractor (Figure 3.1-2) is especially interesting. This is the attractor corresponding to the equation f(pn) = pn + 1/2*k*(3*pn*(l-pn)-pnMinusl*(l-pnMinus1)) which we have already encountered in $2.2.

60

Dynamical Systems and Fractats

(Figure 3.1-3 ff.). By looking closely enough we encounter the same structure whenever we magnify the attractor. This structure is repeated infinitely often inside itself and occurs more often the more closely we look. The description of this ‘self-similarity’, and the aesthetic structure of the Verhulst attractor already referred to, are developed further in exercises at the end of the chapter.

Figure 3.1-3

Self-similarity at each step (top left projections of the attractor).

As already mentioned at the end of $2.1, we have wandered some way from our original problem (‘measles in the children’s home’). We will now explain the mathematical background and some possible generalisations. The equation on which the Verhulst attractor is based is well known as a numerical procedure for the solution of a differential equation. By this we mean an equation in which a function y and one of more of its derivatives occur, either linearly or nonlinearly. You remember: the first derivative y’ describes how rapidly y changes. The second derivative y” describes how y’ changes, and hence the curvature of y. The simplest form for a nonlinear differentialequationis f = Y*(l-Y) = d.Yh The symbol g(y), which we use for y*(l-y), will simplify the later description. A nonlinear differential equation is an equation in which the function y occurs quadratically, to a higher power, or for example as a trignometric expression. Numerical methods are known for solving such equations. Starting from an initial

59

Strange Attractors

pn, pnMinus1,

pnMinus2, oldvalue:

FUNCTION f(pn : real) : real; BEGIN pnMinus1 := pnMinus2; pnMinus2 := pn; f := pn + Feedback/2*(3*pn*(l-pn) pnMinusl*(l-pnMinus1)); END;

real;

-

BEGIN := 0.3; pnMinus2 := 0.3; pn := 0.3; pnMinus1 FOR i := 0 TO Invisible DO pn := f(pn); REPEAT oldValue := pn; := f(pn); w SetUniversalPoint (pn, oldValue); UNTIL Button; END; The value of Feedback is constant during each run of the program, e.g. k = 1.6. I n order to experiment with different k-values, the variable Feedback - and also Left , Right,Bottorn,Top -mustbeinput. Using this VerhulstAttractor program we draw, in the first instance, the whole attractor, when p and i(p) lie between 0 and 1.4 (see Exercise 3-3). If we choose a different range of values, we get different sections of it. To begin with, we look at places where there seems to be just a line, and then at the ‘nodes’ where the ‘lines’ meet or cross. These lines break up when they are magnified. In fact, they are really ‘chains’ into which the points arrange themselves. The picture resembles an aerial photograph of a large number of people walking in the snow along pm-defined tracks. The starting-point and destination are nowhere to be seen. By looking closely enough we can distinguish a faint track (along which the points/people lie more thickly) and parallel to it a wider one, on which the points are distributed more irregularly. A magnification of the wider track shows exactly the same structure. The same even happens if we magnify the thin track by a larger amount. If we examine the ‘nodes’ more carefully, we obtain something we have already encountered: a smaller version of the same attractor. This remarkable behaviour has already arisen in the Feigenbaum diagram. Many sections of the diagram produce the entire figure. This is the phenomenon of self-similarity again. The strange Verhulst attractor exhibits a structure assembled from intricate curves

62

Dynamical Systems and Fractals

3.2 The HCnon Attractor We can find formulas for other graphically interesting attractors, without needing specialmathematical background. Douglas Hofstadter (1981) describes the H&non attractor. On page 7 he writes: ‘It refers to a sequence of points (x,,,y,J generated by the recursive formulas xml = y,-a*+1 yIl+1= b*%r For the sequence illustrated the values a = 7/5 and b = 3/10 were taken; the starting values were ~0 = 0 and yu = 0.’ Contemplate the Henon attractor of Figure 3.2- 1. any

Figure 3.2-l The H&non attractor Like the Feigenbaum diagram, the H&non attractor should not be thought of as just a mathematical toy which produces remarkable computer graphics. In 1968, Michel H&on, at the Institute for Astrophysics, Paris, proposed taking such simple quadratic mappings as models, to carry out computer-graphical simulations of dynamical systems. In particular, he was thinking of the study of the orbits of asteroids, satellites, and other heavenly bodies, or of electrically charged particles in particle accelerators. During the period 1954-63 the mathematicians Kohnogorov, Arnold, and Moser developed a theory centred around the so-called KAM theorem. In it, they studied the behaviour of a stable dynamical system - such as, for example, a satellite circling the Earth - to clarify what happens when tiny external forces act on it. Planets or asteroids which orbit round the Sun often undergo such perturbations, so that their orbits are not truly elliptical. The KAM theorem attempts to decide whether small perturbations by external forces can lead to instability - to chaos - in the long-term behaviour. For

61

Strange Attractors

value yo, we try to approximate the equation in small steps. The rapidity with which we approach the limiting value (if one exists) is represented by the symbol k. r

:

e-* . ..a.. . . *. c:

.: c.

Figure 3.1-4 Self-similarity at each step (detail from the ‘node’ to the right of centre) . The simplest technique, known as Euler’s method, is described e.g. in Abramowitz and Stegun (1968): Y,I = yn+k*Yn+W2). The final term expresses the fact that the equation is not exact, and that the error is of the order of magnitude of k2. Since we have previously considered many iterations, the error interests us no further. The estimate is simplified if instead of f/n = g(y,) = yn*( 1 -y,J we substitute yn+l= y,+k*in = y,+k*&Q = y,,+k*y,*U-y,). Thus we have recovered our old friend, the Feigenbaum formula, from $2.2! There now opens up a promising approach to interesting graphical experiments: choose a differential equation that is easy to compute, and try to approximate the solution by a numerical method. The numerical method, in the form of an iterative procedure, can then be taken as the basis of the graphical experiment. In the same way we can derive the equation for the Verhulst attractor. The starting-point is the so-called two-step Adams-Bashforth method. It is somewhat more complicated than the Euler method (see Exercises 3-6 and 3-7).

64

Dynamical Systems and Fractals

FOR j = 1 to orbitNumber DO BEGIN i := 1; WHILE i <= pointNumber DO BEGIN IF (abs(xOld)<= maxReal) AND (abs(yOld)<= maxReal) THEN BEGIN xNew := xOld*cosA - (yOld - xOld*xOld)*sinA; yNew := xOld*sinA + (yOld - xOld*xOld)*cosA; ok1 := (abs(xNew-Left) < maxInt/deltaxPerPixel); ok2 := (abs(Top-yNew) < MaxInt/deltayPerPixel); IF ok1 AND ok2 THEN BEGIN SetUniversalPoint (xNeW, yNew); END; xOld := xNew; yOld := yNew; END; i := i+l; END; {WHILE i} xOld := x0 + j * dx0; yOld := y0 + j * dy0; END; {FOR j := . ..) END; (* END : problem-specific procedures *)

3.3 The Lorenz Attractor Five years before Michel H&non began working in Paris on models for simulating dynamical systems, equally exciting things were happening elsewhere. In 1963, working in a completely different area, the American Edward N. Lorenz wrote a remarkable scientificarticle. In his article Lorenz described a family of three particular differential equations1 with parameters a, b, c : Pi = a*(y-x) y’ = b*x-y-x*z z! = x*y-oz.

Numerical analysis on a computer revealed that these equations have extremely ‘We write the first derivatives with respect to time as x’, y’. z’, etc. For example x’ will be written in place of dx/dt.

StrangeAttractors

63

instance an asteroid can be disturbed in its path by the gravitational force of Jupiter. Here one talks of resonance. Such resonances occur when the ratio of the orbital periods is a rational number. If, for example, two of Jupiter’s orbits take the same time as five orbits of an asteroid, we have the case of a 2:5resonance. In the title picture of Chapter 3 we see (upper figure) such a computer simulation, where in the course of the simulation ever stronger external influences are imposed. The inner curves elucidate the influence on the orbital behaviour of small external disturbances. Each point in the drawing shows the position of the asteroid after a further revolution. For small disturbances only small differences can be seen, and the system remains stable. When the influence of the external disturbance increases, we observe six ‘islands’. These represent a I:6 resonance. A body, such as for instance an asteroid, having l/6 the orbital period of Jupiter, would find itself in such a resonance band. Further out, we see dotted regions of instability. The behaviour of an asteroid in this region is no longer predictable, because small external influences can have large effects. It is even possible for the asteroid to be catapulted out of its orbit into the ‘emptiness’ of the universe. Scientists believe that the gaps in the asteroid belt can be explained by this mechanism. This brief explanation should make clear the connection between such simple formulas, and deep effects in the field of macroscopic physics. Further explanation can be found in physics texts or in Hughes (1986). The formula to generate the title picture of Chapter 3 is as follows: xwl = x,*cos(w) - (y,-x,z)*sin(w) yrrtl = x,*sin(w) - (yn-xn2)*cos(w). Here w is an angle in the range 0 I w I IC. Compare the structure of this formula with the one described by Hofstadter at the start of this chapter. A program fragment for generating (other) H&non attractors is as follows: Program Fragment 3.2-l PROCEDURE HenonAttractors; (* x0, ~0, dx0, dy0 global variables *) VAR COSA, sinA : real; xNew, yNew, xOld, yOld : real; deltaxPerPixe1, deltayPerPixe1 : real; okl, ok2 : boolean; 8 1, 3 : integer; BEGIN cosA := cos (phaseAngle); sir-A := sin (phaseAngle); xOld := x0; yOld := y0; {starting point of first orbit] := Xscreen/(Right-Left); deltaxPerPixe1 deltayPerPixe1 := Yscreen/(Top-Bottom);

66

Dynamical Systems and Fmctals

The program fragment that generates the figure is like this: Program Fragment 3.3-l (* START : Problem-specific procedures “) PROCEDURE LorenzAttractor; VAR x, y, 2 : real; PROCEDURE f; CONST delta = 0.01; VAR dx, dy, dz : real; BEGIN dx := lo*(y-x); dy := x*(28-2)-y; dz := x*y - (8/3)X2; x := x + delta*dx; Y := y + delta*dy; z := z + delta*dz; END; BEGIN x := 1; y := 1; z := 1; f; SetUniversalPoint (x,z); REPEAT f; DrawUniversalLine (x, z); UNTIL Button; END; (* END : Problem-specific procedures *) The behaviour which Lorenz observed on the screen in 1963 can be described in the following manner. The wandering point on the screen circles first round one of the two foci around which the two-lobed shape develops. Suddenly it changes to the other side. The point wanders on, drawing its line, until suddenly it switches back to the other side again. The behaviour of the path, in particular the change from one lobe to the other, is something that we cannot predict in the long run. Even though this simple model is not, broadly speaking, capable of explaining the complex thermodynamic and radiative mechanisms that go on in the atmosphere, it does establish two points: . It illustrates the basic impossibility of precise weather-prediction. Lorenz talked about this himself, saying that the ‘fluttering of a butterfly’s wing’ can influence

Strange Attractors

65

complicated solutions. The complicated connections with and dependences upon the parameters could at first be elucidated only through computer-graphical methods. The interpretation of the equations was exciting. In particular Lorenz sought - and found - a mathematical description which led to a rational explanation of the phenomenon of unpredictability of the weather in meteorology. The idea of the model is as follows. The Earth is heated by the Sun. Part of the energy received at the Earth’s surface is absorbed and heats the atmosphere from below. From above, the atmosphere is cooled by radiation into space. The lower, warmer layers of air want to rise upwards, and the upper, colder layers want to fall downwards. This transport problem, with oscillating layers of cold and warm air, can lead to turbulent behaviour in the atmosphere. The picture’s remarkable appearance cannot fully capture the surprising behaviour that occurs while it is being drawn on the screen. In consequence it is very important that you program and experiment for yourself. Having said that, let us look first at some pictures of the Lorenz attractor.

Figure 3.3-l Lorenz attractor for a = 10, b = 28, c = 8/3, and screen dimensions

-30, 30, -30, 80.

Figure 3.3-2 Lorenz attractor for a = 20, b = 20, c = 8/3, and screen dimensions

-30, 30, -30, 80.

68

Dynamical Systems

and

Fractals

Exercise 3-5 Make a ‘movie’ in which a sequence of magnified sections of the attractor are superimposed on each other. Exercise 3-6 The two-step Adams-Bashforth method can be written like this: 1 Y,l = Yn + z*~*(3*g&MYn-1)). If we substitute &) = p( 1 -y) we obtain KYJJ = Y~+~*k*(3*Y,*(l-Yn)-Yn-**(l-Y,-1)).

If we use the current variable p and the previous value pnMinus 1, we get the familiar formula f(pn) = pn+l/2*k*(3*pn*(l-pn)-pnMinusl*(l-pNminus1)). Try out the above method to find solutions of differential equations, and also other variations on the method, such as: Y,,+I = yn-I + 2*k*&a) Y,,+I = Y~+~~~*MY,,MY~-IN Y,,+~ = ya+k/24*(55*go;1)-S9*~a-l~37*~a-2)-9*~a-3) or whatever else you can find in your mathematical textbooks. Calculate Feigenbaum diagrams and draw the attractor in @,iip))-coordinates. Exercise 3.7 We will relax the methods for solving differential equations further. The constants 3 and -1 appearing in the Adams-Bashforth method are not sacred. We simply change them. Investigate the attractors produced by the recursion formula f(p) = p + 1/2*k*(a*p*(l-p)+b*pnMinusl*(l-pnMinus1)). Next work out, without drawing anything, which combinations of a and b can occur without the value fTp) becoming too large. Put together a ‘movie’ of the changes in the attractor, occurring when the parameter a alone is varied from 2 to 3, with a = 3, b = -1 as the end point. Exercise 3-8 Write a program to draw the H&non attractor. Note that you do not have to use the same scale on each coordinate axis. Construct sections of this figure. Change the values of a and b in the previous exercises. Get hold of the article by Hofstadter (1981) and check his statements. Exercise 3-9 Experiment with the system of equations for the ‘planetary’ H&non attractor. for the title picture, for instance, are: phaseAngle := 1.111; Left := -1.2, Fight := 1.2;

Data

Strange Attractors

67

the weather. He called it the butterfly &cl. It raises the hope that very complex behaviour might perhaps be understood through simple mathematical models. This is a basic assumption, from which scientists in the modem theory of dynamical systems start. If this hypothesis had been wrong, and had not on occasion already proved to be correct, everybody’s scientific work in this area would have been pointless. As far as we are concerned, it remains true that certain principles on the limits to predictability exist, which cannot be overcome even with the best computer assistance. To understand and pin down this phenomenon is the aim of scientists in the borderland between experimental mathematics, computer graphics, and other sciences. l

Computer Graphics Experiments and Exercises for Chapter 3 Exercise 3 - 1 Modify the program Feigenbaum so that you can use it to draw the parabola attractor. Investigate this figure in fine detail. Look at important k-intervals, for example those with a uniform period. Look at the region near the vertex of the parabola, magnified. Exercise 3-2 Carry out similar investigations using the number sequences described above in $2.2.

Exercise 3-3 Starting from Feigenbaum develop a Pascal program to draw the Verhulst attractor with the value k = 1.6, within the ranges 0 I p I 1.4 and 0 I fTp) I 1.4. Start with p = 0.3 and do not draw the first 20 points. Compare your result with Figure 3.1-2. Investigate different sections from this figure, in which you define the boundaries of the drawing more closely. Exercise 3-4 Make an animated ‘movie’ in which several pictures are shown one after the other. The pictures should show a section of the attractor at increasingly large magnification. We recommend a region near the ‘node’ with coordinates p = 0.6, I@) = 1.289. Start with the entire picture. In this connection we offer a warning: the more extreme the magnification, the more points you must compute that lie outside the region being drawn. It can take more than an hour to put the outline of the attractor on the screen.

Strange Attractors

69

Bottom := -1.2; Tcp := 1.2; x0 := 0.098; y0 := 0.061; dX0 := 0.04; dy0 := 0.03; orbitNuder := 40; pointNumber := 700; further suitable data can be found in Hughes (1986). Exercise 3-10 Experiment with the L,orenz attractor. Vary the parameters a, b, c. What influence do they have on the form of the attractor? Exercise 3-11 Another attractor, called the R&sler formulas: ‘d = -cy+z) J/ = x+ty/5) .?! = l/5 + 24x-5.7). Experiment with this creature.

attractor, can be obtained from the following

72

Dynamical Systems and Fmctals

In the previous chapters we saw what the 140-year-old Verhulst formula is capable of when we approach it with modem computers. Now we pursue the central ideas of selfsimilarity and chaos in connection with two further mathematical classics. These are Newton’s method for calculating zeros, and the Gaussian plane for representing complex numbers. In both cases we are dealing with long-established methods of applied mathematics. In school mathematics both are given perfunctory attention from time to time, but perhaps these considerations will stimulate something to change that.

4.1 Newton’s Method A simple mathematical example will demonstrate that chaos can be just around the comer. Our starting point is an equation of the third degree, the cubic polynomial y = &x) = (x+1)*x*(x-l) = x3-x. This polynomial has zeros at XI = -1, x2 = 0, and x3 = 1 (Figure 4.1-1).

next

Figure 4.1-1 The graph of the function fix) = (x+1)*x*(x-l). In order to introduce chaos into the safe world of this simple mathematical equation, we will apply the apparently harmless Newton method to this function. Sir Isaac Newton was thinking about a widely encountered problem in mathematics: to find the zeros of a function, for which only the formula is known. For equations of the first and second degree we learn simple methods of solution at school, and complicated and tedious methods are known for polynomials of degree 3 or 4. For degree 5 there is no simple expression for the solution in closed form. However, complicated equations like these, and others containing trigonometric or other functions,

Greetings from Sir Isaac

74

Dynamical Systems and Fractals

When we get close enough to the zero for our purposes, we stop the calculation. A criterion for this might be, for example, that f(x) is close enough to zero (If( I 10-6) or that x does not change very much (Ix,-xn+tl I 10-b). For further investigation we return to the above cubic equation fix) = x 3 - x

for which f’(x) = 3x2-1.

Then we compute the improved value xlnt from the initial value x, using xHl = x0 - (x,3-x,)/(3x,2-1). If we exclude2 the two irrational critical points x4 = -6(1/3) and x5 = 4(1/3), then from any starting value we approach one of the three zeros x1, x2, or x3. These zeros thus have the nature of attractors, because every possible sequence of iterations tends towards one of the zeros. This observation leads to a further interesting question: given the starting value, which zero do we approach? More generally: what are the basins of attraction of the three attractors xt , x2, and x3? The first results of this method will be shown in three simple sketches.

c X

Figure 4.1-3 Initial value x6 leads to attractor xt. We know the position of the axes and the graph of the function. At each iteration, we draw a vertical line and construct the tangent to the curve at that point. The result of Figures 4.1-3 to 4.1-S is not particularly surprising: if we begin with values x6, x7, or x8 close to an attractor, the the iteration converges towards that same attractor. By further investigation we can establish:

2These numbers cannot be represented exactly in the computer. The Newton method fails here because the first derivativef’(x,) = 0. Graphically, this follows because the tangents at these points

are horizontal, and obviously cannot cut the x-axis, because they run parallel to it.

73

Greetings from Sir haac

are of interest in many applications. Newton’s point of departure was simple: find the zeros by trial and error. We start with an arbitrary value, which we will call xn. From this the function value flx,J is calculated. In general we will not have found a zero, that is, fix,,) = 0. But from here we can ‘take aim’ at the zero, by constructing the tangent to the curve. This can be seen in Figure 4.1-2. When constructing the tangent we need to know the slope of the curve. This quantity is given by the derivative f ‘(x,), which can often be found easily.1

Graph of the function f(

x-axis Better value xi+1 Figure 4.1-2

Starting value

Xi

How Newton’s method leads to a zero

A further problem should be mentioned. If f ‘(xn) = 0, we find ourselves at a minimum, maximum, or inflexion point. Then we must carry out the analysis at the point X,&t.

The right-#angled triangle in Figure 4.1-2 represents a slope of height f(x,,) and width flx,)/f’(x,). From this last expression we can correct our approximate zero x,, to get a better value for the zero: x*1 = X” - f&J/f ‘(XJ An even better approximation arises if we carry out this calculation again with x,,+t as input. Basically Newton’s method is just a feedback scheme for computing zeros. ‘Even when f’(.r,) is not known as an explicit function we can approximate the differential quotient closely, by&,) = (@,+dx)-f(x,,-dx))/(2*ctx), where dx is a small number, e.g. 10e6.

76

We expect exceptions only where the graph minimum. But we have already excluded these If we now take a glance at Figures 4.1-6 at simple as it appears from the above. In the three very close initial values, namely x9 = 0.447 20, x10 = 0.447 25, and x11 = 0.447 30. We found these values by trial.

Dynamical Systems and Fmctals

of the function has a maximum or a points from our investigations. to 4.1-8, we realise that not everything is next sequence of pictures we begin from

Figure 4.1-6 Initial value x9 leads to attractor y.

Figure 4.1-7 Initial value x10 leads to attractor x1.

Greetings

from

75

Sir Isaac

Figure 4.1-4 Initial value x7 leads to attractor x2.

Figure 4.1-5 Initial value x8 leads to attractor x3. I

The basin of attraction of the attractor xt includes the region -co < x< x4 =

l

-J(1/3).

The basin of attraction of the attractor x3 includes the region x5 = J(1/3) < x < 03. In particular, this region is symmetrically placed relative to the basin of attraction of Xl-

+ +

The numbers near the origin belong to the basin of attraction of q. If we have found the attractor for a given initial value, then nearby initial values lead to the same attractor.

78

Dynamical

Systems and

Fmxals

be seen as high dark-grey rectangles. Can you reconstruct the results collected together after Figure 4.1-5 from Figure 4.1-9?

Figure 4.1-9 Graphical representation of the basins of attraction. Especially interesting are the chaotic zones, in which there is between the basins (of attraction). We show a magnified version of (for x-values in the range -0.6 < x < -0.4) in Figure 4.1-10. The 4.9-9 is stretched along the x-axis by a factor of 40. The graph of range is barely distinguishable from a straight line.

a rapid interchange the left-hand region section from Figure the function in this

Graph of function x-axis

-d.6

-0.5

Figure 4.1- 10 Basins of attraction (detail of Figure 4.1-9).

-0.4

77

Figure 4.1-8 Initial value x1 t leads to attractor x3. Despite their closeness, and despite the smooth and ‘harmless’ form of the graph of the function, the Newton method leads to the three different attractors. A sensible prediction seems not to be possible here. We refer to this ‘breakdown of predictability’ when we speak below of chaos. In all areas of daily life, and also in physics and mathematics, we make use of a great number of unspoken assumptions, when we describe things or processes. One of . the basic principles of physics is the causality principle.3 Recall that this states that the same causes lead to the same effects. If this rule did not hold, there would be no technical apparatus upon which one could rely. Interestingly, this precept is often handled in a very cavalier fashion. We formulate this generalisation as the strong causality principle: similar causes lead to similar effects. That this statement does not hold in general is obvious every Saturday in Germany when the lottery numbers are called - the result is not similar, even though the 49 balls begin each time in the same (or at least a similar) arrangement. Our definition of chaos is no more than this: A chaotic system is one in which the strong causality principle is broken.

In the next step - and indeed in the whole book - we will show that such chaos is not totally arbitrary, but that at least in some regions an order, at first hard to penetrate, lies behind it. In order to explain this order, in Figure 4.1-9 we have drawn the basins of attraction for the three attractors of the function f(x) in different shades of grey and as rectangles of different heights. Everywhere we find a short, medium-grey rectangle, the iteration tends towards the attractor x1. The basin of attraction of q can be recognised as the light-grey, medium-height rectangles; and all points which tend towards x3 can 3Causality:

logical consequence.

80

Dynamical Systems and Fractals

&l-g,-,

lim - = 6.0 = q . n+m g”+l -g”

Index n 1 2 3 4 5 6 7 8 9 10 11 12

gn

-0.577 350 269 189 626 -0.465 600 621 433 678 -0.450 201 477 782 476 -0.447 709 505 812 910 -0.477 296 189 979 436 -0.447 227 359 657 766 -0.447 215 889 482 132 -0.447 213 977 829 095 -0.447 213 659 221 447 -0.447 213 606 120 205 -0.447 213 597 269 999 -0.447 213 595 794 965

7.256 874 166 975 182 6.179 501 149 801554 6.029 219 709 825 583 6.004 851 109 839 370 6.000 807 997 292 021 6.000 134 651772 122 6.000 022 441 303 783 6.000 003 740 154 308 6.000 000 623 270 044 6.000 000 039 232 505 , -

Table 4-l The basin boundaries For x-values greater than zero the same result holds but now with positive g,-values. The resulting quotient is the same. A few words to explain these numbers are perhaps in order. + The number gt has the value gt = 4(1/3) = 3-112. This is worked out by applying school methods to investigate the curve f(x) = x3-x. At x = gl the first derivative f ‘(x) = 3x2- 1 takes the valuefYg~> = 0. The function fix) has an extreme value there, at which the derivative changes sign, so an increasing function becomes decreasing. Because the slope (first derivative) plays a special role in Newton’s method, this leads us to conclude that the points on the right and left of an extreme value belong to distinct basins of attraction. + For the limiting value of the gi we have: lim gn = $ = xg . n+m $ This value too can be expressed analytically.4 4Analytic

behaviour

is here intended in comparison with the numerical behaviour

found previously.

G~tingsfromSiIsaac

79

If we now investigate the basins shown by the grey areas we observe the following: On the outside we find the basins of x1 and x2. A large region from the basin of x3 has sneaked between them. Between the regions for x3 and x2 there is another region for x1. Between the regions for x1 and x2 there is another region for x3. Between the regions for x3 and x2 there is another region for x1,

l l l l l

and so on.

Graph of function

I -0.451

II -0.45

8I -0.449

II -0.448

II -0.447

x-axis I -0.446

Figure 4.1-11 Basins of attraction (detail of Figure 4.1-10). A further magnification by a factor of 40 in Figure 4.1- 11 shows the same scheme again, but on a finer scale. We have already met the scientific description of this phenomenon: self-similarity. The apparent chaos reveals itself as a strongly ordered zone. In a further investigation we will now set to work, calculating as closely as possible the points that separate the basins from each other. The corresponding program will not be described further here: it is left as an exercise. These boundary points will be denoted gj . Only the results are shown, in Table 4-1. I l

The first value is given by gf = -0.577 35.. . If x c gl then x belongs to the basin of xl.

+

If gt c x c g2 then x belongs to the basin of x3.

.

If g2 c x < g3 then x belongs to the basin of xl, and so on.

Using Table 4- 1 we have discovered a simple mathematical connection between the gj-values. Namely, the quotient tends to a constant value. In fact

82

Dynamical Systems

and

Fractals

&ill write out the important equations in full detail. In some motivation and generalisations a knowledge of complex numbers will prove useful. The theory of complex numbers also plays a role in physics and engineering, because of its numerous applications. This is undeniable: just look at a mathematics textbook on the subject. Independently we have collected together the basic ideas below. The complex numbers are an extension of the set of real numbers. Recall that the real numbers comprise all positive and negative whole numbers, all fractions, and all decimal numbers. In particular all numbers that are solutions of a mathematical equation belong to this set. These might, for example, be the solutions of the quadratic equation x2= 2, namely 42, the ‘square root of 2’, or the famous number A, which gives the connection between the circumference and diameter of a circle. There is only one restriction. You cannot take the square root of a negative number. So an equation like 3, -1 has no solutions in real numbers. Such restrictions are very interesting to mathematicians. New research areas always appear when you break previously rigid rules. The idea of introducing imaginary numbers was made popular by Carl Friedrich Gauss (1777-1855), but it goes back far earlier. In 1545 Girolamo Cardano used imaginary numbers to find solutions to the equations x+y = 10, xy = 40. Around 1550, Raphael Bombelli used them to find real roots to cubic equations. They are imaginary in the sense that they have no position on the number line and exist only in the imagination. The basic imaginary number is known as i and its properties are defined thus: i * i = -1. The problem of the equation 9, -1 is thus solved at a stroke. The solutions are x1 = i and x2 = -i. If you remember this, the rules of calculation are very straightforward. A few examples of calculation with imaginary numbers should clarify the computational rules:5 l 2i * 3i = -6. 0 d(-16) = f i*4 = f4i. l The equation x‘t = 1 has four solutions I, - 1, i, and -i: they are all ‘fourth roots’ of 1. l 6i-2i = 4i. Imaginary numbers can be combined with real numbers, so that something new appears. These numbers are called complex numbers. Examples of complex numbers are 2+3i or 3.141592 - 1.4142*i. 5You

will

find

further examples at the end of the chapter.

81

Greetings from Sir Isaac

For this purpose we use Figures 4.1-4 to 4.1-6. In all three cases the iteration runs several times almost symmetrically round the origin, before it decides on its broader course. In the extreme case we can convince ourselves, that there must exists a point xg, such that the iteration can no longer escape, and indeed that each iteration only changes the sign. After two steps the original value recurs. For xg we must have

f(xg) _ xg = r(xp) - -xg or

3

xg -xg x g= = -Xg * 3x;-1

Simplifying the equation, we get 5X82 = 1 whence the above expression. + As regards 4: Why this quotient always has the value q = 6, we cannot explain here. It puzzled us too. Further experiments make it possible to show that q is always 6 if we investigate a cubic function, whose zeros lie on the real line, and are equal distances apart. In other cases we instead find a value qA > 6 and a value qB c 6.

Computer Graphics Experiments and Exercises for 54.1 The only experiments for this chapter are, exceptionally, rather short. You can of course try to work out Table 4- 1, or similar tables for other functions. The next section will certainly be more interesting graphically.

4.2 Complex Is Not Complicated In previous chapters we have formulated the two basic principles of graphical phenomena that concern us: self-similarity and boundaries. The first concept we have encountered many times, despite the different types of representation that are possible in a Cartesian coordinate system. In previous figures the boundaries between basins of attraction have not always been clearly distinguishable. In order to investigate these boundaries more carefully, we will change our previous methods of graphical representation and switch to the twodimensional world of surfaces. We thus encounter a very ingenious and elegant style of graphics, by which we can also show the development of the boundary in two dimensions on a surface. No one would claim that what we have discussed so far is entirely simple. But now it becomes ‘complex’ in a double sense. Firstly, what we are about to consider is really complicated, unpredictable and not at all easy to describe. Secondly, we will be dealing with mathematical methods that have come to be called ‘calculations with complex numbers’. It is not entirely necessary to understand this type of calculation in order to generate the pictures: you can also use the specific formulas given. For that reason we

84

Dynamical Systems and Fractals

P = (x,y) of this Gaussian plane 6 represents a complex number z= x+i*y (Figure 4.2-l). Multiplication can be understood better graphically than by way of the above equation. To do this we consider not, as before, the real and imaginary parts of the complex number, but the distance of the corresponding point from the origin and the direction of the line that joins them (Figure 4.2-l). Instead of Cartesian coordinates (x,y) we use polar coordinates (r,cp). In this polar coordinate system, multiplication of two complex numbers is carried out by the following rule: If zt*q = 23, then rt*~ = r3 and (pr+cp2 = 93. We multiply the distances from the origin and add the polar angles. The distance ris described as the modulus of the number z and written r = I z I.

imaginary axis

real axis Figure 4.2- 1 A point in the Gaussian plane and its polar coordinates. What connection does the complex plane have with our mathematical experiments, with chaos, with computer graphics? The answer is simple. Until now the region in which we have calculated, and which we have drawn, has been a section of the real-number axis, from which the parameter k was chosen. We carried out our calculations, and drew the result, for each point of that section - as long as it remained within the limits of the screen. Now we let the parameter become complex. As a result the equations for calculating chaotic systems 6Translaror’s note: Gauss represented complex numbers on a plane in about 1811. In many countries the Gaussian plane is lrnown as the Argad diagram, after Jean-Robert Argand who published it in 1806. A Danish surveyor, Caspar WesselJ, has a greater claim than either, having independently described the idea in 1797. The above is the conventionally recognised trio: for some reason everyone seems to ignore the fact that John W&is used a plane to represent a complex number geometrically in his Algebra of 1673.

83

Greetings from Sir Isaac

A whole series of mathematical and physical procedures can be carried out especially elegantly and completely using complex numbers. Examples include damped oscillations, and the electrical behaviour of circuits that contain capacitors and resistors. In addition, deep mathematical theories (such as function theory) can be constructed using complex numbers, a fact that is not apparent when we discuss just the basics. All equations for the basic rules, which are important for the respresentation of boundary behaviour, can be expressed using elementary mathematics. We begin with the rule i*i = -1 and the notation z = a+i*b for complex numbers. Two numbers zt and q, which we wish to combine, are zt = a&band q = oti*d. Then the following basic rules of calculation hold: Addition

zt+q = (a+i*b)+(oti*d)

= (a+~) + i*(bM).

Subtraction

21-q = (a+i*b)-(&+d) = (a-c) + i*(b-d). Multiplication

zt*q = (ati*b)*(oti*d) = (a*c-b*d) + i*(a*&b*c). The squareis a special case of multiplication: zt2 = zl*zl = (a+i*b)2 = (9-d) + 2*i*a*b. Division

Here a small problem develops: all expressions that appear must be manipulated so that only real numbers appear in the denominator. For 1 1 -CT c+t*d 52 this can be achieved by multiplying by (c-i@, the complex denominator: c-i*d 1 c-i*d =-, -= c+i*d (c+i*d)*(c-i*d)

conjugate of the

C2td2

From this we get the rule for division: a*ctb*d . b*c-a*d z1 ati*b = -+I*-. -=cti*d z2 C2td2 C2td2 Furthermore, there is also a geometrical representation for all complex numbers and all of the mathematical operations. The two axes of an (x,y)-coordinate system are identified with the real and imaginary numbers respectively. We measure the real numbers along the x-axis and the imaginary numbers along the y-axis. Each point

86

Dynamical Systems

and

Fractals

Exercise 4.2-4 If all the previous exercise have been too easy for you, try to find a formula for powers. How can you calculate the number z = (a+i*b)p when p is an arbitrary positive real number? Exercise 4.2-5 Formulate all of the algorithms (rules of calculation) in this section in a programming language.

4.3 Carl Priedrich Gauss meets Isaac Newton Of course, these two scientific geniuses never actually met each other. When Gauss was born, Newton was already fifty years dead. But that will not prevent us from arranging a meeting between theirrespective ideas and mathematical knowledge. We transform Newton’s method into a search for zeros in the complex plane. The iterative equations derived above will be applied to complex numbers instead of reals. This is a trick that has been used in innumerable mathematical, physical, and technical problems. The advantage is that many important equations can be completely solved, and the graphical representations are clearer. The normally important real solutions are considered as a special case of the complex. Our starting point ($4.1) was f(x) =x3-x. For this the Newton method takes the form x,+1 =x, - (X,3-X,)/(3X,2-1). For complex numbers it is very similar: z,,+~ = I, - (z,S-z,)/(3z,2-1). Recalling that zn = x,+i*y,, this becomes 3 2 2 3 2*(x,-3x,ya+i*(3x,y,-y,)) 5l+1 =

3x:-3yi-l+i*6x,yn

Further calculations, in particular complex division, can be carried out more easily on a computer. The calculation has thus become a bit more complicated. But that is not the only problem that faces us here. Now it is no longer enough to study a segment of the real line. Instead, our pictures basically lie in a section of the complex plane. This twodimensional rectangular area must be investigated point by point. The iteration must therefore be carried out for each of 400 points in each of 300 lines.7 We know the mathematical result already from the previous chapter: one of the three data can vary from program to program and computer to computer. a screen of 400 x 300 pixels.

‘IThese

Most of

our pictures use

Greetings

85

from Sir lsaac

are especially simple. In particular we can represent the results directly in the complex plane. Depending on the shape of the computer screen we use a rectangular or square section of the plane. For each point in the section - as long as it remains within the limits of the scree:n - we carry out our calculations. The complex number corresponding to this point represents the current parameter value. After iteration we obtain the value 42) from the result of our calculation, which tells us how the corresponding screen point is coloured. Complex numbers aren’t so hard, are they? Or aren’t they?

Computer Graphics Experiments and Exercises for 54.2 Exercise

4.2-l

Draw on millimetre graph paper a section of the complex plane. Using a scale 1 unit = 1 cm, draw the points which correspond to the complex numbers z1 = 2-i*2, q = -OS+l*lS, and 5 = 2-i*4. Join these points to the origin. Do the same for the points q = zl+q and 3 = z3-zl. Do you recognise an analogy with the addition and subtraction of vectors? Exercise 4.2-2 The following connection holds between Cartesian coordinates (x,y) and polar coordinates with distance r and polar angle ‘p: ? = xzt-y2 and tan cp = y/x. Ifx=Oandy>(lI,thencp=90°. Ifx=Oandyc0,thencp=270°. If x = 0 and also y = 0, then r = 0 and the angle cp is not defined. Recall that for multiplication the following then holds: if zl*q = z3 then r1*r2 = r3 and cprtcp2 = ‘p3. Express this result in colloquial terms. Investigate ,whether both methods of multiplication lead to the same result, using the numbers in Exercise 4.2- 1. Exercise 4.2-3 In the complex . A number and . A number and l A number and

plane, what is the connection between: its complex conjugate? its square? its square root?

Dynamical Systems

and

Fractals

Figure 4.3-2 Section from Figure 4.3-l left of centre. Compared with the appearance on the real axis, which we have seen already, Figure 4.31 reveals something new. Jn many different places there appear ‘grape&e’ structures like Figure 4.3-2. An example appears magnified in Figure 4.3-3. Self-similarity does not just occur on the real axis in these graphical experiments. Jn general, where a boundary between two basins of attraction occurs, similar figures are observed, sprinkled ever more thickly along the border. The same section as in Figure 4.3-3 leads to the next picture, in a different experiment. In this drawing only points are shown for which it cannot be decided, after 12 iterations, to which basin they belong. Thus the white areas correspond to those which in the previous pictures are shown in grey. Their structure is somewhat reminiscent of various sizes of ‘blister’ attached to a surface. Further magnified sections reveal a similar scheme. The basins of attraction sprout ever smaller offshoots. One of the first mathematicians to understand and investigate such recursive structures was the Frenchman Gaston Julia. After him we call a complex boundary with self-similar elements a Julia ser.

Greetings from Sir Isaac

87

zeros xt, x2, x3 on the real axis will be reached.* This remains true even when the iteration starts with a complex number. The graphical result is nevertheless new. To show how the three basins of attraction fit together, we have shaded them in grey in Figure 4.3-1, just as we did in 34.1.

Figure 4.3-l The basins of attraction in the complex plane.9 Thus the basin of x1 is medium grey, that of x2 is light grey, and that of x3 is dark grey. All points for which it cannot be decided, after 15 iterations, towards which attractor they are tending, are left white. Along the real axis, we again find the various regions that were identified in $4.1. ‘Chaos’, as it first appeared to us in Figure 4.1-9, we recognise in the small multicoloured regions. We have defined chaos as the ‘breakdown of predictability’. The graphical consequence of this uncertainty is fine structures ‘less than one pixel in resolution’. We can investigate their form only by magnification. The interesting region, which we investigated on the real axis in Figures 4.1-9 to 4.1- 11, is shown in Figure 4.3-2 on a large scale. Again, self-similarity and regularity of the structure can be seen. 8We retain the names from 54.1, even though we are working with complex numbers z1 etc. This is permissible, because the imaginary parts are zero. 9The two outlined regions on the real axis and above it will be explored in more detail in the

following pictures.

90

Dynamical Systems and Fractals

To close this section, which began with a simple cubic equation and immediately led into ‘complex chaos’, we illustrate a further possibility, visible in Figure 4.3-1. , in graphical form. Instructions for the production of these pictures are to be found in the next chapter.

Figure 4.3-S Stripes approaching the boundary.

89

Greetings from Si Isaac

imagir realaxis

-

II -1.0

II -0.9

II -0.8

I -0.7

Figure 4.3-3 At the boundary between two basins of attraction. 4

-- 1.0

-- 0 . 9

-- 0.8

imaginary real axis -1.0

-0.9

-0.8

Figure 4.3-4 The boundary between two basins of attraction.

-0.7

92

Dynamical Systems and Fractals

5.1 Julia and His Boundaries We again state the question on the domains of influence of attractors. Where must we start the iteration, to be certain of reaching a given attractor? The precise boundaries between the initial zones should not be investigated. We are not exaggerating when we say that they are invisible. In order to get at least the attractors in the simplest possible fashion, we will use an arrangement as in Figure 5.1- 1.

zB

= -0.5 + 0.866 i 4imaginary axis 0

ZA= 1 h ”

zC

b real axis

= -0.5 - 0.866 i 0

Figure 5.1-1 Position of three point attractors in the Gaussian plane. The imaginary parts of zg and zcare irrational numbers. For instance

We will finish up at one of these three points from any initial value (except ~0 = 0) using the following iteration equation: 1

n + l 2, 3 n +- .

Z

3zt

Such points and such equations naturally don’t fall from out of the blue. This one arises, for example, if you try to use Newton’s method to find the complex zeros of the function* f(z) = 23-l. It is easy to prove that each of the points ZA, zg, zc defined in Figure 5.1-l satisfies ’ If you do not see the connection here, take another look at 54.1.

5 Complex Frontiers

Dynamical Systems and Fractals

94

preassigned bound epsilon, we say ‘we have arrived’.3 To formulate this test in Pascal we require a boolean function. It has the value true if we have already reached the relevant attractor, and otherwise the value false. For example, for the point z&e test becomes the following: Program Fragment 5.1-2 FUNCTION belongsToZc (x, y : real) : boolean; CONST epsqu = 0.0025; (* coordinates of the attractor zc *) xc = - 0 . 5 ;

yc = -0.8660254; BEGIN IF (sqr (x-xc)+sqr (y-yc) < = epsqu) THEN belongsToZc := true ELSE belongsToZc := false; END; (* belongsToZc *)

Thevariable epsqu is the square of the small number 0.05, xc and yc are the coordinates of the attractor ZC, and x and y are the working coordinates which will be modified and tested during the investigation. The calculation for the other attractors requires similar programs. In order to obtain an overview of the basins of the attractors and the boundaries between them, we explore point by point a section of the complex plane, which contains the attractors. We colour the initial point for the iteration series according to which basin it belongs to. We give the method for drawing the boundaries in the following Program Fragment. In a few places we have slightly modified Example 5.1-1, to make the algorithm quicker and more elegant. In particular we do not need to distinguish between x,, and xn+t in the contruction of the mathematical formula. Computers work with assignments, not with formulas. Program Fragment 5.1-3 PROCEDURE Mapping; WAR xRange, yRange : i n t e g e r ; x , y, deltaxPerPixe1, deltayPerPixe1 : real; BEGIN deltaxPerPixe1 : = (Right - Left) / Xscreen; deltayPerPixe1 : = (Top - Bottom) / Yscreen; 31n fact in Program Fragment 5.1-2 we compare the square of the distance with the square of epsilon, eliminating the need to extract a square toot.

Complex Frontiers

93

z3 = 1. We show this here for rg:

ThuszA,zg,zCi~e'ethethreecomplexcubef~~of~j~

We have already dealt with calculation rules for complex numbers in $4.2. If we apply Newton’s method, we get xi-yt-i*(2*xnyn)’ Z

n+l = $(xn+i*yn) +

222

3*(x,+y,)

*

Thus for the complex number zmt we have %+l ‘%+l + i*yn+1

so that we can ohtain equations for the real and imaginary parts x and y: 2

2x + X n+l gn

2

‘n-y, 2

22

3*(x,+y,)

’

Xn*Yn Y n+l =f ( Y,--) . (x;+Y;)

In Program Fragment 5.1-1, we denote the values xn and yn by xN and yN, etc. The instructions for the two iteration equations can in principle be found as follows: Program Fragment 5.1-1 (See also Program Fragments 5.1-2 and 5.1-3) ... XN : = xNplus1; : = yNplus1; P xNplus 1 : = 2*xN/3+ (sqr (xN) -sqr (yN) )

/ (3*sqr (sqr (xN) +sqr (yN) ) ) ; yNplus1 := 2*yN/3- (2*xN*yN) / (3*sqr (sqr (xN) tsqr (yN) ) ) ; ... Using these,whichever initial value z = x+i*y we start with, after suitably many iterations we encl up near one of the three attractors. We can recognise which by looking

at the distance from the known attractors. 2

If this distance is less than some

21f we do not know the attractors, we must compare the current value zn+t with the previous value

2,. If this is less than epsilon, we are finished.

96

Dynamical Systems

REPEAT compute; test; UNTIL (IterationNo = MaximalIteration) distinguish; END; (* JuliaNewtonComputeAndTest *)

and

Fractals

OR finished;

Now the procedure JuliaNewtonComputeAndTest is fornwlatedin reasonable generality, It makes use of four local procedures. The first sets up the values for the local variables: Program Fragment 5.1-5 PROCEDURE startVariableInitialisation; BEGIN finished := false; iterationNo := 0; xsq := sqr(x); Y% := sqr(y); distancesq := xsq + ysq; END (* startVariableInitialisation

*)

The next procedure does the actual computation. Program Fragment 5.1-6 PROCEDURE Compute; BEGIN IterationNo := IterationNo + 1; xTimesy := x*y; := sqr(distanceSq); distanceFourth denominator := distanceFourth+distanceFourthtdistanceFourth; X := 0.666666666*x t (xSq-ySq)/denominator; : = 0.666666666*y Y (xTimesy+xTimesy)/denominator; := sqr(x); ml := sqr(y); Y% := xsq + ysq; distancesq END;

95

Complex Frontiers

Y := 13ottom;

FOR yRange := 0 TO Yscreen DO BEGIN x := left; FOR xRange := 0 to Xscreen DO BEGIN IF JuliaNewtonComputeAndTest (x, y) THEN SetPoint (xRange, yRange); x := x + deltaxPerPixe1; Em); Y ::= y + deltayPerPixe1; END; END; (* Mapping *) In contrast to the. more linear structures of the previous chapter, we no longer compute a hundred points in each series. The 120 000 points of the chosen section4 obviously need more computing time. A complete calculation requires, in some circumstances, more thananhour. Theprocedure Mapping searchesthroughthe screen areaonepixel at a time. For each screen point it computes the universal coordinates x and y. It passes these variables to a functional procedure, which in this case is called JuliaNewtonComputeAndTest. We use such an unequivocal name to distinguish this procedure from others which play similar roles in later programs. The corresponding screen point is coloured, or not, according to the result of this function. TheprocedureMapping uses 7 global variables, which we already know from other problems: Left, Right, Bottom, Top, MaximalIteration, Xscreen, Yscreen. For a computer with 400 x 300 pixels on the graphics screen, we might for example set up the computation as follows: Xscreen:= 400; Yscreen := 300; Left := ->!.QRight:= 2.0; Bottom := -1S;Top := 1.5; Program Fragment 5.1-4 FUNCTION JuliaNewtonComputeAndTest (x, y : real) VAR IterationNo : integer; finished : boolean; xSq, ySq, xTimesy, denominator : real; distancesq, distanceFourth : real; BEGIN Start'JariableInitialisation; 4We here refer to a section of 400 x 300 pixels.

:

boolean;

98

Dynamical Systems and Fractals

equality condition is not fulfilled, so the iteration is stopped before the variable iterationNo getsthat high.

Figure 5.1-2 Boundary between the three basins after 15 iterations. If instead of the boundary we draw the basin of attraction of one of the three attractors, as in Figure 5.1-3, we can use the functional procedure belongsToZc defined in Program Fragment 5.1-2. Program Fragment 5.1-9 PROCEDURE distinguish BEGIN (* does the point belong to the basin of zC? *) JuliaNewtonTestAndCompute := belongsToZc (x,y) END; It is of course entirely arbitrary, that we have chosen to draw the basin of the attractor ZC. In Exercise 5.1-2 we give hints for computing the other two basins. Perhaps you can already guess what form they will take?

Complex

Frontiers

97

A few tricks have heen used so that the most time-consuming calculation steps, especially multiplication and division, are not carried out twice. For example the expression fX is not coded as 2*x/3. In this form, the integer numbers 2 and 3 must first he converted to real numbers every time the procedure is used. Further, a division takes more time than a multiplication. So a more efficient ‘expression is 0.666666666*x. After each iterative step we must test whether we have ‘arrived’ near enough to one of the attractors. Moreover, we must he careful that the numbers we are calculating with do not go outside the range within which the computer can operate. If that happens, we stop the calculation. Program Frag,ment 5.1-7 PROCEDURE test; BEGIN finished := (distancesq < l.OE-18) OR (distancesq > l.OE18) OR belongsToZa (x,y) OR belongsToZb (x,y) OR belongsToZc(x,y); END; Finally we must distinguish what should he drawns. The points which belong to the boundary are those which, after that maximal number of iterations, have not converged to any of the three attractors. Program Fragment 5.14 PROCEDURE distinguish; BEGIN (* does the point belong to the boundary? *) JuliaNewtonComputeAndTest := IterationNo = MaximalIteration; END; We interpret Program Fragment 5.1-8 as follows. We include all points in the boundary for which the computation, after a given number of iterations, has not reached anattractor. InFigureLl-2thismaximalIteration = 15. In all other cases the 5We can carry out the investigation most easily when the computer has a colour graphics screen. Then each basin of attraction is given a colour, and the boundaries are easily visible.

100

Dynamical Systems and Fractals

Program Fragment 5.1.10 PROCEDURE distinguish; BEGIN (* does the hoint reach one of the three attractors *) (* after an odd number of steps? *) JuliaNewtonComputeAndTest : = (iterationNo < maximalIteration) AND odd(iterationNo); END; PROCEDURE distinguish; BEGIN (* does the point reach one of the three attractors *) (* after a number of steps divisble by 3? *) JuliaNewtonComputeAndTest : = (iterationNo < maximalIteration) AND (IterationNo MOD 3 = 0); END;

Figure 5.1-4 Contour lines.

99

Complex Frontiers

Figure 5.1-3 Basin of the attractor ZC. In a different style of drawing, as in Figure 5.1-4, we take into account the number of iterations required to reach any particular one of the three atractors. A point is then coloured if this requires an odd number of iterations. In Figure 5.1-4 you should look for the three point attractors (see Figure 5.1-1). They are surrounded by three roughly circular areas. All points in these regions of the complex plane have already reached the attractor, to the relevant degree of accuracy, after one iteration. From there we see in turn alternating regions of black and white, from which we reach the attractor in 2, 3, 4, . . . steps. In other words, the black regions correspond to initial values which take and odd number of steps to reach an attractor. In this way we obtain pictures reminiscent of contour lines on a map. If you think of the attractors as flat valleys and the boundaries between them as mountain ranges, this interpretation becomes even better. The peaks become ever higher, the longer the computation, deciding to which attractor the point belongs, lasts. If the contour lines get too close together, there is always the possibility of drawing only every third or every fourth one of them.6

6

In the Program Fragment e.g. 7 MOD 3 = 1.

we use the

MOD

function of Pascal. It gives the remainder upon division,

Dynamical Systems and Fractals

Figure 5.1-6 The basins of the three attractors zA,

zB, ZC.

Peitgen and Richter, in Research Group in Complex Dynamics, Bremen (1984a), pp. 19,31, describe this phenomenon by equating the three basins of attraction with the territories of three superpowers on a fantasy planet: Three power centres have divided up their sphere of influence and have agreed to avoid simple boundaries with only two adjoining regions: each boundary point must be adjacent to all three countries. If the computer graphic did not show a solution, one would scarcely believe that it existed. The key to the trick is that everywhere two countries come next to each other, the third establishes an outpost. This is then in turn surrounded by tiny enclaves of the other powers - a principle which leads to ever smaller similar structures and avoids a flat line.’ These ‘similar structures’ are what we have already encountered as self-similarity: here

we meet them again. Meanwhile this behaviour has become so natural to us that it is no longer a surprise! When the basins of attraction seem so ragged, there is one thing in the picture that still hangs together: the boundary. Here we observe a member of an entirely new class of geometrical figures, a fmctal. This concept has been developed over the past twenty years by the France-Polish mathematician Ben&t B. Mandelbrot. By it he refers to structures which cannot be described by the usual forms such as lines, surfaces, or solids. On the one hand, the boundary in Figure 5.1-2 is certainly not a surface. For each

Complex Frontiers

101

PROCEDURE distinguish; BEGIN JuliaNewtonComputeAndTest : = (IterationNo = MaximalIteration) OR ((IterationNo < Bound) AND (IterationNo MOD 3 = 0)); END; The three variations show how you can combine these methods of graphical representation to give new designs (Figure 5.1-5). The global variable Bound should bcabouthalfasbigasMaximalIteration.

Figure 5.1-5 Every third contour line, and the boundaries, in a single picture. There is a further possibility for drawing the pictures which we will only sketch here (see Execise 5.1-8). It is possible to show all three basins in the same picture. Different grey tones represent the different basins (Figure 5.1-6). If you look at the basin of the attractor zc (Figure 5.1-3) it may not be at all clear how the regions within it are divided up. Near the attractor itself the region is a connected piece. But at the boundaries they seem to get increasingly confused with each other. The divison nevertheless exists: it only appears confused. We already know from the example in Chapter 4 that the basins of attraction can never overlap.

Dynamical Systems and Fractals

Figure 5.1-7

A Julia set with fivefold symmetry.

fractal point of view. Then we find about 300 to 1000 times as many small insects in the same space that a single creature, 10 times as big, would occupy. This has actually been verified experimentally: see Morse et al. (1985). Thus there are many more tiny insects on a plant than had hitherto been thought. The smaller the organisms, the larger the world in which they live.’ An entire series of physical processes, whose detailed description raises many other problems, are of a fractal nature. Examples include Brownian motion and the study of turbulence in the flow of gases and fluids. This is true even though natural fractals can obviously display self-similarity and piecewise crumpling only up to some limit, whereas mathematical fractals have these properties completely and at every level. As often happens in mathematics, parts of the scientific preparatory work had already been carried out some time ago. But the discoveries of the French mathematicans Pierre Fatou and Gaston Julia were already becoming somewhat forgotten. In honour of the French researcher who studied the iteration of complex functions prior to 1920, fractal boundaries (Figure 5.1-2) are known as Julia sets. The possibilities raised by the computer now make it possible, for the first time, to investigate this fundamental area. It is indisputably to the credit of the Bremen Research Group of H. 0. Peitgen and P. Richter to have excited attention - not only in the technical world - with the results of the ‘computer cookery’ of their work in graphics.

Complex Frontiers

103

point that we have investigated, after sufficiently many iterations, it can be assigned to one of the three attractors. Only the point (O,O), the origin, obviously belongs to the boundary. Therefore the boundary always lies between the screen pixels, and has no ‘thickness’. On the other hand, the boundary is certainly not a line. Try to work out its length! In any particular picture it looks as though this can be done. But if we magnify small pieces, we find a remarkable phenomenon: the more we magnify - that is, the more closely we look -. the longer the boundary becomes. In other words, the boundary is infinitely long and has zero width. To such structures, between’ lines and surfaces, mathematicians attribute a ftactd dimension which is not a whole number, but lies between 1 and 2. Two properties, closely related, are characteristic of fractals: + Self-similarity, that is, in each tiny piece we observe the form of the entire shape. I Irregularity, that is, there are no smooth boundaries. Lengths or areas cannot be determined. Once this concept had been drawn to the attention of researchers, they soon found many examples of it in Nature. The coastline of an island is a fractal from the geometric point of view. It is possible to read off the length of a coastline from a map with a given scale. But if we use a map with a different scale, that can change the result. And if we actually go to the beach, and measure round every rock, every grain of sand, every atom... we encounter the same phenomenon. The more closely we look, that is, the larger the scale of the map, the longer the coastline seems to be. Thus many natural boundaries, by the same principle, are fractal. Fractals with dimension between 2 and 3 are the main surfaces that will concern us. Every morning when we look in the mirror we notice that: l Skin is fractal - especially when one is ‘getting on in years’. It has the basic purpose of covering the body with the smallest possible surface. But for several other reasons a crumpled structure is preferable. It is even more obvious, when we leave the house: I Clouds, trees, landscapes, and many other objects, when viewed at a different level, appear fractal. To investigate these is the subject of rapidly growing research activity in all areas of natural science. The consequences of this discovery for biology are explained in Walgate (1985) p.76. For small creatures, for example insects on a plant, the living space grows in an unsuspected fashion. Consider as a model case two species, differing in size by a factor of 10. They must expand their population on one of the available surfaces. There should therefore be 100 times as many small creatures as large. But this argument takes on a different appearance if we think of the surface of a leaf from the

106

Dynamical Systems

and

Fractals

zg= -0.5+0.8660254* i and

ZC= -0.5 - 0.8660254 * i, see Figure 5.1-3. It is not a coincidence that the pictures resemble each other in various ways. ‘Ihe reason involves the equivalence of the three complex cube roots of unity. Exercise 5.1-3 Using the method of magnifying detail, investigate sections of Figures 5.1- 1 to 5.1-6. Choose regions that lie near boundaries. In all these cases we find selfsimilarity! Check that if we increase the number of iterations (and also increase the admittedly not short computation time) self-similar structures continue to appear. Exercise 5.1-4 If you want to apply Newton’s equations such as #-1 = 0 or 25-l of 1. These give the positions of the In general the nth roots of 1 are s = cos(*)

method with powers higher than 3, for example to = 0, you must know the appropriate complex roots attractors. given by

+ i*sin(*)

where k runs from 0 to n-l. Produce (with the aid of a computer program) a table of roots of unity z,, up to n = 8. Exercise 5.1-5 Investigate and draw Julia sets resulting from Newton’s method for z?-1 = 0 andzS-1 = 0. The mathematical difficulties are not insuperable. In Program Fragment 5.1-3 you must construct a modified function JuliaNewtonComputeAndTest. If you cannot solve this and the following exercises straight away, you can take a look at $6.4. There we summarise the important rules for calculating with complex numbers. Exercise 5.1-6 We apply Newton’s method and thereby get beautiful, symmetric computer graphics. Although the above examples seem to be well founded, they are certainly not to be thought of as ‘sacred’. As with our excellent experience in changing formulas in the previous chapter, so too we can change Newton’s method somewhat. Starting from Zp- 1, we insert in the equation

Complex Frontiers

105

Their pioneering work is well known internationally. The investigation of Newton’s method carried out above, for the equation 23-l = 0, can be applied equally well to other functions. To show you one result, Figure 5.1-7 indicates what happens for z5-1 = 0. You will find some hints about it in Exercises 5.1-4 and 5.1-5. In other exercises for this chapter we suggest experiments, leading to innumerable new forms and figures, which we have scarcely been able to explore ourselves. So varied are the possibilities opened up, that you are guaranteed to produce pictures that nobody has ever seen before!

Computer Graphics Experiments and Exercises for $5.1 Exercise 5.1-l Apply Newton’s method to the function 42) = 23-l. In the iteration equation ‘n+l = “n

-

f(z,)

-

fyz,)

insert the expressions for the functions fiz) and f’(z). equation Zn+l

What

=!z + 3 n

1 -

Show that this leads to the

.

3zf

For the complex numbers zA to zc in Figure 5.1-l compute the value of ~3. happens?

Exercise 5.1-2 On the basis of Program Fragments 5.1-l to 5.1-3, write a program that allows you to compute the basins and boundaries of the three attractors in Figure 5.1-3. Next investigate and draw the basin of the attractor ,??A = 1 with the iteration formula ‘n+l

1 djz +-. A n 3zi

Compare the resulting picture with those that you get for

108

Dynamical Systems and Fractals

IF (odd(row) AND (column MOD 4 = 0)) (* light grey *) OR (NOT odd (row) AND (column MOD 4 = 2)) THEN . . . IF (odd(row) AND odd(column)) OR (NOT odd (row) AND NOT odd(column))

(* medium grey *) THEN . . .

IF (odd(row) AND (column MOD 4 0 0)) (* dark grey *) OR (NOT odd (row) AND (column MOD 4 <> 2)) THEN ,.. .

5.2 Simple Formulas give Interesting Boundaries The various pictures of previous pages, and the innumerable sections and variations that you have derived from them, owe their existence to the calculating performance of the computer. Without this, no one would have made the effort to perform hundreds of thousands of completely different calculations - especially since it appears that the pictures become ever more ragged and complicated, the more complicated (and ragged?) the underlying formulas become. Again, this conjecture was first considered by B. B. Mandelbrot,7 who already knew in 1979-80 that the production of ‘richly structured’ pictures does not necessarily need complicated mathematical formulas. The important thing is for the iteration formula to be nonlinear. It can thus contain polynomials of the second or higher degree, or transcendental functions, or other such things. The simplest nonlinear iteration equation that leads to nontrivial results was suggested by Mandelbrot: Zn+l = zn2 - c. That is, we obtain a new member of the iteration series, by taking the previous one, squaring it, and subtracting from the square a number c. Until now, in previous chapters, we have investigated relatively complicated formulas, having one simple parameter, which can be changed. In contrast, in this Mandelbrot formula we have a very simple equation, containing not one but two parameters. These are the real and imaginary parts of the complex8 number c. The equation c=c&+l*Cimaginary

holds for c. For the complex number z we have as before z=x+i*y. In other words, we can write the formula as Zn+l =xn+1 + i * Yn+l

=ftzn>

= (xn2-yn2-crd)

’

+ i * (2 *x n*y -c 1. n imaginary

‘ISee the very readable article Fracfals and the Rebirth of Iterafion Theory in Peitgen and Richter (1986) p. 151. 8If the mathematical concepts of real, imaginary, and complex numbers still cause difficulty, we

again advise you to reread 54.2.

107

Complex Frontiers

Z

f&J n+l =Z”-f’o

the factor v(which is of course complex), obtaining: f(z,)

‘n+l = j! n -yq

*

First decide for yourself, without drawing, what the attractors will be. How far do they correspond to the complex roots of unity, that is, with the solutions to zP - 1 = O? Start with values v that lie near 1. Investigate the influence of v on the form of the Julia sets. Exercise 5.14 Investigate the changes that occur if we modify the formula by putting an imaginary summand i*w in the denominator: Z

n+l

=

j!

n

-

f(z,) i*w+f(z,)

’

Again work out, without drawing, what the attractors are. Draw the way the basins of attraction fit together. How far does the modification of the equation influence the symmetry of the corresponding pictures? Exercise 5.14 If you wish to work with grey tones, as in Figure 5.1-6, but these are not directly available on your computer, Figure 5.1-8 shows how to proceed. n n n n n n n

Figure pixels.

5.1-8

n w n n n n

n n n n n n n

n n n n n n

n n n n n n n

n n n n n n

Grey shades, normal size (left) and magnified, to show individual

To achieve this, not every point should be coloured, even when after calculation it is known in which basin it belongs. The drawing depends in which basin and also in which row or column of the screen a point occurs. In particular the conditions for drawing points should be:

110

Dynamical Systems and Fractals

poor. If lflz)lz stays below the value 100.0 after this number of steps, we declare the attractor to be ‘finite’ or effectively ‘zero’. In fact the situation is somewhat more complicated. Only in some cases is fiz) = 0 a limiting value. In other cases we encounter a different number z # 0, a so-called fixed point. It lies near the origin, and satisfies r(z) = z. Further, there are also attractors that are not single points, but which consist of 2,3,4,... or more points. For an attractor with the period 3 we have JVWN) = z. Despite these complications, we concentrate on only one important thing: that the attractor be finite, that is, that the series should not exceed the value 100.0. Each picture shows a section of the complex z-plane. We make the initial values ~0 the basis of our drawing. At each iteration z changes, and we give it the value computed forf(z) at the previous stage. The complex parameter c must be kept constant throughout a given picture. To repeat: there exist two attractors, zero and infinity, whose basins of attraction border each other. As has already been explained in $5.1, we can call these complex boundaries Julia sets. For the rest of this chapter we will be concerned with their graphical representation. Two different complex numbers ct and q generate two different Julia sets, and thus two different graphics! The variety of possible complex numbers produces an uncountable number of distinct pictures. The graphical appearance of these sets can be very varied too, because the form of the Julia set depends strongly on the value of the parameter c. For some of the pictures on the following two pages only the upper halves are drawn. They are symmetric about the origin, as can be seen in Figure 5.2-4 (lower left) and Figure 5.2-5 (upper right). In the series Figures 5.2-l to 5.2-8, the complex parameter c takes the values cl = O.l+O.l*i,q=O.2+0.2*i ,..., ~=0.8+0.8*i. We start with c = 0, surely the simplest case. Without a computer it is easy to see that the boundary is the unit circle. Each z-value, whose modulus is greater than 1, has m as an attractor. Each value 1 z 1~ 1 has 0 as attractor and should be drawn. We also colour the points with I z I = 1 since these too lead to a finite attractor. In terms of contours nothing much can be distinguished in this case, and we do not give a picture. But in the majority of cases, when we change c, the resulting picture yields contours. If c is increased in steps of 0.1 + 0.1 * i, we get in turn Figures 5.2-l to 5.2-8. A program to generate these figures obviously has certain parts in common with the graphics programs that we have already encountered (see Program Fragment 5.2-2). The remainder can be found in Program Fragment 5.1-3. Make the procedure now called JuliaComputeAndTest call theprocedureMapping . The surrounding program must supply the global variables cRea1 and cImaginary with suitable values. In comparison with Program Fragment 5.2-l a small improvement has been made.

Complex Frontiers These formulas can be set up within a Pascal program: Program Fragment 5.2-1 ... : = ,sqr(x) xsq Y% Y X

:= ,sqr (y) : = 2*x*y - cImaginary : = xSq - ySq - cRea1

... It is important to keep these statements in the given order, or else information will get lost.9 In particular, contrary to alphabetical order and other custom, we must Fist compute the value of y and then that for x (because x appears in the equation for y). Just like those for Newton’s method, these iteration formulas seem to be fairly harmless and not very complicated. But it is not so easy to grasp the possibilities for investigation that arise when a single parameter is changed. Not only the components of c play a role, but also the initial value of z, the complex number q= xo+i*yo. Thus we have four quantities to change and/or draw, namely On a sheet of paper we can show only two dimensions, so we must choose two out of the four as the basis of our drawing. As in the previous chapter these are the components x0 and yo of the (complex initial value ZQ. The computation of these pictures takes the following form. The position of a point on the screen (in screen coordinates) represents the components xc and yo (in universal coordinates). For a given value c=creaI+l*cimaginaiy the iteration is carried out. As a result, x and y change, and with them z. After a given number of iterations we colour the point corresponding to z according to the result. If it is not possible to use different colours, we can still use black-and-white or grey tones. The method is then repeated for the next value of ~0. The Mandelbrot formula is so constituted that it has only two attractors. One of them is ‘infinite’. By the attractor ‘co’, we mean that the series of numbers f(z) exceeds any chosen value. Since for complex numbers there is no meaningful concept of larger/smaller, we understand by this that the square of the modulus, lflz)12, exceeds any given value after sufficiently many steps. It does not matter much which value, and we take for this bound the number 100.0 (defined as a real number so that the comparison does not take too long). ThevariableMaximalIteration can be seen as a measure of how much patience we have. The bigger this number, the longer the calculation takes, and the longer we must wait for the-picture. But if Maximal Iterat ion is too small, the drawing is very %ou will still get interesting pictures -but not the ones intended.

112

Dynamical Systems and Fractals

Figures 5.2-5 to 5.2-8 Julia sets. As a result we save one multiplication per iteration and replace it by an addition, which is computedsignificantlyfaster.

Complex Frontiers

Figures 5.2-l to 5.2-4 Julia sets.

111

114

DynamicalSystemsandFractak

compute; test; UNTIL (iterationNo = maximalIteration) distinguish; END; (* JuliaComputeAndTest *)

OR finished;

We recognise familiar structures in the Program Fragment. In the main part the screen section is scanned point by point and the values of x and y passed to the functionalprocedure JuliaComputeAndTest. Thesenumbersarethestatingvalues x0 and yo for the iteration series. The global constants cRea1 and cImaginary control the form of the set that is drawn. Each new pair of numbers generates a new picture! For mathematicians, it is an interesting question, whether the Julia set is connected. Can we reach every point in the basin of the finite attractor, without crossing the basin of the attractor w? The question of connectedness has been answered in a difficult mathematical proof, but it can be studied rather more easily with the aid of computer graphics. In Figures 5.2-7 and 5.2-8 we certainly do not have connected Julia sets. The basin of the attractor 00 can be seen from the contour lines. It cuts the Julia set into many pieces. In Figures 5.2-l to 5.2-5 the Julia set is connected. Is this also the case in Figure 5.2-6? We ask you to consider this question in Exercise 5.2- 1. As another example we will demonstrate what effect an extremely small change of c can have on the picture of the Julia set. We choose for the two parameters cl and ~2 the following values, which differ only by a very tiny amount: cl = 0.745 405 4 + i*O.113 006 3 q = 0.745 428 0 + i*O.113 009 0

Figures 5.2-9 and X2-10 Julia sets for c1 and q. In both cases the Julia sets appear the same (Figures 5.2-9, 5.2-10). The pictures that follow are drawn with contour lines, so that the basin of the attractor w can be

113

Complex Frontiers

Below we describe a complete functional procedure JuliaComputeAndTest, containing all relevant local functions and procedures. Frogram Fragment 5.2-2 FUNCTION JuliaComputeAndTest (x, y : real) : boolean; VAR iterationNo : integer; xSq,, ySq, distancesq : real; finished : boolean; PROCEDURE StartVariableInitia lisation; BEGIN finished := false; iterationNo := 0; xsq := sqr(x); ySq := sqr( Y) ; distancesq := xsq + ysq; END; (* startVariableInitialisation *) PROCEDURE compute; BEGIN iterationNo := iterationNo + 1; ::= x * Y YJ Y : = y + y - cImaginary; x ::= xSq - ySq - cRea1; xsq := sqr(x); ysQ := sqr(y); distancesq := xSq + ySq; END; (* compute *) PROCEDURE test; BEGIN finished := (distancesq END; (* test *)

>

bound);

PROCElXJRE distinguish; BEGIN (* does the point belong to the Julia set? *) JuliaComputeAndTest := iterationNo = maximalIteration; END; (* distinguish *) BEGIN (* JuliaComputeAndTest *) startVariableInitialisation; REPEAT

116

Dynamical Systems and Fractals

Figure 5.2-13 Julia set for ct. Section from Figure 5.2-12.

Figure 5.2-14 Julia set for q. Section corresponding to Figure 5.2-13. The extreme 6000-fold magnification in Figure 5.2-15 (for cl) and Figure 5.216 (for ~2) confirms the distinction. ‘Ihe stripes indicating the basin of attraction of m are connected together in Figure 5.2- 15 from top to bottom. At this point the figure is divided into a left and a right half. As a result the Julia set is no longer connected. It is different for q in Figure 5.2-16. The basin of attraction of m ‘silts up’ in ever more tiny branches, which do not touch each other. Between them the other attractor holds its ground. We must magnify the original Figures 5.2-9 and 5.2-10, with an area of about 60 cm2, so much that the entire figure would cover a medium-sized farm (21 hectares). Only then can we notice the difference.

342

Dynamical Systems and Fmctals

store (F, 0); y += deltayPerPixe1;

/* at the end of each row */

I I /* end: problem-specific procedures */ /* -_----__-_-_-_____-_ application --------------____ /* ----------------------- main

X/

-----------------------*/

/* begin: procedures of main program */ void hello0 { printf("\nComputation of picture data 'I); pr-ntf (“\n------------------------11);

void Initialiseo (. printf ("Left printf ("Right printf ('Bottom printf ("Top printf ( "Maximal /* I

insert

further

> 'I); scanf("%lf", &Left); > 'I); scanf("%lfq', &Right); > I'); scanf ("%lf", &Bottom); > 'I); scanf ("%lf", &Top); Iteration > 'I); scanf ("%lf", &MaximalIteration ); inputs here */

void ComputeAndStore; { Enterwritefile

(&F,

"IntCoded");

Mapping ( ) ;

ExitWriteFile

(F);

I /* end: procedures of main program */ /* ----------------------- main ---------------------main0 /* main program */ Hello(); Initialiseo; ComputeAndDisplay(); 1

*/

F’ascal

341

and the Fig-trees

/* StartVariableInitialisation */ finished = False; iterationNo = 0; x = x0; y = yo; xSq = sqr(x); $32 = sqr(y) ; distanceSq = xsq + ysq; do { /* compute */ iterationNot+; y = x*y; y = yty-cImaginary; x = xSq - ySq -cReal; xSq = sqr(x); ySq = sqr (Y) ; distancesq = xsq + ysq; /* test */ finished = (distancesq > Bound); ) while (iterationNo != MaximalIteration && !finished); /* distinguish, see also Program 11.5-1 */ return iterationNo; tundef sqr

void

Mapping

()

int xRange, yRange; double x, y, deltaxPerPixe1,

deltayPerPixe1;

deltaxPerPixe1 = (Right - Left) / Xscreen; deltay PerPixel = (Top - Bottom) / Yscreen; x0 = 0.0; yo = 0.0; y = Bottom; for (yRange = 0; yRange < Yscreen; yRangett){ x= Left; for (xRange = 0; xRange < Xscreen; xRangett){ store (F, MandelbrotComputeAndTest (x, y)); x t= deltaxPerPixe1;

344

Dynamical Systems and Fmctals

t fread(number,

sizeof(int),

1, F);

(F, number); IntFile F; int number;

void store

fwrite(&b=number,

sizeof(int),

1, F);

main0 EnterReadFile EnterWriteFile

(&in, "IntCoded"); /* Integer encoded */ (&out, "RLIntDat"); /* RL encloded Integer */ while (!feof(in)) ( quantity = 1; ReadIn (in, &colour); if (!feof(in)) ( do( ReadIn (in, &done); if (done != 0) if (done == colour) quantity++; else ( store (out, quantity); store (out, colour); colour = done; quantity = 1; ) while (done != 0 && !feof(in)); store (out, quantity); store (out, number); store (out, 0);

ExitReadFile ExitWriteFile

(in); (out);

Pascal

343

and the Fig-trees

Program 12.3.2 (Compress to int; see 11.5-3) /* CompressToInt, Program 11.5-3 in C */ #include <stdio.h> #define Stringlength 8 typedef FILE *IntFile; typedef char String8 [Stringlength]; String8 Dataname; IntFilein, Out; int quantity, colour, void EnterReadFile IntFile *F; string8 FileName; *F

=

(F, Filename)

fopen(Filename,

void EnterWriteFile IntFile *F; string8 FileName;

"r");

(F, FileName)

*F = fopen(FileName,

void ExitReadFile(F); IntFile F; fclose(F);

void ExitWritefile(F); IntFile F; fclose(F);

void ReadIn(F, IntFile F; int *number;

done ;

number)

"w");

346

Dynamical Systemsand Fractals

void ReadIn (F, number) IntFile F; int *number; fread(number,

sizeof(int),

1, F);

I

void store (outText, CharFile outText; int number;

number)

if (number == 0) fputc('\n', outText); else I fputc(CharTable[number/64], outText); fputc (CharTable[number % 641, outText);

void InitTableO int i; for (i = 0; i < 64; if (i < 10) CharTable[i] = else if (i < 36) CharTable[i] = else if (i < 62) CharTable[i] = else if (i == 62) CharTable[i] = else if (i == 63) CharTable[i] =

i++) ( '0' + i; '0' + i + 7; '0' + i + 13; '>' '?'

main0 InitTableO; EnterReadFile (&in, ' 'RLIntDat"); EnterWriteFile (&outText, "RICharDat'); while (!feof(in)) I

345

PascalandthePig-trees

Program 12.3-3 (Transfer int to char, see 11.5-5) /* TrarsferIntToChar, Program 11.5-5 in C */ #include <stdio.h> #define

Stringlength

8

typedef FILE*IntFile; typedef FILE*CharFile; typedef charString8[Stringlength]; IntFile in; CharFile outText; int quantity, colour; char CharTable[641; String8 DataName; void EnterReadFile IntFile *F; String8 FileName;

(F, FileName)

*F = fopen(Filename,

void EnterWriteFile CharFile *F; String8 FileName; *F

=

(F, FileName)

fopen(Filename,

void ExitReadFile IntFile F;

(F)

fclose (F);

void Exitwritefile CharFile F; fclose (F);

"r");

(F)

"w");

Dynamical Systems and Fnwals

348

(”

(*

-----------------------“TILIT~----------------------------*)

BEGIN: Useful Subroutines *) PROCEDURE ReadReal (information : real); BEGIN write (information); readln (value); END; PROCEDURE

ReadInteger :

:

STRING;

(information integer);

:

VAR

STRING;

value

VAR

value

BEGIN write (information); readln (value); END; PROCEDURE

ReadString :

(information string);

:

STRING;

BEGIN write (information); readln (value); END; PROCEDURE

InfoOutput (information : STRING); BEGIN writeln (information); writeln; END; PROCEDURE CarryOn (information : STRING); BEGIN write (information, ' hit '); readln END; PROCEDURE CarryOnIfKey; BEGIN REPEAT UNTIL KeyPressed END;

VAR

value

Pascal and the Fig-trees

347

ReadIn (in, &quantity); if (quantity == 0) store (outText, 0); else { store (outText, quantity); readin (in, &colour); store (outText, colour);

ExitReadFile (in); ExitWriteFfile (outText);

UNIX is in particular available on the Those were the hints for UNIX. Macintosh II, which brings us to another operating system and another computer family: the Macintosh.

12.4 Macintosh Systems There is an enormous range of Pascal implementations for the Macintosh family of computers, all very suitable for computer graphics experiments. They include Turbo Pascal (Borland), Lightspeed Pascal (Think Technologies), TML-Pascal (TML Systems), and MPW (Apple), the Apple development system on the Macintosh. Of course the programs can also be written in other programming languages such as C or Modula II. We now give the corresponding Reference Program for one of the cited implementations. Program 12.4- 1 (Turbo Pascal reference program for Macintosh) PROGRAM EmptyApplicationShell; (* Turbo Pascal on Macintosh *) USES MemTypes, QuickDraw; CONST Xscreen = 320; (*e.g. 320 points in x-direction Yscreen = 200; (*e.g. 200 points in y-direction VAR PictureName : string; Left, Right, Top, Bottom : real; (* include additional global variables here *) Feedback : real; Visible, Invisible : integer;

*) *)

350

Dynamical Systems and Fractals

DrawUniversalLine (xu, yu : real); 'VAR xs, ys : real; BEGIN xs := (xu - Left) * Xscreen/(Right - Left); YS := (yu- Bottom) * Yscreen / (Top - Bottom); DrawLine (round(xs), round(ys)); END;

PROCEDURE

PROCEDURE TextMode; t* Insert machine-specific graphics commands here ") BEGIN GotoXY(1,23); Text Mode -----------------'); writlen (' _-_----___--END; PROCEDURE GraphicsMode; t* Insert machine-specific graphics commands here BEGIN ClearScreen; END; PROCEDURE EnterGraphics; BEGIN writeln ('To end drawing hit write ('now hit I); readln; GotoXY(1,23); writeln(‘-------------- Graphics Mode CarryOn('BEGIN GraphicsMode; END;

*)

');

---------------a);

:I);

PROCEDURE ExitGraphics BEGIN (*machine-specific actions readln; ClearScreen; TextMode; END;

to

exit

from

Graphics

(END: Graphics Procedures *) (-------------- m.----------GRAPHIC,---------------------------*)

Mode*)

349

F’ascal and the Fig-trees

PROCEDURE Newlines (n : integer); via 1 : integer; BEGIN FOR i := 1 TO n DO writeln; EbJD; (* END: Useful Subroutines *) t* -------------------------UTILITY------------------------------*) (*

------------------------GRAPHICS--G--- --------------------*)

(* BEGIN:

Graphics

Procedures *)

PROCEDURE SetPoint (xs, ys : integer); BEGIN t* Insert machine-specific graphics commands here moveto (xs, Yscreen - ys); line (0,O) END; PROCEDURE SetUniversalPoint (xu, VAR xs, ys : real; BEGIN xs := (xu - Left) * Xscreen / YS := (yu - Bottom) * Yscreen SetPoint (round(xs), round(ys) ENDi

*I

yu: real);

(Right - Left); / (Top - Bottom); );

PROCEDURE GoToPoint (xs, ys : integer); BEGIN t* Insert machine-specific graphics commands here moveto (x3, Yscreen - ys); END;

“)

PROCEDURE DrawLine (xs, ys : integer); BEGIN (" Insert machine-specific graphics commands here lineto (xs, Yscreen - ys); m;

“1

Dynamical Systems and Fractals

352

PROCEDURE ComputeAndDisplay; BEGIN EnterGraphics; FeigenbaumIteration; ExitGraphics; END; (*---------------------------MAIN-------------------------------

(*

BEGIN:

Procedures

of

Main

Program *)

PROCEDURE Hello; BEGIN TextMode; InfoOutput ('Calculation of InfoOutput (I--------------------'); Newlines CarryOn Newlines ESJD;

“)

‘);

(2); ('Start :I); (2);

PROCEDURE Goodbye; BEGIN CarryOn ('To stop : '); END; (*

END: Procedures of Main program *)

(“---------------------------MAIN------------------------------

,c)

BEGIN (* Main Program *) Hello; Initialise; ComputeAndDisplay; Goodbye; END. Of course all of this also works with Include-Files. Compare this program with the reference program from $12.2. After the start of the program a window appears with the name of the main program. This window is simultaneously a text and graphics window. That is, not only characters but also the usual graphics commands in Turbo Pascal such as ClearScreen

351

Pascal and the Fig-trees

(-----------------------

AppLI~TION---------------------*)

(BEGIN: Problem-specific procedures *) (* useful functions for the given application

problem

")

FUNCTION f(p, k : real) : real; BEGIN f := p + k * p * (l-p); END; PROCEDURE FeigenbaumIteration; VAR range, i: integer; population, deltaxPerPixe1 : real; BEGIN deltaxPerPixe1 := (Right - Left) / Xscreen; FOR range := 0 TO Xscreen DO BEGIN Feedback := Left + range * deltaxPerPixe1; population := 0.3; FOR i := 0 TO Invisible DO f(population, Feedback); population := FOR i := 0 TO Visible DO BEGIN SetUniversalPoint (Feedback, population); population := f(population, Feedback); END; END; END; (* END: Problem-specific procedures ("-----------------------APPLICATION---------------------PROCEDURE Initialise; BEGIN ReadReal ('Left >'r ReadReal ('Right >I, ReadReal ('Top >'r ReadReal ('Bottom >'r ReadInteger ('Invisible >'r ReadInteger ('Visible >'r (* possibly further inputs *) ReadString ('Name of Picture >', END;

Left); Right); Top) ; Bottom); invisible); visible); PictureName);

") ")

Dynamical Systems and Fractals

354

Program 12.4-2 (Lightspeed Pascal reference program for Macintosh) PROGRAM EmptyApplicationShell; (* Lightspeed Pascal Macintosh *) (* possible graphics library declarations here *) U S E S UtilGraph; (* include further global variables here *) VAR Feedback: real; Visible, Invisible : integer; PROCEDURE Hello; BEGIN (* as usual *) ... END; PROCEDURE Goodbye; BEGIN CarryOn ('To stop : '1; END; (" ---------------------APPLICATION-------------------------------*) (* BEGIN: Problem-specific procedures *) (* useful functions for the given application FUNCTION f(p, k : real) : real; BEGIN f := p + k * p * (l-p); EM>; PROCEDURE FeigenbaumIteration; VAR range, i: integer; population, deltaxPerPixe1 BEGIN (* as usual *) ... END; PROCEDURE Initialise; BEGIN (* as usual *) ... END;

: real;

problem

*)

353

Pascal and the Fig-trees

and GotoXY apply. It can now be given the appropriate inputs. On logical grounds we still distinguish here between Text MO de and GraphicsMode. In practice we have implemented this in such a way that text called from the procedure TextMode is written in the 22nd row and rolls upwards. When the drawing is finished, you should see the following picture: EmptyApplicationShelI

Figure 12.4-1 Turbo Pascal reference picture. After the drawing is finished the blinking text cursor appears in the left upper comer. You can print out the picture with the key combination <Shift> <4> or make it into a MacPaint document with <Shift> <3>. If you then press the key further commands can be given. Next, some hints on turtle graphics. We described this type of computer graphics experiment in Chapter 8. You can implement your own turtle graphics as in the solutions in 011.3, or rely on the system’s own procedures. In Turbo Pascal on the Macinstosh, as in the MS-DOS version, a turtle graphics library is implemented. Read the description in Appendix F, Turtle Graphics: Mac graphics made easier in the Turbo Pascal Handbook, editions after 1986. In addition to Turbo Pascal there is another interesting Pascal implementation. In Lightspeed Pascal it is not possible to modularise into pieces programs that can be compiled with the main program in the form of Include-Files. In this case we recommend that you use the so-called unit concept. You can also use units in the Turbo Pascal version. In the main program only the most important parts are given here.

Dynamical Systems and Fmctals

356

PROCEDURE Newlines (n : integer); -----------------------UTILITY --------------------------------------------GF?JQBI(-.S -----------------------t* PROCEDURE InitMyCursor; PROCEDURE SetPoint (xs, ys : integer); PROCEDURE SetUniversalPoint (xw, yw : real); PROCEDURE DrawLine (xs, ys : integer); PROCEDURE DrawUniversalLine (xw, yw : real); PROCEDURE TextMode; PROCEDURE GraphicsMode; PROCEDURE EnterGraphics; PROCEDURE ExitGraphics; -----------------------(" ---------------------mG~~IC~ (X

IMPLEMENTATION UTILITY----------------u--X) (" _----__------~----~~~~(* BEGIN: Useful Subroutines *) PROCEDURE ReadReal; BEGIN write (information); readln (value); END; PROCEDURE ReadInteger; BEGIN write (information); readln (value); END; PROCEDURE ReadString; BEGIN write (information); readln (value); END; PROCEDURE InfoOutput; BEGIN writeln (information); writeln; END; PROCEDURE CarryOn; BEGIN write (information, ' hit ');

") ")

*)

Pascal and the Fig-trees

355

PROCEDURE ComputeAndDisplay; BEGIN EnterGraphics; FeigenbaumIteration; ExitGraphics; END; (* END: Problem-specific procedures *) ("-------------------------APPLICATION----------------------") BEGIN (* Main Program *) Hello; Initialise; ComputeAndDisplay; Goodbye; END. In the unit Ut ilGraph we put the data structures and procedures that always remain the same. You can comfortably include all data structures that are global for all programs in such a unit. UNIT UtilGraph; INTERFACE CONST Xscreen = 320; (* e.g. 320 points in x-direction *) Yscreen = 200; (* e.g. 200 points in y-direction *) VAR CursorShape : CursHandle; PictureName : STRING; Left, Right, Top. Bottom : real; (*

-----------------------

PROCEDURE

ReadReal

UTILITY

----------~~~~~_________

(information : STRING; VAR value : real); PROCEDURE ReadInteger (information : STRING; VAR value : integer); PROCEDURE ReadString (information : STRING; VAR value : STRING); PROCEDURE InfoOutput (information : STRING); PROCEDURE CarryOn (information : STRING); PROCEDURE CarryOnIfKey;

“)

358

Dynamical Systems and Fmctals

PROCEDURE DrawLine (xs, ys : integer); BEGIN lineto (xs, Yscreen - ys); END; PROCEDURE DrawUniversalLine (xu, yu : real); VAR xs, ys : real; BEGIN xs := (XU - Left) * Xscreen/(Right - Left); YS := (yu - Bottom) * Yscreen / (Top - Bottom); DrawLine (round(xs), round(ys)); END; PROCEDURE TextMode; (" Insert machine-specific graphics commands here CONST delta = 50; VAR window : Rect; BEGIN SetRect (window, delta, delta, Xscreen+delta, Yscreen+delta); SetTextRect (window); (* Lightspeed Pascal *) ShowText; =;

"1

PROCEDURE GraphicsMode; *) t* Insert machine-specific graphics commands here CONST delta = 50; VAR window : Rect; BEGIN SetRect (window, delta, delta, Xscreen+delta, Yscreen+delta); SetDrawingRect (window); ShowDrawing; InitMyCursor; (* initialise WatchCursorForm *) SetCursor(CursorShape""); (* set up WatchCursorForm *) END; PROCEDURE EnterGraphics; BEGIN writeln ('To end drawing

hit

');

PascalandtheFig-trees

357

readln; END; PROCEDURE CarryOnIfKey; BEGIN REPEAT UNTIL button; END;

(*

Lightspeed

Pascal

*)

PROCEDURE Newlines; WJR i : integer; BEGIN FORi:=lTOnDO writeln; END; (*

END:

Useful

Subroutines

*)

(”

-------------------------“TILITy--------------------------*)

(”

------------------------G-~ICS-------------------------*)

(*

BEGIN:

Graphics Procedures *)

PROCEDURE InitMyCursor; BEGIN CursorShape := GetCursor(WatchCursor); END; PROCEDURE SetPoint (xs, ys : integer); BEGIN t* Insert machine-specific graphics commands here moveto (xs, Yscreen - ys); line (0,O) END; PROCEDURE SetuniversalPoint (xu, yu: real); VAR xs, ys : real; BEGIN := - Left) * Xscreen / (Right - Left); - Bottom) * Yscreen / (Top - Bottom); YS := SetPoint (round(xs), round(ys)); xs

(XU

(YU

*)

Dynamical Systems and Fractals

360

r 6 File Edit Proiect Run Debua Windows FB-LS-Pascal-Referenz Text sJ:o Sk! Representation of ~--~~~~~~-~~---L---_--~~~~~ Se' end To start: hit key Pro beg Left:

Wr: Wr: Wr: Re Grb end

Right Top Bottom Invisible Visible PictureName

7:;

>1.8 >3

>o >1.5 >50 >50

Feigenbaum

Reference

To finish hit

bTz Et Say

n 1

Figure 12.4-2 Screen dialogue.

MPW Pascal MPW Pascal is a component of the software development environment ‘Macintosh Programmer’s Workshop’, and was developed by Apple. It is based on ANSI Standard Pascal. It contains numerous Apple-specific developments such as the SANE library. SANE complies with the IEEE standard 754 for floating-point arithmetic. In addition MPW Pascal, like TML Pascal, contains facilities for object-oriented programming. MPW Pascal, or Object Pascal, was developed by Apple in conjunction with Niklaus Wirth, founder of the Pascal language.

MacApp MacApp consists of a collection of object-oriented libraries for implementing the standard Macinstosh user interface. With MacApp you can considerably simplify the development of the standard Macintosh user interface, so that the main parts of Mac programs are at your disposition for use as building blocks. MacApp is a functional (Pascal) program, which can be applied to an individual program for particular extensions and modifications.

Pascal

andtheFig-trees

359

write ('now hit I); readln; writeln('--------------Graphics MO& --------------t); CarryOn('BEGIN :I); GraphicsMode; END; PROCEDURE ExitGraphics; BEGIN (*machine-specific actions to exit from Graphics Mode*) InitCursor (* call the standard cursor *) (* graphics window no more frozen *) readln; SaveDrawing(PictureName); (* store pit as MacPaint document *) TextMode; (* text window appears *) writeln('-----------TextMode--------------'); END; (* END: Graphics Procedures *) (" _-----___-------------GRAPHI,-S-------w--------------v-") END

If you run this program then the following two windows (Figure 12.4-2) appear one after the other. After inputting the numerical value and pressing , the ‘drawing window’ of Lightspeed Pascal appears, and the Feigenbaum diagram is drawn. While it is being drawn the ‘watch cursor’ - the cursor that resembles a wristwatch - is visible. When the drawing is finished the normal cursor appears. Press to give further commands. As well as Turbo Pascal and Lightspeed Pascal there is a whole series of other Pascal versions or programming languages that will run on the Macintosh. We will make a few remarks about some of these. The graphics procedures are naturally the same in all Pascal versions. TML. Pascal In contrast to Turbo Pascal and Lightspeed Pascal, TML Pascal generates the most efficient code. Nevertheless we recommend Lightspeed Pascal. In our opinion it is the most elegant development system as regards the simplicity of giving commands to the Macintosh. The graphics procedures are the same, and we do not give a sample program.

362

Dynamical Systems and Fmctals

PROCEDURE Hello; BEGIN Clear-Screen; TextMode; InfoOutput ('Calculation of Infooutput (V--------------------------8); Newlines CarryOn Newlines END;

‘I;

(2); ('Start :I); (2);

PROCEDURE Goodbye; BEGIN CarryOn ('To stop : '); END; (”

--------------------------------------------------------

“)

(* include file of problem-specific procedures here :-----(*$I D:feigb.Pas *) (" -------------------------MAIN------------------------------

*) ")

BEGIN Hello; Initialise; ComputeAndDisplay; Goodbye; END. A hint here too for Include-Files: in Include-Files the drive is specified as, for instance, D : . That is just an example to show what to do when the Pascal system is on a different drive from the Include-Files. The Include-File follows; UtilGraph.Pas.

(“--------------------------“TI~IT~-----------------------

(*

BEGIN: Useful Subroutines *) PROCEDURE ReadReal (information : real); BEGIN write (information); readln (value); END;

:

Tstring;

VAR

“)

value

PascalandtheFig-trees

361

Modula lZ Another interesting development environment for computer graphics experiments is Modula II. Modula II was developed by Niiaus Wirth as a successor to Pascal. On the Macintosh there are at present a few Modula II versions: TDI-Modula and MacMETH. MacMETH is the Modula II system developed by ETH at Zurich. We choose TDIModula here, because the same firm has developed a Modula compiler for the Atari. Lightspeed C

C holds a special place for all those who wish to write code that resembles machine language. Many large applications have been developed using C, to exploit the portability of assembly programming. Three examples of C programs have been given already in $12.3 (UNIX systems). They were originally programmed in Lightspeed C on the Macintosh and thus run without change on all C compilers.

12.5 Atari Systems The Atari range has become extremely popular among home computer fans in the last few years. This is doubtless due to the price/power ratio of the machine. Of course, the Atari 1024 is no Macintosh or IBM system 2, but it can produce pretty good Gingerbread Men - in colour. Among the available programming languages are GFA Basic, ST Pascal Plus, and C. We give our Reference Program here for ST Pascal Plus. Program 12.5-1 (ST Pascal Plus reference rrogram for Atari) PROGRAM EmptyApplicationShell; (* ST Pascal Plus on Atari *) CONST (* e.g. 320 points in x-direction *) Xscreen = 320; Yscreen = 200; (* e.g. 200 points in y-direction *) (*$I GEMCONST *) TYPE T&ring = string[80]; (*$I GEMTYPE *) VAR PictureName : Tstring; Left, Right, Top, Bottom : real; (* include additional global variables here *) Feedback : real; Visible, Invisible : integer; (*$I GEMSUBS *) (*$I D:UtilGraph.Pas *)

Dynamical Systems andFmctals

364

(”

------------------------G~~*cs-------------------------*)

(* BEGIN:

Graphics Procedures *)

PROCEDURE SetPoint (xs, ys : integer); BEGIN (" Insert machine-specific graphics commands here move-to (x9, Yscreen - ys);

*)

line-to (xs, Yscreen - ys) ; EM);

PRocEDuRE SetUniversalPoint (xu, yu: real); VAR xs, ys : real; BEGIN xs := - Left) * Xscreen / (Right - Left); := (yu - Bottom) * Yscreen / (Top - Bottom); YS SetPoint (round(xs), round(ys)); END; (XU

PROCEDURE GoToPoint (xs, ys : integer); BEGIN t* Insert machine-specific graphics commands here move-to (xs, Yscreen - ys); END;

*)

PROCEDURE DrawLine (xs, ys : integer); BEGIN (" Insert machine-specific graphics commands here lineto (xs, Yscreen - ys); EM);

*)

PROCEDURE GoToUniversalPoint (xu, yu : real); BEGIN VAR xs, ys : real; BEGIN xs := (xu - Left) * Xscreen / (Right - Left); - Bottom) * Yscreen / (Top - Bottom); YS := GotoPoint (round(xs), round(ys)); END; (yu

PROCEDURE DrawUniversalLine VAR xs, ys : real;

(xu, yu : real);

363

PascalandtheFig-trees

PROCEDURE

ReadInteger :

(information integer);

:

Tstring;

VAR

value

:

Tstring;

VAR

value

BEGIN write (information); readln (value); EM); PROCEDURE

ReadString :

(information string);

BEGIN write (information); readln (value); END; PROCEDURE InfoOutput (information BEGIN writeln (information); writeln; END;

:

Tstring);

PROCEDURE CarryOn (information : Tstring); BEGIN write (information, ' hit '); readln END; PROCEDURE CarryOnIfKey; BEGIN REPEAT UNTIL KeyPress; END;

(* NOT as for Turbo! *)

PROCEDURE Newlines (n : integer); via i : integer; BEGIN FOR i := 1 TO n DO writeln; END; (* END: Useful Subroutines *) ----------------------") (" -------------------------UTILITY---

366

Dynamical Systems and Fractals

12.6 Apple II Systems It is certainly possible to take the view that nowadays the Apple IIe is ‘getting on a bit’. It is undisputedly slow, but nevertheless everything explained in this book can be achieved on it. The new Apple IIGS has more speed compared with the Apple II, and better colours, so that devotees of the Apple are likely to stay with this range of machines, rather than try to cope with the snags of, e.g., MS-DOS. Turbo Pascal Turbo Pascal 3.OOA can only run on the Apple II under CP/M. It functions pretty much as in MS-DOS. Specific problems are the graphics routines, which have to be modified for the graphics system of the Apple II. Recently several technical journals (such as MC and c’l) have given hints for this. TML. Pascal/ORCA P a s c a l Compared with the Apple IIe the Apple IIGS is a well-tried machine in new clothes. In particular, the colour range is improved. We recommend the use of TML Pascal (see Program 12.6-3) or ORCA Pascal. UCSD Pascal Many Pascal devotees know the UCSD system. At the moment there is version 1.3, which runs on the Apple IIe and also the Apple IIGS. Unfortunately until now the UCSD system recognises only 128K of memory, so that extra user memory (on the GS up to 4 MB) can be used only as a RAMdisk. Basically there are few major changes to our previous reference program. The use of Include-Files or units is possible.4 Program 12.6-1 (Reference program for Apple II, UCSD Pascal) PROGRAM EmptyApplicationShell; (* UCSD Pascal on Apple II *) USES applestuff, turtlegraphics; CONST (* e.g. 280 points in x-direction *) Xscreen = 280; (* e.g. 192 points in y-direction *) Yscreen = 192; VAR PictureName : string; Left, Right, Top, Bottom : real; (* include additional global variables here *) Feedback : real; Visible, Invisible : integer; 4Examples for Include-Files are given in 412.2, for units in $12.4.

Pascal and the Fig-trees

365

BEGIN xs := (xu - Left) * Xscreen/(Right - Left); := (yu Bottom) * Yscreen / (Top - Bottom); YS DrawLine (round(xs), round(ys)); END; PROCEDURE TextMode; BEGIN Exit-Gem; END; PROCEDURE GraphicsMode; VARi : integer BEGIN (* machine-specific i : = INIT-Gem; Clear-Screen; END;

graphics

commands

*)

PROCEDURE EnterGraphics; BEGIN writeln ('To end drawing hit I); writeln(‘--------------- Graphics Mode --------------n); CarryOn('BEGIN :I); GraphicsMode; END; PROCEDURE ExitGraphics BEGIN (*Machine-specific actions to exit from Graphics Mode*) readln; Clear-Screen; TextMode; WriteIn ('-----------------Text Mode w---------------8); END; (* ("

END: Graphics Procedures *) -----------------------GRAPHICS--------------------------")

The problem-specific part does not change (see Turbo Pascal, 312.2).

368

Dynamical Systemsand Fmctals

write (information); readln (value); END; PROCEDURE ReadInteger :

(information integer);

STRING;

VAR

STRING;

VAR

value

BEGIN write (information); readln (value); END; PROCEDURE

ReadString :

(information string);

:

BEGIN write (information); readln (value); END; PROCEDURE InfoOutput (information : STRING ); BEGIN writeln (information); writeln; END; PROCEDURE CarryOn (information : STRING ); BEGIN write (information, ' hit '); readln; END; PROCEDURE CarryOnIfKey; BEGIN REPEAT UNTIL KeyPressed; END;

PROCEDURE Newlines (n : integer); VziR I : integer; BEGIN FORi:=lTOnDO

value

367

PascalandtheFig-trees

(*$I

Utiltext *)

PROCEDURE Hello; BEGIN TextMode; InfoOutput ('Calculation of ~nfoou~put (I---------------------'); Newlines CarryOn Newlines END;

‘);

(2); ('Start :I); (2);

PROCEDURE Goodbye; BEGIN CarryOn ('TO stop : I); END; (”

(*

--------------------------------------------------------

include

(*$I (A

file

of

feigb.Pas

*)

problem-specific

procedures

here

“)

:------

-------------------------MAIN------------------------------

*)

“)

BEGIN Hello; Initialise; ComputeAndDisplay; Goodbye; END. Most changes occur in the graphics procedures. UCSD Pascal implements a kind of turtle graphics, which does not distinguish between 1 ine and move. Instead the colour of the pen is changed using the procedure pencolor. On leaving a procedure the colour should always be set to pen co 1 o r ( none ) . Then a program error, leading to unexpected movements on the graphics screen, cannot harm the picture. Program 12.6-2 (Include-File of useful subroutines) (“--------------------------“TI~IT~----------------------(*

BEGIN: Useful Subroutines *) PROCEDURE ReadReal (information : real);

BEGIN

:

STRING;

VAR

“) value

370

DynamicalSystemsandFractals

xs := (xu - Left) * Xscreen / (Right - Left); YS := (yu - Bottom) * Yscreen / (Top - Bottom); GotoPoint (round(xs), round(Ys)); END; PROCEDURE DrawUniversalLine (xu, yu : real); m xs, ys : real; BEGIN xs := (XU - Left) * Xscreen/(Right - Left); YS := (yu- Bottom) * Yscreen / (Top - Bottom); DrawLine (round(xs), round(ys)); END; (* (*

PROCEDURE TextMode PROCEDURE GraphMode

is defined in turtle graphics is defined in turtle graphics

") *)

PROCEDURE EnterGraphics; BEGIN writeln ('To end drawing hit I); Page (Output) ; GotoXY (0,O) ; writeln( I-------------- Graphics Mode --------------‘I; CarryOn('BEGIN :I); InitTurtle; END;

PROCEDURE ExitGraphics BEGIN (*Machine-specific actions readln; TextMode; Page (oputput) ;

to

exit

from

Graphics

Mode*)

GotoXY(O,O); END;

(* END: Graphics Procedures *) (" -----------------------G~~ICs--------------------------*) The problem-specific part does not change (see Turbo Pascal, $12.2). As we have already explained at the start of this chapter, we recommend you to use TML Pascal on the Apple II. There are two versions:

369

F%scal and the Fig-trees

writeln; END; (* END: Useful Subroutines *) (" -------------------------uTILITy--------------------------*) ---GRAPHICS----------------------*) (" _______________-----(* BEGIN: Graphics Procedures *) PROCEDURE SetPoint (xs, ys : integer); BEGIN (" Insert machine-specific graphics commands here moveto (x9, YeI; pencolor(white); move(O); pencolor(none); END;

*)

PROCEDURE SetUniversalPoint (XU, yU: real); VAR xs, ys : real; BEGIN xs := (XU - Left) * Xscreen / (Right - Left); := (yu Bottom) * Yscreen / (Top - Bottom); YS SetPoint (round(xs), round(ys)); END; PROCEDURE GoToPoint (xs, ys : integer); BEGIN (" Insert machine-specific graphics commands here moveto (x9, YeI; END; PROCEDURE DrawLine (xs, ys : integer); BEGIN (" Insert machine-specific graphics commands here pencolor(white); moveto (x9, YS) ; pencolor(none); END; PROCEDURE GoToUniversalPoint BEGIN VAR xs, ys : real; BEGIN

(xu, yu : real);

*)

*)

372

DynamicalSystemsandFractals

Moveto

(x, y);

Line (0, 0); END; PROCEDURE sqr(x :real) : real; BEGIN sqr (x) := x * x; END; PROCEDURE Mapping; VAR xRange, yRange : intger; x, y, x0, y0, deltaxPerPixe1,

deltayPerPixe1

FUNCTION MandelbrotComputeAndTest (cRea1, : real) : integer; v?B iterationNo : integer; x, y, xSq, ySq, distancesq : real; finished: boolean; BEGIN StartVariableInitialisation *) t* finished := false; iterationNo := 0; x := x0; Y := yo; xsq := sqr(x); Y% := sqr(y); := xsq + ysq; distancesq (* StartVariableInitialisation *) REPEAT (* Compute *) iterationNo := iterationNo + 1; := x*y; Y Y := y+y-cImaginary; x := xSq - ySq -cReal; x--l := sqr(x); ySq := sqr(y); := xsq + ysq; distancesq (* Compute *) (* Test *)

: real;

cImaginary

371

PasmlandtheFig-trees

TML Pascal (APW) . TML Pascal (Multi-Window) The first version is best considered as a version for the software developer who wishes to use Apple Programmer’s Workshop, the program development environment from Apple Computer Inc. The second version is easier to use. The multi-window version has a mouse-controlled editor and is similar to TML Pascal on the Macintosh. Below we once again give our reference program, this time for TML Pascal on the Apple IIGS. For a change, here we draw a Gingerbread Man. We confine ourselves to the most important procedures; you have already seen in previous sections that the surrounding program scarcely changes. I

Program 12.6-3 (TML Pascal for Apple IIGS) PROGRAM EmptyApplicationShell(input, output); USES ConsolelO, (* Library for plain vanilla I/O QDIntf; (* Library for Quick-draw calls CONST Xscreen = 640.0; (* SuperHIRES screen 640x400 points*) Yscreen = 200; (* NOTE: real constants! VAR Left, Right, Top, Bottom : real; I, MaximalIteration, Bound : integer; R: Rect;

*) *)

")

PROCEDURE ReadReal (s BEGIN writeln; write (s); readln (number); END;

: string; VAR number : real);

PROCEDURE ReadInteger BEGIN writeln; write (s); readln (number); END;

(s : string; VAR number : integer);

PROCEDURE SetPoint (x, y, colour : integer); BEGIN SetDithColor ( c o l o u r ) ; (* 16 possible colours *)

Dynamical Systems and Fractals

314 BEGIN (* main *) Initialise; Mapping; REPEAT UNTIL KeyPressed; END.

Observe that: We have collected together all local procedures inside the functional

.

proccdurcMandelbrotComputeAndTest l

.

.

The graphics procedure calls arc similar to those for the Macintosh. Therefore it is not necessary for us to list all of them. They are identical.

TheLibrary Console10 contains the following useful subroutines: Function KeyPressed : boolean Procedure EraseScreen; P r o c e d u r e SetDithColor ( c o l o r : i n t e g e r ) ; .

The value for the variable color must lie between 0 and 14, corresponding to the following colours: Black (0), Dark Grey (l), Brown (2), Purple (3), Blue (4), Dark Green (5), Grange (6), Red (7), Flesh (8), Yellow (9), Green (lo), Light Blue (ll), Lilac (12), Light Grey (13), White (14). The way to use colour is easy to see in the program listing. In the algorithmic part distinguish(insideMandelbrotComputeAndTest) the value of IterationNo detertnines

the colour value.

12.7 ‘Kermit Here’ - Communications In the course of time we become ever more special&d. Now the discussion will be extremely special. The difficult probem of computer-computer communication is the final topic. What we now discuss will be most likely to appeal to ‘freaks’ - assuming they do not already know it. The problem is well known: how can we get data and text files from computer X to computer Y? We have already given the main answer in 511.6, ‘A Picture Takes a Trip’. But the gap between direct computer-computer connection and e-mail is vast. To bridge it you need to read manuals, think about cables and connectors - all of which takes time. We cannot make the process effortless, but we can give a little help. First you must buy or assemble a cable, to connect your computer to a modem or another computer via the V24 interface. This hardware problem is the most disagreeable part, because the computer will not do anything if you use the wrong pin-connections. The best solution is the help of a knowledgeable friend, or the purchase of a ready-made cable. Then the next problem raises its head: software. We recommend ‘Kermit’. This communications package exists for virtually every computer in the world: try to get this ‘public domain’ software from usergroups or friends. Of course you can also get other

PascalandtheFig-trees

finished := distancesq > 100.0; (* Test *) - MaximalIteration) OR finished; UNTIL (iterationNo (* distinguish *) THEN IF iterationNo = MaximalIteration MandelbrotComputeAndTest : = 15 ELSE BEGIN IF iteratioNo > Bound THEN MandelbrotComputeAndTest : = 15 ELSE MandelbrotComputeAndTest : = iterationNo MOD 14;

(*

END; distinguish *) END; BEGIN (* Mapping *) SetPenSize(1, 1); deltaxPerPixe1 := (Right - Left) / Xscreen; deltayPerPixe1 := (Top - Bottom) / Yscreen; x0 := 0.0; yo := 0.0; Y := Bottom; FOR yRange := 0 TO trunc (yscreen) DO BEGIN x:= Left; FOR xRange := 0 TO trunc (xscreen) DO BEGIN SetPoint (xRanqe, yRanqe, MandelbrotComputeAndTest (x, y)); x := x + deltaxPerPixe1; IF KeyPressed THEN exit (Mapping); END; Y := y + deltayPerPixe1; END; END; PROCEDURE Initialise; BEGIN ReadReal ('Left ' 'I Left); ReadReal ('Right ' 'I Right); ReadReal ('Top ' 'I Top) ; ReadReal ('Bottom ' '1 Bottom); ReadInteger ('Max. Iteration > ',MaximalIteration); ReadInteger ('Bound ' 'I Bound); END;

373

316

Dynamical Systemsand Fractis

Assume that you want to transfer a file named rlecdat, containing your picture data,

from the VAX to the PC. Then you do this: VAX>kermit

s rlecdat

The UNIX computer waits until the PC is ready for the transfer. You must return to the Kermit environment of your running MS -DOS program. Type: A command line appears. Give it the letter c , as an abbreviation for closeconnection. coMMAND>c

Kermit-MSreceive

picturedata

Thedatarlecdat (on a UNIX system)become picturedata on the MS-DOS system. The transfer then starts, and its successful completion is reported. Kermit-MSdir The transferred file is written into the directory of your MS-DOS machine. If you already have a file of the same name on your PC, things do not work out very well. The converse procedure is also simple: VAX>Kermit

r

You return to the Kermit environment and give the command: Kermit-MSsend

examp1e.p

The transfer then begins in the opposite direction... Everything works much the same on other computers, including the Macintosh. But here there is an elegant variant. In the USA there are two programs named MacPut and MacGet, which can transfer Macintosh text and binary files under the MacTerminal 1.1 protocol to and from a UNIX system. Get hold of the C source files, transfer them to your VAX, compile them into the program - and you are free of all Kermit problems. login: kalle password: 4.3 BSD UNIX O4: Thu Feb 19 16:00:24 Mon Jul 27 18:28:20 MET DST 1987 suwmacget msdosref.pas -u

MET 1987

375

Pascal and the Fig-trees

software, provided both computers use the same communications protocol, for instance XModem. Kermit is the most widely available and its documentation is clearly written. Without going too much into fine detail, we will first describe how file transfer works5 between an IBM-PC running under MS-DOS and a UNIX system, such as a VAX or SUN. We assume that your IBM-compatible has two drives or a hard disk, and that the Kermit program is on drive b : or c : . Then you must enter into the following dialogue with the host computer, for example the VAX. (... means that the screen printout is not given in full.) Kermit Dialogue: MS-DOS -C--B UNIX b>kermit IBM-PC Kermit-MS V2.26 Type ? for help Kermit-MS>? BYE CLOSE CONNECT DEFINE ... STATUS TAKE Kermit-MS>status Heath-19 emuilation ON ... Communication port: 1 Kermit-MS>set baud 9600

Local

Echo

Off

Debug

Mode

Off

Now you must set the other parameters such as XON/XOPF, Parity, Stop-bits, g-bit, etc. as applicable. Once both computers are similarly configured, the connection can be made. Kermit-MS>connect [connecting to host, type control-] C to return to PC] Hit and the UNIX system reports... login : kalle password: ...

bnder Kermit, the procedure is much the same for other machines.

377

Pascal and the Fig-trees

suN>1s -1 total 777 -rwxrwxr-x -m-r --r--rwxrwxr-x -rw-r--r-- m - m -r--

1 1 1 1 1

kalle kermit kalle kermit kalle

16384 9193 19456 9577 5584

Jan Jan Jan Jan Jul

16 1987 macget 16 1987 macget.c.source 16 1987 macget 16 1987 macget.c.source 27 18:33 msdosref.pas

Dynamical Systems and Fractals

380

13.1 Data for Selected Computer Graphics Especially in your first investigations, it is useful to know where the interesting sections occur. Then you can test out your own programs there. Some of the more interesting Julia sets, together with their parameters in the Mandelbrot set, are collected together below. In addition to the title picture for this Chapter, an ‘Atlas’ of the Mandelbrot set, we also give a table of the appropriate data for many of the pictures in this book. For layout reasons many of the original pictures have been cropped. Some data for interesting pictures may perhaps be missing: they come from the early days of our experiments, where there were omissions in our formulas or documentation. Table 13-1 shows for each figure number the type of picture drawn, as this may not be clear from the caption. We use the following abbreviations: G

Gingerbread man (Mandelbrot set) or variation thereon

J

Julia set, or variation thereon

C

Set after Curry, Garnett, Sullivan

Nl

Newton development of the equationflr) = (~-1)*x*(x+1)

N3

Newton development of the eqationf(x)

N5

Newton development of the equati~flx) =x5-1

T

Tomogram picture, see Chapter 6

F

Feigenbaum

*

See text for farther information

=x3-1

diagram

Near the (approximate) boundaries of the picture sections you will see the maximal number of iterations and the quantity that determines the spacing of the contour lines. The last two columns give the initial value for Mandelbrot sets, and the complex constant c for Julia sets.

Picture Type Left

Right

TOP

Bottom

5.1-2ff N 3 5.1-7 N5 5.2-l J 5.2-2 J 5.2-3 J 5.2-4 J 5.2-5 J 5.2-6 J 5.2-l J 5.2-8 J 5.2-9 J 5.2-10 J 5.2-11 J 5.2-12 J 5.2-13 J

2.00 2.00 1.60 1.60 1.60 1.60 1.60 1.60 1.60 1.60 1.75 1.75 0.40 0.316 4 0.298 14

-1.50 -1.50 0.00 0.00 0.00 -1.20 -1.20 0.00 0.00 0.00 -1.20 -1.20 -0.322 -0.209 1 -0.203 3

1.50 1.50 ;5 1.20 20 1.20 20 20 1.20 1.20 20 1.20 20 1.20 20 1.20 20 1.20 20 1.20 200 1.20 200 -0.15 200 -0.191 4 400 -0.201 3 400

-2.00 -2.00 -1.60 -1.60 -1.60 -1.60 -1.60 -1.60 -1.60 -1.60 -1.75 -1.75 0.15 0.29 0.295 11

Maximal iteration

Bound

; 20 20 20 20 20 20 20 20 0 0 40 140 140

Complex constant or initial value ci or fl cr0r.m

0.10 0.20 0.30 0.40 0.50 0.60 0.70 0.80 0.745 0.745 0.745 0.745 0.745

405 428 405 405 405

4 4 4 4

0.10 0.20 0.30 0.40 0.50 0.60 0.70 0.80 0.113 0.113 0.113 0.113 0.113

006 cG9 006 006 006

3 3 3 3

13 Appendices

Dynamical Systems and Fractals

382

Pictore T y p e . Left

10-2 10-3 10-4 10-5 10-6 10-7 10-8 10-9 lo-10 lo-11 lo-12 lo-13 lo-14 lo-15 lo-16 lo-19 lo-20 10-21 12.1-1 12.4-2

G G G G G G G G G G G G G G G G G G F F

Right

0.80 0.95 0.80 0.95 0.85 0.95 0.85 0.95 0.857 0.867 0.857 0.867 0.940 0.915 0.935 0.945 0.925 0.935 0.857 0.867 0.900 0.92 1.044 1.172 1.044 1.172 1.044 1.172 0.75 0.74 0.745 05 0.745 54 0.745 34 0.745 90 0.015 36 0.015 40 1.80 3.00 1.80 3.00

Top

Bottom

Maximal iteration

Bound

Complex cxxwant or initial value ci or JQ cr or .m

-0.35 -0.35 -0.35 -0.35 -0.270 -0.270 -0.315 -0.305 -0.295 -0.270 -0.255 -0.299 2 -0.299 2 -0.299 2 0.108 0.112 91 0.112 95 1.020 72 0.00 0.00

-0.15 -0.15 -0.25 -0.25 -0.260 -0.260 -0.305 -0.295 -0.285 -0.260 -0.275 -0.211 6 -0.211 6 -0.211 6 0.115 5 0.113 24 0.113 05 1.020 75 1.50 1.50

25 25 25 25/50 50 loo 100 100 100 100 150 60 60 60 120 400 400 300 50 50

0 15 0 15/21 0 40 40 40 40 40 60 30 30 30 99 100 140 60 100 100

O.Oil 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00

Table 13-1 Data for selected pictures.

0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00

381

AppendiCeS

Picture Type Left

5.2-14 5.2-15 5.2-16 5.2-11 5.2-18 5.2-19 5.2-20 5.2-23 6.1-1 6.1-2 6.1-3 6.1-4 6.1-5 6.1-6 6.1-7 6.1-8 6.1-9 6.1-10 6.1-11 6.1-12 6.1-13 6.1-14 6.2-lff 6.2-11 6.3-4ff 6.4-l 6.4-2 6.4-3ff 6.4-6 6.4-7 7.1-l 1.1-2 7.1-3 7.1-4 7.1-5 7.1-6 7.2-l 7.2-2 7.2-3 7.2-4 7.2-5 7.2-6 7.2-7 7.2-8 1.4-l 7.4-2 1.4-3 7.4-4 9.5 10-l

J J J J J J J J J J G G G G G G G G G G G G T T F C C Gt C Jt Nl N3 J G J G G G+ Gt N3 J J J J G G J J J G

0.295 1 1 0 . 2 9 6 26 0.296 2 6 -1.75 -2.00 -0.08 -0.08 -1.75 -0.05 -0.05 -1.35 -1.35 -1.35 -1.35 -1.35 -1.35 -1.35 -0.45 1.934 68 0.74 0.74 -0.465 -2.10 0.62 0.60 -2.50 -0.20 -2.10 0.90 -2.00 -2.00 1.00 -2.00 -1.35 -2.00 -1.35 -4.00 -1.50 -3.00 -2.00 -2.00 -18.00 -2.00 -3.20 -1.35 -1.35 -2.00 -2.00 -1.00 -1.35

Right

Top

Bottom

Maximal iteration

Bound

0.298 1 4 0.296 8 6 0.296 8 6 1.75 1.50 0.07 0.07 1.75 0.05 0.05 2.65 2.65 2.65 2.65 2.65 2.65 2.65 -0.25 1.949 3 0.75 0.75 -0.45 2.10 0.64 0.90 2.00 0.40 2.10 1.10 2.cQ 2.00 3.40 2.00 2.65 2.00 2.65 1.50 1.50 3.00 2.00 2.00 18.00 2.00 3.20 2.65 2.65 2.00 2.00 1.00 2.65

-0.2033 -0.2024 -0.2024 -1.20 -1.20 -0.1 -0.1 -1.20 -0.075 -0.075 -1.50 -1.50 -1.50 -1.50 -1.50 -1.50 -1.50 -0.10 -0.005 0.108 0.115 5 0.34 -2.10 0.75 0.00 -2.00 1.50 -2.10 -0.03 -2.00 -1.50 -4.50 -1.50 -1.50 -1.50 -1.50 -2.00 -0.10 -2.25 -1.00 -1.50 -13.50 -1.50 -2.00 -1.50 -1.50 -1.50 -1.50 -1.20 -1.50

-0.2013 -0.202 -0.202 1.20 1.20 0.1 0.1 1.20 0.075 0.075 1.50 1.50 1.50 1.50 1.50 1.50 1.50 0.10 0.009 0.115 5 0.123 0.35 2.10 0.80 1.50 2.00 1.91 2.10 0.10 2.00 1.50 -2.70 1.50 1.50 1.50 1.50 2.00 1.50 2.25 1.50 1.50 13.50 1.50 4.80 1.50 1.50 1.50 1.50 1.20 1.50

400 600 600 50 1000 200 300 60 400 400 4 6 8 10 20 100 60 40 100 120 120 200 100 250 50 250 100 100 100 225 20 20 10 15 20 20 40 40 30 40 30 30 30 30 20 20 30 30 100 20

140 200 200 0 12 60 0 10 150 150 0 0 0 0 0 16 0 40 20 100 100 60 7 100 250 0 0 7 0 8 0 0 0 0 0 0 12 7 10 3 10 10 30 30 0 0 0 5 0 0

Complex lxmsmt or initial value

0.745 4 2 8 4 0 . 7 4 5 405 4 0.745 428 0.745 428 0.745 4 2 8 0.745 428 0.745 428 1.25 0.745 4 0 5 4 0.745 428 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 * yo=O.l

0.113 CO9 0 . 1 1 3 006 3 0.113 co9 0.113 0 0 9 0.113 009 0.113 0 0 9 0.113 009 0.011 0.113 006 3 0.113 009 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 * ci=o.4

0.00 0.00 0.00 0.00 -0.50

0.00 0.00 0.00 O.Oll 0.44

0.50 0.00 0.745 O.CCl 0.00 0.00 0.00

0.50 0.M) 0.113 0.00 0.00 0.00 0.00

1.39 1.39 -0.35 -0.35 0.00 0.00 0.50 -0.35 -0.30 0.00

-0.02 -0.02 -O.CW -0.004 0.00 0.00 0.50 0.15 -0.005 0.00

Dynamical Systems and Fractals

384

Picture

Page

Caption

2.2.3-2

53

3.1-1

57

Trace’ of the parabola-attractor in the p IQ?)-plane

3.1-2

58

The Verhulst attractor fork = 1.60

3.1-3

60

Self-similarity at each step (top left projections of the attractor)

3.1-4

61

Self-similarity at each step (detail fmm the ‘node’ to the right of cenwe)

3.2-l

62

The H&non attractor

3.3-l

65

Lorenz

Feigenbaum landscape with the data 3.2.4. LA, 0.50.500

attractor for a = 10. b = 28, c = S/3. and screen dimensions -30, 30,

-30. 80 3.3-2

65

Lmenz attractor for a = 20. b = 20. c = 8/3. and screen diensions -30. 80

4.1-l

72

The graph of the function &r) = (.x+1)+x*(x-l)

4.1-2

73

How Newton’s method leads to a zero

4.1-3

74

hitid VdU.5

kads to atnaCt‘,f

X1

4.1-4

75

Initial vahw x7 leads to attTactor

x2

4.1-s

75

hitiatdue

x3

4.1-6

16

Initial value XrJ leads to attractor

4.1-I

76

Initial value xl0 leads to attractor xi

4.1-8

1-l

Initial value x11 leads to attractor x3

4.1-9

78

Graphical representation of the basins of attraction

4.1-10

78

Basins of attraction (detail of Fig. 4.1-9)

4.1-11

79

Basins of attraction (detail of Fig. 4.1-10)

4.2-l

84

A point in the Gaussian plane and its polar coordinates

4.3-l

87

The basins of attraction in the complex plane

4.3-2

88

Section from Fig. 4.3-l left of centre

4.3-3

89

At the boundary between two basins of attraction

4.3-4

89

The boundary between two basins of amaction

4.3-5

90

‘Stripes approaching the boundary’

5.1-l

92

Position of three point attractors in the Gaussian plane

5.1-2

98

Boundary between the three basins after 15 iterations

5.1-3

99

Basin of the attractor zc

5.1-4

100

‘Contour limes

5.1-5

101

Every third contour line. and the boundaries, in a single picture

5.1-6

102

The basins of the three attractors zA. zB. zc

5.1-7

104

A Julia set with fivefold symmetry

5.1-8

107

Grey shades, normal size (left) and magnified to show individual pixels

5.2.1-4

111

Julia sets

5.2.5-8

112

Julia sets

5.2-9/10

114

Julia sets for cl and c.2

X6

xg leads to Bth‘actol

x2

-34 30,

383

Appendices

13.2 Figure Index

Figure

Page

caption

1.1-1

4

Feedback cycle of weather research

1.1-2

6

General feedback scheme

1.2-1

7

Rough Diamond

1.2-2

8

Vulcan’s Eye

1.2-3

9

1.2-4

10

Tornado Convention

1.2-5

11

Quadruple Alliance

1.2-6

12

Seahorse Roundelay

1.2-7

13

JuliaPropeller

1.2-S

14

variation 1

1.2-9

14

variation2

1.2-10

15

Variation3

Gingerbread Man

1.2-11

15

Explosion

1.2-12

16

Mach 10

2.1-1

19

Feedback scheme for ‘measles’

2.1-2

20

Development of the disease for 4, = 0.3 and k = 0.5

2.1-3

20

Development of the disease for po = 0.3 and k = 1.0

2.1-4

21

Development of the disease for ~0 = 0.3 and k = 1.5

2.1-5

21

Development of the disease for 4) = 0.3 and k = 2.0

2.1-6

21

Development of the disease for w = 0.3 and k = 2.5

2.1-7

22

Development of the disease for po = 0.3 and k = 3.0

2.1-8

22

List of formulas

2.1-9

23

Discrete series of 6 (ki,pi)-values after 10 iterations

2.1-10

26

Calculationofmeasles

2.1.1-t

28

Two coordinate systems

values

2.1.1-2

33

Representation of the measles epidemic on the screen, IterationNo

2.1.2-1

36

Initial value p = 0.1. k = 1.99, a limit point, with screen dialogue

2.1.2-2

37

Initial valuep = 0.1. k= 2.4, two limiting

2.2-l

38

Situation after the onset of oscillations, iterationnumber = 50

points

2.2-2

40

Print-out from Program 2.2-i

2.2-3

43

Section from the Feigenbaum diagram

2.2-4

44

Fig-tree with data: 2.5,2.8, 0.9, 1.4, 50, 100

2.2-5

44

Fig-tree with data: 2.83.2.87, 0.5, 0.8. 50, 100

2.2.1-1

46

Logarithmic representation from k = 1.6 to k = 2.569

2.2.2-l

50

Basin of attraction for the Feigenbaum diagram

2.2.3-l

52

Feigenbamn Ian&cape with the data 0.3. 0, 1.4. 50. 500

= 10

Dynamical Systems and Fractals

386

Picture

Page

Caption

6.3-2

163

Diiect comparison: Gingerbread Man / Fig-bee

6.3-3

163

A parameter path in the Mandelbmt set

6.3-4

164

Quasi-Feigenbaom diagram, real part

6.3-5

165

Quasi-Feigenbaum

6.3-6

165

Pseudo-three-dimensional representation of tiforcation (oblique view horn the

6.4-l

171

Basin of the attractor z = 1

6.4-2

172

Section from Figure 6.4-l (with a surprise!)

6.4-3

174

General&d Mandelbmt set for powers from 1 to 2

6.4-4

175

Generalised Mandelbrot set for &wers from 2 to 3

6.4-5

176

Generabed

6.4-6

177

Section from Figure 6.4-l near c = 1

6.4-l

178

Generalised Julia set

7.1-t

181

Boundaries between three atuactors

7.1-2

184

Julia set for Newton’s method applied to d-1

7.1-3

185

Julia set for c = 0.5 + it0.5

7.1-4

185

Gingerbread Man

7.1-5

186

Julia set, top and bottom interchanged, c = 0.745 + iaO.113

7.1-6

186

Gingerbread Man, inverse iteration height

7.2-l

188

Inverted Mandelbrot set

7.2-2

188

Gingerbread Man for the third power (top half, compare Figure 6.4-5)

7.2-3

189

Gingerbread Man for the third power. inverted (cropped on right)

7.2-4

189

Inverted Julia set for Newton ‘s method applied to d-1

7.2-5

190

Julia set for c = 1.39 - i*O.O2

7.2-6

190

Inverted

7.2-7

191

Julia set for c = -0.35 - i+O.O04

7.2-8

191

Inverted Julia set for c = -0.35 - i*O.O@l

7.3-l

192

The entire complex plane in two unit circles

7.3-2

193

Projection from plane to sphere

7.3-3

198

Examples of Mandelbrot sets on the Riemann sphere

7.3-4

198

Gingerbread Man rotated 60°, front and back

1.4-l

200

Gingerbread Man with interior structure (insideFactor - 2)

7.4-2

200

Gingerbread Man with interior stmctwe (insideFactor = 10)

7.4-3

201

Julia set for c = 0.5tit0.5 with interior stmchre

7.4-4

201

Julia set for c = -0.35+i*O.l5 with interior s~~cture

8.1-l

204

‘Genesis’of the Hilbertcurve

8.1-2

205

‘Genesis’ of the Sierptiki c u r v e

8.1-3

205

Different dragon curves

diagram, imaginary part

from)

Mandelbror set for powers from 3 to 5

on the real axis

Julia set for c = 1.39 - it0.02

385

Appendices

Picture

Page

Caption

5.2-11

115

Julia setfor cl. Section from Fig. 5.2-9

5.2-12

115

Julia set for cl. Section from Fig. 5.2-11

5.2-13

116

Julia set for cl. Section from Fig. 5.2-12

5.2-14

116

Julia set for 9. Section corresponding to Fig. 5.2-13

5.2-15

117

Julia set for cl. Section from Fig. 5.2-13

5.2-16

117

Julia set for s. Section from Fig. 5.2-14

5.2-17

118

Juliasetswithsmalliterationnumber

5.2-18

119

Julia set with higher iteration number also acts as a boundary

5.2-19

120

Section from the cenne of Fig. 5.2-17

5.2-20

121

Section from the centre of Fig. 5.2-19

5.2-21

124

Backwards iteration, 20 seconds’ computing time

5.2-22

124

Backwards iteration. 4 hours’ computing time

5.2-23

126

Yet another Julia set (just to whet your appetite)

6.1-1

129

Julia set for cl, section near the origin

6.1-2

130

Julia set for g, section near the origin

6.1-3

136

Mandelbrot set (4 repetitions)

6.1-4

136

Mandelbrot set (6repetitions)

6.1-5

136

Mandelbrot set (8 repetitions)

6.1-6

137

Mandelbrot set (10 repetitions)

6.1-7

137

Mandelbrot set (20 repetitions)

6.1-8

138

Mandelbrot set (100 repetitions, ‘contour lines’ up to 16)

6.1-9

139

Mandelbrot set (60 repetitions)

6.1-10

140

Mandelbrot set (section left of the origin)

6.1-11

141

A Mandelbrot set of the second order

6.1-12

142

A section between the main body and a bud

6.1-13

142

A section directly below Figure 6.1-12

6.1-14

143

Asatellitefairlyfarleft

6.2-l

146

Quasi-Mend&rot sets for different initialvalues

6.2-2

147

Quasi-Mandelbrot

6.2-3

150

Diagram for c&e 2

6.2-4

151

Diagram for case 2

6.2-5

152

Diagram for case 3

6.2-6

153

Diagram for case 3

6.2-7

154

Diagram for case 4

6.2-8

155

Diagram for case 4

6.2-9

156

Diagram for case 5

6.2-10

157

D i a g r a m f o r case 5

6.2-11

158

Detail with ‘I-fold spiral

6.3-l

162

Feigenbaun diagram from the Mandelbrot set

sets for different initial values

388

Dynamical Systems

and Fractals

13.3 Program Index We list here both programs and program fragments (without distinguishing them). Each represents the algorithmic heart of the solution to some problem. By embedding these procedures in a surrounding program you obtain a runnable Pascal program. It is left to you as an exercise to declare the requisite global variables, to change the initiahsation procedure appropriately, and to fit together the necessary fragments (see hints in Chapters 11 and 12). The heading ‘Comments’ states which problem the procedures form a solution to.

Progmn

Page

commenta

2.1-1

23

Measles numeric

2.1.1-1

29

Measles graphical

2.1.2-1

35

Graphical iteration

2.2-l

38

Feigenbaum iteration

2.2-2

42

Print-out of kin a running program

3.1-1

58

Verhulst attractor

3.2-l

63

H&non attractor

3.3-l

66

L‘3rel-u attrsctor

5.1-l

93

Assignment for iteration equation

5.1-2

94

Belongs to zC

5.1-3

94

Mapping

5.1-4

95

JuliaNewtonComputeAst

5.1-5

96

StartVariableInitialisation

5.1-6

96

Compute

5.1-7

97

Test

5.1-8

97

Distinguish (does the point belong to the boundary?)

5.1-9

98

Distinguish (does the point

belong to the basin?)

5.1-10

100

Distinguish (iteration number MOD 3 etc.)

5.2-l

109

Formulas in Pascal

5.2-2

113

JuliaNewtonComputeAndTest

5.2-3

122

Backwardsiteration

5.2-4

123

Roots

6.1-1

135

MandelbrotComputeAndTest

6.3-l

159

Equality test for real numbers

6.3-2

159

Equality test for complex numbers

6.3-3

160

Mapping

6.3-4

164

Working part of Mapping

6.3-5

164

Drawing commands, real part

6.3-6

164

Drawing commands, imaginary part

387

AppendiCeS

Picture

Page.

caption

8.1-4

206

Different Koch curves

8.1-5

206

A C-curve

8.2-l

212

Grassandtwigs

8.2-2

213

Two-dimensional cloud formation

8.2-3

214

Different grasses

8.2-4

215

Fractal landscape with lake and mountains

8.3-l

211

T h e stmchlre 111[11111[11111

8.3-2

220

Construction of a graftal

8.3-3

221

Graftal-plant

8.3-4

221

Development of a graftal from the 4th to the 12th generation

8.3-5

222

A graftal from the 4th to the 13th generation

8.4-l

224

Interference pattern 1

8.4-2

225

Interference pattern 2

8.4-3

225

Interference pattern 3

8.4-4

226

Garland

8.4-5

221

Spiderweb with a = -137. b = 17. c = -4. n = 1 898 687

8.4-6

228

Cellculhlre

9-l

235

Complex weather boundaries around Bremen:

9-2

236

Gingerbread weather?

9-3

239

Water drop experiment

9-4

241

EEG curves: normal action and fibrillation

9-5

245

Revolving. self-modifying patterns

10-l-21

248-55

From

11.2-1

273

Fractal mountains

11.2-2

281

Input dialogue for Graftal

11.3-1

285

Rijssler attractor

11.5-l

304

Three methods of data compression

12.1-1

328

Feigenbaum reference pichue

12.4-1

353

Turbo Pascal reference picture

12.4-2

360

Screen dialogue

379

‘Atlas’of the Mandelbrot set.

23/24.7 1985

on the screen

the ‘Land of Infinite Structures’: no title

Dynamical Systems and Fractak

390

12.4-2

354

Lightspeed

Pascal

Reference

Program

for

Macintosh

12.5-1

361

ST Pascal Plus Reference Program for Atari

12.6-1

366

UCSD Pascal Reference Program for Apple II

12.6-2

361

Include-File

12.6-3

371

TMLPascal

of

useful

subroutines

Reference Program for Apple UGS

389

Program

Page

Comments

Drawing commar&.. pseudo-3D

6.3-l

165

6.4- 1

168

Complex

6.4-2

170

Curry-Gamett-Sullivan

6.4-3

173

Compute for higher powers

7.1-1

181

DJ-Mapping

7.1-2

182

D3ComputeAndTest

7.1-3

183

D3Draw

7.2-l

187

ComputeAndTesf inverted

arithmetic method

194

Mapping for Riemann sphere

7.4-l

199

Distinguish for structures in interior

8.1-1

207

Turtle graphics

8.4-l

224

Conett method

8.4-2

227

Martin method

11.1-1

258

Empty Application Shell, shell program for graphics

11.1-2

265

Globalconstwts.

11.2-1

267

Turtle graphics - dragon

11.2-2

269

Fractallandscapes

11.2-3

213

Graft&

7.3-l

tyypes, variables

11.3-1

281

Feigenbaum iteration. logarithmic

11.3-2

282

Fcigenbaum

11.3-3

285

Riissler attractor

11.3-4

286

Newton demonstration

11.4-t

288

Mapping for Newton development of x3-t

11.4-2

291

Mapping for quadratic iteration. Julia sets

11.4-3

293

Mapping for Gingerbread Man

11.4-4

296

Mapping for tomogram

11.4-5

297

Mapping for quasi-Feigenbaum

11.4-6

299

Compote for high-powered Gingerbread Man

11.4-7

300

Mapping and Initialise for pseudo-3D

11.5-1

305

Integer encoding (Berkeley Pascal)

11.5-2

310

Integer encoding to paint

11.5-3

312

Compress int to int

11.5-4

314

Run length encoding integer to paint

11.5-5

315

T r a n s f e r int to char

11.5-6

317

Run length encoding char to paint

12.2-1

331

Turbo Pascal Reference Program for MS-DOS

12.3-lff

339

Program examples in C

12.4-1

347

Turbo Pascal Reference Program for Macintosh

landscape

diagram

392

Dynamical Systems and Fractals

P. Mann (1987). Datenkompression mit dem Huffmann Algorithmus, User Magazin (Newsletter of the Apple User Group, Europe) 22-3. R. M. May (1976). Simple mathematical models with very complicated dynamics, Nature 261 (June 10 1976). D. R. Morse, J. H. Lawton, M. M. Dodson, and M. H. Williamson (1985). Fractal dimension of vegetation and the distribution of arthropod body lengths, Nature 314,

731-733.

M. M. Newman and R. F. Sproull (1979). Principles of Interactive Computer Graphics, McGraw-Hill. H.-O. Peitgen and P. Richter (1985). Die undendliche Reise, GE0 7 (July 1985). H.-O. Peitgen and P. Richter (1986). The Beauty of Fractals, Springer, Berlin, Heidelberg, New York. H.-O. Peitgen and D. Saupe (1985). Fractal images - from mathematical experiments to fantastic shapes: dragonflies, scorpions, and imaginary planets, SIGGRAPH 85. Research Group in Complex Dynamics, Bremen (1984a). Harmonie in Chaos und Cosmos, Exhibition catalogue, Sparkasse Bremen, 16.1.84-3.2.84. Research Group in Complex Dynamics, Bremen (1984b). Morphologie Kompfexer Grenzen, Exhibition catalogue, Max Planck Institute for Biophysical Chemistry 27.5.84-9.6.84; Exhibition catalogue, Sparkasse Bonn 19.6.84-10.7.84. Research Group in Complex Dynamics, Bremen (1985). SchZinheit im Chaos; Computer Graphics face complex dynamics. Exhibition catalogue, Goethe Institute, Munich. W. Rose (1985). Die Entdeckung des Chaos, Die Zeit 3 (11 January 1985). A. M. Saperstein (1984). Chaos - a model for the outbreak of war, Nature (24 May 1984). SIGGRAPH (1985) Special interest group on computer graphics. Course notes: Fractals, Basic Concepts, Computation and Rendering.

Alvy Ray Smith (1984). Plants, fractals, and formal languages, Computer Graphics 18 No. 3 (July 1984). Frank Streichert (1987). Informationverschwendung - Nein danke: Datenkompression durch Huffmann-Kodierung, c’r 1 (January 1987). E. Teiwes (1985). Programmentwicklung in UCSD Pascal, Vogel, Wirzburg. R. Walgate (1985). Je kleiner das Wesen, desto grosser die Welt, Die Zeit 20 (10 May 1985). N.Wirth (1983). Algorithmen and Datenstrukturen, Teubner, Stuttgart.

391

13.4

Bibliography

H. Abelson and A. A. diSessa (1982). Turtle Geometry, MIT Press. M. Abramowitz and J. A. Stegun (1968). Handbook of Mathematical Functions, Dover, New York. Apple Computer Inc. (1980). Apple Pascal Language Reference Manual and Apple Pascal System Operating Manual. K.-H. Becker and G. Lamprecht (1984). PASCAL - Einfihrung in die Programmiersprache, Vieweg. R. Breuer (1985). Das Chaos, GE0 7 July 1985. K. Clausberg (1986). Feigenbaum und Mandelbrot, Neue symmetrien zwischen Kunst und Naturwissenschaften, Kunstform International 85 (September/October 1986). P. Collet, J.-P. Eckmann, and 0. E. Lanford (1980). Universal properties of maps on an interval, Communications in Mathematical Physics 76 (1980) 211. J. P. Crutchfield, J. D. Farmer, N. H. Packard, and R. S. Shaw, et al. (1986). Chaos, Scientific American (December 1986) 38-49. J. H. Curry, L. Garnett, and D. Sullivan (1983). On the iteration of a rational function: computer experiments with Newton’s method, Commun. Math. Phys. 91 (1983) 267-77.

U. Deker and H. Thomas (1983). Unberechenbares Spiel der Natur - Die ChaosTheorie, Bild der Wissenschaft 1 (1983). A.K.Dewdney (1986a). Computer recreations, Scientific American 255 (September 1986) 14-23. A.K.Dewdney (1986b). Computer recreations, Scientific American 255 (December 1986) 14-18. Werner Durandi (1987). Schnelle Apfelmtinnchen, c’t 3 (1987). Steve Estvanik (1985). From fractals to Graftals, Computer Language, March 1985, 45-s.

G. Y .Gardner (1985). Visual simulation of clouds, Computer Graphics 19 No.3. Heimsoeth Software (1985). Turbo Pascal 3.0 Manual. D. R. Hofstadter (1981). Metamagical Themas, Scientific American (November 1981) 16-29. D. A. Huffmann [ 19521. A method for the construction of minimum-redundancy codes, Proc. Inst. Radio Engrs. 40 (1952) 1698. Gordon Hughes [1986]. H&on mapping with Pascal, Byte, December 1986,161. S. Lovejoy and B. B. Mandelbrot (1985). Fractal properties of rain, and a fractal model, SIGGRAPH 85. B. B. Mandelbrot (1977). Fractals: Form, chance, and dimension, Freeman, San Francisco.

393

Appendices

13.5

Acknowledgements

We are grateful to all’chaos researchers who have helped us with information, discussions, and criticisms: Dipl.-Phys. Wolfram B&k, Bremen Dr Axe1 Brunngraber, Hanover Prof. Dr. Helmut Emde, TH Darmstadt Dr Hartmut Jiirgens, Bremen Dipl.-Inform. Roland Meier, Bremen

396

Dynamical Systems and Fractals

Fatou, Pierre, 104 feedback, 4, 34 scheme, 6,73 Feigenbaum, Mitchell, 40 diagram, 39,40,43-4, 50, 160, 162 landscape, 5 1 number, 47 scenario, 54, 56 fibrillation, 241 fig-tree, 37,44, 159 file transfer 3 19 fingerprint of chaos, 237 fractal, 102, 104, 199, 267 dimension, 103 graphics, 204-29 landscape 211-6,273 frontier, 54

Gaussian plane, 72, 84 Gingerbread Man, see Mandelbrot set gipsy moth, 243 global variable, 265 graftal, 216-23,273 Grand Canyon, 248 graphical iteration, 34 graphics procedure, 29 GraphMode, 32 grey tone, 79, 107

hard copy, 303 heartbeat, 240- 1 HCnon, Michel, 62,64 Hercules Graphics Adaptor (HGA), 329 Hilbert curve, 204,208 Huffman method. 3 19

IBM-PC, IBM-AT, 328,375 imaginary number, 82 Include-File, 332, 352, 362 integer encoding, 305 inversion, 186 iteration, 19,34

Julia, Gaston, 88, 104 Julia set, 88, 105, 110, 111-21, 129-30, 184, 288 inverted, 189-9 1 with interior structure, 201

KAM theorem, 62 Kermit, 319,339,374 Keypressed, 47 Koch curve, 206,209

layout of Pascal programs, 258,264 Lightspeed C, 360 Lightspeed Pascal, 353 limits to predictability, 238,244 look-up table, 3 11 Lorenz, Edward N., 64

MacApp, 360 MacGet and MacPut, 376 machine-independence, 258,264 Macintosh, 41, 319, 347 magnetism, 244 Mandelbrot, Benoit B., 102, 108, 138 Mandelbrot set, 3, 128-66, 185, 198, 293 inverted, 188-9 with interior structure, 200 May, Robert M., 244 measles, 19

395

Ill&X

acoustic coupler, 320 Adams-Bashforth method, 61,68 algorithm, 258 Apple IIe, 366 Apple IIGS, 366, 371 armament behaviour, 242-3 asteroid, 63 Atari, 3 19,361 atlas of the Mandelbmt set, 379 attractor, 49,54,92, 172 HCnon, 62 Lorenz, 64-5 parabola, 57 Riissler, 69, 285 strange, 49,56 Verhulst, 58

backwards iteration, 122, 124 basin of attraction, 50,75,98,99, 105 Berkeley Pascal, 309 bifurcation, 39,46,54 billiards, 238 binary representation, 2 18 BinHex, 324 boolean function, 94 Borland, 329 boundary, 51, 80,89, 98, 108, 199 breakdown of predictability, 77,87 butterfly effect, 67, 236,237 Button, 32

C (programming language), 361 Cartesian coordinates, 85 cascade, 4 1 causality principle, 4,237 strong, 4,77,238

chaos, 2, 53, 72, 87, 232-45 researcher, 244 theory, 244 chaotic zone, 78 Cohen, Richard J., 241 Colour Graphics Adaptor (CGA), 329 computability of the world, 233 complex arithmetic, 83 conjugate, 83 number, 81 plane, 84 computer-aided design (CAD), 180 computer art,8 graphics, 180 graphics experiments, 6 contour line, 99, 144 C-curve, 206,210 connected set, 128, 157 CP/M, 366 cube root of unity, 93, 106 Curry-Garnett-Sullivan, 167, 170 cyclic sequence, 168

data compression, 3 11 data transmission, 474 DATEX, 320 decimal representation, 218 delta (Feigenbaum number), 46,48 dragon curve, 205,209 dynamical system, 5,18,54

electronic mail (e-mail), 3 19 Euler’s method, 61 Excel, 22, 132 experimental mathematics, 2,54

398

Dynamical Systems and Fractals

universal coordinate system, 27 Unix, 309, 322, 337, 375 useful subroutine, 25,266 V24 interface, 374 VAX, 41,309,337,375 war, 241-3 weather, 4, 232-8 forecast, 66, 234-6 window, 27,41 zero, 73, 86

Index

391

measuring instrument, 25 meteorology, 232 modem, 320 Modula II, 360 modulus, 84 Monument Valley, 248 MPW Pascal, 360 MS-DOS, 319,328

RAMdisk, 311 real number, 82 repetital, 224 repetitive design, 224-9 Research Group in Complex Dynamics, Bremen, 2, 102, 138 Riemann sphere, 192 run length encoding, 304

Newton’s method, 72, 80, 86, 92, 104-5 nonlinear, 45

Saperstein, Alvin M., 242 screen coordinates, 27 section, 41 self-similarity, 42,61, 103 Sierpihski curve, 205 snowflake curve, 206,210 soft copy, 303 spreadsheet, 22, 13 l-4 stop bits, 375 ST Pascal Plus, 361 strange attractor, see attractor structured program, 258 SUN, 41, 309, 337,375

ORCA Pascal, 366 order and chaos, 79 orthogonal projection, 194

PAD parameter, 320 Papert, Seymour, 206 paradigm, 2 parity, 375 period doubling, 41, 54 periodicity, 159 phase transition, 243 point of no return, 54 polar coordinates, 84, 122 production rule, 216 projection, 192 centre, 192 promptline, 338 PSI2 system, 328 pseudo-3D graphics, 165, 182,300

quadratic iteration, 131,291 quasi-Feigenbaum diagram, 164,297 quasi-Mandelbrot set, 146-7, 149

tap, 238-40 TextMode, 32 three-dimensional graphics, 180-6 TML Pascal, 359,366,37 1 tomogram, 145 transformation equation, 28 transient, 38 tree graphics, 212 Turbo Pascal, 330,353,366 Turbo Pascal reference program, 33 1 turtle graphics, 206,267

UCSD Pascal, 366 unit circle, 192