Kurs 01270 Numerische Mathematik - FernUniversität Hagen€¦ · 1.2. MASCHINENARITHMETIK 5 1.2.1 Gleitkommazahlen Für technisch-wissenschaftliche Anwendungen – so auch in der

Numerische Mathematik

Prof. Dr. Torsten Linß

Kurs 01270

LESEPROBE

Das Werk ist urheberrechtlich geschutzt. Die dadurch begrundeten Rechte, insbesondere das Recht der Vervielfaltigung

und Verbreitung sowie der Ubersetzung und des Nachdrucks bleiben, auch bei nur auszugsweiser Verwertung, vorbe-

halten. Kein Teil des Werkes darf in irgendeiner Form (Druck, Fotokopie, Mikrofilm oder ein anderes Verfahren) ohne

schriftliche Genehmigung der FernUniversitat reproduziert oder unter Verwendung elektronischer Systeme verarbeitet,

vervielfaltigt oder verbreitet werden.

c�20

16Tor

sten

Linß,

FernU

niin

Hagen

Kapitel 1

Fehleranalyse und Computerzahlen

Sich zu Beginn eines Mathematikkurses lang und breit über Fehler auszulassen, mag etwas ab-surd erscheinen, wo doch gerade in der Mathematik auf logische Strenge und Exaktheit größterWert gelegt wird. Es geht vielmehr darum, im Grunde außermathematische Einflüsse in ihrerWirkung auf Resultate mathematischer Rechnungen zu analysieren und zu bewerten. Um einkonkretes Problem aus der Praxis zu lösen, beschreibt man es mit dem Formalismus der Mathe-matik, formt es so um, dass es algorithmisch zugänglich ist und bestimmt schließlich eine genä-herte Lösung mit Hilfe verfügbarer Rechentechnik. In allen drei Stufen können Fehler auftreten,die einzugrenzen sind, um entscheiden zu können, ob das erhaltene Resultat einen akzeptablenErsatz für das eigentlich gesuchte Ergebnis darstellt. Eine kleine Geschichte, die von Prof. FranzLocher überliefert wurde, mag die Problematik erläutern.

Der berühmte Gallier Obelix wollte in der Nähe seines Dorfes eine Hinkelstein-Allee errichten.Die Steinreihe sollte 60 Steine umfassen und genau geradlinig verlaufen. Je zwei Steine sollteneinen Abstand von 30 Obelix-Längen haben. Obelix hatte sich einen Stock geschnitten, der genauso lang war wie er selbst und den er als Maßstab benutzte. Zum Peilen, ob die Steine in einerGeraden stehen, verließ er sich auf sein scharfes Auge.

Alles war gut gegangen, aber beim 57. Stein gab es Probleme. Denn gleich nach dem 56. Steinwar das Ufer eines kleinen, ungefähr 15 Obelix-Längen breiten Teiches. Wo genau sollte der 57.Stein aufgestellt werden?

Teich3030

30

57 ?55 5654

Abbildung 1.1: Lage des 57. Steines

1

c�20

16Tor

sten

Linß,

FernU

niin

Hagen

2 KAPITEL 1. FEHLERANALYSE UND COMPUTERZAHLEN

Obelix überlegte hin und her. Auch ein leckerer Wildschweinbraten half ihm nicht auf die richtigeSpur. Schließlich holte er sich Rat bei dem Druiden Numerix aus dem Nachbardorf Agen, einemetwas introvertierten Vetter seines Freundes Asterix, der bei so kniffligen Problemen oft ganzgute Ideen hatte.

Abbildung 1.2: Obelix und Numerix

Kein Problem für Numerix! Er malte eine Skizze in den Sand und erklärte Obelix, dass er zweiHilfshinkelsteine A und B genau mit den angegebenen Abständen plazieren solle. Dann könne ervon A und B aus auch den 57. Stein genau positionieren. Wichtig seien die Abstände von 30 und42 Obelix-Längen, was immer die Zahl 42 bedeuten mochte.

A

30

57 ?

Teich

55 5654

3030

30

30

42 4242

B

Abbildung 1.3: Konstruktion mit Hilfe von Hilfshinkelsteinen

Obelix ging ans Werk und plagte sich einen ganzen Tag (Numerix hatte vergessen, ihm zu raten,ein langes Seil zu verwenden!), bis er schließlich den 57. Stein aufgestellt hatte, der aber leidernicht in einer Fluchtlinie mit den anderen stand. Am nächsten Morgen zog er nochmals Numerix

c�20

16Tor

sten

Linß,

FernU

niin

Hagen

1.1. ABSOLUTER UND RELATIVER FEHLER 3

zu Rate. Der meinte zwar, ein bißchen mogeln müsse man am Schluss vielleicht schon, abernicht so viel, wie es hier anscheinend nötig sei. Irgend etwas war faul im Staate Gallien. Numerixmaß alles nach und stellte dann auch fest, daß der Abstand von A nach B nur 28 Obelixlängenbetrug. (Obelix waren beim Abstecken zwei Wildschweine über den Weg gelaufen; er hatte seineArbeit kurz unterbrochen und in der Aufregung die Wildschweine mitgezählt.) Als Numerix diesberichtigt hatte, stand auch der 57. Stein ganz ordentlich in der Reihe. Obelix freute sich; aberNumerix dachte, man hätte halt doch 42 und eine halbe Länge statt nur 42 nehmen sollen!

Ihnen ist sicher schnell klar, warum auch beim zweiten Mal der 57. Stein nicht genau in derFluchtlinie stand – offensichtlich eine Folge von Fehlern und von Fehlerakkumulation. Bei denFehlern, mit denen Obelix zu kämpften hatte, können wir verschiedene Typen unterscheiden:

• menschlicher Irrtum,

• Modellfehler (der geometrischen Konstruktion liegt der Satz von Pythagoras1 zu Grunde,der natürlich nur in vollkommen ebenem Gelände anwendbar ist),

• Messfehler (z.B. bei der Peilung auf Geradlinigkeit),

• Rundungsfehler (1.4 statt√

2).

1.1 Absoluter und relativer Fehler

Diese beiden Begriffe sind wesentlich in der Fehlerrechnung und ihrem Wesen nach bekannt.Trotzdem möchten wir sie hier nochmals formal definieren.

Definition 1.1.1. Seien α, α ∈ C, wobei wir α als Näherung der Größe α interpretieren. Wirnennen

Δα ≔ α − α

den absoluten Fehler von α und

εα ≔Δα

|α| =α − α|α| , α � 0,

den relativen Fehler von α.

Bemerkung 1.1.2. Beachten Sie, dass die Fehler vorzeichenbehaftet sind. Oft wird man sichlediglich für eine Abschätzung des Betrags der Fehler interessieren.

Bemerkung 1.1.3. Absolute Fehler sind von geringer Aussagekraft. Wird, z.B., für einen Mara-thonlauf die Strecke um 1mm falsch vermessen, hat dies keinen Einfluss auf den Rennausgang.Bei einer 4mm-Schraube sieht dies anders aus. Abweichungen von 1mm machen sie unbrauch-bar. Von größerer Beutung sind daher relative Fehler, da sie die Abweichung in Relation zurGröße setzen.

1Pythagoras von Samos, *≈569 v. Chr., †≈ 475 v. Chr.

c�20

16Tor

sten

Linß,

FernU

niin

Hagen


Bei Rechnung mit fehlerbehafteten Größen ist ein Ergebnis zu erwarten, das ebenfalls mit ei-nem Fehler behaftet ist. Wir wollen uns dies an einem einfachen Beispiel veranschaulichen, derBerechnung des Volumens einer Pyramide mit Grundfläche F > 0 und Höhe h > 0.

Da sowohl F als auch h fehlerbehaftet sein können, ist auch für das Volumen

V =1

3F · h

ein Fehler zu erwarten. Seien also F = F + ΔF und h = Δh + h die fehlerbehaftete Grundflächebzw. Höhe. Das mit diesen Näherungen ermittelte Volumen der Pyramide sei

V =1

3F · h.

Für den absoluten Fehler des Volumens gilt (Übungsaufgabe!)

ΔV = V − V =1

3

�

FΔh + hΔF + ΔFΔh

�

. (1.1)

Sind die Fehler ΔF und Δh klein, dann ist ihr Produkt ΔFΔh sehr klein und kann vernachlässigtwerden:

ΔV �1

3

�

FΔh + hΔF

�

. (1.2)

Im Rahmen der Fehlerrechnung sprechen wir von Gleichheit in linearen Näherung (oder ers-ter Näherung), wenn Produkte und höhere Potenzen (größer als 1) der Fehler vernachlässigtwerden. Statt des Gleichheitszeichens verwenden wir das Symbol „�“.

Zur Bestimmung des relativen Fehlers des Volumens dividieren wir (1.2) durch V = 13 F · h > 0

und erhalten für den relativen Fehler des Volumens in linearer Näherung

εV =ΔV

V�

13

(FΔh + hΔF)13 F · h

=Δh

h+ΔF

F= εF + εh.

Wir stellen fest, dass sich bei der Berechnung des Volumens der Pyramide die relativen Fehler(in linearer Näherung) addieren.

Aufgabe 1.1.4. Verifizieren Sie (1.1). ♦

1.2 Maschinenarithmetik

Die Beschränktheit der Resourcen eines Computers, insbesondere des Speicherplatzes, bedingt,dass nicht alle reellen Zahlen auf einem Computer zur Verfügung stehen, sondern lediglich eineendliche Teilmenge. Dieser Abschnitt führt ein in das Rechnen mit Computerzahlen.

c�20

16Tor

sten

Linß,

FernU

niin

Hagen

1.2. MASCHINENARITHMETIK 5

1.2.1 Gleitkommazahlen

Für technisch-wissenschaftliche Anwendungen – so auch in der numerischen Mathematik – ha-ben sich Gleitkommazahlen (engl.: floating-point numbers) durchgesetzt. Sie werden durch

• Vorzeichen, Mantisse, Basis und Exponent

beschrieben. Z.B. entspricht dem Dezimalbruch −5432.1 die Gleitkomma-Darstellung

− 0.54321 × 104

↑ ↑ ↑ տ ExponentVorzeichen Mantisse Basis e = 4σ = −1 b = 10

Die Eingabe und Ausgabe von Zahlen erfolgt in der Regel im Dezimalsystem, da es uns amgeläufigsten ist. Zur eigentlichen Rechnung müssen diese Zahlen jedoch in das interne Zahlen-system des Computers umgewandelt werden, das i.Allg. auf dem Dualsystem basiert.

Im Dualsystem mit Basis b = 2 wird dabei jede Zahl x ∈ R nach Zweierpotenzen entwickelt:

x = ±�

αk2k + αk−12k−1 + · · ·

�

, αk � 0, α j ∈ {0, 1}, j = k, k − 1, . . .

Dem entspricht die Darstellung als Dualbruch

x = ±�αkαk−1αk−2 · · ·α0 . α−1α−2 · · ·�

2,

↑Komma, Dualpunkt

wobei ein tiefgestelltes b in der Darstellung [. . . ]b die zugrundeliegende Basis angibt.

Definition 1.2.1. Seien b ∈ N \ {1}, m ∈ N, e∗, e∗ ∈ Z, e∗ < e∗. Die Elemente der Menge

Mb(m, [e∗, e∗]) ≔

�

0� ∪�

x ∈ R : x = σbem�

i=1

zib−i, σ ∈ {−1, 1},

zi ∈ {0, 1, . . . , b − 1}, z1 � 0, e ∈ Z, e∗ ≤ e ≤ e∗�

heißen die (normalisierten) Gleitkommazahlen mit Mantissenlänge m ∈ N, Basis b ∈ N \ {1}und Exponentenbereich [e∗, e∗]. In dieser halbexponentiellen Darstellung wird das Vorzeichen

der Gleitkommazahl durch σ repräsentiert, die zi sind die Ziffern und e der Exponent.

Die endliche MengeMb(m, [e∗, e∗]) normalisierter Gleitkommazahlen ist durch die Parameter b,m sowie das Intervall [e∗, e∗] festgelegt. Man kann sich überlegen, dassMb(m, [e∗, e∗]) exakt

2(b − 1)bm−1(e∗ − e∗ + 1) + 1

c�20

16Tor

sten

Linß,

FernU

niin

Hagen


−4 −3 −2 −1 0 1 2 3 4

R

Abbildung 1.4: Normalisierte Gleitkommazahlen; vertikale Linien repräsentieren die ElementevonM2(3, [−1, 2]).

Zahlen umfasst, die auf der reellen Zahlenachse aber nicht gleichmäßig verteilt sind, wasAbb. 1.4 an einem einfachen Beispiel verdeutlicht.

Die kleinste positive Zahl inMb(m, [e∗, e∗]) ist

zmin ≔ min�

y : y ∈ Mb(m, [e∗, e∗]), y > 0

�

= [0.10 · · · 0]b · be∗ = be∗−1,

die größte ist

zmax ≔ max�

y : y ∈ Mb(m, [e∗, e∗])�

= [0. (b − 1)(b − 1) · · · (b − 1)��

m−mal Ziffer b−1

]b · be∗ ≈ be∗ .

Bei Betrachtung von Abb. 1.4 fallen die Lücken zwischen Null und ±zmin auf – die sog. „Lückenum die Null“. Diese können durch Übergang zu den denormalisierten GleitkommazahlenMb(m, [e∗, e∗]) aufgefüllt werden, bei denen als erste Ziffer der Mantisse auch die Null zuge-lassen wird, siehe Abb. 1.5.

−4 −3 −2 −1 0 1 2 3 4

R

Abbildung 1.5: Denormalisierte Gleitkommazahlen M2(3, [−1, 2]).

Aufgabe 1.2.2. Bestimmen Sie alle Elemente vonM2 (3, [−1, 2]) ! ♦

1.2.2 Rundung

Eine gegebene reelle Zahl z lässt sich i.Allg. nicht durch eine Gleitkommazahl darstellen. Zahlen,die betragsmäßig größer als zmax sind, lassen sich nicht sinnvoll durch eine Gleitkommazahl re-präsentieren und werden computerintern als „NaN“ (engl.: not-a-number) gekennzeichnet. Manspricht auch davon, dass ein Gleitkommaüberlauf (engl.: overflow) stattgefunden hat.

c�20

16Tor

sten

Linß,

FernU

niin

Hagen


Ist |z| ≤ zmax, so muss z ∈ R \ Mb(m, [e∗, e∗]) auf eine Maschinenzahl gerundet werden. Formalwird z durch eine nächstgelegene Gleitkommazahl rd(z) approximiert. Die Abbildung

rd : [−zmax, zmax]→ Mb(m, [e∗, e∗]) : z �→ rd(z)

mit

|rd(z) − z| = miny∈Mb(m,[e∗,e∗])

|y − z| . (1.3)

wird als Rundung bezeichnet. In der Regel ist rd(z) eindeutig bestimmt. Liegt allerdings z exaktin der Mitte zweier benachbarter Gleitkommazahlen, dann gibt es zwei potentielle Kandidatenfür rd(z). Für diesen Fall sind in den entsprechenden Standards Festlegungen getroffen, die Ein-deutigkeit schaffen. Ist rd(z) = 0 für ein z � 0, so spricht man von Gleitkommaunterlauf.

Realisiert wird die Rundung auf zwei Wegen:

• prozessorintern, falls z das Ergebnis einer Rechenoperation mit Maschinenzahlen ist,

• durch Programmbibliotheken, falls z eine Programmeingabe ist, z.B. durch Eingabe alsZeichenkette.

Für ein gegebenes z ∈ R ist eine obere Schranke für den Betrag des absoluten Rundungsfehlersdurch (1.3) gegeben:

|rd(z) − z| = miny∈Mb(m,[e∗,e∗])

|y − z| .

Wie eingangs diskutiert (Bem. 1.1.3) sind absolute Fehler von geringer Aussagekraft. Von grö-ßerer Bedeutung sind relative Fehler. Für eine reelle Zahl z � 0 ist der relative Rundungsfehlerbei Repräsentation durch Maschinenzahlen gegeben durch

rd(z) − z

|z| ,

vgl. Def. 1.1.1. Ihn wollen wir im Folgenden genauer untersuchen.

Sei z ∈ R mit |z| ∈ [zmin, zmax]. Dann existiert ein eindeutig bestimmtes e ∈ [e∗, e∗] mit|z| ∈ [be−1, be). Die normalisierten Gleitkommazahlen im Intervall [be−1, be] sind

[0.10 · · · 00]b · be, [0.10 · · · 01]b · be, . . . , [0.(b − 1) · · · (b − 1)]b · be, [1.0 · · · 0]b · be.

Man überlegt sich, dass auf dem Intervall [be−1, be] der Abstand zwischen zwei benachbartenGleitkommazahlen be−m ist. Für den Betrag des absoluten Rundungsfehler folgt somit zunächst

|rd(z) − z| ≤ 1

2be−m

c�20

16Tor

sten

Linß,

FernU

niin

Hagen


und für den relativen Rundungsfehler

|rd(z) − z||z| ≤ 1

2

be−m

be−1=

1

2b1−m

≕ eps, (1.4)

da |z| ≥ be−1.

Die Größe eps, welche bei gewählter Basis nur von der Länge m der Mantisse abhängt, wird alsMaschinengenauigkeit bezeichnet. Sie ist die wichtigste Größe, die Gleitkommaarithmetikencharakterisiert.

Wir formalisieren dieses letzte Ergebnis und schaffen uns zugleich ein Modell zur mathemati-schen Fassung der Gleitkommazahlen.

Satz 1.2.3. Die Abbildung rd : [−zmax, zmax]→ Mb(m, [e∗, e∗]) erfülle (1.3). Dann existiert fürjedes z ∈ R, zmin ≤ |z| ≤ zmax, ein ε ∈ R mit

rd(z) = (1 + ε) z und |ε| ≤ eps = 1

2b1−m.

Bemerkung 1.2.4. Ist z ∈ (−zmin, zmin) – also wenn denormalisierte Gleitkommazahlen zum Ein-satz kommen – dann gilt die Abschätzung (1.4) i.Allg. nicht. Für z→ 0 konvergiert der relativeRundungsfehler gegen Eins.

In der Praxis haben sich die IEEE2-Standards mit unterschiedlichen Genauigkeiten durchgesetzt:

• einfache Genauigkeit: M2(24, [−126, 127]),

• doppelte Genauigkeit: M2(53, [−1022, 1023]) und

• erweiterte doppelte Genauigkeit: M2(64, [−16382, 16383]).

Die für sie charakteristischen Parameter sind in der folgenden Tabelle aufgelistet. Sie enthältaußerdem die Namen der entsprechenden C-Datentypen sowie die Anzahl der zur Speicherungeiner Gleitkommazahl des jeweiligen Typs benötigten Bytes. Die Wahl der Exponentenbereichebedingt, dass zmax ≈ 1/zmin, weshalb zmax nicht angegeben ist.

b m e∗ e∗ eps zmin C, C++ Bytes2 24 −126 127 5.960 · 10−8 5.878 · 10−39 float 42 53 −1022 1023 1.110 · 10−16 1.112 · 10−308 double 82 64 −16382 16383 5.421 · 10−20 1.681 · 10−4932 long double 12

Tabelle 1.1: Parameter der Maschinenzahlen des IEEE-Standards

2Institute of Electrical and Electronics Engineers, https://www.ieee.org/

c�20

16Tor

sten

Linß,

FernU

niin

Hagen


Bemerkung 1.2.5. Für höhere Genauigkeiten sind Programmbibliotheken entwickelt worden,z.B. die GNU Multiple Precision Arithmetic Library3 oder ARPREC4. Allerdings hat höhereGenauigkeit ihren Preis, nämlich längere Rechenzeiten und höheren Speicherbedarf.

Bemerkung 1.2.6. Für die Kodierung des Vorzeichens wird ein Bit benötigt. Bei Verwendungder Basis 2 genügen für die Mantisse normalisierter Gleitkommazahlen m − 1 Bits, da die ers-te Mantissenstelle stets Eins ist. Für den Exponenten werden 8, 11 bzw. 16 Bits (bei einfacher,doppelter bzw. erweiterter doppelter Genauigkeit) benötigt. Bei genauerer Betrachtung fällt auf,dass statt der möglichen 256, 2048 bzw. 32768 Exponenten lediglich 254, 2046 bzw. 32766 ver-wendet werden. Die verbleibenden zwei möglichen Exponenten werden genutzt, um anzuzeigen,dass

• ein Überlauf stattgefunden hat, also keine sinnvolle Gleitkommazahl vorliegt, oder

• die kodierte Zahl eine denormalisierte Gleitkommazahl ist. In diesem Fall ist der Exponente = e∗ und die erste Mantissenstelle ist Null.

Bemerkung 1.2.7. Die vier Grundrechenarten mit IEEE-konformen normalisierten Gleitkom-mazahlen werden hardwareseitig durch alle aktuellen Prozessortypen unterstützt. Rechenopera-tionen mit denormalisierten Zahlen werden mittels Programmbibliotheken bewerkstelligt undsind i.Allg. wesentlich langsamer. Die Nutzung denormalisierter Zahlen kann durch Compiler-optionen beeinflusst werden.

1.2.3 Grundoperationen und elementare Funktionen

Wir wenden uns jetzt den arithmetischen Grundoperationen zu. Diese liefern als Resultate i.a.selbst dann keine Gleitkommazahlen, wenn die Operanden Gleitkommazahlen sind. Daher sindmaschinen-interne Rundungen erforderlich. Als Resultat erhält man Näherungen

x ⊕ y, x ⊖ y, x ⊗ y und x ⊘ y

für die arithmetischen Grundoperationen

x + y, x − y, x × y und x/y.

Die Näherungen werden in zwei Schritten berechnet:

S1. Aus den zwei Operanden wird zunächst prozessorintern ein Zwischenresultat mit höhererGenauigkeit durch Rechnung mit längerer Mantisse gebildet.

S2. Anschließend wird dieses Ergebnis auf die normale Stellenzahl gerundet und auf denentsprechenden Speicherplatz geschrieben.

3http://gmplib.org/4http://crd-legacy.lbl.gov/∼dhbailey/mpdist/

c�20

16Tor

sten

Linß,

FernU

niin

Hagen


Oder kurz

x ⊙ y ≔ rd(x · y),

wobei „·“ und „⊙“ für eine beliebige der vier Grundoperationen bzw. ihre maschinenseitige Rea-lisierung stehen.

Die so implementierten arithmetischen Grundoperationen besitzen folgende Eigenschaft: Für allex, y ∈ Mb(m, [e∗, e∗]) mit |x · y| ∈ [zmin, zmax] existiert ein ε ∈ R derart, dass

x ⊙ y = (1 + ε) (x · y) mit |ε| ≤ eps.

Elementare Funktionen

f ∈�

sin, cos, tan,√, exp, ln, . . .

�

werden mittels Programmbibliotheken ausgewertet. Ist f◦ die programmtechnische Implementie-rung von f , dann gilt

f◦(x) = (1 + ε) f (x) für alle x ∈ Ω ⊂ Df , mit |ε| ≤ Kfeps, (1.5)

mit einer moderaten Konstante Kf , z.B. Kf ∈ [1, 10]. Für welchen Teilbereich Ω der Gleit-kommazahlen Abschätzungen dieses Typs tatsächlich gelten, und wie groß Kf ist, sollte demCompiler-Handbuch zu entnehmen sein.

Aufgabe 1.2.8. Betrachtet werde die Menge der Gleitkommazahlen M2(4, [−7, 7]). Bestimmen Sie fürjede der folgenden Operationen mit den Computerzahlen x = [0.1011]2 · 20 und y = [0.1100]2 · 20, ob sieexakt ausgeführt werden oder ob es zu Rundungen, Überlauf oder Unterlauf kommt:

z = x ⊖ y, z = (y ⊖ x)10, z = x ⊕ y, z = y ⊕ (x ⊘ 4) und z = x ⊕ (y ⊘ 4).

Bemerkung: Zur Vereinfachung erfolge die Rundung nach jedem Rechenschritt durch einfaches Abschnei-den nach der 4. Mantissenstelle. ♦

Aufgabe 1.2.9. Das Distributivgesetz

(a + b)c = ac + bc

gilt in der Menge der Gleitkommazahlen i.Allg. nicht. Diskutieren Sie, inwieweit das Distributivgesetzverletzt wird!

Gegeben seien dazu eine Gleitkommaarithmetik mit Maschinengenauigkeit eps sowie Gleitkommazahlena, b und c. Wir setzen

y1 = (a ⊕ b) ⊗ c und y2 = (a ⊗ c) ⊕ (b ⊗ c).

Die relativen Fehler εk, k = 1, 2, der berechneten Ergebnisse sind durch yk = (a + b)c(1 + εk), k = 1, 2,gegeben. Bestimmen Sie die relativen Fehler beider Berechnungsvorschriften in linearer Näherung! Wannist eine wesentlich genauer als die andere? ♦

c�20

16Tor

sten

Linß,

FernU

niin

Hagen

1.3. RUNDUNGSFEHLEREINFLUSS UND FEHLERFORTPFLANZUNG 11

1.3 Rundungsfehlereinfluss und Fehlerfortpflanzung

Wir beginnen diesen Abschnitt mit einem Beispiel.

1.3.1 Numerische Differentiation

Eine der grundlegenden Aufgaben der numerischen Mathematik ist die näherungweise Berech-nung der Ableitung einer Funktion, die zwar nicht explizit bekannt, aber z.B. mittels eines Algo-rithmus auswertbar ist. Eine ähnliche Aufgabenstellung ist die Bestimmung der Beschleunigungeines Körpers aus einer gegebenen Messreihe seiner Geschwindigkeit.

Definitionsgemäß gilt für eine Funktion f ∈ C1(a, b)

f ′(x) = limh→0

f (x + h) − f (x)

h, x ∈ (a, b).

Eine naheliegende Idee ist nun, für ein hinreichend kleines h > 0 den Quotienten

�

δh f�

(x) ≔f (x + h) − f (x)

h(1.6)

als eine Approximation für f ′(x) zu verwenden. Die Sinnhaftigkeit dieses Zugangs wird durchfolgenden Satz abgesichert, der eine Aussage über den auftretenden Approximationsfehler trifft.

Satz 1.3.1. Seien f ∈ C2[a, b], a < b, und M ≔ maxξ∈[a,b]

| f ′′(ξ)|. Dann gilt

��

δh f�

(x) − f ′(x)�� ≤ M

2|h|

für alle x ∈ [a, b] und h � 0 mit x + h ∈ [a, b].

Beweis. Seien x und x+h wie in den Voraussetzungen des Satzes. Dem Satz von Taylor5 zufolgeexistiert ein ξ zwischen x und x + h mit

f (x + h) = f (x) + h f ′(x) +h2

2f ′′(ξ).

Wir dividieren durch h � 0 und bilden die Beträge:

��

δh f�

(x) − f ′(x)�� =|h|2| f ′′(ξ)| .

Es folgt die Behauptung des Satzes, da | f ′′(ξ)| ≤ M. �

5Brook Taylor *18.8.1685 (Edmonton, Middlesex, England), †29.12.1731 (Somerset House, London, England)

c�20

16Tor

sten

Linß,

FernU

niin

Hagen


Der Fehler bei der näherungsweisen Berechnung der ersten Ableitung (einer zweimal stetig dif-ferenzierbaren Funktion) gemäß (1.6) ist (im schlechtesten Fall) proportional zu h. Wir wollendies an einem konkreten Beispiel illustrieren. Unser Vorgehen dabei ist typisch für die numeri-sche Mathematik: ein Verfahren/Algorithmus wird an einer Testaufgabe erprobt, dessen Lösungbekannt ist.

Zu berechnen sei die Ableitung der Exponentialfunktion exp : x �→ ex an der Stelle x = 1. DieAbleitung der Exponentialfunction ist natürlich bekannt:

exp′(1) = exp(1) ≈ 2.718281828459045.

Wir approximieren exp′(1) durch�

δh exp�

(1) mit h = 10−1, 10−2, . . . , 10−15. Zu diesem Zweckhaben wir ein kleines Programm geschrieben, das uns auf einem handelsüblichen Rechner aus-geführt Tabelle 1.2 liefert.

h (δh exp)(1) Fehler10−1 2.858841954873883 1.406 · 10−1

10−2 2.731918655787124 1.364 · 10−2

10−3 2.719641422533225 1.360 · 10−3

10−4 2.718417747082924 1.359 · 10−4

10−5 2.718295419956717 1.359 · 10−5

10−6 2.718283187430615 1.359 · 10−6

10−7 2.718281968405734 1.399 · 10−7

10−8 2.718281821856294 6.603 · 10−9

10−9 2.718282043900899 2.154 · 10−7

10−10 2.718283376168529 1.548 · 10−6

10−11 2.718314462413218 3.263 · 10−5

10−12 2.718714142702083 4.323 · 10−4

10−13 2.717825964282383 4.559 · 10−4

10−14 2.708944180085382 9.338 · 10−3

10−15 3.108624468950438 3.903 · 10−1

Tabelle 1.2: Approximation der Ableitung von exp durch δh; korrekte Stellen unterstrichen

Zunächst beobachten wir, dass im Einklang mit Satz 1.3.1 für h = 10−1, . . . , 10−8 der Fehler pro-portional zu h ist, und die Güte der Approximation mit kleiner werdendem h zunimmt. Bei wei-terer Verkleinerung von h ist jedoch eine signifikante Verschlechterung zu beobachten. Auf denersten Blick widerspricht dies Satz 1.3.1.

Dieser Widerspruch ist aber nur ein scheinbarer, denn der Beweis von Satz 1.3.1 geht davon aus,dass mit reellen Zahlen gerechnet wird. Unser Programm arbeitet aber mit Gleitkommazahlen!Dadurch ist die Berechnung von

�

δh f�

(x) mit Rundungsfehlern behaftet:

f ′(x) ≈ �δh f�

(x) ≈�

f◦(rd(x) ⊕ rd(h)) ⊖ f◦(rd(x))�

⊘ rd(h).

Rundungsfehler treten auf

c�20

16Tor

sten

Linß,

FernU

niin

Hagen


• bei der Repräsentation von x und h durch Gleitkommazahlen,

• bei der Addition von x und h,

• bei der Auswertung von f

• bei der Subtraktion im Zähler sowie

• bei der Division durch h.

Exemplarisch wollen wir lediglich den Einfluss der fehlerbehafteten Auswertung von f analy-sieren. Vereinfachend nehmen wir daher an, dass x, h und x + h exakt durch Gleitkommazahlenrepräsentiert werden, und auch die Division durch h exakt ausgeführt wird. (Die hierbei auf-tretenden Fehler können in der Tat vernachlässigt werden.) Mit diesen vereinbarten Annahmengilt

f ′(x) − f◦(x + h) − f◦(x)

h= f ′(x) − (1 + ε1) f (x + h) − (1 + ε2) f (x)

h

mit relativen Fehlern bei der Auswertung von f entsprechend (1.5):

|ε1| , |ε2| ≤ Kf eps . (1.7)

Den Zähler des zweiten Bruches auf der rechten Seite multiplizieren wir aus und erhalten für denGesamtfehler:

f ′(x) − f◦(x + h) − f◦(x)

h= f ′(x) − �δh f

�

(x)��

Approximationsfehler

+ε1 f (x + h) − ε2 f (x)

h��

Rundungsfehler

,

Den Approximationsfehler schätzen wir mit Hilfe von Satz 1.3.1 ab, für den Rundungsfehlerverwenden wir (1.7):

��f ′(x) − f◦(x + h) − f◦(x)

h

��≤ M |h|

2+

2eps

|h| Kf maxx∈[a,b]

| f (x)| . (1.8)

Diese detailliertere Untersuchung zeigt den Einfluss der Rundungsfehler. Für kleiner werden-des h wird zwar der Approximationsfehler kleiner, aber die Rundungsfehler aus der Arbeit mitGleitkommazahlen werden verstärkt. Abbildung 1.6 illustriert die Situation.

Eine gute Wahl von h zeichnet sich dadurch aus, dass Approximations- und Rundungsfehler aufder rechten Seite von (1.8) die gleiche Größenordnung besitzen. Das ist der Fall, wenn

h ≈ epsh,

woraus sich h∗ ≈ √eps ergibt. Durch Einsetzen von h∗ in (1.8) erhalten wir für den Gesamtfehler��f ′(x) − f◦(x + h∗) − f◦(x)

h∗

��≤ Mf

√eps

c�20

16Tor

sten

Linß,

FernU

niin

Hagen


Abbildung 1.6: Fehlerkomponenten bei der numerischen Differentiation

mit einer (i. Allg. unbekannten) Konstante Mf , die von f , f ′′ und möglicherweise auch vonverwendeten Programmbibliotheken abhängt.

In obigem Beispiel hat unser Computer mit doppelter Genauigkeit gerechnet. Für diese isteps ≈ 1.110 · 10−16. Eine gute Wahl ist dementsprechend h∗ ≈ 10−8. Für diese Wert von h habenwir in Tabelle 1.2 auch die genaueste Approximation der Ableitung erhalten. Der Gesamtfehlerliegt bei

√eps ≈ 10−8.

Das Ergebnis ist etwas ernüchternd. Bei der näherungsweisen Berechnung der Ableitung mit-tels (1.6) sind lediglich die ersten 8 Dezimalstellen korrekt, obwohl unser Computer mit 16Dezimalstellen arbeitet.

Aufgabe 1.3.2. Untersuchen Sie den symmetrischen Differenzenquotienten

f ′(x) ≈ �δ∗h f�

(x) ≔f (x + h) − f (x − h)

2h, h > 0.

Zeigen Sie: Ist f ∈ C3[a, b], a < b, und x ± h ∈ (a, b), dann gilt für den Approximationsfehler��

δ∗h f�

(x) − f ′(x)�� ≤ Mh2

mit einer Konstante M ≥ 0. Bestimmen Sie M.

Analysieren Sie den Rundungsfehlereinfluss bei Arbeit mit Maschinengenauigkeit eps. Für welches h isteine hohe Approximationsgüte zu erwarten? Wie groß ist der zu erwartende Fehler? ♦

1.3.2 Kondition von Aufgaben

Gegeben sei die Aufgabe, aus einem Satz von Eingangsdaten x1, . . . , xn ∈ R ein Resultat z ∈ Rentsprechend der Vorschrift

z = f (x1, . . . , xn)

c�20

16Tor

sten

Linß,

FernU

niin

Hagen


zu berechnen. Wir interessieren uns dafür, den Einfluss von Fehlern in den Eingangsdaten aufdas Resultat abzuschätzen. Störungen der Eingangsdaten resultieren z.B. aus der Verwendungvon Gleitkommazahlen oder von mit Messfehlern behafteten Daten.

Mit dieser Fragestellung hatten wir uns an einem einfachen Beispiel bereits im Abschnitt 1.1beschäftigt, wo das Volumen einer Pyramide zu berechnen war. Wir wollen das Vorgehen jetztverallgemeinern und formalisieren.

Bemerkung 1.3.3. An dieser Stellen müssen wir klar trennen zwischen der Aufgabe und einerkonkreten Berechnungsvorschrift zu ihrer Lösung auf einem Computer. Durch die Arbeit mitGleitkommazahlen werden im Laufe der Rechnung Rundungsfehler eingeführt, die bei einerschlechten Berechnungsvorschrift das Resultat ungünstig verfälschen können, wie wir es z.B.schon in Aufgabe 1.2.9 beobachtet haben.

Dem Einfluss von Rundungsfehlern bei der Berechnung von f und der Analyse von Berech-nungsvorschriften/Algorithmen werden wir uns in §1.3.3 widmen.

Um uns das Studium der Fehlerfortpflanzung zu erleichtern, nehmen wir an, dass die Funktionf : Rn → R in einer hinreichend großen Umgebung von (x1, . . . , xn) zweimal stetig differenzier-bar ist. Dies gestattet uns eine Taylorentwicklung bis zum quadratischen Glied.

Die betrachteten Daten fassen wir zu dem Datenvektor

x ≔ (x1, . . . , xn)T ,

zusammen. Die mit Fehlern behafteten Daten seien

x ≔ (x1, . . . , xn)T .

Definitionsgemäß ist der absolute Fehler

Δx ≔ (Δx1 , . . . ,Δxn)T = x − x.

Die relativen Fehler der einzelnen Komponenten sind

εxi ≔Δxi

|xi|, i = 1, . . . , n.

Uns interessiert der Einfluss von Δx auf den Fehler Δz ≔ z − z im Resultat. Dabei ist z = f (x) derexakte Funktionswert, während sich z = f (x) aus der Berechnung mit dem gestörten Argumentergibt.

Wir definieren die Hilfsfunktionen

ξ : [0, 1]→ Rn : t �→ ξ(t) ≔ x + tΔx (1.9a)

und

ϕ : [0, 1]→ R : t �→ ϕ(t) ≔ f�

ξ(t)�

. (1.9b)

c�20

16Tor

sten

Linß,

FernU

niin

Hagen


Diese ist so definiert, dass ϕ(0) = f (x) und ϕ(1) = f (x), was die Fehlerdarstellung

Δz = z − z = f (x) − f (x) = ϕ(1) − ϕ(0)

gestattet. Dem Satz von Taylor zufolge existiert ein τ ∈ (0, 1) mit

ϕ(1) = ϕ(0) + ϕ′(0) · (1 − 0) +(1 − 0)2

2ϕ′′(τ).

Damit folgt

Δz = ϕ′(0) +

1

2ϕ′′(τ). (1.10)

Wir müssen nun die Ableitungen von ϕ auf jene von f zurückführen. Dazu lösen wir die folgendeÜbungsaufgabe.

Aufgabe 1.3.4. Beweisen Sie: Für die gemäß (1.9) definierte Funktion ϕ gilt

ϕ′(t) = ∇ f�

ξ(t)�TΔx =

n�

i=1

∂ f

∂xi

�

ξ(t)�

Δxi

und

ϕ′′(t) = ΔTx Hf�

ξ(t)�

Δx =

n�

i=1

n�

j=1

∂2 f

∂xi∂x j

�

ξ(t)�

ΔxiΔx j ,

dabei sind ∇ f und Hf der Gradient bzw. die Hesse6-Matrix von f . ♦

Wir wenden die Ergebnisse der Übungsaufgabe auf (1.10) an, und erhalten für den Fehler von z

Δz =

n�

i=1

∂ f

∂xi(x)Δxi +

1

2

n�

i=1

n�

j=1

∂2 f

∂xi∂x j

�

ξ(τ)�

ΔxiΔx j , τ ∈ (0, 1).

Wie im Abschnitt 1.1 nehmen wir an, dass die Fehler Δxi klein sind und somit Produkte ΔxiΔx j

vernachlässigt werden können. Für den Fehler von z erhalten wir also in linearer Näherung

Δz �

n�

i=1

∂ f

∂xi(x)Δxi . (1.11)

Die Zahl σi ≔∂ f∂xi

(x) gibt in erster Näherung an, um welchen Faktor verstärkt (oder gedämpft)der absolute Fehler Δxi der i-ten Komponente des Datenvektors in den absoluten Fehler Δz desResultates eingeht.

6Ludwig Otto Hesse, *22.4.1811 (Königsberg, Preussen) †4.8.1874 (München, Deutschland)

c�20

16Tor

sten

Linß,

FernU

niin

Hagen


Von größerer Bedeutung für uns ist – insbesondere mit Blick auf die Gleitkommazahlen, dieRepräsentanten reeller Zahlen mit gewissen relativen Genauigkeiten sind – der Zusammenhangzwischen relativen Fehlern in den Eingangsdaten und im Ergebnis.

Wir dividieren (1.11) durch z = f (x):

εz =Δz

z�

n�

i=1

xi

f (x)

∂ f

∂xi(x)Δxi

xi=

n�

i=1

xi

f (x)

∂ f

∂xi(x) εxi .

Der relative Fehler in xi geht also um den Faktor

xi

f (x)

∂ f

∂xi(x)

verstärkt in den relativen Fehler des Ergebnisses ein.

Definition 1.3.5. Gegeben sei die Aufgabe z = f (x) für ein x ∈ Rn zu berechnen. Die Größe

κi ≔xi

f (x)

∂ f

∂xi(x) , i = 1, . . . , n,

wird als Konditionszahl der Aufgabe bezüglich der i-ten Komponente des Datenvektors (oderbezüglich des i-ten Argumentes) bezeichnet.

Man beachte, dass im Vergleich zu den σi neben den partiellen Ableitungen von f auch die Fak-toren xi/ f (x) auftreten. Diese sind besonders ungünstig, wenn ein betragsmäßig kleines Resultataus betragsmäßig großen Daten zu berechnen ist. Die Größen κi sind unabhängig vom Maßstab,in dem Daten und Resultat gemessen werden. Das gibt den Konditionszahlen eine hervorragendeBedeutung beim Arbeiten mit Gleitkommazahlen. Tritt eine betragsmäßig große Konditionszahlκi auf, so wirkt sich der relative Fehler εi in der i-ten Komponente des Datenvektors sehr ungüns-tig auf den relativen Fehler des Resultats aus.

Bemerkung 1.3.6. Eine Aufgabe mit (mindestens) einer betragsmäßig großen Konditionszahlwird als schlecht konditioniert bezeichnet. Man spricht auch von der natürlicher Instabili-tät der Aufgabe. Sind alle Konditionszahlen moderat, so spricht man hingegen von einer gutkonditionierten Aufgabe.

Der Übergang von „gut konditioniert“ zu „schlecht konditioniert“ ist fließend. Entscheidend ist,ob in einer bestimmten Anwendung die Verstärkung der relativen Fehler um einen gewissenFaktor akzeptiert werden kann oder nicht.

Wir analysieren exemplarisch die Grundrechenarten.

Beispiel 1.3.7. Multiplikation: Gegeben ist die Aufgabe, das Produkt z zweier reeller Zahlen x1

und x2 zu berechnen. Der Zusammenhang zwischen Ergebnis und Eingangsdaten ist gegebendurch

z = f (x1, x2) = x1x2.

c�20

16Tor

sten

Linß,

FernU

niin

Hagen


Die Konditionszahl κ1 bezüglich des ersten Argumentes ist

κ1 =x1

f (x1, x2)

∂ f

∂x1(x1, x2) =

x1

x1x2x2 = 1.

Völlig analog erhalten wir κ2 = 1. Die Multiplikation zweier Zahlen ist gut konditioniert. ♠

Beispiel 1.3.8. Division: Zu berechnen ist

z = f (x1, x2) =x1

x2, x2 � 0.

Für die Konditionszahlen erhalten wir

κ1 =x1

f (x1, x2)

∂ f

∂x1(x1, x2) =

x1x1

x2

1

x2= 1

sowie

κ2 =x2

f (x1, x2)

∂ f

∂x2(x1, x2) =

x2x1

x2

−x1

x22

= −1.

Die Division zweier Zahlen ist ebenfalls gut konditioniert. ♠

Beispiel 1.3.9. Addition, Subtraktion: Zu berechnen ist

z = f (x1, x2) = x1 + x2.

Die Konditionszahlen sind

κ1 =x1

f (x1, x2)

∂ f

∂x1(x1, x2) =

x1

x1 + x2und κ2 =

x2

f (x1, x2)

∂ f

∂x2(x1, x2) =

x2

x1 + x2.

Diese werden groß, wenn (x1 + x2) betragsmäßig wesentlich kleiner als x1 bzw. x2 ist. Mit ande-ren Worten, wird die Differenz zweier etwa gleichgroßer Zahlen berechnet (also x1 ≈ −x2), isteine signifikante Verstärkung von Rundungsfehlern zu erwarten. ♠

Der u.U. schlechten Kondition der Subtraktion sind wir bereits bei der numerischen Differentia-tion im Abschnitt 1.3.1 begegnet. Dort wurde gemäß

exp′(1) ≈ e1+h − e1

h

eine Approximation der ersten Ableitung berechnet. Wir wollen bei 16stelliger Genauigkeit dieBerechnung der Differenz im Zähler für h = 10−8 detailliert nachvollziehen.

e1+h = x1 2.718 281 855 641 863e1 = x2 2.718 281 828 459 045

e1+h − e1 = z 0.000 000 027 182 818 = 2.718 281 800 000 000 · 10−8

c�20

16Tor

sten

Linß,

FernU

niin

Hagen


Wir beobachten bei der Berechnung der Differenz einen „Verlust“ der letzten 8 Mantissenstel-len. Dieser Effekt, der bei der Subtraktion zweier annähernd gleicher Zahlen auftritt, wird alsStellenauslöschung bezeichnet. Er muss – falls möglich – vermieden werden.

Beispiel 1.3.10. Wurzelfunktion. Zu berechnen sei z = f (a) =√

a, a ≥ 0. Die Konditionszahldieser Aufgabe ist

κ =a

f (a)f ′(a) =

a√

a

1

2√

a=

1

2.

Die Aufgabe ist gut konditioniert. ♠

Beispiel 1.3.11. Lösung quadratischer Gleichungen. Vorgelegt sei die Aufgabe, bei gegebenenp, q > 0, q ≪ p2,

λ = ϕ(p, q) = p −�

p2 − q

zu berechnen. Es handelt sich dabei um eine der Lösungen von λ2 − 2pλ+ q = 0. Auf den erstenBlick scheint hier eine kritische Subtraktion aufzutreten, da

�

p2 − q ≈ p, weshalb man Stellen-auslöschung erwarten könnte. Allerdings stehen Minuend und Subtrahend in einem Zusammen-hang. Sie sind also nicht unabhängig voneinander mit Rundungsfehlern behaftet. Es bedarf dahereiner genaueren Untersuchung.

Wir bestimmen zunächst die Konditionszahl der Aufgabe bezüglich p:

κ1 =p

ϕ(p, q)

∂ϕ

∂p(p, q) =

p

p −�

p2 − q

1 −p

�

p2 − q

=−p�

p2 − q≈ −1,

da�

p2 − q ≈ p für q ≪ p2.

Für die Konditionszahl bezüglich q gilt

κ2 =q

ϕ(p, q)

∂ϕ

∂q(p, q) =

q

p −�

p2 − q

1

2�

p2 − q=

p +�

p2 − q

2�

p2 − q,

wobei wir bei der letzten Umformung

λ = ϕ(p, q) = p −�

p2 − q =q

p +�

p2 − q(1.12)

verwendet haben (Vieta7scher Wurzelsatz). Es folgt

κ2 =p +�

p2 − q

2�

p2 − q≈ 1, für q ≪ p2.

Beide Konditionszahlen sind in etwa 1. Die Aufgabe ist somit gut konditioniert. ♠7François Viète (latinisiert Vieta), *1540 (Fontenay-le-Comte, Poitou (jetzt Vendée), Frankreich), †13.12.1603

(Paris, Frankreich)

c�20

16Tor

sten

Linß,

FernU

niin

Hagen


1.3.3 Kondition von Algorithmen

Die natürliche Stabilität (oder Instabilität) ist eine Eigenschaft der gegebenen Aufgabe. Sie hängtnur von der vorgelegten Aufgabe ab, aber nicht von dem für die Berechnung gewählten Algo-rithmus.

In diesem Abschnitt werden wir sehen, dass das Ergebnis einer gut konditionierten Aufgabedurch einen ungeschickt gewählten Algorithmus (Berechnungsmethode) stark verfälscht wer-den kann, also ein Verlust an Genauigkeit eintritt. In diesem Fall spricht man von numerischerInstabilität. Sie ist eine Eigenschaft des Algorithmus und hängt vom gewählten Rechnungsver-lauf ab, bei dem Rundungsfehler in einzelnen Berechnungsschritten unter Umständen erheblichverstärkt werden können.

Um unser weiteres Vorgehen zu motivieren kommen wir zurück auf Beispiel 1.3.11, in dem fürgegebene p, q > 0, q ≪ p2,

λ = p −�

p2 − q (1.13)

zu berechnen war. Wir setzen (1.13) direkt in einen Algorithmus um und berechnen nacheinanderdie Zwischenergebnisse

y1 ≔ p · p , y2 ≔ y1 − q und y3 ≔√

y2

sowie das Endergebnis

λ ≔ p − y3.

Wird hierbei mit Gleitkommazahlen gerechnet, werden alle drei Zwischenergebnisse yi mit Feh-lern behaftet sein. Wir müssen uns der Frage stellen, welchen Einfluss diese Fehler auf das End-ergebnis haben. Dazu stellen wir λ in Abhängigkeit von den yi dar und analysieren anschließendmit unseren Ergebnissen aus Abschnitt 1.3.2 die Fehlerfortpflanzung.

Wir rollen den Algorithmus von hinten auf. Der letzte Berechnungsschritt gibt uns unmittelbardie Abhängigkeit von y3:

λ = p − y3 . (1.14a)

Wir gehen einen Schritt zurück und ersetzen y3 =√

y2 :

λ = p − √y2 , (1.14b)

was uns die Abhängigkeit von y2 liefert. Als nächstes substituieren wir y2 = y1 − q :

λ = p −√

y1 − q . (1.14c)

Wir haben jetzt explizite Darstellungen von λ in Abhängigkeit von den Zwischenergebnisse yi

und können nun mit Hilfe unserer Überlegungen aus §1.3.2 die Frage beantworten, wie sichrelative Fehler in yi auf das Resultat λ auswirken. Oder mit anderen Worten:

c�20

16Tor

sten

Linß,

FernU

niin

Hagen


• Wie ist die Aufgabe, λ gemäß (1.14c) zu berechnen, bezüglich y1 konditioniert?

• Wie ist die Aufgabe, λ gemäß (1.14b) zu berechnen, bezüglich y2 konditioniert?

• Wie ist die Aufgabe, λ gemäß (1.14a) zu berechnen, bezüglich y3 konditioniert?

Wir bestimmen die entsprechenden Konditionszahlen Ki gemäß Definition 1.3.5:

K1 ≔y1

λ

∂λ

∂y1=

y1

λ

−1

2√

y1 − q,

K2 ≔y2

λ

∂λ

∂y2=

y2

λ

−1

2√

y2,

K3 ≔y3

λ

∂λ

∂y3=

y3

λ(−1) .

Man überlegt sich, dass λ, y1, y2, y3 > 0. Ferner folgt aus q ≪ p2,

λ = p −�

p2 − q =q

p +�

p2 − q≈ q

2psowie

√y1 − q ≈ p.

Somit ist

K1 ≈ −p2

q, also |K1| ≈

p2

q≫ 1.

Kleine Fehler in y1 werden also signifikant verstärkt, was alles andere als wünschenswert ist!

Aber woran liegt das? Gehen wir die Schritte des Algorithmus im Einzelnen durch. Bei derBerechnung von y1 werden zwei Zahlen multipliziert. Hier geht nichts schief, vgl. Bsp. 1.3.7.Im nächsten Schritt wird eine kleine Zahl von einer großen subtrahiert. Auch dies kann nichtdie Ursache sein, siehe Bsp. 1.3.9. Zur Berechnung von y3 wird eine Wurzel gezogen. Auch diesist problemlos, wie wir in Bsp. 1.3.10 festgestellt hatten. Es ist der letzte Schritt, bei dem λ alsDifferenz von p und y3 berechnet wird. Da y3 ≈ p tritt hier Stellenauslöschung auf.

Formal können wir dies bestätigen, indem wir die Aufgabe, λ gemäß (1.14a) zu berechnen, be-trachten und ihre Konditionszahl bzgl. y3 untersuchen:

K3 ≈ −2p2

q.

Sie ist betragsmäßig sehr groß. Also spätestens im letzten Schritt werden alle unsere Bemühun-gen, ein genaues Ergebnis zu berechnen, zunichte gemacht.

Die Aufgabe ist gut konditioniert, unser erster Algorithmus, den wir uns ausgedacht haben, aberunbrauchbar. Wir müssen also noch an einer Alternative arbeiten. Bevor wir uns dieser Aufgabezuwenden, wollen wir unserer bisheriges Vorgehen verallgemeinern und formalisieren.

c�20

16Tor

sten

Linß,

FernU

niin

Hagen


Ein Algorithmus zur Berechnung von z = f (x) aus dem Datenvektor x bestehe aus folgendenBerechnungsschritten, bei denen Zwischenergebnisse yi, i = 1, . . . ,N − 1, berechnet werden.

y1 = r1(x)

y2 = r2(x, y1)

y3 = r3(x, y1, y2)...

yN−1 = rN−1(x, y1, y2, . . . , yN−2)

z = rN(x, y1, y2, . . . , yN−1)

Uns interessiert die Frage, wie sich Rundungsfehler im Zwischenergebnis yi auf das Resultat zauswirken.

Zu diesem Zweck betrachten wir yi als Eingabe und stellen uns die Frage, wie die Aufgabe, zaus x sowie y1, . . . , yi zu bestimmen, bezüglich yi konditioniert ist. Diese Aufgabe wird durch diesog. Restabbildung

Ri : (x, y1, . . . , yi) �→ z

beschreiben. Die Restabbildungen werden sukzessive, durch Elimination der Zwischenergebnis-se yN−1, yN−2, . . . , yi+1, aus den Berechnungsvorschriften des Algorithmus bestimmt:

z = RN−1(x, y1, . . . , yN−1) ≔ rN�

x, y1, . . . , yN−1�

= RN−2(x, y1, . . . , yN−2) ≔ RN−1�

x, y1, . . . , yN−2, rN−1(x, y1, . . . , yN−2)�

...

= RN−k(x, y1, . . . , yN−k) ≔ RN−k+1�

x, y1, . . . , yN−k, rN−k+1(x, y1, . . . , yN−k)�

, k < N.

Die Verstärkung oder Abschwächung der relativen Fehler im Zwischenergebnis yi berechnensich, unseren Ergebnissen aus Abschnitt 1.3.2 folgend, gemäß

yi

Ri(x, y1, . . . , yi)

∂Ri

∂yi(x, y1, . . . , yi) =

yi

z

∂Ri

∂yi(x, y1, . . . , yi), i = 1, . . . ,N − 1.

Definition 1.3.12. Die Größen

Ki ≔yi

z

∂Ri

∂yi(x, y1, . . . , yi), i = 1, . . . ,N − 1,

heißen die Konditionszahlen des Algorithmus (bzgl. des Zwischenergebnisses yi).

Bemerkung 1.3.13. Der Algorithmus heißt numerisch stabil, wenn alle Konditionszahlen desAlgorithmus betragsmäßig nicht wesentlich größer sind als die Konditionszahlen der Aufgabe.Ansonsten heißt er instabil.

Wie bei der Kondition von Aufgaben ist der Übergang von „stabil“ zu „instabil“, fließend. Ent-scheidend ist wiederum, in welchem Ausmaß Verstärkungen der relativen Fehler akzeptiert wer-den können.

c�20

16Tor

sten

Linß,

FernU

niin

Hagen


Beispiel 1.3.14. Wir kommen zurück auf unser einführendes Beispiel und analysieren es mit demsoeben hergeleiteten Formalismus. Für gegebene p, q > 0, q ≪ p2, ist also λ = p −

�

p2 − q zuberechnen.

Der Algorithmus ist:

y1 ≔ r1(p, q) = p · p,y2 ≔ r2(p, q, y1) = y1 − q,

y3 ≔ r3(p, q, y1, y2) =√

y2,

λ ≔ r4(p, q, y1, y2, y3) = p − y3.

Offenbar sind λ, y1, y2, y3 > 0.

Zur Untersuchung der Stabilität bestimmen wir zunächst die Restabbildungen:

λ = R3(p, q, y1, y2, y3) = r4(p, q, y1, y2, y3) = p − y3,

= R2(p, q, y1, y2) = R3�

p, q, y1, y2, r3(p, q, y1, y2)�

= p − √y2,

= R1(p, q, y1) = R2�

p, q, y1, r2(p, q, y1)�

= p −√

y1 − q

und berechnen anschließend die Konditionszahlen des Algorithmus

K1 =y1

λ

∂R1

∂y1(p, q, y1) =

y1

λ

−1

2√

y1 − q,

K2 =y2

λ

∂R2

∂y2(p, q, y1, y2) =

y2

λ

−1

2√

y2,

K3 =y3

λ

∂R3

∂y3(p, q, y1, y2, y3) =

y3

λ(−1).

In der gegebenen Situation, also q ≪ p2, gilt

y2 ≈ p2, y3 ≈ p und λ = p −�

p2 − q =q

p +�

p2 − q≈ q

2p

Woraus dann für die Beträge der Konditionszahlen des Algorithmus folgt

|K1| , |K2| ≈p2

q≫ 1 und |K3| ≈

2p2

q≫ 1.

Der Algorithmus ist numerisch instabil und somit unbrauchbar, da eine (hier sogar alle) Kondi-tionszahlen des Algorithmus wesentlich größer als die Konditionszahlen der Aufgabe sind, vgl.Beispiel 1.3.11. Die Ursache liegt – wie bereits diskutiert – in der Subtraktion im letzten Schrittdes Verfahrens, bei der Stellenauslöschung auftritt. ♠

Durch Anwendung des Vietasche Wurzelsatzes kann eine alternative Berechungsvorschrift an-gegeben werden, die numerisch stabil ist. Wir lösen dazu die folgende Übungsaufgabe.

c�20

16Tor

sten

Linß,

FernU

niin

Hagen


Aufgabe 1.3.15. Ausgehend von (1.12) kann zum Berechnen von

λ = p −�

p2 − q =q

p +�

p2 − q, p, q > 0, p2 ≫ q,

der folgende Algorithmus verwendet werden:

y1 ≔ p · p, y2 ≔ y1 − q, y3 ≔√

y2, y4 ≔ p + y3, λ ≔ q/y4.

Bestimmen Sie die Restabbildungen Ri, i = 1, . . . , 4, und berechnen Sie die zugehörigen KonditionszahlenKi, i = 1, . . . , 4, des Algorithmus! Entscheiden Sie, ob der Algorithmus numerisch stabil ist! ♦

c�20

16Tor

sten

Linß,

FernU

niin

Hagen

1.4. LÖSUNGEN DER AUFGABEN 25

1.4 Lösungen der Aufgaben

Lösung 1.1.4.

ΔV = V − V =1

3F · h − 1

3F · h = 1

3

�

(F + ΔF) (h + Δh) − F · h�

=1

3

�

Fh + FΔh + hΔF + ΔFΔh − Fh�

=1

3

�

FΔh + hΔF + ΔFΔh

�

.

♣

Lösung 1.2.2. Wegen b = 2 sind die in der Darstellung möglichen Ziffern gerade 0 und 1. Bei den norma-lisierte Gleitkommazahlen muss die erste Nachkommastelle der Mantisse von 0 verschieden sein. Zudemhat die Mantisse jeweils 3 Nachkommastellen. In untenstehender Tabelle erhalten wir also die erste Spaltealler vorkommenden Mantissen (1. Spalte). Die erste Nachkommastelle hat dabei den Wert 1

2 , die zwei-te den Wert 1

4 und die dritte den Wert 18 . Für eine Mantisse [0.α1α2α3]3 errechnet sich so ein Wert von

α12 +

α24 +

α38 (siehe 2. Spalte).

Für die vorkommenden Exponenten e ∈ {−1, 0, 1, 2} müssen alle Mantissen noch mit 2e multipliziertwerden. Diese Ergebnisse stehen in der dritten bis sechsten Spalte.

m x = α12 +

α24 +

α38 x · 2−1 x · 20 x · 21 x · 22

0.100 12

14

12 1 2

0.101 12 +

18 =

58

516

58

54

52

0.110 12 +

14 =

34

38

34

32 3

0.111 12 +

14 +

18 =

78

716

78

74

72

Sämtliche in der Tabelle aufgeführten Zahlen kommen zudem mit negativem Vorzeichen vor. Zusätzlich

gehört noch die 0 zuM2(3, [−1, 2]). ♣

Lösung 1.2.8. Wir arbeiten in M2(4, [−7, 7]), d.h. mit Basis 2, der Mantissenlänge 4 und dem Exponen-tenbereich −7, . . . , 7. Die beiden Operanden sind

x = [0.1011]2 · 20 = 1 · 2−1 + 0 · 2−2 + 1 · 2−3 + 1 · 2−4

und

y = [0.1100]2 · 20 = 1 · 2−1 + 1 · 2−2 + 0 · 2−3 + 0 · 2−4

z = x ⊖ y :

x − y = −[0.1000]2 · 2−3 ∈ M2(4, [−7, 7]), =⇒ x ⊖ y = x − y = −[0.1000]2 · 2−3.

Die Rechnung wird also exakt ausgeführt.

c�20

16Tor

sten

Linß,

FernU

niin

Hagen


z = (y ⊖ x)10 :

y ⊖ x = [0.1000]2 · 2−3 =⇒ (y ⊖ x)10 = [0.1000]2 · 2−39.

Exponent (−39) ist kleiner als −7, unterschreitet also den Exponentenbereich. Das Ergebnis wird auf 0gerundet: (y ⊖ x)10 = 0. Es findet ein Unterlauf statt

z = x ⊕ y :

x + y = [1.0111]2 · 20� M2(4, [−7, 7]), =⇒ x ⊕ y = [0.1011]2 · 21.

Das Ergebnis ist durch Abschneiden der 5. Mantissenstelle gerundet.

z = y ⊕ (x ⊘ 4) : Zunächst ist x ⊘ 4 = [.1011]2 · 2−2 = x/4, also

y + x ⊘ 4 = [.111011]2 · 20� M2(4, [−7, 7]), =⇒ y ⊕ (x ⊘ 4) = [0.1110]2 · 20.

Das Ergebnis ist durch Abschneiden der 5. und 6. Mantissenstelle gerundet.

z = x ⊕ (y ⊘ 4) : Es ist (y ⊘ 4) = [0.1100]2 · 2−2 = y/4, also

x + y ⊘ 4 = [0.1110]2 · 20 ∈ M2(4, [−7, 7]), =⇒ x ⊕ (y ⊘ 4) = y + x/4 = [0.1110]2 · 20.

Das Ergebnis ist exakt. ♣

Lösung 1.2.9. Sowohl die Multiplikation als auch die Addition von Maschinenzahlen werden mit relati-ven Fehlern kleiner als eps ausgeführt. D.h. für die beiden Berechnungsvorschriften gilt

y1 = (a ⊕ b) ⊗ c = (1 + e1)�

(a ⊕ b)c�

= (1 + e1)(1 + e2)(a + b)c

bzw.

y2 = (a ⊗ c) ⊕ (b ⊗ c) = (1 + e3)�

a ⊗ c + b ⊗ c) = (1 + e3)�

(1 + e4)ac + (1 + e5)bc�

= (1 + e3)

�

(1 + e4)a

a + b+ (1 + e5)

b

a + b

�

(a + b)c

mit |ei| ≤ eps, i = 1, . . . , 5.

Für die relativen Fehler ε1 und ε2 der beiden Ergebnisse erhalten wir

ε1 = e1 + e2 + e1e2 � e1 + e2.

sowie

ε2 = e3 + e4a

a + b+ e5

b

a + b+ e3

�

e4a

a + b+ e5

b

a + b

�

� e3 + e4a

a + b+ e5

b

a + b.

Bei Verwendung der ersten Berechnungsvorschrift addieren sich die Rundungsfehler. Die zweite Berech-nungsvorschrift ist wesentlich ungünstiger falls a ≈ −b, da |a + b| sehr klein ist. Dann sind |a/(a + b)| und|b/(a + b)| sehr groß und die Fehler e4 und e5 werden signifikant verstärkt.

c�20

16Tor

sten

Linß,

FernU

niin

Hagen


Ein Beispiel bei Rechnung auf dem Computer mit doppelter Genauigkeit (eps = 2−52 ≈ 1.1 · 10−16) mögedieses Ergebnis verdeutlichen. Wir wählen die drei Gleitkommazahlen a = 1 − 2−52, b = −1 und c = 3/2.Die relativen Fehler sind ε1 = 0 bzw. ε2 = 1/3 ≫ eps.

Bei der zweiten Berechnungsvorschrift ist der relative Fehler ca. 1015 mal größer als die Maschinenge-

nauigkeit. Das Ergebnis wäre also völlig unbrauchbar. ♣

Lösung 1.3.2. Seien x ∈ (a, b) beliebig und h > 0 hinreichend klein, so dass x ± h ∈ [a, b]. Nach Taylorexistieren ein ξ− ∈ [x − h, x] und ein ξ+ ∈ [x, x + h] mit

f (x − h) = f (x) − h f ′(x) +h2

2f ′′(x) − h3

6f ′′′(ξ−)

und

f (x + h) = f (x) + h f ′(x) +h2

2f ′′(x) +

h3

6f ′′′(ξ+).

Es folgt

�

δ∗h f�

(x) − f ′(x) =h2

12

�

f ′′′(ξ+) + f ′′′(ξ−)�

Setze M ≔ 16 maxξ∈[a,b]

| f ′′′(ξ)|. Wir erhalten für den Approximationsfehler

��

δ∗h f�

(x) − f ′(x)�� ≤ Mh2.

Zur Analyse des Rundungsfehlereinflusses verfahren wir wie bei der Herleitung von (1.8) :

f ′(x) − f◦(x + h) − f◦(x − h)

2h= f ′(x) − �δ∗h f

�

(x) +ε1 f (x + h) − ε2 f (x − h)

2h,

woraus die Abschätzung

��f ′(x) − f◦(x + h) − f◦(x − h)

2h

��≤ Mh2 +

eps

hK f max

x∈[a,b]| f (x)|

folgt.

Eine gute Wahl von h ergibt sich wieder, wenn beide Fehlerterme die gleiche Größe besitzen, d.h.

h2 ≈ epsh

⇐⇒ h∗ = eps1/3.

Das zugehörige Fehlerniveau bei der Approximation der ersten Ableitung ist eps2/3.

Bei Rechnung mit doppelter Genauigkeit, also eps ≈ 1.1 · 10−16, ist h∗ ≈ 4.8 · 10−6 mit Fehlerniveau vonungefähr 2.3 · 10−11.

Insgesamt eine signifikante Verbesserung im Vergleich zur Verwendung der einseitigen Differenz δh im

Abschnitt 1.3.1. Man beachte aber, dass eine höhere Regularität (Differenzierbarkeit) erforderlich ist. ♣

c�20

16Tor

sten

Linß,

FernU

niin

Hagen


Lösung 1.3.4. ξ(t) = x + tΔx =⇒ ξ′(t) = Δx, also ξ′i (t) = Δxi , i = 1, . . . , n.

Wir wenden die Kettenregel auf ϕ an:

ϕ(t) = f�

ξ(t)�

ϕ′(t) =n�

i=1

∂ f

∂xi

�

ξ(t)�

ξ′i (t)

=

n�

i=1

∂ f

∂xi

�

ξ(t)�

Δxi = ∇ f�

ξ(t)�TΔx

ϕ′′(t) =n�

i=1

d

dt

�

∂ f

∂xi

�

ξ(t)�

Δxi

�

=

n�

i=1

n�

j=1

∂

∂x j

�

∂ f

∂xi

�

ξ(t)�

Δxi

�

ξ′j(t)

=

n�

i=1

n�

j=1

∂2 f

∂xi∂x j

�

ξ(t)�

ΔxiΔξ j = ΔTx Hf�

ξ(t)�

Δx

♣

Lösung 1.3.15. Algorithmus:

y1 = r1(p, q) = p · p,y2 = r2(p, q, y1) = y1 − q,

y3 = r3(p, q, y1, y2) =√

y2,

y4 = r4(p, q, y1, y2, y3) = p + y3,

λ = r5(p, q, y1, y2, y3, y4) = q/y4.

Offenbar sind λ, y1, y2, y3 > 0.

Die Restabbildungen sind:

λ = R4(p, q, y1, y2, y3, y4) = r5(p, q, y1, y2, y3, y4) = q/y4,

= R3(p, q, y1, y2, y3) = R4�

p, q, y1, y2, y3, r4(p, q, y2, y3)�

= q/(p + y3),

= R2(p, q, y1, y2) = R3�

p, q, y1, y2, r3(p, q, y1, y2)�

= q/(p +√

y2),

= R1(p, q, y1) = R2�

p, q, y1, r2(p, q, y1)�

= q/(p +√

y1 − q)

Die Konditionszahlen des Algorithmus sind

K1 =y1

λ

∂R1

∂y1(p, q, y1) =

y1

λ

−q

(p +√

y1 − q)2

1

2√

y1 − q= − y1q

2λy3y24

,

K2 =y2

λ

∂R2

∂y2(p, q, y1, y2) =

y2

λ

−q

(p +√

y2)2

1

2√

y2= − y3q

2λy24

,

K3 =y3

λ

∂R3

∂y3(p, q, y1, y2, y3) =

y3

λ

−q

(p + y3)2= −y3q

λy24

,

K4 =y4

λ

∂R4

∂y4(p, q, y1, y2, y3, y4) =

y4

λ

−q

y24

= − q

λy4

c�20

16Tor

sten

Linß,

FernU

niin

Hagen


In der gegebenen Situation, also q ≪ p2, gilt

y2 ≈ p2, y3 ≈ p, y4 ≈ 2p und λ ≈ q

2p

Woraus für die Konditionszahlen des Algorithmus

|K1| , |K2| ≈1

4, |K3| ≈

1

2sowie |K4| ≈ 1

folgt. Die Konditionszahlen des Algorithmus besitzen die gleiche Größenordnung wie die der Aufgabe.

Der Algorithmus ist damit numerisch stabil. ♣

c�20

16Tor

sten

Linß,

FernU

niin

Hagen


c�20

16Tor

sten

Linß,

FernU

niin

Hagen

Inhaltsverzeichnis

1 Fehleranalyse und Computerzahlen 11.1 Absoluter und relativer Fehler . . . . . . . . . . . . . . . . . . . . . . . . . . . 31.2 Maschinenarithmetik . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

1.2.1 Gleitkommazahlen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51.2.2 Rundung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61.2.3 Grundoperationen und elementare Funktionen . . . . . . . . . . . . . . . 9

1.3 Rundungsfehlereinfluss und Fehlerfortpflanzung . . . . . . . . . . . . . . . . . . 111.3.1 Numerische Differentiation . . . . . . . . . . . . . . . . . . . . . . . . . 111.3.2 Kondition von Aufgaben . . . . . . . . . . . . . . . . . . . . . . . . . . 141.3.3 Kondition von Algorithmen . . . . . . . . . . . . . . . . . . . . . . . . 20

1.4 Lösungen der Aufgaben . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

2 Vektorräume und Matrizen 312.1 Norm und normierte Vektorräume . . . . . . . . . . . . . . . . . . . . . . . . . 312.2 Skalarprodukt und unitäre Vektorräume . . . . . . . . . . . . . . . . . . . . . . 342.3 Orthogonalität . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 372.4 Normen von linearen Abbildungen und Matrizen . . . . . . . . . . . . . . . . . 41

2.4.1 Lineare Abbildungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . 422.4.2 Matrizen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 452.4.3 Das Störungslemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

2.5 Dreiecks-, Permutations- und spezielle Matrizen . . . . . . . . . . . . . . . . . . 492.6 Unitäre und orthogonale Matrizen . . . . . . . . . . . . . . . . . . . . . . . . . 522.7 Lösungen der Aufgaben . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

3 Lineare Gleichungssysteme 653.1 Kondition linearer Gleichungssysteme . . . . . . . . . . . . . . . . . . . . . . . 653.2 Direkte Verfahren für lineare Gleichungssysteme . . . . . . . . . . . . . . . . . 693.3 Gausselimination und LR-Faktorisierung . . . . . . . . . . . . . . . . . . . . . . 71

3.3.1 Eliminationsstrategie . . . . . . . . . . . . . . . . . . . . . . . . . . . . 723.3.2 Die LR-Faktorisierung . . . . . . . . . . . . . . . . . . . . . . . . . . . 743.3.3 Der Gauss-Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . . . 753.3.4 Pivot-Strategien . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 763.3.5 Aufwand des Verfahrens . . . . . . . . . . . . . . . . . . . . . . . . . . 78

i

c�20

16Tor

sten

Linß,

FernU

niin

Hagen

ii INHALTSVERZEICHNIS

3.4 Das Cholesky-Verfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 793.5 Tridiagonale Matrizen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84

3.5.1 Der Thomas-Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . . . 853.5.2 Zyklische Reduktion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85


4 Lineare Quadratmittelprobleme 934.1 Die Normalgleichungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 934.2 QR-Zerlegung und Quadratmittelprobleme . . . . . . . . . . . . . . . . . . . . . 974.3 Das Householder-Verfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1004.4 Lösungen der Aufgaben . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107

5 Polynome 1095.1 Polynome und Monome . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109

5.1.1 Der Vektorraum der Polynome . . . . . . . . . . . . . . . . . . . . . . . 1105.1.2 Polynommultiplikation und -division . . . . . . . . . . . . . . . . . . . 1125.1.3 Euklidischer Divisionsalgorithmus . . . . . . . . . . . . . . . . . . . . 1145.1.4 Das Horner-Verfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . 114

5.2 Tschebyscheff-Polynome . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1175.3 Orthogonale Polynome . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121

5.3.1 Der Orthogonalitätsbegriff für Polynome . . . . . . . . . . . . . . . . . 1215.3.2 Dreigliedrige Rekursionen für orthogonale Polynome . . . . . . . . . . . 1255.3.3 Der Clenshaw-Algorithmus zur Polynomauswertung . . . . . . . . . . . 1295.3.4 Nullstellen orthogonaler Polynome . . . . . . . . . . . . . . . . . . . . 131


6 Polynominterpolation 1436.1 Lineare Interpolation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1446.2 Die Lagrangesche Form des Interpolationspolynoms . . . . . . . . . . . . . . . 1466.3 Die Newtonsche Form des Interpolationspolynoms . . . . . . . . . . . . . . . . 1496.4 Auswertung des Interpolationspolynoms . . . . . . . . . . . . . . . . . . . . . . 153

6.4.1 Das Verfahren von Aitken und Neville . . . . . . . . . . . . . . . . . . 1536.4.2 Das modifizierte Horner-Schema . . . . . . . . . . . . . . . . . . . . . 155

6.5 Der Interpolationsfehler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1566.6 Hermite-Interpolation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1596.7 Rundungsfehlereinfluss . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1606.8 Das Runge-Phänomen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1626.9 Optimierung der Stützstellen . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1636.10 Lösungen der Aufgaben . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167

7 Quadratur 1697.1 Riemann-Summen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1697.2 Interpolatorische Quadraturformeln . . . . . . . . . . . . . . . . . . . . . . . . 172

c�20

16Tor

sten

Linß,

FernU

niin

Hagen

INHALTSVERZEICHNIS iii

7.2.1 Einfache Quadraturformeln . . . . . . . . . . . . . . . . . . . . . . . . 1727.2.2 Summierte Quadraturformeln . . . . . . . . . . . . . . . . . . . . . . . 1767.2.3 Der Quadraturfehler . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179

7.3 Gauss-Legendre-Formeln . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1857.4 Extrapolation und Romberg-Verfahren . . . . . . . . . . . . . . . . . . . . . . . 191

7.4.1 Richardson-Extrapolation . . . . . . . . . . . . . . . . . . . . . . . . . 1917.4.2 Das Romberg-Verfahren . . . . . . . . . . . . . . . . . . . . . . . . . . 194


8 Nichtlineare Gleichungen 2018.1 Banachscher Fixpunktsatz und Fixpunktiteration . . . . . . . . . . . . . . . . . 2028.2 Konvergenzgeschwindigkeit . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2068.3 Nullstellenaufgaben für Funktionen einer Veränderlichen . . . . . . . . . . . . . 207

8.3.1 Bisektion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2078.3.2 Das Newton-Verfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . 2098.3.3 Das Sekantenverfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . 211

8.4 Das Newton-Verfahren für Gleichungssysteme . . . . . . . . . . . . . . . . . . 2148.4.1 Grundidee des Verfahrens . . . . . . . . . . . . . . . . . . . . . . . . . 2148.4.2 Konvergenz des Newton-Verfahrens . . . . . . . . . . . . . . . . . . . . 2168.4.3 Gedämpfte Newton-Verfahren . . . . . . . . . . . . . . . . . . . . . . . 219


c�20

16Tor

sten

Linß,

FernU

niin

Hagen

iv INHALTSVERZEICHNIS

Documents

Kurs 01270 Numerische Mathematik - FernUniversität Hagen€¦ · 1.2. MASCHINENARITHMETIK 5 1.2.1 Gleitkommazahlen Für technisch-wissenschaftliche Anwendungen – so auch in der