close

Anmelden

Neues Passwort anfordern?

Anmeldung mit OpenID

Blatt 2 Lösung

EinbettenHerunterladen
¨
Ubungsblatt
2
Numerik I, Dr. Peter Philip, Arnau Pons Domenech
LMU-M¨
unchen, Wintersemester 2014/2015
24. Oktober 2014
Aufgabe 1
[10 Pkt.]
Sei f1 = O(g1 ) und f2 = O(g2 ) im Punkt x0 ∈ R ∪ {−∞, ∞} (wobei fi , gi : D →
R, D ⊆ R, gi > 0, ∀i). Beweisen oder widerlegen Sie folgende Aussagen bez¨
uglich
des Punktes x0 .
(i) f1 + f2 = O(g1 + g2 )
(ii) f1 − f2 = O(g1 − g2 )
(iii) f1 − f2 = O(g1 + g2 )
(iv) f1 · f2 = O(g1 · g2 )
(v) f1 /f2 = O(g1 /g2 ) wobei f2 , g2 = 0 gilt.
L¨osung
Zu (i):
lim sup
x→x0
f1
f2
f1
f2
f1 + f2
≤ lim sup
+ lim sup
≤ lim sup
+ lim sup
g1 + g2
g1 + g2
g1 + g2
g1
g2
x→x0
x→x0
x→x0
x→x0
<∞
Zu (ii):
Sei x0 = ∞, f1 = 2x, f2 = x, g1 = x2 + 2, g2 = x2 + 1, D = R. Dann gilt f1 = O(g1 ),
f2 = O(g2 ) und g1 , g2 > 0 aber
lim sup
x→x0
x
f1 − f2
= lim sup
=∞
g1 − g2
1
x→x0
Zu (iii):
Analog zu (i)
Zu (iv):
lim sup
x→x0
Zu (v):
f1 · f2
f1
f2
≤ lim sup
· lim sup
<∞
g1 · g2
g1
g2
x→x0
x→x0
Sei x0 = ∞, f1 = x, f2 = x, g1 = x2 , g2 = x4 , D = R \ {0}. Dann gilt f1 = O(g1 ),
f2 = O(g2 ) und g1 , g2 > 0 aber
lim sup
x→x0
f1 /f2
1
= lim sup
= lim sup x2 = ∞
g1 /g2
1/x2
x→x0
x→x0
Aufgabe 2
[10 Pkt.]
(a) Sei b ∈ N, b ≥ 2 und n ∈ N. Weiterhin sei p die Anzahl der Stellen der Darstellung
von n bez¨
uglich der Basis b (dabei wird nat¨
urlich angenommen, dass die erste
Stelle nicht 0 ist und die verschwindenden Koeffizienten von bk mit k < 0 werden
nicht mitgez¨ahlt). Finden Sie eine Formel, die p durch n und b ausdr¨
uckt.
(b) F¨
ur n ∈ N sei b(n) die Anzahl der Ziffern in der Bin¨ardarstellung von n und
d(n) sei die Anzahl der Ziffern in der Dezimaldarstellung von n. Zeigen Sie, dass
b(n)
= log2 10.
limn→∞ d(n)
L¨osung
Zu (a):
Sei N ∈ N so, dass bN ≤ n < bN +1 . Dann hat die Darstellung von n bez¨
uglich der
Basis b genau N + 1 Stellen, also p = N + 1. Wegen N ≤ logb n < N + 1 gilt also
p = N + 1 = logb n + 1.
(1)
Zu (b):
Zun¨achst gilt f¨
ur jedes x ∈ R:
x − 1 < x ≤ x.
(2)
Weiterhin gilt f¨
ur jedes n ∈ N mit n > 1, dass log2 n = log2 10log10 n =(log10 n)(log2 10),
also
log2 n
.
(3)
log2 10 =
log10 n
Nach Teil (a) gilt außerdem
b(n) = log2 n + 1,
d(n) = log10 n + 1.
(4)
Also folgt f¨
ur jedes n ∈ N mit n > 1:
(log2 10)
1
1+
1
log10 n
(3)
=
(4)
=
log2 n (2) log2 n + 1 (4) b(n)
<
=
log10 n + 1
log10 n + 1
d(n)
log2 n + 1 (2) log2 n + 1 (3)
1
<
= log2 10 +
.
log10 n + 1
log10 n
log10 n
(5)
Wegen
lim
n→∞
(log2 10)
1
1+
folgt aus (5), dass limn→∞
1
log10 n
b(n)
d(n)
= lim
n→∞
log2 10 +
1
log10 n
= log2 10,
(6)
= log2 10, was zu zeigen war.
Aufgabe 3
[10 Pkt.]
(a) Sei n ∈ N. Bestimmen sie das kleinste α, f¨
ur das
n → ∞ gilt.
n
k=1
k 2 = O (nα ) im Limes
(b) Zeigen Sie, dass f¨
ur alle n ∈ N und alle α > 0 x (log x)n = o (x1+α ) im Limes
x → ∞ gilt.
(c) Sei f : R → R und n ∈ N. Beweisen oder widerlegen Sie:
ur x → ∞.
f (x) = O (xn ) f¨
ur x → ∞ ⇒ f (x) = o xn+1 f¨
L¨osung
Zu (a):
Sei n ∈ N. Aus der Summenformel, die sich durch vollst¨andige Induktion beweisen
l¨aßt, folgt
n
n(n + 1)(2n + 1)
1
1
1
k2 =
= n3 + n2 + n.
6
3
2
6
k=1
Wie in Beispiel 2.24(a) ergibt sich 13 n3 + 12 n2 + 16 n = O (n3 ) und α = 3 ist das kleinste
α, f¨
ur das die Behauptung gilt.
Zu (b):
Da der Logarithmus langsamer bei ∞ w¨achst als jede Potenz von x, gilt f¨
ur jedes
β>0
log x
= 0.
lim
x→∞ xβ
Es folgt
n
x (log x)n
log x
=
→ 0 f¨
ur x → ∞,
x1+α
xα/n
was nach Definition 2.21 (b) zu zeigen war.
Zu (c): Die Behauptung ist zu beweisen. Sei f : R → R und n ∈ N. Nach Definition
2.21 (b) ist
f (x)
lim n+1 = 0
x→∞ x
zu zeigen. Nach Proposition 2.22 (a) existieren ein C > 0 und ein δ > 0, so dass f¨
ur
alle x > δ
f (x)
≤C
xn
gilt. Folglich gilt f¨
ur alle x > δ
f (x)
f (x)
C
1
≤
=
·
n+1
n
x
x
|x|
|x|
C
→ 0 f¨
ur x → ∞.
|x|
und
Aufgabe 4
[10 Pkt.]
Berechnen Sie f¨
ur die Matrix
A :=
1
2
1
3
1
3
1
4
eine N¨aherung der Inversen A−1 durch Gleitkommaarithmetik zur Basis 10 mit zweistelliger Genauigkeit. Wenden Sie dazu zun¨achst auf die Eintr¨age von A den Rundungsoperator rd2 aus (2.7) im Skript an (das Ergebnis werde mit rd2 (A) bezeichnet),
und benutzen Sie dann die folgende Formel
−1
a b
c d
=
1
ad − bc
d −b
−c a
zum Invertieren einer 2 × 2-Matrix, um rd2 (A) zu invertieren. Dabei soll bei jeder
arithmetischen Operation die Formel (2.9) verwendet werden. Die sich so ergebende
N¨aherung von A−1 heiße B. Berechnen Sie schließlich noch das Produkt B rd2 (A),
wobei Sie wieder bei jeder arithmetischen Operation die Formel (2.9) verwenden. Vergleichen Sie das Ergebnis C mit der exakten Einheitsmatrix, und vergleichen Sie B
mit der exakten Matrix A−1 , indem Sie jeweils f¨
ur die vier Eintr¨age den absoluten
und (wo m¨oglich) den relativen Fehler angeben.
L¨osung
Anwendung von rd2 auf die Eintr¨age von A ergibt
rd2 (A) =
0.50 · 100 0.33 · 100
.
0.33 · 100 0.25 · 100
(7)
Mit Hilfe der in der Aufgabenstellung angegebenen Formel ergibt sich zun¨achst f¨
ur
die exakte Inverse von A:
−1
A
=
1
8
1
−
1
9
1
4
− 31
− 13
1
2
=
18 −24
−24
36.
(8)
Weiterhin ist
B = (0.1 · 101 )/2 (0.50 ·2 0.25 −2 0.33 ·2 0.33) ·2
0.25 −0.33
−0.33
0.50
.
(9)
Berechnung ergibt
0.50 ·2 0.25 −2 0.33 ·2 0.33 = rd2 (0.125) −2 rd2 (0.1089) = 0.13 −2 0.11
= 0.20 · 10−1 ,
(10)
(0.1 · 101 )/2 (0.20 · 10−1 ) = 0.50 · 102 ,
B = 0.50 · 102 ·2
=
0.25 −0.33
−0.33
0.50
0.13 · 102 −0.17 · 102
−0.17 · 102
=
0.25 · 102
(11)
rd2 (0.125 · 102 ) rd2 (−0.16 · 102 )
rd2 (−0.16 · 102 )
rd2 (0.25 · 102 )
.
(12)
Damit ergibt sich f¨
ur den absoluten und den relativen Fehler:
ea (A−1 ) =
18 − 13 24 − 17
24 − 17 36 − 25
=
5 7
,
7 11
(13)
er (A−1 ) =
5/18 7/24
7/24 11/36
0.28 0.29
.
0.29 0.31
(14)
≈
Schließlich ist noch
B ·2 rd2 (A) =
=
=
=
0.13 · 102 −0.17 · 102
−0.17 · 102
0.25 · 102
0.13 · 102 ·2 0.50 −2 0.17 · 102 ·2 0.33
·2
0.50 · 100 0.33 · 100
0.33 · 100 0.25 · 100
0.13 · 102 ·2 0.33 −2 0.17 · 102 ·2 0.25
−0.17 · 102 ·2 0.50 +2 0.25 · 102 ·2 0.33 −0.17 · 102 ·2 0.33 +2 0.25 · 102 ·2 0.25
0.65 · 101 −2 0.56 · 101
0.43 · 101 −2 0.43 · 101
−0.85 · 101 +2 0.83 · 101 −0.56 · 101 +2 0.63 · 101
0.9
0.0
−0.2 0.7
.
(15)
Damit ergibt sich f¨
ur den absoluten und den relativen Fehler:
erma (id) =
0.1 0
,
0.2 0.3
(16)
ermr (id) =
0.1 −
.
− 0.3
(17)
Document
Kategorie
Technik
Seitenansichten
17
Dateigröße
134 KB
Tags
1/--Seiten
melden