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

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

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

Aufgabe 32: (Folgen, Konvergenz. Das geometrisch-arithmetische Mittel) Sei 0 < x < y.

a) Zeige x < \sqrt{x · y} < \frac{x + y}{2} < y.

Definiere x_{1} = x, y_{1} = y und dann rekursiv x_{n+1} = \sqrt{x_{n} · y_{n}}, y_{n+1} = \frac{x_{n} + y_{n}}{2} .

b) Zeige, dass (x_{n}) streng monoton steigend und dass (y_{n}) streng monoton fallend ist.

c) Zeige, dass (y_{n} − x_{n}) eine Nullfolge ist.

d) Folgere, dass (x_{n}) und (y_{n}) gegen den selben Grenzwert konvergieren.

Man nennt diesen Grenzwert das ”geometrisch-arithmetische Mittel“ von x und y.

e) Berechne für x = 1, y = 2 die ersten 5 Intervalle [x_{n}, y_{n}]. Wie schnell nehmen die Intervalllängen y_{n} − x_{n} ab?

f) (Etwas anspruchsvoller) Sei x ≥ 1.

i) Zeige: \sqrt{x_{n}} + \sqrt{y_{n}} ≥ 1 für alle n,

ii) Folgere: \sqrt{y_{n}} − \sqrt{x_{n}} ≤ y_{n} − x_{n} für alle n,

iii) Folgere: y_{n+1} − x_{n+1} ≤ \frac{1}{2} · (y_{n} − x_{n})^{2}.

Wieso erklärt iii) die in e) beobachtete schnelle Konvergenz?

Musterlösung:

a) Mit 0 < x < y gilt

x = \sqrt{x^{2}} < \sqrt{x · y}, \frac{x + y}{2} < \frac{y + y}{2} = y.

Weiterhin gilt

\sqrt{x · y} < \frac{x + y}{2} ⇔ x · y < \frac{(x + y)^{2}}{4} ⇔ 4 · x · y < x^{2} + 2 · x · y + y^{2}

⇔ 0 < x^{2} − 2 · x · y + y^{2} = (x − y)^{2},

wobei letztere Ungleichung sicherlich gültig ist. b) Folgt unmittelbar aus a):

x_{n} < \underbrace{\sqrt{x_{n} · y_{n}}}_{x_{n+1}} < \underbrace{\frac{x_{n} + y_{n}}{2}}_{y_{n+1}} < y_{n}.

c) Es gilt

y_{n} − x_{n} = \frac{x_{n−1} + y_{n−1}}{2} − \sqrt{x_{n−1} · y_{n−1}} ≤ \frac{x_{n−1} + y_{n−1}}{2} − x_{n−1} = \frac{y_{n−1} − x_{n−1}}{2} .

Mit dieser rekursiven Beziehung folgt

y_{n} − x_{n} ≤ \frac{y_{n−1} − x_{n−1}}{2} ≤ \frac{y_{n−2} − x_{n−2}}{4} ≤ … ≤ \frac{y_{1} − x_{1}}{2^{n−1}} .

Damit ist (y_{n} − x_{n}) eine Nullfolge.

d) Da (x_{n}) monoton wächst und nach oben durch x_{n} < y_{n} < y beschränkt ist, konvergiert (x_{n}) gegen einen Grenzwert x^{∗}. Da (y_{n}) monoton fällt und nach unten durch x < x_{n} < y_{n} beschränkt ist, konvergiert (y_{n}) gegen einen Grenzwert y^{∗}. Wegen

y^{∗} − x^{∗} = lim_{n→∞} y_{n} − lim_{n→∞} x_{n} = lim_{n→∞}(y_{n} − x_{n}) = 0

stimmen diese Grenzwerte überein.

e) Für x = 1, y = 2 erhält man die Werte:

\begin{matrix}x_{1} = \underline{1}.0, & y_{1} = 2.0, & y_{1} − x_{1} = 1.0, \\ x_{2} = \underline{1.4}14213562, & y_{2} = \underline{1}.5, & y_{2} − x_{2} = 0.085..., \\ x_{3} = \underline{1.456}475315, & y_{3} = \underline{1.45}7106781, & y_{3} − x_{3} = 0.00063..., \\ x_{4} = \underline{1.4567910}14, & y_{4} = \underline{1.4567910}48, & y_{4} − x_{4} = 0.000000034..., \\ x_{5} = \underline{1.456791031}, & y_{5} = \underline{1.456791031}, & y_{5} − x_{5} = 1.00... · 10^{−16}. \end{matrix}

Die unterstrichenen Stellen stimmen mit denen des Grenzwerts überein. Die Folgen (x_{n}), (y_{n}) konvergieren offensichtlich sehr schnell.

f) i) Es gilt 1 ≤ x < x_{n} < y_{n} für alle Indizes, womit sicherlich

\sqrt{x_{n}} + \sqrt{y_{n}} ≥ 1

folgt. ii) Aus \sqrt{x_{n}} + \sqrt{y_{n}} ≥ 1 folgt:

\sqrt{y_{n}} − \sqrt{x_{n}} ≤ (\sqrt{y_{n}} − \sqrt{x_{n}}) · (\sqrt{y_{n}} + \sqrt{x_{n}}) = y_{n} − x_{n}.

iii) Es folgt

y_{n+1} − x_{n+1} = \frac{x_{n} + y_{n}}{2} − \sqrt{x_{n} · y_{n}} = \frac{\sqrt{x_{n}}^{2} + \sqrt{y_{n}}^{2}}{2} − \sqrt{x_{n}} · \sqrt{y_{n}}

= \frac{\sqrt{x_{n}}^{2} − 2 · \sqrt{x_{n}} · \sqrt{y_{n}} + \sqrt{y_{n}}^{2}}{2} = \frac{(\sqrt{x_{n}} − \sqrt{y_{n}})^{2}}{2} ≤ \frac{(y_{n} − x_{n})^{2}}{2} .

Dies erklärt die schnelle Konvergenz: Ist der Abstand der Folgenglieder y_{n} und x_{n} erst einmal klein, ist der nächste Abstand durch Quadrarieren wesentlich kleiner usw.

Aufgabe 33**: (O–Kalkül; 5 + 5 Bonuspunkte) Diese Aufgabe kann schriftlich bearbeitet werden. Bearbeitungen werden zu Beginn der Vorlesung am Mi, 18.5.05, eingesammelt.

Zeige: für n → ∞ gilt

a) \frac{1}{n − 1} + \frac{1}{n + 1} − \frac{2}{n} = O(\frac{1}{n^{3}} ), b) \frac{1}{n − 1} + \frac{1}{n + 1} − \frac{2}{n} = \frac{2}{n^{3}} + O(\frac{1}{n^{5}} ).

Musterlösung: a)

\frac{1}{n − 1} + \frac{1}{n + 1} − \frac{2}{n} = \frac{(n + 1) · n + (n − 1) · n − 2 · (n + 1) · (n − 1)}{(n − 1) · (n + 1) · n}

= \frac{n^{2} + n + n^{2} − n − 2 · (n^{2} − 1)}{n · (n^{2} − 1)} = \frac{2}{n · (n^{2} − 1)}.

Offensichtlich ist

\frac{2/(n · (n^{2} − 1))}{1/n^{3}} = \frac{2 · n^{3}}{n^{3} − 1}

beschränkt (denn diese Folge hat den Grenzwert 2 für n → ∞). Damit gilt

\frac{2}{n · (n^{2} − 1)} = O(\frac{1}{n^{3}} ).

b) Mit a) ergibt sich

\frac{1}{n − 1} + \frac{1}{n + 1} − \frac{2}{n} − \frac{2}{n^{3}} = \frac{2}{n · n^{2} − 1)} − \frac{2}{n^{3}} = \frac{2 · n^{3} − 2 · (n^{3} − n)}{n^{4} · (n^{2} − 1)}

= \frac{2 · n}{n^{4} · (n^{2} − 1)} = \frac{2}{n^{3} · (n^{2} − 1)} = \frac{2}{n^{5} · (1 − \frac{1}{n^{2}} )}.

Dieser Ausdruck ist O(\frac{1}{n^{5}} ), denn

\frac{2/(n^{5} · (1 − \frac{1}{n^{3}} ))}{1/n^{5}} = \frac{2}{1 − \frac{1}{n^{2}}}

ist beschränkt (da konvergent).

Aufgabe 34: (O–Kalkül)

a) Zeige: wenn f(n) = o(g(n)) gilt, dann gilt auch f(n) = O(g(n)).

b) Sei k ∈ ℤ. Wenn f(n) = o(n^{k}) gilt, folgt dann automatisch f(n) = O(n^{k−1})?

c) Sei k ∈ ℤ. Wenn f(n) = o(n^{k}) gilt, folgt dann automatisch f(n) = o(n^{k+1})?

d) Seien k_{1}, k_{2} ∈ ℤ. Zeige O(n^{k_{1}}) · O(n^{k_{2}}) = O(n^{k_{1}+k_{2}}).

Musterlösung:

a) f(n) = o(g(n)) heißt, dass die Folge f(n)/g(n) eine Nullfolge ist und damit automatisch beschränkt ist. Also gilt auch f(n) = O(g(n)).

b) Gegebenbeispiel: Es gilt

f(n) = \frac{1}{n · \sqrt{n}} = o(\frac{1}{n}),

denn

\frac{1/(n · \sqrt{n})}{1/n} = \frac{1}{\sqrt{n}}

ist eine Nullfolge. Es gilt aber nicht f(n) = O(1/n^{2}), denn

\frac{1/(n · \sqrt{n})}{1/n^{2}} = \sqrt{n}

ist unbeschränkt.

c) Wenn f(n) = o(n^{k}), ist

\frac{f(n)}{n^{k}}

eine Nullfolge. Damit ist

\frac{f(n)}{n^{k+1}} = \frac{f(n)}{n^{k}} · \frac{1}{n}

erst recht eine Nullfolge, also gilt in der Tat automatisch f(n) = o(n^{k+1}).

d) f_{1}(n) = O(n^{k_{1}}) bzw. f_{2}(n) = O(n^{k_{2}}) bedeuten, dsss

\frac{f_{1}(n)}{n^{k_{1}}} und \frac{f_{2}(n)}{n^{k_{2}}}

beschränkt sind. Damit folgt, daß

\frac{f_{1}(n) · f_{2}(n)}{n^{k_{1}} · n^{k_{2}}} = \frac{f_{1}(n) · f_{2}(n)}{n^{k_{1}+k_{2}}}

beschränkt ist. Also gilt f_{1}(n) · f_{2}(n) = O(n^{k_{1}+k_{2}}). Dies ist mit O(n^{k_{1}}) · O(n^{k_{2}}) = O(n^{k_{1}+k_{2}}) gemeint.

Aufgabe 35*: (Geometrische Reihen, 10 Bonuspunkte)

Seien M_{1}, M_{2}, M_{3} Zahlen (die von hex zufällig gewählt werden). Berechne ∑_{k=M_{3}}^{∞} \frac{1}{M_{1}^{M_{2}·k}} .

Musterlösung: Sei

c := \frac{1}{M_{1}^{M_{2}}} ∈ (0, 1).

Gefragt ist

∑_{k=M_{3}}^{∞} c^{k} = ∑_{k=0}^{∞} c^{k} − ∑_{k=0}^{M_{3}−1} c^{k} = \frac{1}{1 − c} − \frac{1 − c^{M_{3}}}{1 − c} = \frac{c^{M_{3}}}{1 − c} = \frac{1 / M_{1}^{M_{2}·M_{3}}}{1 − 1 / M_{1}^{M_{2}}}

= \frac{1}{M_{1}^{M_{2}·M_{3}}} · \frac{M_{1}^{M_{2}}}{M_{1}^{M_{2}} − 1} = \frac{1}{M_{1}^{M_{2}·(M_{3}−1)}} · \frac{1}{M_{1}^{M_{2}} − 1} = \frac{1}{M_{1}^{M_{2}·M_{3}} − M_{1}^{M_{2}·(M_{3}−1)}} .

Mit MuPAD:

>> M1:= 3: M2:= 5: M3:= 8:
>> sum(1/ M1^(M2*k), k = M3..infinity)
                    1/12107633913957929094
>> 1/ ( M1^(M2*M3)- M1^(M2*(M3 - 1)) )
                    1/12107633913957929094

Aufgabe 36: (Reihen, p-adische Darstellung) Sei p ∈ {2, 3, 4, …}. Mit der sogenannten ”p-adischen Darstellung“

b_{k} b_{k−1} … b_{1} b_{0} . b_{−1} b_{−2} b_{−3} …

ist die Zahl ∑_{j≤k} b_{j} · p^{j} gemeint, wobei b_{j} ∈ {0, 1, …, p − 1} die ”Ziffern zur Basis p“ genannt

werden. (Für p = 10 sind dies die wohlbekannten Dezimalziffern, für p = 2 die Binärziffern (Bits) b_{j} ∈ {0, 1}.)

a) Berechne die rationale Zahl, die im Binärsystem durch die periodische Entwicklung

1011 . 1100 \overline{10} (= 1011 . 1100 10 10 10 10 …)

gegeben ist.

b) (Erinnerung an die Mathe I) Gegeben sei eine reelle Zahl 0 < x < 1. Gib einen Algorithmus, an, welcher die Ziffern von x zur Basis p berechnet. Verwende als Hilfsmittel nur die sogenannte ”Gauss-Klammer“ ⌊y⌋ = die größte ganze Zahl ≤ y. (In einigen Hochsprachen steht diese Funktion z.B. als trunc zur Verfügung.)

Musterlösung: a)

1011 . 1100 10 10 10 10 …
= 1 · 2^{3} + 0 · 2^{2} + 1 · 2^{1} + 1 · 2^{0} + 1 · 2^{−1} + 1 · 2^{−2} + 0 · 2^{−3} + 0 · 2^{−4}
+1 · 2^{−5} + 0 · 2^{−6} + 1 · 2^{−7} + 0 · 2^{−8} + 1 · 2^{−9} + 0 · 2^{−10} + ⋯
= 2^{3} + 2^{1} + 2^{0} + 2^{−1} + 2^{−2} + (2^{−5} + 2^{−7} + 2^{−9} + ⋯)
= 8 + 2 + 1 + \frac{1}{2} + \frac{1}{4} + \frac{1}{2^{5}} · (1 + 2^{−2} + 2^{−4} + ⋯)
= 8 + 2 + 1 + \frac{1}{2} + \frac{1}{4} + \frac{1}{2^{5}} ∑_{k=0}^{∞} (\frac{1}{4})^{k}
= \frac{47}{4} + \frac{1}{32} · \frac{1}{1 − \frac{1}{4}}
= \frac{47}{4} + \frac{1}{32} · \frac{4}{3}
= \frac{283}{24}.

b) Die Ziffern müssen aus der Menge {0, 1, …, p − 1} sein. Die Idee, an die einzelnen Ziffern zu gelangen, ist: schiebe die Ziffer durch Multiplikation mit einer p-Potenz vor den ”Dezimalpunkt“ und schneide die Nachpunktziffern mittels ⌊ ⌋ ab:

\begin{aligned}b_{−1} & = & ⌊p · x⌋ , & x = 0 . b_{−1} b_{−2} b_{−3} b_{−4} b_{−5} … \\ b_{−2} & = & ⌊p^{2} · (x − \frac{b_{−1}}{p} )⌋ , & x − \frac{b_{−1}}{p} = 0 . 0 b_{−2} b_{−3} b_{−4} b_{−5} … \\ b_{−3} & = & ⌊p^{3} · (x − \frac{b_{−1}}{p} − \frac{b_{−2}}{p^{2}} )⌋ , & x − \frac{b_{−1}}{p} − \frac{b_{−2}}{p^{2}} = 0 . 0 0 b_{−3} b_{−4} b_{−5} … \\ b_{−4} & = & ⌊p^{4} · (x − \frac{b_{−1}}{p} − \frac{b_{−2}}{p^{2}} − \frac{b_{−3}}{p^{3}} )⌋ , & x − \frac{b_{−1}}{p} − \frac{b_{−2}}{p^{2}} − \frac{b_{−3}}{p^{3}} = 0 . 0 0 0 b_{−4} b_{−5} … \end{aligned}

usw, also:

b[-1]:= trunc(p*x);
i:= -1;
repeat
  x:= x - b[-i]/p^(i);
  i:= i + 1;
  b[-i]:= trunc(p^i*x);
until x = 0 end_repeat;

Hierbei ist durch Induktion leicht zu zeigen, dass

y := x − \frac{b_{−1}}{p} − \frac{b_{−2}}{p^{2}} − ⋯ − \frac{b_{−i}}{p^{i}} = 0 . 0 0 … 0 b_{−i−1} b_{−i−2} … ∈ [0, \frac{1}{p^{i}} )

gilt, so dass die Ziffern b_{−i−1} = ⌊p^{i+1} · y⌋ in der Menge {0, 1, …, p − 1} liegen.

Aufgabe 37*: (p-adische Darstellung. 10 Bonuspunkte) Seien M_{1}, …, M_{6} ganze Zahlen (“Ziffern”) aus {0, 2, …, 15} (die von hex zufällig gewählt werden). Welche rationale Zahl wird durch folgende periodische Hexadezimalzahl (Basis p = 16) dargestellt:

M_{1} M_{2} . M_{3} M_{4} \overline{M_{5} M_{6}} (= M_{1} M_{2} . M_{3} M_{4} M_{5} M_{6} M_{5} M_{6} M_{5} M_{6} …) ?

Anleitung: Aufgabe 36.

Musterlösung:

M_{1} M_{2} . M_{3} M_{4} \overline{M_{5} M_{6}}

= M_{1} · p^{1} + M_{2} · p^{0} + \frac{M_{3}}{p} + \frac{M_{4}}{p^{2}} + M_{5} · (\frac{1}{p^{3}} + \frac{1}{p^{5}} + \frac{1}{p^{7}} + ⋯) + M_{6} · (\frac{1}{p^{4}} + \frac{1}{p^{6}} + \frac{1}{p^{8}} + ⋯)

= M_{1} · p + M_{2} + \frac{M_{3}}{p} + \frac{M_{4}}{p^{2}} + M_{5} · \frac{1}{p^{3}} · (1 + \frac{1}{p^{2}} + \frac{1}{p^{4}} + ⋯) + M_{6} · \frac{1}{p^{4}} · (1 + \frac{1}{p^{2}} + \frac{1}{p^{4}} + ⋯)

= M_{1} · p + M_{2} + \frac{M_{3}}{p} + \frac{M_{4}}{p^{2}} + (\frac{M_{5}}{p^{3}} + \frac{M_{6}}{p^{4}} ) · ∑_{k=0}^{∞} (\frac{1}{p^{2}} )^{k}

= M_{1} · p + M_{2} + \frac{M_{3}}{p} + \frac{M_{4}}{p^{2}} + (\frac{M_{5}}{p^{3}} + \frac{M_{6}}{p^{4}} ) · \frac{1}{1 − \frac{1}{p^{2}}}

= M_{1} · p + M_{2} + \frac{M_{3}}{p} + \frac{M_{4}}{p^{2}} + (\frac{M_{5}}{p^{3}} + \frac{M_{6}}{p^{4}} ) · \frac{p^{2}}{p^{2} − 1}.

Z.B. für M_{1}M_{2}...M_{6} = 3456780:

34.56 \overline{80} = 3 · 16 + 4 + \frac{5}{16} + \frac{6}{16}^{2} + (\frac{8}{16^{3}} + \frac{0}{16^{4}} ) · \frac{16^{2}}{16^{2} − 1} = \frac{1708309}{32640}.

Aufgabe 38*: (p-adische Darstellung. 10 Bonuspunkte) Sei M eine Zahl (die von hex zufällig gewählt wird). Berechne die ersten 10 Ziffern b_{−1}, …, b_{−10} ∈ {0, 1, …, 6} zur Basis p = 7 von

\frac{1}{\sqrt{M}} = 0 . b_{−1} b_{−2} b_{−3} ….

Anleitung: Aufgabe 36.b) (MuPAD-Hilfsmittel: trunc. Für Schleifen siehe for, repeat oder while.) Mit der MuPAD-Funktion numlib::g adic kann das Ergebnis überprüft werden.

Musterlösung: Für M = 13, also x = 1/\sqrt{13}, p = 7:

x:= 1/sqrt(13):
p:= 7:
b[-1]:= trunc(p*x);
i:= 1;
repeat
  x:= x - b[-i]/p^i;
  i:= i + 1;
  b[-i]:= trunc(p^i*x);
until i = 10 end_repeat:
b[-i] $ i=1..10
                 1, 6, 4, 0, 6, 2, 6, 5, 0, 6

Probe:

float(1/sqrt(13))
                         0.2773500981
float(_plus(b[-i]/7^i $ i=1..10))
                         0.277350098

Eine weitere Probe: die Ziffern bleiben erhalten, wenn man mit irgendeiner Potenz von p multipliziert. Die Funktion numlib::g adic akzeptiert eine ganze Zahl und berechnet die Ziffern bzgl. einer Basis:

numlib::g_adic(trunc(p^10*1/sqrt(13)), p)
                [6, 0, 5, 6, 2, 6, 0, 4, 6, 1]

Die Ziffern müssen hierbei von rechts nach links gelesen werden; mit revert wird die Liste umgeordnet:

revert(%)
                [1, 6, 4, 0, 6, 2, 6, 5, 0, 6]