# Kapitel 12: Rekursiv definierte Folgen. # =========================== # In diesem Kapitel nutzen wir die graphischen F"ahigkeiten von Maple. # (Andere M"oglichkeit: "rsolve" --> Kap. 13) # ===================================== # 1) Ein Programm zur Berechnung von Folgengliedern. # ----------------------------------------------------------------- # Aufg. 12.1 # Die Folge {a[n], n=1..infinity sei definiert durch a[1]=1/4 , # a[n+1]=a[n]^2+1/4 # f"ur nat"urliches n . # Man bestimme ihren Grenzwert f"ur n gegen infinity. # Das folgende Programm definiert eine Funktion a der Variable n , so # dass a(n)=a[n] ist. > a:=proc(n) local j, result; result:=1/4; for j from 2 to n do > result^2+1/4; result:="; od; end; # Erkl"arung .... # Test: > [a(1),a(2),a(3),a(4)]; > a(1); # F"ur n=1 baue ein: RETURN('procname(args)'). # evalf > aa:=proc(n) local j, result; result:=1/4; if > n<2 then RETURN('procname(args)') else for j from 2 to n do > evalf(result^2+1/4); result:="; od; fi; end; # Der letzte der folgenden Befehle braucht ca. 20 Sekunden: > aa(1);aa(2);aa(3);aa(4);aa(10);aa(100);aa(1000);aa(10000);aa(100000); # Grenzwert =1/2 ? > limit(aa(n),n=infinity); Error, (in aa) cannot evaluate boolean > limit('aa(n)','n'=infinity); # Ohne "evalf": > limit('a(n)','n'=infinity); > ?limit # "Limit" verarbeitet nur "algebraic expressions", dazu geh"oren nicht # die Programme. # "Most limits are resolved by computing series". # =========================================== # 2) Eine rekursive Folge mit Parameter. # ---------------------------------------------------------------------- # ----- # Aufgabe 12.2 # Die Folge (a[n]) , n=1,2,3,... sei definiert durch # a[1]=x , a[n+1]=(a[n]+x/a[n])/2 , f"ur x>=1 . # Man bestimme ihren Grenzwert f"ur n gegen unendlich. # Ein Programm zur numerischen Berechnung und graphischen Darstellung # der Folgenglieder: > a:= proc(n, x) local j, result ; if n<1 then FAIL else result := > evalf(x); for j from 2 to n do result:=evalf(1/2*(result + x/result)); > od; result; fi; end; # Probe f"ur x=3: > x:=3; > a(0,x); a(1,x); a(2,x); a(3,x); a(4,x); # Falls der Konvergenzbeweis auf theoretischem Wege (Monotonie und # Beschr"anktheit) erbracht ist und durch Einsetzen von a[n]=a und # a[n+1]=a in die Rekursionsgleichung und Aufl"osen von # a=(a+3/a)/2 nach a festgestellt ist, da"s der Grenzwert sqrt(a) # ist (das kann Maple machen) kann durch Aufrufen des numerischen Wertes # von sqrt(3) gepr"uft werden, wie gut die erreichte N"aherung ist: > solve(a=(a+3/a)/2,a); > evalf(sqrt(3)); # Dasselbe auf 30 Stellen genau: > Digits:=30; > a(2,x); a(3,x); a(4,x); a(5,x); a(6,x);a(7,x);a(8,x); > evalf(sqrt(3)); # Mit n=7 erreicht man also bereits 29 Stellen hinter dem Komma. # ============================================ # Wir betrachten nun auch Werte 0 x:=1/3; > Digits; > a(1,x); a(2,x); a(3,x); a(4,x); a(5,x); a(6,x);a(7,x); a(8,x); > evalf(sqrt(1/3)); # ============================================ # Wir wollen nun eine graphische Darstellung der Folgenglieder # erzeugen. Dazu kann der Befehl "plot" verwendet werden, wenn # die Koordinaten der Punkte als Liste (Menge) von Listen ein- # gegeben werden. > Digits:=10; > [seq([i,a(i,1/3)], i=1..10)]; > plot(", style=point); # Besser lesbar ist das Bild mit "style=line": > plot([seq([i,a(i,1/3)],i=1..10)],style=line); # Mehrere Folgen in einem Bild (f"ur x=1/3 , x=1/4 , x=1/5 ) erh"alt # man, indem man eine Menge in {. . . } eingibt: > plot(\{[seq([i,a(i,1/3)],i=1..10)],[seq([i,a(i,1/4)],i=1..10)],[seq([i > ,a(i,1/5)],i=1..10)]\},style=line); # ============================================ # 3) Variable Anfangswerte. # -------------------------------- # Bisher war der Anfangswert x identisch mit dem Parameter x in der # Rekursionsformel. Das folgende modifizierte Programm enth"alt als # Startwert eine Gr"osse s, die von x verschieden sein kann. > A:= proc(n,x,s) local j, result ; if n<1 then FAIL else result := > evalf(s); for j from 2 to n do result:=evalf(1/2*(result + x/result)); > od; result; fi; end; # Test mit x=1/3 und Startwerten s=1/4 , 1/3 , 1/2 , 1 : > plot(\{[seq([i,A(i,1/3,1/4)],i=1..10)],[seq([i,A(i,1/3,1/3)],i=1..10)] > ,[seq([i,A(i,1/3,1/2)],i=1..10)],[seq([i,A(i,1/3,1)],i=1..10)]\},style > =line); # ============================================ # 4) Mandelbrot--Menge. # ---------------------------- # Obwohl Maple f"ur die Konvergenzpr"ufung von rekursiven Folgen nicht # geeignet ist, kann eine bekannte Anwendung solcher # Folgen mit Maple behandelt werden, bei der es um Divergenz # geht, sogenannte Mandelbrot--Mengen. # Unser erstes Beispiel (Aufgabe 12.1) ist bereits ein Spezialfall # davon: # Es stellt einen Punkt einer Mandelbrot--Menge dar. Die gesamte Menge # erh"alt man, indem man die Zahl 1/4, die dort sowohl als Anfangswert # als auch in der Rekursionsformel auftritt, durch eine komplexe Zahl # x+iy ersetzt: # a[n+1]=a[n]^2+x+I*y , a[1]=x+I*y , # Dann besteht die Folge (a[n]) ebenfalls aus komplexen # Zahlen. # Das folgende kurze Programm stammt aus # http://samuel.math.rwth-aachen.de/MapleAnswers/138.html # Siehe auch [16], S.260 - 262. # # Damit ist es m"oglich, im Laufe einer halben Stunde (!) 90 000 # Punkte zu bearbeiten. Das Ergebnis ist das sogenannte Apfelm"annchen, # eine Figur, die bei fortlaufender Vergr"osserung immer neue Details # zeigt, in denen sich ein bestimmtes Grundmuster wiederholt. > mandelbrot:=proc(x, y) local z, m; z:=evalf(x+y*I); m:=0; to 25 while > abs(z)<2 do z:=z^2+(x+y*I); m:=m+1; od; m;end; # Dabei ist die Zeile "to 25 while abs(z)<2 do .... od" eine # verk"urzte Form von "for j=0 to 25 while abs(z)<2 do .... od". # Da der Iterationsindex j in der Schleife nicht vorkommt, darf # man ihn weglassen. # Die folgenden Bilder sollte man auf dem eigenen Computer zun"achst # mit geringerer Aufl"osung (z.B. "grid=[49,49]") erzeugen, und sich an # die Leistungsgrenze des Computers langsam herantasten. > with(plots): > plot3d('mandelbrot(x,y)', 'x'=-2 .. 0.5, > 'y'=-1.2 .. 1.2,grid=[249,249],shading=zhue,orientation=[76,4]); # Eine kleine Modifikation des Programms bewirkt, dass nur die Punkte # x+iy erscheinen, bei denen der Wert m=25 erreicht wird: > mandelbrotPLAIN:=proc(x, y) local z, > m,result; z:=evalf(x+y*I); m:=0; > to 25 while abs(z)<2 do z:=z^2+(x+y*I); m:=m+1; od; if m=25 then > result:=1 else result:=FAIL fi;result; end; > plot3d('mandelbrotPLAIN(x,y)', 'x'=-2 .. 0.5,'y'=-1.2 .. 1.2, > grid=[249,249],style=patch,color=black,orientation=[90,0]); # Nun kann man sich davon "uberzeugen, dass eine "Detailvergr"osserung" # tats"achlich "ahnliche Strukturen aufweist: > plot3d('mandelbrotPLAIN(x,y)', 'x'=-0.3 .. > 0.1, 'y'=0.6 .. 1, grid=[300, 300],style=patch, > color=black,orientation=[90,0]); >