Embed Size (px)
Citation preview
Numerische Methoden
ETH Zurich
SS 2006
Inhalt
1 Lineare Algebra 11.1 Vektorraume (VRe) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.2 Matrizen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21.3 Matrixoperationen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31.4 Spur und Determinante . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51.5 Rang und Kern . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51.6 Spezielle Matrizen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61.7 Eigenwerte und Eigenvektoren . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71.8 Ahnlichkeitstransformationen . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71.9 Schur und Jordan Normalform . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81.10 Normen in Cn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91.11 Normaquivalenz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111.12 Matrixnormen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121.13 Skalarprodukt und Orthogonalitat . . . . . . . . . . . . . . . . . . . . . . . . . . 141.14 Gram-Schmidt Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151.15 Singularwertzerlegung (SVD) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2 Computerarithmetik 192.1 Gleitkommazahlen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192.2 Runden mit Maschinenepsilon . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212.3 Gleitkommaoperationen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3 Direkte Losung Linearer Gleichungssysteme: Gaußelimination (GEM) 253.1 Gaußscher Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.1.1 Dreiecksmatrizen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253.1.2 Gaußscher Algorithmus und LR-Zerlegung . . . . . . . . . . . . . . . . . 273.1.3 LR-Zerlegung fur schwach besetzte Matrizen . . . . . . . . . . . . . . . . 34
3.2 Symmetrisch positiv definite Matrizen . . . . . . . . . . . . . . . . . . . . . . . 383.3 Pivotstrategien & Nachiteration . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.3.2 Spaltenpivotstrategie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 413.3.3 Existenz von LR-Zerlegungen ohne Spaltenpivotsuche . . . . . . . . . . . 483.3.4 Nachiteration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
A Ubungsaufgaben 50
i
1 Lineare Algebra
Wir rekapitulieren grundlegende Begriffe der linearen Algebra, die spater wiederholt gebrauchtwerden.
1.1 Vektorraume (VRe)
Definition 1.1.1 Ein Vektorraum (VR) uber einem Zahlkorper K(= R, C) ist Menge V 6= ∅mit Addition “+” (kummutativ + assoziativ) und Skalarmultiplikation “···”, mit
i) ex. 0 ∈ V : ∀v ∈ V : v + 0 = v ,
ii) ∀v ∈ V : 0 · v = 0, 1 · v = v fur 0, 1 ∈ K ,
iii) (inverses Element): ∀v ∈ V ex. −v ∈ V : v + (−v) = 0 ,
iv) ∀α ∈ K : ∀v, w ∈ V : α(v + w) = αv + αw ,∀α, β ∈ K : ∀v ∈ V : (α + β) v = αv + βv ,
v) ∀α, β ∈ K, ∀v ∈ V : (αβ)v = α(βv) .
Beispiel 1.1.2 V = Rn, V = Cn
V = Pn :={
pn(x) =m∑
k=0
ak xk}
,
V = Cp([a, b]) .
Definition 1.1.3 ∅ 6= W ⊂ V Teilraum (TR) ⇐⇒ W ist VR uber K.
Beispiel 1.1.4 a) Sei [a, b] ⊂ R beschranktes Intervall, und x0, x1, . . . , xn “Stutzstellen” mita = x0 < x1 < · · · < xn = b. Dann gilt:
Vn ={f ∈ C0([a, b])
∣∣ f |[xi−1,xi] ist linear}⊂ C0([a, b]) ist TR .
b) Polynome vom Grad n sind ein Teilraum der stetigen Funktionen, d.h. Pn ⊂ C0(R).
c) Sei v1, . . . , vn ⊂ V beliebig. Dann gilt
W := span{v1, . . . , vn} “erzeugendes System”
:= {v = α1 v1 + · · ·+ αn vn : αi ∈ K} ist TR von V .
1
Direkte Summe von TR: Seien W1, . . . , Wm ⊂ W TR =⇒
S := {w : w = v1 + · · · + vm mit vi ∈ Wi : i = 1, . . . , m} ist TR.
S direkte Summe der Wi, S = W1 ⊕ · · · ⊕ Wm, ⇐⇒ ∀s ∈ S ex.! v1, . . . , vm mit vi ∈ Wi;S = v1 + · · ·+ vm.
Definition 1.1.5 i) {v1, . . . , vm} ⊂ V linear unabhangig ⇐⇒
α1 v1 + · · ·+ αm vm = 0 ⇐⇒ α1, . . . , αm = 0 .
ii) V = span{u1, . . . , um} ∧ ui linear unabhangig =⇒ {u1, . . . , um} Basis von V .∧ m = dim V .
1.2 Matrizen
Sei m, n ∈ N. mn Zahlen aij ∈ K, i = 1, . . . , m, j = 1, . . . , n bilden eine Matrix mit m Zeilenund n Spalten, eine m × n Matrix,
A =
a11 . . . a1m
......
am1 . . . amm
. (1.2.1)
Falls aij ∈ R schreiben wir A ∈ Rm×n und analog, falls aij ∈ C schreiben wir A ∈ Cm×n. Wirbenutzen die Bezeichnungen:
A = A(m × n):
matrix1.1.eps83 × 39 mm
\tex{$\vdots$}\tex{$\vdots$}
\tex{$\dots$}
\tex{$\dots$}
\tex{$a_{11}$}
\tex{$a_{m1}$} \tex{$a_{mn}$}
\tex{$a_{1n}$}
\tex{Zeilenvektor}
\tex{Diagonale}
\tex{Spaltenvektor}
Definition 1.2.1 Sei A m × n Matrix, und ip, jq Indizes mit
1 ≤ i1 < · · · < ik ≤ m, 1 ≤ j1 < · · · < j` ≤ n .
S = (Spq) = (aip,jq), p = 1, . . . , k, q = 1, . . . , `, heisst Untermatrix von A.
2
Definition 1.2.2 A(m × n) Blockmatrix, falls
A =
an . . . a1`
......
ak1 . . . ak`
,
mit Aij Untermatrizen von A .
Beispiel 1.2.3
1 2 34 5 6
7 8 9
=
(A11 A12
A21 A22
).
Notation 1.2.4 (MATLAB-Notation) Bei einem Vektor a ∈ Rn bezeichnet in Matlab-Notation a(i) die Komponente ai. Die Notation a(k : l) ist eine Kurzform fur den Vektor derLange l − k + 1 mit den Komponenten k bis l des Vektors a. Analoge Notationen gelten furMatrizen: Die Eintrage einer Matrix A sind A(n, m), und der Ausdruck A(k : l, r : s) bezeichnetdie Untermatrix von A, aus den Zeilen k bis l und den Spalten r bis s besteht. Fur eine Vektora ∈ Rn mit n Komponenten gilt length (a) = n.
Untermatrix von A: Symbolisch schreiben wir
i1
i2j1 j2
Analog ist fur Vektoren v ∈ Kn: v(i1 : i2) Teilvektor von v; symbolisch:
i1
i2
.
A(m × n) = (a1, . . . , an), wobei ai ∈ Km Spaltenvektoren der Matrix A sind.
1.3 Matrixoperationen
Wir rekapitulieren die wichtigsten Matrixoperationen.
Definition 1.3.1 Eine quadratische Matrix A = A(n × n) heisst invertierbar ⇐⇒
∃B = B(n × n), dass AB = BA = I.
Wir schreiben B Inverse von A, B = A−1(n × n).Es gilt
A singular ⇐⇒ A nicht invertierbar.
3
Proposition 1.3.2 Die Inverse A−1(n × n) von A = (a1, . . . , an) existiert ⇐⇒die Spalten a1, . . . , an sind linear unabhangig.
Definition 1.3.3 Sei A = A(m × n) = (aij) ∈ Rm×n.Dann ist
A> = A>(n × m) = (aji) ∈ Rn×m Transponierte von A .
Wir geben einige Rechenregeln fur die Transponierte einer Matrix A.
Proposition 1.3.4
(A>)> = A, (A + B)> = A> + B>, (AB)> = B>A>, (αA)> = αA> ∀α ∈ K .
A−1 ex. =⇒ (A>)−1 ex. und (A>)−1 = (A−1)> = A−>.
Fur Matrizen mit komplexen Eintragen ist oft die komplex konjugierte transponierte Matrixvon Interesse, die sog. hermitesch Transponierte.
Definition 1.3.5 Seien A = (aij) ∈ Cm×n. Dann ist B = AH := A> = (aji) die hermitesch
Transponierte zu A.
Beispiel 1.3.6 A ∈ Cn×m, B ∈ Cm×n. Dann gilt:
(AB)H = BHAH , (αA)H = α AH , α ∈ C .
Definition 1.3.7
A ∈ Rn×n symmetrisch ⇐⇒ A = A> ,
schiefsymmetrisch ⇐⇒ A = −A> ,
orthogonal ⇐⇒ A−1 = A> ⇐⇒ A>A = AA> = I .
Definition 1.3.8
A ∈ Cn×n hermitesch ⇐⇒ A> = A ⇐⇒ AH = A ,
unitar ⇐⇒ AHA = AAH = I .
Definition 1.3.9A ∈ Cn×n normal ⇐⇒ AAH = AHA .
4
1.4 Spur und Determinante
Sei A = A(n × n) eine quadratische Matrix. Dann heisst tr(A) :=n∑
i=1
aii die Spur von A.
Aus der linearen Algebra erinnern wir an die Determinante von A:
det(A) =∑
π∈P
sgn(π) a1π1. . . anπn
.
Sie erfullt folgende Rechenregeln.
det(A) = det(A>), det(AB) = det(A) det(B), det(A−1) = 1/det(A)
det(A) = det(AH), det(αA) = αn det(A) ∀α ∈ K .
1.5 Rang und Kern
Definition 1.5.1 A = A(m× n) hat rang q, wenn die grosste Blockuntermatrix A(q × q) von
A mit det A(q, q) 6= 0 die Grosse q hat. Wir schreiben: q = rank(A).
A = A(m × n) hat maximalen Rang ⇐⇒ rank A = min(m, n).
Eigenschaft 1.5.2
rank A = dim(range(A)
)wo
range(A) := {y ∈ Km : y = Ax, x ∈ Kn} .
Eigenschaft 1.5.3
ker A = {x ∈ Kn : Ax = 0 ∈ Km} heisst ‘Kern’ von A, Nullraum von A .
Es gilt: ∣∣∣∣∣rank(A) = rank(A>), rank(A) = rank(AH) ,
rank(A) + dim(ker(A)
)= n .
Eigenschaft 1.5.4
A nichtsingular ⇐⇒ det(A) 6= 0 ⇐⇒ ker A = {0} ⇐⇒
rank(A) = n ⇐⇒ A = {a1, . . . , an} ∧ ai linear unabhangig .
5
1.6 Spezielle Matrizen
A = A(m × n) obere Trapezmatrix ⇐⇒ aij = 0 for i > j
untere Trapezmatrix ⇐⇒ aij = 0 for i < j
m = n =⇒ obere Dreiecksmatrix ⇐⇒ aij = 0 for i > j
untere Dreiecksmatrix ⇐⇒ aij = 0 for i < j .
Beispiel 1.6.1 (Dreiecksmatrizen)
L =
`11 0 . . . 0...
. . .. . .
...... ?
. . . 0`n1
. . . `nn
, U =
u11 . . . . . . u1n
. . . ?...
0. . .
unn
beispiel1.eps105 × 9 mm
\tex{$=$}\tex{$0$}
\tex{$0$}\tex{$=$} \tex{~}
Proposition 1.6.2 Sei L eine untere Dreiecksmatrix. Dann gilt
1) det L = `11 . . . `nn =n∏
i=1
`ii = `11 . . . `nn, det U = u11 . . . unn
2) Dreiecksmatrizen schreiben wir symbolisch als
beispiel2.eps
104 × 9 mm\tex{$0$} \tex{$0$} \tex{$0$}
\tex{$0$} \tex{$0$} \tex{$0$}\tex{$=$} \tex{$=$}\tex{,}
Definition 1.6.3
1) A ∈ Cm×n (p, q)-Bandmatrix, wenn
aij = 0 fur i > j + p, j > i + q .
beispiel3.eps
45 × 26 mm
\tex{$\star$}
\tex{$0$}
\tex{$q$}
\tex{$q+1$}
\tex{$0$}
\tex{$p+1$}
2) p = q = 1: A-Tridiagonalmatrix.
3) p = m − 1, q = 1: A untere Hessenberg.
6
1.7 Eigenwerte und Eigenvektoren
Sei A ∈ Cn×n quadratische Matrix. Dann ist:
λ ∈ C Eigenwert von A ⇐⇒ ∃ 0 6= x ∈ Cn : Ax = λx .
σ(A) = {λ ∈ C : λ Eigenwert von A} heisst Spektrum von A.
x Rechtseigenvektor von Ay Linkseigenvektor von A
∣∣∣∣ ⇐⇒ Ax = λx, yHA = λyH .
λ ∈ σ(A) erfullt die charakteristische Gleichung
pA(λ) := det(A − λI) = 0 .
Proposition 1.7.1
1) A ∈ Cn×n =⇒ pA(λ) ∈ Pn =⇒ σ(A) = {λ1, . . . , λn}, und
2) det(A) = pA(0) = λ1λ2 . . . λn, tr(A) =
n∑
i=1
λi .
3) σ(A) = σ(A>), σ(AH) = σ(A), d.h. λ ∈ σ(A) ⇐⇒ λ ∈ σ(AH)
Der Spektralradius von A ∈ Cn×n ist
ρ(A) = max1≤i≤n
|λi| = maxλ∈σ(A)
|λ| .
Fur den Spektralradius gilt (nachrechnen!)
ρ(A) = ρ(AH), ρ(Ak) =(ρ(A)
)k, k ∈ N .
1.8 Ahnlichkeitstransformationen
Ahnlichkeitstransformationen lassen das Spektrum einer Matrix invariant. In der Numerikwerden Ahnlichkeitstransformationen benutzt, um Eigen- und Singularwerte und, allgemeiner,die Schur Normalform sowie die Singularwertzerlegung der Matrix A stabil zu berechnen.
Definition 1.8.1 Seien A(n × n), C(n × n) Matrizen mit det C 6= 0. Dann heisst die trans-formierte Matrix
C−1 AC ahnlich zu A .
Proposition 1.8.2 σ(A) = σ(C−1 AC), pA(λ) = pC−1 AC(λ).
Beweis:
λ ∈ σ(C−1 AC) =⇒ det (C−1 AC − λ C−1︸︷︷︸
I
C) = 0 ,
⇐⇒ det (C−1 (A − λI) C) = 0 ,
⇐⇒ det (A − λI) = 0 .
2
7
1.9 Schur und Jordan Normalform
Wir rekapitulieren den folgenden Satz aus der linearen Algebra: jede Matrix A(n × n) kannahnlich auf die sog. Jordan’sche Normalform transformiert werden.
A ∈ Cn×n hat n Eigenwerte λ1, . . . , λn. Diese sind Nullstellen des charakteristischen Polynomsp(λ) = det(A − λ 1).
alg. Vielfachheit von λiλiλi = Vielfachheit der Nullstelle λi von p(λ):
p(λ) = (λ − λi)malg
i q(λ), Ordnung q(λ) = n − malgi .
geom. Vielfachheit von λiλiλi = mgeomi := # lineare unabhangige Eigenvektoren zum Eigenwert
λi. Es gilt:mgeom
i ≤ malgi .
Defekt:di := malg
i − mgeomi ≥ 0 .
Jordan Normalform: ∃T ∈ Cn×n nicht singular,
T−1AT =
λ1 1 00 λ1 1 00 0 λ1 1 0...
. . .
0 0 λ1 10 0 0 λ1
0 0 0
0 λ1 0 0
0 0
λ2 1 00 λ2 1 00 0 λ2 1 0...
. . .
0 0 λ2 10 0 0 λ2
0
0 0 0. . .
= J
wobei:
• pro Eigenvektor je 1 Jordanblock
λ1 1 00 λ1 1 00 0 λ1 1 0...
. . .
0 0 λ1 10 0 0 λ1
auftritt. Seine Grosse hangt
ab von der Lange der Hauptvektorketten.
8
• λi sind in den verschiedenen Jordanblocken sind nicht notwendig verschieden,
• die Jordan’sche Normalform ist praktisch schlecht zu berechnen, da die Transformation-smatrix T in der Jordan’schen Normalform nicht ‖ ◦ ‖2-isometrisch ist: es gibt x ∈ Cn:
‖T x‖2 � ‖x‖2 .
In der Numerik verlangt man deshalb weniger als die Jordan’sche Normalform: “nur T!=
unitar”.Dies “bezahlt” damit, dass die transformierte Matrix J weniger Nulleintrage hat. Genauer
gilt:
Theorem 1.9.1 (Schur)
A ∈ Cn×n beliebig, λ1, . . . , λn ∈ C Eigenwerte. Dann existiert Q ∈ Cn×n unitar so, dass
QH AQ =
λ1 ∗. . .
0 λn
.
Beweis: Sei u1 Eigenvektor zu λ1, ‖u1‖2 = 1. Wahle u2, . . . , un ∈ Cn so, dass V 1 = (u1, . . . , un)unitar. Dann gilt, mit A0 = A,
V H1 A0 V 1 =
λ1 ∗ . . . ∗
0
... A1
0
.
Wiederhole Schlussweise mit A1 ∈ C(n−1)×(n−1):
V 2 =
1 0 . . . 0
0
... V 2
0
, V 2 = (u2, . . . , un) ∈ C(n−1)×(n−2) .
Rekursion mit V 3, . . . , V n ergibt die Behauptung. 2
1.10 Normen in Cn
Sei V VR uber dem Koeffizientenkorper K = R, C. Dann ist
‖ ◦ ‖ : V → R+ Norm ⇐⇒
9
∀x ∈ V : ‖x‖ ≥ 0j ‖x‖ = 0 ⇐⇒ x = 0 . (N1)
∀x ∈ V, α ∈ K : ‖αx‖ = |α| ‖x‖ . (N2)
∀x, y ∈ V : ‖x + y‖ ≤ ‖x‖ + ‖y‖ . (N3)
Bemerkung 1.10.1∣∣‖x‖ − ‖y‖
∣∣ ≤ ‖x − y‖.
Beweis: (N3) ⇐⇒
‖x‖ − ‖y‖ = ‖x − y + y‖ − ‖y‖
≤ ‖x − y‖ + ‖y‖ − ‖y‖ = ‖x − y‖ ;
x ↔ y =⇒ Behauptung .
2
Beispiele: V ∈ Cn, p ≥ 1, x = (x1, . . . , xn)>.
‖x‖p :=( n∑
i=1
|xi|p) 1
p
, 1 ≤ p < ∞ .
Theorem 1.10.2 ‖ ◦ ‖p ist Norm auf Cn.
Beweis: (N1), (N2) sind offensichtlich, wir zeigen (N3). Hierzu brauchen wir
Lemma 1.10.3 Seien indices p, q ≥ 1 konjugiert,
1
p+
1
q= 1, p, q ≥ 1 .
Dann gilt
∀a, b > 0 : ab ≤ap
p+
bq
q.
Beweis: x 7−→ log x konkav, d.h.
∀α, β ≥ 0, α + β = 1 : ∀u, v > 0 :
α log u + β log v ≤ log(αu + βv) : α = 1p, β = 1
q, u = ap, v = bq .
Dann:
log(ab) = log a + log b = α log(ap) + β log(bq) ≤ log(1
pap +
1
qbq)
.
2
Theorem 1.10.4 (Holder Ungleichung)
Seien p, q ≥ 1 konjugiert, x, y ∈ Cn. Dann gilt
∣∣∣n∑
i=1
xi yi
∣∣∣ ≤ ‖x‖p ‖y‖q .
Beweis: x = 0 ∨ y = 0 trivial. Seien x 6= 0, y 6= 0. Setze
x = x / ‖x‖p, y = y / ‖y‖p .
10
Lemma 1.10.3 =⇒
|xi| |yi| ≤|xi|
p
p+
|yi|q
q, i = 1, . . . , n ,
n∑
1
|xi| |yi| ≤1
p
∥∥x∥∥p
p+
1
p
∥∥y∥∥q
q= 1 .
2
Theorem 1.10.5 (Minkowski Ungleichung)
Sei p ≥ 1, x, y ∈ Cn. Dann
‖x + y‖p ≤ ‖x‖p + ‖y‖p .
Beweis:
∥∥x + y∥∥p
p=
n∑
i=1
|xi + yi|p ≤
n∑
i=1
|xi + yi|p−1(|xi| + |yi|
)
Holder
≤( n∑
i=1
(|xi + yi|
p−1)q) 1
q (‖x‖p + ‖y‖p
)
=∥∥x + y
∥∥p/q
p
(‖x‖p + ‖y‖p
)=∥∥x + y
∥∥p−1
p
(‖x‖p + ‖y‖p
),
da (p − 1) q = p, 1q
= (p − 1)/p = 1 − 1p. 2
1.11 Normaquivalenz
Es ist aus der Analysis bekannt, dass alle Normen auf endlichdimensionalen Raumen aquivalentsind.
Definition 1.11.1 ‖ ◦ ‖p, ‖ ◦ ‖q auf V aquivalent ⇐⇒ ex. 0 < cpq ≤ Cpq < ∞ mit
cpq ‖x‖q ≤ ‖x‖p ≤ Cpq ‖x‖q ∀x ∈ V .
In der Numerik brauchen wir insbesondere fur Cn die Werte der Aquivalenzkonstanten.Beispiel: V = Cn.
cpq q 1 2 ∞
p 1 1 11
2 n− 12 1 1
∞ n−1 n− 12 1
Cpq = (cqp)−1 .
11
1.12 Matrixnormen
Definition 1.12.1 (Matrixnorm)
‖ ◦ ‖: Cm×n → R:
‖A‖ ≥ 0 ∧ ‖A‖ = 0 ⇐⇒ A = 0 , (N1)
‖αA‖ = |α| ‖A‖ ∀α ∈ C, ∀A ∈ Cm×n , (N2)
‖A + B‖ ≤ ‖A‖ + ‖B‖ ∀A, B ∈ Cm×n . (N3)
Definition 1.12.2 Matrixnorm ‖ ◦ ‖M konsistent oder vertraglich mit Vektornorm ‖ ◦ ‖V ⇐⇒
‖Ax‖M ≤ ‖A‖M‖x‖V ∀x ∈ Rn .
Definition 1.12.3 ‖ ◦ ‖M submultiplikativ ⇐⇒
∀A ∈ Cn×m, B ∈ Cm×q : ‖AB‖M ≤ ‖A‖M ‖B‖M .
Beispiel: Die Frobeniusnorm in Cn×m ist
‖A‖F =( n∑
i,j=1
|aij|2) 1
2
= tr (AAH)12 .
‖ ◦ ‖F ist konsistent mit ‖ ◦ ‖2:
‖Ax‖22 =
(xH AH , Ax
)=
n∑
i=1
∣∣∣n∑
j=1
aij xj
∣∣∣2
≤n∑
i=1
( n∑
j=1
|aij |2
n∑
j=1
|xj |2)
= ‖A‖2F ‖x‖2
2 .
Sei ‖ ◦ ‖∗ auf Cm, ‖ ◦ ‖∗∗ auf Cn. Fur A ∈ Cm×n ist
‖A‖∗∗∗ := supx 6=0
‖Ax‖∗‖x‖∗∗
= maxx 6=0
‖Ax‖∗‖x‖∗∗
Operatornorm auf Cm×n, induziert durch ‖ ◦ ‖∗, ‖ ◦ ‖∗∗.
‖ ◦ ‖∗∗∗ ist kompatibel, d.h.
‖Ax‖∗ ≤ ‖A‖∗∗∗ ‖x‖∗∗ ,
12
Beispiel:
‖A‖p := maxx 6=0
‖Ax‖p
‖x‖p.
‖AB‖p = maxx 6=0
Bx 6=0
‖ABx‖p
‖Bx‖p
‖Bx‖p
‖x‖p
≤ maxx 6=0
Bx 6=0
‖ABx‖p
‖Bx‖pmaxx 6=0
‖Bx‖p
‖x‖p
≤ ‖A‖p ‖B‖p .
Proposition 1.12.4 ‖ ◦ ‖F ist submultiplikativ.
Beweis: Sei
A = (a1, . . . , an) ∈ Cm×n, B =
bT1...
bTn
∈ Cn×k .
DannAB = a1 bT
1 + · · ·+ an bTn .
Dreiecksungleichung:
‖A B‖F ≤ ‖a1 bT1 ‖F + · · ·+ an bT
n‖F
= ‖a1‖2 ‖b1‖2 + · · ·+ ‖an‖2 ‖bn‖2
≤( n∑
i=1
∥∥ai
∥∥2
2
) 12( n∑
i=1
∥∥bi
∥∥2
2
) 12
= ‖A‖F ‖B‖F .
2
Weitere wichtige Normen sind:
‖A‖1 = maxj=1,...,n
m∑
i=1
|aij | Spaltensummenorm
‖A‖∞ = maxi=1,...,n
n∑
j=1
|aij| Zeilensummennorm
‖A‖1 = ‖AT‖∞, A = AH =⇒ ‖A‖1 = ‖A‖∞ .
Die Norm ‖ ◦ ‖2 einer Matrix A ∈ Cm×n steht in engem Zusammenhang mit ρ(A), σ1(A).
13
Theorem 1.12.5 Sei σ1(A) maximaler Singularwert von A. Dann ist
‖A‖2 =√
ρ(AHA) =√
ρ(AAH) = σ1(A) .
Bemerkung 1.12.6 A = AT =⇒ ‖A‖2 = ρ(A), AHA = I =⇒ ‖A‖2 = 1.
1.13 Skalarprodukt und Orthogonalitat
Definition 1.13.1 Sei V ein Vektorraum uber K. Eine Bilinearform (·, ·) : V × V → K heisstSkalarprodukt, falls gilt:
∀x, y, z ∈ V, ∀γ, λ ∈ K : (γx + λy, z) = γ(x, z) + λ(y, z) , (S1)
(y, x) = (x, y) (S2)
(x, x) > 0 fur alle x 6= 0 . (S3)
Beispiel: V = Cn: (x, y) = yHx =
n∑
i=1
xi yi.
Es gilt Q, A ∈ Cn×n ⇐⇒
∀x, y ∈ Cn : (Ax, y) = (x, AHy)
(Qx, Qy) = (x, QHQy) .
Unitare Matrizen lassen die Euklidische Norm eines Vektors x invariant.
Proposition 1.13.2 Q ∈ Cn×n unitar, d.h. QHQ = I. Dann gilt:
‖Qx‖2 = ‖x‖2 ∀x ∈ Cn .
Beweis: ‖Qx‖22 = (x, QHQx) = (x, x) = ‖x‖2
2. 2
Definition 1.13.3 x, y ∈ Rn orthogonal ⇐⇒ x>y = 0 und wir schreiben symbolisch:
x ⊥ y .
14
1.14 Gram-Schmidt Algorithmus
Seien r ≥ 1 Vektorenx1, . . . , xr ∈ Cm
gegeben. Der Gram-Schmidt Algorithmus erzeugt aus (*) eine neue Familie von r Vektoren
q1, . . . , q
r∈ Cm
derart, dass giltspan{x1, . . . , xr} = span{q
r, . . . , q
r} (1.14.1)
und die qisind paarweise orthogonal:
qi⊥ q
jfur 1 ≤ i, j ≤ r, i 6= j . (1.14.2)
Der Gram-Schmidt Algorithmus ist definiert wie folgt:
Algorithmus 1.14.1 (Gram-Schmidt)
input x1, . . . , xr ∈ Cn.
q1
:= x1,
for k = 1, . . . , r − 1 do:
qk+1 := xk+1 −k∑
i=1
(qi, xk+1)
(qi, q
i)
qi.
Eigenschaften der qk verifiziert man direkt. Etwa (1.14.2) durch Induktion: sei (1.14.2) schonfur 1 ≤ i, j ≤ k bewiesen. Dann folgt fur ` ≤ k aus Algorithmus 1.14.1, dass gilt
(q`, qk+1) = (q`, xk+1) −k∑
i=1
(qi, xk+1)
(qi, qi)(q`, qi)︸ ︷︷ ︸
δ`i
= (q`, xk+1) −(q`, xk+1)
(q`, q`)(q`, q`) = 0 ,
woraus (1.14.2) folgt.
In Algorithmus 1.14.1 waren r, m beliebig. Fur r > m ergeben (1.14.1) und (1.14.2), dasseinige der q
iverschwiinden mussen. Genauer gilt:
Proposition 1.14.2 Falls die xi vollen Rang r haben, gilt (1.14.1) mit q1, . . . , q
r6= 0. Falls
jedochs = dim(span{x1, . . . , xr}) < r
ist, so sind r − s > 0 Vektoren der q1, . . . , q
rgleich 0.
Als eine Anwendung des Gram-Schmidt Algorithmus erhalten wir das Basiserganzungslemma:
15
Lemma 1.14.3 Sei r < n. Falls V 1 = [v1, . . . , vr] ∈ Cn×r orthonormale Spalten hat, d.h.vH
i vj = δij, dann existiert V 2 ∈ Cn×(n−r) derart, dass die Matrix
V =[V 1 V 2
]
unitar ist, d.h. V HV = 1, und (rangeV 1)⊥ = rangeV 2.
Beweis des Basiserganzungslemmas 1.14.3 Es besagt: falls die Matrix V 1 = [v1, . . . , vt] ∈ Cn×t,t < n, orthonormale Spalten hat mit vH
i vj = δij, dann existieren vt+1, . . . , vn derart, dass dieMatrix
V = [V 1 V 2], wo V 2 := [vt+1, . . . , vn]
unitar ist, d.h. V HV = 1, und (range V 1)⊥ = range V 2.
Fur den Beweis wenden wir den Gram-Schmidt Algorithmus 1.14.1 an auf die r Vektoren
{x1, . . . , xr} = {v1, . . . , vt, e1, . . . , en} ,
wobei r = n + t ist. Gram-Schmidt reproduziert dann die v1, . . . , vt (beweisen!) und ergibtweitere n Vektoren q
1, . . . , q
nmit
{qi, q
j} = δij , (vi, qj
) = 0, 1 ≤ i ≤ t, 1 ≤ j ≤ n .
Da dim(span{x1, . . . , xr}) = n > t ist, sind n−t Vektoren der qi6= 0 und t der q
iverschwinden.
Eine Anwendung der Normen und der Orthogonalitat ist der Beweis der sogenannten Sin-gularwertzerlegung.
1.15 Singularwertzerlegung (SVD)
Die SVD einer Matrix A ergibt: “totale Information” uber Matrix A, und ist, anders als dieJordan Normalform, stabil berechenbar.
Theorem 1.15.1 Sei A ∈ Cm×n, r = rang(A). Dann existieren σ1 ≥ σ2 ≥ · · · ≥ σr > 0,U ∈ Cn×n, V ∈ Cm×m, unitar mit
A = V Σ UH (1.15.1)
wo
Σ =
σ1
. . . 0σr
0. . .
00
∈ Rm×n .
16
Beweis von Theorem 1.15.1. Sei x ∈ Cn, y ∈ Cm Vektoren mit ‖x‖2 = ‖y‖2 = 1, und σ ∈ R
mitAx = σ y, wobei σ = ‖A‖2 .
Nach Lemma 1.14.3 existiert U 2 ∈ Cn×(n−1), V 2 ∈ Cm×(m−1) derart, dass die Matrizen
U =[x U 2
]∈ Cn×n, V =
[y V 2
]∈ Cm×m
unitar sind. Weiterhin gilt
V HAU =[y V 2
]HA[x U 2
]=
yH Ax yH AU 2
V H2 Ax V H
2 AU 2
=:
σ wH
0 B
=: A1 .
Da
∥∥∥∥∥A1
(σ
w
)∥∥∥∥∥
2
2
=
∥∥∥∥∥σ2 + wHw
B w
∥∥∥∥∥
2
2
= (σ2 + wHw)2 + ‖B w‖22 ≥ (σ2 + wHw)2 ,
gilt auch
∥∥A1
∥∥2
2= sup
0 6=x∈Cn
∥∥A1 x∥∥2
2
‖x∥∥2
2
≥
∥∥∥A1
(σw
)∥∥∥2
2
∥∥∥σw
∥∥∥2
2
≥(σ2 + wHw)2
σ2 + wHw= σ2 + wHw . (1.15.2)
Da auch σ2 = ‖A‖22 = ‖V H A U‖2
2 = ‖A1‖22, folgt aus (1.15.2), dass gilt
∥∥A1
∥∥2
2≥∥∥A1
∥∥2
2+ wHw woraus folgt 0 ≤ wHw ≤ 0, d.h. w = 0 .
Also ist
A1 =
σ 0T
0 B
= V H
0 A0 U 0 .
Rekursion dieser Schlussweise auf B =⇒ Behauptung. �
Korollar 1.15.2 Die Singularwerte σ1, . . . , σr sind eindeutig.
Korollar 1.15.3 Falls σ1 > σ2 > · · · > σr, u1, . . . , ur, sind ei Singularvektoren v1, . . . , vr
eindeutig bis auf einen Faktor λ mit |λ| = 1.
Bild und Kern einer Matrix A ∈ Cm×n konnen durch die singularen Vektoren charakterisiertwerden:
17
Korollar 1.15.4 Sei A ∈ Cm∈n, r ≤ min{m, n} der Rang von A. Dann gilt:
Aui =
{σi vi 1 ≤ i ≤ r ,
0 r + 1 ≤ i ≤ n .
AH vi =
{σi ui 1 ≤ i ≤ r ,
0 r + 1 ≤ i ≤ m .
Korollar 1.15.5
A =
r∑
i=1
σi vi uHi .
Korollar 1.15.6 Sei A ∈ Cm×n, A = V H ΣU . Dann
ker A = span{ur+1, . . . , un} ,
range A = span{v1, . . . , vr} ,
ker AH = span{vr+1, . . . , vm} ,
range AH= span{u1, . . . , ur} .
Korollar 1.15.7 σi(A) =√
λi(AHA), i = 1, . . . , p
Beweis:A = V ΣUH =⇒ AH = U ΣHV H =⇒
AHA = U ΣH V HV︸ ︷︷ ︸I
ΣUH =⇒
λi(AHA) = ΣH Σ =
(σi(A)
)2.
2
Also gilt fur A hermitesch: AH = A =⇒
AHA = A2 ∧ σi =√
λ2i = |λi|, i = 1, . . . , n .
σ1 ≥ σ2 ≥ · · · ≥ σr > σr+1 = · · · = σp = 0
=⇒ r = rank(A), ker(A) = span{vr+1, . . . , vn} ,
range(A) = span{u1, . . . , ur} .
Definition 1.15.8 Sei A = V ΣUH ∈ Cm×m. Dann ist Σ = V HAU = diag(σ1, . . . , σr, 0, . . . , 0).Die Matrix
A+ := U Σ+V H ∈ Cn×m
mit
Σ+ = diag( 1
σ1, . . . ,
1
σr, 0, . . . , 0
)
heisst Penrose Pseudoinverse von A.
18
2 Computerarithmetik
2.1 Gleitkommazahlen
Mathematische Modelle beschreiben Phanomene quantitativ mittels unendlicher Systeme vonZahlen. Beispiele sind die rationalen Zahlen Q (abzahlbar unendlich) sowie die reellen ZahlenR (uberabzahlbar unendlich).
Auf einem Computer stehen bei alphanumerischen Rechnungen immer nur endlich viele,sogenannte Gleitkommazahlen zur Verfugung, die wir generisch mit F (fur “floating pointnumbers”) bezeichnen, und die je nach Hersteller und Compiler variieren. Es gilt immer
F ⊂ Q ⊂ R, |F| < ∞ . (2.1.1)
Definition 2.1.1 Gleitkommazahlen sind die Teilmenge F von R von Zahlen der Form
x = (−1)s · (0 · a1a2, . . . , at) · βe = (−1)s · m · βe−t , (2.1.2)
wobei
• β ∈ N, β ≥ 2 die Basis der Gleitkommazahl x ∈ F ist,
• t ∈ N die Anzahl der erlaubten signifikanten Stellen ai von x ∈ F ist, mit
0 ≤ ai ≤ β − 1 , (2.1.3)
• m = a1a2a3, . . . , at eine ganze Zahl, die sogenannte Mantisse, ist, mit
0 ≤ m ≤ βt − 1 , (2.1.4)
• e eine ganze Zahl, der Exponent von x ∈ F in (2.1.2) ist; er variiert in einem endlichenIntervall, d.h.
L ≤ e ≤ U (2.1.5)
mit L < 0, U > 0 ganz, und
• s das Vorzeichen von x ∈ F ist.
Falls N Speicherpositionen fur x ∈ F zur Verfugung stehen, gilt die Aufteilung
s → eine Position
m → t Positionen
e → N − t − 1 Positionen.
Bemerkung 2.1.2 x ∈ F in (2.1.2) ist auch gegeben durch
x = (−1)s βe(a1
β+
a2
β2+ · · ·+
at
βt
). (2.1.6)
19
Bemerkung 2.1.3 Darstellung (2.1.2) ist nicht eindeutig - um Eindeutigkeit zu erhalten,nehmen wir immer an:
a1 6= 0 . (2.1.7)
a1 heisst fuhrende Stelle. Dann gilt
0 < βt−1 ≤ m ≤ βt − 1 . (2.1.8)
Insbesondere ist also dann x = 0 nicht in F. Deshalb treffen wir
Konvention 2.1.4 Die Menge aller x ∈ F wie in (2.1.2) ist
F(β, t, L, U) = {0} ∪{x ∈ R : x = (−1)sβe
t∑
i=1
ai β−i}
, (2.1.9)
die Menge der Gleitkommazahlen mit t signifikanten Stellen, Basis β ≥ 2, Ziffern 0 ≤ ai ≤ β−1und Exponentenbereich (L, U) mit L ≤ e ≤ U , mit (2.1.7).
Bemerkung 2.1.5 Es gilt
x ∈ F(β, t, L, U) =⇒ −x ∈ F(β, t, L, U) , (2.1.10)
xmin := βL−1 ≤ |x| ≤ βU(1 − β−1) =: xmax , (2.1.11)
|F(β, t, L, U)| = 2(β − 1) βt−1(U − L + 1) + 1 . (2.1.12)
Bemerkung 2.1.6 (Nicht normalisierte Gleitkommazahlen)
Aus (2.1.11) folgt fur x ∈ R mit 0 < |x| < xmin, dass x /∈ F. Dies kann behoben werdendurch Aufgeben von a1 6= 0 nur fur diese x. Damit erhalt man x der Form (2.1.6) mit1 ≤ m ≤ βt−1 − 1, x ∈ (−βL−1, βL−1). Damit ist immer noch die Darstellung (2.1.9) eindeutigund die Menge aller solcher x der Form (2.1.9) heisst FD ⊃ F. Es gilt
min{|x| 6= 0 : x ∈ FD(β, t, L, U)
}= βL−t . (2.1.13)
Auf den meisten Rechnern hat man einfach und doppelt genaue Zahlen. Fur binareGleitkommazahlen (β = 2) ist
N = 32 fur einfach genaue Zahlen wie folgt verteilt:
1 8 bits 23 bitss e m
N = 64 fur doppelt genaue Zahlen:
1 11 bits 52 bitss e m
20
Bemerkung 2.1.7 (IEEE/IEC Standard)
Die Gleitkommadarstellung wurde 1985 durch das “Institute of Electronics and ElectricalEngineers” (IEEE) entwickelt und 1989 durch die “International Electronical Commission (IEC)als Standard IEC 559 angenommen. Es gilt:
β t L U
IEEE single 2 24 −125 128
IEEE double 2 53 −1021 1024
und, fur die Ausnahmewerte 0,±∞:
Wert Exponent Mantisse
± 0 L − 1 0
±∞ U + 1 0
NaN U + 1 6= 0
2.2 Runden mit Maschinenepsilon
Zwei Zahlen x, y ∈ F, x 6= y, konnen nicht beliebig nahe zueinander liegen. Es gilt fur
0 6= x ∈ F : β−1 εM |x| ≤ min{|x − y| : y ∈ F\{0}
}≤ εM |x| , (2.2.1)
mit dem “Maschinenepsilon” εM .
Definition 2.2.1 (Maschinenepsilon εM)
Die kleinste Zahl 0 < εM ∈ F mit 1 + εM > 1 heisst Maschinenepsilon; es gilt
εM = β1−t . (2.2.2)
Es erfullt εM = min{|1−y| : y ∈ F\{1}
}. Folgender MATLAB code findet εM +2.2204 ·10−16:
e=1; while(1+e>1) e=e/2; end; 2*e
Fig. 1: MATLAB code zur Bestimmung von εM in MATLAB
Beachte, dass Operationen zwischen x, y ∈ F nicht Ergebnisse in F liefern mussen; es gilt
x, y ∈ F impliziert nicht x ◦ y ∈ F .
Hier steht ◦ fur eine generische Operation, 0 ∈ {+,−, ∗, /}, ◦ : R × R → R.
Abhilfe schafft hier die Rundung von x ◦ y.
21
Definition 2.2.2 (Rundung)
Sei F(β, t, L, U) Gleitkommazahlen. Die Rundung f` ist eine Abbildung. f`: R → F
definiert fur x ∈ R in der normalisierten Positionsdarstellung
0 6= x = (−1)s βe∞∑
j=1
aj β−j ∈ R
mit Exponent L ≤ e ≤ U durch
f((x) := (−1)s (0, a1a2, . . . , at) βe , (2.2.3)
wobei
at :=
{at fur at+1 < β/2 ,
a1 + 1 fur at+1 ≥ β/2 .
Proposition 2.2.3
x ∈ F =⇒ f`(x) = x,
x, y ∈ R ∧ x ≤ y =⇒ f`(x) ≤ f`(y).
Bemerkung 2.2.4 (Abschneiden)
Alternativ zur Rundung kann man auch Abschneiden. Dann ist f` wie in (2.2.3), mitat = at.
Bemerkung 2.2.5 (Uberlauf/Unterlauf)
(2.2.3) gilt nur fur x ∈ R mit Exponent e ∈ [L, U ]. Fur x ∈ (−∞,−xmax) ∪ (xmax,∞) istf`(x) in (2.2.3) nicht definiert.
Sei x, y ∈ F und z = x ◦ y ∈ R. Falls
|z| = |x ◦ y| > xmax(F) := max{|x| : x ∈ F}
sprechen wir von Uberlauf, fur
|z| = |x ◦ y| < xmin(F) := min{|x| : 0 6= x ∈ F}
von Unterlauf.
Theorem 2.2.6 Sei F = F(β, t, L, U) ⊂ R und z ∈ R gegeben im Bereich von F, d.h. mit
xmin(F) ≤ |z| ≤ xmax(F) . (2.2.4)
Dann gibt es δi ∈ R mit
f`(z) = z(1 + δ1), |δi| < u :=1
2β1−t, i = 1, 2, (2.2.5)
f`(z) = z/(1 + δ2) . (2.2.6)
22
Beweis: (2.2.5): ohne Beschrankung der Allgemeinheit sei z > 0. Dann ist
z = mβe−t, βt−1 ≤ m < β1 − 1 .
Also istF 3 z− := bmc βe−t ≤ z ≤ dme βe−t =: z+ ∈ F ,
d.h. z liegt zwischen den Gleitkommazahlen z−, z+ ∈ F. Also ist f`(z) ∈ {z−, z+} und
|f`(z) − z| ≤|z+ − z−|
2≤
βe−t
2.
Daher folgt|f`(z) − z|
|z|≤
12mβe−t
m βe−t=
1
2β1−t =: u .
Hier gilt Gleichheit nur dann, wenn m = βt−1. Dann aber ist z = f`(z) ∈ F, deshalb gilt|δ| < u. (2.2.6) beweist man analog. 2
Bemerkung 2.2.7 Die Zahl
u =1
2β1−t =
1
2εM (2.2.7)
heisst Rundungseinheit (Unit Roundoff) von F(β, t, L, U).
Beispiele fur die Werte der Maschinenarithmetik sowie von u enthalt die folgende Tabelle:
Machine and arithmetic β t L U u
Cray-1 single 2 48 -8192 8191 4 × 10−15
Cray-1 double 2 96 -8192 8191 1 × 10−29
DEC VAX G format, double 2 53 -1023 1023 1 × 10−16
DEC VAX D format, double 2 56 -127 127 1 × 10−17
HP 28 and 48G calculators 10 12 -499 499 5 × 10−12
IBM 3090 single 16 6 -64 63 5 × 10−7
IBM 3090 double 16 14 -64 63 1 × 10−16
IBM 3090 extended 16 28 -64 63 2 × 10−33
IEEE single 2 24 -125 128 6 × 10−8
IEEE double 2 53 -1021 1024 1 × 10−16
IEEE extended (typical) 2 64 -16381 16384 5 × 10−20
Tab. 2.1: Floating point arithmetic parameters
23
2.3 Gleitkommaoperationen
Wir sehen, dass ◦ ∈ {+,−, ∗, /} aus F hinausfuhrt: F ◦ F /∈ F im Allgemeinen.
Definition 2.3.1 (Maschinenoperationen)
Fur x, y ∈ F mit x ◦ y im Bereich von F heisst
x ◦ y := f`(f`(x) ◦ f`(y)
)∈ F (2.3.8)
Maschinenoperation zu ◦.
Fur die Analyse von Algorithmen benutzen wir wegen (2.2.5), (2.2.6) das sogenannte Stan-dardmodell des Rundungfehlers: fur jede Maschinenoperation gilt
x ◦ y = (x ◦ y)(1 + δ), |δ| ≤ u, ◦ = +,−, ∗, / . (2.3.9)
Bemerkung 2.3.2 (Petaflop)
Die aktuellen Grossrechner fuhren bis zu 1015 Operationen ◦ / Sekunde aus. In MATLABdouble precision ist u = 1
2εM = 1
22−53 ≈ 10−16, so dass Akkumulation von δ’s in (2.3.9) schnell
die Grosse 1 ergibt, falls (im schlechtesten Fall) bei jeder Operation ◦ der maximale Fehlerδ = u realisiert wird.
24
3 Direkte Losung Linearer Gleichungssysteme: Gauße-
limination (GEM)
Wir schreiben lineare Gleichungssysteme in der Form
Ax = b; (3.0.1)
hier ist A ∈ Rn×n eine regulare Matrix, b ∈ Rn ist gegeben, und x ∈ Rn ist die gesuchte Losung.Die Matrix A und die Vektoren x, b haben die Komponenten
A =
a11 a12 · · · · · · a1n
a21 a22 · · · · · · a2n...
.... . .
......
.... . .
...an1 an2 · · · · · · ann
, x =
x1
x2......
xn
, b =
b1
b2......bn
.
3.1 Gaußscher Algorithmus
3.1.1 Dreiecksmatrizen
Wir betrachten zuerst einmal zwei Spezialfalle von Matrizen A. Wir sagen, daß A eine linkeDreiecksmatrix (oft auch: untere Dreiecksmatrix) ist, falls
aij = 0 fur alle i, j mit i < j.
Analog sprechen wir von A als einer rechten Dreiecksmatrix (oft auch: obere Dreiecksmatrix),falls
aij = 0 fur alle i, j mit i > j.
Linke Dreiecksmatrizen werden meist mit L bezeichnet und rechte Dreiecksmatrizen mit R.Die Namensgebung ist aus der Struktur der Matrix leicht verstandlich:
L =
a11 0 · · · · · · 0a21 a22 0 · · ·
a31 a32. . .
. . ....
......
. . .. . . 0
an1 an2 · · · ann−1 ann
, R =
a11 a12 · · · · · · a1n
0 a22 · · · · · · a2n
0 0. . .
......
.... . .
. . ....
0 0 · · · 0 ann
.
(Im englischsprachigen Raum werden Matrizen dieses Typs typischerweise mit L und U furlower und upper bezeichnet.) Hat die Matrix A in (3.0.1) linke oder rechte Dreiecksgestalt,dann ist das Losen des Gleichungssystems besonders einfach. Bei Losen von
Lx = b
spricht man von Vorwartssubstitution und beim Losen von
Rx = b
25
spricht man von Ruckwartssubstitution. Die Namensgebung erfolgt aus der Tatsache, daß manbeim Losen von Lx = b die Unbekannten xi sukzessive “vorwarts” bestimmt d.h. zuerst x1 =b1/a11, mit dessen Hilfe man x2 bestimmt, dann x3 u.s.w. Bei Losen von Rx = b werden dieUnbekannten xi sukzessive “ruckwarts” bestimmt, d.h. zuerst xn = bn/ann, dann damit xn−1,dann xn−2 u.s.w. Dieses Vorwarts- und Ruckwartseinsetzen formalisieren wir in den folgendenzwei Algorithmen
Algorithmus 3.1.1 (Vorwartssubstitution) Sei A eine Linksdreiecksmatrix mit aii 6= 0 furi = 1, . . . , n. Dann kann die Losung x von Ax = b wie folgt berechnet werden:for i from 1 to n do {
xi :=1
aii
(bi −
i−1∑
k=1
aikxk
)(Konvention: leere Summe = 0)
}
Algorithmus 3.1.2 (Ruckwartssubstitution) Sei A eine Rechtsdreiecksmatrix mit aii 6= 0fur i = 1, . . . , n. Dann kann die Losung x von Ax = b wie folgt berechnet werden:for i from n to 1 by −1 do {
xi :=1
aii
(bi −
n∑
k=i+1
aikxk
)(Konvention: leere Summe = 0)
}
Man uberzeugt sich leicht davon, daß in beiden Algorithmen fur jedes i auf der rechten Seiteder Zuweisung Objekte stehen, die bereits in einem vorangehenden Schritt bestimmt wurden.
Definition 3.1.3 Die Menge der n× n-Linksdreiecksmatrizen wird mit Ln bezeichnet. Fernerdefinieren wir L1
n := {L ∈ Ln |Lii = 1, i = 1, . . . , n}.
Die Linksdreiecksmatrizen und Rechtsdreiecksmatrizen bilden je einen Ring:
Theorem 3.1.4 Es gilt fur beliebige L, L′ ∈ Ln:
1. L + L′ ∈ Ln;
2. L · L′ ∈ Ln;
3. det L =∏n
i=1 Lii;
4. Ist L ∈ Ln regular, dann ist L−1 ∈ Ln;
5. falls L ∈ L1n, L′ ∈ L1
n, dann ist L · L′ ∈ L1n.
Analoge Aussagen gelten fur Rechtsdreiecksmatrizen.
Beweis: Ubung (vgl. Aufgabe 1). Die Aussagen fur Rechtsdreiecksmatrizen folgen aus denenfur Linksdreiecksmatrizen durch Transposition. 2
26
Theorem 3.1.5 Seien Lk ∈ Rn×n, k = 1, . . . , n − 1 Linksdreiecksmatrizen von der Form
Lk =
1. . .
1lk+1k 1
.... . .
ln k 1
.
Dann ist
L−1k =
1. . .
1−lk+1 k 1
.... . .
−ln k 1
.
Ferner hat das Produkt L1L2 · · ·Ln−1 die Darstellung
L1L2 · · ·Ln−1 =
1
l21. . .
l31. . . 1
... lk+1k 1
......
. . .. . .
ln1 ln2 · · · ln k · · · lnn−1 1
.
Beweis: Ubung (vgl. Aufgabe 2). Satz 3.1.4 zeigt bereits, daß die Matrizen Lk invertierbarsind und daß das Produkt eine Linksdreiecksmatrix sein muß, dessen Diagonaleintrage 1 sind.2
3.1.2 Gaußscher Algorithmus und LR-Zerlegung
Im vorhergehenden Abschnitt haben wir gesehen, daß gestaffelte Gleichungssysteme (d.h. solche,bei denen die Matrix A linke oder rechte Dreiecksgestalt hat) besonders einfach aufzulosen sind.Der Gaußsche Algorithmus fuhrt nun den allgemeinen Fall auf diese beiden Falle zuruck, indemer eine Matrix A in ein Produkt aus einer Linksdreiecksmatrix und einer Rechtsdreiecksmatrixzerlegt:
A = LR. (3.1.2)
Ist eine solche Zerlegung bekannt, dann kann das Gleichungssystem (3.0.1) mithilfe einerVorwarts- und einer Ruckwartssubstitution gelost werden. Fuhrt man namlich den Hilfsvektory = Rx ein, so ergibt sich b = Ax = LRx = L(Rx) = Ly; dies fuhrt auf folgende Vorge-hensweise:
1. lose das Gleichungssystem Ly = b fur y mithilfe von Algorithmus 3.1.1;
27
2. lose das Gleichungssystem Rx = y fur x mithilfe von Algorithmus 3.1.2.
Definition 3.1.6 Sei A ∈ Rn×n. Dann besitzt A eine LR-Zerlegung, falls es eine Rechts-dreiecksmatrix R und eine Linksdreiecksmatrix L ∈ L1
N gibt, so daß A = LR.
Hat eine regulare Matrix A eine LR-Zerlegung, so ist diese eindeutig:
Theorem 3.1.7 Sei A ∈ Rn×n regular und habe eine LR-Zerlegung LR = A. Dann ist Rii 6= 0fur i = 1, . . . , n, und die Zerlegung ist eindeutig.
Beweis: Wegen 0 6= det A = det L · det R =∏n
i=1 Rii folgt die erste Behauptung. SeienLR = A = L′R′ zwei LR-Zerlegungen von A. Dann sind nach obiger Uberlegung R und R′
invertierbar (ihre Determinanten verschwinden nicht). Somit gilt
L′R′ = LR =⇒ L−1L′ = R(R′)−1.
Nach Satz 3.1.4 ist L−1L′ ∈ L1n; ebenfalls nach Satz 3.1.4 ist R(R′)−1 eine Rechtsdreiecksmatrix.
Die einzige Matrix, die zugleich Linksdreiecksmatrix und Rechtsdreiecksmatrix ist und einElement von L1
n ist, ist die Identitat. Also ist R = R′ und L = L′.Die Voraussetzung der Regularitat von A ist wesentlich fur die Eindeutigkeitsaussage, wie
das Beispiel (1 00 1
)·
(0 10 0
)=
(0 10 0
)=
(1 0−1 1
)·
(0 10 1
)
zeigt. 2
finis 1.DS
Die LR-Zerlegung einer Matrix A ∈ Rn×n geschieht in n − 1 Schritten. Zur Motivation desAlgorithmus schreiben wir das Gleichungssystem (3.0.1) aus:
a11 x1 + a12 x2 + · · · + a1n xn = b1
a21 x1 + a22 x2 + · · · + a2n xn = b2...
......
......
......
......
......
......
......
......
...an1 x1 + an2 x2 + · · · + ann xn = bn
Es wird nun von der zweiten, dritten, etc. Zeile ein geeignetes Vielfaches der ersten Zeilesubtrahiert, um die Variable x1 in Zeilen 2 bis n zu eliminieren. Wir definieren also (fura11 6= 0)
li1 :=ai1
a11, i = 2, . . . , n
und ziehen von der i-ten Zeile das li1-fache der ersten Zeile ab. Wir erhalten damit ein Glei-chungssystem von der folgenden Form:
a11 x1 + a12 x2 + · · · + a1n xn = b1
a(1)22 x2 + · · · + a
(1)2n xn = b
(1)2
......
......
......
......
......
......
......
a(1)n2 x2 + · · · + a
(1)nn xn = b
(1)n
28
wobei die neuen Koeffizienten a(1)ij gegeben sind durch
a(1)ij = aij − a1j li1, i, j = 2, . . . , n,
b(1)i = bi − b1 li1, i = 2, . . . , n.
Offenbar kann man (falls a(1)22 6= 0) nun ahnlich weitermachen, um in den Zeilen 3 bis n die
Variable x2 zu eliminieren. Dies geschieht, indem man
li2 :=a
(1)i2
a(1)22
, i = 3, . . . , n
setzt und dann von der i-ten Zeile (i ≥ 3) das li2-fache der 2-ten Zeile abzieht. Auf diese Weiseerhalt man dann ein System der Form
a11 x1 + a12 x2 + a13 x3 + · · · + a1n xn = b1
a(1)22 x2 + a
(1)23 x3 + · · · + a
(1)2n xn = b
(1)2
a(2)33 x3 + · · · + a
(2)3n xn = b
(2)3
......
......
......
...
a(2)n3 x3 + · · · + a
(2)nn xn = b
(2)n
Nach (n − 1)-Schritten erhalt man dann eine schließlich ein System von Gleichungen, dasRechtsdreiecksgestalt hat:
a11 x1 + a12 x2 + a13 x3 + · · · + a1n xn = b1
a(1)22 x2 + a
(1)23 x3 + · · · + a
(1)2n xn = b
(1)2
a(2)33 x3 + · · · + a
(2)3n xn = b
(2)3
. . .. . .
. . ....
......
. . .. . .
......
...
a(n−1)nn xn = b
(n−1)n
Die Zahlen a(k−1)kk , k = 1, . . . , n − 1, die wahrend der Eliminationschritte auftreten, heißen
Pivots1. Offensichtlich mussen wir verlangen, daß die Pivots nicht verschwinden, d.h. a(k−1)kk 6= 0
fur k = 1, . . . , n − 1. Die berechneten Koeffizienten lij und das Endschema ergeben dann diegesuchte LR-Zerlegung: Wir setzen
L :=
1
l21. . .
l31. . . 1
... lk+1,k 1
......
. . .. . .
ln1 ln2 · · · ln k · · · ln,n−1 1
, R :=
a11 a12 · · ·
0 a(1)22 a
(1)21 · · ·
... 0 a(2)33 a
(2)34
.... . .
. . ....
. . .. . .
0 · · · · · · · · · 0 a(n−1)nn
1Bonaparte Pivot, 1.4.1769–1.4.1821, mit dem Spitznamen “der gute Teiler”
29
und behaupten, daß A = LR gilt. Um dies einzusehen, schreiben wir die entstandenen Glei-chungssysteme in Matrixschreibweise. Im k-ten Eliminiationschritt hat das Gleichungssystemdie Form
A(k)x = b(k)
wobei A(k), b(k) folgende Form haben:
A(k) =
a11 a12 a13 · · · · · · · · · a1n
a(1)22 a
(1)23 · · · · · · · · · a
(1)2n
. . ....
......
...
a(k)k+1k+1 a
(k)k+1 k+2 · · · a
(k)k+1 n
......
......
a(k)n k+1 a
(k)n k+2 · · · a
(k)nn
, b(k) =
b1
b(1)2...
b(k)k+1
b(k)k+2...
b(k)n
. (3.1.3)
Wir setzen aus Notationsgrunden
A(0) := A, b(0) := b.
Fur die Ausfuhrung des k-ten Schrittes werden die Faktoren
lik :=a
(k−1)ik
a(k−1)kk
, i = k + 1, . . . , n,
benotigt. Die Verbindung unseres Vorgehens mit der gesuchten LR-Zerlegung von A ist nun,daß A(k) aus A(k−1) durch Multiplikation mit eine speziellen Linksdreiecksmatrix ergibt: Setztman
Lk :=
1. . .
1−lk+1,k 1
.... . .
−ln k 1
, (3.1.4)
so kann man nachrechnen (Ubung!), daß gilt:
A(k) = LkA(k−1) und b(k) = Lkb
(k−1), k = 1, . . . , n − 1. (3.1.5)
Man erhalt alsoA(n−1) = Ln−1Ln−2 · · ·L1A
(0) = Ln−1Ln−2 · · ·L1A.
Da alle auftretenden Linksdreiecksmatrizen Lk regular sind (vgl. Satze 3.1.4, 3.1.5), konnen wirdies umschreiben als
LR = A,
wobeiL := L−1
1 L−12 · · ·L−1
n−1, R = A(n−1).
30
Hier ist R eine Rechtsdreiecksmatrix nach Konstruktion (vgl. (3.1.3)), und L ist eine Links-dreiecksmatrix nach Satz 3.1.4. Aus Satz 3.1.5 erhalten wir
L−1k =
1. . .
1lk+1,k 1
.... . .
ln k 1
(3.1.6)
und damit—wiederum aus Satz 3.1.5—fur die Eintrage in L ganz explizit:
L = L−11 L−1
2 · · ·L−1n−1 =
1
l21. . .
l31. . . 1
... lk+1,k 1
......
. . .. . .
ln1 ln2 · · · ln k · · · ln,n−1 1
(3.1.7)
Wir haben also eine explizite Konstruktion einer LR-Zerlegung von A gefunden: Die Eintrageder Linksdreiecksmatrix L sind die Faktoren lik, die im Laufe des Algorithmus bestimmt werdenund die Rechtsdreiecksmatrix R ist gerade das Endschema des Gaußschen Algorithm, die MatrixA(n−1). Wir konnen unser Vorgehen in dem folgenden abstrakten Algorithmus, der GaußschenElimination ohne Pivotsuche festhalten:
Algorithmus 3.1.8 (Rohfassung der LR-Zerlegung ohne Pivotsuche)A(0) := Afor k from 1 to n − 1 do {
1. bestimme Matrix Lk (vgl. (3.1.4)) durch Berechnung der Faktoren
lik =A
(k−1)ik
A(k−1)kk
, i = k + 1, . . . , n
2. setze A(k) := LkA(k−1)
}LR-Zerlegung von A ist A = LR mit R = A(n−1) und L gegeben durch (3.1.7).
Fur eine Computerimplementierung von Algorithmus 3.1.8 mussen die Matrixmultiplikationennoch explizit ausgeschrieben werden. In tatsachlichen Implementierungen wird man direkt“auf” der Matrix A operieren, d.h. sie wahrend des Algorithmus verandern. Dies geschieht ausSpeicherplatzgrunden, weil man nicht Speicher fur die n Matrizen A(0), A(1), . . . bereitstellenkann/will. In dieser Form erhalt man dann
31
Algorithmus 3.1.9 (LR-Zerlegung ohne Pivotsuche)input: Matrix Aoutput: Linksdreiecksmatrix L und Rechtsdreiecksmatrix R mit LR = AL := Idn = Identitatsmatrix der Große n × nfor k from 1 to n − 1 do {
for i from k + 1 to n do {
Lik :=Aik
Akk% k-te Spalte von L
for j from k to n do { % k-te Zeile von R und updaten der Zeilen k + 1, . . . , n von AAij := Aij − LikAkj
}}
}setze R := Rechtsdreiecksanteil von Areturn (L,R)
In der formulierten Form geht die Matrix A in Algorithmus 3.1.9 verloren, da sie mit derRechtsdreiecksmatrix R uberschrieben wird. In der rechentechnischen Praxis wird zudem weiterSpeicher gespart: Nach Beendigung von Algorithmus 3.1.9 enthalt die Matrix im oberen Teildie gesuchte Rechtsdreiecksmatrix R. Der untere Teil enthalt noch den unteren Teil der Origi-nalmatrix A (man uberzeuge sich davon, daß Algorithmus 3.1.9 den unteren Teil von A nichtverandert). Der untere Teil der Matrix A hat genausoviele Eintrage wie zum Abspeichern derLinksdreiecksmatrix L genotigt werden (die Diagonaleintrage von L sind alle 1 und mussendaher nicht gesondert abgespeichert werden). In den meisten Implementierungen von LR-Zerlegungen wird deshalb einfach nur die Matrix A ∈ Rn×n ubergeben, und zuruckgegebenwird wieder eine Matrix A ∈ Rn×n, in der die wesentliche Information uber die Faktoren L undR gespeichert ist:
Aij =
{Rij falls j ≥ i
Lij falls j < i(3.1.8)
Eine Implementierung dieses Algorithmus ist dann wie folgt:
Algorithmus 3.1.10 (LR-Zerlegung ohne Pivotsuche: klassische Implementierung)
input: Matrix Aoutput: uberschreibt die Matrix A mit ihrer LR-Zerlegung (vgl. (3.1.8))for k from 1 to n − 1 do {
for i from k + 1 to n do {
Aik :=Aik
Akk% k-te Spalte von L
for j from k+1 to n do { %k-te Zeile von R und updaten der Zeilen k + 1 . . . , n von AAij := Aij − AikAkj
}}
}return (A)
Das Losen eines linearen Gleichungssystems (3.0.1) wird deshalb wie folgt durchgefuhrt:
32
LR-Zerlegung (Algorithmus 3.1.11)1
3n(n − 1)(n + 1)
Vorwartssubst. (Algorithmus 3.1.1 unter Ausnutzung von Lii = 1)1
2n(n − 1)
Ruckwartssubst. (Algorithmus 3.1.2)1
2n(n + 1)
Gesamtkosten1
3n3 + n2 −
1
3n ≈
1
3n3
Tabelle 3.1: Kosten fur das Losen eines linearen Gleichungssystems mit Algorithmus 3.1.11.
Algorithmus 3.1.11 (Gauß-Algorithmus ohne Pivotsuche)
1. Bestimme LR-Zerlegung von A mithilfe von Algorithmus 3.1.10.
2. Lose Ly = b mithilfe der Vorwartssubstitution Algorithmus 3.1.1. Dabei beachtet man,daß die Diagonalelemente von L gilt: Lii = 1.
3. Lose Rx = y mithilfe der Ruckwartssubstitution Algorithmus 3.1.2.
In Tabelle 3.1 sind die Kosten beim Losen eines linearen Gleichungssystems mithilfe von Algo-rithmus 3.1.11 zusammengestellt. Wir haben nur die Multiplikationen/Divisionen gezahlt unddie Additionen vernachlassigt. Wie man sieht, sind die Kosten (fur große n) dominiert durch dieLR-Zerlegung. Bereits fur n = 100 machen die Vorwarts- und Ruckwartssubstitionen zusam-men nur 3% der Gesamtkosten aus. Ein positiver Nebeneffekt ist, daß, falls eine LR-Zerlegungerst einmal aufgestellt ist, das lineare Gleichungssystem (3.0.1) fur viele verschiedene rechteSeiten b billig gelost werden kann.
Bemerkung 3.1.12 In der LR-Zerlegung in Algorithmus 3.1.10 haben wir nicht den Fall abge-fangen, daß ein sog. Pivot A
(k−1)kk = 0 sein konnte. Algorithmus 3.1.10 versagt deshalb bereits
bei dem trivialen Beipiel
A =
(0 11 0
).
Der Behandlung solcher Falle werden wir uns im Abschnitt 3.3 zuwenden.
Abschließend stellen wir einen zu Algorithmus 3.1.10 aquivalenten Algorithmus zur Bestim-mung der LR-Zerlegung vor.
Algorithmus 3.1.13 (Doolittle Variante der LR-Zerlegung)for k from 1 to n do {
Lkk = 1for j from k to n do { % Berechne k-te Zeile von R
Rkj := Akj −∑k−1
l=1 LklRlj %Konvention: leere Summe = 0}for i from k + 1 to n do { % Berechne k-te Spalte von L
Lik :=1
Rkk
(Aik −
k−1∑
l=1
LilRlk
)%Konvention: leere Summe = 0
33
}}
Man beachte, daß der Algorithmus wohldefiniert ist, da die Rechtsdreiecksmatrix R zeilenweiseund die Linksdreiecksmatrix L spaltenweise aufgebaut wird. Fur jedes k werden von L nurdie Spalten 1 bis k − 1 und von R nur die Zeilen 1 bis k − 1 benotigt, die bereits berechnetwurden. Algorithmus 3.1.13 stellt die Matrizen L und R in genau derselben Reihenfolge auf wieAlgorithmus 3.1.10. Von Interesse ist jedoch, daß er aus folgenden Uberlegungen hergeleitetwerden kann: Fur jedes i, j gilt fur die LR-Zerlegung von A:
Aij =n∑
l=1
LilRlj .
Aus der Tatsache, daß L Linksdreiecksmatrix, R Rechtsdreiecksmatrix und Lii = 1, folgt damit
Aij =
i−1∑
l=1
LilRlj + Rij ,
Aij =
j−1∑
l=1
LilRlj + RjjLij .
Auflosen dieser beiden Gleichungen nach Rij und Lij ergibt dann die Ausdrucke in Algorith-mus 3.1.13.
3.1.3 LR-Zerlegung fur schwach besetzte Matrizen
Die LR-Zerlegung in Algorithmus 3.1.10 geht von einer vollbesetzten Matrix A aus. In derPraxis (z.B. in der Strukturmechanik und bei der Diskretiersierung von partiellen Differen-tialgleichungen) sind die auftretenden Matrizen oft schwach besetzt (engl. sparse), d.h. vieleEintrage von A sind gleich Null. Dies kann in zweierlei Hinsicht ausgenutzt werden:
1. Speicherersparnis: Man speichert nicht die gesamte Matrix A ab, sondern nur die wesentlicheInformation, d.h. welche Eintrage von Null verschieden sind und was ihre Werte sind.
2. Die Matrizen L, R der LR-Zerlegung von A sind ebenfalls schwach besetzt. Auch hierkann Speicher und Rechenzeit eingespart werden, indem nur die nicht-trivialen Eintragevon L und R berechnet werden.
Im folgenden stellen wir zwei Typen von schwach besetzten Matrizen vor: Bandmatrizen undSkyline-Matrizen. Selbstverstandlich decken diese beiden Typen nicht alle in der Praxis auftre-tenden Falle von schwach besetzten Matrizen ab.
Bandmatrizen
Definition 3.1.14 Eine Matrix A ∈ Rn×n heißt eine Bandmatrix mit Bandbreite p + q + 1,falls es p, q ∈ N0 mit
aij = 0 fur j > i + p oder i > j + q.
Die Zahl p heißt die oberere Bandbreite und q die untere Bandbreite.
34
Bandmatrizen haben also nichtverschwindende Eintrage hochstens auf den p Nebendiagonalenuber der Hauptdiagonalen und auf den q Nebendiagonalen unter der Hauptdiagonalen:
a11 a12 · · · a1,p+1 0 · · · · · · 0a21 a22 · · · · · · a2,p+2 0 · · · 0...
.... . .
. . . 0
aq+1,1 aq+1,2. . .
. . . 0
0 aq+2,2. . . an−p,n
... 0. . .
. . ....
......
. . .. . .
...0 0 · · · 0 an,n−q · · · an,n−1 ann
(3.1.9)
Um diese Matrix darzustellen, brauchen wir nur (p + q + 1)n − p(p+1)2
− q(q+1)2
reelle Zahlenabzuspeichern. Auch die LR-Zerlegung einer Bandmatrix erbt die spezielle Struktur:
Theorem 3.1.15 Sei A ∈ Rn×n eine Bandmatrix mit oberer Bandbreite p und unterer Band-breite q und LR-Zerlegung LR = A. Dann haben L, R Bandstruktur, und es gilt:
Lij = 0 falls j > i oder j < i − q
Rij = 0 falls j < i oder j > i + p.
Beweis: Die Ausssage des Satzes folgt durch sorgfaltige Untersuchung von Algorithmus 3.1.13.Man sieht recht einfach, daß die Aussage richtig ist fur die erste Zeile von R und die ersteSpalte von L. Dann schließt man induktiv fur die weiteren Zeilen/Spalten mithilfe von Algo-rithmus 3.1.13. 2
finis 2.DS
Satz 3.1.15 sagt aus, daß die Matrizen L, R der LR-Zerlegung der Bandmatrix A aus (3.1.9)folgende Struktur haben:
L =
1 0 · · · · · · · · · · · · · · · 0l21 1 0 · · · · · · · · · · · · 0...
.... . .
. . . 0
lq+1,1 lq+1,2. . .
. . . 0
0 lq+2,2. . .
. . ....
0 0. . .
. . .. . .
...
0 0. . .
. . . 00 0 · · · 0 ln,n−q · · · ln,n−1 1
35
LR-Zerlegung (Algorithmus 3.1.16) ≈ nqp
Vorwartssubst. (Alg. 3.1.1; Ausnutzen der Bandstruktur von L) ≈ nq
Ruckwartssubst. (Alg. 3.1.2; Ausnutzen der Bandstruktur von R) ≈ np
Gesamtkosten Multiplikationen/Divisionen ≈ n(pq + p + q)
Tabelle 3.2: Kosten beim Losen von Gleichungssystemen mit Bandmatrizen
R =
r11 r12 · · · r1,p+1 0 · · · · · · 00 r22 · · · · · · r2,p+2 0 · · · 0... 0
. . .. . . 0
......
. . .. . .
. . . 0...
.... . .
. . . rn−p,n...
.... . .
. . ....
......
. . .. . .
. . ....
0 0 · · · · · · · · · 0 rnn
Die Tatsache, daß die Matrizen L und R auch wieder schwach besetzt sind, wird bei Algorithmenzur Bestimmung von LR-Zerlegungen von Bandmatrizen ausgenutzt. Es brauchen insbesonderenur die nicht-trivialen Eintrage von L, R berechnet zu werden. Dies fuhrt auf die folgendeVariante von Algorithmus 3.1.10, bei dem die beiden inneren Schleifen verkurzt werden konnen.
Algorithmus 3.1.16 (LR-Zerlegung fur Bandmatrizen)input: Matrix A mit oberer Bandbreite p und unterer Bandbreite qoutput: uberschreibt die Matrix A mit ihrer LR-Zerlegungfor k from 1 to n − 1 do {
for i from k + 1 to min {n, k + q} do {
Aik :=Aik
Akkfor j from k + 1 to min {n, k + p} do {Aij := Aij − AikAkj
}}
}return (A)
Die Bandstruktur von L und R wird ebenfalls bei der Vorwarts- und Ruckwartssubstitution aus-genutzt (Ubung: Man formuliere die entsprechenden Varianten von Algorithmen 3.1.1, 3.1.2).Die Kosten der Algorithmen sind in Tabelle 3.2 zusammengestellt. Es werden nur Multiplika-tionen und Divisionen gezahlt und vereinfachend n � max {p, q} angenommen.
Skyline-Matrizen
Ein wichtiger weiterer Spezialfall der schwach besetzten Matrizen sind die sog. Skyline-Matrizen(engl.: skyline matrices). Dies sind Matrizen, wie auf der linken Seite in Fig. 3.1 illustriert.
36
Figur 3.1: Striche deuten von Null verschiedene Eintrage an. Links: Skyline-Matrix, bei derdie Besetzungsstruktur bei LR-Zerlegung erhalten bleibt. Rechts: Keine Skyline-Matrix unddie LR-Zerlegung erhalt nicht die Besetzungsstruktur.
A =
1 1 11 2 2
1 3 31 2 3 5 18
1 51 6
1 2 3 18 5 6 92
L = R> =
11
11 2 3 1
11
1 2 3 4 5 6 1
Figur 3.2: A ∈ R7×7 und ihre LR-Zerlegung.
Eine Matrix A ∈ Rn×n heißt eine Skyline-Matrix, falls es fur i = 1, . . . , n Zahlen pi, qi ∈ N0
gibt, so daßAij = 0 falls j < i − pi oder i < j − qj . (3.1.10)
Es gilt dann
Theorem 3.1.17 Sei A ∈ Rn×n eine Skyline-Matrix, d.h. es gebe pi, qi mit (3.1.10). Moge Adie LR-Zerlegung A = LR haben. Dann gilt fur die Eintrage von L und R:
Lij = 0 fur j < i − pi, Rij = 0 fur i < j − qj .
Beweis: Wie in Satz 3.1.15 kann die Aussage mithilfe von Algorithmus 3.1.13 eingesehenwerden (Ubung). 2
Satz 3.1.17 besagt, daß die Faktoren L und R der LR-Zerlegung einer Skyline-Matrix A dieselbeBesetzungsstruktur haben wie A. Figur 3.2 zeigt dies fur ein einfaches Beispiel. Das Erhaltender Besetzungsstruktur kann naturlich algorithmisch ausgenutzt werden, sowohl was Speicherangeht als auch bzgl. Rechenzeit, indem nur die nicht-trivialen Eintrage von L und R aus-gerechnet und abgespeichert werden. Dies fuhrt auf Varianten von Algorithmus 3.1.13, dieanalog zum Fall der Bandmatrizen sind. Man beachte, daß man die Matrizen in Fig. 3.1 nichtals Bandmatrix behandeln will, da die Bandbreiten p, q je gleich n waren. Das rechte Beispielin Fig. 3.1 ist keine Skyline-Matrix im Sinne obiger Definition, und die Besetzungsstrukturgeht bei der LR-Zerlegung verloren: L ist i.a. eine volle Linksdreiecksmatrix und R eine volleRechtsdreiecksmatrix (Man spricht bei Zerstorung der Besetzungsstruktur von fill-in).
37
3.2 Symmetrisch positiv definite Matrizen
In vielen Anwendungen treten symmetrische, positiv definite Matrizen auf, die oft zudemschwach besetzt sind. Der Grund hierfur ist, daß diese Matrizen meist von physikalischenModellen stammen, bei denen der Ausdruck x>Ax eine Energie darstellt.
Definition 3.2.1 Sei A ∈ Rn×n. Die transponierte Matrix A> ist gegeben durch
(A>)ij := Aji ∀i, j ∈ {1, . . . , n}.
Eine Matrix A ∈ Rn×n heißt
1. symmetrisch, falls A = A>;
2. positiv definit, falls x>Ax > 0 ∀0 6= x ∈ Rn;
3. positiv semi-definit, falls x>Ax ≥ 0 ∀0 6= x ∈ Rn.
Eine symmetrische, positiv definite Matrix A ∈ Rn×n heißt kurz SPD.
Theorem 3.2.2 Sei A ∈ Rn×n SPD. Dann gilt:
1. A ist regular (invertierbar);
2. Aii > 0 fur alle i ∈ {1, . . . , n};
3. |Aij| < 12(Aii + Ajj) fur i 6= j und damit maxij |Aij| = maxi Aii.
Beweis: Ubung. 2
Theorem 3.2.3 Sei A ∈ Rn×n SPD. Dann existiert ein L ∈ L1n und eine Diagonalmatrix D
mit Dii > 0, i = 1, . . . , n, so daß A = LDL>. Die Matrizen L und D sind eindeutig. Zudem istL, R := DL> die LR-Zerlegung von A, die mithilfe von Algorithmus 3.1.10 bestimmt werdenkann.
Beweis: Wir partitionieren die Matrix A wie folgt:
A(0) = A =
A11 z>
z B
,
wobei z> = (A12, . . . , A1n). Im ersten Schritt der Gaußelimination erhalt man
A(1) = L1A(0) =
A11 z>
0... B′
0
, L1 =
1−l21 1
.... . .
−ln1 1
, (3.2.11)
38
wobei li1 = Ai1/A11. Man beachte, daß nach Satz 3.2.2 A11 > 0. Eine Rechnung zeigt nun, daß
L1AL>1 = A(1)L>
1 =
A11 0 · · · 00... B′
0
.
Hier ist insbesondere die Matrix B ′ unverandert aus (3.2.11) ubernommen. Man rechnet nunnach (oder verwendet den Tragheitssatz von Sylvester2), daß B′ wieder SPD ist, denn dieMatrix L1AL>
1 ist wieder SPD. Mithin kann man dieselbe Argumentation fur B ′ wiederholen.Induktiv schließt man dann, daß
Ln−1 · · ·L1AL>1 L>
2 · · ·L>n−1 =
A11
d22
. . .
dnn
=: D.
Nach Konstruktion sind die Matrizen Lk, k = 1, . . . , n − 1 gerade die Linksdreiecksmatrizen,die in Algorithmus 3.1.11 berechnet werden. Das hier vorgestellte Induktionsargument zeigt,daß der Algorithmus nicht abbricht, weil in jedem Eliminationsschritt das Pivotelement nichtverschwindet (die Diagonalelemente einer SPD-Matrix sind nach Satz 3.2.2 strikt positiv!). DieEindeutigkeit von L (die dann die Eindeutigkeit von D nach sich zieht) folgt aus Satz 3.1.7,weil A = LDL> = L(DL>) eine LR-Zerlegung von A ist. 2
Satz 3.2.3 ist die Basis fur die Cholesky3-Zerlegung einer SPD-Matrix A.
Korollar 3.2.4 Sei A ∈ Rn×n SPD. Dann existiert eine eindeutige Linksdreiecksmatrix L ∈ Ln
mit Lii > 0, i = 1, . . . , n, so daß A = L · L>. Die Matrix L heißt der Cholesky-Faktor von A.
Umgekehrt gilt: Sei L ∈ Ln regular. Dann ist A := L · L>
SPD.
Beweis: Nach Satz 3.2.3 existiert ein L ∈ L1n und eine Diagonalmatrix D mit Dii > 0, so daß
A = LDL>. Wir setzen nun
L := LD1/2,(D1/2
)ij
:= δijD1/2ii .
Dann gilt offensichtlich L · L>
= A. Eindeutigkeit des Cholesky-Faktors: Sei L eine Links-
dreiecksmatrix mit Lii > 0, i = 1, . . . , n und L ·L>
= A. Definiere die Diagonalmatrix D durchDij = δijLii. Dann ist D invertierbar und
L := LD−1
ist ein Element von L1n. Wir haben also
A = L · L>
= LDD>L> = L(DD>)L>.
2Sylvester, James Joseph 1814–18973Cholesky, Andre-Louis, 1875-1918
39
Dies ist eine Zerlegung wie in Satz 3.2.3. Aus der Eindeutigkeitsaussage von Satz 3.2.3 folgtdamit, daß L und DD> eindeutig bestimmt sind. Weil die Diagonalmatrix D positive Diago-naleintrage hat, ist damit auch D eindeutig bestimmt.
Der Beweis der Aussage, daß fur eine regulare Linksdreiecksmatrix L die Matrix L ·L>
SPDist: Ubung. 2
Fur SPD-Matrizen benutzt man anstelle der LR-Zerlegung in der Praxis die Cholesky-Zerlegung.Algorithmisch bestimmt man sie mithilfe einer Variante von Algorithmus 3.1.13:
Algorithmus 3.2.5 (Cholesky-Zerlegung)input: SPD-Matrix A ∈ Rn×n
output: Cholesky-Faktor L von A
for k from 1 to n do {
Lkk :=
(Akk −
k−1∑
j=1
L2
kj
)1/2
%Konvention: leere Summe = 0
for i from k + 1 to n do { % Berechne k-te Spalte von L
Lik :=1
Lkk
(Aik −
k−1∑
j=1
LijLkj
)%Konvention: leere Summe = 0
}}
Daß der Algorithmus das Gewunschte leistet, sieht man in ahnlicher Weise wie bei Algorith-
mus 3.1.13, indem man den Anzatz A = LL>
macht und dann Bestimmungsgleichungen furdie Eintrage von L herleitet:
Aik =
n∑
j=1
LijLkj.
Wegen der Symmetrie von A reicht es, k ≤ i zu betrachten. Nutzt man die Tatsache aus, daßL eine untere Dreiecksmatrix ist, dann folgt:
fur k = i: Akk =
i−1∑
j=1
L2
kj + L2
kk,
fur k < i: Aik =
k−1∑
j=1
LijLkj + LikLkk.
Auflosen nach Lij und Lii ergibt dann die Ausdrucke, die in Algorithmus 3.2.5 auftreten.
Betrachten wir die Kosten der Cholesky-Zerlegung. Aus Algorithmus 3.2.5 geht hervor, daßdie Cholesky-Zerlegung einer SPD-Matrix A mit
∼1
6n3 Multiplikationen/Divisionen und n Quadratwurzeln
berechnet wird. Vernachlassigt man die Kosten fur das Wurzelziehen, dann ist die Cholesky-Zerlegung ungefahr halb so teuer wie die LR-Zerlegung. Die Reduktion um den Faktor 2 liegt
40
daran, daß wegen der Symmetrie der Matrix und der Zerlegung nur ein Faktor der Zerlegungberechnet werden muß.
Da viele in der Praxis auftretenden SPD-Matrizen Bandstruktur haben, formulieren wirnoch die Variante der Cholesky-Zerlegung, die die Bandstruktur ausnutzt.
Algorithmus 3.2.6 (Cholesky-Zerlegung fur SPD Bandmatrizen)input: SPD-Matrix A ∈ Rn×n; oberere Bandbreite p = untere Bandbreite qoutput: Cholesky-Faktor L von A
for k from 1 to n do {
Lkk :=
Akk −
k−1∑
j=max {1,k−p}
L2
kj
1/2
for i from k + 1 to min {n, k + p} do {
Lik :=1
Lkk
Aik −
k−1∑
j=max {1,k−p}
LijLkj
}}
Bemerkung 3.2.7 Algorithmus 3.2.5 zur Bestimmung der Cholesky-Zerlegung kann auch dazubenutzt werden, zu prufen, ob eine gegebene symmetrische Matrix positiv definit ist. Manfuhrt Algorithmus 3.2.5 durch; bricht er ab, weil eine Division durch Null auftritt oder weileine Wurzel aus einer negativen Zahl gezogen werden soll, dann war die Matrix nicht SPD.Andernfalls ist sie SPD (vgl. die zweite Aussage aus Korollar 3.2.4).
3.3 Pivotstrategien & Nachiteration
3.3.2 Spaltenpivotstrategie
Bei unserer Herleitung der LR-Zerlegung nahmen wir stets an, daß die Pivots A(k−1)kk 6= 0. Dies
muß nicht immer der Fall sein, wie die Matrix
A =
(0 11 0
)
zeigt. Die Matrix A ist jedoch regular, und man kann Gleichungssysteme von der Form Ax = blosen, indem man zuerst die Zeilen 1 und 2 vertauscht. Die nach Vertauschung dieser Zeilenerhaltene Matrix Aper hat dann ein von Null verschiedenes Pivot (Aper)11; in diesem Fall hatAper sogar bereits Rechtsdreiecksgestalt.
Man erwartet, daß auch bei kleinen Pivots numerische Schwierigkeiten auftauchen. Folgen-des Beispiel erfullt diese Erwartung:
Beispiel 3.3.11 Wir bestimmen in 4-stelliger Gleitkommaarithmetik F (d.h. β = 10, t = 4)die Losung x des folgenden linearen Gleichungssystems:
A =
(3.1 · 10−4 1
1 1
), b =
(−3−7
).
41
Es ist dann l21 = 1/(3.1 · 10−4) ≈ 3.226 · 103 und die LR-Zerlegung von A ist
L =
(1 0
3.226 · 103 1
), R =
(3.1 · 10−4 1
0 1 − l21
)≈
(3.1 · 10−4 1
0 −3.225 · 103
).
Die Losung von Ly = b fuhrt dann auf
y = L−1b =
(−3
9.671 · 103
)
und damit ist die Losung x von Rx = y
x = R−1y =
(1
3.1·10−4 (−3 − (−2.999))−2.999
)=
(−3.226−2.999
).
Das “exakte” Ergebnis ist x = (−4.001246 . . . ,−2.99875 . . .)>. Hier sind beim Ruckwartseinsetzenin der x1-Komponente durch Ausloschung alle Ziffern verloren gegangen. Der Grund ist dieschlechte Pivotwahl. Wir starteten mit einem sehr kleinen Pivot und erhielten dadurch sehrgroße (und auch sehr kleine) Eintrage in der LR-Zerlegung. Dies fuhrt dann zu Ausloschungbei der Vorwarts- und Ruckwartssubstitution.
Beispiel 3.3.11 zeigt, daß kleine Pivots zu numerischen Instabilitaten bei Vorwarts- und Ruckwarts-substitution fuhren konnen. Daß kleine Pivots gemieden werden sollen, legt folgende Betrach-tung nahe: Wir nehmen an, daß die rechte Seite b und die gesuchte Losung Eintrage haben,die von vergleichbarer Großenordnung sind (wie in Beispiel 3.3.11). Wird bei der Vorwarts-oder Ruckwartssubstitution mit großen Zahlen multipliziert, so entstehen Zwischenergebnisse,die groß sind (wie in Beispiel 3.3.11). Da das Endergebnis wieder moderat ist, erwartet man,daß dies durch Subtraktion vergleichbarer Zahlen erreicht wird—bei diesen Subtraktionen trittdann die Gefahr der Ausloschung auf. Dies ist im obigen Beispiel 3.3.11 eingetreten.
Um das Problem des kleinen Pivots in den Griff zu bekommen, wird deshalb nicht eineLR-Zerlegung der Matrix A gesucht, sondern die LR-Zerlegung einer Matrix Aper, die durchgeeignetes Vertauschen von Zeilen von A entstanden ist. Man beachte, daß fur das Losen vonGleichungssystemen das Vertauschen von Zeilen keine Rolle spielt (wenn man beim Vektor aufder rechten Seite die entsprechende Vertauschung ebenfalls durchfuhrt). Daß Zeilenvertauschennumerisch vorteilhaft sein kann, zeigt folgende Fortsetzung von Beispiel 3.3.11:
Beispiel 3.3.12 Wir losen das lineare Gleichungssystem aus Beispiel 3.3.11, indem wir diebeiden Zeilen von Ax = b vertauschen, d.h. wir betrachten
Aper =
(1 1
3.1 · 10−4 1
), bper =
(−7−3
).
Nun ist l21 = 3.1 · 10−4 und
Lper =
(1 0
3.1 · 10−4 1
), Rper =
(1 10 1 − l21
)≈
(1 10 0.9997
).
Fur die Losungen y, x von Ly = b, Rx = y erhalten wir damit
y =
(−7
−2.998
), x =
(−4.001−2.999
).
42
Wir erhalten also das korrekte Ergebnis bis auf Rundungsgenauigkeit. Da die Permutations-matrix
P =
(0 11 0
)
bei Multiplikation von links an die Matrix A die Zeilen 1 und 2 vertauscht, haben wir alsofolgende Zerlegung erhalten:
LperRper = Aper = PA.
In Beispiel 3.3.12 konnte das lineare Gleichungssystem numerisch stabil gelost werden, indemdie beiden Zeilen des Gleichungssystems vertauscht wurden. Fur eine allgemeine Matrix Aist die richtige Zeilenanordnung naturlich nicht im Voraus bekannt. Sie muß also wahrenddes Algorithmus mitbestimmt werden. Man geht deshalb algorithmisch wie folgt vor (siehe
Algorithmus 3.3.15 unten): In jedem Eliminationsschritt wird nicht einfach A(k−1)kk als Pivot
benutzt, sondern es wird in der Spalte k das betragsgroßte Element A(k−1)ik mit Zeilenindex i ≥ k
gesucht; anschließend werden die Zeilen k und i vertauscht und dann der Eliminationsschrittdurchgefuhrt.
Das Vertauschen von Zeilen in einer Matrix beschreibt man formal am besten im Permuta-tionsmatrizen:
Definition 3.3.13 (Permutationsmatrizen) Sei π : {1, . . . , n} → {1, . . . , n} eine Permu-tation der Zahlen 1, . . . , n (d.h. π ist eine bijektive Abbildung) und bezeiche e1, . . . , en die nEinheitsvektoren: (ei)j = δij. Dann heißt
Pπ :=(eπ(1), eπ(2), . . . , eπ(n)
)
die zu π gehorige Permutationsmatrix.
Lemma 3.3.14 (Eigenschaften von Permutationsmatrizen) Sei π : {1, . . . , n} → {1, . . . , n}eine Permutation und Pπ die zugehorige Permutationsmatrix. Dann gilt:
(i) Pπei = eπ(i) fur i ∈ {1, . . . , n}.
(ii) P−1π = P>
π .
(iii) Die Matrix PπA entsteht aus A durch Zeilenpermutation, d.h. die i-te Zeile von A ist dieπ(i)-te Zeile von PπA, i = 1, . . . , n.
Beweis: Ubung. 2
Der Algorithmus zur LR-Zerlegung mit Pivotsuche ist damit wie folgt:
Algorithmus 3.3.15 (LR-Zerlegung mit Spaltenpivotsuche)A(0) := Afor k from 1 to n − 1 do {
1. suche i ∈ {k, . . . , n} mit |A(k−1)ik | ≥ |A
(k−1)i′k | fur alle i′ ∈ {k, . . . , n}
43
2. setze πk : {1, . . . , n} → {1, . . . , n} die Permutation, die i und k vertauscht:
πk(j) =
i falls j = k,
k falls j = i,
j sonst
3. A(k−1) := PπkA(k−1) % vertausche Zeilen k und i in A(k−1)
4. bestimme Matrix Lk (vgl. (3.1.4)) durch Berechnung der Faktoren
lik =A
(k−1)ik
A(k−1)kk
, i = k + 1, . . . , n
5. setze A(k) := LkA(k−1)
}setze π := πn−1 ◦ πn−2 ◦ · · · ◦ π1
setze P := Pπ
setze R := A(n−1),
L gegeben durch (3.1.7)
return(P,L,R) % LR-Zerlegung von PA ist PA = LR.
Bemerkung 3.3.16 Der Algorithmus wird in der Praxis etwas anders realisiert: wie beim Fallohne Pivotsuche, Algorithmus 3.1.8, operiert man direkt auf der Matrix A und erhalt am Schlußdas Endschema R anstelle von A. Außerdem wird wie in Algorithmus 3.1.10 der Linksdreiecks-faktor L ebenfalls im unteren Teil von A abgespeichert. Die Permutationsmatrix P wird nichtexplizit aufgestellt, sondern es wird nur ein Vektor mit naturlichen Zahlen zuruckgegeben, derangibt, wie die Zeilen von A permutiert werden.
Wir fuhren das Vorgehen an einem einfachen Beispiel vor.
Beispiel 3.3.17
A =
1 2 22 −7 21 24 0
Bei der Pivotsuche in der 1. Spalte, stoßen wir auf die 2. Zeile. Man vertauscht also die 1. und 2. Zeile:
A(0) =
2 −7 21 2 21 24 0
und fuhrt dann den Eliminationsschritt durch. Es ist l21 = 0.5, l31 = 0.5 und damit
A(1) =
2 −7 20 5.5 10 27.5 −1
.
Bei der Pivotsuche in der 2. Spalte mussen wir nun nur die Elemente A(1)22 und A
(1)32 vergleichen. Da A
(1)32
betragsmaßig großer ist als A(1)22 , vertauschen wir die 2. und die 3. Zeile:
A(1) =
2 −7 20 27.5 −10 5.5 1
.
44
Beim nachsten Eliminationsschritt entsteht l32 = 5.527.5 = 0.2. Wir erhalten als Endschema und als Matrix L
R = A(2) =
2 −7 20 27.5 −10 0 1.2
, L =
1 0 00.5 1 00.5 0.2 1
.
Es bleibt, die Permutationsmatrix P zu bestimmen. In Algorithmus 3.3.15 wurde die Permutationen π1, π2
aufgestellt mit
π1(1) = 2, π1(2) = 1, π1(3) = 3
π2(1) = 1, π2(2) = 3, π2(3) = 2.
Damit ergibt sich fur π = π2 ◦ π1:
π(1) = 3, π(2) = 1, π(3) = 2
und somit fur die Permutationsmatrix Pπ
P = Pπ =
0 1 00 0 11 0 0
.
Man hatte die Permutation π auch weniger formal durch Verfolgen der Zeilenvertauschungen erhalten konnen:
die ursprunglich 1. Zeile ist zur 3. Zeile geworden (im ersten Schritt wurden Zeilen 1 und 2 vertauscht, in zweiten
Schritt Zeilen 2 und 3), die ursprungliche 2. Zeile ist zur 1. Zeile geworden, und die ursprunglich 3. Zeile ist am
Schluß die 2. Zeile. Die Permutation π ist damit π(1) = 3, π(2) = 1, π(3) = 2. Man uberzeugt sich davon, daß
in der Tat LR = PA.
Das Losen von Gleichungssystemen erfolgt dann so:
Algorithmus 3.3.18input: regulare Matrix A ∈ Rn×n, b ∈ Rn,
output: Losung x von Ax = b
1. Bestimme P, L, R mithilfe von Algorithmus 3.3.15 so, daß PA = LR.
2. Setze b′ := Pb und lose Ly = b′ mithilfe von Algorithmus 3.1.1.
3. Lose Rx = y mihilfe von Algorithmus 3.1.2.
Bemerkung 3.3.19 Im 2. Schritt von Algorithmus 3.3.18 wird die Multiplikation Pb nicht alsMatrix-Vektor Multiplikation ausgefuhrt, sondern es werden naturlich nur die entsprechendenZeilen in b vertauscht.
Daß Algorithmus 3.3.15 tatsachlich die LR-Zerlegung einer Zeilenpermutation von A liefert,garantiert der folgende Satz.
Theorem 3.3.20 Zu jeder regularen Matrix A ∈ Rn×n existiert eine Permutationsmatrix Pπ,so daß eine Dreieckszerlegung
LR = PπA
moglich ist. Hier ist L ∈ L1n und R ist eine Rechtsdreiecksmatrix. Zudem gilt
|Lij | ≤ 1 ∀i, j ∈ {1, . . . , n}.
45
Beweis: Die LR-Zerlegung und die Permutationsmatrix, deren Existenz im Satz behauptetwird, konstruieren wir mithilfe von Algorithmus 3.3.15. Im ersten Schritt von Algorithmus 3.3.15wird (falls notig) eine Zeilenvertauschung von zwei Zeilen durchgefuhrt, so daß die neue Matrix
A(0) := Pπ1A,
so daß A(0)11 das betragsmaßig großte Element der ersten Spalte von A(0) ist. Die Permuta-
tionsmatrix Pπ1vermittelt dabei die Vertauschung der beiden Zeilen (Pπ1
= Id falls keine
Vertauschung notig ist). Zudem ist A(0)11 6= 0, denn sonst ware die erste Spalte identisch Null
im Widerspruch zur Annahme, daß A regular ist. Weil A(0)11 das betragsgroßte Element in der
ersten Spalte von A(0) ist, gilt fur die Eintrage li1 = A(0)i1 /A
(1)11 , daß |li1| ≤ 1. Wir erhalten also
nach dem ersten Eliminationsschritt mit L1 gegeben durch (3.1.4):
A(1) = L1A(0) = L1Pπ1
A =
A(1)11 ∗ · · · ∗0... B(1)
0
.
Aus der Regularitat von L1, Pπ1und A folgt also 0 6= det A(1) = A
(1)11 det B(1). Mithin ist die
Untermatrix B(1) regular. Wir konnen also mit Algorithmus 3.3.15 fortfahren und erhaltenschließlich
R = A(n−1) = Ln−1Pπn−1Ln−2Pπn−2
· · ·L1Pπ1A, (3.3.12)
wobei die Matrizen Lk alle Eintrage haben, die betragsmaßig durch 1 beschrankt sind. Um dieFrobeniusmatrizen Lk von den Permutationsmatrizen Pπk
zu separieren, schieben wir in derDarstellung von R aus (3.3.12) zwischen die Faktoren Lk und Pπk
die Identitat P−1k Pk, wobei
die Permutationsmatrix Pk gegeben ist durch: Pk := Pπn−1Pπn−2
· · ·Pπk+1(Pn−1 = Idn). Wir
erhalten damit
R = Ln−1P−1n−1Pn−1Pπn−1
Ln−2P−1n−2Pn−2Pπn−2
Ln−3P−1n−3Pn−3Pπn−3
Ln−4P−1n−4Pn−4 · · ·L1P
−11 P1Pπ1
A.
Weil PkPπk= Pk−1, ergibt sich mit der Abkurzung
Lk := PkLkP−1k (3.3.13)
fur R:R = Ln−1Ln−2 · · · L1P0A.
Da P0 als Verkettung von Permutationsmatrizen eine Permutationsmatrix ist, bleibt zu zeigen,daß das Produkt der Matrizen Lk tatsachlich eine Linksdreiecksmatrix ist. Sei π : {1, . . . , n} →{1, . . . , n} eine beliebige Permutation, die nur die Zahlen ≥ k + 1 permutiert (d.h. π(j) = jfur j ≤ k). Dann uberzeugt man sich davon, daß fur eine Frobeniusmatrix Lk von der Form(3.1.4) gilt:
Lk = PπLkP−1π = PπLkP
>π =
1. . .
1−lπk(k+1),k 1
.... . .
−lπk(n),k 1
. (3.3.14)
46
Die oben eingefuhrten Permutationen Pk sind genau von der Art, daß bei den zugehorigePermutationen der Zahlen 1 bis n nur die Zahlen ≥ k + 1 permutiert werden. Also haben dieMatrizen Lk aus (3.3.13) die Darstellung (3.3.14). Aus Satz 3.1.5 folgt damit, daß
L := L−11 L−1
2 · · · L−1n−1
tatsachlich ein Element von L1n ist. Zusatzlich liefert Satz 3.1.5 die explizite Darstellung
L =
1lπ1(2),1 1lπ1(3),1 lπ2(3),2 1
......
. . .
lπ1(n),1 lπ2(n),2 · · · lπn−1(n),n−1 1
Die Permutationsmatrix P0 gehort nach Definition zu einer Permutation der Zahlen 1 bis n,die gerade die Vertauschung der Zeilenindizes wahrend Algorithmus 3.3.15 angibt. 2
Bemerkung 3.3.21 Satz 3.3.20 zusammen mit Algorithmus 3.3.15 kann (zumindest bei derHandrechnung) dazu benutzt werden, festzustellen, ob eine gegebene Matrix A regular ist, daSatz 3.3.20 zeigt, daß Algorithmus 3.3.15 nur abbricht, wenn die gegebene Matrix nicht regularist.
Bemerkung 3.3.22 (Rechtfertigung der Spaltenpivotsuche) Beispiel 3.3.12 zeigte, daßSpaltenpivotsuche die numerische Stabilitat von Algorithmen erhohen kann. Wie unsere Plau-sibilitatsbetrachtungen im Anschluß an Beispiel 3.3.11 gezeigt haben, ist die Spaltenpivotsucheeine sinnvolle Strategie unter einer Annahme an die Skalierung des Problems; wir nahmennamlich an, daß die Eintrage der Losung und der rechte Seite des linearen Gleichungssystemsvon vergleichbarer Große sind. Diese Art der Skalierung kann man erreichen, indem man nichtdas lineare Gleichungssystem Ax = b, sondern das System
(D1AD2)x′ = b′ := D2b, x = D2x
′
betrachtet, wobei D1, D2 geeignete Diagonalmatrizen sind. Algorithmisch ist es jedoch sehrschwer, D1, D2 zu finden; Programme zum Losen linearer Gleichungssysteme uberlassen deshalbdie Skalierung meist dem Benutzer und verwenden hochstens die Spaltenpivotsuche.
Bemerkung 3.3.23 (Vollpivotsuche) Die Spaltenpivotsuche bei der LR-Zerlegung verur-sacht zusatzliche Kosten O(n2), die im Verhaltnis zu den Gesamtkosten O(n3) relativ kleinsind. (Ubung: Geben Sie genau an, wieviele Vergleiche bei der Spaltenpivotsuche gemachtwerden mussen.)
Alternativ zur Spaltenpivotsuche kann auch eine Vollpivotsuche durchgefuhrt werden. Dabeiwird in jedem Schritt des Gaußalgorithmus das betragsmaßig großte Element der Restmatrixgesucht und durch Zeilen- und Spaltenvertauschungen zum Pivot gemacht. Man erhalt aufdiese Weise eine Zerlegung
PπAPπ′ = LR
47
der Matrix A, wobei die Permutationen π, π′ die Zeilen- und Spaltenvertauschungen reprasentieren.Die Eintrage der berechneten Faktoren L, R sind betragsmaßig kleiner als bei Spaltenpivot-suche, so daß man erwartet, daß Gaußelimination mit Vollpivotsuche numerisch stabiler ist.Sie wird jedoch aus Kostengrunden nur sehr selten eingesetzt, denn der zusatzliche Aufwandist nun O(n3).
3.3.3 Existenz von LR-Zerlegungen ohne Spaltenpivotsuche
Pivotstrategien sind oft notig, um numerische Stabilitat beim Losen von Gleichungssystemenzu gewahrleisten. Nachteile sind:
1. Mehraufwand: Fur die Pivotsuche werden zusatzliche O(n2) Operationen benotigt.
2. Verlust der Besetzungsstruktur: Bei Matrizen mit bestimmten Besetzungsstrukturen (z.B.Skyline-Matrizen) kann die Besetzungsstruktur durch die Zeilenvertauschungen verlorengehen. Damit erhohen sich die Kosten fur die Berechnung und die Speicherung der Fak-toren L und R.
Es ist deshalb von Interesse, Klassen von Matrizen auszumachen, bei denen die LR-Zerlegungauch ohne Pivotsuche durchgefuhrt werden kann.
Der folgende Satz charakterisiert die Menge der Matrizen, die eine LR-Zerlegung besitzen:
Theorem 3.3.24 Sei A ∈ Rn×n regular. Dann besitzt A eine LR-Zerlegung genau dann wennalle Hauptminoren Ak, k = 1, . . . , n regular sind. Hierbei ist Ak ∈ Rk×k gegeben durch (Ak)ij =Aij, i, j = 1, . . . , k.
Beweis: Ubung. 2
In der Praxis ist die Regularitat der Hauptminoren nur schwer uberprufbar. Fur die folgendenbeiden Klassen von Matrizen ist jedoch die die Existenz einer LR-Zerlegung gesichert:
1. Symmetrisch positiv definite Matrizen: Satz 3.2.3 garantiert, daß die Cholesky-Faktorisierungohne Pivotsuche durchgefuhrt werden kann.
2. Diagonal dominanten Matrizen: der folgende Satz 3.3.25 zeigt, daß diagonal dominanteMatrizen eine LR-Zerlegung besitzen.
Wir rekapitulieren: Eine Matrix A ∈ Rn×n heißt Zeilen diagonaldominant, falls
|Aii| >∑
j 6=i
|Aij| ∀i ∈ {1, . . . , n}.
Theorem 3.3.25 Es gilt: eine diagonal dominante Matrix hat eine LR-Zerlegung, die mithilfeder Gauss Elimination ohne Pivotsuche, d.h. Algorithmus 3.1.9, bestimmt werden kann.
Beweis: Ubung (vgl. Aufgabe 13). 2
48
3.3.4 Nachiteration
Bei schlecht konditionierten Problemen kann es passieren, daß die Losung, die man mit Algo-rithmus 3.3.18 erhalt, stark fehlerbehaftet ist. Durch Rundungsfehler hat man z.B. nicht dieexakte LR-Zerlegung von PA sondern nur eine Approximation LR. Anstatt nun die approxi-mative LR-Zerlegung zu verwerfen und mit erhohter Rechengenauigkeit die gesamte Rechnungerneut durchzufuhren, wendet man Nachiteration (engl.: iterative refinement/improvement)an.
Es soll Ax = b berechnet werden, und es existiere eine (approximative) LR-Zerlegung LR
von A. Es wird zunachst eine Losung x von LRx = b mithilfe der Algorithmen 3.1.1, 3.1.2bestimmt. Durch Rundungsungenauigkeiten (auch schon beim Aufstellen von L und R) kannes sein, daß die berechnete Losung x zu ungenau ist. Um eine Verbesserung der Losung zuerhalten, wird nun eine Korrektur ∆x der berechneten Losung x gesucht, d.h. wir verlangen,daß x + ∆x die Gleichung A(x + ∆x) = b erfullt. Somit erhalten fur die gesuchte Korrektur∆x die sog. Residualgleichung
A∆x = r := b − Ax. (3.3.15)
Man beachte, daß das Residuum r 6= 0, weil x nicht die exakte Losung unseres ursprunglichenProblems ist. Da fur A bereits eine (approximative) LR-Zerlegung vorliegt, erfolgt das Losender Residualgleichung (3.3.15) wieder einfach nur durch eine Vorwarts- und eine Ruckwarts-substitution. Der folgende Algorithmus formalisiert dieses Vorgehen.
Algorithmus 3.3.26 (Nachiteration)input : (approximative) LR-Zerlegung einer Matrix A, rechte Seite boutput: Losung x von Ax = b
1. Bestimme Losung x von LRx = b mithilfe von Algorithmen 3.1.1, 3.1.2
2. Bestimme das Residuum r = b − Ax mit erhohter Rechengenauigkeit
3. Falls das Residuum r zu groß ist (in einer geeigneten Norm), finde Korrektur
∆x als Losung von LR∆x = r mithilfe von Algorithmen 3.1.1, 3.1.2.
4. setze x := x + ∆x und gehe zu 2.
Wesentlich in der Praxis ist dabei, daß das Residuum im 2. Schritt mit erhohter Genauigkeitausgewertet wird; wurde die LR-Zerlegung z.B. nur in einfacher Genauigkeit bestimmt, so wirddas Residuum in doppelter Genauigkeit ausgewertet. Da wir bereits gesehen hatten, daß dieVorwarts- und Ruckwartssubstitution relativ billig im Vergleich zur LR-Zerlegung sind, ist dieNachiteration vom Standpunkt des Aufwandes eine attraktive Moglichkeit, die Genauigkeiteiner rundungsfehlerbehafteten Losung zu verbessern.
49
