Kurs:Numerik I/Besonderheiten des numerischen Rechnens

Aus Wikiversity

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.