<<

. 13
( 31 .)



>>

und somit aus (3.31)

A’1 · A
x b A
¤ +
x 1’q b A
und hieraus die Behauptung.

Die Zahl cond(A) hat also die Bedeutung eines Verst¨rkungsfaktors und mißt die
a
Emp¬ndlichkeit der L¨sung x gegenuber St¨rungen in A und b. Das LGS Ax = b
o o
¨
heißt schlecht konditioniert, wenn cond(A) >> 1.

Beispiel 3.34. Auswirkung schlechter Kondition:

1 1 1 1
A= , b= , x=
1 0.99 1 0

0.01 0.01 0 200/101
∆A = , ∆b = , x + ∆x =
0 0 0 ’100/101
54 Lineare Gleichungssysteme




Obwohl der Fehler in A bei 1% liegt, haben x, x + ∆x nichts mehr miteinander zu
tun.
Erkl¨rung:
a

’99 100
A’1 = ||A’1 ||∞ = 200,
||A||∞ = 2, , cond∞ (A) = 400!
100 ’100

Geometrisch: Die Zeilenvektoren a1 , a2 von A haben beinahe die gleiche Richtung.


3.4.2 Skalierung
Die Kondition eines Problems kann ggf. durch Skalierung der Matrix A verbessert
¨
werden. Unter Skalierung versteht man den Ubergang
« 
d1 0
¬ ·
..
D=¬ ·,
A ’ DA, di = 0,
.
 
0 dn

d.h. die i-te Zeile von A wird mit di multipliziert. Die optimale Wahl einer Dia-
gonalmatrix D, welche cond(DA) moglichst klein macht, erhalt man durch den
¨ ¨
folgenden Satz (ohne Beweis):

Satz 3.35 (Van der Sluis). Fur A = (aik ) sei
¨

n
|aik | = 1, i = 1, . . . , n (insbesondere ||A||∞ = 1).
k=1


Dann gilt fur jede Diagonalmatrix D mit det D = 0
¨

cond∞ (DA) ≥ cond∞ (A).

Folgerung 3.36. Fur eine beliebige regul¨re Matrix A = (aik ) ist mit der Ska-
a
¨
lierung
’1
n
D = diag(di ), di := |aik |
k=1

die Kondition cond∞ (DA) m¨glichst klein.
o
Fehlerabsch¨tzungen
a 55




3.4.3 Iterative Nachverbesserung
Unabh¨ngig von einer schlechten Kondition der Matrix A liefern numerische Ver-
a
fahren zur L¨sung linearer Gleichungssysteme nicht die exakte L¨sung. Wir erhal-
o o
ten dann lediglich eine Naherungslosung, die unseren Anforderungen aber mogli-
¨ ¨ ¨
cherweise nicht hinreichend gerecht wird. Mit einem kleinen Trick l¨ßt sich die
a
berechnete N¨herungsl¨sung aber dennoch weiter verbessern:
a o
x sei exakte L¨sung von Ax = b
o
x
˜ sei irgendeine Naherungslosung, z.B. aus Gauß-Algorithmus.
¨ ¨
Verbesserung in drei Schritten:

1. Berechne r := b ’ A˜
x ”Residuum“

2. Bestimme ∆x aus A∆x = r ”Korrektur“

3. Berechne x := x + ∆x
˜

Begrundung:
¨

= x + ∆x = x + A’1 r = x + A’1 (b ’ A˜)
x ˜ ˜ ˜ x
= x+x’x=x
˜ ˜

In der praktischen Anwendung/Implementierung bewirken Rundungsfehler, dass
i.A. x = x ist. Die Verbesserung kann wiederholt werden, solange ∆x nur mit
einer Stelle korrekt berechnet wird. In diesem Fall ist x besser als x.
˜

Bei der algorithmischen Durchfuhrung sind einige Dinge zu beachten:
¨

• Wurde x durch den Gauß-Algorithmus gewonnen, so erfullt x das Glei-
˜ ¨˜
chungssystem meist sehr gut, d. h.

b ≈ A˜
x ’ r = b ’ A˜ ausl¨schungsgef¨hrdet!
x o a

Um dem entgegenzuwirken berechnet man im Schritt 1. das Residuum mit
doppelter Genauigkeit.

• Bei der Au¬‚¨sung von A · ∆x = r benutze man die bereits berechnete
o
LR ’ Zerlegung.

• Rundungsfehler im 3. Schritt begrenzen i.A. die erreichbare Genauigkeit.
56 Lineare Gleichungssysteme




Beispiel 3.37. Sechs Dezimalstellen; unterstrichene Stellen sind falsch

0.566012 0.765456 x1 0.395102
=
0.389953 0.527611 x2 0.272744

exakt : x1 = ’ 2.20227459 . . .
x2 = 2.14462470 . . .
Gauß x1 = ’ 2.19453
˜
x2 =
˜ 2.13889
1. Nachverbesserung 2. Nachverbesserung
x1 = ’2.20 226 x1 = ’2.20227
x2 = 2.14461 x2 = 2.14462
Bemerkung 3.38. Meist reicht nur ein Schritt, um das Resultat deutlich zu
verbessern.


3.5 Die QR-Zerlegung einer Matrix, das Verfah-
ren von Householder
3.5.1 Einleitung und Motivation
Sei A eine (n, n)-Matrix (reell, nicht notwenig regul¨r).
a
Bei der LR-Zerlegung (ohne Pivotsuche) hatten wir das Ergebnis:

A = LR
L: linke Dreiecksmatrix
R: rechte Dreiecksmatrix.
Bei der QR-Zerlegung suchen wir hingegen eine Zerlegung der Form:

A = QR
Q: orthogonal, d. h. QT Q = I,
R: rechte Dreiecksmatrix.
Motivation zur QR-Zerlegung:
Zur L¨sung des LGS Ax = b erzeugt man bei der LR-Zerlegung und Gauß-
o
Elimination eine Sequenz

(A, b) = (A(1) , b(1) ) ’ . . . ’ (A(j) , b(j) ) ’ . . . ’ (A(n) , b(n) ) = (R, c)
(A(j+1) , b(j+1) ) = Lj (A(j) , b(j) ).
QR“Zerlegung 57




Sei µ(j) der Rundungsfehler bei der Berechnung von (A(j) , b(j) ). Fur irgendeine
¨
Vektornorm x gilt nach Satz 3.33 die Absch¨tzung
a
n
∆x
µ(j) cond(A(j) ).
¤
x j=1

Die Gauß-Elimination ist daher nicht gutartig, falls

cond(A(j) ) >> cond(A(1) ) = cond(A).

¨
Idee: W¨hle Matrix Qj mit Ubergang
a

(A(j+1) , b(j+1) ) = Qj (A(j) , b(j) ), cond(A(j+1) ) = cond(A(j) ).

Dazu beschranken wir uns auf die euklidische Norm
¨

= (xT x)1/2 ,
x=x A=A
2 2


und notieren eine sp¨ter zu benutzende Hilfsaussage:
a

Hilfssatz 3.39. Sei Q orthogonal, dann gilt:

(i) Q =1
2

(ii) QA =A fur alle A
¨
2 2

(iii) Wenn A regul¨r ist, gilt cond2 (QA) = cond2 (A).
a
¨
Beweis: Ubung

3.5.2 Householdermatrizen
Sei w ∈ IRn mit wT w = 1 und sei die Householdermatrix Q de¬niert durch

Q := I ’ 2wwT , wwT = (wi · wk ).

Dann hat die so konstruierte Matrix Q folgende Eigenschaften:
Q ist symmetrisch:

QT = I ’ 2(wwT )T = I ’ 2wwT = Q

Q ist orthogonal wegen wT w = 1 :

QT Q = (I ’ 2wwT )(I ’ 2wwT )
= I ’ 2wwT ’ 2wwT + 4wwT wwT = I
58 Lineare Gleichungssysteme




Fur x ∈ IRn bedeutet
¨

Qx = (I ’ 2wwT )x = x ’ 2(wT x)w

eine Spiegelung an der Hyperebene

<<

. 13
( 31 .)



>>