13
Große Gleichungssysteme fast richtig l ¨ osen Teilnehmer: 7 Sch¨ ulerinnen und Sch¨ uler Andreas-Gymnasium Herder-Gymnasium Immanuel-Kant-Gymnasium athe-Kollwitz-Gymnasium mit tatkr¨aftiger Unterst¨ utzung durch: Anika Meyer Humboldt-Universit¨ at zu Berlin Gruppenleiter: Falk Ebert Herder-Gymnasium, Humboldt-Universit¨ at zu Berlin, Matheon 17

Groˇe Gleichungssysteme fast richtig l osendidaktik.mathematik.hu-berlin.de/user/fehlingerl/Falk.pdf · 2019. 6. 14. · Groˇe Gleichungssysteme fast richtig l osen Teilnehmer:

  • Upload
    others

  • View
    0

  • Download
    0

Embed Size (px)

Citation preview

Page 1: Groˇe Gleichungssysteme fast richtig l osendidaktik.mathematik.hu-berlin.de/user/fehlingerl/Falk.pdf · 2019. 6. 14. · Groˇe Gleichungssysteme fast richtig l osen Teilnehmer:

Große Gleichungssysteme fast richtig losen

Teilnehmer:

7 Schulerinnen und Schuler Andreas-GymnasiumHerder-GymnasiumImmanuel-Kant-GymnasiumKathe-Kollwitz-Gymnasium

mit tatkraftiger Unterstutzung durch:Anika Meyer Humboldt-Universitat zu Berlin

Gruppenleiter:Falk Ebert Herder-Gymnasium, Humboldt-Universitat zu Berlin, Matheon

17

Page 2: Groˇe Gleichungssysteme fast richtig l osendidaktik.mathematik.hu-berlin.de/user/fehlingerl/Falk.pdf · 2019. 6. 14. · Groˇe Gleichungssysteme fast richtig l osen Teilnehmer:

1. Einleitung

Viele Modellierungsaufgaben, wie zum Beispiel das Beschreiben einer Temperaturverteilung in einemEisenstab, lassen sich letztendlich auf lineare Gleichungssysteme (LGS) zuruckfuhren.Je nach Problem ergeben sich hier schnell LGS mit tausenden oder mehr Variablen. Gleichungssystemedieser Große bringen schnell Probleme in der Auswertung mit sich. Vor allem die exakte Auswertung istoft rechenaufwandig.Um den Rechenaufwand erheblich zu minimieren und einige Probleme erst losbar zu machen, bietet essich an, die LGS numerisch zu losen.Im Rahmen unserer Projektarbeit haben wir uns mit solchen numerischen Verfahren zum Losen großerLGS beschaftigt und schließlich das oben beschriebene Beispiel in Octave simuliert.

2. Warmeleitung

Abb.1: Metallbalken

Es wird ein Metallbalken betrachtet, dessen Tem-peratur an beiden Seiten konstant gehalten wird.Ziel ist es, die Temperatur T (x) an jedem Ort xim Metallbalken in Abhangigkeit der Randbedin-gungen bestimmen zu konnen.

Dazu diskretisiert man das Phanomen. D.h.anstatt unendlich viele Werte bestimmen zumussen, reduziert man die Anzahl der zu bestim-menden Werte, indem der Metallstab in aquidi-stante Intervalle aufgeteilt wird. Die Temperaturmuss also nur fur alle Ti bestimmt werden. DieRandbedingungen T0 und Tn sind gegeben.

Abb.2: Diskretisierung des Metallbalkens

Die Warmeleitungsgleichung liefert nun folgende Differentialgleichung fur T mit den RandbedingungenT (0) = T0 und T (1) = T1. Der Balken wird hier mit der Lange 1 LE angenommen.

T ′′(x) = 0

Um diese Gleichung als LGS zu schreiben, wird der Term T ′′(x) diskretisiert.

Satz 1. Fur eine genugend glatte Funktion f : R→ R gilt:

f ′′(x) =f(x− h)− 2f(x) + f(x+ h)

h2+O(h2).

Beweis:Der Beweis erfolgt durch die Taylorentwicklung der Funktionen f(x+ h) und f(x− h) am Entwicklungs-punkt x.

f(x+ h) =

∞∑k=0

f (n)(x)

k!(x+ h− x)k =

∞∑k=0

fn(x)

k!hk

= f(x) + f ′(x) · h+f ′′(x)

2!· h2 +

f ′′′(x)

3!· h3 +

f (4)(x)

4!· h4 + ...

f(x− h) =

∞∑k=0

f (n)(x)

k!(x− h− x)k =

∞∑k=0

fn(x)

k!(−h)k

= f(x)− f ′(x) · h+f ′′(x)

2!· h2 − f ′′′(x)

3!· h3 +

f (4)(x)

4!· h4 − ...

18

Page 3: Groˇe Gleichungssysteme fast richtig l osendidaktik.mathematik.hu-berlin.de/user/fehlingerl/Falk.pdf · 2019. 6. 14. · Groˇe Gleichungssysteme fast richtig l osen Teilnehmer:

Es ergibt sich mit den Taylorentwicklungen:

f(x+ h) + f(x− h)− 2f(x)

h2=

2f(x) + 2 f′′(x)2! · h

2 + 2 f(4)(x)4! · h4 + ...− 2f(x)

h2= f ′′(x) +

h2 · f (4)(x)

12+ ...

Fur h→ 0 streben die Taylorsummanden nach f ′′(x) gegen 0 und damit gilt fur kleine h:

f ′′(x) ≈ f(x+h)−2f(x)+f(x−h)h2 .

Da h gegen 0 strebt, lauft der Term der niedrigsten Potenz (h2) am langsamsten gegen Null. f(x+h)−2f(x)+f(x−h)h2

konvergiert also quadratisch gegen f ′′(x). Dies lasst sich auch schreiben als

f ′′(x) =f(x+ h)− 2f(x) + f(x− h)

h2+O(h2).

In Bezug auf die Intervallunterteilung lasst sich h = 1n wahlen (Der Metallbalken ist 1 LE lang). Damit

lasst sich die Warmeleitungsgleichung folgendermaßen diskretisieren:

T ′′(x) = 0

T (x+ h)− 2T (x) + T (x− h)

h2= 0 (1)

Tk+1 − 2Tk + Tk−1

h2= 0.

Zusammen mit gegebenen Randbedingungen T (0) = T0, T (1) = Tn stellt (1) ein lineares Gleichungssys-tem mit den n− 1 Unbekannten T1 bis Tn−1 dar.

3. Numerische Verfahren zum Losen von LGS

3.1. Gauß-Verfahren

Beim Gauß-Verfahren wird ein lineares Gleichungssystem mit n Gleichungen und n Variablen der Form

a11 · x1 + . . . + a1n · xn = b1...

......

an1 · x1 + . . . + ann · xn = bn

(2)

durch Skalierung und Addition von Zeilen in Dreiecksform

a11 · x1 + a12 · x2 + . . . + a1n · xn = b10 + a22 · x2 + . . . + a2n · xn = b2...

......

0 + . . . + 0 + ann · xn = bn

gebracht. Dies erfordert in etwa in der Großenordnung von n3 Rechenoperationen. Gerade fur sehr großeGleichungssysteme ist das sehr aufwandig.

3.2. Jacobi-Verfahren

Lost man jeweils die i-te Gleichung eines linearen Gleichungssystems (2) nach xi auf, ergibt dies

x1 = 1a11

(b1 − a12x2 − a13x3 − . . .− a1nxn)

x2 = 1a22

(b2 − a21x1 − a23x3 − . . .− a2nxn)

... =...

xn = 1ann

(bn − an1x1 − an2x2 − . . .− an−1xn−1).

19

Page 4: Groˇe Gleichungssysteme fast richtig l osendidaktik.mathematik.hu-berlin.de/user/fehlingerl/Falk.pdf · 2019. 6. 14. · Groˇe Gleichungssysteme fast richtig l osen Teilnehmer:

Ausgehend von Startwerten x[0]1 , . . . , x

[0]n konnen daraus mit dem folgenden Iterationsschritt neue Werte

x[k+1]i aus den x

[k]i bestimmt werden.

x[k+1]1 = 1

a11(b1 − a12x[k]2 − a13x

[k]3 − . . .− a1nx

[k]n )

x[k+1]2 = 1

a22(b2 − a21x[k]1 − a23x

[k]3 − . . .− a2nx

[k]n )

... =...

x[k+1]n = 1

ann(bn − an1x[k]1 − an2x

[k]2 − . . .− an−1x

[k]n−1)

(3)

Unter geeigneten Bedingungen, die wir im weiteren untersuchen werden, sind diese x[k]i zunehmend bessere

Naherungen fur die Losungen xi von (2). Dieses Iterationsverfahren lasst sich folgendermaßen in eineMatrix-Vektor-Schreibweise uberfuhren:

a11 · x[k+1]1 + . . . + a1n · x[k]n = b1

......

...

an1 · x[k]1 + . . . + ann · x[k+1]n = bn

⇐⇒

a11 0

. . .

0 ann

︸ ︷︷ ︸

D

·

x1

...

xn

[k+1]

︸ ︷︷ ︸x[k+1]

+

0 a12 . . . a1n

a21. . .

. . ....

.... . .

. . . an−1,n

an1 . . . an,n−1 0

︸ ︷︷ ︸

A−D

·

x1

...

xn

[k]

︸ ︷︷ ︸x[k]

=

b1

...

bn

︸ ︷︷ ︸b

Die Koeffizientenmatrix A des LGS lasst sich dabei in eine Diagonalmatrix D und eine Matrix (A−D)zerlegen, sodass sich mit weiteren Aquivalenzumformungen folgende Kurzschreibweise fur das Jacobi-Verfahren ergibt:

Dx[k+1] + (A−D)x[k] = b

D−1 · | Dx[k+1] = b− (A−D)x[k]

x[k+1] = D−1(b− (A−D)x[k])

x[k+1] = D−1b︸ ︷︷ ︸cJ

+ (−D−1(A−D))︸ ︷︷ ︸MJ

x[k]

= MJx[k] + cJ .

Dabei gehen wir stillschweigend davon aus, dass aii 6= 0 fur alle i und D damit invertierbar ist.

3.3. Gauß-Seidel-Verfahren

Geht man wie beim Jacobi-Verfahren (3) vor und berechnet die neuen Iterierten x[k+1]i der Reihe nach

fur i = 1, 2, . . . , n, dann kann man ab i = 2 bereits auf die Iterierten x[k+1]j fur j < i zuruckgreifen.

Damit ist zu erwarten, dass die Verbesserung der Naherungslosung beschleunigt wird. Allerdings isteine Parallelisierung, d.h. die verteilte Berechnung auf mehreren Rechnern, im Gegensatz zum Jacobi-

20

Page 5: Groˇe Gleichungssysteme fast richtig l osendidaktik.mathematik.hu-berlin.de/user/fehlingerl/Falk.pdf · 2019. 6. 14. · Groˇe Gleichungssysteme fast richtig l osen Teilnehmer:

Verfahren ausgeschlossen. Fur das Gauß-Seidel-Verfahren ergibt sich also:

x[k+1]1 = 1

a11(b1 − a12x[k]2 − a13x

[k]3 − . . .− a1nx

[k]n ),

x[k+1]2 = 1

a22(b2 − a21x[k+1]

1 − a23x[k]3 − . . .− a2nx[k]n ),

... =...

x[k+1]n = 1

ann(bn − an1x[k+1]

1 − an2x[k+1]2 − . . .− an−1x[k+1]

n−1 ).

(4)

In Matrix-Vektor-Schreibweise ergibt sich danna11 0 . . . 0

a21 a22. . .

......

. . .. . . 0

an1 . . . ann−1 ann

︸ ︷︷ ︸

L+D

·

x1......xn

[k+1]

︸ ︷︷ ︸x[k+1]

+

0 a12 . . . a1n...

. . .. . .

......

. . . an−1n0 . . . . . . 0

︸ ︷︷ ︸

R

·

x1......xn

[k]

︸ ︷︷ ︸x[k]

=

b1......bn

︸ ︷︷ ︸b

.

Als Kurzschreibweise ergibt sich aus (L+D) · x[k+1] +R · x[k] = b durch aquivalentes Umformen:

x[k+1] = −(L+D)−1 ·R︸ ︷︷ ︸MGS

·x[k] + (L+D)−1 · b︸ ︷︷ ︸bGS

= MGS · x[k] + bGS .

Beispiel 1. Exaktes und numerisches Losen eines LGS

3x1 + x1 + x1 = 53x1 + 3x2 + x3 = 73x1 + 3x2 + 3x3 = 9

Exakte Losung nach Gauß:x1 = 1, x2 = 1, x3 = 1

Jacobi-Verfahren:

Iterationsschritt 0 1 2 3x1 0 1, 67 −0, 11 2, 11x2 0 2, 33 −0, 33 2, 78x3 0 3 −1 4, 11

Gauß-Seidel:

Iterationsschritt 0 1 2 3x1 0 1, 67 1, 22 1, 07x2 0 0, 67 0, 89 0, 96x3 0 0, 67 0, 89 0, 96

Es ist zu erkennen, dass das Jacobi-Verfahren fur diese Verfahrensmatrix nicht konvergiert, das Gauß-Seidel-Verfahren jedoch schon.

4. Konvergenz der numerischen Losungsverfahren

Bei den rekursiven Vorschriften der Jacobi- und Gauß-Seidel-Verfahren handelt es sich um Fixpunktite-rationen.

Definition 1 (Fixpunktiteration). Sei ϕ : G→ G eine Abbildung. Ein x∗ mit ϕ(x∗) = x∗ heißt Fixpunktder Abbildung. Die rekursive Vorschrift

xn+1 = ϕ(xn)

mit gegebenem x0 heißt Fixpunktiteration.

Uberlegung. Das Jacobi- und Gauß-Seidel-Verfahren lassen sich schreiben als

x[k+1] = MJ · x[k] + CJ = ϕ(x[k])

bzw. x[k+1] = MGS · x[k] + CGS = ϕ(x[k]).

21

Page 6: Groˇe Gleichungssysteme fast richtig l osendidaktik.mathematik.hu-berlin.de/user/fehlingerl/Falk.pdf · 2019. 6. 14. · Groˇe Gleichungssysteme fast richtig l osen Teilnehmer:

Die Bedingungen fur die Konvergenz einer solchen Fixpunktiteration ergeben sich aus dem Fixpunktsatzvon Banach. Vorab muss dazu die Kontraktion definiert werden.

Definition 2 (Kontraktion). Sei ϕ : I→ I eine Funktion. ϕ ist eine Kontraktion auf I wenn gilt:

a) ϕ(I) ⊆ I (Selbstabbildung)

b) |ϕ(x)− ϕ(y)| ≤ L · |x− y| ∀x, y ∈ I mit L < 1

Damit gilt fur die Konvergenz von Fixpunktiterationen der Fixpunktsatz von Banach.

Satz 2 (Fixpunktsatz von Banach).Sei ϕ : I→ I eine Kontraktion auf I. Dann existiert genau ein Fixpunkt x∗ ∈ I und die Fixpunktiterationxn+1 = ϕ(x) mit beliebigem Startwert x0 ∈ I liefert eine gegen x∗ konvergierende Folge (xn).

Da der Fixpunktsatz von Betragen, also Abstanden ausgeht und diese nicht ohne weiteres auf Vektorenund Matrizen angewendet werden konnen, muss der Abstandsbegriff fur Vektoren und Matrizen geklartwerden.

4.1. Normen

Definition 3. Norm eines Vektors || · || : Rn → R+ ∪ {0}

a) ||x|| ≥ 0 ∀x ∈ Rn, ||x|| = 0⇔ x = 0 ∈ Rn

b) ||αx|| = |α| ||x|| ∀x ∈ Rn, α ∈ R

c) ||x+ y|| ≤ ||x||+ ||y||

Eine Abbildung, die diese Bedingungen erfullt, heißt Norm eines Vektors.

Im Folgenden werden einige gangige Beispiele fur Vektornormen angefuhrt.

Beispiel 2. Normen von Vektoren

1.) ||x||1 =∑nk=1 |xk|

2.) ||x||2 =

√n∑k=1

|xk|2 (Euklidische Norm)

3.) ||x||∞ = limp→∞p√∑n

k=0 |xk|p = maxk=1,...,n |xk|

Prinzipiell ware eine Eigenschaft wie die absolute Homogenitat (Def. 3b) auch fur Matrix-Vektor-Produktewunschenswert.

||A · x|| = ||A|| · ||x||Es lasst sich aber leicht sehen, dass diese Gleichung im Allgemeinen fur kein ‖A‖ erfullbar ist. Wirschwachen die Forderung ab und suchen nur nach einer reellen Zahl, die die Submultiplikativitat erfullt:

||A · x|| ≤ ||A|| · ||x||||x||6=0⇔ ||A|| ≥ ||A · x||

||x||∀x ∈ Rn, x 6= 0.

Diese Zahl wird nicht eindeutig sein. Entsprechend wahlen wir das kleinstmogliche ||A||.

22

Page 7: Groˇe Gleichungssysteme fast richtig l osendidaktik.mathematik.hu-berlin.de/user/fehlingerl/Falk.pdf · 2019. 6. 14. · Groˇe Gleichungssysteme fast richtig l osen Teilnehmer:

Definition 4. (Matrixnorm)Die von einer Vektornorm induzierte Matrixnorm ist wiefolgt definiert:

||A|| := supx 6=0

||A · x||‖x‖

= sup||x||=1

||A · x||.

Insbesondere ergibt sich aus der ∞-Norm eines Vektors die ∞-Norm einer Matrix, bzw. die sogenannteZeilensummennorm.

Definition 5. (Zeilensummennorm fur A ∈ Rm,n)

||A||∞ = maxi=1...m

n∑j=1

|aij | ⇒ ||A · x||∞ ≤ ||A||∞ · ||x||∞

Die definierten Normen erlauben eine Anwendung des Fixpunktsatzes auf ϕ : Rn → Rn.

Satz 3. (Konvergenz des Jacobi-Verfahrens)Die Iteration

x[k+1] = −D−1(A−D)x[k] +D−1b

konvergiert fur beliebige x[0], b ∈ Rn, wenn A strikt diagonaldominant ist, d.h. |aii| >∑nj=1,j 6=i |aij |

(Diagonale ist großer als Summe des Betrags der restlichen Zeile).

Beweis: Um den Fixpunktsatz von Banach anwenden zu konnen, muss ϕ eine Kontraktion sein. Daϕ : Rn → Rn, ist ϕ eine Selbstabbildung.Betrachte

‖ϕ(x)− ϕ(y)‖∞ = ‖MJ · x+ cJ −MJ · y − cJ‖∞ = ‖MJ · (x− y)‖∞ ≤ ‖MJ‖∞ · ‖x− y‖∞,

mit

||MJ ||∞ = ||D−1(A−D)||∞ =

∥∥∥∥∥∥∥∥∥

a−111 · ( 0 a12 a13 . . . a1n )a−122 · ( a21 0 a23 . . . a2n )

... · (...

......

...... )

a−1nn · ( an1 an2 . . . ann−1 0 )

∥∥∥∥∥∥∥∥∥∞

=

∥∥∥∥∥∥∥∥∥

0 a12

a11a13a11

. . . a1na11

a21a22

0 a23a22

. . . a22a22

......

......

...an1

annan2

ann. . . ann−1

ann0

∥∥∥∥∥∥∥∥∥∞

= maxi=1...n

n∑j=1,i6=j

|aij ||aii|

!< 1

⇒n∑

j=1,i6=j

|aij ||aii|

< 1 ∀i = 1...n

⇔n∑

j=1,i6=j

|aij | < |aii| ∀i = 1...n (strikte Diagonaldominanz)

Damit konvergiert ϕ, wenn A strikt diagonaldominant ist. �

Bemerkung 1. Die gleiche Bedingung gilt fur das Gauß-Seidel-Verfahren. (ohne Beweis)

23

Page 8: Groˇe Gleichungssysteme fast richtig l osendidaktik.mathematik.hu-berlin.de/user/fehlingerl/Falk.pdf · 2019. 6. 14. · Groˇe Gleichungssysteme fast richtig l osen Teilnehmer:

5. Optimierungen der numerischen Losungsverfahren (Jacobi)

5.1. Fehlerabschatzung

Betrachtet man die Abweichung der ermittelten Naherungslosung von der exakten Losung x∗ = A−1b desLGS Ax = b, so lasst sich diese folgendermaßen abschatzen:

||x[k] − x∗||∞ = ||x[k] −A−1b||∞= ||A−1(Ax[k] − b)||∞ ≤ ||A−1||∞ · ||Ax[k] − b︸ ︷︷ ︸

r[k]

||∞.

Das sogenannte Residuum r[k] = Ax[k] − b liefert ein Maß fur den Fehler, denn fur r[k] = 0 ist auchx[k] − x∗ = 0. Mithilfe des Residuums lasst sich die Iterationsvorschrift des Jacobi-Verfahrens auchfolgendermaßen schreiben:

x[k+1] = MJx[k] + CJ

= x[k] −D−1(Ax[k] − b)= x[k] −D−1r[k].

Damit ergibt sich der neue Jacobi-Schritt x[k+1] als Summe des alten Schritts x[k] und einer Korrektur−D−1r[k]. Diese Korrektur wird umso kleiner, je naher x[k] an x∗ kommt.

5.2. Relaxiertes Jacobi-Verfahren

Uberlegung. Die Korrektur der Naherungslosung kann in jedem erneuten Iterationsschritt durch denParameter α skaliert werden.

x[k+1] = x[k] − αD−1r[k] α ∈]0, 2[

Fur α > 1 spricht man von einer Uberrelaxation, fur α < 1 von einer Unterrelaxation. Mittels Ab-schwachung des Werts der Korrektur (α < 1) kann ein Oszillieren um die Losung x∗ vermindert werden.Im konkreten Fall unseres Modellproblems konnen hochfrequente Schwingungen gefiltert werden, wodurcheine schnellere Konvergenz erreicht werden kann.

Uberlegung. Im konkreten Fall sogenannter Laplace- oder Poisson-Gleichungen wie z.B. im Einfuhrungs-beispiel (1) erhalt man als Systemmatrix des LGS

A =1

h2·

−2 1

1. . .

. . .

. . .. . . 11 −2

. (5)

Das Jacobi-Verfahren fur diese Probleme hat die Form:

x[k+1] = x[k] −D−1r[k]

= x[k] +h2

2r[k].

24

Page 9: Groˇe Gleichungssysteme fast richtig l osendidaktik.mathematik.hu-berlin.de/user/fehlingerl/Falk.pdf · 2019. 6. 14. · Groˇe Gleichungssysteme fast richtig l osen Teilnehmer:

Dies kann wie folgt umgeformt werden.

Ax[k+1] = Ax[k] +h2

1Ar[k],

Ax[k+1] − b = Ax[k] − b+h2

2Ar[k],

r[k+1] = r[k] +h2

2Ar[k].

Genaueres Betrachten von h2

2 A · r[k] liefert

h2

2A =

h2

2

1

h2·

−2 1

1. . .

. . .

. . .. . . 11 −2

=

−1 1

2

12

. . .. . .

. . .. . . 112 −1

.

Bei Simulationen lasst sich beobachten, dass manche Formen des Residuums bei einem Jacobi-Schritt nurum einen sehr geringen Faktor kleiner werden. Dies soll hier genauer untersucht werden.

Uberlegung. (Ansatz: Sinus als Residuum) Wir betrachten das Residum r als eine Uberlagerung ein-zelner Sinusschwingungen

r0 = 0, rn = 0, ri = sin(xi · π · ω) = sin(i

n· π · ω).

Die Bedingung r0 = rn = 0 ist dadurch gerechtfertigt, dass die Randwerte T = 0 und Tn vorgegebensind, an diesen Stellen also keine Abweichung von der exakten Losung auftritt und das Residuum damit0 ist.

Eine Zeile von A · r lautet1

2ri−1 − ri +

1

2ri+1.

Einsetzen von ri fuhrt auf:

sin

(i

n· π · ω

)·(

cos(πn· ω)− 1)

= sin (ri) ·(

cos(πn· ω)− 1)

︸ ︷︷ ︸λ

.

Es ergibt sich

r[k+1] = r[k] +h2

2A · r[k]

= r[k] + cos((π

n· ω)− 1)· r[k]

= cos(πn· ω)

︸ ︷︷ ︸λ

r[k].

Daraus sind mehrere Effekte erkennbar. Zuerst ist |λ| < 1 fur alle ω = 1, . . . , n − 1. Damit konvergiertdas Jacobi-Verfahren auch fur Matrizen der Form (5), auch wenn diese nicht strikt diagonaldominantsind. Zum anderen ist |λ| ≈ 1 fur sehr kleine und sehr große ω. Ein Residuum, welches also entweder sehrwenig oder sehr stark schwingt, wird durch das Verfahren fast gar nicht gedampft. Residuen die einer

25

Page 10: Groˇe Gleichungssysteme fast richtig l osendidaktik.mathematik.hu-berlin.de/user/fehlingerl/Falk.pdf · 2019. 6. 14. · Groˇe Gleichungssysteme fast richtig l osen Teilnehmer:

Schwingung mit ω ≈ n2 entsprechen werden hingegen innerhalb eines Schrittes gedampft.

Wir bringen den Relaxationsfaktor α ins Spiel und erhalten

r[k+1] = r[k] + αh2

2A · r[k]

=(

1 + α(

cos(π

nw)− 1

))r[k].

Und im konkreten Fall von α = 12 ergibt sich

r[k+1] =1 + cos(πnw)

2︸ ︷︷ ︸λ

r[k].

Damit ist auch in diesem Fall der Dampfungsfaktor aus (0, 1). Auch hier werden niederfrequente Losungs-anteile kaum gedampft. Anders als bei α = 1 werden hier die hochfrequenten Anteile sehr stark gedampft.

Das normale Jacobi-Verfahren(α = 1) dampft die sehr nie-derfrequenten und sehr hoch-frequenten Losungsanteile kaum.Ein Schritt des mit α =12 unterrelaxierten Verfahrensdampft vor allem hochfrequenteLosungsanteile. Dies wird beimMehrgitterverfahren genutzt.

5.3. Mehrgitterverfahren

Uberlegung. Der Grundgedanke des Mehrgitterverfahrens besteht darin, dass man eine sehr grob diskre-tisierte Losung als Grundlage fur eine Losung auf einem feineren Gitter nutzt. Niederfrequente Anteile desResiduums werden durch eine Vergroberung (Restriktion) des Gitters hochfrequent. In einem groberenGitter konnen die hochfrequenten Unbekannten mit weniger Schritten an eine Losung angenahert wer-den. Anschließend wird das Gitter wieder verfeinert (Prolongation). Die dadurch entstehenden Nahe-rungslosungen auf dem Feingitter sind ein guter Ausgangspunkt fur eine Nachiteration mit Jacobi. Zuerstsollte aber ein Glattungsschritt erfolgen, da die Prolongation einen sehr hochfrequenten Fehler in das Re-siduum einbringt.Schematisch ist das Ganze im Folgenden dargstellt.

26

Page 11: Groˇe Gleichungssysteme fast richtig l osendidaktik.mathematik.hu-berlin.de/user/fehlingerl/Falk.pdf · 2019. 6. 14. · Groˇe Gleichungssysteme fast richtig l osen Teilnehmer:

6. Beispielrechnug (Temperaturverteilung)

Wie in Abschnitt 2 wird ein Metallbalken betrachtet, dessen Temperatur an beiden Seiten konstant gehal-ten wird. Ziel ist es, die Temperatur an jedem Ort im Metallbalken in Abhangigkeit der Randbedingungenbestimmen zu konnen.Anstatt der Warmeleitungsgleichung wie in (1), welche Warmeabgabe an die Umgebung ignoriert, be-trachten wir einen Balken, der sich in einer Umgebung von Tu = 20◦C befindet und mit der UmgebungWarme tauschen kann.

T ′′(x)− T − Tuλ

= 0⇔ T ′′ − T

λ= −Tu

λ.

Nach Diskretisierung nimmt diese Gleichung die folgende Form an:

T ′′(x)− T (x)

λ= −Tu

λ

T (x+ h)− 2T (x) + T (x− h)

h2− T (x)

λ= −Tu

λ

Tk+1 − 2Tk + Tk−1

h2− Tk

λ= −Tu

λ.

Diese rekursive Vorschrift lasst sich dann als LGS schreiben.

1

h2T2 −

2

h2T1 −

1

λT1 = −TU

λ− T0

1

h2T3 −

2

h2T2 +

1

h2T1 −

1

λT2 = −TU

λ...

− 2

h2Tn−1 +

1

h2Tn−2 −

1

λTn−1 = −TU

λ− 1

h2Tn.

In Matrix-Vektor-Schreibweise ergibt das dann:

1

h2·

−2 1

1. . .

. . .

. . .. . . 11 −2

·T1

T2...

Tn−1

− 1

λ·

T1

T2...

Tn−1

=

−Tuλ −

1h2T0

−Tuλ...

−Tuλ −1h2Tn

⇔ 1

h2·

−2− h2

λ 1

1. . .

. . .

. . .. . . 1

1 −2− h2

λ

︸ ︷︷ ︸

AW

·

T1

T2...

Tn−1

︸ ︷︷ ︸

t

=

−Tuλ −

1h2T0

−Tuλ...

−Tuλ −1h2Tn

︸ ︷︷ ︸

bW

Auch dieses LGS konnen wir in der Form AW · t = bW mit strikt diagonaldominantem AW schreiben. Esergibt sich damit die folgende Fixpunktiteration fur das Jacobi-Verfahren

x[k+1] = ϕ(x[k]) = −D−1(AW −D)︸ ︷︷ ︸MW

x[k] +D−1b︸ ︷︷ ︸ cW .Die numerische Losung dieses Gleichungssystems bzw. die obige Iteration haben wir in Octave pro-grammiert und konnten damit die Temperaturverteilung in dem Metallbalken bestimmen. GraphischeDarstellungen der einzelnen Schritte finden sich in den Abbildungen 3 bis 10. Dabei ist das obere Bild

27

Page 12: Groˇe Gleichungssysteme fast richtig l osendidaktik.mathematik.hu-berlin.de/user/fehlingerl/Falk.pdf · 2019. 6. 14. · Groˇe Gleichungssysteme fast richtig l osen Teilnehmer:

jeweils der aktuelle Losungsverlauf mit eingeblendeter Referenzlosung. Darunter ist das zugehorige Resi-duum dargestellt. Aus Grunden der Ubersichtlichkeit wurde eine Diskretisierung mit n = 16 Intervallen,also n− 1 = 15 Unbekannten betrachtet.

Abb.3: Zufallig initialisierte Startwerte Abb.4: Erster Restriktionsschritt

Abb.5: Maximale Restriktionsstufe Abb.6: Jacobi-Verfahren

Abb.7: Erste Prolongation Abb.8: Naherung fur sieben Unbekannte

28

Page 13: Groˇe Gleichungssysteme fast richtig l osendidaktik.mathematik.hu-berlin.de/user/fehlingerl/Falk.pdf · 2019. 6. 14. · Groˇe Gleichungssysteme fast richtig l osen Teilnehmer:

Abb.9: Oszillationen nach Prolongation Abb.10: Finale Losung

Zuerst wurde maximal restringiert, bis die Anzahl der Unbekannten auf 1 reduziert worden ist (Abb. 5).Diese Gleichung wurde mit Jacobi exakt gelost (Abb. 6). Die Prolongation auf drei Unbekannte (Abb. 7)weist an den interpolierten Stellen deutliche Abweichungen auf. Diese wurden aber mit zwei relaxierten(α = 1

2 ) Jacobi Schritten weitestgehend behoben. Schrittweise wurde weiter prolongiert und jeweilszweimal nachgeglattet. In Abb. 9 ist das Resultat nach der letzten Prolongation dargestellt. Deutlichsichtbar ist auch das stark oszillierende Residuum, welches durch Glattung fast vollstandig verschwindet(Abb. 10).Es ist anzumerken, dass nur zwei Jacobi-Schritte auf dem feinsten Gitter durchgefuhrt wurden. Alleweiteren Schritte erfolgten auf groberen Gittern mit jeweils deutlich weniger Unbekannten. Damit liegtder Gesamtaufwand fur die Berechnung bei etwa 4 Jacobi-Schritten auf dem Feingitter. Diese Betrachtungist auch fur deutlich großere n noch zutreffend. Damit liegt der Aufwand fur ein vollstandig durchgefuhrtesMehrgitterverfahren in der Großenordnung einiger n2 im Gegensatz zu n3 bei Gauß.

7. Zusammenfassung

Zum Losen von großen Gleichungssystemen nutzen wir das Gauß-Seidel-Verfahren und das Jacobi-Verfahren.Beide Verfahren losen Gleichungssysteme iterativ. Das verringert den Rechenaufwand.So ist das exakte Losen eines LGS mit n Unbekannten mittels Gauß-Verfahren etwa n mal so teuer wiedas numerische Annahern durch das Jacobi Verfahren. Bei einem LGS mit 1000 Unbekannten konntenso statt einer Gauß-Losung 1000 Jacobi-Iterationen gemacht werden.Wir konnten fur das Jacobi-Verfahren ein einfach zu uberprufendes Konvergenzkriterium des Iterations-verfahrens herleiten.Weiterhin haben wir das Konzept der Mehrgitterverfahren erfolgreich auf ein realitatsnahes Beispiel an-gewandt und damit zeigen konnen, dass mit insgesamt geringem Aufwand bei geschickter Restriktion undProlongation ein relativ großes Gleichungssystem schnell gelost werden kann.

29