numerik:maschinenzahlen
no way to compare when less than two revisions
Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen angezeigt.
— | numerik:maschinenzahlen [2014-12-29 13:27] (aktuell) – angelegt - Externe Bearbeitung 127.0.0.1 | ||
---|---|---|---|
Zeile 1: | Zeile 1: | ||
+ | ====== Maschinenzahlen ====== | ||
+ | > The aim of computing is insight, not numbers. | ||
+ | >> --- R.W. Hamming | ||
+ | |||
+ | Aus der Schulmathematik sind natürliche, | ||
+ | $\mathbb{N} \subset \mathbb{Z} \subset \mathbb{Q} \subset \mathbb{R} \subset \mathbb{C}$. | ||
+ | Der Übergang zu immer umfassenderen Zahlbereichen wurzelt in dem Wunsch, im kleineren Zahlbereich unlösbare Aufgaben lösen zu können: | ||
+ | |||
+ | | $x+5 = 2$ | unlösbar in $\mathbb{N} | ||
+ | | $x*5 = 2$ | unlösbar in $\mathbb{Z} | ||
+ | | $x^2 = 2$ | unlösbar in $\mathbb{Q} | ||
+ | | $x^2 = -1$ | unlösbar in $\mathbb{R} \leadsto \mathbb{C}$ | ||
+ | |||
+ | Umso erstaunlicher ist für den Neuling, dass Computer nur mit einem Teilbereich der ganzen bzw. gebrochenen Zahlen umgehen können. Und auch das nur eingeschränkt. | ||
+ | Warum? Nun, Speicher ist endlich. | ||
+ | ===== Ganzzahlen ===== | ||
+ | > Gott schuf die ganzen Zahlen, der Rest ist Menschenwerk. | ||
+ | >> --- Leopold Kronecker | ||
+ | |||
+ | Die Menge natürlicher Zahlen $\mathbb{N}$ ist unbegrenzt, es gibt unendlich viele. | ||
+ | Computerspeicher ist aber endlich, daher stehen zur Zahldarstellung nur begrenzt viele Stellen ($b$ Bits) zur Verfügung. | ||
+ | Da Berechnungen mehr als eine Zahl erfordern und für viele Berechnungen Zahlen mit kleinen Beträgen genügen, | ||
+ | ist der Wertebereich von Ganzzahlen im Computer eingeschränkt: | ||
+ | |||
+ | <file cpp kronecker.cpp> | ||
+ | #include < | ||
+ | |||
+ | int main() | ||
+ | { | ||
+ | unsigned int n = 0; // Peano-Axiom 1: 0 ist eine natürliche Zahl. | ||
+ | do { ++n; } while (n > 0); // Peano-Axiom 2: Jede natürliche Zahl hat einen Nachfolger. | ||
+ | |||
+ | auto min = n; | ||
+ | auto max = n-1; | ||
+ | std::cout << min << " | ||
+ | } | ||
+ | </ | ||
+ | Je nach Maschine dauert es eine kleine Weile, diese " | ||
+ | Abhängig von Prozessor, Betriebssystem, | ||
+ | Rechenoperationen können nicht aus Menge maschinell darstellbarer Ganzzahlen $\mathbb{G} \subseteq \mathbb{Z}$ herausführen. | ||
+ | So kommt es zu befremdlichen Ergebnissen. | ||
+ | Die Summe positiver ganzer Zahlen, z.B. '' | ||
+ | Dieser // | ||
+ | Willkommen in der Welt der [[wp> | ||
+ | Wird das höchstwertige Bit als Vorzeichen interpretiert (Datentyp '' | ||
+ | | ||
+ | |||
+ | |||
+ | |||
+ | ===== Gleitkommazahlen ===== | ||
+ | > Nobody wants to be a zero... Almost everybody wants to be a number one... | ||
+ | > But the problem with these two number is, that they' | ||
+ | > ---- Laurie Anderson | ||
+ | |||
+ | Durch Abspalten von Zehnerpotenzen lässt sich die gleiche Zahl auf verschiedene Weisen | ||
+ | \begin{align*} | ||
+ | & 299792,458 \\ | ||
+ | & 299, | ||
+ | & 2, | ||
+ | \end{align*} | ||
+ | darstellen, bei denen das Komma (Gleitkomma, | ||
+ | Bei sehr großen und sehr kleinen Zahlen ist das vorteilhaft: | ||
+ | $3, | ||
+ | Neben der Größenordnung ist die Anzahl der Bedeutung tragenden (signifikanten, | ||
+ | Wie viele Stellen sinnvoll oder " | ||
+ | |||
+ | Im englischen Sprachraum wird die Schreibweise 3.00E5 " | ||
+ | Dabei steht '' | ||
+ | |||
+ | ==== Eine Definition ==== | ||
+ | Eine Gleitkommazahl $x$ zur Basis $B$ | ||
+ | mit dem Wert $x = \pm \sum_{i=0}^n z_i B^{E-i}$ | ||
+ | hat die Darstellung $\pm (z_0, z_1 z_2 \ldots z_n)_B \cdot B^E$ | ||
+ | mit $n+1$ zählenden Stellen $z_i \in \{0, \ldots, B-1 \}$. | ||
+ | $(z_0, z_1 z_2 \ldots z_n)_B$ wird Mantisse (oder Signifikand) genannt. | ||
+ | Falls $z_0 \neq 0$, heißt $x$ normalisiert. | ||
+ | |||
+ | |||
+ | ==== Endliche Mantissen und Exponenten ==== | ||
+ | Für das Vorzeichen $s$ muss ein Bit zur Verfügung stehen: $\pm 1 = (-1)^s$. | ||
+ | |||
+ | Bei begrenzter Anzahl von Nachkommastellen $n$ erlaubt diese Darstellung nur endliche Brüche zur Basis $B$. | ||
+ | Irrationale Zahlen und periodische Brüche wie $\pi = 3, | ||
+ | Ein gemeiner Bruch hat nur dann endlich viele Stellen, wenn sein Nenner durch Erweitern oder Kürzen in eine Potenz der Basis $B$ überführt werden kann. | ||
+ | Manchmal läuft ein Basiswechsel unserer gewohnten Vorstellung zuwider: | ||
+ | $\frac{1}{10} = 0,1_{10} = 0, | ||
+ | ([[http:// | ||
+ | Dennoch ist dieser Basiswechsel nötig, wenn Computer Zahlen zur Basis 2 speichern --- und die gebräuchlichsten tun dies. | ||
+ | |||
+ | Für normalisierte binäre Zahlen ($B=2$) gilt $z_0 = 1$. | ||
+ | Als Mantisse $1,m = (1,z_1 z_2 \ldots z_n)_2$ dient dann die Bitfolge der Nachkommaziffern. | ||
+ | Die führende Eins muss nicht extra gespeichert werden. | ||
+ | |||
+ | Der Wertebereich des Exponenten $E$ muss für die Speicherung ebenfalls eingeschränkt werden: $E_{min} \leq E \leq E_{max}$. | ||
+ | (Hardware-)Implementierer haben es einfacher, wenn negative Zahlen im Exponenten vermieden werden können. Daher | ||
+ | arbeiten sie mit einem verschobenen Exponenten (biased exponent) $e = E+v$ und einem festgelegten Versatz (engl. bias) $v = E_{max}$ | ||
+ | statt $E = e -v$.((Deutschsprachige Lehrbücher bezeichen den verschobenen Exponenten zuweilen als Charakteristik.)) | ||
+ | |||
+ | Bitmuster mit dem niedrigsten $e = 0$ stellen den Zahlbereichs-Unterlauf (Null und subnormale Zahlen mit $z_0 = 0$) dar. | ||
+ | Das erlaubt einen sanfteren Übergang zur Null. | ||
+ | Bitmuster mit dem höchstmöglichen $e = 2v+1$ kodieren den Überlauf ($\pm \infty$) und nicht als Zahl deutbare Bitmuster (NaN = not a number), | ||
+ | die der Fehlerdiagnose dienen. So können Situationen wie 0/0, $\infty-\infty$, | ||
+ | |||
+ | Zahlenbasis, | ||
+ | |||
+ | ==== IEEE 754-2008 ==== | ||
+ | Der Standard [[wpde> | ||
+ | |||
+ | * einfach genaue Gleitkommazahl (binary32, [[wp> | ||
+ | * doppelt genaue Gleitkommazahl (binary64, | ||
+ | * sowie weitere Formate: binary16, binary128, decimal32, decimal64, decimal128 u.a. | ||
+ | |||
+ | ^ Bitmuster ^ '' | ||
+ | | NaN | '' | ||
+ | | Überlauf | '' | ||
+ | | $\nearrow$ max. | '' | ||
+ | | normalisiert | '' | ||
+ | | $\searrow$ min. | '' | ||
+ | | $\nearrow$ max. | '' | ||
+ | | subnormal | '' | ||
+ | | $\searrow$ min. | '' | ||
+ | | +Null | '' | ||
+ | |||
+ | Mit höchstwertigem Bit 1 werden entsprechend negative Zahlen dargestellt. Als Kuriosität existieren zwei Bitmuster +0 und -0 für die Null, die aber als wertgleich behandelt werden. NaNs werden als ungeordnet betrachtet. | ||
+ | |||
+ | ===== Rundung ===== | ||
+ | Nicht als Maschinenzahl darstellbare reelle Zahlen $x$ müssen gerundet werden. Die Art der Rundung ist [[: | ||
+ | (zur nächstliegenden Maschinenzahl, | ||
+ | |||
+ | Wird diese Rundung $\text{rd}(x)$ zur nächstliegenden Maschinenzahl hin ausgeführt, | ||
+ | beträgt die maximale absolute Abweichung $|x- \text{rd}(x)| = \frac{1}{2} \text{ulp}(x)$ die Hälfte des Abstandes zweier Maschinenzahlen in der Umgebung von $x$. | ||
+ | Die Auflösung, d.h. der Unterschied zwischen $z_n = 0$ und $z_n = 1$ (engl. [[ulp|unit of least precision]]) $\text{ulp}(x) = B^{E-n}$ hängt von der Größenordnung der Zahl ab. | ||
+ | Die Gleitkommazahlen sind nicht gleichmäßig über den gesamten darstellbaren Bereich verteilt. Betragsmäßige größere Zahlen haben einen größeren Abstand voneinander. | ||
+ | Die relative Auflösung einer normalisierten Zahl zur Basis 2 bleibt dadurch im Bereich | ||
+ | $2^{-(n+1)} < \frac{\text{ulp(x)}}{x} = \frac{2^{E-n}}{1, | ||
+ | Bei einfacher " | ||
+ | bei doppelter " | ||
+ | |||
+ | Das Wort " | ||
+ | Auflösung und Genauigkeit sollten nicht verwechselt werden. | ||
+ | Die Auflösung begrenzt die maximal erreichbare Genauigkeit einer Maschinenzahl. | ||
+ | Die Genauigkeit einer nur näherungsweise angegebenen Zahl $\tilde{x}$ kann jedoch viel geringer sein, | ||
+ | wenn wir uns z.B. mit der Näherung 3,14 für die Kreiszahl begnügen. | ||
+ | Ebenso führen Rechenoperationen aus dem Bereich der Maschinenzahlen heraus. | ||
+ | Die Ergebnisse sind wieder zu einer Maschinenzahl zu runden, so dass sich Rundungsfehler akkumulieren können. | ||
+ | Die Auflösung täuscht dann eine nicht vorhandene Genauigkeit vor. | ||
+ | |||
+ | Als Folge der zwischen den einzelnen Operationen ausgeführten Rundungen gehorcht die Maschinenarithmetik nicht dem Assoziativgesetz, | ||
+ | wie ein Beispiel mit nur zwei signifikanten Dezimalen verdeutlicht: | ||
+ | \begin{align*} | ||
+ | (0,17 + 0,17) + 3,0 &= 0,34 + 3,0 \approx 3,3 \\ | ||
+ | 0,17 + (0,17 + 3,0) & | ||
+ | \end{align*} | ||
+ | |||
+ | |||
+ | ==== Fehlerfortpflanzung ==== | ||
+ | Seien $\varepsilon_x = (x-\tilde{x})/ | ||
+ | die relativen Fehler der Maschinenzahlen $\tilde{x} = (1-\varepsilon_x)x$ und $\tilde{x} = (1-\varepsilon_y)y$ zu den " | ||
+ | Ist der Rundungsfehler klein gegenüber den relativen Fehlern der Ausgangswerte, | ||
+ | Dann ergeben sich die Formeln aus [Gerhard Opfer: Numerische Mathematik für Anfänger. Vieweg, Braunschweig (2002), S. 7f])) | ||
+ | |||
+ | Addition (Subtraktion als Addition von Zahlen mit unterschiedlichen Vorzeichen): | ||
+ | \begin{align*} | ||
+ | | ||
+ | | ||
+ | = \varepsilon_x \frac{x}{x+y} + \varepsilon_y \frac{y}{x+y} \mp \frac{1}{2} B^{-n} | ||
+ | \end{align*} | ||
+ | |||
+ | Multiplikation: | ||
+ | \begin{align*} | ||
+ | | ||
+ | | ||
+ | | ||
+ | \end{align*} | ||
+ | |||
+ | Division: | ||
+ | \begin{align*} | ||
+ | | ||
+ | | ||
+ | | ||
+ | \end{align*} | ||
+ | |||
+ | Bei kleinen relativen Fehlern sind die Vereinfachungen bei Multiplikation und Division gerechtfertigt. | ||
+ | Beide Operationen sind gutartig in dem Sinne, dass kleine Fehler der Eingabewerte nicht zu großen Fehlern im Ergebnis führen. | ||
+ | Addition von Zahlen $x + y \approx 0$ und Subtraktion von Zahlen $x - y \approx 0$ | ||
+ | führen dagegen zu großen relativen Fehlern (Auslöschungseffekt) bis hin zu völlig sinnlosen Resultaten. | ||
+ | |||
+ | Für die häufig zusammen vorkommende Multiplikation und Addition steht die Funktion [[: | ||
+ | |||
+ | \begin{align*} | ||
+ | | ||
+ | \end{align*} | ||
+ | |||
+ | ==== Kondition ==== | ||
+ | Der absolute Fehler einer (als exakt vorausgesetzten) Funktionswertberechnung | ||
+ | $f(x) - f(\tilde{x}) \approx f'(x) \cdot(x-\tilde{x})$ | ||
+ | wird vor allem durch den Anstieg $f'$ in der Nähe der Werte $x$ und $\tilde{x}$ bestimmt. | ||
+ | Für den relativen Fehler | ||
+ | \begin{align*} | ||
+ | | ||
+ | & | ||
+ | \end{align*} | ||
+ | ist die Konditionszahl $K_{f(x)} = \frac{f' | ||
+ | Sie gibt an, um welchen Faktor der relative Fehler der Eingangsgröße $x$ verstärkt wird.((Wirtschaftler nennen diese Größe | ||
+ | [[wpde> | ||
+ | Um wieviel Prozent ändert sich die Ausgangsgröße bei einer Änderung der Eingangsgröße um ein Prozent?)) | ||
+ | Eine Funktion wie $\sqrt{x}$ verhält sich überall gutartig: $K_{\sqrt{x}} = \frac{x}{\sqrt{x} \cdot 2 \sqrt{x}} = 1/2$. | ||
+ | Sie halbiert den Fehler. | ||
+ | Dagegen führt die Berechnung von $f(x) = (x-1)^3$ in der Nähe der Nullstelle $x = 1 + \varepsilon$ wegen | ||
+ | $K_{f(x)} = \frac{3(x-1)^2\cdot(1+\varepsilon)}{(x-1)^3} \approx 3/ | ||
+ | bei $\varepsilon = 10^{-5}$ zu einem 300000fachen Fehler, | ||
+ | d.h. mehr als 5 Dezimalstellen gehen verloren. | ||
+ | Aufgaben mit sehr großen Konditionszahlen heißen //schlecht gestellt//. | ||
+ | |||
+ | ===== Auswege ====== | ||
+ | Für ganzzahlige Berechnungen mit großer Stellenanzahl, | ||
+ | |||
+ | Die Nachverfolgung der Rundungsfehler bei Gleitkommaberechnungen per Hand gestaltet sich schnell unübersichtlich. | ||
+ | Aufgabe der numerischen Mathematik ist, trotz dieser Unzulänglichkeiten stabile Rechenvorschriften zu finden, die den unvermeidbaren Fehler nicht unnötig vergrößern. | ||
+ | |||
+ | Obwohl schon seit längerem Vorschläge existieren, die Ergebnisverifikation von Gleitkommaberechnungen zu automatisieren | ||
+ | (Einschluss des korrekten Ergebnisses durch [[wpde> | ||
+ | [[http:// | ||
+ | ist die Mehrzahl der Computernutzer mehr an [[http:// | ||
+ | |||
numerik/maschinenzahlen.txt · Zuletzt geändert: 2014-12-29 13:27 von 127.0.0.1