<<

. 10
( 31 .)



>>

1. P A = LR
p = (p1 , . . . , pn ) Permutationsvektor

2. Lc = P b
Vorw¨rtseinsetzen: i = 1, . . . , n:
a
i’1
ci = bpi ’ lik ck
k=1

3. Rx = c
Ruckwartseinsetzen: i = n, n ’ 1, . . . , 1:
¨ ¨
n
1
xi = (ci ’ rik xk )
rii k=i+1


3.2.6 Aufwandsbestimmung
Ein wichtiger Aspekt bei der Analyse numerischer Verfahren ist es zu untersu-
chen, wie lange diese Verfahren in der Regel ben¨tigen, um zum gewunschten
o ¨
Ergebnis zu gelangen. Da sich die Rechenzeiten von Computer zu Computer un-
terscheiden, orientiert man sich nicht an der Rechenzeit, sondern an der Anzahl
der Rechenoperationen, die ein Algorithmus ben¨tigt.
o
Das vorgestellte Gauß“Verfahren liefert nach endlich vielen Schritten ein Ergeb-
nis, wobei die Anzahl der elementaren Rechenoperationen von der Dimension
n der Matrix A abh¨ngt. Multiplikationen und Divisionen sind sogenannte we-
a
sentliche Rechenoperationen. Die Auswertung einer wesentlichen Rechenoperation
war im Allgemeinen noch vor einigen Jahren deutlich ™teurer™ als eine Addition
oder Subtraktion (rechnerintern wird nicht in Addition und Subtraktion unter-
schieden). Die Unterschiede verschmelzen jedoch mehr und mehr mit moderenen
Rechnerarchitekturen.
Zur Aufwandsbestimmung z¨hlen wir die Rechenoperationen einfach ab. Zuvor
a
erinnern wir uns an: n
1
i = (n + 1)n
2
i=1
und n
1
i2 = n(n + 1)(2n + 1).
6
i=1
Anzahl der Operationen: (ohne Additionen)
42 Lineare Gleichungssysteme




1. P A = LR
[(n ’ 1) + (n ’ 1)2 ] + [(n ’ 2) + (n ’ 2)2 ] + . . . + [1 + 12 ]
n’1
[(n ’ j) + (n ’ j)2 ] = 1 n(n ’ 1) + 1 n(n ’ 1)(2n ’ 1)
= 2 6
j=1
1
(n3
= ’ n)
3

2. Lc = P b
1 + 2 + . . . + (n ’ 1) = 1 (n2 ’ n)
2

3. Rx = c
1 + 2 + . . . + n = 1 (n2 + n)
2

Gesamtaufwand: 1 n3 + n2 ’ 1 n Multiplikationen. (Additionen: 3 n3 + 1 n2 ’ 5 n)
1
3 3 2 6

Bemerkung 3.8. Der Aufwand und damit die Rechenzeit steigt mit der dritten
Potenz der Zahl der Unbekannten an: O(n3 ).

3.2.7 Algorithmus
Wir formulieren abschließend den Algorithmus.

Programm: P A = LR
fur j = 1, . . . , n :
¨
pj = j
fur j = 1, . . . , n ’ 1 :
¨
Pivotsuche:
max = |ajj |, r=j
fur i = j + 1, . . . , n :
¨
falls |aij | > max :
max = |aij |, r=i
falls max = 0 : STOP A singul¨r
a

Zeilentausch:
falls r > j :
fur k = 1, . . . , n :
¨
hr = ajk , ajk = ark , ark = hr
hi = pj , pj = pr , pr = hi
Transformation:
fur i = j + 1, . . . , n :
¨
aij = aij /ajj
fur k= j + 1, . . . , n :
¨
aik = aik ’ aij ajk
Matrizen mit speziellen Eigenschaften 43




3.3 Matrizen mit speziellen Eigenschaften
Besitzen Matrizen spezielle Eigenschaften, so kann es sich lohnen diese Eigen-
schaften gewinnbringend bei der Implementierung zu berucksichtigen.
¨

3.3.1 Diagonaldominante Matrizen: Diagonalstrategie
Zunachst geben wir Bedingungen an, die die Durchfuhrung der Gauß-Elimination
¨ ¨
ohne Pivotsuche erm¨glichen (Diagonalstrategie).
o
Satz 3.9. Sei A eine (n, n)-Matrix, deren Hauptabschnittsmatrizen Aj regul¨r
a
sind. Dann gibt es eine eindeutige Zerlegung
A = LR
L : linke Dreiecksmatrix mit ljj = 1, j = 1, . . . , n,
R : regul¨re rechte Dreiecksmatrix.
a
Beweis: Der Beweis wird durch Induktion uber n gefuhrt.
¨ ¨
IA: Fur n = 1 ist die Beh. trivial.
¨
IV: Die Beh. sei richtig fur n ’ 1.
¨
IS: Fur eine (n, n)-Matrix ist die folgende Zerlegung zu zeigen.
¨
Ln’1 0
An’1 c Rn’1 r
A= = .
lT 1
aT ann 0 rnn
Nach der Induktionsvoraussetzung gibt es eine Zerlegung
An’1 = Ln’1 Rn’1 .
Fur die gesuchten l, r ∈ IRn’1 , rnn ∈ IR erh¨lt man die Gleichungen
a
¨
(3.13) c = Ln’1 r
lT Rn’1 = aT T
(3.14) ’ Rn’1 l = a
lT r + rnn = ann .
(3.15)
Diese Gleichungen sind eindeutig au¬‚¨sbar, da nach Voraussetzung Ln’1 , Rn’1
o
regular sind.
¨

Mit
(j)
D = diag(rjj ) = diag(ajj )
erhalt man somit die Zerlegung
¨
A=LDR , ljj = 1, rjj = 1.
Die Regularit¨t der Hauptabschnittsmatrizen von A kann mit einer einfachen
a
Bedingung fur die Elemente aij von A nachgepruft werden.
¨ ¨
44 Matrizen mit speziellen Eigenschaften




De¬nition 3.10 (Diagonaldominanz). Die Matrix A heißt diagonaldominant,
wenn n
|aii | > |aik |, (i = 1, . . . , n).
k=1
k=i

Satz 3.11. Bei einer diagonaldominanten Matrix A sind alle Hauptabschnitts-
matrizen regul¨r, also existiert die LR-Zerlegung A = LR.
a
Beweis: Fur die j-te Abschnittsmatrix Aj gelte
¨
fur ein x ∈ IRj .
Aj x = 0 ¨
Zu zeigen ist dann x = 0. W¨re
a
|xr | = max |xi | > 0,
1¤i¤j

so betrachten wir die r-te Gleichung
j
ari xi = 0.
i=1

Zusammen mit
j
|arr | > |ark |
k=1
k=r

ergibt sich hieraus ein Widerspruch:
j
|arr ||xr | = | ark xk |
k=1
k=r
¤ |ark ||xk |
k=r
¤ |ark ||xr | < |arr ||xr |.
k=r



Beispiel 3.12. Die bei der Berechnung von Spline-Funktionen (vgl. Kapitel zur
Interpolation) auftretende tridiagonale Matrix
« 
4 1 0
¬ ·
¬1 41 ·
¬ ·
¬ ·
.. .. ..
¬ ·
. . .
¬ ·
¬ ·
1 4 1

0 14
ist diagonal dominant und damit LR-zerlegbar.
Cholesky“Verfahren 45




Bemerkung 3.13. Spezielle Matrizen, die das Kriterium in Satz 3.9 erfullen,
¨
sind die positiv de¬niten Matrizen (vgl. n¨chsten Abschnitt).
a


3.3.2 Positiv de¬nite Matrizen: Cholesky“Verfahren
De¬nition 3.14. Eine (n, n)“Matrix A heißt symmetrisch, falls A = AT gilt.

De¬nition 3.15. Eine symmetrische (n, n)“Matrix A heißt positiv de¬nit, falls

x ∈ IRn , x = 0
xT Ax > 0,
(3.16) fur alle
¨

gilt.

Die positive De¬nitheit scheint sehr einschr¨nkend zu sein, dennoch ist sie in
a
vielen Anwendungen erfullt.
¨

Bemerkung 3.16. Fur positiv de¬nite Matrizen kann eine LR“Zerlegung ohne
¨
Pivoting durchgefuhrt werden.
¨

Satz 3.17. Sei A positiv de¬nit.

1. Alle Hauptabschnitt-Matrizen von A sind positiv de¬nit und regul¨r. Insbe-

<<

. 10
( 31 .)



>>