Universität Stuttgart Wissensverarbeitung und Numerik I nstitut für K ernenergetik und E nergiesysteme Numerische Methoden, SS 2003Teil V: Kp. 99/1 Was

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 2003 Teil V: Kp. 9

Was wir zur numerischen Lösung von Dglen wissen

Modelle sind Abstraktionen.

Es darf nur Unbedeutendes weggelassen werden Das numerische Modell muss in Einklang mit dem physikalischen und dem

mathematischen Modell sein. Deshalb sind Grundverständnisse beider Modellierungsschritte nötig

Mathematische Grundbeziehungen technischer Modelle sind Erhaltungsgleichungen in integraler und differenzieller Form

Integrale und differenzielle Form legen den Schwerpunkt der Aussage auf unterschiedliche Effekte. Ziel beachten

Drei Auswirkungen der Endlichkeit von Rechnern kennen gelernt

Rundung, Diskretisierung, Abbruch Kondition eines Algorithmus, Konsistenz einer Diskretisierung und

Konvergenz einer Lösung bedeuten

Rundungsfehler, Diskretisierungsfehler, Abbruchfehler werden beherrscht

9/2


isse

nsv

erar

be

itu

ng

un

d N

um

erik



Was wir zur numerischen Lösung von Dglen wissen

Wie diskretisieren wir Funktionen

Was ist ein iteratives Verfahren Nullstellensuche nach Newton

Wie berechnet man für eine Funktion f(x) das Integral in (a,b)

Wie berechnet man die Ableitung der Ordnung n an Stelle xi

Als Differenz aus n+1 Werten Was ist das Ergebnis der Diskretisierung: Differentialgleichung wird

überführt in System von Gleichungen zur Bestimmung von Werten yi

Einfache Lösung für explizite Verfahren

xNayy ii

n

i

0

n

p

n

pxFx 1

i

iii

xg

xgxx

'1

jj

jii

bi

aiH

abdxxf

2

~

9/3


isse

nsv

erar

be

itu

ng

un

d N

um

erik



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 Diagonalmatrizen, Tridiagonale Matrizen und 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.

b A x -1 A -1

9/4


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

9/5


isse

nsv

erar

be

itu

ng

un

d N

um

erik



Beispiele für Gleichungssysteme

nnnn 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 A Diagonalmatrix D

A tridiagonale Matrix

9/6


isse

nsv

erar

be

itu

ng

un

d N

um

erik



Teil V: Gleichungslöser

Kap. 9: Matrizen und ihre Eigenschaften

Inhalt:

Definitonen und RechenregelnSpezielle MatrizenKennzahlenSpeicherung

V9: Matrizen und ihre Eigenschaften

9/7


isse

nsv

erar

be

itu

ng

un

d N

um

erik



Das sollten Sie heute lernen

Was sind grosse dünnbesetzte Matrizen 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

9/8


isse

nsv

erar

be

itu

ng

un

d N

um

erik



Eigenschaften großer, dünn besetzter Matrizen

Diskretisiert man Variablen, so erhält man Vektoren. Bestehen zwischen Variablen Beziehungen in Form von Gleichungen, so führt die Diskretisierung auf Gleichungssysteme. In Gleichungssystemen werden Variablen durch Vektoren und ihre Verbindung über Matrizen beschrieben.

Matrizen sind Gebilde aus n•n Zahlen, Funktionen oder Operatoren. Bei der Diskretisierung von Differentialgleichungen entstehen große (n, m >> 106) und in der Regel dünnbesetzte Matrizen (nur etwa 10 n Elemente ungleich Null). Im Folgenden werden Eigenschaften dünnbesetzter Matrizen beschrieben, die im Kontext der numerischen Lösung von Differentialgleichungen Bedeutung haben.

9/9


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

9/10


isse

nsv

erar

be

itu

ng

un

d N

um

erik



Rechenregeln: Addition und Subtraktion

Bezeichnung:

torSpaltenvekoderSpalte:1m

orZeilenvektoderZeile:1n

,1;,1,

mkniaoderAoderA ik

Identität: Zwei Matrizen sind dann und nur dann gleich, wenn ihre Elemente gleich sind

kiBA ,allefürafolgtAus ik

ReihenundSpaltenvonAnzahlgleiche

habenundungVoraussetz BAnSubtraktio

baBAAddition ikik

9/11


isse

nsv

erar

be

itu

ng

un

d N

um

erik



Rechenregeln: Multiplikation und Division

CBACBA

ABBA

baBAtionMultiplikaj

jkij

! :Beachte

B vonZeilender Zahlder

gleichist A vonSpaltender ZahlDie:ungVoraussetz

formuliert der Problemals

Operation die wirdnStattdesse

angegeben.explizitseltenwird

vonInverseheißt

BAB/A

angebbar Regelneinfachen keine sind Es:

systemenGleichungs vonLösung

1

1

1

1-

-B

B

BB

Division

9/12


isse

nsv

erar

be

itu

ng

un

d N

um

erik



Rechnen mit dünnbesetzten Matrizen

Bei Rechenoperationen müssen Addition und Multiplikation genauer untersucht werden

Dünnbesetzte Matrizen bestehen vor allem aus 0 Elementen. Für solche Elemente ergeben Addition und Multiplikation keine Beiträge

Operationen mit dünnbesetzten Matrizen werden also besonders effektiv, wenn Operationen mit 0 Elementen möglichst vermieden werden.

Werden Operationen auf 0 Elemente nicht durchgeführt, so müssen diese Elemente auch nicht gespeichert werden.

Wie Datenstrukturen die Effektivität von Algorithmen bestimmen, wird am Beispiel der Matrizenrechnung besonders deutlich

Die Effektivität von Algorithmen wird auch durch die Eigenschaften einer Matrix (z.B. Kondition) bestimmt. Vereinfacht können Eigenschaften dünnbesetzter matrizen durch Kennzahlen abgeschätzt werden

9/13


isse

nsv

erar

be

itu

ng

un

d N

um

erik



Speicherung großer MatrizenGroße Matrizen können nicht ganz im Kernspeicher gehalten werden. Man muß deshalb versuchen, möglichst wenig redundante Information zu speichern oder die Matrizen zu unterteilen. Folgende Techniken haben sich bewährt:

a) Speichern der gesamten Matrix variabel dimensioniert - 1d Feld

b) Ausnutzung von Symmetrien - Speichern und Operieren auf Dreiecksmatrizen

c) Ausnutzung der Bandbreite - Speichern und Operieren auf Bandmatrizen

d) Ausnutzen der lokalen Bandbreite - Hier ist ein zusätzliches Feld zur Angabe

der lokalen Bandbreiten notwendig.

e) Elementweise Speicherung - zu jedem Element müssen zwei Indizes

gespeichert werden.

f) Blockweise Speicherung - Hypermatrizen (ab > 1000 Unbekannten)

g) Elemente werden nicht gespeichert, sondern je neu gerechnet.

Die Datenspeicherung hat erheblichen Einfluss auf die Implementierung

der Algorithmen zum Umgang mit Matrizen

9/14


isse

nsv

erar

be

itu

ng

un

d N

um

erik



Spezielle Matrizen - 1

0 Elementeeleenthält vi AMatrix besetzte dünn

erttransporti

hsymmetrisc

hquadratisc

kiT

kiik

aA

aa

mn

Matrizen hequadratiscfür n m Bandbreite

0 Elementeenthält naleHauptdiagoder längs Bandein nur

0

11

Bandmatrix

IAAmitAInverse

DaatrixDiagonalma

IAImitIikatrixEinheitsma

aNullmatrix

ikiiik

ik

ik

9/15


isse

nsv

erar

be

itu

ng

un

d N

um

erik



Spezielle Matrizen - 2

BidiagonalmatrixBandmatrix mit m = 2

Tridiagonalmatrix Bandmatrix mit m = 3

xk

iik

ik

ik

Jdx

dya

a

ikfür

kifüra

Matrix-Jakobi

n verknüpfelogisch Systeme zwei kann

bit) (ein annehmen Werte zweinur kann MatrixBoolsche

atrix Dreiecksmuntere0

atrix Dreiecksmobere0rixDreicksmat

ist beschränkt Zahlen aufnur nicht das ug,ungswerkze Beschreibmächtigessehr ein sind Matrizen

9/16


isse

nsv

erar

be

itu

ng

un

d N

um

erik



Einfache Kenngrößen: Determinante

Für viele Zwecke ist es nützlich, die Informationen einer Matrix in Kennzahlen zusammenzufassen. Dabei können nur bestimmte Aspekte berücksichtigt werden, entsprechend existieren eine Vielzahl von Kenngrößen.

.eliminiert Spalte und Zeile man wenn

,erhält aus man die ist, der Matrix nte Determinadie//wo

//1-Adet

rekursiv Definition

ab. Zahl auf Matrix hequadratiscbildet

det/A /teDeterminan a)

j

ji

AijA

ijA

Aoder

ijji a

////////////////// ABBABAAAAA nT

Die Bedeutung der Determinante kann am Beispiel der Cramer‘schen Regel zur Gleichungsauflösung gezeigt werden.

Rechenregeln

9/17


isse

nsv

erar

be

itu

ng

un

d N

um

erik



Definition Die homogene Gleichung hat nur für bestimmte Werte von -Lösungen. Diese Werte heißen Eigenwerte, die zugehörigen Lösungsvektoren

sind die Eigenvektoren.

Bestimmung der Eigenwerte über die charakteristische Gleichung. Man erhält sie, wenn man die Determinante des Eigenwertproblems bildet. Die charakteristische Gleichung lautet:

Ist eine n-reihige quadratische Matrix so gilt: besitzt genau n Eigenwerte als Wurzeln der charakteristischen Gleichung. Nur für diese Werte existieren

Eigenlösungen oder Eigenvektoren

Eigenvektoren sind nur bis auf Konstante bestimmt, sie müssen normiert werden. Oft Norm 1:

EV zu verschiedenen EW sind linear unabhängig, es können ihren Richtungen, die Eigenrichtungen, zugeordnet werden. Daraus folgt, daß ein beliebiger Vektor nach den EV entwickelt werden kann:

Für die Entwicklungskoeffizienten gilt

Eigenwerte(EW ) und Eigenvektoren(EV )

iBiiA

0//det BA

A A i

i

ijjB

iT

ii

iax

x

ia

xi

a Ti

9/18


isse

nsv

erar

be

itu

ng

un

d N

um

erik



Norm eines VektorsNormen sind wichtig für Fehlerabschätzungen. Man unterscheidet Vektor- und

Matrix-Normen. Norm eines Vektors

heißt Norm des Vektors , wenn es folgende Eigenschaften hat:

Solche Größen können verschieden eingeführt werden. Beispiele sind:

v v

v2 i iv

i

iv1

1

iix v1 ma

vuvu d)

va av c)

0 v fürnur 0 und 0 v b)

definiert Vektorraum imv allefür ist va)

(Betrag) Norm eeuklidischoder 2

1

9/19


isse

nsv

erar

be

itu

ng

un

d N

um

erik



Matrix-Normen

Allgemeiner heißt man Norm einer Matrix jede Größe, für die gilt

und die Eigenschaften a bis c der Vektor-Norm erfüllt.

Matrix- und Vektor-Norm sind konsistent , wenn

Es gilt: Zu jeder Norm existiert eine konsistente Matrix-Norm und umgekehrt (ohne Beweis).

Beispiel 1:

Beispiel 2: Zeilennorm =

Maximalwert der Summe der Beträge aller Elemente einer Zeile

Die Existenz der Normen ist wichtig für Abschätzungen. Sie müssen nur selten explizit berechnet werden. Die folgenden Kenngrößen lassen sich aus Anwendungen des Normbegriffes ableiten.

A BABA

AxxA

x von Norm2

1

zur konsistenzist ,

,max

02

xx

AxAx

xA

9/20


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

9/21


isse

nsv

erar

be

itu

ng

un

d N

um

erik



Spektralradius

Den Betrag des größten Eigenwertes nennt man Spektralradius.

(A) der Matrix . (A) = max

In der komplexen Ebene liegen alle Eigenwerte innerhalb eines Kreises mit (A) als Radius. Zwischen der Norm und dem Spektralradius besteht folgende Beziehung

A i

tt A

AA

x

x

nn

n

max)(und

xA x oder

x A xA

Normen ekonsistentfür gilt Ferner

x xAgilt

xA Wegen

zeigen leicht dassich läßt 1 t Für

nn

n

Diese Beziehung ist für Fehlerabschätzungen wichtig. Als Spektralnorm bezeichnet man die Wurzel des Spektralradius der Matrix AxA

9/22


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 Geben Sie die Bedeutung der Kennzahl Kondition an

Documents

Universität Stuttgart Wissensverarbeitung und Numerik I nstitut für K ernenergetik und E nergiesysteme Numerische Methoden, SS 2003Teil V: Kp. 99/1 Was