Universität Stuttgart Wissensverarbeitung und Numerik I nstitut für K ernenergetik und E nergiesysteme Numerische Methoden, SS 2003Teil V, Kp. 1010/1 Lösung

10/1

Universität Stuttgart W

isse

nsv

erar

be

itu

ng

un

d N

um

erik

Institut für Kernenergetikund Energiesysteme

Numerische Methoden, SS 2003 Teil V, Kp. 10

Lösung von linearen Gleichungssystemen - Grundlagen

Zu Lösen ist ein Gleichungssystem: A x = b

dabei sind A eine n*n Matrix, x der Vektor der Unbekannten und b der Vektor der rechten

Seite. Lösung ist wo die Inverse von A ist

Bei den Verfahren zur Lösung von Gleichungssystemen unterscheiden wir zunächst zwischen direkten und iterativen Verfahren. Direkte Verfahren lassen sich in der Regel in zwei Schritte unterteilen. Im ersten erfolgt eine Transformation der Systemmatrix derart, dass die neue Matrix leicht invertierbar wird. Leicht invertierbare Matrizen sind etwa Diagonalmatrizen oder Dreiecksmatrizen. Im zweiten Schritt erfolgt die eigentliche Inversion.

Bei iterativen Verfahren wird die Systemmatrix aufgespalten in einen Teil, der leicht invertierbar ist und einen Rest, der im Gleichungssystem der rechten Seite zugeschlagen wird. Die rechte Seite kann daher nur näherungsweise bestimmt werden. Die Näherung ist in den verschiedenen Iterationsschritten zu verbessern.

In diesem Kapitel werden direkte Verfahren vorgestellt.

b A x -1 A -1

10/2


isse

nsv

erar

be

itu

ng

un

d N

um

erik



Diese Fragen sollten Sie beantworten können

Definieren sie den Begriff grosse dünnbesetzte Matrix Was sind Kennzahlen Was ist eine Norm und zu was braucht man sie Wie speichert man grosse Matrizen Wie hängen Speicherung und Effektivität von

Rechenmethoden zusammen Geben Sie die Bedeutung der Kennzahl Norm an

Noch offen: Geben Sie die Bedeutung der Kennzahl Kondition an

10/3


isse

nsv

erar

be

itu

ng

un

d N

um

erik



Kondition

Die Kondition einer Matrix ist ein weiteres Maß für ihre Rechneranpassung. Konditionszahlen können - ähnlich den Normen - verschieden gebildet werden. Gebräuchlich ist das Verhältnis von Normen oder von größtem zu kleinstem Eigenwert.

xAbgilt iggleichzeit

bAxschreiben können wir

bAxstatt1

1

minmaxAAA cond wo

Acond

folgt Daraus

bxAAxb

manerhält tion MultiplikaDurch

1

1

b

b

x

x

10/4


isse

nsv

erar

be

itu

ng

un

d N

um

erik



V10: Gleichungslöser - Direkte Verfahren

Teil V: Gleichungslöser

Kap. 10: Lösung von linearen Gleichungssystemen - Direkte Verfahren

Inhalt: Direkte Verfahren:

Leicht invertierbare Matrizen LU-Zerlegung nach Gauß und Cholesky

Experimente:Lösung eines Gleichungssystems nach Cholesky

10/5


isse

nsv

erar

be

itu

ng

un

d N

um

erik



Beispiele für Gleichungssysteme

nnnnnnn

nn

nn

nn

bxaxaxaxa

bxaxaxaxa

bxaxaxaxa

bxaxaxaxa

...

.......

...

...

...

332211

33333232131

22323222121

11313212111

A volle Matrix

10/6


isse

nsv

erar

be

itu

ng

un

d N

um

erik



Beispielmatrix

10,109,108,107,106.105,104,103,102,101,10

10,99,98,97,96,95,94,93,92,919

10,89,88,87,86,85,84,83,82,81,8

10,79,78,77,76,75,74,73,72,71.7

10,69,68,67,66,65,64,63,62,61,6

10,59,58,57,56,55,54,53,52,51,5

10,49,48,47,46,45,44,43,42,41,4

10,39,38,37,36,35,34,33,32,31,3

10,29,28,27,26,25,24,23,22,212,

10,19,18,17,16,15,14,13,12,11,1

,

aaaaaaaaaa

aaaaaaaaaa

aaaaaaaaaa

aaaaaaaaaa

aaaaaaaaaa

aaaaaaaaaa

aaaaaaaaaa

aaaaaaaaaa

aaaaaaaaaa

aaaaaaaaaa

A

10/7


isse

nsv

erar

be

itu

ng

un

d N

um

erik



Das sollten Sie heute lernen

Was ist ein direktes Verfahren Umwandlung eines Gleichungssystemes in ein lösbares

Problem Grundideen der Verfahren von Gauss und Cholesky

10/8


isse

nsv

erar

be

itu

ng

un

d N

um

erik



Leicht invertierbare Matrizen

Leicht invertierbare Matrizen sind

a) Diagonalmatrizen,

b) tridiagonale Matrizen,

c) blockdiagonale Matrizen,

d) Dreiecksmatrizen.

Im Folgenden werden Verfahren zur Lösung von Gleichungssystemen, deren Systemmatrix eine dieser Formen hat, angegeben.

10/9


isse

nsv

erar

be

itu

ng

un

d N

um

erik



Gleichungssysteme mit Diagonalmatrix D

nnnnbxd

bxd

bxd

bxd

3333

2222

1111

Für Diagonalmatrizen gilt

1111

DdaA

DA

iiii

10/10


isse

nsv

erar

be

itu

ng

un

d N

um

erik



Gleichungssysteme mit tridiagonaler Matrix

nnnn d

d

d

d

x

x

x

x

ac

bac

bac

ba

2

1

3

2

1

333

222

11

Die Lösung von Gleichungssystemen mit tridiagonalen Matrizen erfolgt in 2 Schritten:

Im ersten Schritt wird aus jeder Gleichung eine Unbekannte eliminiert.

Im 2. Schritt wurden die Gleichungen dann aufgelöst.

10/11


isse

nsv

erar

be

itu

ng

un

d N

um

erik



Leicht invertierbare Matrizen - Tridiagonale Matrizen

Hilfsgrößen h1 = -b1 / a1

p1 = d1 / a1 und x1 = p1 + h1 x2

Dann für i = 2 bis n-1:

hi = -bi / (ai + hi-1 ci) pi = (di - pi-1 ci) / (ai + hi-1 ci)

und xi = pi + hi xi-1

nnnnp

p

p

p

x

x

x

x

h

h

h

§

2

1

3

2

1

333

222

11

10

10

10

1

10/12


isse

nsv

erar

be

itu

ng

un

d N

um

erik



Leicht invertierbare Matrizen - Tridiagonale Matrizen

Für i = n kann dann xn berechnet werden:

xn = pn = (dn - pn-1 cn) / (an + hn-1 cn)

Aus der rückläufigen Sequenz i = n-1 bis 1 folgen die restlichen Lösungen:

xi = pi + hi • xi+1

nnnnp

p

p

p

x

x

x

x

h

h

h

§

2

1

3

2

1

333

222

11

10

10

10

1

10/13


isse

nsv

erar

be

itu

ng

un

d N

um

erik



Leicht invertierbare Matrizen - Blocktridiagonale Matrizen

nD

D

D

nX

X

X

nA

nC

BAC

BA

2

1

2

1

222

11

Bei blocktriagonalen Matrizen werden die Matrixelemente selber Matrizen und entsprechend die Vektorelemente Vektoren:

Ai, Bi und Ci sind quadratische kxk-Matrizen und Xi, Di sind Vektoren der Länge k.

10/14


isse

nsv

erar

be

itu

ng

un

d N

um

erik



Leicht invertierbare Matrizen - Blocktridiagonale Matrizen

Beachte: Statt der Rechnung mit Zahlen sind hier Matrizenoperationen und die Lösung von Gleichungssystemen erforderlich.

1

111

11

11

11

11

11

11

1,1

,2

1

iiii

mm

iiiiiii

iii

XHPXmi

PXmi

PCDHCAPBHCAHmi

DAPBAHi

Der Algorithmus für tridiagonale Matrizen kann auf blocktridiagonale Matrizen erweitert werden:

10/15


isse

nsv

erar

be

itu

ng

un

d N

um

erik



Beispiele blocktridiagonaler Matrizen aus Diskretisierung partieller Dgl‘en

1 2 3 4 6 8 10 12

1 x x x

2 x A x B

3 x x x

4 x x x x

C x A x B

6 x x x x

x x x x

8 C x A x B

x x x x

10 x x x

C x A x

12 x x x

1,3 2.3 3,3 4,3

3 6 9 12

1,2 2,2 3,2 4,2

2 5 8 11

1,1 2,1 3,1 4,1

1 4 7 10

K

K

2121

1

x

niu

niu

niu

t

niu

niu

Zeit

O r t

explizit implizit

10/16


isse

nsv

erar

be

itu

ng

un

d N

um

erik



Gleichungssystem mit unterer Dreiecksmatrix L

nnnnnnn bxlxlxlxl

bxlxlxl

bxlxl

bxl

...

.....

332211

3333232131

2222121

1111

ni

i

k kx

ikl

ib

iili

x

...,,2,1

1

1

1

Vorwärts-Substitution

10/17


isse

nsv

erar

be

itu

ng

un

d N

um

erik



Leicht invertierbare Matrizen - Dreiecksmatrizen

ni

i

k kyiklibiil

iy

...,,2,1

1

1

1

1...,1,

1

1

nni

n

x

ikxikuiy

iiuix

Gelingt es also, die Matrix [A] in das Produkt zweier Dreiecksmatrizen aufzuspalten, so kann man mit den angegebenen Formeln das Gleichungssystem lösen. Die Algorithmen von Gauss und Cholesky leisten solche Aufspaltungen.

Vorwärts-Substitution

Rückwärts-Substitution

0

0

jiijlijlLbyL

und

jiijuijuUyxU

Die beiden

Gleichungssysteme mit Dreiecksmatrizen

lassen sich mit folgenden Formeln lösen:

10/18


isse

nsv

erar

be

itu

ng

un

d N

um

erik



Aufspaltung einer Matrizen A in Dreiecksmatrizen

a11 a12 a13 a14

a21 a22 a23 a24

a31 a32 a33 a34

a41 a42 a43 a44

l11

l21 l22

l31 l32 l33

l41 l42 l43 l44

u11 u12 u13 u14

u22 u23 u24

u33 u34

u44

=

*

Eine Matrix A lässt sich als Produkt einer unteren Dreiecksmatrix L und einer oberen Dreiecksmatrix U darstellen. Wegen A = L • U gilt

kjk

ikij ula

10/19


isse

nsv

erar

be

itu

ng

un

d N

um

erik



Aufspaltung einer Matrizen A in Dreiecksmatrizen

Damit wird aus dem Gleichungssystem Ax = b ein System von 2 Gleichungssystemen mit Dreiecksmatrizen

Ax = L • U • x = L • y = b mit U • x = y

Für die Berechnung der n (n+1)-Elemente von L und U stehen aus n2-Gleichungen zur Verfügung.

n weitere Werte müssen festgelegt werden. Häufige Wahlen sind

1. lii = 1 Gauß‘scher Algorithmus

2. lii = uii Cholesky-Verfahren

kjk

ikij ula

10/20


isse

nsv

erar

be

itu

ng

un

d N

um

erik



Der verkettete Gauß‘sche Algorithmus

Die Aufspaltung der Matrix erfolgt in folgenden Teilschritten:

1) Für die n-freien Elemente wird festgelegt: lii = 1

Damit sind alle Elemente der Zeile 1 von bekannt.

A

La11 a12 a13 a14

a21 a22 a23 a24

a31 a32 a33 a34

a41 a42 a43 a44

=

*1l21 1l31 l32 1l41 l42 l43 1

u11 u12 u13 u14

u22 u23 u24

u33 u34

u44

10/21


isse

nsv

erar

be

itu

ng

un

d N

um

erik




2) Man multipliziert Zeile 1 von Matrix mit allen Spalten von Matrix .

Das Ergebnis ist a1i = u1i. Damit sind alle Elemente von Zeile 1 und Spalte 1 von bekannt.

L

a11 a12 a13 a14

a21 a22 a23 a24

a31 a32 a33 a34

a41 a42 a43 a44

=

*1l21 1l31 l32 1l41 l42 l43 1

a11 a12 a13 a14

u22 u23 u24

u33 u34

u44

U

U

10/22


isse

nsv

erar

be

itu

ng

un

d N

um

erik




3) Man multipliziert jetzt die Zeile 2 bis n der Matrix mit der Spalte 1 der Matrix , so ergibt sich

A U

11

111111 u

ia

iloderu

il

ia

L

4) Im nächsten Schritt werden Zeile 2 der Matrix und alle Spalten der Matrix multipliziert. Daraus bestimmt man die Elemente u2i .

5) Entsprechend dem Vorgehen in 3 werden jetzt die Elemente li2 bestimmt.

LU

10/23


isse

nsv

erar

be

itu

ng

un

d N

um

erik




Das Ergebnis dieses Vorgehens läßt sich allgemein angeben

kju

i

k ikl

ija

ijuoder

kju

i

k ikl

iju

ija

giltjiFür

1

1

1

11

:

10/24


isse

nsv

erar

be

itu

ng

un

d N

um

erik




Für i > j gilt:

jju

j

k kjuiklija

ijloder

kjuj

k ikljjuijlija

1

1

1

1

Für i > j gilt:

10/25


isse

nsv

erar

be

itu

ng

un

d N

um

erik



Der verkettete Gauß‘sche AlgorithmusAus diesem Vorgehen lassen sich leicht eine Reihe von Folgerungen ableiten:

a) Sind in einer Zeile die Elemente ai1 bis aim je 0, so sind auch die Elemente li1 bis lim je 0

b) Sind in einer Spalte j die Elemente a1j bis amj je 0, so sind auch die Elemente u1j bis umj je 0.

c) Ist ein Element aij ungleich 0, so sind auch die entsprechenden Elemente der triangularisierten Matrix ungleich 0 und es können zu allen folgenden Elementen von L bzw. U Beiträge erwartet werden.

Durch die Triangularisierung wird die Form der von Null verschiedenen Matrixteile nicht verändert: Es werden aber Gebiete aufgefüllt. Für die Triangularisierung sind also nur solche Speichertechniken möglich, die dieses Auffüllen erlauben.

Die Zahl der Operationen (Multiplikationen) läßt sich nach diesem Vorgehen

abschätzen zu ~

Ein einfacher Trick erlaubt es, das Verfahren auch auf symmetrische Matrizen zu erweitern.

.2

2

nn

10/26


isse

nsv

erar

be

itu

ng

un

d N

um

erik



Das Cholesky-Verfahren -1

Für symmetrische Matrizen gilt AT = A und die Zerlegung nach Gauß ergibt

TI

LDTI

UTAI

UDI

LUI

LA

Wobei der Index I andeutet, dass die Hauptdiagonalelemente 1 sind.

Da diese Zerlegung eindeutig ist, gilt: ILTIU

Das bedeutet

Für i = j gilt: 2/11

12

21

1

i

k kiuiiaiiu

iiukiu

i

k kiuiia

a):

10/27


isse

nsv

erar

be

itu

ng

un

d N

um

erik



Das Cholesky-Verfahren -2

Für i < j gilt:

1

1

1

1

1

i

k kju

kiuija

iiuiju

ijuiiukju

i

k kiuija

Aus Gleichung (a) kann das Diagonalelement uii der Zeile i berechnet werden. Die übrigen Elemente der Zeile i ergeben sich aus (b). So wird [U] zeilenweise (i = 1, ..., n) berechnet. Notwendig ist, dass die Matrix [A] positiv definiert ist, andernfalls kann sich in a) ein negativer Radikand ergeben.

Ein Beispiel soll das Vorgehen beim Cholesky-Verfahren veranschaulichen.

b):

10/28


isse

nsv

erar

be

itu

ng

un

d N

um

erik



Beispiel Cholesky Verfahren 1Gegeben sei das Gleichungssystem

5.4

5.4

0.5

3

2

1

5.35.20.1

5.20.50.2

0.10.20.4

x

x

x

Wir schreiben die Matrix als Produkt UTU, d.h.

33

2322

131211

332313

2212

11

00

00

00

5.35.20.1

5.20.50.2

0.10.20.4

u

uu

uuu

buu

uu

u

Und bestimmen die Elemente von U. Aus der ersten Zeile der Matrizengleichung erhalten wir die drei Gleichungen

1311

1211

211

0.1

0.2

0.4

uu

uu

u

Wir bestimmen daraus die Unbekannten 5.0,0.1,0.20.4 131211 uuu

10/29


isse

nsv

erar

be

itu

ng

un

d N

um

erik



Beispiel Cholesky Verfahren 2

Die zweite Zeile liefert die Gleichungen

232223221312

222

222

212

1211

5.05.2

0.100.5

00.2

uuuuuu

uuu

uu

u11 und u12 sind schon bekannt, so dass nur noch die restlichen beiden Gleichungen gelöst werden müssen. Die Lösung lautet

0.1,0.20.10.5 2322 uu

Schließlich bestimmen wir aus der dritten Zeile die letzte Unbekannte

5.10.125.05.333 u

Durch Vorwärtssubstitution bestimmen wir nun die Komponenten des Hilfsvektors y

3

2

1

5.10.15.0

00.20.1

000.2

5.4

5.4

0.5

y

y

y

10/30


isse

nsv

erar

be

itu

ng

un

d N

um

erik



Beispiel Cholesky Verfahren 3

Damit lassen sich durch Rückwärtssubstitution die Komponenten von x bestimmen:

.0.1,0.0,0.1 123 xxx

Durch „Rückwärtseinsetzen“ erhalten wir die Lösung

Daraus ergeben sich die drei Gleichungen

5.1..,0.15.05.45.1

0.1..,0.15.40.2

5.2..,5.00.2

3213

212

11

yhdyyy

yhdyy

yhdy

5.1

0.1

5.2

5.100

0.10.20

5.00.10.2

3

2

1

x

x

x

10/31


isse

nsv

erar

be

itu

ng

un

d N

um

erik



Anmerkung zu Cholesky Verfahren

Anmerkung:

Man vermeidet das Wurzelzeichen, wenn man auf folgende Darstellung zurückgreift:

DTD

ITI

UDU

UDDDUA1

1

Dann wird für alle i j

Diiii

DkkDkjDki

i

kijDij

uDund

uuuau

/1

1

10/32


isse

nsv

erar

be

itu

ng

un

d N

um

erik



Iterative Verbesserung

Bei den direkten Lösungsverfahren treten Rundungsfehler hauptsächlich bei der Triangularisierung auf.

Löst man über so erhält man eine Lösung .

Bildet man das Produkt der ursprünglichen Matrix und der Lösung so kann man ein Residuum berechnen:

bxA ,bxUL 1x

1x

1r 11 xAbr

Den Beitrag von zur Lösung erhält man aus 1r

11 rxUL Damit kann man verbessern1x

112 xxx

Wiederholt man diesen Vorgang, so werden die Auswirkungen der Triangularisierung immer kleiner. Der Aufwand pro Iterationsschritt beträgt weniger als der für zwei Auflösungen mit dem triangularisierten System.

10/33


isse

nsv

erar

be

itu

ng

un

d N

um

erik



Anwendung - Vergleich der Leistung von Rechnern

Anwendung

Löse ein Matrixproblem mit einer allgemeinen Matrix n = 100 Optimierung der inneren Schleifen n = 1000 3stufige Optimierung n = beliebig skalierbares paralleles Problem

Ergebnisse Vergleichsdaten für ca. 1500 Rechnersysteme verfügbar Bestimmung der TOP 500-Liste

10/34


isse

nsv

erar

be

itu

ng

un

d N

um

erik



Anwendung Vergleich der Leistung von Rechnern -2

Metriken Rmax Leistung in GF/s für das größtmögliche Problem

Nmax Zahl der Spalten/Zeilen für größtmögliches Problem

N 1/2 Zahl der Spalten/Zeilen, für die Rmax erreicht wurde

Rpeak. Theoretische maximale Leistung in GF/s

Juni 2002 Rmax = 35.61 TF/s für Earth Simulation Computer(NEC SX)

Nmax = 1041 216

Laufzeit 5.8 h bei Standard-LU programmiert in FORTRAN

Web site http://www.supercomp.de

10/35


isse

nsv

erar

be

itu

ng

un

d N

um

erik



Diese Fragen sollten Sie beantworten können

Was ist ein direktes Verfahren zur Lösung von Gleichungssystemen

Geben Sie die Grundideen der Verfahren von Gauss und Cholesky an

Wie löst man Probleme mit tridiagonalen Matrizen Was bedeuten Vorwärts- und Rückwärts- Substitution

Documents

Universität Stuttgart Wissensverarbeitung und Numerik I nstitut für K ernenergetik und E nergiesysteme Numerische Methoden, SS 2003Teil V, Kp. 1010/1 Lösung