Prof. Dr. Karsten Urban Dipl.-Math. Katharina Becker-Steinberger, Dipl.-Math. oec. Sebastian Kestler Institut fu¨r Numerische Mathematik Wintersemester 2012/13 Numerik 1 Blatt 1 (Abgabe Mittwoch, 31.10.2012 vor den Theorie-U¨bungen in H2) Hinweise: a) Die Anmeldung fu¨r die Tutorien (im SLC unter der Veranstaltung “Numerik 1”) und die Matlab-U¨bungen (im SLC unter “Numerik 1 (MatLab)”) l¨auft von Freitag, 19.10.2012, 14 Uhr bis Sonntag, 21.10.2012, 18 Uhr. Bei der Anmeldung zu den Matlab-U¨bungen erfolgt auch die Einteilung in die Gruppen “A” und “B” (s.a. Semesteru¨bersicht auf der Homepage). b) Abgabe der U¨bungsbl¨atter nur zu zweit. Einzeln abgegebene Bl¨atter werden nicht bewertet. c) Zulassungskriterien: 50% der U¨bungspunkte (7 U¨bungsbl¨atter) und insgesamt 4 abgegebene Aufgaben in LATEX. Auf jedem Blatt wird mind.eine Aufgabe zur Abgabe mit LATEX angeboten. c) Aufgaben die auf Englisch gestellt sind, mu¨ssen nicht auf Englisch beantwortet werden. d) Eine kurze Einfu¨hrung in LATEX wird noch am Mittwoch, den 24.10. in den U¨bungen gegeben. WeitereHinweise,insbesonderezurInstallation vonLATEX,findensichaufderHomepage. Zudem ist LATEX auf den Linux-Rechnern des kiz installiert. Aufgabe 1 (Zahldarstellung, LATEX-Aufgabe) (6 Punkte) Fu¨r die Anwendung von Bedeutung sind bei der Zahldarstellung (vgl. Definition 2.1.9) die Basen b = 10 (Dezimalzahlen), b = 2 (Bin¨arzahlen), b = 8 (Oktalzahlen) und b = 16 (Hexadezimalzahlen). Bei Hexadezimalzahlen treten Ziffern mit Werten zwischen 0 und 15 auf. Damit alle Ziffern einstellig notiert werden k¨onnen, werden fu¨r die Ziffern mit den Werten 10 bis 15 die Buchstaben A bis F verwendet. Erg¨anzen Sie folgende Tabelle (geben Sie dabei alle Rechnungen an): Dezimal Dual Oktal Hexadezimal 27.375 10011.011111 11.11 A.BC Hinweis: Diese Aufgabe kann als LATEX-Aufgabe abgegeben werden. Die untere Gaußklammer “⌊ ⌋” k¨onnen Sie mit “\lfloor” bzw. “\rfloor” erzeugen. Aufgabe 2 (Eindeutigkeit der Zahldarstellung) (3+2 Punkte) a) Zeigen Sie, dass fu¨r n∈ N und b ∈ N≥2 die Abbildung n−1 ϕ :{0,1,...,b−1}n → {0,1,...,bn −1} mit (a0,...,an−1)7→ Xakbk k=0 bijektiv ist. b) Zeigen Sie, dass jede reelle Zahl von Null verschiedene Zahl unter der Bedingung ”a < b−1 fu¨r k unendlich viele k ≤ n” eine eindeutige b-adische Entwicklung besitzt (siehe Bemerkung 2.1.6). Aufgabe 3 (Umwandlung in und Operationen auf Gleitpunkt-Darstellungen) (2+2+2+2 Punkte) a) Gegeben seien a = 7,b = −6,c = 3 ∈ M(2,3,2). Zeigen Sie, dass gilt: a = (0.111) ·2(00)2 = 8 8 16 2 (0.111) ·20, b = −(0.110) ·2(00)2 = −(0.110) ·20 und c = (0.110) ·2−(10)2 = (0.110) ·2−2. 2 2 2 2 2 b) Zeigen Sie fu¨r Operationen ⊕, ⊖ auf M(2,3,2), dass (a⊕b)⊕c = (0.101) ·2−1 = 5 und dass 2 16 a⊕(b⊕c) = (0.110) ·2−1 = 3. Verwenden Sie dazu die Standardrundung. Bestimmen Sie den 2 8 relativen Fehler beider Ergebnisse. c) Bestimmen Sie fu¨r a = 3 und b = 4 die Darstellungen von a und b in M(2,5,3) und M(2,3,3) 5 7 (da die Zahlen nicht exakt darstellbar sind, muss hier gerundet werden). d) Berechnen Sie auf beiden Gleitpunkt-Darstellungen a⊖b. Wie groß ist der jeweilige Fehler und wie heißt das beobachtete Ph¨anomen? Aufgabe 4 (Umwandlung in b-adische Gleitpunkt-Darstellung) (4+3 Punkte) Zu gegebener Basis b ∈ N , sei x ∈ [b−bn,bbn−1) in der (eindeutigen) Darstellung ≥2 ∞ n−1 x= bt·ℓ(v)·Xdjb−j, ℓ(v) := Xvjbj j=1 j=0 gegeben, wobei wir annehmen, dass d < b − 1 fu¨r unendlich viele j. Wir interessieren uns fu¨r die j Bestimmung von t ∈ {−1,1}, des n-stelligen Exponenten v = (v ,...,v ) ∈ {1,...,b− 1}n und 0 n−1 der m-stelligen Mantisse d = (d ,...,d ) ∈ {1,...,b−1}m (ohne Runden) mit d 6= 0, d.h. fu¨r die 1 m 1 Darstellung von fl(x)∈ M(b,m,n) (s.a. Definition 2.1.13). a) Zeigen Sie, dass mittels des Pseudo-Codes in Algorithmus 1 tats¨achlich fu¨r gegebenes x ∈ [b−bn,bbn−1) die Koeffizienten d= (d ,...,d ) berechnet werden. 1 m b) Algorithmus 1 berechnet ebenfalls den Wert fu¨r ℓ. Schreiben Sie einen Algorithmus in Pseudo- Code (Englisch ist hier keine Pfllicht) der die entsprechenden Koeffizienten v = (v ,...,v ) 0 n−1 berechnet und zeigen Sie, dass ihr Algorithmus das richtige Ergebnis liefert. Algorithm 1 Computation of d= (d ,...,d ) 1 m 1: if 0 < bx < 1 then 2: Find the smallest k ∈ N such that y := bk+1x ≥ 1. 1 3: Set ℓ = ℓ(v) = k and t = −1. 4: for j = 1,...,m do 5: Compute the smallest d ∈ {0,...,b−1} such that y −d < 1. j j j 6: Set y = b(y −d ). j+1 j j 7: end for 8: else if bx ≥ 1 then 9: Find the smallest k ∈ N such that x < bk 0 10: Set ℓ = ℓ(v) = k and t = 1. 11: Set y := bx. 1 12: for j = 1,...,m do 13: Compute the smallest d ∈ {0,...,b−1} such that y −d bk < bk. j j j 14: Set y = b(y −d bk). j+1 j j 15: end for 16: end if