Kurs:Numerik I/Besonderheiten des numerischen Rechnens

Einleitung

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

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

Die Zahlen $\pi$ oder $\sqrt{2}$ besitzen z.B. als irrationale Zahlen eine unendliche nicht-periodische Dezimalbruchentwicklung.

Beispiel - Rechenoperationen mit endlichen b-adischen Zahlendarstellungen

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 $(\sqrt{2}{)}^2=2$, während die umgekehrte Verkettung $\sqrt{2^2}=2$ keine Zwischenergebnisse mit unendlicher Dezimalbruchentwicklung besitzt und damit das korrekte Ergebnis liefert.

Fehlerrechnung

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

Bekanntlich ist die Zahl $x:=311.57\dots$ im Dezimalsystem gleichbedeutend mit

$3\cdot 10^2+1\cdot 10^1+1\cdot 10^0+5\cdot 10^{-1}+7\cdot 10^{-2}+\dots$

Man spricht in diesem Fall auch von einem $b$-adischen Bruch zur Basis $b=10$. Statt der bekannten Basis $b:=10$ in unserem Dezimalsystem kann man auch eine andere Basis $b\in \mathbb{N}$ mit $b\ge 2$ wählen. Wäre $b:=8$, so hätte beispielsweise die Zahl mit der Ziffernfolge $311.57\dots$ im 8er-System den Wert

$3\cdot 8^2+1\cdot 8^1+1\cdot 8^0+5\cdot 8^{-1}+7\cdot 8^{-2}$

Stellenwert - Ziffernwert - Bündelungseinheit

Der Stellenwert $3\cdot 10^2$ setzt sich also multiplikativ aus dem Ziffernwert $3$ und dem Wert der Bündelungseinheit $10^2=100$.

Stellenwert $=$ Ziffernwert $\cdot$ Bündelungseinheit

Die Bündelungseinheiten sind Potenzen $b^n=10^n$ einer Basis $b=10$ und die Ziffernwerte sind nicht-negative natürliche Zahlen, die 0 sein können und kleiner als die Basis der $b=10$ der Bündelungseinheit. Diese obere Grenze für die Ziffern ergibt sich aus dem Bündelungssystem, bei 10 Bündelungseinheiten mit einer Potenz $n$ zu einer Bündelungseinheit der Potenz $n+1$ zusammengefasst wird.

Verallgemeinerung zu b-adischen Stellenwertsystemen

Die Ziffern $z_i\in \{0,1,\dots ,b-1\}$ an der i-ten Stelle im Zahlwort erhält den Stellenwert werden nun bezüglich der Basis $b$ und deren Potenz an der i-ten Stelle ermittelt. So entspricht eines Zahlwortes der Zahl $x$ aus dem Dezimalsystem der reellen Zahl:

$\begin{array}{ccc}x& =& \pm (\underset{\text{ganzzahliger Anteil}}{\underbrace{z_n{b}^n+\dots +z_0{b}^0}}+\underset{\text{Nachkommanstellen}}{\underbrace{z_{-1}{b}^{-1}+z_{-2}{b}^{-2}+\dots }})\\ & =& \pm \sum _{i=-\mathrm{\infty }}^n{m}_i{b}^i\end{array}$

Wichtige b-adische Stellenwertsystemen

Praktisch wichtig sind dabei die Basen

• $b=2:\text{Dualbasis},m_i\in \{0,1\},$,
• $b=10:\text{Dezimalbasis},m_i\in \{0,1,\dots ,9\},$,
• $b=16:\text{Hexadezimalbasis},m_i\in \{0,1,\dots ,9,A,B,C,D,E,F\},$
• $b=60:\text{Sexagesimalbasis},m_i\in \{0,1,\dots ,58,59\}\text{(auch }6\times 10\text{-er Basis genannt, da die Zahlen bis zur 60 im Dezimalsystem dargestellt werden)}.$

Historische Anmerkung

• Die Babylonier beispielsweise verwendeten die Basis $b=60$ (Sexagesimalsystem).
• Die Römer verwendeten kein reines Bündelungs bzgl. einer Basis $b$, 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

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

Mit $b=2$, dem sog. dyadischen Bruch $11100.10_{(b)}$ entspricht im Dezimalsystem die Zahl

$1\cdot 2^4+1\cdot 2^3+1\cdot 2^2+0\cdot 2^1+0\cdot 2^0+1\cdot 2^{-1}=16+8+4+\frac{1}{2}=28.5$

Beispiel 2 - Umrechung in das Dezimalsystem

$b=16.$ 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 $b$-adische Bruch $C17.E_{(b)}$ zur Basis $b=16$ bedeutet im Dezimalsystem die Zahl

$12\cdot 16^2+1\cdot 16^1+7\cdot 160+14\cdot 16^{-1}=3095.875.$

Bemerkung - Umrechnungsverfahren

Will man umgekehrt eine Dezimalzahl bezüglich einer anderen Basis $b=10$ 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. $2^{-1}=\frac{1}{2}$) weiter forgesetzt wird, um damit auch die Ziffernwerte der Nachkommastellen zu ermitteln.

Beispiel 3 - Umrechnung in ein b-adische Stellenwertsystem

Gegeben sei die Zahl $x:=60.125$ im Dezimalsystem. Diese sei nun mittels einer anderen Basis dargestellt (hier $b=2$).

• $b=2$: (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 $2^n$ von 2, mit der Eigenschaft $2^n\le 60.125$. Wegen $2^5=32$ und $2^6=64$ findet man die Potenz $n=5$.
• Damit erhält man die erste Ziffer im Dualsystem mit $2^5=32=100000_{(2)}$
• Die Division mit Rest wird nun mit $2^4=16=10000_{(2)}$ auf den Rest $60.125-2^5=28.125$ fortgesetzt.

Beispiel 3 - b-adische Umrechnungschritte ganze Zahlen

• In dem Rest $60.125-2^5=28.125$ steckt das 1-fache von $2^4=16=10000_{(2)}$,
• in dem verbleibenden Rest $28.125-2^4=12.125$ steckt nun einmal die Bündelungseinheit $2^3=8=1000_{(2)}$,
• der nächste Rest $4.125$ enthält wieder das einmal die Bündelungseinheit $2^2=4=100_{(2)}$,
• die Zahl $0.125$ das 0-fache von $2^1=2=10_{(2)}$ sowie das 0-fache von $2^0=1=1_{(2)}$,

Der ganzzahlige Anteil $60$ von $60.125$ lässt sich damit durch die Dualzahl $111100_{(2)}=60$ darstellen.

Beispiel 3 - b-adische Umrechnungschritte Nachkommastellen

Es fehlt also noch die Darstellung der Nachkommanstellen $0.125$ im Dualsystem. Daher werden nun Bündelungseinheit $b^n$ mit negativem Exponenten betrachtet.

• die Zahl $0.125$ das 0-fache von $2^{-1}=0.5$
• sowie das 0-fache von $2^{-2}=0.25$ und schließlich
• das 1-fache von $2^{-3}=0.125$

Beispiel 3 - b-adische Umrechnung Ergebnis

Damit ergibt sich aus der $b$-adischen Darstellung $60=111100_{(2)}$ und der Berechnung der Nachkommastellen im Dualsystem $0.125=0.001_{(2)}$ die gesamte $b$-adische Darstellung von $60.125$ durch:

$60.125=111100_{(2)}+0.001_{(2)}=111100.001_{(2)}$

Beispiel 4 - Umrechnung in ein b-adische Stellenwertsystem

$b=8$: (Als Vielfache der Potenzen von 8 stehen jetzt die Ziffern $0,1,\dots ,7$ zur Verfügung bzw. für die erste Stelle die Ziffern $1,2,\dots ,7$.) Es ergibt sich mit einer analogen Rechnung die 8-adische Zahldarstellung von $60.125$ über:

$60.125=7\cdot 8^1+4\cdot 8^0+1\cdot 8^{-1}=74.1_{(b)}$

Also entspricht $60.125$ im Dezimalsystem der Zahl $74.1_{(b)}$ zur Basis $b=8$.

Notation - b-adischer Zahlen

Um Zahlen in einem b-adischen Stellenwertsystem von der Darstellung im Dezimalsystem zu unterscheiden, wird die Basis $b$ als Index an die Zifferndarstellung in dem jeweiligen System hinzugefügt.

Beispiel 5 - Umrechnung in ein b-adische Stellenwertsystem

$b=16$: Man erhält

$60.125=3\cdot 16^1+12\cdot 16^0+2\cdot 16^{-1}.$

Es ergibt sich zur Basis $b=16$ die Zahl $3C.2_{(b)}$.

Existenzsatz b-adische Zahldarstellung

Sei $b\in \mathbb{N}$ und $b\ge 2$. Dann lässt sich jede reelle Zahl in einen $b$-adischen Stellenwertsystem zur Basis $b$ darstellen.

Beweisidee

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 $b$-adischen Zahldarstellung besitzen kann und umgekehrt.

Aufgaben

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

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 $b$-adischen Zahlensystem automatisch umgerechnet werden.

Hilfen zur Umsetzung:

Umrechnungsaufgaben

• Rechnen Sie die Zahl $123$ in das 7-adische System um.
• Rechnen Sie die Zahl $123_{(7)}$ aus dem 7-adischen Stellenwertsystem in das Dezimalsystem um.
• Stellen Sie die Bruch $\frac{1}{7}$ 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 $b$-adischer Zahldarstellung).

Arithmetische Operationen

• Addieren Sie die Zahlen $345_{(7)}+654_{(7)}$ 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 $12_{(7)}\cdot 4_{(7)}$ 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 $0.012_{(7)}\cdot 4_{(7)}$ im 7-adischen Stellenwertsystem ohne Umrechnung in das Dezimalsystem. Welche Analogien können Sie dabei zu Rechenregeln im Dezimalsystem identifizieren,
• Berechnen Sie die Division $11_{(7)}:4_{(7)}$, $12_{(7)}:4_{(7)}$ und $345_{(7)}:4_{(7)}$ (Notieren Sie dazu die Vielfachen von $4_{(7)}$ im 4-adischen System).

Rechnen auf einem Computer

Wir gehen nun von einer Zahlendarstellung von $x\in ℝ$ mittels der Basis $b\in \mathbb{N}$ mit $b\ge 2$ und den Ziffern $z_i\in \{0,1,\dots ,b-1\}$ aus, d. h. von einer Darstellung

$x=\pm \sum _{i=-\mathrm{\infty }}^n{z}_i{b}^i$

mit $z_n\ne 0$.

Bündelungseinheit größer 10

Für eine Bündelungseinheit/Basis $b>10$ kann die Ziffer $z_i$ 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

$A=10,B=11,C=12,D=13,E=14,F=15$

Näherungsweisedarstellung als endliche p-adische Entwicklung

Durch Abschneiden dieses unendlichen Ausdrucks ergibt sich eine endliche Zahlendarstellung

$\begin{array}{ccc}x& =& \pm (z_n{b}^n+m_{n-1}{b}^{n-1}+\dots +z_0{b}^0+z_{-1}{b}^{-1}+z_{-2}{b}^{-2}+\dots )\\ & =& \pm \sum _{i=-\mathrm{\infty }}^n{z}_i\cdot b^i\end{array}$

Gleitkomma-Darstellung

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

$x:=\pm \sum _{i=-\mathrm{\infty }}^n{z}_i{b}^i,$

wobei

• der ganzzahlige Anteil durch $G(x):=\pm \sum _{i=0}^n{z}_i{b}^i$ und
• die Nachkommastellen, die sog. Mantisse $M(x):=\pm \sum _{i=-\mathrm{\infty }}^{-1}{z}_i{b}^i,$ entspricht.

Notation b-adische Darstellung

Die folgende Zahldarstellung $z_n\dots z_0.z_{-1}\dots z_{-m_{(b)}}$ mit $m+n+1$ Ziffern und $z_n=0$ kann man als Zahlwort in einen ganzzahligen Teil und eine Nachkommateil (Mantisse) zerlegen.

Notation ganzzahliger Teil

In Analogie zum Dezimalsystem kann man im $b$-adischen Stellen den ganzahligen Teil des Zahlwortes an den Ziffern vor dem Dezimalpunkt ablesen. Formal liefert das:

$G(x)=z_n\dots z_{0_{(b)}}$

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

Notation Mantisse

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

$M(x)=0.z_{-1}\dots z_{-m_{(b)}}$

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

Notation Vorzeichen

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 $p$-adischen System haben daher in Ziffernnotation eine nachstehende Zeichenfolge. $\pm z_n\dots z_0.z_{-1}\dots z_{-m_{(b)}}$

Normalisierte Gleitkommadarstellung - ganzzahliger Anteil

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 $b$ auch den ganzzahligen Anteil einer reellen Zahl darstellen kann.

$\pm z_n\dots z_0.z_{-1}\dots z_{-m_{(b)}}=0.z_n\dots z_0{z}_{-1}\dots z_{-m_{(b)}}\cdot b^{n+1}$

Normalisierte Gleitkommadarstellung - Mantisse

Bei einer normalisierten Gleitkommadarstellung verwendet man nur eine Matissen und eine Exponenten, mit dem die Ziffernfolge in der Mantisse durch Multiplikation mit Potenzen von $b$ dann als erste Nachkommastelle $z_{-k}$ eine von 0 verschiedene Ziffer besitzt und die folgende reelle Zahl darstellen kann.

$\pm 0.0\dots 0z_{-k}\dots z_{-m_{(b)}}=0.z_{-k}\dots z_0{z}_{-1}\dots z_{-m_{(b)}}\cdot b^{n+1}$

Notation A(b,r,s)

Für die Notation einer normalisierten Gleitkommadarstellung $m\cdot b^n$ benötigt man 3 Festlegungen $(b,r,s)$:

• $b$ als Basis/Bündelungseinheit der Zahlen im $b$-adischen Zahlsystem,
• $r$ die zur Verfügung stehende Ziffernzahl für die Mantisse der Zahl und
• $s$ die Anzahl der Ziffern für den Exponenten $n$ im $b$-adischen Zahlsystem der normalisierten Darstellung.

Exakte und näherungsweise Darstellung von Zahlen

Wenn man z.B. eine periodische Zahldarstellung oder eine irrationale Zahl näherungsweise durch eine endliche $b$-adischen Zahldarstellung repräsentiert, entsteht ein Fehler. Einige Zahlen können aber ohne Fehler dargestellt werden. $𝒜(b,r,s)$ bezeichnet dann die Menge der exakt darstellbaren Zahlen im $b$-adischen Zahlsystem, das mit $r$ Nachkommastellen und $s$ sind die Stellen für den Exponenten der Bündelungseinheit. Eine Fehlerschranke kann in diesem Fall durch eine Potenz von $b$ angegeben werden.

Bemerkung zur exakten und näherungsweisen Darstellung von Zahlen

Ob eine Zahl eine endliche oder unendliche Darstellung im $b$-adischen Zahlsystem hängt von der Bündelungseinheit ab.

• $\frac{1}{7}$ hat im Dezimalsystem eine periodische Dezimalbruchentwicklung,
• $\frac{1}{7}$ hat im 7er-System mit $0.1_{(7)}$ eine endliche $p$-adische Zahldarstellung,

Beispiele Normalisierte Gleitkommadarstellung

Bei der normalisierten Gleitkommadarstellung wird ein Zahl $x=m\cdot b^n$ dargestellt, wobei $|m|<1$ maximal $s$ Nachkommastellen besitzt.

Beispiel 1 - Dezimalsystem

Sei $b:=10$: Die Zahl $-30.421$ lautet (bei Nichtberücksichtigung der Größen $r$ und $s$) in normalisierter Gleitkomma-Darstellung $-0.30421\cdot 10^2$. Letztere Darstellung schreibt man z.B. für $r:=6$ und $s:=2$ auch in der Form $-0.304210E+02$ oder $-0.304210_{10}+02$.

Beispiel 2 - Dezimalsystem

Die Zahl $-0.00030421$ lautet in der normalisierten Gleitkomma-Darstellung für $r:=6$ und $s:=-3$ z. B. $-0.304210E-03$ oder $-0.304210_{10}-03$.

Exakt darstellbare Zahlen in normalisierter Darstellung

Eine normalisierte Gleitkomma-Darstellung mit der Basis $b$, beispielsweise $b:=10$ oder $b:=2$, bestimmt die Menge $𝒜:=𝒜(b;r;s)$ reeller Zahlen, die auf dem Rechner mit $s$ Nachkommatellen exakt dargestellt werden können, die sog. Maschinenzahlen. $r$ gibt dabei dei Stellen für den Exponenten von $b$. Eine solche Zahlendarstellung ermöglicht also nur die Repräsentation einer endlichen Teilmenge der reellen Zahlen.

Kleinste exakt darstellbare Zahl =

Die kleinste darstellbare positive Zahl $a_{\min }$ durch

$M:=0.1,E:=-\underset{s-mal}{\underbrace{(b-1)(b-1)\dots (b-1)}}$

Kleinste exakt darstellbare Zahl =

Die größte positive Zahl $a_{\max }$ ist durch

$M:=0.\underset{r-mal}{\underbrace{(b-1)(b-1)\dots (b-1)}},E:=+\underset{s-mal}{\underbrace{(b-1)(b-1)\dots (b-1)}}$

gegeben. Die Mantisse $M$ von $a_{\min }$ entspricht offenbar der Dezimalzahl $b^{-1}$ und die von $a_{\max }$ der Dezimalzahl

$(b-1)\sum _{i=1}^r{b}^{-i}=(b-1)[\frac{1-b^{-r-1}}{1-b^{-1}}-1]=\frac{b(b^{r+1}-1)}{b^{r+1}}-b+1=1-b^{-r}.$

Der Exponent $E$ für beide Zahlen ist bis auf das Vorzeichen gegeben durch die Dezimalzahl

$(b-1)\sum _{i=0}^{s-1}{b}^i=(b-1)\frac{1-b^s}{1-b}=b^s-1.$

Somit haben $a_{\min }$ und $a_{\max }$ den Dezimalwert

$a_{\min }=b^{-b^s},a_{\max }=(1-b^{-r})b^{b^s-1}.$

Ist $D$ die reelle Zahlenmenge

$D:=[-a_{\max },-a_{\min }]\cup \{0\}\cup [a_{\min },a_{\max }],$

so können also insbesondere Zahlen $x\notin D$ nicht auf dem Rechner wiedergegeben werden. Im Fall $x>a_{\max }$ und $x<-a_{\max }$ melden alle Rechner normalerweise einen Exponentenüberlauf („overflow“), während sie im Fall $x\in (-a_{\min },a_{\min })$ meist keine Meldung machen und $x=0$ setzen.

Ferner ist offenbar nicht jede Zahl $x\in D$ auf dem Rechner, d. h. als $x\in A$ darstellbar (z. B. trifft dies für die Zahlen $\pi$ und $\sqrt{2}$ zu). Somit stellt sich das Problem, eine Zahl $x\in D$ durch eine Zahl aus $A$ zu approximieren. Man verwendet hierzu einen Rundungsoperator $\mathrm{rd}:D\to A$, der jeder Zahl $x\in D$ eine Zahl $\mathrm{rd}(x)\in A$ zuordnet, welche sinnvollerweise der folgenden Beziehung genügt:

(1.2) $|x-\mathrm{rd}(x)|=\underset{a\in A}{\min }|x-a|.$

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 $b:=10$ und eine Endziffer 5 nach oben.

Beispiel 1.5

Sei $b:=10,r:=4$ und $s:=2$. Dann gilt

$\mathrm{rd}(3.14159)=0.3142_{10}+01,$

$\mathrm{rd}(14.2842)=0.1428_{10}+02,$

$\mathrm{rd}(0.142749)=0.1427_{10}+00,$

$\mathrm{rd}(0.14275)=0.1428_{10}+00.$

Allgemein kann man für $b:=10$ und eine Mantissenlänge $r$ die zu einer beliebigen Zahl $x\in D$ gehörende Maschinenzahl $\mathrm{rd}(x)\in A$ folgendermaßen finden. Es sei dazu $x\in D$ zunächst in der Form $x=a\cdot 10^q$ dargestellt, wobei $q\in \mathbb{Z}$ und

$|a|=0.{\alpha }_1{\alpha }_2\dots {\alpha }_r{\alpha }_{r+1}\dots$

mit $0\le {\alpha }_i\le 9$ und ${\alpha }_1\ne 0$ seien. Insbesondere ist also $|a|\ge 0.1$. Zu $a$ bildet man nun

$\tilde{a}:=\{\begin{array}{cc}0.{\alpha }_1{\alpha }_2\dots {\alpha }_r,& \text{falls }0\le {\alpha }_{r+1}\le 4,\\ 0.{\alpha }_1{\alpha }_2\dots {\alpha }_r+10^{-r},& \text{falls }{\alpha }_{r+1}\ge 5\end{array}$

und setzt dann

$\mathrm{rd}(x):=\mathrm{sgn}(x)\cdot \tilde{a}\cdot 10^q.$

Offenbar ist die Zahl $\mathrm{rd}(x)$ für jedes $x\in D$ eine Maschinenzahl, d. h. $\mathrm{rd}(x)\in A$.

Beispiel 1.6

Für $b:=10,r:=4$ und $s:=2$ folgt

$\mathrm{rd}(0.99997_{10}+98)=0.1000_{10}+99,$

$\mathrm{rd}(0.012345_{10}-9)=0.1235_{10}-10.$

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

$|x-\mathrm{rd}(x)|\le 5\cdot 10^{-(r+1)}\cdot 10^q=\frac{1}{2}10^{-r}10^q$

und für den relativen Fehler, sofern $x\ne 0$ ist,

$\frac{|x-\mathrm{rd}(x)|}{|x|}\le \frac{0.5\cdot 10^{-r}10^q}{|a|10^q}\le \frac{0.5\cdot 10^{-r}}{0.1}=\frac{1}{2}10^{-r+1}.$

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

$|x-\mathrm{rd}(x)|\le \frac{1}{2}{b}^{-r}{b}^q,\frac{|x-\mathrm{rd}(x)|}{|x|}\le \frac{1}{2}{b}^{-r+1}.$

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

$eps:=\frac{1}{2}{b}^{-r+1}.$

Mit dieser gilt also

(1.3) $\mathrm{rd}(x)=x(1+\epsilon ),|\epsilon |\le eps,$

wie man mit der Setzung $\epsilon :=-(x-\mathrm{rd}(x))/x$ sieht.

Beispiel 1.7 (IEEE-Standard)

$\begin{array}{ccc}& \text{single precision}& \text{double precision}\\ a_{\min }& 1.10\cdot 10^{-38}& 2.23\cdot 10^{-308}\\ a_{\max }& 3.40\cdot 10^{+38}& 1.80\cdot 10^{+308}\\ eps& 0.60\cdot 10^{-7}& 1.11\cdot 10^{-16}\end{array}$

Die arithmetischen Grundoperationen $+,-,*,/$ werden auf digitalen Rechnern durch sog. Gleitpunktoperationen ersetzt, welche Maschinenzahlen wieder auf Maschinenzahlen abbilden. Sind $a,b\in A$, ist „$\circ$“ eine der vier Grundoperationen, $c:=a\circ b$ und $c\in D$, so definiert man die zugehörige Gleitpunktoperation $gl(a\circ b)$ durch

$gl(a\circ b):=\mathrm{rd}(a\circ b).$

Für sie gilt nach (1.3)

$gl(a\circ b)=(a\circ b)(1+\epsilon ),|\epsilon |\le eps.$

Für das Ergebnis $c:=a\circ b$ kann natürlich auch $c\notin D$ gelten. In diesem Fall meldet der Rechner normalerweise einen Exponentenüberlauf oder setzt er $c:=0$.

1.4 Differentielle Fehleranalyse

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 $f:{ℝ}^n\to {ℝ}^m$ durch die Gleichung

$f(x)=y$

bzw. gleichbedeutend durch die Gleichungen

(1.4) $f_i(x)=y_i,i=1,\dots ,m$

beschrieben wird. Dabei ist also $x\in {ℝ}^n$ der Daten- und $y\in {ℝ}^m$ der Ergebnis-Vektor. Für

$f(x+\mathrm{\Delta }x)=:y+\mathrm{\Delta }y$

gilt dann nach dem Satz von Taylor zeilenweise

(1.5) $\mathrm{\Delta }{y}_i=f_i(x+\mathrm{\Delta }x)-f_i(x)=\sum _{j=1}^n\frac{\partial f_i}{\partial x_j}(x)\mathrm{\Delta }{x}_j+𝒪(\underset{j=1,\dots ,n}{\max }|\mathrm{\Delta }{x}_j{|}^2),i=1,\dots ,m,$

so dass für hinreichend kleine $|\mathrm{\Delta }{x}_j|$ der Restterm $𝒪(\underset{j=1,\dots ,n}{\max }|\mathrm{\Delta }{x}_j{|}^2)$ vernachlässigt werden kann und folglich der dominierende relative Fehler gegeben ist durch

$\frac{|\mathrm{\Delta }{y}_i|}{|y_i|}\approx \sum _{j=1}^n|\frac{\partial f_i}{\partial x_j}(x)\frac{x_j}{f_i(x)}|\left|\frac{\mathrm{\Delta }{x}_j}{x_j}\right|=\sum _{j=1}^n{k}_{ij}(x)\left|\frac{\mathrm{\Delta }{x}_j}{x_j}\right|,i=1,\dots ,m$

mit

$k_{ij}(x):=|\frac{\partial f_i}{\partial x_j}(x)|\left|\frac{x_j}{f_i(x)}\right|$

Die Größen $k_{ij}(x)$ entscheiden demnach über den Einfluss der relativen Fehler $|\mathrm{\Delta }{x}_j|/|x_j|$ in den Daten auf den relativen Fehler $|\mathrm{\Delta }{y}_i|/|y_i|$ 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 $k_{ij}(x)$ „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 $k_{ij}(x)$ 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

Die Lösungen ${\lambda }_1$ und ${\lambda }_2$ einer quadratischen Gleichung

(1.6) $x^2-2px+q=0$

sind gegeben durch

(1.7) ${\lambda }_{1,2}:=p\pm \sqrt{p^2-q},$

wobei wir hier davon ausgehen, dass die Gleichung zwei unterschiedliche reelle Lösungen besitzt, also

$p^2-q>0$

ist. Zur Analyse der Fehlerempfindlichkeit der beiden Lösungen von (1.6) in Abhängigkeit von den Eingabedaten $p$ und $q$ betrachten wir diese nun als Funktionen von $p$ und $q$. Wir untersuchen dazu die beiden Gleichungen

(1.8) ${\lambda }_1(p,q)=p+\sqrt{p^2-q},{\lambda }_2(p,q)=p-\sqrt{p^2-q}.$

(Im Vergleich mit (1.4) ist $x:=(p,q),m=2,f_i:={\lambda }_i$ und entsprechen die rechten Seiten in (1.8) den $y_i$.) Man hat dafür

(1.9) ${\lambda }_1+{\lambda }_2=2p,{\lambda }_1-{\lambda }_2=2\sqrt{p^2-q},{\lambda }_1{\lambda }_2=q.$

Damit errechnet man

$\frac{\partial {\lambda }_{1,2}}{\partial p}=1\pm \frac{p}{\sqrt{p^2-q}}=\frac{\sqrt{p^2-q}\pm p}{\sqrt{p^2-q}}=\pm \frac{{\lambda }_{1,2}}{{\lambda }_1-{\lambda }_2},$

$\frac{\partial {\lambda }_{1,2}}{\partial p}=\mp \frac{1}{2\sqrt{p^2-q}}=\mp \frac{1}{{\lambda }_1-{\lambda }_2}.$

Hieraus ergeben sich die Verstärkungsfaktoren

$k_{11}:=\left|\frac{\partial {\lambda }_1}{\partial p}\frac{p}{{\lambda }_1}\right|=\left|\left(\frac{2{\lambda }_1}{{\lambda }_1-{\lambda }_2}\right)\left(\frac{{\lambda }_1+{\lambda }_2}{2{\lambda }_1}\right)\right|=\frac{|1+({\lambda }_1/{\lambda }_2)|}{|1-({\lambda }_1/{\lambda }_2)|},$

$k_{12}:=\left|\frac{\partial {\lambda }_1}{\partial q}\frac{q}{{\lambda }_1}\right|=\left|\left(\frac{1}{{\lambda }_1-{\lambda }_2}\right)\left(\frac{{\lambda }_1{\lambda }_2}{{\lambda }_1}\right)\right|=\frac{1}{|1-({\lambda }_1/{\lambda }_2)|},$

$k_{21}:=\left|\frac{\partial {\lambda }_2}{\partial p}\frac{p}{{\lambda }_2}\right|=\left|\left(\frac{2{\lambda }_2}{{\lambda }_1-{\lambda }_2}\right)\left(\frac{{\lambda }_1+{\lambda }_2}{2{\lambda }_2}\right)\right|=k_{11},$

$k_{22}:=\left|\frac{\partial {\lambda }_2}{\partial q}\frac{q}{{\lambda }_2}\right|=\left|\left(\frac{1}{{\lambda }_1-{\lambda }_2}\right)\left(\frac{{\lambda }_1{\lambda }_2}{{\lambda }_2}\right)\right|=k_{12}.$

Die Bestimmung der Lösungen von (1.6) ist somit für ${\lambda }_1\approx {\lambda }_2$ ein schlecht konditioniertes Problem. Zur Veranschaulichung geben wir ein Zahlenbeispiel. Es seien $p:=2$ und $q:=3.999$. Dann sind ${\lambda }_1=2.01$ und ${\lambda }_2=1.99$ die beiden Nullstellen von (1.6). Für die Verstärkungsfaktoren ergibt sich in diesem Fall

$k_{11}=k_{21}=\frac{|1+({\lambda }_1/{\lambda }_2)|}{|1-({\lambda }_1/{\lambda }_2)|}\approx 200,k_{22}=k_{12}=\frac{1}{|1-({\lambda }_1/{\lambda }_2)|}\approx 99.5.$

Somit ist zu erwarten, dass Eingabefehler in den Daten $p$ und $q$ in Bezug auf die Lösungen ${\lambda }_1$ und ${\lambda }_2$ von (1.6) um den 100- bis 200-fachen Wert verstärkt werden.

Wir wollen nun zwei unterschiedliche Algorithmen zur Berechnung von

${\lambda }_1:=p+\sqrt{p^2-q},{\lambda }_2:=p-\sqrt{p^2-q}$

betrachten und zwar unter den Bedingungen

(1.10) $p^2-q>0,|q|\ll p^2,p<0.$

In diesem Fall ist offenbar

${\lambda }_1\approx -|p|+|p|=0,{\lambda }_2\approx -|p|-|p|=-2|p|,$

d. h. für nicht zu kleine $|p|$ auch ${\lambda }_1\gg {\lambda }_2$ 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

$u:=p^2,v:=u-q,w:=\sqrt{v}\ge 0.$

Wegen $p<0$ sollte man als nächstes den unkritischen Wert

${\lambda }_2:=p-w$

berechnen. Zur Berechnung von ${\lambda }_1$ betrachten wir nun zwei Varianten (vgl. (1.9)):

$\text{Variante A}:{\lambda }_1:=p+w,$

$\text{Variante B}:{\lambda }_1:=q/{\lambda }_2.$

Da unter den Voraussetzungen (1.10) $w\approx -p$ gilt, tritt bei Variante A zwangsläufig Auslöschung auf. Betrachtet man ${\lambda }_1$ als Funktion in den Variablen $p$ und $w$, so erhält man für die Verstärkungsfaktoren

$k_{11}(p,w)=\left|\frac{p}{p+w}\right|=\underset{\gg 1}{\underbrace{\left|\frac{1}{1+(w/p)}\right|}},$

$k_{12}(p,w)=\left|\frac{w}{p+w}\right|=\underset{\gg 1}{\underbrace{\left|\frac{1}{1+(p/w)}\right|}}.$

Also ist die Variante A im Fall (1.10) nicht stabil. Bei Variante B erhält man dagegen

$k_{11}(q,{\lambda }_2)=k_{12}(q,{\lambda }_2)=1.$

D. h., der Algorithmus B ist stabil. Für $p:=-2$ und $q:=0.01$ ergibt sich bei exakter (bzw. 4-stelliger) Rechnung

$u:=p^2=4(4.000),$

$v:=u-q=3.99(3.990),$

$w:=\sqrt{v}=1.99749\dots (1.997),$

${\lambda }_2:=p-w=-3.9974\dots (-3.997).$

Die exakte Lösung für ${\lambda }_1$ ist ${\lambda }_1=-0.0025$. Bei Rechnung mit 4-stelliger Mantisse erhält man im Fall der Variante B ${\lambda }_1=-0.0025$, während man für die Variante A ${\lambda }_1=-0.0030$ erhält mit einem relativen Fehler bezüglich der exakten Lösung von

$\left|\frac{0.0030-0.0025}{0.0025}\right|=0.2$

Im Fall

$p^2-q>0,|q|\ll p^2,p>0$

gilt offenbar $w\approx p$. Somit ist die Berechnung von ${\lambda }_1:=p+w$ stabil möglich und von ${\lambda }_2:=p-w$ kritisch. Ein stabiler Algorithmus ergibt sich hier durch die Vertauschung der Rollen von ${\lambda }_1$ und ${\lambda }_2$ 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

• absoluter Fehler
• relativer Fehler

Seiteninformation

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

Wiki2Reveal

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.

• Die Seite wurde als Dokumententyp PanDocElectron-SLIDE erstellt.
• Link zur Quelle in Wikiversity: https://de.wikiversity.org/wiki/Kurs:Numerik%20I/Besonderheiten%20des%20numerischen%20Rechnens
• siehe auch weitere Informationen zu Wiki2Reveal und unter Wiki2Reveal-Linkgenerator.