Universität Stuttgart Wissensverarbeitung und Numerik I nstitut für K ernenergetik und E nergiesysteme Numerische Methoden, SS 2001T V, Kp. 9 9/1 Beispiele

9/1

Universität Stuttgart W

isse

nsv

erar

be

itu

ng

un

d N

um

erik

Institut für Kernenergetikund Energiesysteme

Numerische Methoden, SS 2001 T V, Kp. 9

Beispiele für Gleichungssysteme

nnn d

d

d

d

x

x

x

x

ac

bac

bac

ba

2

1

3

2

1

333

222

11

nnnn bxd

bxd

bxd

bxd

3333

2222

1111

nnnnnnn

nn

nn

nn

bxaxaxaxa

bxaxaxaxa

bxaxaxaxa

bxaxaxaxa

332211

33333232131

22323222121

11313212111

.....

2.) A Diagonalmatrix D

1.) A volle Matrix 3.) A tridiagonale Matrizen

4.) A untere Dreiecksmatrix L

nnnnnnn bxlxlxlxl

bxlxlxl

bxlxl

bxl

...

.....

332211

3333232131

2222121

1111

9/2


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.

Für Diagonalmatrizen gilt

1111

DdaA

DA

iiii

9/3


isse

nsv

erar

be

itu

ng

un

d N

um

erik



Leicht invertierbare Matrizen - Tridiagonale Matrizen

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.

Dazu berechnet man zuerst die Hilfsgröße h1 = -b1 / a1

rechte Seite 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

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

9/4


isse

nsv

erar

be

itu

ng

un

d N

um

erik



Anwendung auf Diskretisierung partieller Dgl‘en

A2)

Abbildung K = j + (i-1) JM

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

1 2 3 4 6 8 10 12

1 x x x

2 x x x x

3 x x x x x

4 x x x x

x x x

6 x x x x

x x x x

8 x x x

x x x x

10 x x x x x

x x x x

12 x x x

1,3 2.3 3,3 4,3

5 11 6 12

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

9 3 10 4

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

1 7 2 8

K

K

A3) Abbildung nach red-black ordering

9/5


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

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. Der Algorithmus für tridiagonale Matrizen kann auf blocktridiagonale Matrizen erweitert werden:

9/6


isse

nsv

erar

be

itu

ng

un

d N

um

erik



Leicht invertierbare Matrizen - Dreiecksmatrizen

ni

i

k kyiklibiiliy

...,,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 tridiagonalen

Gleichungssysteme

lassen sich mit folgenden Formeln lösen:

9/7


isse

nsv

erar

be

itu

ng

un

d N

um

erik



Aufspaltung einer Matrizen A in Dreiecksmatrizen

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

gilt A = L • U, und aus dem Gleichungssystem Ax = b wird 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 = uiiCholesky-Verfahren

Die Aufgabe der Lösung eines allgemeinen Gleichungssystems ist damit, reduziert auf die Aufgabe zwei Gleichungssysteme, mit leicht invertierbaren Matrizen zu lösen.

kjk

ikij ula

kjk

ikij ula

9/8


isse

nsv

erar

be

itu

ng

un

d N

um

erik



Der verkettete Gauß‘sche Algorithmus

111

i1l oder

1111 sichergibt so ,Matrix der 1 Spalteder mit Matrix der bis 2 Zeilen diejetzt ert multipliziMan 3)

bekannt. von 1 Spalte und 1 von ZeileElemente alle sindDamit

.11ist Ergebnis Das .Matrix n Spalten voallen mit Matrix von 1 ert ZeilemultipliziMan 2)

bekannt. von 1 der Zeile Elemente alle sindDamit

1 :festgelegt wirdElementefreien - dieFür 1)

: tenTeilschritfolgenden in erfolgt Matrix der gAufspaltun Die

uiauilia

ULn

UiuiaUL

Liil

n

A

9/9


isse

nsv

erar

be

itu

ng

un

d N

um

erik




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.

Das Ergebnis dieses Vorgehens läßt sich allgemein angeben:

kjui

k iklijaijuoder

kjui

k iklijuija

giltjiFür

1

1

1

11

:

L U

9/10


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:

9/11


isse

nsv

erar

be

itu

ng

un

d N

um

erik




Aus 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 nursolche 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

9/12


isse

nsv

erar

be

itu

ng

un

d N

um

erik



Das Cholesky-Verfahren

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 A:

IU0,5DUmitUTU

IU0,5D0,5DTIU

IUDTIUA

Für i = j gilt:

2/11

12

21

1

i

k kiuiiaiiu

iiuki

ui

k kiuiia

a):

9/13


isse

nsv

erar

be

itu

ng

un

d N

um

erik



Das Cholesky-Verfahren

Für i < j gilt:

1

1

1

1

1

i

k kju

kiuija

iiuiju

ijuiiukj

ui

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):

9/14


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

9/15


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

9/16


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

9/17


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

9/18


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.

Documents

Universität Stuttgart Wissensverarbeitung und Numerik I nstitut für K ernenergetik und E nergiesysteme Numerische Methoden, SS 2001T V, Kp. 9 9/1 Beispiele