Kurs:Numerik I/Besonderheiten des numerischen Rechnens

Einleitung Bearbeiten

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.

b-adisches Zahlsystem Bearbeiten

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 Darstellung Bearbeiten

Die Zahlen oder besitzen z.B. als irrationale Zahlen eine unendliche nicht-periodische Dezimalbruchentwicklung.

Beispiel - Rechenoperationen mit endlichen b-adischen Zahlendarstellungen Bearbeiten

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.

Fehlerrechnung Bearbeiten

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 Spezialfall Bearbeiten

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

Stellenwert - Ziffernwert - Bündelungseinheit Bearbeiten

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 Stellenwertsystemen Bearbeiten

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:

Wichtige b-adische Stellenwertsystemen Bearbeiten

Praktisch wichtig sind dabei die Basen

  • ,
  • ,

Historische Anmerkung Bearbeiten

  • 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.

Beispiele Bearbeiten

Die folgenden Bespiele zeigen:

  • 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 Dezimalsystem Bearbeiten

Mit , dem sog. dyadischen Bruch entspricht im Dezimalsystem die Zahl

Beispiel 2 - Umrechung in das Dezimalsystem Bearbeiten

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

Bemerkung - Umrechnungsverfahren Bearbeiten

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 Stellenwertsystem Bearbeiten

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 Zahlen Bearbeiten

  • 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 Nachkommastellen Bearbeiten

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 Ergebnis Bearbeiten

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 Stellenwertsystem Bearbeiten

: (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 .

Notation - b-adischer Zahlen Bearbeiten

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 Stellenwertsystem Bearbeiten

: Man erhält

Es ergibt sich zur Basis die Zahl .

Existenzsatz b-adische Zahldarstellung Bearbeiten

Sei und . Dann lässt sich jede reelle Zahl in einen -adischen Stellenwertsystem zur Basis darstellen.

Beweisidee Bearbeiten

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.

Aufgaben Bearbeiten

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

Tabellenkalkulation Bearbeiten

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.

Hilfen zur Umsetzung:

Umrechnungsaufgaben Bearbeiten

  • Rechnen Sie die Zahl in das 7-adische System um.
  • 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).

Arithmetische Operationen Bearbeiten

  • 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).

Rechnen auf einem Computer Bearbeiten

Wir gehen nun von einer Zahlendarstellung von mittels der Basis mit und den Ziffern aus, d. h. von einer Darstellung

mit .

Bündelungseinheit größer 10 Bearbeiten

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 Entwicklung Bearbeiten

Durch Abschneiden dieses unendlichen Ausdrucks ergibt sich eine endliche Zahlendarstellung

Gleitkomma-Darstellung Bearbeiten

Digitale Rechenanlagen, kurz Computer oder Rechner, arbeiten meist mit einer normalisierten (endlichen) Gleitkomma-Darstellung reeller Zahlen

wobei

  • der ganzzahlige Anteil durch und
  • die Nachkommastellen, die sog. Mantisse entspricht.

Notation b-adische Darstellung Bearbeiten

Die folgende Zahldarstellung mit Ziffern und kann man als Zahlwort in einen ganzzahligen Teil und eine Nachkommateil (Mantisse) zerlegen.

Notation ganzzahliger Teil Bearbeiten

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.

Notation Mantisse Bearbeiten

In Analogie zum Dezimalsystem kann man auch im -adischen Stellen das Zahlwort für die Nachkommanstellen als Zeichenfolge zusammensetzen

In der obigen Matisse einer Zahl sieht man eine endliche -adische Zahldarstellung mit Nachkommastellen.

Notation Vorzeichen Bearbeiten

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.

Normalisierte Gleitkommadarstellung - ganzzahliger Anteil Bearbeiten

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.

Normalisierte Gleitkommadarstellung - Mantisse Bearbeiten

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.

Notation A(b,r,s) Bearbeiten

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 Zahlen Bearbeiten

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 Zahlen Bearbeiten

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,

Beispiele Normalisierte Gleitkommadarstellung Bearbeiten

Bei der normalisierten Gleitkommadarstellung wird ein Zahl dargestellt, wobei maximal Nachkommastellen besitzt.


Beispiel 1 - Dezimalsystem Bearbeiten

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 .


Beispiel 2 - Dezimalsystem Bearbeiten

Die Zahl lautet in der normalisierten Gleitkomma-Darstellung für und z. B. oder .

Exakt darstellbare Zahlen in normalisierter Darstellung Bearbeiten

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.

Kleinste exakt darstellbare Zahl = Bearbeiten

Die kleinste darstellbare positive Zahl durch

Kleinste exakt darstellbare Zahl = Bearbeiten

Die größte positive Zahl ist durch

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.

Beispiel 1.5 Bearbeiten

Sei und . Dann gilt

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. .

Beispiel 1.6 Bearbeiten

Für und folgt

Für den mit der Rundung verbundenen absoluten Fehler hat man

und für den relativen Fehler, sofern ist,

Bei einer analogen Definition der Rundungsoperation für die Basis erhält man

Diese Vorgehensweise führt auf die Definition der sogenannten relativen Maschinengenauigkeit

Mit dieser gilt also

(1.3)

wie man mit der Setzung sieht.

Beispiel 1.7 (IEEE-Standard) Bearbeiten

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 .

1.4 Differentielle Fehleranalyse Bearbeiten

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).

Beispiel 1.11 Bearbeiten

Die Lösungen   und   einer quadratischen Gleichung

(1.6)  

sind gegeben durch

(1.7)  

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.


Siehe auch Bearbeiten

Seiteninformation Bearbeiten

Diese Lernresource können Sie als Wiki2Reveal-Foliensatz darstellen.

Wiki2Reveal Bearbeiten

Dieser Wiki2Reveal Foliensatz wurde für den Lerneinheit Kurs:Numerik I' erstellt der Link für die Wiki2Reveal-Folien wurde mit dem Wiki2Reveal-Linkgenerator erstellt.