Kapitel_2

2. Lineare Gleichungssysteme: direkte und iterative
Lösungsverfahren
Problem (P2): Löse Ax = b, A ∈ Rn und b ∈ R.
2.1 Satz: Die folgenden Aussagen sind äquivalent:
(i) Ax = b ist für jedes b eindeutig lösbar;
(ii) Rang(A) = n;
(iii) det(A) 6= 0;
(iv) Alle Eingenwerte von A sind ungleich Null;
(v) A ist invertierbar;
(vi) Ax = 0 hat eine eindeutige Lösung x = 0.
Konditionszahlen einer Matrix, Matrixnormen
2.2 Definition: Eine Abbildung k · k : Rn×n → [0, ∞) heißt Matrixnorm,
wenn
(i) kAk > 0 für alle A ∈ Rn×n , A 6= 0;
(ii) kα · Ak = |α| · kAk für alle A ∈ Rn×n , α ∈ R;
(iii) kA + Bk ≤ kAk + kBk für alle A, B ∈ Rn×n .
Eine Matrixnorm k · k auf Rn×n heißt verträglich mit einer Vektornorm
k · k′ auf Rn , wenn gilt
kAxk′ ≤ kAk · kxk′
für alle
A ∈ Rn×n , x ∈ Rn .
2.3 Definition: Sei A ∈ Rn×n invertierbar. Konditionszahl cond(A) von A
ist definiert durch cond(A) = kAkkA−1 k.
Beispiele:
kAk∞ = max
1≤j≤n
kAk1 = max
1≤k≤n
n
X
|ajk | (Zeilensummennorm),
k=1
n
X
|ajk | (Spaltensummennorm).
j=1
Sei A ∈ Rn×n symmetrisch, dann gilt
kAk2 = max{|λ| : λ Eigenwert von A}
(Spektralnorm).
Die Matrixnormen k · k1 , k · k2 bzw. k · k∞ sind verträglich mit den
entsprechenden Vektornormen k · k1 , k · k2 bzw. k · k∞ .
2.4 Fehleranalyse, Kondition
Problem (P2): Löse Ax = b, A ∈ Rn×n und b ∈ Rn .
f Löse Ae
ex = e
e ∈ Rn×n und e
Problem (P2):
b, A
b ∈ Rn .
Kondition: Vergleiche den Ausgabefehler kx − xek mit den Eingabefehler
e und kb − e
kA − Ak
bk, wobei die Lösungen x und e
x von Ax = b bzw.
e
Ae
x =e
b ohne Rundungsfehler (exakt) berechnet werden;
Hilfsatz: Sei B ∈ Rn×n mit kBk < 1. Dann ist die Matrix I + B
invertierbar, und es gilt
k(I + B)−1 k ≤
1
.
1 − kBk
Störungssatz: Die Matrix A ∈ Rn×n sei invertierbar, und es sei
1
.
kA−1 k
e <
kA − Ak
e ebenfalls invertierbar, und für den relativen Fehler
Dann ist die Matrix A
der Lösung von Ax = b gilt
!
e
kx − e
xk
kb − e
bk kA − Ak
cond(A)
.
≤
+
e
kxk
kbk
kAk
1 − cond(A) · kA−Ak
kAk
Bemerkung: Ist cond(A) ·
xk
kx − e
kxk
k∆Ak
kAk
<< 1, so wird
. cond(A)
e
kb − e
bk kA − Ak
+
kbk
kAk
!
,
d.h. cond(A) ist der Verstärkungsfaktor, mit dem sich die Eingabefehler
e und b − e
A−A
b auf x − e
x auswirken.
2.5 Eliminationsverfahren
Satz (Cramersche Regel): Sei A ∈ Rn×n regulär. Die Lösung x von
Ax = b ergibt sich als


a1,1 . . . a1,j−1 b1 a1,j+1 . . . a1,n

.. 
..
..
..
det  ...
. 
.
.
.
an,1 . . . an,j−1 bn an,j+1 . . . an,n
, j = 1, . . . , n.
xj =
det(A)
Rechner mit 108 Gleitkommaoperationen pro Sekunde
n
Rechenzeit
10
0.4 s
12
1 min
14
36 Stunden
16
41 Tage
18
38 Jahre
20
16000 Jahre
Gauß-Elimination mit Pivotierung und Äquilibrierung/Zeilenskalierung
Beispiel (Gauß-Elimination mit Pivotierung):
(P2)
0.Initialisierung
Löse

3
 2
1
 

 
6
x1
2




x2
7 .
3
·
=
1
x3
4
1
1
1
[A[0] ; b[0] ] = [A; b]
1.Schritt
Pivotierung (keine Pivotierung erforderlich):

1
0
[1] [1]
Gauß-Elimination: [A ; b ] =  −2/3 1
−1/3 0
[0]
[0]
[0] [0]
[Ap ; bp ] = I · [A ; b ]
0
[0] [0]
0  · [Ap ; bp ]
1
2.Schritt


1 0 0
Pivotierung:
=  0 0 1  · [A[1] ; b[1] ]
0 1 0


1
0
0
[1] [1]
[2] [2]

0
1
0  · [Ap ; bp ]
Gauß-Elimination: [A ; b ] =
0 −1/2 1

 
 

3
1
6
x1
2





0 2/3
−1
x2
10/3  .
⇒ Löse Ax = b ⇔ Löse
·
=
0
0
−1/2
x3
4
[1] [1]
[Ap ; bp ]
Definitionen+Eigenschaften:
(i) Permutationsmatrix Pi ,j ist die Einheitsmatrix I mit vertauschten
i−ten und j−ten Zeilen. Die Matrixmultiplikation Pi ,j · A vertauscht i−te
und j−te Zeilen von A.
(ii) Pivotsuche: Aus Gründen der numerischen Stabilität trifft man
gewöhnlich die Wahl
ar (k),k = max |aj,k | , k = 1, . . . , n − 1, r (k) ∈ {k, . . . , n}.
k≤j≤n
Das Element ar (k),k heißt Pivotelement.
(iii) Pivotierung (k-ter Schritt): Pivotsuche und Zeilenvertauschung
[A[k−1]
; bp[k−1] ] = Pk,r (k) · [A[k−1] ; b [k−1] ]
p
mit 1 ≤ k ≤ r (k) ≤ n.
Algorithmus: (Gauß-Elimination mit Pivotierung)
Gegeben: A ∈ Rn×n invertierbar, b ∈ Rn .
Initialisierung:
[A[0] ; b [0] ] = [A; b]
Für k = 1, . . . , n − 1:
[k−1] [k−1] Pivotsuche:
ar (k),k = max aj,k , k ≤ r (k) ≤ n
k≤j≤n
[k−1]
Pivotierung:
[Ap
[k−1]
; bp
] = Pk,r (k) · [A[k−1] ; b [k−1] ]
[k−1],p
Gauß-Elimination: mit gj,k = aj,k



[A ; b ] = 


[k]
[k]
[k−1],p
/ak,k

1
..
.1
−gk+1,k
..
.
−gn,k
1
..
.
1
, j = k + 1, . . . , n,


 · [A[k−1] ; b [k−1] ]
p
p


Bemerkungen:
(i) A[n−1] ist eine obere Dreiecksmatrix.
(ii) Ax = b ist äquivalent zu A[n−1] · x = b [n−1] .
(iii)
Man
braucht a priori nicht zu wissen, ob A invertierbar ist. Ist
[k−1] ar (k),k = 0 für ein k = 1, . . . , n − 1, dann ist A singulär und der
Algorithmus muss abgebrochen werden.
Lemma: Sei A ∈ Rn×n invertierbar, b ∈ Rn . Die zur Lösung von Ax = b
mit Hilfe des Gauß-Eliminationsverfahren erforderliche Anzahl von
3
arithmetischen Operationen ist ≈ n3 .
Satz (Numerische Stabilität der Gauß-Elimination): Seien A ∈ Rn×n
invertierbar und b ∈ Rn . Das Gleichungssystem A · x = b wird mit
Gauß-Elimination mit Pivotierung gelöst. Dann ist die unter dem Einfluss
von Rundungsfehlern tatsächlich berechnete Lösung e
x die exakte Lösung
e·e
des Gleichungssystems A
x = b mit
e ∞
kA − Ak
≤ 1.01 · 2n−1 · (n3 + 2n2 ) · eps.
kAk∞
Äquilibrierung/Zeilenskalierung: Man kann manchmal die Konditionszahl
einer invertierbaren Matrix A ∈ Rn×n verkleinern, indem man die Matrix
A mit einer Diagonalmatrix


!−1
d11
n
X


..
D =
|ajk |
,
 , djj =
.
k=1
dnn
von links multipliziert (skaliert). Das Problem
(P2) Löse
Ax = b,
hat die selbe Lösung als DAx = Db.
A ∈ Rn×n ,
b ∈ Rn ,
2.6 Iterationsverfahren: Jacobi- und Gauß-Seidel-Verfahren
Fixpunkt-Iteration: Mit einer beliebigen invertierbaren Matrix C ∈ Rn×n
gilt die Äquivalenz
Ax = b ⇔ Cx = Cx − Ax + b ⇔ x = (I − C −1 A)x + C −1 b.
Man versucht C so zu wählen, dass
• zu gegebenem Vektor x [k] , k ≥ 0, der neue Vektor
x [k+1] = (I − C −1 A)x [k] + C −1 b
mit wenig Aufwand zu berechnen ist;
• die Iterationsfunktion φ : Rn → Rn , φ(x) = (I − C −1 A)x + C −1 b
kontrahierend ist und eine möglichst kleine Kontraktionszahl besitzt.
Darstellung der Iterationsfunktion:
Die Matrix A wird in drei Teile zerlegt gemäß A = L + D + R mit

0


a
L =  21
 ..
 .
an1
···
..
.
..
.
···
···
..
.
an,n−1


0
a11

.. 


.
 0
, D = 
.. 
 ..
 .
.
0
0
0
..
..
.
.
···
···
..
.
..
.
0


0
0
.
.. 

.
. 
.
, R = 

 ..
.
0 
ann
0
a12
..
.
···
···
..
.
..
.
···

a1n
.. 

. 
.

an−1,n 
0
Proposition:
a) Die Iterationsfunktion des Jacobi-Verfahrens (JV) lautet
φJV (x) = (I − D −1 A)x + D −1 b = −D −1 (L + R)x + D −1 b.
b) Die Iterationsfunktion des Gauß-Seidel-Verfahrens (GSV) lautet
φGSV (x) = (I − (L + D)−1 A)x + (L + D)−1 b = −(L + D)−1 Rx + (L + D)−1 b.
Verglichen mit der allgemeinen Form φ(x) = (I − C −1 A)x + C −1 b, werden hier also
die folgenden Matrizen C verwendet:
C = D, ajj =
6 0, j = 1, . . . , n.
C = L + D ajj 6= 0, j = 1, . . . , n.
(JV)
(GSV)
Konvergenzanalyse der Folge x [k+1] = φ(x [k] ), k ≥ 0:
Definition: Die Iterationsfunktion φ : Rn → Rn heißt kontrahierend, falls
es eine Norm k · k existiert, so dass für alle x, y ∈ Rn gilt
kφ(x) − φ(y )k ≤ Lkx − y k
mit der Kontraktionszahl 0 ≥ L = kI − C −1 Ak < 1.
Satz: Die Matrizen A und C seien invertierbar. Dann sind die folgenden
Aussagen äquivalent:
(i) Die Folge (x [k] )k∈N0 konvergiert bei beliebigem Startvektor
x [0] ∈ Rn gegen die Lösung x ∗ von Ax = b.
(ii) Die Iterationsmatrix B = I − C −1 A hat den Spektralradius
ρ(B) = max{|λ| : λ Eigenwert von B} < 1.
(iii) Es gibt eine (natürliche) Matrixnorm k · k auf Rn×n mit kBk < 1.
Beweisidee ((iii ) ⇒ (i )):
Banachscher Fixpunktsatz: Sei φ : Rn → Rn kontrahierend mit der Kontraktionszahl
0 ≤ L < 1.
•
•
Dann hat x = φ(x) genau eine Lösung x ∗ ∈ Rn .
Für jeden Startwert x [0] ∈ Rn konvergiert die Folge (x [k] )k∈N0 mit
x [k+1] = φ(x [k] ),
k ≥ 0,
gegen x ∗ .
Beweisidee (Äquivalenz von (ii ) und (iii )):
Hilfssatz: Gegeben sei die Matrix B ∈ Rn×n .
•
Für jede natürliche Matrixnorm k · k : Rn×n → R gilt
ρ(B) ≤ kBk.
•
Zur Matrix B ∈ Rn×n und beliebigem ǫ > 0 existiert eine natürliche Matrixnorm
k · k : Rn×n → R so, dass für den Spektralradius ρ(B) gilt
kBk ≤ ρ(B) + ǫ.
Bemerkungen:
(i) Der Banachscher Fixpunktsatz liefert auch die folgenden
Fehlerabschätzungen: für k ≥ 0 gelten
kx [k+1] − x [k] k ≤
kx [k] − x ∗ k ≤
L
kx [k] − x [k−1] k (a posteriori)
1−L
Lk
kx [1] − x [0] k (a priori)
1−L
(ii) Die Matrixnormen k · kp , p = 1, 2, ∞ sind natürliche Matrixnormen.
(iii) Satz: Falls die Matrix A ∈ Rn×n stark diagonaldominant ist, d.h.
|ajj | >
n
X
|ajk | für alle j = 1, . . . , n,
k=1
k6=j
dann konvergieren die beiden Jacobi- und Gauß-Seidel-Verfahren für
jeden Startvektor x [0] ∈ Rn .

Download Report