<<

. 12
( 31 .)



>>

¬ ·
¬ ·
¬ — — — — —·
¬ ·
¬ ·
— — — —

———

hat die Bandbreite m = 2.

Ein Blick auf den Gauß“Algorithmus zeigt leicht die folgende Aussage:

Satz 3.25. Besetzt die Matrix A mit der Bandbreite m eine LR-Zerlegung A =
LR, so haben L und R ebenfalls die Bandbreite m, denn es gilt

lik = 0 fur i, k mit i ’ k > m,
¨
rik = 0 fur i, k mit k ’ i > m.
¨

Korollar 3.26. Die Linksdreiecksmatrix L der Cholesky-Zerlegung A = LLT ei-
ner positiv de¬niten Bandmatrix mit der Bandbreite m besitzt ebenfalls Bandbreite
m.
50 Lineare Gleichungssysteme




Besonders einfach zu behandelnde LGS erhalt man fur tridiagonale Matrizen A
¨ ¨
der Bandbreite m = 1. Zu l¨sen sei das LGS Ax = d mit
o
« 
a1 b1
« 
¬ ·
¬ c2 a2 b2 d1
·
¬ · ¬.·
¬ ·
.. .. .. d=¬ . ·
A=¬ ·,
. . . .
¬ ·
¬ ·
cn’1 an’1 bn’1 dn
 
cn an

Es existiere die LR-Zerlegung A = LR. Nach Satz 3.25 sind L und R bidiagonal
und k¨nnen in der Form angesetzt werden
o
«  « 
1 m1 r1
¬l 1 · ¬ ·
¬2 · m2 r2
¬ ·
¬ · ¬ ·
¬ ·
l3 1 R=¬ ·.
L=¬ ·, ¬ ·
¬ · ¬ ·
.. ..
¬ · mn’1 rn’1
 
. .
 
mn
ln 1

Die Ausmultiplikation A = LR fuhrt auf die Beziehung ri = bi , i = 1, . . . , n und
¨
den folgenden Algorithmus zur L¨sung von Ax = d :
o

A = LR
m1 = a1
fur i = 2, . . . , n :
¨
li = ci /mi’1
mi = ai ’ li · bi’1
Ly = d
y1 = d1
(3.26)
fur i = 2, . . . , n :
¨
yi = di ’ li · yi’1
Rx = y
xn = yn /mn
fur i = n ’ 1, n ’ 2, . . . , 1 :
¨
xi = (yi ’ bi · xi+1 )/mi
Fehlerabsch¨tzungen
a 51




3.4 Fehleranalyse und Fehlerbehandlung
3.4.1 Fehlerabsch¨tzungen
a
Wie in der Einleitung ausgefuhrt k¨nnen Computer nicht alle reellen Zahlen dar-
o
¨
stellen, daher werden die meisten Zahlen intern gerundet. Als Konsequenz er-
geben sich Rundungsfehler. Selbst wenn Eingabedaten und das Ergebnis eines
Algorithmus frei von Rundungsfehlern w¨ren, k¨nnen Zwischenergebnisse gerun-
a o
det worden sein. Aus diesem Grund wird in der Regel nicht die L¨sung x des
o
Gleichungssystems Ax = b berechnet, sondern die L¨sung x eines ™benachbarten™
o ˜
oder ™gest¨rten™ Gleichungssystems
o

(3.27) (A + A)˜ = b +
x b

b : Fehler im Vektor b (Residuum),
A : Fehler in der Matrix A,
x := x ’ x : Fehler der N¨herungsl¨sung
˜ a o
Um die nachfolgende Analyse durchzufuhren ben¨tigen wir den Begri¬ der zuge-
o
¨
ordneten Matrixnorm. Wir erinnern zun¨chst an verschiedene Normen fur Vek-
a ¨
toren x ∈ IRn . In dieser Vorlesung verwenden wir ublicherweise
¨
n

x2 ,
xT x =
x = (euklidische Norm oder 2“Norm)
2 i
i=1


welche wir meistens einfach mit . bezeichnen. Weitere Normen sind die
n
x = |xi |, (1“Norm)
1
i=1

oder die

x = max |xi |, (Maximumsnorm oder ∞“Norm).

i=1,...,n

Fur alle Vektornormen kann man eine zugeordnete Matrixnorm de¬nieren.
¨
eine Vektornorm im IRn .
De¬nition 3.27. Sei A eine (n, n)“Matrix und . p
Die Zahl
A p := max Ax p
x p =1


heißt die der Vektor“Norm . zugeordnete Matrixnorm.
p

Bemerkung 3.28. Wir bezeichnen nachfolgend die Vektornormen und die ihnen
zugeordneten Matrixnormen mit dem gleichen Symbol.
52 Lineare Gleichungssysteme




Sei nachfolgend A = (ai,j ).

Beispiel 3.29.
n
A := max |ai,j |, (Spaltensummennorm)
1
j=1,...,n
i=1

Beispiel 3.30.
n
A := max |ai,j |, (Zeilensummennorm)

i=1,...,n
j=1


Beispiel 3.31.
ρ(AT A),
A := (Spektralnorm)
2

wobei ρ(B) den Betrag des betragsgr¨ßten Eigenwert einer symmetrischen Matrix
o
B bezeichnet.

De¬nition 3.32. Als Kondition von A bzgl. einer Matrixnorm . bezeichnen
p
wir die Zahl
condp (A) := A p A’1 p .

Satz 3.33 (Fehleranalyse). Sei x die eindeutige L¨sung von Ax = b, und
o A,
b St¨rungen von A, b mit
o

A
(3.28) q = cond(A) < 1.
A

Dann ist auch das gest¨rte System
o

(3.29) (A + A)(x + x) = b + b

eindeutig l¨sbar und es gilt
o

x cond(A) A b
(3.30) ¤ +
x 1’q A b

Beweis: Sei x + x L¨sung von (3.29). Nach Ausmultiplizieren ergibt sich
o

Ax + A x + Ax + A x’b’ b=0

und weiter wegen Ax ’ b = 0

A x= b’ Ax ’ Ax
Fehlerabsch¨tzungen
a 53




und somit
x = ’A’1 (’ b + Ax + A x) .
Fur vertr¨gliche Matrixnormen folgt hieraus (Dreiecksungleichung)
a
¨

A’1 · ’
x ¤ b+ Ax + Ax
A’1 (
¤ b+ A·x+ A· x)

und weiter

1 ’ A’1 · x ¤ A’1 (
A b+ A · x)

Aufgrund der Voraussetzung (3.28) mit q < 1 folgt

A’1
x¤ ( b+ A · x)
1’q
als absolutem Fehler. Es ergibt sich weiter

A’1
x b
(3.31) ¤ + A .
x 1’q x

Aus b = Ax ¤ A · x folgt

b
x≥
A

<<

. 12
( 31 .)



>>