Diese Seite kann als Wiki2Reveal Folien angezeigt werden.
Einzelne Abschnitte werden als Folien betrachtet und Änderungen an den Folien wirken sich sofort auf den Inhalt der Folien aus.
Alle Berechnungen auf digitalen Rechenanlagen können grundsätzlich nur mit endlicher Genauigkeit durchgeführt werden. Deshalb spielt die verwendete Zahlendarstellung eine wichtige Rolle.
Beispiel - Irrationale Zahlen und deren b-adische DarstellungBearbeiten
Die Zahlen oder besitzen z.B. als irrationale Zahlen eine unendliche nicht-periodische Dezimalbruchentwicklung.
Beispiel - Rechenoperationen mit endlichen b-adischen ZahlendarstellungenBearbeiten
Wenn die arithmetischen Operationen nicht symbolisch (wie in einem Computeralgebrasystem CAS), sondern numerisch durchgeführt werden, dann liefert z.B. die Verkettung von Wurzelziehen mit Quadrieren einen numerischen Fehler , während die umgekehrte Verkettung keine Zwischenergebnisse mit unendlicher Dezimalbruchentwicklung besitzt und damit das korrekte Ergebnis liefert.
Der Umgang mit Fehler und die Abschätzung von Fehlern in einem Algorithmus ist ein wesentlicher Aspekt in der Numerik, da man für die Nutzung von näherungsweisen Berechnungen in der Praxis z.B. abschätzen muss, ob gewisse Toleranzen bei möglichen Abweichung mit berechneten Fehlerschranken noch innerhalb der Toleranzgrenzen für das Problem liegen, für das das numerische Verfahren verwendet wird.
Dezimales Stellenwertsystem als SpezialfallBearbeiten
Bekanntlich ist die Zahl im Dezimalsystem gleichbedeutend mit
Man spricht in diesem Fall auch von einem -adischen Bruch zur Basis . Statt der bekannten Basis in unserem Dezimalsystem kann man auch eine andere Basis mit wählen. Wäre , so hätte beispielsweise die Zahl mit der Ziffernfolge im 8er-System den Wert
Der Stellenwert setzt sich also multiplikativ aus dem Ziffernwert und dem Wert der Bündelungseinheit .
Stellenwert Ziffernwert Bündelungseinheit
Die Bündelungseinheiten sind Potenzen einer Basis und die Ziffernwerte sind nicht-negative natürliche Zahlen, die 0 sein können und kleiner als die Basis der der Bündelungseinheit. Diese obere Grenze für die Ziffern ergibt sich aus dem Bündelungssystem, bei 10 Bündelungseinheiten mit einer Potenz zu einer Bündelungseinheit der Potenz zusammengefasst wird.
Verallgemeinerung zu b-adischen StellenwertsystemenBearbeiten
Die Ziffern an der i-ten Stelle im Zahlwort erhält den Stellenwert werden nun bezüglich der Basis und deren Potenz an der i-ten Stelle ermittelt. So entspricht eines Zahlwortes der Zahl aus dem Dezimalsystem der reellen Zahl:
Die Babylonier beispielsweise verwendeten die Basis (Sexagesimalsystem).
Die Römer verwendeten kein reines Bündelungs bzgl. einer Basis , sondern eine alternierende Zwei-Fünfer-Bündelung angelehnt ist, bei der fünf Einer "I" zu einem Fünfer "V", 2 Fünfer "V" zu einem Zehner "X", 5 Zehner "X" zu einem Fünfziger "L", 2 Fünfziger "L" zu einem Hunderter "C", ...
Die Notationsform der Römer besitzt ferner subtrahierende Notationen wie z.B. "IX"=4 und einen Zeichenverwendung für Bündelungseinheiten negative Eigenschaften, die diese Zahlennotation für arithmetische Operationen und damit auch für die Numerik ungeeignet machen.
Umrechungen von dem b-adischen Stellenwertsystem in das dezimale Stellenwertsystem
Umrechungen von dem das dezimale Stellenwertsystem in b-adischen Stellenwertsystem
Addition in b-adischen Stellenwertsystemen
Multiplikation in b-adischen Stellenwertensystem
Beispiel 1 - Umrechung in das DezimalsystemBearbeiten
Mit , dem sog. dyadischen Bruch entspricht im Dezimalsystem die Zahl
Beispiel 2 - Umrechung in das DezimalsystemBearbeiten
Im 16-er-System fehlen uns im Vergleich zu dem Dezimalsystem 6 zusätzliche Ziffern für die Zahlen A=10, B=11, C=12, D=13, E=14, F=15. Der -adische Bruch zur Basis bedeutet im Dezimalsystem die Zahl
Will man umgekehrt eine Dezimalzahl bezüglich einer anderen Basis dargestellt werden soll, so verwendet man eine fortgesetzte Division mit Rest (siehe Euklidischer Algorithmus), die dann aber nicht notwendigerweise terminiert, sondern auch Vielfache von Bündelungseinheiten mit negativen Potenzen betrachtet werden (also z.B. ) weiter forgesetzt wird, um damit auch die Ziffernwerte der Nachkommastellen zu ermitteln.
Beispiel 3 - Umrechnung in ein b-adische StellenwertsystemBearbeiten
Gegeben sei die Zahl im Dezimalsystem. Diese sei nun mittels einer anderen Basis dargestellt (hier ).
: (Als Vielfache der Potenzen von 2 stehen nur die Ziffern 0 und 1 zur Verfügung, und für die erste Stelle nur die 1.)
Man ermittelt zuerst die höchste Potenz von 2, mit der Eigenschaft . Wegen und findet man die Potenz .
Damit erhält man die erste Ziffer im Dualsystem mit
Die Division mit Rest wird nun mit auf den Rest fortgesetzt.
Beispiel 3 - b-adische Umrechnungschritte ganze ZahlenBearbeiten
In dem Rest steckt das 1-fache von ,
in dem verbleibenden Rest steckt nun einmal die Bündelungseinheit ,
der nächste Rest enthält wieder das einmal die Bündelungseinheit ,
die Zahl das 0-fache von sowie das 0-fache von ,
Der ganzzahlige Anteil von lässt sich damit durch die Dualzahl darstellen.
Beispiel 3 - b-adische Umrechnungschritte NachkommastellenBearbeiten
Es fehlt also noch die Darstellung der Nachkommanstellen im Dualsystem. Daher werden nun Bündelungseinheit mit negativem Exponenten betrachtet.
die Zahl das 0-fache von
sowie das 0-fache von und schließlich
das 1-fache von
Beispiel 3 - b-adische Umrechnung ErgebnisBearbeiten
Damit ergibt sich aus der -adischen Darstellung und der Berechnung der Nachkommastellen im Dualsystem die gesamte -adische Darstellung von durch:
Beispiel 4 - Umrechnung in ein b-adische StellenwertsystemBearbeiten
: (Als Vielfache der Potenzen von 8 stehen jetzt die Ziffern zur Verfügung bzw. für die erste Stelle die Ziffern .) Es ergibt sich mit einer analogen Rechnung die 8-adische Zahldarstellung von über:
Also entspricht im Dezimalsystem der Zahl zur Basis .
Um Zahlen in einem b-adischen Stellenwertsystem von der Darstellung im Dezimalsystem zu unterscheiden, wird die Basis als Index an die Zifferndarstellung in dem jeweiligen System hinzugefügt.
Beispiel 5 - Umrechnung in ein b-adische StellenwertsystemBearbeiten
Die Beweisidee nutzt das oben beschriebene Kontruktionsverfahren für die Ziffern in induktiver Form. Dabei ist zu bemerken, dass endliche Dezimalbruchentwicklung periodische unendliche Nachkommastellen in der Matisse der -adischen Zahldarstellung besitzen kann und umgekehrt.
Die folgenden Aufgaben gliedern sich in zwei Bereiche:
Umrechnung von einem b-adischen Stellenwertsystem in ein anderes b-adisches Stellenwertsystem,
arithmetische Operationen in Stellenwertsystemen und die Betrachtung von Rechenregeln im Dezimalsystem und deren Analogie in Analogie b-adischen Stellenwertsystem
Erstellen Sie in Tabellenkalkulation mit LibreOffice-Calc und dem Befehl =REST(...;...) (z.B. =REST(566;7) liefert den Rest bei Division durch 7 von 566 zurück). Versuchen Sie bei der Umrechnung die mathematischen Operationen stellenweise berücksichtigen. Beim Wechsel des Stellenwertsystems und das Basis der Bündelungseinheit soll dabei die Zahl im -adischen Zahlensystem automatisch umgerechnet werden.
Rechnen Sie die Zahl aus dem 7-adischen Stellenwertsystem in das Dezimalsystem um.
Stellen Sie die Bruch einmal im Dezimalenstellenwertsystem und einmal im 7-adischen Stellenwertsystem dar. Was fällt Ihnen bei der Umwandlung des Bruches auf und welche Begründung können Sie dafür angeben (bzgl. periodischer -adischer Zahldarstellung).
Addieren Sie die Zahlen im 7-adischen Stellenwertsystem ohne Umrechnung in das Dezimalsystem. Übertragen Sie dabei die Rechenregeln im Dezimalsystem auf das 7-adischen Stellenwertsystem,
Multiplizieren Sie die Zahlen im 7-adischen Stellenwertsystem ohne Umrechnung in das Dezimalsystem. Übertragen Sie dabei die Rechenregeln im Dezimalsystem auf das 7-adischen Stellenwertsystem,
Multiplizieren Sie die Zahlen im 7-adischen Stellenwertsystem ohne Umrechnung in das Dezimalsystem. Welche Analogien können Sie dabei zu Rechenregeln im Dezimalsystem identifizieren,
Berechnen Sie die Division , und (Notieren Sie dazu die Vielfachen von im 4-adischen System).
Für eine Bündelungseinheit/Basis kann die Ziffer in der dezimalen Darstellung also auch eine Ziffer mit mehr als einer Stelle sein. Im Hexadezimalsystem (16er-System) verwendet man in der Regel Buchstaben für die Ziffern 10,...,15. Also
Näherungsweisedarstellung als endliche p-adische EntwicklungBearbeiten
Durch Abschneiden dieses unendlichen Ausdrucks ergibt sich eine endliche Zahlendarstellung
In Analogie zum Dezimalsystem kann man im -adischen Stellen den ganzahligen Teil des Zahlwortes an den Ziffern vor dem Dezimalpunkt ablesen. Formal liefert das:
In der obigen Matisse einer Zahl sieht man eine endliche -adische Zahldarstellung mit Nachkommastellen.
Da man mit der Ziffernfolge im Zahlwort zunächst einmal nur nicht negative Zahlen definieren kann, fehlt für die Zahldarstellung in noch das Vorzeichen, das die Zeichen "" oder "" annehmen kann. Zahldarstellung im -adischen System haben daher in Ziffernnotation eine nachstehende Zeichenfolge.
Bei einer normalisierten Gleitkommadarstellung verwendet man nur eine Matissen und eine Exponenten für die Bündelungseinheit des Stellenwertsystems, mit dem die Ziffernfolge in der Mantisse durch Multiplikation mit Potenzen von auch den ganzzahligen Anteil einer reellen Zahl darstellen kann.
Bei einer normalisierten Gleitkommadarstellung verwendet man nur eine Matissen und eine Exponenten, mit dem die Ziffernfolge in der Mantisse durch Multiplikation mit Potenzen von dann als erste Nachkommastelle eine von 0 verschiedene Ziffer besitzt und die folgende reelle Zahl darstellen kann.
Für die Notation einer normalisierten Gleitkommadarstellung benötigt man 3 Festlegungen :
als Basis/Bündelungseinheit der Zahlen im -adischen Zahlsystem,
die zur Verfügung stehende Ziffernzahl für die Mantisse der Zahl und
die Anzahl der Ziffern für den Exponenten im -adischen Zahlsystem der normalisierten Darstellung.
Exakte und näherungsweise Darstellung von ZahlenBearbeiten
Wenn man z.B. eine periodische Zahldarstellung oder eine irrationale Zahl näherungsweise durch eine endliche -adischen Zahldarstellung repräsentiert, entsteht ein Fehler. Einige Zahlen können aber ohne Fehler dargestellt werden.
bezeichnet dann die Menge der exakt darstellbaren Zahlen im -adischen Zahlsystem, das mit Nachkommastellen und sind die Stellen für den Exponenten der Bündelungseinheit. Eine Fehlerschranke kann in diesem Fall durch eine Potenz von angegeben werden.
Bemerkung zur exakten und näherungsweisen Darstellung von ZahlenBearbeiten
Ob eine Zahl eine endliche oder unendliche Darstellung im -adischen Zahlsystem hängt von der Bündelungseinheit ab.
hat im Dezimalsystem eine periodische Dezimalbruchentwicklung,
hat im 7er-System mit eine endliche -adische Zahldarstellung,
Sei : Die Zahl lautet (bei Nichtberücksichtigung der Größen und ) in normalisierter Gleitkomma-Darstellung . Letztere Darstellung schreibt man z.B. für und auch in der Form oder .
Die Zahl lautet in der normalisierten Gleitkomma-Darstellung für und z. B. oder .
Exakt darstellbare Zahlen in normalisierter DarstellungBearbeiten
Eine normalisierte Gleitkomma-Darstellung mit der Basis , beispielsweise oder , bestimmt die Menge reeller Zahlen, die auf dem Rechner mit Nachkommatellen exakt dargestellt werden können, die sog. Maschinenzahlen. gibt dabei dei Stellen für den Exponenten von . Eine solche Zahlendarstellung ermöglicht also nur die Repräsentation einer endlichen Teilmenge der reellen Zahlen.
gegeben. Die Mantisse von entspricht offenbar der Dezimalzahl und die von der Dezimalzahl
Der Exponent für beide Zahlen ist bis auf das Vorzeichen gegeben durch die Dezimalzahl
Somit haben und den Dezimalwert
Ist die reelle Zahlenmenge
so können also insbesondere Zahlen nicht auf dem Rechner wiedergegeben werden. Im Fall und melden alle Rechner normalerweise einen Exponentenüberlauf („overflow“), während sie im Fall meist keine Meldung machen und setzen.
Ferner ist offenbar nicht jede Zahl auf dem Rechner, d. h. als darstellbar (z. B. trifft dies für die Zahlen und zu). Somit stellt sich das Problem, eine Zahl durch eine Zahl aus zu approximieren. Man verwendet hierzu einen Rundungsoperator , der jeder Zahl eine Zahl zuordnet, welche sinnvollerweise der folgenden Beziehung genügt:
(1.2)
Im Fall, dass die Aufgabe in (1.2) zwei Lösungen besitzt, rundet man dabei normalerweise (wir legen dies hier auch so fest) z. B. für und eine Endziffer 5 nach oben.
Allgemein kann man für und eine Mantissenlänge die zu einer beliebigen Zahl gehörende Maschinenzahl folgendermaßen finden. Es sei dazu zunächst in der Form dargestellt, wobei und
mit und seien. Insbesondere ist also . Zu bildet man nun
und setzt dann
Offenbar ist die Zahl für jedes eine Maschinenzahl, d. h. .
Die arithmetischen Grundoperationen werden auf digitalen Rechnern durch sog. Gleitpunktoperationen ersetzt, welche Maschinenzahlen wieder auf Maschinenzahlen abbilden. Sind , ist „“ eine der vier Grundoperationen, und , so definiert man die zugehörige Gleitpunktoperation durch
Für sie gilt nach (1.3)
Für das Ergebnis kann natürlich auch gelten. In diesem Fall meldet der Rechner normalerweise einen Exponentenüberlauf oder setzt er .
Der Einfluss von Störungen in den Daten auf die Lösung eines Problems sowie die Fortpflanzung von Eingangs- und Rundungsfehlern bei numerischen Algorithmen kann durch die sogenannte differentielle Fehleranalyse untersucht werden. Zu deren Beschreibung nehmen wir an, dass ein Problem bzw. eine Berechnungsvorschrift mittels einer zweimal stetig differenzierbaren Funktion durch die Gleichung
bzw. gleichbedeutend durch die Gleichungen
(1.4)
beschrieben wird. Dabei ist also der Daten- und der Ergebnis-Vektor. Für
gilt dann nach dem Satz von Taylor zeilenweise
(1.5)
so dass für hinreichend kleine der Restterm vernachlässigt werden kann und folglich der dominierende relative Fehler gegeben ist durch
mit
Die Größen entscheiden demnach über den Einfluss der relativen Fehler in den Daten auf den relativen Fehler im Ergebnis. Sie werden deshalb häufig auch Verstärkungsfaktoren genannt. Im Fall, dass die Ausgangsgleichung einen Algorithmus beschreibt, sagt man, dass dieser stabil ist, wenn alle „klein“, idealerweise ungefähr gleich 1 sind. Anderenfalls sagt man, er ist instabil.
Im Fall, dass die Ausgangsgleichung ein mathematisches Problem beschreibt, spricht man bei den auch von Konditionszahlen (engl. to condition = bedingen, bestimmen). Sind die Konditionszahlen dem Betrag nach groß, hat man also ein schlecht konditioniertes, anderenfalls ein gut konditioniertes Problem. Für manche Zwecke ist aber diese Definition von Konditionszahlen unpraktisch, so dass auch andere Größen als Konditionszahlen bezeichnet werden (vgl. Definition 2.18).
wobei wir hier davon ausgehen, dass die Gleichung zwei unterschiedliche reelle Lösungen besitzt, also
ist. Zur Analyse der Fehlerempfindlichkeit der beiden Lösungen von (1.6) in Abhängigkeit von den Eingabedaten und betrachten wir diese nun als Funktionen von und . Wir untersuchen dazu die beiden Gleichungen
(1.8)
(Im Vergleich mit (1.4) ist und entsprechen die rechten Seiten in (1.8) den .) Man hat dafür
(1.9)
Damit errechnet man
Hieraus ergeben sich die Verstärkungsfaktoren
Die Bestimmung der Lösungen von (1.6) ist somit für ein schlecht konditioniertes Problem. Zur Veranschaulichung geben wir ein Zahlenbeispiel. Es seien und . Dann sind und die beiden Nullstellen von (1.6). Für die Verstärkungsfaktoren ergibt sich in diesem Fall
Somit ist zu erwarten, dass Eingabefehler in den Daten und in Bezug auf die Lösungen und von (1.6) um den 100- bis 200-fachen Wert verstärkt werden.
Wir wollen nun zwei unterschiedliche Algorithmen zur Berechnung von
betrachten und zwar unter den Bedingungen
(1.10)
In diesem Fall ist offenbar
d. h. für nicht zu kleine auch und somit das Problem der Bestimmung der Lösungen der quadratischen Gleichung (1.6) gut konditioniert. Ein „Lösungsalgorithmus“ könnte nun zunächst darin bestehen, hintereinander die folgenden Größen zu berechnen
Wegen sollte man als nächstes den unkritischen Wert
berechnen. Zur Berechnung von betrachten wir nun zwei Varianten (vgl. (1.9)):
Da unter den Voraussetzungen (1.10) gilt, tritt bei Variante A zwangsläufig Auslöschung auf. Betrachtet man als Funktion in den Variablen und , so erhält man für die Verstärkungsfaktoren
Also ist die Variante A im Fall (1.10) nicht stabil. Bei Variante B erhält man dagegen
D. h., der Algorithmus B ist stabil. Für und ergibt sich bei exakter (bzw. 4-stelliger) Rechnung
Die exakte Lösung für ist . Bei Rechnung mit 4-stelliger Mantisse erhält man im Fall der Variante B , während man für die Variante A erhält mit einem relativen Fehler bezüglich der exakten Lösung von
Im Fall
gilt offenbar . Somit ist die Berechnung von stabil möglich und von kritisch. Ein stabiler Algorithmus ergibt sich hier durch die Vertauschung der Rollen von und oben.
Wir nennen einen Algorithmus zur Lösung eines bestimmten Problems numerisch stabiler als einen zweiten zur Lösung desselben Problems, wenn der Gesamteinfluss aller Rundungsfehler auf die Lösung bei dem ersten Algorithmus kleiner als bei dem zweiten ist.