- 25 -

2 Finite Differenzen Methode (FDM) Lösungsgebiet wird mit einem (i.a. rechtwinkligen) Gitternetz überzogen Potentialverteilung wird durch eine Taylor–Reihe approximiert:

m

mm

xxfm

dxfdxf )()(

!)()( )(

2.1 Herleitung von Differenzenformeln

Feldproblem wird lokal überführt in eine Differenzengleichung

d

xfdxf

x

fd

)()(lim

0

Vorwärts– Differenz

hx x23

0

Rückwärts – Differenz

)()()(

xd

dxfxf

x

f

hx x12

0

Zentrale Differenz

)(2

)()(x

d

dxfdxf

x

f

hx x 213

0

)()()(

xd

xfdxf

x

f

- 26 -

Genauigkeitsvergleich Taylorreihenentwicklung liefert

...6

1

2

1:)( 32 xxxxhx hhhhx

...6

1

2

1:)( 32 xxxxhx hhhhx

1. Ableitung ergibt sich mittels Vorwärtsdifferenz

)(...6

1

2

1 3 hOh

hhh

xhxxx

xhxx

und mittels zentraler Differenz

)(2

...6

1

222 hO

hh

hhxhx

xhxhx

x

Für die 1. Ableitung an den Stellen 2

hx und

2

hx folgt

hxhx

hx

2

h

hxxh

x

2

und damit für die 2. Ableitung an der Stelle x

222 2

hhhxhx

hx

hx

x

2.1.1 Taylorreihenansatz Fünf – Punkte – Differenzenstern

Poisson – Gleichung:

2D, kartesisch:

),(

),(2

2

2

2 yxyxf

yx (1)

1. Schritt: Diskretisierung Differenzenstern

- 27 -

2. Schritt: Taylorentwicklung für das Potential an der Stelle P0(x0,y0)

n

n

Ryxy

kx

hn

yxy

kx

h

yxy

kx

h

),(!

1

...),(!3

1

),(!2

1

00

00

3

00

2

3. Schritt: Anwendung der Taylorentwicklung auf den Differenzenstern

...62

3

1

2

1101 xxxxxx

hhh (2)

...62

3

2

2

2202 xxxxxx

hhh (3)

...62

3

3

2

3303 yyyyyy

hhh (4)

...62

3

4

2

4404 yyyyyy

hhh (5)

4. Schritt: Ermittlung der Differenzenformel

4321

00

4

4

3

3

432

2

1

1

210 11

),(2

111

hhhh

yxfhhhhhhhh

(6)

Sonderfall: h1 + h2 + h3 + h4 = h (quadratisches Gitter)

),(4

)(4

100

2

43210 yxfh

(7)

und für die Laplacegleichung

)(4

143210 (8)

),(!1

1),(),( 000000 yx

yk

xhyxkyhx

- 28 -

Neun – Punkte - Differenzenstern Taylorentwicklung bis Term 4.Ordnung

...2462

41

31

21

101 xxxxxxxxxx

hhhh

...2462

42

32

22

202 xxxxxxxxxx

hhhh

Zusammenfassung der Ableitungen entsprechend der Schwarz´schen Regel, angewendet auf die Laplacegleichung:

yyxxxxyyyxxyyyxx , :

yyyxxxyxyyxyxxxy

yyyyxxyyyyxxxxxx

,

,

...2462

43

33

23

303 yyyyyyyyyy

hhhh

...2462

44

34

24

404 yyyyyyyyyy

hhhh

...46424

1

336

1

22

1

43

331

23

213

31

41

33

2313

21

31

2331

213105

yyyyxyyyxxyyxxxyxxxx

yyyxyyxxyxxx

yyxyxxyx

hhhhhhhh

hhhhhh

hhhhhh

...46424

1

336

1

22

1

4

4

3

42

2

4

2

24

3

2

4

2

3

4

2

424

2

2

3

2

2

442

2

24206

yyyyxyyyxxyyxxxyxxxx

yyyxyyxxyxxx

yyxyxxyx

hhhhhhhh

hhhhhh

hhhhhh

...

...

4108

3207

yx

yx

hh

hh

- 29 -

Daraus folgt ein Gleichungssystem für die acht Unbekannten:

ii

iii

i

T

xxxxyyyxxxxxxyyx

cdDx

x

8

1

8

1

1

10

1

0 ),,,,,,,(

Analytisch auflösbare Spezialfälle des 9–Punkte-Differenzensterns:

a) reguläres Rechteckgitter : h1= h2= h, h3= h4= k

8765

43

22

21

22

220

20

1

55)(10

1

khhkkh

b) äquidistantes Gitter: h1= h2= h3= h4= k

876543210 20

1

5

1

Diskretisierungsfehler:

5 – Punkte – Stern: O(h2) 9 – Punkte – Stern: O(h6)

- 30 -

Differenzenformeln für Zylindersymmetrie

Rotationssymmetrie: 02

2

Poisson – Gleichung:

),(1

2

2

2

2

zrfzrrr

...2

21

101 zzz

hh

...2

22

202 zzz

hh

...2

23

303 rrr

hh

...2

24

404 rrr

hh

Elimination der 1. Ableitung r und z, Ausdrücken der 2. Ableitung rr und zz durch die Knotenpotentiale und Auflösung nach 0 liefert die 5 – Punkte – Differenzenformel:

43

342

21

2

),(2

43

4

43

23

34

243

1

2

2

1

1

21

2

0

hh

hhr

hh

r

zrfhh

hhr

hhr

hhhhhh

r

Für ein reguläres Rechteckgitter (h1= h2= h, h3= h4= k) ergibt sich:

22

43432212

0 114

1

2

1

2

1

kh

krkh

und für ein quadratisches Gitter (h = k):

4343210 84

1 r

h

Achsennahe Differenzenformeln o.g. Formeln gelten nicht in der Nähe der Rotationsachse! Punkte 1 bis 3 vorgegeben: Punkte 3, 5, 8 vorgegeben:

3210 46

1 8530 24

1

Differenzenformel für einen unsymmetrischen Stern:

2

321

32

32

2

1

1

210 21

21

hhh

hhhhh

- 31 -

Differenzenformel in Polarkoordinaten

Polarkoordinaten: 02

2

z

Laplace – Gleichung: Vereinfachung: h1= h2= h ( ) h3= h4= k ( r ) 5 – Punkte – Differenzenstern:

22

2

43432212

0 1422

1

hk

rk

r

k

r

h

Approximation von Rändern und Grenzen Randnahe Gitterpunkte: Unregelmäßiger 5 – Punkte – Stern

mit: 4321 , hqqhqq ba

3412 hqqhqq ba ,

Unregelmäßiger 9 – Punkte – Stern:

Berechnung der Koeffizienten ci erfordert einen erheblichen Aufwand

numerische Berechnung

011

2

2

22

2

rrrr

ii

iq

4

10

214231

43

hhhhhh

hhqa

434231

21

hhhhhh

hhqb

ii

ic

8

10

...2

hh

2

01

...2

kk rr

2

r303

...2

kk rr

2

r04

2

021

h

2

k2

43r

2

2 0 ...2

hh

2

043rr

k

2

- 32 -

Besondere Berandungen ( Symmetrien ) Symmetrien = Linien mit verschwindender Normalkomponente der elektrischen Feldstärke 5 – Punkte – Stern:

43

3210 2

4

1

9 – Punkte – Stern:

768543 ,,

)(10

12

5

1753210

2 Symmetrielinien: Kombination von Symmetrielinie und Randkurve Differenzenformel eines vollständigen, unregelmäßigen 9-Punkte-Differenzensterns:

768543 ,, cccccc

ii

iii

i cc

7,5,32,1

0 2

5310 5

1

5

2

- 33 -

Grenzflächen im Feldgebiet Laplace – Gleichung: - quadratisches Gitter

- kartesische Koordinaten

02

2

2

2

yx

Einbeziehung der Grenzbedingungen:

1 2 1 2

21 21 2 1

1 2

t t x x n n y yE E E E

Die 2. Ableitungen müssen in beiden Bereichen die Laplace–Gleichungen erfüllen, die Grenzknotenpotentiale ergeben sich aus der Taylorentwicklung, sowohl im Bereich 1 als auch im Bereich 2. Folglich gilt:

Daraus folgt ein System von neun Gleichungen, das nach Auflösung nach dem Potential 0 die Differenzenformel für einen Grenzknoten liefert:

4

1

23

21

1210

2

4

1

Diagonalformel: (

85... bekannt)

86

1

275

21

10 )(2

2

2

201 2 xxx

hh

2

1 0 1 1

2

2 0 2 2

2

3 0 1 1

2

4 0 2 2

2

2

2

2

x xx

x xx

y yy

y yy

hh

hh

hh

hh

- 34 -

Erfassung der Randbedingungen

Beispiel: 5 – Punkte – Stern für die Laplace – Gleichung:

04 04321

a) Dirichlet–Bedingungen: hier: ,)( 313 gsg s1 = Knoten 3 auf dem Rand S

30421 4 g

b) Neumann – Bedingung:

hier: 0120

12 22

phph

px

00431 242 hp

c) Cauchy – Bedingung: )()()( sqssn s

hier: 2 000

12 qh

20001 2)( hq

000432 22

142 hqh

)(spn s

)()( sgs

- 35 -

3D – Approximationen Differenzengleichung: (äquidistantes Gitter)

6

10 6

1i

i

Beispiel: Poisson–Gleichung für inhomogene, statische Magnetfelder

2 ,m m

µS div

µ

M

Finite – Differenzen – Operatoren: ( = 0 gesetzt, Gleichung mit h multipliziert)

0)()(

)( S

ST

Es gilt:

3 4 5 61 2

0 0 0

3 4 5 61 2

1 2 3 4 5 6

( )( )

2 2 2

2 2 2

( ) ( ) ( )

SS

x y z

x y z

e e e

e e e

mit:

0

65

0

43

0

21

2,

2,

2

6

106)(

iiT

06)1()1()1()1()1()1( 0654321

3D – Differenzenstern auf einer Grenzfläche Punkt 0 auf der Grenzfläche 0,

singulär Berücksichtigung der

Grenzbedingungen

)()( 202011

neuer Operator:

- 36 -

2.1.2 Umlaufintegralmethode Diskretisierung und Differenzenapproximation Diskretisierung: - regelmäßiges Gitternetz (rechtwinklig)

- in der Masche konstant, gleich Wert im Maschenmittelpunkt - J = konst. je Masche - Integrationsweg: Seitenhalbierende zu Seitenhalbierende

1?rot

A dl

2

1 1b

a

Arot dx

y

x xAdl e e

2

xx

yy

AA1 20

03

03

2

2

1 1c

b

Arot dy

x y yA dl e e

2

yy

xx

AA1 30

20

20

2

: : usw.

2 2 3 3 4 4 5 5 6 6J S J S J S J S J S J dS

2

xx

2

yyJ 2003

2

A0 = A0 (A1, A2, A3, A4, (A), J, Geometrie) Differenzenformel großes, schwach besetztes, (nichtlineares) Gleichungssystem weitere Lösung wie bei FDM !

12

3

4

- 37 -

2.2 Aufstellung und Lösung der Gleichungssysteme Knotennummerierung und Indizierung Standardindizierung: parallel zu Koordinatenachsen mit m indizierten Knoten je Reihe verschiedene Bandbreiten BW

BW = 2m + 1

a) Zeilen mit m = 4 BW = 9

b) Spalten mit m = 3 BW = 7

Ermittlung der Bandbreite BW = s + 1 + r In einer Zeile gilt: r = j – i, r – Superdiagonale s - Subdiagonale s = i – j, i – Zeilenindex j – Spaltenindex Einfachindizierung P(i, j) P(k): k = i + (j – 1) I I – Zahl der inneren Knoten je Zeile

Abb.: 2D–Differenzenstern im einfach indizierten Gitter

- 38 -

3D – Gitter Pi, j, k: y – Richtung: mj 1

x – Richtung: ni 1 z – Richtung: lk 1

Einfachindizierung: Pq, r, s Pt mit: t = (s – 1)n m + (q – 1) m +r und nq 1 n – Anzahl y-z-Gitterebenen

mr 1 m – Anzahl x-z-Gitterebenen ls 1 l – Anzahl x-y-Gitterebenen

Diagonalindizierung: Rechteckgitter mit (I x J) – Gitterpunkten; I – Punkte in der Zeile J – Punkte in der Spalte Indizierung: - Start am linken unteren Gitterpunkt des Rechtecks

- Diagonalreihe für Diagonalreihe nummerieren a) J < I von links oben nach rechts unten

b) I < J von rechts unten nach links oben Beispiel: I = 6, J = 5 Lösung der Gleichungssysteme a) direkte Verfahren : - Gauß – Elimination

- Cholesky – Verfahren b) iterative Verfahren : - Jacoby – Verfahren

- Gauß – Seidel – Verfahren - Relaxationsverfahren - Gradientenverfahren

Relaxationsverfahren für FDM besonders geeignet,

wenn der optimale Relaxationfaktor bekannt ist! Dreieckszerlegung der Matrix: FDEA

- 39 -

Iterationsformel:

bDExMx

bxFxEDxxmm

mmmm

11)()1(

)()1(1)()1(

)(

)()1(

mit der Iterationsmatrix M :

DFDEM )1()()( 111

allgemeine Form des Iterationsverfahrens:

cxMx mm )()1( Optimaler Relaxationsfaktor Voraussetzungen an die Matrix: - symmetrisch

- positiv definit - konsistent geordnet (tridiagonal, blockweise tridiagonal)

positiv definit: symmetrische Matrix A mit reellen Koeffizienten ars, deren quadratische Form

p

ssrrs

p

r

xxaQ11

für jedes p- Tupel (x1, . . ., xp) positiv ist.

- 40 -

Relaxationsverfahren lineares Gleichungssystem:

bxA ),( rsaA T

p

T

p

bbb

xxx

),...,(

),...,(

1

1

Iterationsvorschrift:

r

p

rs

m

srs

r

s

m

srs

m

rrr bxaxaxa

1

)(1

1

)1()1(~

)1()()1( ~)1( m

r

m

r

m

r xxx

r

p

rs

m

srs

r

s

m

srs

m

rrr

m

rrr bxaxaxaxa1

)(1

1

)1()()1( )1(

= Punkt – SOR – Methode Spezialfall für = 1: Gauß – Seidel – Iteration

p

rs

m

srs

r

s

m

srsr

m

rrr xaxabxa1

)(1

1

)1()1(

Konvergenzbeschleunigung Verringerung des Spektralradius

iiM max)( µ - Eigenwert von M

Relaxationsfaktor so wählen, dass möglichst klein wird! Sind rD Diagonalmatrizen, so gilt:

2

111

2

opt

1 –

2

22

1

)1(

Vorgehensweise:

Differenzvektor: )()1()1( mmm xxd

)(

)1(

m

m

d

d

Bestimmung von 2

1

Bestimmung von opt

Konvergenz für: 0 < < 2 = 1 - Gauß – Seidel – Iteration > 1 - Überrelaxation < 1 - Unterrelaxation

betragsgrößter Eigenwert der Matrix

Beziehung zwischen 1 und Spektralradius der Iterationsmatrix

- 41 -

Gradientenverfahren lineares Gleichungssystem: bxA

A - reelle, positiv definite Matrix (m x m) x0 - Anfangsnäherung

n - Iterationsindex r - Residuum

r, x, b, p - Vektoren mit m Komponenten CG – Algorithmus (Conjugate Gradient Method)

0:n 1;: ;0: ;:1100

pbxAr

while residual > tolerance do begin

1n:n

:

:

:

:

:

:

:

1

1

1

1

nnnn

nnnn

n

nn

n

T

nn

nnnn

n

nn

n

T

nn

xx

Arr

pap

rp

rr

end

CGS – Algorithmus (Conjugate Gradient Squared) A - nicht positiv definit CG nicht anwendbar! modifizierter Algorithmus (nach SONNEVELD, siehe Marsal)

0:n 1;: ;0:: ;:11000

qqbxAr

while residual > tolerance do begin

end

1n:n

)(:

)(:

:

:

:

:

)(:

:

:

:

11

11

1

00

1

1

00

nnnnn

nnnnn

nnn

n

nn

nT

n

nn

nnnnnn

nnnn

n

nn

nT

n

quxx

quArr

vuq

vr

pAv

pqup

qru

rr

- 42 -

Bandbreitenreduzierung (Algorithmus nach Cuthill/Mckee) Umnummerierung aller Variablen (renumbering) führt zur Reduzierung der Bandbreite

und spart damit Speicherplatz! Ziel Minimierung

iiDK

mit: jiDi max jeder Zeile

d.h.

iD größter Abstand zwischen Diagonalterm der Zeile i

und jedem anderen Spaltenterm j dieser Zeile gebräuchlichstes Verfahren: Algorithmus von Cuthill/McKee

[Cuthill, E.;McKee, M. (1969):“Reducing the Bandwidth of Sparse Symmetric Matrices“,

ACM Proc. 24. Nat. Conf.; New York; vgl.: Hoole /10-9 /, S.222 – 224] Beispiel: (8 x 8) – Matrix mit 20 NNE

20019018017168

15014013007

1201100106

908705

60004

5403

322

11

87654321

Ausgangspunkt für die Umnummerierung ist die Darstellung der Verbindungen jedes Knoten zu allen anderen Nachbarknoten. Aufbau der Tabelle:

Knoten Zahl der Verbindungen

Verbindung zu neue Nummer neue Verbindung zu

1 3 2,6,8 4 5,2,3 2 4 1,3,5,8 5 4,6,7,3 3 3 2,5,7 6 5,7,8 4 2 6,8 1 2,3 5 3 2,3,7 7 5,6,8 6 3 1,4,8 2 4,1,3 7 2 3,5 8 6,7 8 4 1,2,4,6 3 1,2,4,5

- 43 -

Algorithmus: 1. Start mit dem Knoten mit den wenigsten Verbindungen.

Hier 4 (oder 7) neue Nr. 1 in Spalte 4 2. Der mit Knoten 4 verbundene Knoten 6 (oder 8) wird Nr. 2 in Spalte 4,

Knoten 8 wird Nr. 3 3. Nun erfolgt das gleiche mit dem neuen Knoten 2 (alt: 6):

von den Verbindungen 1, 4, 8 sind 4 und 8 bereits nummeriert. Folglich wird Knoten 1 die Nr. 4.

4. Fortsetzung dieser Prozedur für alle restlichen Knoten

Umkehrung dieses Algorithmus führt zu einer noch effektiveren Umnummerierung Freie Wahl bei gleichrangigen Knoten führt auf unterschiedliche Strategien mit

unterschiedlichen Speicherplatzanforderungen. Modifizierungen sind also möglich!

5. Aufstellung der letzten Spalte:

Beispiel: neuer Knoten 4 (alt:1) hat Verbindungen zu 2, 6 und 8 gemäß Spalte 3 Neue Verbindungen von Knoten 4: 5, 2, 3 Knoten 2 (in Spalte 1) 5 (in Spalte 5) 6 2 8 3

6. Neuordnung der Reihenfolge der Nummerierung 2, 3, 5 damit wird Nr. 5 über der Diagonale in die obere Dreiecksmatrix (symmetrisch) “abgeschoben“ und entfällt somit für die Abspeicherung! Es ergibt sich die folgende unsymmetrische Matrix:

201918000008

17161500007

141300006

121110005

98704

6543

322

11

87654321

Die Tabelle ist leicht zu programmieren Dadurch entstehender Zusatzaufwand kann größtenteils kompensiert werden, wenn

Verkonditionierungen angewendet werden (z.B. bei CG – Verfahren)

Einsparungen bei Speicherplatzreservierungen für die Matrix Zusammenfassung: Bevorzugte iterative Verfahren:

- Gauß–Seidel–Verfahren - Relaxationsverfahren ( insbesondere SOR ) - Newton–Verfahren ( in vielen Varianten ) - Newton–Raphson–Verfahren ( häufig bei nichtlinearen FEM–Matrizen )