<<

. 6
( 31 .)



>>



j=1
: der relative Fehler, (i = 1, . . . , n),
¨
y =f(x)
y =f(x)

y =f(x)




Abbildung 2.2: Fehlerein¬‚usse.




‚xj
‚fi (x)
Fehlerfortp¬‚anzung, Kondition




liefert fur den absoluten Fehler y = y ’ y die Approximation


xj ,
i = 1, . . . , m.
Wir hatten festgestellt, dass bei der Berechnung mit dem Computer verschiedene




Die Funktion f sei eine C 1 “Funktion. Die Taylor“Entwicklung erster Ordnung
begrenzt. Anstelle einer exakten Rechnung y = f (x) wird man daher eine Appro-
genannt werden. Die Genauigkeit der Berechnung von y = f (x) wird durch die
so bezeichnen wir mit x die Eingabedaten, w¨hrend y Ausgabe“ oder Resultatdaten




Wir befassen uns zun¨chst damit, wie sich Fehler in x auf das Ergebnis y = f (x)
Fehler auftreten konnen. Betrachten wir fur D ‚ IRn und f : D ’ IRm das
Fehleranalyse 25




Fur den relativen Fehler erhalt man dann
¨ ¨
n
yi ‚fi (x) xj xj
(2.6) ≈ · , xj , yi = 0.
yi ‚xj fi (x) xj
j=1

De¬nition 2.22 (Kondition).
1. Die Zahlen
‚fi (x) xj
(2.7) kij (x) =
‚xj fi (x)
heißen Verstarkungsfaktoren bzw. (relative) Konditionszahlen.
¨
2. Das Problem ™Berechne y = f (x)™ heißt gut konditioniert, falls alle kij (x)
die Gr¨ßenordnung 1 haben. Andernfalls heißt das Problem schlecht kondi-
o
tioniert.
Zuerst untersuchen wir damit die arithmetischen Operationen +, ’, —, /.
Multiplikation: y = f (x1 , x2 ) = x1 — x2
Es gilt k11 (x) = k12 (x) = 1: gutartig.

Division: y = f (x1 , x2 ) = x1 /x2
Es gilt k11 (x) = k12 (x) = 1: gutartig.

Addition, Subtraktion: y = f (x1 , x2 ) = x1 + x2
Es gilt
x1 x2
k11 (x) = , k12 (x) =
x1 + x2 x1 + x2
Das Problem ist schlecht konditioniert, falls x1 ≈ ’x2 . Daher ist die Subtraktion
nahezu gleichgroßer Zahlen mit gleichen Vorzeichen schlecht konditioniert.
Dieses Ph¨nomen heißt Ausl¨schung.
a o
Beispiel 2.23.
1.31 ’ 1.25 = 0.06
1.32 ’ 1.24 = 0.08 (St¨rrechnung)
o
Es gilt:
x = (1.31, ’1.25)
y = x1 + x2 = 0.06
x = (0.01, 0.01)
xi
¤ 0.008, d.h. relativer Eingabefehler ca. 0.8%
xi
k1,i (x) ¤ 22, i = 1, 2
26 Fehleranalyse




Der relative Fehler im Ergebnis ist ca. 40 mal (Summe) gr¨ßer als der relative
o
Fehler in den Daten.

Wurzel: y = f (x1 ) = x1 , x1 > 0
¨
Es gilt k(x) = 1/2: gutartig. (Ubung)


Bemerkung 2.24. Bei einigen Problemen kann die Ausl¨schung durch geeignete
o
Umformulierung vermieden werden, vgl. die nachfolgenden Beispiele.


2.6 Algorithmen
Ein Algorithmus zur Berechnung der L¨sung y = f (x) eines Problems ist eine
o

Sequenz von endlich vielen ™elementaren Operationen™ (+, ’, —, /, cos(x), x, . . .).
Es gibt i.A. mehrere Anordnungen der Rechenschritte, welche zum gleichen Er-
gebnis y = f (x) fuhren. In jedem Rechenschritt fallen Rundungsfehler an. Dabei
¨
kann der Fall auftreten, daß bei der L¨sung eines an sich gut konditionierten
o
Problems eine ungunstige Anordnung der Rechenschritte zum Aufschaukeln der
¨
Rundungsfehler fuhrt. Der zugehorige Algorithmus ist numersich instabil.
¨ ¨
Beispiel 2.25. Gesucht ist die betragskleinere L¨sung von x2 + 2px ’ q = 0 mit
o
p >> q.
Die exakte L¨sung ist gegeben durch
o

p2 + q
(2.8) y = f (p, q) = ’p +
¨
Fur die Konditionszahlen gilt: (Ubung)
¨

(2.9) kp (p, q) < 1, kq (p, q) < 1, (wegen p >> q)

also ist die Aufgabe gut konditioniert fur q > 0.
¨
2
(W¨re jedoch etwa q ≈ ’p , w¨re das Problem schlecht konditioniert.)
a a

Beispiel 2.26. Wir betrachten erneut die Aufgabenstellung aus Beispiel 2.25 und
untersuchen zwei Algorithmen:
Algorithmus 1: y = f (p, q) = ’p + p2 + q

s := p — p
t := s + q

u := t
y := ’ p + u
Fehleranalyse 27




Fur p >> q tritt in y := ’p + u Ausl¨schung auf, der Algorithmus ist in
o
¨
diesem Fall schlecht konditioniert, obgleich das Problem gut konditioniert ist.
q
Algorithmus 2: y = f (p, q) = √ 2
p+ p +q

s := p — p
t := s + q

u := t
v := p + u
y := q/v


Algorithmus 2 ist fur p >> q gutartig.
¨
Zahlenwerte: p = 6.0002, q = 0.01 und einer Mantissenl¨nge von 5 erhalten wir
a
Algorithmus 1: 0.0008
Algorithmus 2: 0.00083326
exakte L¨sung: 0.00083325 (gerundet auf Mantissenl¨nge)
o a
¨
(Ubung: Nachrechnen)
28 Fehleranalyse
Kapitel 3

Lineare Gleichungssysteme

3.1 Einfuhrung und Aufgabenstellung
¨
Algorithmen zur Losung linearer Gleichungssysteme bilden die Basis fur viele
¨ ¨
Anwendungen der Numerik.
Aufgabenstellung: Sei A eine (m, n)“Matrix und sei b ∈ IRm . Gesucht ist ein
Vektor x ∈ IRn , welcher das lineare Gleichungssystem (LGS)

(3.1) Ax = b

lost.
¨
In der Numerik unterscheidet man in direkte Methoden zur L¨sung von Ax = b,
o
bei der eine L¨sung x in endlich vielen Schritten berechnet wird und indirekte
o
Methoden, bei denen eine N¨herungsl¨sung x von Ax = b iterativ bestimmt wird.
a o
In diesem Kapitel werden wir uns mit den direkten Methoden auseinandersetzen,
die indirekten Methoden sind dann Bestandteil der Numerik II.

Bemerkung 3.1. Abh¨ngig vom ”Aussehen“ der Koe¬zientenmatrix A unter-
a
scheidet man in

kleine - große Systeme
symmetrische - nichtsymmetrische Matrizen
mit - ohne Bandstruktur
schwach - vollbesetzte Matrizen

Danach richtet sich auch die Auswahl der Verfahren.

Beispiel 3.2. Wir betrachten das Gleichstromnetzwerk in Abbildung 3.1.
Nach den Kirchhoffschen Gesetzen mussen sich zun¨chst an allen Knoten
a
¨

29
30 Lineare Gleichungssysteme




Abbildung 3.1: Gleichstromnetzwerk.


die eingehenden und die ausgehenden Str¨me zu Null erg¨nzen. Fur Anfang und
o a ¨
Ende erhalten wir
I1 + I2 = I = I4 + I5 ,
fur Oben und Unten
¨

I2 = I3 + I4 und I1 + I3 = I5 .

Daruberhinaus mussen sich die Spannungen in den beiden Dreiecken zu Null sum-
¨ ¨
mieren, nach dem Ohmschen Gesetz (U = R · I) fuhrt dies fur die bekannten
¨ ¨
Widerst¨nde Ri auf die beiden Gleichungen
a

R2 I2 + R3 I3 ’ R1 I1 = 0 und R3 I3 + R5 I5 ’ R4 I4 = 0

Wir erhalten somit nach Umsortierung ein lineares Gleichungssystem der Form
Ax = b:
I1 + I2 =I
I4 + I5 =I
I2 ’ I3 ’ I4 =0
I1 + I3 ’ I5 =0
’R1 I1 + R2 I2 + R3 I3 =0
’R3 I3 + R4 I4 ’ R5 I5 = 0
W¨hrend man das letzte Beispiel sicher noch von Hand l¨sen kann, werden
a o
gr¨ßere Probleme am Computer gel¨st, vgl. Abbildung 3.2.

<<

. 6
( 31 .)



>>