Numerische Mathematik I · Einleitung Beispiel Die Methode versagt f¨ur das Polynom q(x) = x3 +x2 −2.1 Analysis: Es existiert genau eine reelle Nullstelle im Intervall [1,2]

Numerische Mathematik I

(Folien zur Vorlesung)Joachim Stockler

http://www.mathematik.tu-dortmund.de/lsviii/new/de/lehrveranstaltungen/wise1213/numerik.html

Auszuge aus dem Vorlesungsskript von H. Blum, J. Fliege, T. Suttmeier ausdem WS 2010/11 und Material der Vorlesung von M. Charina aus dem WS

2009/10 werden verwendet.

Numerische Mathematik I 0

Einleitung

Kapitel 0. Einleitung

Lineare Algebra, Analysis,...:

(I) Losbarkeit eines mathematischen Problems: Existenz, Eindeutigkeit vonLosungen

Numerik:

(II) Kondition (= naturliche Stabilitat) des mathematischen Problems: welchenEinfluss haben Anderungen der gegebenen Daten auf die Losung

(III) Numerische Algorithmen zur Losung des mathematischen Problems:

(a) Entwicklung der Algorithmen und Implementierung in einerProgrammierumgebung

(b) Komplexitat der Algorithmen (bezogen auf Computerarchitektur)(c) Kondition der Algorithmen (= numerische Stabilitat)(d) Bei naherungsweiser Berechnung der Losung: Fehleranalyse, Abbruchkriterien

fur Iterationsverfahren


Einleitung Beispiel

0.1 Beispiel Nullstellenberechnung eines Polynoms

Fundamental-Satz der Algebra:

Jedes Polynom n−ten Grades hat genau n komplexe Nullstellen unter

Berucksichtigung der Vielfachheit.

Gegeben: p(x) = x3 + x2 − 2

Losungsmethode der Schule: Raten einer Nullstelle und anschließendeFaktorisierung mit dem Hornerschema: p(x) wird berechnet in der Formp(x) = ((x + 1)x + 0)x − 2:

1 1 0 −2 ← Koeffizienten von p

x = 1 1 2 2 ← x · Zahl links unterhalbSumme 1 2 2 0 = p(1)

Die letzte Zeile im Schema liefert die Koeffizienten der Faktorisierung

p(x) = (x − 1)(x2 + 2x + 2) = (x − 1)(x + 1 + i)(x + 1− i)


Einleitung Beispiel

Die Methode versagt fur das Polynom q(x) = x3 + x2 − 2.1

Analysis: Es existiert genau eine reelle Nullstelle im Intervall [1, 2](Zwischenwertsatz und Monotonie).

Numerik: Newtonverfahren zur naherungsweisen Berechnung dieser Nullstelle:

Mathematische Notation(Pseudo-Code):

Wahle Startwert x0

Fur k = 0, 1, 2, . . .:

berechne xk+1 := xk − q(xk)/q′(xk)

bis k > kmax oder |q(xk+1)| ≤ tol.

Ad-hoc Programmierung in Mat-lab/Octave

kmax=10; tol=1e-12; format long

k=0; x=1; q=x∧3+x∧2-2.1;

while (k <= kmax) && (abs(q) > tol)

qs=3*x∧2+2*x;

x=x-q/qs;

k=k+1; q=x∧3+x∧2-2.1;

end


Einleitung Beispiel

0.2 Beispiel Losung linearer Gleichungssysteme

Die eindeutige Losung von

[2.0001 1.99991.9999 2.0001

] [x1x2

]=

[11

]

ist [x1, x2]T = [0.25, 0.25]T .

Die Anderung der rechten Seite auf [1.0001, 0.9999]T , also um 0.1 Promillein jeder Komponente, liefert die neue Losung [x1, x2]

T = [0.75, −0.25]T .Dies ist eine relative Anderung der Komponenten um 200 Prozent.

Deshalb ist dieses mathematische Problem “schlecht konditioniert”, “nicht stabil”.


Einleitung Beispiel

0.3 Beispiel Determinantenberechnung

Berechnung von detA fur A ∈ Rn×n.

Leibnizregel:

detA =∑

σ∈Sn

ǫσ a1,σ1 · · · an,σn

mit ǫσ = 1 oder −1 fur die Permutation σ gerader oder ungerader Ordnung(z.B. Regel von Sarrus fur n = 3).Aufwand: n! Summanden, die jeweils n − 1 Multiplikationen erfordern.IMMENS!

rekursive Verwendung des Entwicklungssatzes von Laplace:

detA =n∑

k=1

(−1)1+ka1,k detA1,k ,

wobei A1,k durch Streichen der 1. Zeile und der k-ten Spalte von A entsteht.Aufwand: Viel geringer, wenn bei der Rekursion die Determinante derTeilmatrizen, die mehrfach auftreten, nur einmal berechnet werden (z.B. inMaple)


Einleitung Beispiel

A mit dem Gauß-Algorithmus in Dreiecksgestalt uberfuhren:

A −→ R =

r1,1 · · · r1,n. . .

...0 rn,n

Je nach Anzahl der Zeilen- und Spalten-Permutationen ist

detA = ± detR = ±r1,1r2,2 · · · rn,n.

Aufwand: n3/3 fur Gauß-Algorithmus und n − 1 Multiplikationen fur detR .Dies ist das effizienteste Verfahren.


Einleitung Beispiel

0.4 Beispiel Grenzwertberechnung durch Einsetzen?

Berechne: α = limx→0

tan x − x

x3.

Es ist α = 1/3 (rechne z.B. mit de l’Hospital oder Taylorentwicklung desZahlers)

Numerische Rechnung mit Matlab ergibt fur

x = 10−k mit k = 1 : 9

die Ergebnisse

0.33467208545054, 0.33334666720702, 0.33333346673159,0.33333333651891, 0.33333287573298, 0.33330746474457,0.33087224502121, 0, 0

Verwendung der Taylor-Reihe

tan x = x +1

3x3 +

2

15x5 +

17

315x7 + · · ·

macht die Losung ganz einfach.

Das mathematische Problem ist gut gestellt, aber die Berechnung uber denFunktionsterm ist numerisch instabil.Numerische Mathematik I 7

Einleitung Beispiel

Kapitel 1. Fehleranalyse

Inhalt:

1.1 Zahldarstellung und Rundungsfehler

1.2 Konditionierung mathematischer Aufgaben

1.3 Stabilitat numerischer Algorithmen


Einleitung Beispiel

Prolog: Arten von Fehlern

Eingangsfehler (Datenfehler)Messungenauigkeiten, Erhebungsfehler

Diskretisierungsfehler

Riemannsche Summe als Approximation des IntegralsDifferenzenquotient als Approximation der Ableitungn−te Partialsumme als Approximation des Grenzwertes der Reihe

Rundungsfehler, z.B. bei Dezimalzahlen mit 5 Nachkommastellen

1

3≈ 0.33333

AbbruchfehlerAbbruch von Iterationen (siehe Beispiel 0.1) nach k Schritten

Menschlicher Irrtum oder maschinelle Fehlfunktion:Kein Gegenstand der Numerik, Kontrollmaßnamen


Zahldarstellung und Rundungsfehler Definition (Gleitkommazahlen):

1.1 Zahldarstellung und Rundungsfehler

1.1.1 Definition (Gleitkommazahlen):

Die Menge fl = fl(b, r , s) von Gleitkommazahlen zur Basis b ∈ N, b ≥ 2, mitMantissenlange r ∈ N und Exponentenlange s, besteht aus allen reellen Zahlender Form

±

r∑

j=1

mj · b−j

· bE , E = ±

s−1∑

k=0

ek · bk ,

mit mj , ek ∈ 0, . . . , b − 1.

Die Zahl x ∈ fl heißt normalisiert, wenn m1 6= 0.


Zahldarstellung und Rundungsfehler Bemerkung:

(i) Moderne Rechner verwenden b = 2, 10, 16.(ii) Die Verwendung der Gleitkommazahlen im numerischen Rechnen ist

wesentlich, um Zahlen unterschiedlicher Große verarbeiten zu konnen.(iii) Die Menge fl = fl(b, r , s) ist endlich! Sie ist Teilmenge des zulassigen

Bereichs fur Gleitkommazahlen

D(fl) := [amin, anegmax ] ∪ 0 ∪ [aposmin, amax ]

mitamin,max = ±(1− b−r )bb

s−1 und aneqmax,posmin = ±b−bs

.

(iv) In jedem halboffenen Intervall IE := [bE−1, bE ) mit −bs + 1 ≤ E ≤ bs liegtdie gleiche Anzahl (b − 1)br−1 von Gleitkommazahlen. Diese sind

bE−1 = 0. 100 . . .0︸︷︷︸r

·bE ,

bE−1 + bE−r = 0. 100 . . .1︸︷︷︸r

·bE ,

bE−1 + 2bE−r ,...bE − bE−r .

Der Abstand der Gleitkommazahlen in diesem Intervall ist bE−r .Numerische Mathematik I 11

Zahldarstellung und Rundungsfehler Definition (Rundungsoperator):

1.1.3 Definition (Rundungsoperator):

Es seien b ∈ N gerade sowie r , s ∈ N gegeben. Der Rundungsoperatorrd : D(fl)→ fl(b, r , s) ist definiert durch rd(0) = 0 und fur jede reelle Zahl

x = ±

∞∑

j=1

mj · b−j

· bE 6= 0

mit m1 6= 0 und E ∈ 0,±1, . . . ,±bs − 1 durch

rd(x) = sgn(x) ·

r∑

j=1

mj · b−j

· bE , falls mr+1 <

b2 ,

r∑

j=1

mj · b−j + b−r

· bE , sonst.

Hierdurch wird |x − rd(x)| = mina∈fl |x − a| erfullt.

Bemerkung: Fur ungerades b kann rd(x) nicht allein anhand der Mantissenstelle mr+1 bestimmt

werden.Numerische Mathematik I 12

Zahldarstellung und Rundungsfehler Satz:

1.1.4 Satz:

Es seien b ∈ N gerade, r , s ∈ N. Dann gilt fur x ∈ D(fl) \ 0

(i) fur den absoluten Rundungsfehler |x − rd(x)| ≤1

2bE−r

(ii) fur den relativen Rundungsfehler

∣∣∣∣x − rd(x)

x

∣∣∣∣ ≤1

2b−r+1.

1.1.5 Korollar:

Unter den Voraussetzungen von Satz 1.1.4 gilt

rd(x) = x(1 + δx) mit |δx | ≤1

2b−r+1 =: eps.

Die Zahl eps wird die Maschinengenauigkeit oder relative Rechengenaugkeit derGleitkommaarithmetik genannt.


Zahldarstellung und Rundungsfehler Definition:

1.1.6 Definition:

Bei dem Standardmodell der Gleitkommaarithmetik sind dieGleitkommaoperationen

⊕,⊖,⊗,⊘ : fl × fl → fl

definiert durch

x ⊙ y := rd(x · y) = (x · y)(1 + δ), |δ| ≤ eps, ⊙ ∈ ⊕,⊖,⊗,⊘.

ACHTUNG: Die Rechengesetze (Assoziativgesetz, Distributivgesetze) gehenverloren!


Konditionierung eines mathematischen Problems

1.2 Konditionierung eines mathematischen Problems

Aufgabe: Auswertung einer Funktion f : X → Y in einem Punkt x ∈ X . Hier sindX ,Y Teilmengen eines Vektorraums.

Problem: Einfluss von Fehlern der Eingabedaten bei exakter Rechnung

Eingabedaten Ausgabedaten

x ∈ X Problem y = f (x)mit Fehler → f → mit Fehler∆x = x − x ∆y = y − y

Wir werden die “Verstarkungsfaktoren” k(x) in

‖∆y‖

‖y‖≤ k(x)

‖∆x‖

‖x‖

oder, im Fall y ∈ Rm und x ∈ Rn, die einzelnen Faktoren in

|∆yi |

|yi |≤

n∑

j=1

kij(x)|∆xj |

|xj |

beschreiben.Numerische Mathematik I 15

Konditionierung eines mathematischen Problems Definition: Norm

1.2.1 Definition: Norm

Sei V ein Vektorraum uber dem Korper K = R oder K = C. Eine Abbildung‖ · ‖ : V → R heißt eine Norm auf V , falls

(N1) ‖v‖ ≥ 0 fur alle v ∈ V , sowie (‖v‖ = 0⇔ v = 0);

(N2) ‖αv‖ = |α|‖v‖ fur alle α ∈ K und v ∈ V ;

(N3) ‖v + w‖ ≤ ‖v‖+ ‖w‖ fur alle v ,w ∈ V .

Bemerkung:

(i) (N2) nennt man positive Homogenitat, (N3) ist die Dreiecksungleichung.

(ii) Fur jede Norm ‖ · ‖ gilt außerdem

(N4) ‖v ± w‖ ≥∣∣∣‖v‖ − ‖w‖

∣∣∣, v ,w ∈ V .


Konditionierung eines mathematischen Problems Hilfssatz:

1.2.2 Hilfssatz:

Sei V ein Vektorraum uber dem Korper K und ‖ · ‖ : V → R eine Norm.

(i) Durch d : V × V → R mit d(v ,w) = ‖v − w‖ ist eine Metrik auf Vdefiniert, d.h.

(M1) d(v ,w) ≥ 0 fur alle v ,w ∈ V , sowie (d(v ,w) = 0⇔ v = w);(M2) d(v ,w) = d(w , v) fur alle v ,w ∈ V ;(M3) d(u,w) ≤ d(u, v) + d(v ,w) fur alle u, v ,w ∈ V .

(ii) Die Norm ‖ · ‖ : V → R ist eine gleichmaßig stetige Funktion.


Konditionierung eines mathematischen Problems Beispiele von Normen auf Rn :

1.2.3 Beispiele von Normen auf Rn:

Die ℓp-Normen mit 1 ≤ p ≤ ∞: euklidische Norm (p = 2), Maximumnorm(p =∞) und ℓ1-Norm als Spezialfalle

1.2.4 Satz:

Auf dem endlich-dimensionalen Vektorraum Kn sind alle Normen aquivalent, d.h.:Zu je zwei Normen ‖ · ‖ und ‖ · ‖′ gibt es positive Konstanten m,M mit denen gilt

m‖x‖′ ≤ ‖x‖ ≤ M‖x‖′ , x ∈ Kn.


Konditionierung eines mathematischen Problems Bemerkung:

1.2.5 Bemerkung:

‖ · ‖ sei eine Norm auf Kn. Die Konvergenz einer Vektorfolge(x (k)

)

k∈N

gegen

einen Vektor x ∈ Kn ist erklart durch

x (k) → x ⇐⇒ limk→∞

‖x (k) − x‖ = 0.

Dies ist nach Satz 1.2.4 gleichbedeutend mit der komponentenweisen Konvergenz

limk→∞

x(k)j = xj , j = 1, . . . , n.


Konditionierung eines mathematischen Problems Definition (absolute und relative Fehler):

1.2.6 Definition (absolute und relative Fehler):

Sei V ein normierter Vektorraum mit zugehoriger Normen ‖ · ‖. Weiter seienx , x ∈ V sowie ∆x := x − x . Dann heißt

‖∆x‖ = ‖x − x‖

der absolute Fehler von x an x . Im Fall x 6= 0 heißt

‖∆x‖

‖x‖

der relative Fehler von x an x .


Konditionierung eines mathematischen Problems Definition (Konditionszahl):

1.2.7 Definition (Konditionszahl):

Seien V ,W normierte Vektorraume mit zugehorigen Normen ‖ · ‖V bzw. ‖ · ‖W .Weiter sei f : V →W eine Funktion und x ∈ V \ 0 sowie f (x) 6= 0.

Die Zahl k(x) ≥ 0 heißt Konditionszahl (des relativen Fehlers) von f an der Stellex , wenn fur kleine Fehler ‖x − x‖V gilt

‖f (x)− f (x)‖W‖f (x)‖W

≤ k(x) ·‖x − x‖V‖x‖V

+ o

(‖x − x‖V‖x‖V

).


Konditionierung eines mathematischen Problems Bezeichnungen (Landau-Symbole):

1.2.8 Bezeichnungen (Landau-Symbole):

Es seien V ,W normierte Vektorraume, g : V →W und h : V → R+ seienFunktionen. Wir sagen:

g ist von der Ordnung groß O(h) bei x = 0, geschrieben g(x) = O(h(x)) furx → 0, wenn

∃C , ǫ > 0 : ‖x‖V < ǫ ⇒ ‖g(x)‖W ≤ Ch(x);

g ist von der Ordnung klein o(h) bei x = 0, geschrieben g(x) = o(h(x)) furx → 0, wenn

limx→0

1

h(x)‖g(x)‖W = 0.

Bemerkung: Die Bezeichnung g(x) = O(h(x)) besagt

lim supx→0

1

h(x)‖g(x)‖W < ∞.


Konditionierung eines mathematischen Problems Satz (Konditionszahl differenzierbarer Funktionen):

1.2.9 Satz (Konditionszahl differenzierbarer Funktionen):

Es sei Ω ⊂ Kn offen und f = (f1, . . . , fm) : Ω→ K

m stetig differenzierbar. Danngilt fur x mit lauter von 0 verschiedenen Komponenten und fi (x) 6= 0

∣∣∣∣fi (x)− fi (x)

fi (x)

∣∣∣∣ ≤n∑

j=1

ki ,j(x) ·

∣∣∣∣xj − xj

xj

∣∣∣∣ + o

(∣∣∣∣xj − xj

xj

∣∣∣∣)

mit den Konditionszahlen bzgl. der relativen Eingangsfehler

ki ,j(x) :=

∣∣∣∣∂fi∂xj

(x) ·xj

fi (x)

∣∣∣∣ .


Konditionierung eines mathematischen Problems Bemerkung:

1.2.10 Bemerkung: Durch Verwendung der Richtungsableitung

∂v fi (x) = limh→0

fi (x + hv)− fi (x)

h

in Richtung v = 1‖x−x‖2

(x − x) erhalt man

∣∣∣∣fi (x)− fi (x)

fi (x)

∣∣∣∣ ≤ k(x) ·‖x − x‖2‖x‖2

+ o

(‖x − x‖2‖x‖2

)

mit

k(x) = max‖v‖2=1

|∂v fi (x)|‖x‖2|fi (x)|

.

Dies macht fur alle x 6= 0 Sinn.


Konditionierung eines mathematischen Problems Bezeichnung (Konditionierung math. Probleme):

1.2.11 Bezeichnung (Konditionierung math. Probleme):

Man nennt das Problem der Berechnung von y = f (x), x ∈ Ω, schlechtkonditioniert, wenn mindestens ein ki ,j ≫ 1 ist; andernfalls nennt man es gutkonditioniert. Im Fall ki ,j < 1 spricht man von Fehlerdampfung und im Fallki ,j > 1 von Fehlerverstarkung


Konditionierung eines mathematischen Problems Beispiel (Konditionierung arithmetischer Grundoperationen):

1.2.12 Beispiel (Konditionierung arithmetischer Grundoperationen):

Die Addition y = f (x1, x2) = x1 + x2, x1, x2 ∈ R \ 0, mit

k1(x1, x2) =

∣∣∣∣∂f

∂x1(x) ·

x1

f (x)

∣∣∣∣ =∣∣∣∣

x1

x1 + x2

∣∣∣∣

k2(x1, x2) =

∣∣∣∣∂f

∂x2(x) ·

x2

f (x)

∣∣∣∣ =∣∣∣∣

x2

x1 + x2

∣∣∣∣

ist schlecht konditioniert fur x1 ≈ −x2.

Die Multiplikation y = f (x1, x2) = x1 · x2 mit

k1(x1, x2) =

∣∣∣∣∂f

∂x1(x) ·

x1

f (x)

∣∣∣∣ =∣∣∣∣x2 ·

x1

x1 · x2

∣∣∣∣ = 1

k2(x1, x2) =

∣∣∣∣∂f

∂x2(x) ·

x2

f (x)

∣∣∣∣ =∣∣∣∣x1 ·

x2

x1 · x2

∣∣∣∣ = 1

ist generell gut konditioniert. Dasselbe gilt fur die Division.


Konditionierung eines mathematischen Problems Beispiel:

1.2.13 Beispiel: Konditionierung von y = f (x1, x2) = x21 − x22 .

Seien x1, x2 ∈ R \ 0. Das Problem der Berechnung von x21 − x22 mit

k1(x1, x2) =

∣∣∣∣∂f

∂x1(x) ·

x1

f (x)

∣∣∣∣ =

∣∣∣∣∣∣∣

2

1−(

x2x1

)2

∣∣∣∣∣∣∣

k2(x1, x2) =

∣∣∣∣∂f

∂x2(x) ·

x2

f (x)

∣∣∣∣ =

∣∣∣∣∣∣∣

2

1−(

x1x2

)2

∣∣∣∣∣∣∣

ist schlecht konditioniert fur x1 ≈ ±x2.


Konditionierung eines mathematischen Problems Beispiel: Losung quadratischer Gleichungen

1.2.14 Beispiel: Losung quadratischer GleichungenEs seien p, q ∈ R, q 6= 0. Lose y2 − py + q = 0:

Vietascher Wurzelsatz: y1,2(p, q) =p2 ±

√p2

4 − q, sowie p = y1 + y2 undq = y1 · y2.

Mit y1 − y2 = 2√

p2

4 − q ist

∂y1∂p

=y1

y1 − y2,

∂y2∂p

= −y2

y1 − y2,

∂y1∂q

=−1

y1 − y2,

∂y2∂q

=1

y1 − y2,

also

k1,1(p, q) =

∣∣∣∣∂y1∂p

(p, q) ·p

y1(p, q)

∣∣∣∣ =∣∣∣∣y1 + y2

y1 − y2

∣∣∣∣

k1,2(p, q) =

∣∣∣∣∂y1∂q

(p, q) ·q

y1

∣∣∣∣ =∣∣∣∣

y2

y1 − y2

∣∣∣∣

und analog fur k2,1 und k2,2. Also ist die Berechnung von y1, y2 schlechtkonditioniert fur y1 ≈ y2.


Numerische Stabilitat von Algorithmen Definition:

1.3 Numerische Stabilitat von Algorithmen

1.3.1 Definition:

Ein Algorithmus zur Auswertung der Funktion

f : Ω→ Rm, Ω ⊂ R

n offen

ist eine Zerlegungf = φ(r) φ(r−1) · · · φ(0)

in elementare Abbildungen (arithmetische Grundoperationen oderStandardfunktionen)

φ(i) : Ωi → Ωi+1, Ωi ⊂ Rni , i = 0, . . . , r .

Er fuhrt die Eingabedaten x uber eine Kette von Zwischenergebnissen

x =: x (0) 7→ φ(0)(x (0)) =: x (1) 7→ . . . 7→ φ(r)(x (r)) =: x (r+1) = y

zu y = f (x).

Bemerkung: Ein Rundungsfehler, der bei Berechnung von x i+1 = φ(i)(x (i)) auftritt, geht in dieNumerische Mathematik I 29

Numerische Stabilitat von Algorithmen Definition und Satz (numerische Stabilitat)

1.3.2 Definition und Satz (numerische Stabilitat)

Ein Algorithmus φ(r) · · · φ(0) heißt numerisch stabil, wenn der im Verlaufe derAusfuhrung akkumulierte Fehler den durch die Konditionierung des Problemsy = f (x) bedingten unvermeidbaren Problemfehler nicht wesentlich ubersteigt.

Der Algorithmus ist numerisch stabil, wenn alle Restabbildungen

φ(r) · · · φ(i+1), i = 0, . . . , r − 1,

gut konditioniert sind.


Numerische Stabilitat von Algorithmen Beispiel:

1.3.3 Beispiel: Numerische Stabilitat von

y = f (x1, x2) = x21 − x22︸︷︷︸

Alg. A

= (x + 1)(x − 1)︸︷︷︸

Alg. B.

A Mit EXAKTEN Eingabedaten x1, x2 und relativen Rundungsfehlern |δk | ≤ eps ist

yA = (x1 ⊙ x1)⊖ (x2 ⊙ x2)

= (x21 (1 + δ1)− x22 (1 + δ2))(1 + δ3)

= x21 − x22 + δ1x21 − δ2x

22 + δ3(x

21 − x22 ) +O(eps2).

Der relative Fehler bei Weglassen des O(eps2)-Terms ist

|yA − y |

|y | eps ·

x21 + x22 + |x21 − x22 |

|x21 − x22 |= eps ·

(

1 +

∣∣∣∣

1 + (x2/x1)2

1− (x2/x1)2

∣∣∣∣

)

;

der Rundungsfehler wirkt sich stark aus bei x1 ≈ ±x2 und hat die gleiche Großenordnungwie die Konditionszahl in Beispiel 1.2.13; der Alg. ist also numerisch stabil.

B Mit EXAKTEN Eingabedaten x1, x2 und relativen Rundungsfehlern |δk | ≤ eps ist

yB = (x1 ⊕ x2)⊙ (x1 ⊖ x2)

= (x1 + x2)(1 + δ1)(x1 − x2)(1 + δ2)(1 + δ3)

= x21 − x22 + (δ1 + δ2 + δ3)(x21 − x22 ) +O(eps2).

Der relative Fehler bei Weglassen des O(eps2)-Terms ist

|yB − y |

|y | 3eps;

der Rundungsfehler wirkt sich also nicht stark aus. Algorithmus B ist besser!


Numerische Stabilitat von Algorithmen Beispiel: Losung quadratischer Gleichungen

1.3.4 Beispiel: Losung quadratischer GleichungenEs seien p, q ∈ R, q 6= 0 und q ≪ p2/4.

Lose y2 − py + q = 0, also berechne y1,2 = p2±

√p2

4− q.

Das Problem ist unter diesen Voraussetzungen gut konditioniert (wegen y1/y2 ≫ 1).

Berechnung beider Losungen

u = (p ⊙ p)⊘ 4, v = u ⊖ q, w = SQRT (v).

Falls p < 0, setze

Alg. A: y2 = (p ⊘ 2)⊖ w , y1 = (p ⊘ 2) ⊕ w

Alg. B: y2 = (p ⊘ 2)⊖ w , y1 = q ⊘ y2

Abgekurzte Rundungsfehleranalyse: “Restabbildungen”

Rundungsfehler an p,w ubertragen sich auf y2 gemaß

|∆y2 |

|y2|

∣∣∣∣

p/2

p/2 − w

∣∣∣∣

︸︷︷︸

≤1

∣∣∣∣

∆p

p

∣∣∣∣+

∣∣∣∣

w

p/2 − w

∣∣∣∣

︸︷︷︸

≤1

∣∣∣∣

∆w

w

∣∣∣∣ ≤ 2eps.

Alg. A ergibt fur y1

|∆y1 |

|y1|

∣∣∣∣

p/2

p/2 + w

∣∣∣∣

︸︷︷︸

≫1

∣∣∣∣

∆p

p

∣∣∣∣+

∣∣∣∣

w

p/2 + w

∣∣∣∣

︸︷︷︸

≫1

∣∣∣∣

∆w

w

∣∣∣∣

mit großen Verstarkungsfaktoren im Fall |q| ≪ p2/4, also w ∼ |p|/2.


Numerische Stabilitat von Algorithmen Beispiel: Losung quadratischer Gleichungen

Alg. B ergibt fur y1|∆y1 |

|y1|

∣∣∣∣

∆q

q

∣∣∣∣+

∣∣∣∣

∆y2

y2

∣∣∣∣

mit Faktor 1.

Daher ist Alg. B numerisch stabil, Alg. A ist es nicht.


Documents

Numerische Mathematik I · Einleitung Beispiel Die Methode versagt f¨ur das Polynom q(x) = x3 +x2 −2.1 Analysis: Es existiert genau eine reelle Nullstelle im Intervall [1,2]