Prof. Thomas Richter 15. Juni 2017Institut für Analysis und NumerikOtto-von-Guericke-Universität Magdeburgthomas.richter@ovgu.de

Material zur Vorlesung Algorithmische Mathematik II am 15.06.2017

Lineare Gleichungssysteme, Störungstheorie

1 Konditionierung numerischer ProblemeNumerische Lösungen sind oft mit Fehlern behaftet. Fehlerquellen sind zahlreich: DieEingabe kann mit einem Messfehler versehen sein, ein approximatives Verfahren wirddie Lösung nicht exakt berechnen, sondern nur annähern, manche Aufgaben könnennurmithilfe eines Computers oder Taschenrechners gelöstwerden und so ist die Lösungmit Rundungsfehlern versehen. Wir definieren:

Folie 1

Definition 1 (Fehler). Sei x ∈ R die Approximation einer Größe x ∈ R. Mit |δx| = |x−x|bezeichnen wir den absoluten Fehler und mit |δx|/|x| den relativen Fehler.

Üblicherweise ist die Betrachtung des relativen Fehlers von größerer Bedeutung: Dennein absoluter Messfehler von 100m ist klein, wenn man den Abstand zwischen Erdeund Sonne zu bestimmen versucht, jedoch groß, wenn der Abstand zwischen Mensaund Mathematikgebäude gemessen werden soll.Bei der Analyse von numerischen Verfahren spielen Fehler, insbesondere die Fortpflan-zung von Fehlern, eine entscheidende Rolle. Wir betrachten ein Beispiel:

Beispiel 1 (Größenbestimmung). Thomas will seine Größe h bestimmen, hat allerdings keinMaßband zur Verfügung. Dafür hat er eine Uhr, einen Ball und im Physikunterricht gut aufge-passt. Zur Lösung der Aufgabe hat er zwei Ideen:

- Verfahren 1: Thomas lässt den Ball aus Kopfhöhe fallen und misst die Zeit t0, bis der Ballauf dem Boden ankommt. Die Höhe berechnet er aus der Formel für den freien Fall,

y(t) = h−1

2gt2 ⇒ h =

1

2gt20,

mit der Gravitationskonstanten g = 9.81m/s2.

1

Messung 0.58 s 0.61 s 0.62 s 0.54 s 0.64 s 0.598 sMessfehler (rel.) 4% 0.5% 2% 10% 6% 1%

Größe 1.65 m 1.82 m 1.89 m 1.43 m 2.01 m 1.76 m

Fehler (abs.) 0.15 m 0.02 m 0.09 m 0.37 m 0.21 m 0.04 mFehler (rel.) 8% 1 % 5% 21% 12% 2%

Tabelle 1: Experiment 1: Größenbestimmung durch Fallenlassen eines Balles

Messung 1.60 s 1.48 s 1.35 s 1.53 s 1.45 s 1.482 sMessfehler (rel.) 5% 2.5% 11% <1% 5% 2%

Größe 2.53 m 1.47 m 0.48 m 1.90 m 1.23 m 1.49 m

Fehler (abs.) 0.73 m 0.33 m 1.32 m 0.10 m 0.57 m 0.31 mFehler (rel.) 40% 18% 73% 6% 32% 17%

Tabelle 2: Experiment 2: Größenbestimmung durch Hochwerfen eines Balles

- Verfahren 2: Der Ball wird 2m über den Kopf geworfen und wir messen die Zeit bis derBall wieder auf dem Boden angekommen ist. Die Strecke s = 2m wird in t ′ =

√2s/g Se-

kunden zurückgelegt, hierfür benötigt der Ball eine Startgeschwindigkeit von v0 = gt ′ =√2 sg ≈ 6.26m/s. Es gilt für die Flugbahn:

y(t) = h+ v0t−1

2gt2 ⇒ h =

1

2gt20 − v0t0

Das zweite Verfahren wird gewählt, weil die Zeit t0, die der Ball in Verfahren 1 zum Fallenbenötigt, sehr klein ist. Große Messfehler werden vermutet. Wir führen zunächst Algorithmus1 durch und messen 5-mal (exakte Lösung h = 1.80m und t0 ≈ 0.606 s). Die Ergebnissesind in Tabelle 1 zusammengefasst. In der letzten Spalte wurde als Zeit der Mittelwert allerMessergebnisse gewählt. Dies geschieht in der Hoffnung, den Messfehler zu optimieren.Wir führen nun Algorithmus 2 durch und messen 5-mal (exakte Lösung h = 1.80m und t0 ≈1.519 s). In der Tabelle sind die Messergebnisse und ermittelten Größen zusammengefasst. Inder letzten Spalte wird wieder der Mittelwert aller Messergebnisse betrachtet.

Trotz anfänglicher Zweifel erweist sich Algorithmus 1 als stabiler. Mögliche Fehlerquel-len sind der Messfehler bei der Bestimmung der Zeit t0 sowie bei Algorithmus 2 dieGenauigkeit beim Erreichen der Höhe von 2m. In Algorithmus 1 führt der Messfehlerzu etwa dem doppelten relativen Fehler in der Größe. Bei Algorithmus 2 führen selbstkleine Fehler6 1% in den Messungen zu wesentlich größeren Fehlern im Ergebnis. Derimmer noch kleine Fehler von 5% bei der erstenMessung führt zu einem Ergebnisfehlervon etwa 40%. Auch bei Betrachtung des Mittelwerts über alle Messwerte ist die ermit-telte Größe von 1.49m keine gute Näherung.

2

Wir wollen nun untersuchen, welche Auswirkung der Fehler in der Eingabe eines Al-gorithmus auf das Ergebnis hat. Hierzu sei die Aufgabe wieder allgemein durch dieVorschrift A : x 7→ y beschrieben. Die Eingabe x sei mit einem Fehler δx behaftet. Diegestörte Eingabe x = x+ δx liefert ein gestörtes Ergebnis y = y+ δy:

y = A(x), δy = y− y = A(x) −A(x) = A(x+ δx) −A(x)

Wir dividieren durch y = A(x) und erweitern rechts mit δx sowie mit x

δy

y=A(x+ δx) −A(x)

δx

x

A(x)

δx

x.

Auf der linken Seite verbleibt der relative Fehler im Ergebnis. Gehenwir nun davon aus,dass die Störung δx infinitesimal klein ist, so bleibt rechts ein Differenzenquotient fürdie erste Ableitung der Aufgabe. Im Fall |δx|→ 0 gilt∣∣∣∣δyy

∣∣∣∣ ≈ ∣∣∣∣∂A(x)∂x

x

A(x)

∣∣∣∣ · ∣∣∣∣δxx∣∣∣∣ ,

und wir nennen die GrößeκA,x :=

∂A(x)

∂x

x

A(x),

die Konditionszahl der Aufgabe A(·) in Bezug auf die Eingabe x. Die Konditionszahl be-schreibt die relative Fehlerverstärkung einer Aufgabe in Bezug auf eine Eingabegröße.Wir definieren:

Folie 2

Definition 2 (Konditionszahl). Es sei A : Rn → Rm. Wir nennen

κi,j :=∂Ai(x)

∂xj

xj

Ai(x)

die relativeKonditionszahl der Aufgabe. EineAufgabe heißt schlecht konditioniert, falls|κi,j|� 1, ansonsten gut konditioniert. Im Fall |κi,j| < 1 spricht man von Fehlerdämp-fung, ansonsten von Fehlerverstärkung.

Wir setzen das Beispiel zur experimentellen Größenbestimmung fort:

Beispiel 2 (Größenbestimmung, Fortsetzung).

- Verfahren 1: Zum Durchführen des Verfahrens h(t0) ist als Eingabe die gemessene Zeit t0erforderlich. Für die Konditionszahl gilt:

κh,t0 :=∂h(t0)

∂t0

t0

h(t0)= gt0

t012gt

20

= 2

Ein relativer Fehler in der Eingabe δt0/t0 kann demnach einen doppelt so großen relativenFehler in der Ausgabe verursachen.

3

- Verfahren 2: Wir bestimmen die Konditionszahl in Bezug auf die Zeit t0:

κh,t0 = (gt0 − v0)t0

12gt

20 − v0t0

= 2gt0 − v0gt0 − 2v0

Wir wissen, dass der Ball bei exaktem Wurf und ohne Messfehler t0 ≈ 1.519 s unterwegsist bei einer Startgeschwindigkeit von v0 ≈ 6.26m/s. Dies ergibt:

κh,t0 ≈ κh,v0 ≈ 8

Fehler in der Eingaben δt0/t0 sowie δv0/v0 werden um den Faktor 8 verstärkt. Die durchdie Konditionszahlen vorhergesagten Fehlerverstärkungen lassen sich in den Tabellen 1und 2 zu Beispiel 1 gut wiederfinden.

2 ZahldarstellungDie Analyse von Fehlern und Fehlerfortpflanzungen spielt eine zentrale Rolle in der nu-merischen Mathematik. Fehler treten vielfältig auf, auch ohne ungenaue Eingabewerte.Oft sind numerische Algorithmen sehr komplex, setzen sich aus vielen Operationen zu-sammen. Bei der Approximationmit demComputer treten unweigerlichRundungsfehlerauf. Da der Speicherplatz im Computer bzw. die Anzahl der Ziffern auf dem Taschen-rechner beschränkt ist, treten Rundungsfehler schon bei der bloßen Darstellung einerZahl auf. Auch wenn es für die numerische Aufgabe

x2 = 2, ⇔ x = ±√2,

mit x = ±√2 eine einfach anzugebende Lösung gibt, kann diese auf einem Computer

nicht exakt dargestellt werden:√2 = 1.41421356237309504880 . . .

Der naheliegende Grund für einen zwingenden Darstellungsfehler ist der beschränk-te Speicher eines Computers. Ein weiterer Grund liegt in der Effizienz. Ein Computerkann effizient nicht mit beliebig langen Zahlen rechnen. Grund ist die beschränkte Da-tenbandbreite (das sind die 8 Bit, 16 Bit, 32 Bit oder 64 Bit der Prozessoren). Operatio-nenmit Zahlen in längerer Darstellungmüssen zusammengesetzt werden, ähnlich demschriftlichen Multiplizieren oder Addieren aus der Schule.Computer speichern Zahlen gerundet in Binärdarstellung, also zur Basis 2:

rd(x) = ±n2∑

i=−n1

ai2i, ai ∈ {0, 1}.

Die Genauigkeit der Darstellung somit der Rundungsfehler hängen von der Anzahl derZiffern, also von n1 und n2 ab. Die Fixkommadarstellung der Zahl im Binärsystem lautet:

rd(x) = [an2an2−1 . . .a1a0.a−1a−2 . . .a−n1 ]2

4

Praktischer ist die Gleitkommadarstellung von Zahlen. Hierzu wird die Binärdarstellungnormiert und ein gemeinsamer Exponent eingeführt:

rd(x) = ±

0∑i=−n1−n2

ai+n22i

2n2 , ai ∈ {0, 1}.

Der führende Term (die ai) heißt dieMantisse und wird von uns mitM bezeichnet, denExponenten bezeichnen wir mit E. Der Exponent kann dabei eine positive oder negativeZahl sein. Zur Vereinfachungwird der Exponent E als E = e−bmit einer positiven Zahle ∈ NunddemBias b ∈ N geschrieben. Der Biaswert bwird in einer konkreten Zahldar-stellung fest gewählt und bestimmt somit den größtmöglichen negativen Exponenten.Der variable Exponentenanteil e wird selbst im Binärformat gespeichert. Es bleibt, dieAnzahl der Binärstellen für Mantisse und Exponent zu wählen. Hinzu kommt ein Bitfür das Vorzeichen S ∈ {+,−}. Die Gleitkommadarstellung im Binärsystem lautet:

rd(x) = S · [m0.m−1m−2 . . .m−#m]2 · 2[e#e...e1e0]2−b

Die Mantisse wird üblicherweise mit m0 = 1 normiert zu M ∈ [1, 2). Das heißt, dieführende Stelle muss nicht explizit gespeichert werden.

5

Folie 3Auf modernen Computern hat sich das IEEE-754-Format zum Speichern von Zah-len etabliert:

Definition 3 (Normalisierte Gleitkommazahlen im IEEE 754-Format). Das IEEE754-Format a beschreibt die Gleitkommadarstellung einer Zahl im Binärformat

x = s ·M · 2e−b

mit einem Vorzeichen s ∈ {+,−}, einer Mantisse M ∈ [1, 2) sowie einem Exponentene ∈ N mit Bias b ∈ N. Die Gleitkommazahl wird in Binärdarstellung gespeichert:

se#e . . . e2e1m#m . . .m2m1,

mit#e Bit für den Exponenten und#m Bit für die Mantisse. Der Bias wird im Allgemei-nen als 2#e−1 − 1 gewählt. Die Interpretation der Zahlen hängt vom Exponenten ab:

Null Im Fall e = 0 und m1 = · · · = m#m = 0 ist x = ±0. Die Unterscheidungzwischen +0 und −0 entsteht beim Runden kleiner Zahlen zur Null. Im direktenVergleich interpretiert ein Computer +0 = −0.

Unendlich Im Fall e = 2#e − 1 (also alle Bit im Exponenten gleich 1) und m1 =· · · = m#m = 0 ist x = ±∞. Unendlich entsteht etwa beim Teilen durch 0 (mitVorzeichen!) oder falls das Ergebnis zu groß (oder negativ zu klein) ist, um darstellbarzu sein.

NaN Im Fall e = 2#e − 1 undM > 0 steht der Wert für not a number und tritt zumBeispiel bei der Operation 0/0 oder ∞−∞ auf.

Normalisierte Zahl Im Fall 0 6 e < 2#e−1 steht die Zahl für

s · 1.m#m . . .m2m1 · 2e−b.aIEEE 754-2008: Standard for Floating-Point Arithmetic, IEEE Standard Association, 2008.doi:10.1109/IEEESTD.2008.4610935

Das Rechnen mit Gleitkommazahlen kann im Computer effizient realisiert werden. ImIEEE 754-Format wird die Gleitkommadarstellung durch denormalisierte Zahlen erwei-tert. Wir erwähnen dies zur Vollständigkeit:

Bemerkung 1 (Denormalisierte Zahlen). Denormalisierte Zahlen dienen zum Schließen derLücke zwischen Null und der kleinsten positiven darstellbaren Zahl 1.0 . . . 001 · 2−b. Im Falle = 0 undM > 0 wird die Zahl interpretiert als:

s · 0.m#m . . .m2m1 · 21−b

Die Genauigkeit bei der Rechnung mit denormalisierten Zahlen ist reduziert.

6

In der Tabelle zu Folie 4 sind verschiedene Gleitkommadarstellungen zusammenge-fasst, die historisch und aktuell benutzt werden. Derzeit wird fast ausschließlich dasIEEE-Format verwendet. Hier sind zwei Darstellungen üblich, single-precision (in C++float) und double-precision (in C++ double). Durch die Normierung der Mantisse wirdein Bit, das sogenannte hidden-bit, gewonnen. Historisch wurden in Rechensystemenjeweils unterschiedliche Zahlendarstellungen gewählt. Während die ersten Computernoch im Prozessor integrierte Recheneinheiten für Gleitkomma-Arithmetik, die eine so-genannte floating-point processing unit (FPU) hatten, verschwand diese zunächst wiederaus den üblichen Computern und war nur in speziellen Rechnern vorhanden. In Formvon Coprozessoren konnte eine FPU nachgerüstet werden (z.B. der Intel 8087 zum Intel8086). Der “486er” war der erste Prozessor für Heimcomputer mit integrierter FPU.Heute können Gleitkommaberechnungen effizient auf Grafikkarten ausgelagert wer-den. Die Prozessoren der Grafikkarten, die graphics processing units (GPU) sind speziellfür solche Berechnungen ausgelegt (z.B. schnelle Berechnung von Lichtbrechungen undSpiegelungen, Abbilden von Mustern auf 3D-Oberflächen). Spezielle Steckkarten (z.B.NVIDIA Tesla), die gleich mehrere GPUs enthalten, werden in Höchstleistungssyste-men eingesetzt. Die Genauigkeit der Darstellung ist im Wesentlichen von den in derMantisse zu Verfügung stehenden Stellen bestimmt. Größte und kleinste darstellbareZahlen sind durch die Stellen im Exponenten bestimmt. In numerischen Verfahren istdie Verwendung von doppelt-genauer Zahlendarstellung (double) üblich. Die Rechen-einheiten moderner Computer nutzen intern eine erhöhte Genauigkeit zum Durchfüh-ren von elementaren Operationen (80 Bit bei modernen Intel-CPUs). Gerundet wird erstnach Berechnung des Ergebnisses.

Folie 4

Größe Vorzeichen Exponent Mantisse Bias

einf. genau (single) 32 Bit 1 Bit 8 Bit 23+1 Bit 127dopp. genau (double) 64 Bit 1 Bit 11 Bit 52+1 Bit 1023

Zuse Z1 (1938) 24 Bit 1 Bit 7 Bit 15 Bit —IBM 704 (1954) 36 Bit 1 Bit 8 Bit 27 Bit 128i8087 Coprozessor (1980) Erste Verwendung von IEEE (single + double)Intel 486 (1989) Erste integrierte FPU in Standard-PCNVIDIA G80 (2007) GPU (single)NVIDIA Fermi (2010) GPU (double)

Beispiel 3 (Gleitkommadarstellung). Wir gehen von vierstelliger Mantisse und vier Stellenim Exponenten aus mit Bias 24−1 − 1 = 7.

• Die Zahl x = −96 hat zunächst negatives Vorzeichen, also S = 1. Die Binärdarstellungvon 96 ist

9610 = 1 · 64+ 1 · 32+ 0 · 16+ 0 · 8+ 0 · 4+ 0 · 2+ 0 · 1 = 11000002,

7

normalisiert

9610 = 1.10002 · 2610 = 1.12 · 21310−710 = 1.12 · 211012−b.

Als Gleitkommadarstellung ergibt sich 1110110002.

• Die Zahl x = −384 hat wieder negatives Vorzeichen und S = 1. Die Binärdarstellungvon 384 ist:

38410 = 1 · 256+ 1 · 128+ 0 · 64+ 0 · 32+ 0 · 16+ 0 · 8+ 0 · 4+ 0 · 2+ 0 · 1= 1100000002,

also normalisiert

38410 = 1.1000 · 2810 = 1.1000 · 21510−710 = 1.10002 · 211112−b.

Alle Bits im Exponenten sind 1. Der spezielle Wert e = 11112 ist jedoch zur SpeicherungvonNaN (not a number) vorgesehen. Die Zahl 384 ist zu groß, um in diesemZahlenformatgespeichert zu werden. Stattdessen wird −∞ oder binär 1111100002 gespeichert.

• Die Zahl x = 1/3 = 0.33333 . . . ist positiv, also S = 0. Die Binärdarstellung von 1/3 ist1

3= 0.01010101 . . .2 .

Normalisiert mit vierstelliger Mantisse erhalten wir1

3≈ 1.01012 · 2−2 = 1.01012 · 2510−710 = 1.01012 · 201012−b,

also die Binärdarstellung 0010101012. Wir mussten bei der Darstellung runden und er-halten rückwärts

1.01012 · 201012−7 = 1.3125 · 2−2 = 0.328125

mit dem relativen Fehler ∣∣∣∣∣ 13 − 1.01012 · 201012−b13

∣∣∣∣∣ ≈ 0.016.

• Die Zahl x =√2 ≈ 1.4142135623 . . . ist positiv, also S = 0. Gerundet gilt:

√2 ≈ 1.01112

Diese Zahl liegt bereits normalisiert vor. Mit Bias b = 7 gilt für den Exponenten e = 0 =7− 7 √

2 ≈ 1.01112 · 201112−b,also 001110111. Rückwärts in Dezimaldarstellung erhalten wir

1.01112 · 201112−b = 1.4375

mit dem relativen Darstellungsfehler∣∣∣∣√2− 1.4375√2

∣∣∣∣ ≈ 0.016.

8

• Schließlich betrachten wir die Zahl x = −0.003. Mit S = 1 gilt:

0.00310 ≈ 0.000000001100012

und normalisiert0.00310 ≈ 1.10012 · 2−9 = 1.10012 · 2−2−7.

Der Exponent −9 = −2 − b ist zu klein und kann in diesem Format (also vier Stellenfür den Exponenten) nicht dargestellt werden. Die Zahl kann hingegen denormalisiertdargestellt werden als

0.00310 ≈ ·0.00112 · 21−7.

Binär ergibt dies 1000000112. Umrechnen in Dezimaldarstellung liefert

0.00112 · 21−7 = 0.1875 · 2−6 ≈ 0.0029

mit dem relativen Darstellungsfehler∣∣∣∣0.003− 0.0029

0.003

∣∣∣∣ ≈ 0.033.

9

Folie 5Vereinfachte Gleitkommadarstellung

Definition 4 (Rechnen mitM Stellen im 10er System). Wenn wir mitM Stellen Ge-nauigkeit rechnen, dann stehenM Stellen zur Speicherung der Mantisse zur Verfügung.Der Exponent kann stets exakt dargestellt werden. Durch

x = ±0.s1s2s3 · 10k

für k ∈ Z und s1, s2, s3 ∈ {0, . . . , 9} können alle möglichen Zahlen dargestellt werden.

Einige Beispiele zum Rechnen mit 3 Stellen Genauigkeit:

• Runden

1

3≈ 0.333,

100

3≈ 33.3,

10000

3≈ 3330, 1/3000 ≈ 0.000333

Wir “speichern” 3 Ziffern und vorher oder nachher beliebig viele Nullen. Jedediese Zahlen kann geschrieben werden als

0.333 · 10k

mit einem Exponenten k ∈ Z.

• Addieren, Subtrahieren, Multiplizieren

0.321+ 0.931 = 1.252 ≈ 1.25, 1.09+ 0.899 = 1.989 ≈ 1.99,

124+ 0.210 = 124.21 ≈ 124, 0.921− 1.52 = −0.599

0.321 · 0.931 = 0.298851 ≈ 0.299, 0.912/0.00125 = 729.6 ≈ 730

Gerundet wird stets nach exakter Rechnung. Dies ist mit dem Computer ver-gleichbar, da intern für die Berechnungen eine höhere Genauigkeit zur Ver-fügung steht.

• Zusammengesetzte Arithmetik. Gerundet wird nach jedem Zwischenschritt

7 ·(4

7−

3

7

)≈ 3 · (0.571− 0.429) ≈ 3 · 0.142 = 0.994

Ausder begrenztenAnzahl vonZiffern ergibt sich zwangläufig ein Fehler bei derDurch-führung von numerischen Algorithmen. Der relative Fehler, der bei der Computerdar-stellung x einer Zahl x ∈ R entstehen kann,∣∣∣∣rd(x) − xx

∣∣∣∣ ,ist durch die sogenannteMaschinengenauigkeit beschränkt:

10

Folie 6

Definition 5 (Maschinengenauigkeit). Die Maschinengenauigkeit eps ist der maxi-male relative Rundungsfehler der Zahldarstellung und wird bestimmt als:

eps := inf{x > 0 : rd(1+ x) > 1}

Bei unserem Zahlensystem “Rechnen mit drei Stellen Genauigkeit” gilt

1+ x ≈ 1 ⇔ |x| < 0.005.

Sind im Zahlenformat denormalisierte Zahlen vorgesehen, so verschlechtert sich dieGenauigkeit für x→ 0.Da Rundungsfehler zwangsläufig auftreten, gelten grundlegende mathematische Ge-setze wie das Assoziativgesetz

(a+ b) + c = a+ (b+ c), (a · b) · c = a · (b · c)

oder das Distributivgesetz

a · (b+ c) = ab+ ac, (a+ b) · c = ac+ bc

auf Computern nicht mehr. Aufgrund von Rundungsfehlern spielt die Reihenfolge, inder Operationen ausgeführt werden, eine wichtige Rolle und verändert das Ergebnis.Auch ein einfacherVergleich vonZahlen ist oft nichtmöglich, dieAbfrage if (3.8/10.0==0.38)↪→ kann durch Rundung das falsche Ergebnis liefern undmuss durch Abfragen der Artif (fabs(3.8/10.0 − 0.38) < eps) ersetzt werden (der Befehl fabs( ) steht in C/C++ für den Be-trag einer Zahl).

Bemerkung 2. Die Maschinengenauigkeit hat nichts mit der kleinsten Zahl zu tun, die aufeinem Computer darstellbar ist. Diese ist wesentlich durch die Anzahl der Stellen im Exponen-ten bestimmt. Die Maschinengenauigkeit wird durch die Anzahl der Stellen in der Mantissebestimmt. Bei der üblichen Gleitkommadarstellung mit doppelter Genauigkeit (double in C++)gilt eps ≈ 10−16, bei einfacher Genauigkeit, z.B. auf Grafikkarten, gilt eps ≈ 10−8.

11

Folie 7

Beispiel 4 (Konditionierung der Grundoperationen).

1. Addition, Subtraktion: A(x,y) = x+ y:

κA,x =

∣∣∣∣ x

x+ y

∣∣∣∣ = ∣∣∣∣ 1

1+ yx

∣∣∣∣Im Fall x ≈ −y kann die Konditionszahl der Addition (x ≈ y bei der Subtraktion)beliebig groß werden. Ein Beispiel mit vierstelliger Rechnung:

x = 1.021, y = −1.019 ⇒ x+ y = 0.002

Jetzt sei y = 1.020 gestört. Der relative Fehler in y ist sehr klein

|1.019− 1.020|/|1.019| 6 0.1%.

Wir erhalten das gestörte Ergebnis

x+ y = 0.001

und einen Fehler von 100%. Die enorme Fehlerverstärkung bei der Addition von Zah-len mit etwa gleichem Betrag wird Auslöschung genannt. Hier gehen wesentlicheStellen verloren. Auslöschung tritt üblicherweise dann auf, wenn das Ergebnis einernumerischen Operation verglichen mit den Eingabewerten einen sehr kleinen Betraghat. Kleine relative Fehler in der Eingabe verstärken sich zu großen relativen Fehlernim Ergebnis.

2. Multiplikation: A(x,y) = x · y. Die Multiplikation zweier Zahlen ist stets gut kon-ditioniert:

κA,x =

∣∣∣∣y xxy∣∣∣∣ = 1

3. Division: A(x,y) = x/y. Dasselbe gilt für die Division:

κA,x =

∣∣∣∣∣ 1y xxy∣∣∣∣∣ = 1, κA,y =

∣∣∣∣∣ xy2 yxy∣∣∣∣∣ = 1

4. Wurzelziehen: A(x) =√x:

κA,x =

∣∣∣∣ 1

2√x

x√x

∣∣∣∣ = 1

2

Ein Fehler in der Eingabe wird im Ergebnis sogar reduziert.

12

Die meisten numerischen Algorithmen bestehen im Kern aus der wiederholten Aus-führung dieser Grundoperationen. Der Aufwand von Algorithmen wird in der Anzahlder notwendigen elementaren Operationen (in Abhängigkeit von der Problemgröße)gemessen. Die Laufzeit eines Algorithmus hängt wesentlich von der Leistungsfähigkeitdes Rechners ab. Diese wird in FLOPS, also floating point operations per second gemessen.In Tabelle 3 fassen wir die erreichbaren FLOPS für verschiedene Computersysteme zu-sammen. Die Leistung ist im Laufe der Jahre rapide gestiegen, alle zehn Jahre wird et-wa der Faktor 1000 erreicht. Die Leistungssteigerung beruht zum einen auf effizientererHardware. Erste Computer hatten Register mit 8 Bit Breite, die in jedem Takt (das istdie MHz-Angabe) verarbeitet werden konnten. Auf aktueller Hardware stehen Regis-ter mit 64 Bit zur Verfügung. Hinzu kommt eine effizientere Abarbeitung von Befehlendurch sogenanntes Pipelining: Die übliche Abfolge im Prozessor beinhaltet “Speicherlesen, Daten bearbeiten, Ergebnis speichern”. Das Pipelining erlaubt es dem Prozessor,schon den Speicher für die nächste Operation auszulesen, während noch die aktuellebearbeitet wird. So konnte die Anzahl der notwendigen Prozessortakte pro Rechenope-ration erheblich reduziert werden. Die Kombination aus Intel 8086 mit FPU 8087 hatbei einem Takt von 8 Mhz und 50 000 FLOPS etwa 150 Takte pro Fließkommaoperati-on benötigt. Der 486er braucht bei 66 MHz und etwa 1 000 000 FLOPS nur 50 Takte proOperation. Der Pentium III liegt bei etwa 5 Takten pro Fließkommaoperation.In den letzten Jahren beruht die Effizienzsteigerung wesentlich auf einem sehr hohenGrad an Parallelisierung. Ein aktueller Core I7-Prozessor kann mehrere Operationengleichzeitig durchführen. Eine NVIDIA 580-GPU erreicht ihre Leistung mit über 500Rechenkernen. Um diese Leistung effizient nutzen zu können, müssen die Algorithmenentsprechend angepasst werden, sodass auch alle 500 Kerne ausgelastet werden. Kannein Algorithmus diese spezielle Architektur nicht ausnutzen, so fällt die Leistung aufetwa ein GigaFLOP zurück, also auf das Niveau des Pentium III aus dem Jahr 2001.Werden die 500 Kerne hingegen optimal ausgenutzt, so erreicht eine Grafikkarte diegleiche Leistung wie der Heidelberger Linux-Cluster Helics aus dem Jahr 2002.Modernste Supercomputer wie der Sunway TaihuLight (schnellster Computer der Weltin 2016) vernetzen über 10 000 000 Kerne. Einen aktuellen Überblick gibt die Top 500 Lis-te der Supercomputer1. Bei parallelen Höchstleistungsrechnern spielt auch der Stromver-brauch eine bedeutende Rolle. Der Sunway TaihuLight verbraucht im Jahr so viel Stromwie 70 000 Privatpersonen. Jede Nutzungsstunde schlägt mit einer Stromrechnung voneinigen Tausend Euro zu Buche. Durch neue Bauweisen, insbesondere durch kleineresLayout der Platinen, kann der Stromverbrauch pro FLOP ständig gesenkt werden.

3 Rundungsfehleranalyse und Stabilität vonnumerischen Algorithmen

BeimEntwurf von numerischenAlgorithmen für eineAufgabe sind oft unterschiedlicheWege möglich, die sich z.B. in der Reihenfolge der Verfahrensschritte unterscheiden.

1https://www.top500.org Liste der jeweils 500 schnellsten Computer der Welt.

13

CPU Jahr FLOPS Preis Energieverbrauch

Zuse Z3 1941 0.3 Einzelstücke 4 kWIBM 704 1955 5 · 103 >10 000 000 EUR 75 kWIntel 8086 + 8087 1980 50 · 103 2 000 EUR 200 Wi486 1991 1.4 · 106 2 000 EUR 200 WIPhone 4s 2011 100 · 106 500 EUR 10 W2 x Pentium III 2001 800 · 106 2 000 EUR 200 WCore i7 2011 100 · 109 1 000 EUR 200 WHelics I (in HD) 2002 1 · 1012 1 000 000 EUR 40 kWNVIDIA GTX 580 (GPU) 2010 1 · 1012 500 EUR 250 WK Computer 2011 10 · 1015 > 500 000 000 EUR 12 000 kWSunway TaihuLight 2016 93 · 1015 250 000 000 EUR 15 500 kW

Tabelle 3: Gleitkommageschwindigkeit sowie Anschaffungskosten einiger aktuellerund historischer Computer (HD = Heidelberg. Dieser Computer war der 35-schnellste in der Welt als er angeschafft wurde.)

Folie 8

Beispiel 5 (Distributivgesetz). Wir betrachten die Aufgabe A(x,y, z) = x · z − y · z =(x− y)z und zur Berechnung zwei Vorschriften:

a1 := x · z, a1 := x− y,

a2 := y · z, a := a1 · z,a := a1 − a2.

Es sei x = 0.519, y = 0.521, z = 0.941. Bei vierstelliger Arithmetik erhalten wir:

a1 := rd(x · z) = 0.4884, b1 := rd(x− y) = −0.002,

a2 := rd(y · z) = 0.4903, b2 := rd(a1 · z) = −0.001882,

a3 := rd(a1 − a2) = −0.0019.

Mit A(x,y, z) = −0.001882 ergeben sich die relativen Fehler:∣∣∣∣−0.0001882− a30.0001882

∣∣∣∣ ≈ 0.01,

∣∣∣∣−0.0001882− b20.0001882

∣∣∣∣ = 0.

Das Distributivgesetz gilt auf dem Computer nicht!

Die Stabilität hängt also entscheidend vom Design des Algorithmus ab. Eingabefehleroder auch Rundungsfehler, die in einzelnen Schritten entstehen, werden in darauffol-

14

genden Schritten des Algorithmus verstärkt. Wir analysieren nun beide Verfahren imDetail und gehen davon aus, dass in jedem der elementaren Schritte (wir haben hiernur Addition undMultiplikation) ein relativer Rundungsfehler εmit |ε| 6 eps entsteht,also

rd(x+ y) = (x+ y)(1+ ε), rd(x · y) = (x · y)(1+ ε).Zur Analyse eines gegebenen Algorithmus verfolgen wir die Rundungsfehler, welchein jedem Schritt entstehen, und deren Akkumulation:

Beispiel 6 (Stabilität desDistributivgesetzes). Wir berechnen zunächst die Konditionszahlender Aufgabe:

κA,x =

∣∣∣∣ 1

1− yx

∣∣∣∣ , κA,y =

∣∣∣∣∣ 1

1− xy

∣∣∣∣∣ , κA,z = 1.

Für x ≈ y ist die Aufgabe schlecht konditioniert. Wir starten mit Algorithmus 1 und schätzenin jedem Schritt den Rundungsfehler ab. Zusätzlich betrachten wir Eingabefehler (oder Dar-stellungsfehler) von x,y und z. Wir berücksichtigen stets nur Fehlerterme erster Ordnung undfassen alle weiteren Terme mit den Landau-Symbolen (für kleine ε) zusammen:

a1 =x(1+ εx)z(1+ εz)(1+ ε1) = xz(1+ εx + εz + ε1 +O(eps2))

= xz(1+ 3ε1 +O(eps2))

a2 =y(1+ εy)z(1+ εz)(1+ ε2) = yz(1+ εy + εz + ε2 +O(eps2))

= yz(1+ 3ε2 +O(eps2))

a3 =(xz(1+ 3ε1) − yz(1+ 3ε2) +O(eps2))(1+ ε3)

= (xz− yz)(1+ ε3) + 3xzε1 − 3yzε2 +O(eps2)

Wir bestimmen den relativen Fehler:∣∣∣∣a3 − (xz− yz)

xz− yz

∣∣∣∣ = |(xz− yz)ε3 + 3xzε1 − 3yzε2|

|xz− yz|6 eps+ 3

|x|+ |y|

|x− y|eps

Die Fehlerverstärkung dieses Algorithmus kann für x ≈ y groß werden und entspricht etwa(Faktor 3) der Konditionierung der Aufgabe. Wir nennen den Algorithmus daher stabil.Wir betrachten nun Algorithmus 2:

a1 =(x(1+ εx) − y(1+ εy))(1+ ε1)

= (x− y)(1+ ε1) + xεx − yεy +O(eps2)

a2 =z(1+ εz)((x− y)(1+ ε1) + xεx − yεy +O(eps2)

)(1+ ε2)

= z(x− y)(1+ ε1 + ε2 + εz +O(eps)2) + zxεx − zyεy +O(eps2)

Für den relativen Fehler gilt in erster Ordnung:∣∣∣∣a2 − (xz− yz)

xz− yz

∣∣∣∣ = |z(x− y)(ε1 + ε2 + εz) + zxεx − zyεy|

|xz− yz|

6 3eps+|x|+ |y|

|x− y|eps

15

Die Fehlerverstärkung kann für x ≈ y wieder groß werden. Der Verstärkungsfaktor ist jedochgeringer als bei Algorithmus 1. Insbesondere fällt auf, dass dieser zweite Algorithmus bei fehler-freien Eingabedaten keine Fehlerverstärkung aufweist. (Das ist der Fall εx = εy = εz = 0.)Beide Algorithmen sind stabil, der zweite hat bessere Stabilitätseigenschaften als der erste.

Wir nennen die beiden Algorithmen stabil, obwohl der eine wesentlich bessere Stabili-tätseigenschaften hat. Der Stabilitätsbegriff dient daher oft zum relativen Vergleich ver-schiedener Algorithmen. Wir definieren:

Folie 9

Definition 6 (Stabilität). Ein numerischer Algorithmus zum Lösen einer Aufgabe heißtstabil, falls die bei der Durchführung akkumulierten Rundungsfehler den durch die Kondi-tion der Aufgabe gegebenen unvermeidlichen Fehler nicht übersteigen.

Wir halten fest: Für ein schlecht konditioniertes Problem existiert kein stabiler Algorith-mus mit einer geringeren Fehlerfortpflanzung als durch die Konditionierung bestimmt.Für gut konditionierte Probleme können jedoch beliebig instabile Verfahren existieren.DerwesentlicheUnterschied zwischen beidenAlgorithmen aus demBeispiel ist die Rei-henfolge der Operationen. In Algorithmus 1 ist der letzte Schritt eine Subtraktion, derenschlechte Kondition wir unter dem Begriff Auslöschung kennengelernt haben. Bereitsakkumulierte Rundungsfehler zu Beginn des Verfahrens werden hier noch einmal we-sentlich verstärkt. Bei Algorithmus 2 werden durch die abschließende Multiplikationdie Rundungsfehler, die zu Beginn auftreten, nicht weiter verstärkt. Aus dem analysier-ten Beispiel leiten wir eine Regel her:

Bei dem Entwurf von numerischen Algorithmen sollen schlecht konditionierte Operationen zuBeginn durchgeführt werden.

16

4 Lineare Gleichungsysteme

Folie 10Als einführendes Beispiel betrachten wir das einfache Gleichungssystem(

0.988 0.9600.992 0.963

)(x

y

)=

(0.0840.087

)mit der Lösung (x,y)T = (3,−3)T . Wir bestimmen die Lösungs numerisch durchGauß-Elimination mit dreistelliger Rechengenauigkeit. Die Gauß-Elimination set-zen wir dabei als bekannt voraus:( )

0.988 0.960 0.0840.992 0.963 0.087 ×0.988/0.992( )0.988 0.960 0.0840.988 0.959 0.0866 ↓ −( )0.988 0.959 0.0840 0.001 −0.0026

Mithilfe der Gauß-Elimination haben wir die Matrix A auf eine Dreiecksgestalttransformiert. Die rechte Seite b wurde entsprechend modifiziert. Das resultieren-de Dreieckssystem kann nun sehr einfach durch Rückwärtseinsetzen gelöst werden(bei dreistelliger Rechnung):

0.001y = −0.0026 ⇒ y = −2.6

0.988x = 0.087− 0.959 · (−2.6) ≈ 2.58 ⇒ x = 2.61.

Wir erhalten also (x,y) = (2.61,−2.60). Der relative Fehler der numerischen Lö-sung beträgt somit mehr als 10%.

Die numerischeAufgabe, einGleichungssystem zu lösen, scheint also entweder generellsehr schlecht konditioniert zu sein, oder aber das Eliminationsverfahren zur Lösungeines linearen Gleichungssystems ist numerisch sehr instabil und nicht gut geeignet.Der Frage nach der Konditionierung und Stabilität gehen wir im folgenden Abschnittauf den Grund.

17

5 MatrixnormenFür Normen auf dem Raum derMatrizen definieren wir weitere Struktureigenschaften.

Folie 11

Definition 7 (Matrixnormen). Eine Norm ‖ · ‖ : Rn×n → R+ heißtMatrixnorm, fallssie submultiplikativ ist:

‖AB‖ 6 ‖A‖ ‖B‖ ∀A,B ∈ Rn×n.

Sie heißt verträglich mit einer Vektornorm ‖ · ‖ : Rn → R+, falls gilt:

‖Ax‖ 6 ‖A‖ ‖x‖ ∀A ∈ Rn×n, x ∈ Rn.

Eine Matrixnorm ‖ · ‖ : Rn×n → R+ heißt von einer Vektornorm ‖ · ‖ : Rn → R+

induziert, falls gilt:

‖A‖ := supx 6=0

‖Ax‖‖x‖

.

Für eine induzierte Matrixnorm gilt stets:

‖A‖ := supx 6=0

‖Ax‖‖x‖

= sup‖x‖=1

‖Ax‖ = sup‖x‖61

‖Ax‖

Es ist leicht nachzuweisen, dass jede von einer Vektornorm induzierte Matrixnorm mitdieser auch verträglich ist. Verträglich mit der euklidischen Norm ist aber auch dieFrobenius-Norm

‖A‖F :=

n∑i,j=1

a2ij

12

, (1)

welche nicht von einer Vektornorm induziert ist. Für allgemeine Normen auf dem Vek-torraum der Matrizen gilt nicht notwendigerweise ‖I‖ = 1, wobei I ∈ Rn×n die Ein-heitsmatrix ist. Dieser Zusammenhang gilt aber für jede von einer Vektornorm induzier-te Matrixnorm. Wir fassen im folgenden Satz die wesentlichen induzierten Matrixnor-men zusammen.

18

Folie 12

Satz 1 (Induzierte Matrixnormen). Sei A ∈ Rn×n. Die aus der euklidischen Vektor-norm, der Maximumsnorm sowie der l1-Norm induzierten Matrixnormen sind die Spek-tralnorm ‖ · ‖2, die maximale Zeilensumme ‖ · ‖∞, sowie die maximale Spaltensumme‖ · ‖1:

‖A‖2 =√

spr(ATA), spr(B) := max{|λ|, λ ist Eigenwert von B},

‖A‖∞ = maxi=1,...,n

m∑j=1

|aij|,

‖A‖1 = maxj=1,...,m

n∑i=1

|aij|.

Beweis. (i) Es gilt:

‖A‖22 = supx 6=0

‖Ax‖22‖x‖22

= supx 6=0

(Ax,Ax)

‖x‖22= supx 6=0

(ATAx, x)

‖x‖22.

DieMatrixATA ist symmetrisch undhat als solche nur reelle Eigenwerte. Sie besitzt eineOrthonormalbasisωi ∈ Rn von Eigenvektorenmit Eigenwerten λi > 0. Alle Eigenwerteλi sind größer gleich null, denn:

λi = λi(ωi,ωi) = (ATAωi,ωi) = (Aωi,Aωi) = ‖Aωi‖2 > 0 (2)

Es sei x ∈ Rn beliebigmit Basisdarstellung x =∑i αiωi. Es gilt dannwegen (ωi,ωj)2 =

δij die Beziehung ‖x‖22 =∑i α

2i mit αi ∈ R:

‖A‖22 = sup|α|6=0

(∑i αiA

TAωi,∑i αiωi)∑

i α2i

= sup|α|6=0

(∑i αiλiωi,

∑i αiωi)∑

i α2i

= sup|α|6=0

∑i λiα

2i∑

i α2i

6 maxiλi,

wobei|α| = max

i|αi|.

Es sei nun umgekehrt durch λk der größte Eigenwert gegeben. Dann gilt wegen (2) mitαi = δki:

0 6 maxiλi = λk =

∑i

λiα2i =

∑i,j

(λiαiωi,αjωj) = (ATAx, x) = ‖Ax‖22. (3)

Also giltmaxi λi 6 ‖A‖22.

19

(ii)Wir zeigen das Ergebnis exemplarisch für die Maximumsnorm:

‖Ax‖∞ = sup‖x‖∞=1

maxi

m∑j=1

aijxj

Diese Summe mit ‖x‖∞ = 1 nimmt ihr Maximum an, falls |xj| = 1 und falls das Vorzei-chen xj so gewählt wird, dass aijxj > 0 für alle j = 1, . . . ,m. Dann gilt:

‖Ax‖∞ = maxi

m∑j=1

|aij|

Als Nebenresultat erhalten wir aus (3), dass jeder Eigenwert betragsmäßig durch dieSpektralnorm der Matrix A beschränkt ist. Es gilt sogar mit beliebiger Matrixnorm undverträglicher Vektornorm für einen Eigenwert λmit zugehörigem Eigenvektor w ∈ Rnvon A:

|λ| =|λ| ‖w‖‖w‖

=‖Aw‖‖w‖

6‖A‖ ‖w‖‖w‖

= ‖A‖

Eine einfache Schranke für den betragsmäßig größten Eigenwert erhält man also durchAnalyse beliebiger (verträglicher) Matrixnormen.

6 Störungstheorie und Stabilitätsanalyse vonlinearen Gleichungssystemen

Folie 13

Zu einer quadratischen regulären Matrix A ∈ Rn×n sowie einem Vektor b ∈ Rnbetrachten wir das lineare Gleichungssystem

Ax = b.

Durch numerische Fehler, Rundungsfehler, Eingabefehler oder durch Messunge-nauigkeiten liegen sowohl A als auch b nur gestört vor:

Ax = b

Dabei sei A = A+ δA sowie b = b+ δbmit den Störungen δA sowie δb.Wir wollen wissen, wie sich die Störung in der rechten Seite auf die Störung imErgebnis auswirkt

‖δx‖‖x‖

∼‖δb‖‖b‖

.

20

Wir kommen nun zur Kernaussage dieses Abschnitts undwollen die Fehlerverstärkungbeim Lösen von linearen Gleichungssystemen betrachten. Fehler können dabei sowohlin der Matrix A als auch in der rechten Seite b auftauchen. Wir betrachten zunächstStörungen der rechten Seite.

Folie 14

Satz 2 (Störung der rechten Seite). Es sei A ∈ Rn×n eine reguläre Matrix, b ∈ Rn.Durch x ∈ Rn sei die Lösung des linearen Gleichungssystems Ax = b gegeben. Es sei δbeine Störung der rechten Seite b = b+ δb und x die Lösung des gestörten Gleichungssys-tems Ax = b. Weiter sei ‖ · ‖ eine mit einer Vektornorm ‖ · ‖ verträgliche Matrixnorm.Dann gilt:

‖δx‖‖x‖

6 cond(A)‖δb‖‖b‖

,

mit der Konditionszahl der Matrix

cond(A) = ‖A‖ · ‖A−1‖.

Beweis. Es sei ‖ · ‖ eine beliebige Matrixnormmit verträglicher Vektornorm ‖ · ‖. Für dieLösung x ∈ Rn und gestörte Lösung x ∈ Rn gilt:

x− x = A−1(Ax−Ax) = A−1(b− b) = A−1δb

Also:

‖δx‖‖x‖

6 ‖A−1‖‖δb‖‖x‖

· ‖b‖‖b‖

= ‖A−1‖‖δb‖‖b‖

· ‖Ax‖‖x‖

6 ‖A‖ · ‖A−1‖︸ ︷︷ ︸=:cond(A)

‖δb‖‖b‖

Bemerkung 3 (Konditionszahl einer Matrix). Die Konditionszahl einer Matrix spielt dieentscheidende Rolle in der numerischen linearen Algebra. Betrachten wir etwa die Konditionie-rung derMatrix-Vektor-Multiplikation y = Ax, so erhalten wir bei gestörter Eingabe x = x+δxwieder

‖δy‖‖y‖

6 cond(A)‖δx‖‖x‖

.

Die Konditionszahl einer Matrix hängt von der gewählten Norm ab. Da jedoch alle Matrixnor-men im Rn×n äquivalent sind, sind auch alle Konditionsbegriffe äquivalent. Mit Satz 1 folgernwir für symmetrische Matrizen für den Spezialfall cond2(A):

cond2(A) = ‖A‖2 · ‖A−1‖2 =max{|λ|, λ Eigenwert von A}min{|λ|, λ Eigenwert von A}

.

21

Wir betrachten nun den Fall, dass die Matrix A eines linearen Gleichungssystems miteiner Störung δA versehen ist. Es stellt sich zunächst die Frage, ob die gestörte MatrixA = A+ δA überhaupt noch regulär ist.

Folie 15

Hilfsatz 1. Es sei durch ‖ · ‖ eine von der Vektornorm induzierte Matrixnorm gegeben.Weiter sei B ∈ Rn×n eine Matrix mit ‖B‖ < 1. Dann ist die Matrix I+ B regulär und esgilt die Abschätzung

‖(I+ B)−1‖ 6 1

1− ‖B‖.

Beweis. Es gilt‖(I+ B)x‖ > ‖x‖− ‖Bx‖ > (1− ‖B‖)‖x‖.

Da 1 − ‖B‖ > 0, ist durch I + B eine injektive Abbildung gegeben. Also ist I + B einereguläre Matrix. Weiter gilt:

1 = ‖I‖ = ‖(I+ B)(I+ B)−1‖ = ‖(I+ B)−1 + B(I+ B)−1‖> ‖(I+ B)−1‖− ‖B‖ ‖(I+ B)−1‖ = ‖(I+ B)−1‖(1− ‖B‖) > 0.

Mit diesem Hilfssatz können wir im Folgenden auch auf die Störung der Matrix einge-hen.

Folie 16

Satz 3 (Störung der Matrix). Es sei A ∈ Rn×n eine reguläre Matrix, b ∈ Rn. Weitersei x ∈ Rn die Lösung des linearen Gleichungssystems Ax = b und sei A = A+ δA einegestörte Matrix mit ‖δA‖ 6 ‖A−1‖−1. Für die gestörte Lösung x = x + δx von Ax = b

gilt:‖δx‖‖x‖

6cond(A)

1− cond(A)‖δA‖/‖A‖‖δA‖‖A‖

.

Beweis. Wir betrachten den Fall, dass die rechte Seite nicht gestört ist: δb = 0. Dann giltfür die Lösung x sowie die gestörte Lösung x und den Fehler δx := x− x:

(A+ δA)x = b

(A+ δA)x = b+ δAx⇒ δx = −[A+ δA]−1δAx.

22

Da laut Voraussetzung ‖A−1δA‖ 6 ‖A−1‖ ‖δA‖ < 1, folgt mit Hilfssatz 1:

‖δx‖ 6 ‖[I+A−1δA]−1A−1δA‖ ‖x‖ 6 ‖A−1‖1− ‖A−1δA‖

‖δA‖ ‖x‖

6cond2(A)

1− ‖A−1‖‖δA‖‖δA‖‖A‖

‖x‖

Das Ergebnis erhalten wir durch Erweitern mit ‖A‖/‖A‖.

Diese beiden Störungssätze können einfach kombiniert werden, um gleichzeitig die Stö-rung durch rechte Seite und Matrix abschätzen zu können:

Folie 17

Satz 4 (Störungssatz für lineare Gleichungssysteme). Es sei A ∈ Rn×n eine reguläreMatrix, b ∈ Rn die rechte Seite. Weiter sei x ∈ Rn die Lösung des linearen Gleichungs-systems Ax = b mit einer regulären Matrix A ∈ Rn×n. Für die Lösung x ∈ Rn desgestörten Systems Ax = b mit Störungen δb = b − b und δA = A − A gilt unter derVoraussetzung

‖δA‖ < 1

‖A−1‖die Abschätzung

‖δx‖‖x‖

6cond(A)

1− cond(A)‖δA‖/‖A‖

(‖δb‖‖b‖

+‖δA‖‖A‖

)mit der Konditionszahl

cond(A) = ‖A‖ ‖A−1‖.

Beweis. Wir kombinieren die Aussagen von Satz 2 und 3. Hierzu sei x die Lösung vonAx = b, x die gestörte Lösung Ax = b und x die Lösung zu gestörter rechter SeiteAx = b. Dann gilt:

‖x− x‖ 6 ‖x− x‖+ ‖x− x‖ 6 cond(A)‖δb‖‖b‖‖x‖+ cond(A)

1− cond(A)‖δA‖‖A‖

‖δA‖‖A‖

‖x‖.

Beachte ‖δA‖ < ‖A−1‖−1

0 6 cond(A)‖δA‖‖A‖

< ‖A‖ ‖A−1‖ 1

‖A‖ ‖A−1‖= 1.

Also gilt

cond(A) 6cond(A)

1− cond(A)‖δA‖‖A‖

.

Damit folgt die Aussage.

23

Mit diesem Ergebnis kehren wir zum einführenden Beispiel zurück:

A =

(0.988 0.9590.992 0.963

)⇒ A−1 ≈

(8302 −8267

−8552 8517

)In der maximalen Zeilensummennorm ‖ · ‖∞ gilt:

‖A‖∞ = 1.955, ‖A−1‖∞ ≈ 17069, cond∞(A) ≈ 33370.

Das Lösen eines linearen Gleichungssystems mit der Matrix A ist also äußerst schlechtkonditioniert. Hieraus resultiert der enorme Rundungsfehler im Beispiel zu Beginn desKapitels. Wir halten hier fest: Bei großer Konditionszahl ist die Konditionierung desProblems sehr schlecht, d.h., der große Fehler ist immanent mit der Aufgabe verbundenund nicht unbedingt auf ein Stabilitätsproblem des Verfahrens zurückzuführen.

24