Mathe II für Informatiker Sommersemester 05 Walter Oevel 17. 5. 2005

Ü b u n g s b l a t t 6

Lösungen von ∗-Aufgaben sind per Web-Formular unter http://math-www.upb.de/~walter (⟶ Lehre SS 05 ⟶ Übungen) bis spätestens Do, 26.5.05, abzuliefern. Lösungen von ∗∗-Aufgaben sind schriftlich abzugeben. Sie werden zu Beginn der Vorlesung am Mi, 25.5.05 eingesammelt.

Aufgabe 39: (Von Schnecken und Bäumen. Die harmonische Reihe) Eine Schnecke beginnt, einen 1 Meter hohen Baum hochzukriechen, wobei sie jeden Tag die Strecke ϵ ∈ (0, 1) schafft. In der Nacht ruht sie, während der Baum um einen Meter wächst (kurioserweise wächst dieser Baum nur nachts). Wird die Schnecke jemals die Baumspitze erreichen? Wie alt wird sie sein, wenn sie täglich nur 10 cm zurücklegt?

Musterlösung: Am Morgen des ersten Tages befindet sich die Schnecke auf der Höhe m_{1} = 0, am Abend des ersten Tages auf der Höhe a_{1} = ϵ. Am Morgen des zweiten Tages wacht sie in der Höhe m_{2} = \frac{2}{1} · a_{1} auf (sie ist durch das Wachstums des Baums mittransportiert worden) und erreicht am Abend die Höhe a_{2} = m_{2} + ϵ. Usw. Sie erreiche am Abend des n-ten Tages die Höhe a_{n}. Am Morgen des (n + 1)-ten Tages wacht sie in der Höhe m_{n+1} = \frac{n+1}{n} · a_{n} auf (der Baum ist von n auf n + 1 Meter gewachsen und hat sie dabei um einen entsprechenden Bruchteil mitgenommen). Abends hat sie die Höhe a_{n+1} = m_{n+1} + ϵ erreicht:

m_{n+1} = \frac{n + 1}{n} · a_{n}, a_{n+1} = m_{n+1} + ϵ.

Die jeweils abends erreichte Höhe (a_{n}) ist damit durch die Rekursion

a_{n+1} = \frac{n + 1}{n} · a_{n} + ϵ, a_{1} = ϵ

gegeben, also

\frac{a_{n+1}}{n + 1} = \frac{a_{n}}{n} + \frac{ϵ}{n + 1}, a_{1} = ϵ.

Betrachtet man b_{n} := a_{n}/n, so ist die Folge (b_{n}) durch die Rekursion

b_{n+1} = b_{n} + \frac{ϵ}{n + 1}, b_{1} = ϵ

gegeben:

b_{n+1} = b_{n} + \frac{ϵ}{n + 1} = b_{n−1} + \frac{ϵ}{n} + \frac{ϵ}{n + 1} = b_{n−2} + \frac{ϵ}{n − 1} + \frac{ϵ}{n} + \frac{ϵ}{n + 1}

= … = b_{1} + \frac{ϵ}{2} + ⋯ + \frac{ϵ}{n − 1} + \frac{ϵ}{n} + \frac{ϵ}{n + 1} = ϵ · ∑_{k=1}^{n+1} \frac{1}{k} .

Da der Baum am n-ten Tag die Höhe n hat, erreicht die Schnecke die Baumspitze an dem Tag, für den zum ersten Mal b_{n} ≥ 1 gilt. Da ∑_{k} \frac{1}{k} uneigentlich gegen ∞ konvergiert, wird sie irgendwann einmal die Baumspitze erreichen!

Für ϵ = 0.1 (Meter) ist die Bedingung

b_{n} = 0.1 · ∑_{k=1}^{n} \frac{1}{k} ≥ 1 ⇔ ∑_{k=1}^{n} \frac{1}{k} ≥ 10

zu erfüllen. Durch Ausprobieren mit MuPAD erhält man:

n  ∑_{k=1}^{n} \frac{1}{k}
10 2.9289...
100 5.1873...
1000 7.4854...
2000 8.1783...
4000 8.8713...
8000 9.0945...
10 000 9.7876...
12 000 9.9699...
12 366 9.999962...
12 367 10.000043... (geschafft!)

Die Schnecke ist dann etwa 12 367/365 ≈ 33.88 Jahre alt, der Baum ist über 12 km hoch.

Aufgabe 40: (Reihen. Diverse Konvergenzkriterien) Untersuche die folgenden Reihen auf Konvergenz:

a) ∑_{k=1}^{n} \frac{1}{k + \sqrt{k}} , b) ∑_{k=2}^{n} \frac{1}{k^{2} − \sqrt{k}} , c) ∑_{k=1}^{n} \frac{\sqrt{k + 1} − \sqrt{k − 1}}{\sqrt{k}}.

d) ∑_{k=1}^{n} \frac{\sqrt{k + 1} − \sqrt{k − 1}}{k}, e) ∑_{k=1}^{n} \frac{k!}{k^{k}} , f) ∑_{k=1}^{n} \frac{e^{−k}}{e^{−2·k}} , g) ∑_{k=1}^{n} \frac{e^{−2·k}}{e^{−k}} .

Musterlösung:

a) Divergenz nach dem Minorantenkriterium. Es gilt

\frac{1}{k + \sqrt{k}} ≥ \frac{1}{k + k} = \frac{1}{2 · k} .

Damit ist ∑_{k} \frac{1}{2·k} eine divergente Minorante.

b) Konvergenz nach dem Majorantenkriterium. Es gilt

\frac{1}{k^{2} − \sqrt{k}} ≤ \frac{1}{k^{2} − k} = \frac{1}{k · (k − 1)}.

Bekannterweise konvergiert ∑_{k=2}^{∞} \frac{1}{k · (k − 1)} = ∑_{k=1}^{∞} \frac{1}{(k + 1) · k} und bildet damit eine konvergente Majo-

rante. c) Divergenz nach dem Minorantenkriterium. Es gilt

\frac{\sqrt{k + 1} − \sqrt{k − 1}}{\sqrt{k}} = \frac{1}{\sqrt{k}} · \frac{(\sqrt{k + 1} − \sqrt{k − 1}) · (\sqrt{k + 1} + \sqrt{k − 1})}{\sqrt{k + 1} + \sqrt{k − 1}}

= \frac{1}{\sqrt{k}} · \frac{2}{\sqrt{k + 1} + \sqrt{k − 1}} = \frac{1}{\sqrt{k}} · \frac{2}{\sqrt{k} · (\sqrt{1 + \frac{1}{k}} + \sqrt{1 − \frac{1}{k}} )} = \frac{1}{k} · \frac{2}{\sqrt{1 + \frac{1}{k}} + \sqrt{1 − \frac{1}{k}}} .

Der hintere Faktor konvergiert gegen 1, ist also sicherlich größer als 1/2 für hinreichned großes k. Damit folgt für hinreichend große k

\frac{\sqrt{k + 1} − \sqrt{k − 1}}{\sqrt{k}} ≥ \frac{1}{2 · k} .

Damit ist ∑_{k} \frac{1}{2·k} eine divergente Minorante.

d) Konvergenz nach dem Majorantenkriterium. Analog zu c) gilt

\frac{\sqrt{k + 1} − \sqrt{k − 1}}{k} = \frac{1}{k} · \frac{(\sqrt{k + 1} − \sqrt{k − 1}) · (\sqrt{k + 1} + \sqrt{k − 1})}{\sqrt{k + 1} + \sqrt{k − 1}}

= \frac{1}{k} · \frac{2}{\sqrt{k + 1} + \sqrt{k − 1}} = \frac{1}{k} · \frac{2}{\sqrt{k} · (\sqrt{1 + \frac{1}{k}} + \sqrt{1 − \frac{1}{k}} )} = \frac{1}{k^{3/2}} · \frac{2}{\sqrt{1 + \frac{1}{k}} + \sqrt{1 − \frac{1}{k}}} .

Der hintere Faktor konvergiert gegen 1, ist also sicherlich kleiner als 2 für hinreichned großes k. Damit folgt für hinreichend grosse k

\frac{\sqrt{k + 1} − \sqrt{k − 1}}{k} ≤ \frac{2}{k^{3/2}} .

Nach Beispiel 3.25 ist ∑_{k} \frac{2}{k^{3/2}} eine konvergente Majorante.

e) Das Quotientenkriterium für z_{k} = \frac{k!}{k^{k}} liefert

\frac{z_{k+1}}{z_{k}} = \frac{(k + 1)!/(k + 1)^{k+1}}{k!/k^{k}} = (k + 1)\frac{k^{k}}{(k + 1)^{k+1}} = \frac{k^{k}}{(k + 1)^{k}}

= (\frac{k}{k + 1})^{k} = ( \frac{1}{\frac{k+1}{k}} )^{k} = \frac{1}{(1 + \frac{1}{k})^{k}} .

Mit (1 + \frac{1}{k})^{k} → e = 2.718... konvergiert \frac{z_{k+1}}{z_{k}} gegen 1/e = 0.367.... Damit gilt für alle hinreichend großen k sicherlich \frac{z_{k+1}}{z_{k}} ≤ \frac{1}{2}. Nach dem Quotientenkriterium konvergiert die Reihe.

f) Es gilt

\frac{e^{−k}}{e^{−2·k}} = e^{2·k} · e^{−k} = e^{k}.

Die Summanden bilden keine Nullfolge. Damit kann die Reihe nicht konvergieren.

g) Konvergenz nach dem Majorantenkriterium. Es gilt

\frac{e^{−2 k}}{e^{−k}} = \frac{1}{e^{2·k} · e^{−k}} = \frac{1}{e^{k}} = \frac{1}{(2.718...)^{k}} ≤ \frac{1}{2^{k}} .

Die geometrische Reihe ∑_{k}(\frac{1}{2})^{k} ist damit eine konvergente Majorante.

Aufgabe 41**: (Konvergenz von Reihen. Quotientenkriterium. 5 + 5 Bonuspunkte) Diese Aufgabe kann schriftlich bearbeitet werden. Bearbeitungen werden zu Beginn der Vorlesung am Mi, 25.5.05, eingesammelt.

Betrachte die Reihe f(x) = ∑_{k=1}^{∞} F_{k} ·x^{k}, wo F_{k} die in Aufgabe 31 definierten Fibonacci–Zahlen

sind.

a) Für welche Werte von x konvergiert diese Reihe?

Anleitung: Quotientenkriterium. Verwende das Ergebnis von Aufgabe 31.a).

b) Berechne (1−x−x^{2})·f(x). Welche (rationale) Funktion wird auf dem Konvergenzbereich der Reihe durch f(x) dargestellt?

Musterlösung:

a) Das Quotientenkriterium garantiert Konvergenz, wenn bis auf endlich viele Indizes

\frac{F_{k+1} · |x|^{k+1}}{F_{k} · |x|^{k}} = x_{k} · |x|

durch einen Wert < 1 beschränkt ist. Hierbei konvergiert x_{k} = F_{k+1}/F_{k} nach Aufgabe 31.a) gegen den Grenzwert x^{∗} = \frac{1+\sqrt{5}}{2}. Für jedes x mit x^{∗} · |x| < 1 folgt für ϵ = \frac{1−x^{∗}·|x|}{2·|x|} > 0:

x_{k} · |x| ≤ (x^{∗} + ϵ) · |x| = (x^{∗} + \frac{1 − x^{∗} · |x|}{2 · |x|}) · |x| = x^{∗} · |x| + \frac{1 − x^{∗} · |x|}{2} = \frac{1 + x^{∗} · |x|}{2}

für alle hinreichend großen Indizes. Diese Schranke ist kleiner als 1, womit das Quotientenkriterium erfüllt ist. Also: die Reihe konvergiert für alle x mit

|x| < \frac{1}{x^{∗}} = \frac{2}{1 + \sqrt{5}} = \frac{\sqrt{5} − 1}{2} ≈ 0.618... .

b) Mit den Rechenregeln für Reihen und der rekursiven Definition F_{n+1} = F_{n} + F_{n−1} der Fibonacci-Zahlen folgt:

(1 − x − x^{2}) · (F_{1} · x + F_{2} · x^{2} + F_{3} · x^{3} + …)
= F_{1} · x + F_{2} · x^{2} + F_{3} · x^{3} + F_{4} · x^{4} + …
− F_{1} · x^{2} − F_{2} · x^{3} − F_{3} · x^{4} − …
− F_{1} · x^{3} − F_{2} · x^{4} − … _{0} _{0} _{0}
= F_{1} · x + (F_{2} − F_{1}) · x^{2}.

Mit F_{1} = F_{2} = 1 ergibt sich

(1 − x − x^{2}) · ∑_{k=1}^{∞} F_{k} · x^{k} = x ⇒ ∑_{k=1}^{∞} F_{k} · x^{k} = \frac{x}{1 − x − x^{2}}

für alle x mit |x| < \frac{2}{1+\sqrt{5}}.

Aufgabe 42*: (Wurzelkriterium. 10 Bonuspunkte) Seien M_{1}, …, M_{4} Zahlen (die von hex zufällig gewählt werden). Definiere die Folge (c_{n}) rekursiv durch

c_{n} = M_{1} · c_{n−1} + M_{2}, c_{0} = M_{3}.

Bestimme eine Konstante r, so dass die Reihe

∑_{k=0}^{∞} \frac{c_{k} · x^{k}}{M_{4}^{k/2}}

für alle x mit |x| < r konvergiert und für alle x mit |x| > r divergiert (man nennt r den ”Konvergenzradius“ der Reihe). Anleitung: Wurzelkriterium. Verwende ohne Beweis, dass die Folge (c_{n}) gegen einen Grenzwert c > 0 konvergiert (hex wählt die Zahlen geeignet).

Musterlösung: Das Wurzelkriterium liefert Konvergenz, wenn

k \sqrt{\frac{|c_{k}| · |x|^{k}}{|M_{4}|^{k/2}}} = \frac{^{k} \sqrt{|c_{k}|} · |x|}{\sqrt{|M_{4}|}}

durch eine Konstante K < 1 beschränkt ist Da (c_{k}) gegen einen Grenzwert c > 0 konvergiert, gilt \frac{c}{2} ≤ c_{k} ≤ 2 · c für hinreichend große Indizes. Per Intervallkonvergenz

k \sqrt{\frac{c}{2}} < ^{k} \sqrt{c_{k}} < ^{k} \sqrt{2 · c}

folgt lim_{k→∞} ^{k} \sqrt{c_{k}} = 1, da lim_{k→∞} ^{k} \sqrt{\frac{c}{2}} = 1 und lim_{k→∞} ^{k} \sqrt{2 · c} = 1. Damit ist für

\frac{|x|}{\sqrt{|M_{4}|}} < 1

sicherlich das Wurzelkriterium erfüllt. Andererseits, für

\frac{|x|}{\sqrt{|M_{4}|}} > 1

ist die Folge

c_{k} · \frac{x^{k}}{|M_{4}|^{k/2}} ≈^{k≫1} c · (\frac{x}{\sqrt{|M_{4}|}})^{k}

sicherlich keine Nullfolge, die Reihe kann also nicht konvergieren. Der gesuchte Konvergenzradius ist damit

r = \sqrt{|M_{4}|}.

Anmerkung: der Grenzwert c der Folge (c_{n}) geht in die Lösung gar nicht ein. Die Berechnung von c ist überflüssig und dient nur als nützliche Übung für diejenigen, die nicht gemerkt haben, dass man den Wert von c gar nicht braucht.

Aufgabe 43: (Die Exponentialreihe. Einfacher Beweis) Beweise mit Hilfe des Cauchy-Produkts der Reihen für e^{x} und e^{y} die Funktionalgleichung e^{x} · e^{y} = e^{x+y} der Exponentialfunktion.

Hilfestellung: verwende den Binomischen Lehrsatz (x + y)^{n} = ∑_{k=0}^{n} \binom{n}{k} · x^{k} · y^{n−k}.

Musterlösung: Die Koeffizienten c_{n} des Cauchy-Produkts

∑_{n=0}^{∞} c_{n} = ∑_{i=0}^{∞} \frac{x^{i}}{i!} · ∑_{j=0}^{∞} \frac{y^{j}}{j!}

sind durch

c_{n} = ∑_{{i,j \atop i+j=n}} \frac{x^{i}}{i!} · \frac{y^{j}}{j!} = ∑_{i=0}^{n} \frac{x^{i}}{i!} · \frac{y^{n−i}}{(n − i)!} = \frac{1}{n!} · ∑_{i=0}^{n} \frac{n! · x^{i} · y^{n−i}}{i! · (n − i)!} = \frac{1}{n!} · ∑_{i=0}^{n} \binom{n}{i} · x^{i} · y^{n−i} = \frac{(x + y)^{n}}{n!}

gegeben, also

e^{x} · e^{y} = ∑_{i=0}^{∞} \frac{x^{i}}{i!} · ∑_{j=0}^{∞} \frac{y^{j}}{j!} = ∑_{n=0}^{∞} \frac{(x + y)^{n}}{n!} = e^{x+y}.

Aufgabe 44: (Die Exponentialreihe) Es geht um die numerische Auswertung der Exponentialfunktion mittels Gleitpunktarithmetik.

a) (Technisch anspruchsvoll) Sei x eine reelle Gleitpunktzahl mit |x| ≤ \frac{1}{2}. Wieviele Reihenglieder der Exponentialreihe S_{n}(x) = ∑_{k=0}^{n} \frac{x^{k}}{k!} müssen aufaddiert werden, damit |e^{x} − S_{n}(x)| ≤ \frac{|e^{x}|}{10^{16}} garantiert werden kann? (Diese Bedingung besagt, dass S_{n}(x) die ersten 16 Dezimalstellen von e^{x} korrekt approximiert.)

b) Berechne mittels MuPAD einige Partialsummen der Exponentialreihe für x = −123.456 mit DIGITS = 16 und vergleiche mit dem von der Systemfunktion exp gelieferten Wert. Gelingt es, durch die Partialsummen eine Approximation dieses Wertes zu erreichen? Erklärung?

Relevante MuPAD Funktionen: exp, plus, $.

c) Wie kann a) für |x| > \frac{1}{2} verwendet werden? Benutze die Funktionalgleichung der Exponentialfunktion, um trotz des Desasters in b) über die Exponentialreihe zu einer Approximation von e^{−123.456} zu gelangen, in der die führenden Dezimalstellen korrekt sind.

Musterlösung: Aus der Reihendarstellung ist unmittelbar klar, dass e^{x} monoton wachsend in x ist.

a) Wegen der Monotonie gilt für reelles x mit |x| ≤ \frac{1}{2} 0.6065 ≈ e^{− \frac{1}{2}} ≤ e^{x}.

Es gilt

|e^{x} − S_{n}(x)| = | ∑_{k=0}^{∞} \frac{x^{k}}{k!} − ∑_{k=0}^{n} \frac{x^{k}}{k!} | = | ∑_{k=n+1}^{∞} \frac{x^{k}}{k!} | ≤ ∑_{k=n+1}^{∞} \frac{|x|^{k}}{k!}

≤ ∑_{k=n+1}^{∞} \frac{1}{2^{k} · k!} = \frac{1}{2^{n+1} · (n + 1)!} + \frac{1}{2^{n+2} · (n + 2)!} + ⋯

≤ \frac{1}{2^{n+1} · (n + 1)!} · (1 + \frac{1}{2 · (n + 2)} + \frac{1}{4 · (n + 2) · (n + 3)} + ⋯)

≤ \frac{1}{2^{n+1} · (n + 1)!} · (1 + \frac{1}{2} + \frac{1}{4} + ⋯) = \frac{2}{2^{n+1} · (n + 1)!} = \frac{1}{2^{n} · (n + 1)!}.

Durch Ausprobieren findet man folgende Werte:

\begin{matrix}n & 5 & 10 & 11 & 12 & 13 & 14 \\ \frac{1}{2^{n}·(n+1)!} & 4.3 · 10^{−5} & 2.4 · 10^{−11} & 1.0 · 10^{−12} & 3.9 · 10^{−14} & 1.4 · 10^{−15} & 4.7 · 10^{−17} \end{matrix}

Damit reicht n = 14, um

|e^{x} − S_{n}(x)| ≤ \frac{4.7}{10^{17}} ≤ \frac{0.6065}{10^{16}} ≤ \frac{e^{x}}{10^{16}}

garantieren zu können.

b) Numerisches Experiment:

>> DIGITS:= 16:
>> x:=-123.456:
>> _plus(x^k/k! $ k= 0..100)
                     8.368805809476164e50
>> _plus(x^k/k! $ k= 0..200)
                     9.692087156726235e42
>> _plus(x^k/k! $ k= 0..400)
                     -6.490160608451007e32
>> _plus(x^k/k! $ k= 0..800)
                     -6.490160608451007e32
>> _plus(x^k/k! $ k= 0..1600)
                     -6.490160608451007e32

Der wirkliche Wert ist:

>> exp(-123.456)
                     2.419582541264601e-54

Der Grund für dieses katastrophale Verhalten der numerischen Partialsummen ist ”Auslöschung“: riesige Summanden mit wechselnden Vorzeichen sollen sich zuletzt fast vollständig aufheben und ein sehr kleines Endergebnis liefern. Hier sind einige der Summanden:

\frac{x^{123}}{123!} = −1.48441946501462... · 10^{52}, \frac{x^{124}}{124!} = 1.477907173168104... · 10^{52}.

Bei diesen Zahlen müssten mehr als 106 der führenden Dezimalstellen genau sein, damit die 54-te Nachkommastelle des Endergebnisses (die erste führende Ziffer von e^{−123.456}) korrekt sein kann. Wir benutzen aber nur 16 Dezimalstellen Genauigkeit!

c) Die Idee ist, mit

e^{x} = (e^{\frac{x}{2^{n}}} )^{(2^{n})}

die Exponentialreihe mit hinreichend grossem n für kleine Argumente \frac{x}{2^{n}} auszuwerten. Das Ergebnis kann dann per Repeated Squaring schnell zu e^{x} potenziert werden. Für x = −123.456 wähle 2^{n} = 256, so dass |\frac{x}{2^{n}} | = 0.48225 ≤ \frac{1}{2} gilt. Nach a) kann e^{x/2^{n}} durch die Partialsumme S_{14} der Exponentialreihe auf 16 Dezimalstellen genau approximiert werden;

e^{−123.456/256} ≈ ∑_{k=0}^{14} \frac{(−123.456/256)^{k}}{k!} = 0.6173926942959764...

Damit ergibt sich

e^{−123.456} ≈ (0.6173926942959764...)^{256} = 2.419582541264614 · 10^{−54}.

Dieses Ergebnis ist korrekt bis auf die letzten beiden der angegebenen Ziffern (das Potenzieren verstärkt den Approximationsfehler durch S_{14} etwas).