1.2. Fibonacci Numbers The fibnum function is recursive. In fact. the term recursive is used in both a hematical and a computer science sense. The relationship fn=fn-1+fn-2 is nown as a recursion relation and a function that calls itself is a recursive function A recursive program is elegant, but expensive. You can measure execution time with tic and toc. Try tic, fibnum(50), toc Now compare the results produced by goldfract (6)and fibonacci(7). The first contains the fraction 21 /13 while the second ends with 13 and 21. This is not just a coincidence. The continued fraction is collapsed by repeating the statement p=p+ q while the Fibonacci numbers are generated by f(k)=f(k-1)+f(k-2) In fact, if we let on denote the golden ratio continued fraction truncated at n terms. fn In the infinite limit, the ratio of successive Fibonacci numbers approaches the golden To see this, compute 40 Fibonacci numbers f fibonacci(n) Then compute their ratios f(2:n)./f(1:n-1) This takes the vector containing f(2) through f(n)and divides it, element by element, by the vector containing f(1) through f(n-1). The output begins with 1.50000000000000 1.6666666666666 1.62500000000000 1.61538461538462 1.61764705882353 1.61818181818182
1.2. Fibonacci Numbers 11 ans = 233 The fibnum function is recursive. In fact, the term recursive is used in both a mathematical and a computer science sense. The relationship fn = fn−1 + fn−2 is known as a recursion relation and a function that calls itself is a recursive function. A recursive program is elegant, but expensive. You can measure execution time with tic and toc. Try tic, fibnum(24), toc Do not try tic, fibnum(50), toc Now compare the results produced by goldfract(6) and fibonacci(7). The first contains the fraction 21/13 while the second ends with 13 and 21. This is not just a coincidence. The continued fraction is collapsed by repeating the statement p = p + q; while the Fibonacci numbers are generated by f(k) = f(k-1) + f(k-2); In fact, if we let φn denote the golden ratio continued fraction truncated at n terms, then fn+1 fn = φn. In the infinite limit, the ratio of successive Fibonacci numbers approaches the golden ratio: limn→∞ fn+1 fn = φ. To see this, compute 40 Fibonacci numbers. n = 40; f = fibonacci(n); Then compute their ratios. f(2:n)./f(1:n-1) This takes the vector containing f(2) through f(n) and divides it, element by element, by the vector containing f(1) through f(n-1). The output begins with 2.00000000000000 1.50000000000000 1.66666666666667 1.60000000000000 1.62500000000000 1.61538461538462 1.61904761904762 1.61764705882353 1.61818181818182
Chapter 1. Introduction to MATLAB and ends with 1.61803398874990 1.61803398874989 1.61803398874989 Do you see why we chose n =40? Use the up arrow key on your keyboard to bring back the previous expression. Change it to f(2:n)./f(1:n-1) and then press the Enter key. What is the value of the last element? The population of Fibonaccis rabbit pen doesn't double every month; it is multiplied by the golden ratio every month It is possible to find a closed-form solution to the Fibonacci number recurrence relation. The key is to look for solutions of the form fn cp for some constants c and p. The recurrence relation +1 We've seen this equation before. There are two possible values of p, namely o and 1-o. The general solution to the recurrence is The constants ci and c2 are determined by initial conditions, which are now conveniently written fo f1=c19+c2(1-)=1 Exercise 1. 4 asks you to use the MATLAB backslash operator to solve this 2-by-2 system of simultaneous linear equations, but it is actually easier to solve the system by hand Inserting these in the general solution gives 1
12 Chapter 1. Introduction to MATLAB and ends with 1.61803398874990 1.61803398874989 1.61803398874990 1.61803398874989 1.61803398874989 Do you see why we chose n = 40? Use the up arrow key on your keyboard to bring back the previous expression. Change it to f(2:n)./f(1:n-1) - phi and then press the Enter key. What is the value of the last element? The population of Fibonacci’s rabbit pen doesn’t double every month; it is multiplied by the golden ratio every month. It is possible to find a closed-form solution to the Fibonacci number recurrence relation. The key is to look for solutions of the form fn = cρn for some constants c and ρ. The recurrence relation fn = fn−1 + fn−2 becomes ρ 2 = ρ + 1. We’ve seen this equation before. There are two possible values of ρ, namely φ and 1 − φ. The general solution to the recurrence is fn = c1φ n + c2(1 − φ) n . The constants c1 and c2 are determined by initial conditions, which are now conveniently written f0 = c1 + c2 = 1, f1 = c1φ + c2(1 − φ) = 1. Exercise 1.4 asks you to use the Matlab backslash operator to solve this 2-by-2 system of simultaneous linear equations, but it is actually easier to solve the system by hand: c1 = φ 2φ − 1 , c2 = − (1 − φ) 2φ − 1 . Inserting these in the general solution gives fn = 1 2φ − 1 (φ n+1 − (1 − φ) n+1)
1.3. Fractal Fer This is an amazing equation. The right-hand side involves powers and quo- tients of irrational numbers, but the result is a sequence of integers. You can check this with matlaB, displaying the results in scientific notation format long e f=(phi.^(n+1)-(1-phi).(n+1))/(2*phi-1) Bt operator is an element-by-element power operator. It is not necessary to or the final division because (2*phi-1) is a scalar quantity. The computed llt starts with 1.000000000000000e+000 2.000000000000000e+000 3.000000000000000e+000 8.000000000000002e+000 1.300000000000000e+001 3.400000000000001e+001 and ends with 5.702887000000007e+006 9.2274650000000 1.493035200000002e 2.415781700000003e+007 3.908816900000005e+007 6.324598600000007e+007 1.023341550000001e+008 1.655801410000002e+008 Roundoff error prevents the results from being exact integers, but finishes the job 1.3 Fractal Fern The M-files fern. m and finitefern m produce the Fractal Fern"described by Michael Barnsley in Fractals Everywhere 1. They generate and plot a potentially infinite sequence of random, but carefully choreographed, points in the plane. The runs forever, producing an increasingly dense plot. The command
1.3. Fractal Fern 13 This is an amazing equation. The right-hand side involves powers and quotients of irrational numbers, but the result is a sequence of integers. You can check this with Matlab, displaying the results in scientific notation. format long e n = (1:40)’; f = (phi.^(n+1) - (1-phi).^(n+1))/(2*phi-1) The .^ operator is an element-by-element power operator. It is not necessary to use ./ for the final division because (2*phi-1) is a scalar quantity. The computed result starts with f = 1.000000000000000e+000 2.000000000000000e+000 3.000000000000000e+000 5.000000000000001e+000 8.000000000000002e+000 1.300000000000000e+001 2.100000000000000e+001 3.400000000000001e+001 and ends with 5.702887000000007e+006 9.227465000000011e+006 1.493035200000002e+007 2.415781700000003e+007 3.908816900000005e+007 6.324598600000007e+007 1.023341550000001e+008 1.655801410000002e+008 Roundoff error prevents the results from being exact integers, but f = round(f) finishes the job. 1.3 Fractal Fern The M-files fern.m and finitefern.m produce the “Fractal Fern” described by Michael Barnsley in Fractals Everywhere [1]. They generate and plot a potentially infinite sequence of random, but carefully choreographed, points in the plane. The command fern runs forever, producing an increasingly dense plot. The command
Chapter 1. Introduction to MATLAB Figure 1.3. Fractal fern. finitefern(n) generates n points and a plot like Figure 1.3. The command finitefern(n, 's') shows the generation of the points one at a time. The command F= finitefern(n); generates, but does not plot, n points and returns an array of zeros and ones for use with sparse matrix and image-processing functions The NCM collection also includes fern. png, a 768-by-1024 color image with half a million points that you can view with a browser or a paint program. You can also view the file with F= imread('fern png If you like the image, you might even choose to make it your computer desktop background. However, you should really run fern on your own computer to see tI dynamics of the emerging fern in high resolution
14 Chapter 1. Introduction to MATLAB Figure 1.3. Fractal fern. finitefern(n) generates n points and a plot like Figure 1.3. The command finitefern(n,’s’) shows the generation of the points one at a time. The command F = finitefern(n); generates, but does not plot, n points and returns an array of zeros and ones for use with sparse matrix and image-processing functions. The NCM collection also includes fern.png, a 768-by-1024 color image with half a million points that you can view with a browser or a paint program. You can also view the file with F = imread(’fern.png’); image(F) If you like the image, you might even choose to make it your computer desktop background. However, you should really run fern on your own computer to see the dynamics of the emerging fern in high resolution
1.3. Fractal Fern The fern is generated by repeated transformations of a point in the plane. Let a be a vector with two components, ai and x2, representing the point. There are four different transformations. all of them of the form x→Ax+b, with different matrices A and vectors b. These are known as affine transformation The most frequently used transformation has 0.850.04 A=(-0040.5),b=(16 This transformation shortens and rotates aa little bit, then adds 1.6 to its second component. Repeated application of this transformation moves the point up and to the right, heading toward the upper tip of the fern. Every once in a while, one of the other three transformations is picked at random. These transformations move the point into the lower subfern on the right, the lower subfern on the left, or the stem Here is the complete fractal fern program. function fern AFERN MATLAB implementation of the Fractal Fern ZMichael Barnsley, Fractals Everywhere, Academic Press, 1993 AThis version runs forever, or until stop is toggled See also: FINITEFERN set(gcf, 'color,,'white,,",, 'none 'numbertitle,,'off, 'name,'Fractal Fern,) h=plot(x(1),x(2),’,); darkgreen= [O 2/301 set(h,’ markersize),1,’ color, darkgreen, erasemode’,none3); axis([-33010]) axis off stop =u ('style,,'toggle','string','stop back hite’) 91.00] 04.85];b1=[0;1.6]; A2=[.20-.26;.23.22];b2=[0;1.6] A3=[-.1528;.26.24];b3=[0;.44] A4=[00;0.16
1.3. Fractal Fern 15 The fern is generated by repeated transformations of a point in the plane. Let x be a vector with two components, x1 and x2, representing the point. There are four different transformations, all of them of the form x → Ax + b, with different matrices A and vectors b. These are known as affine transformations. The most frequently used transformation has A = µ 0.85 0.04 −0.04 0.85 ¶ , b = µ 0 1.6 ¶ . This transformation shortens and rotates x a little bit, then adds 1.6 to its second component. Repeated application of this transformation moves the point up and to the right, heading toward the upper tip of the fern. Every once in a while, one of the other three transformations is picked at random. These transformations move the point into the lower subfern on the right, the lower subfern on the left, or the stem. Here is the complete fractal fern program. function fern %FERN MATLAB implementation of the Fractal Fern %Michael Barnsley, Fractals Everywhere, Academic Press,1993 %This version runs forever, or until stop is toggled. %See also: FINITEFERN. shg clf reset set(gcf,’color’,’white’,’menubar’,’none’, ... ’numbertitle’,’off’,’name’,’Fractal Fern’) x = [.5; .5]; h = plot(x(1),x(2),’.’); darkgreen = [0 2/3 0]; set(h,’markersize’,1,’color’,darkgreen,’erasemode’,’none’); axis([-3 3 0 10]) axis off stop = uicontrol(’style’,’toggle’,’string’,’stop’, ... ’background’,’white’); drawnow p = [ .85 .92 .99 1.00]; A1 = [ .85 .04; -.04 .85]; b1 = [0; 1.6]; A2 = [ .20 -.26; .23 .22]; b2 = [0; 1.6]; A3 = [-.15 .28; .26 .24]; b3 = [0; .44]; A4 = [ 0 0 ; 0 .16]; cnt = 1;