Jacobi-Verfahren
10x + y −
z = −2
−x + 8y +
z =
1
x − y − 20z =
3
Wir wollen uns der Lösung schrittweise nähern.
Es fällt auf, dass die Diagonalelemente dominieren.
Wir formen nach den Variablen auf der Diagonale um und erhalten:
2
1
1
x = − 10
− 10
y + 10
z
y =
1
8
+ 18 x −
1
z
8
3
1
1
z = − 20
+ 20
x − 20
y
Ein plausibler Startvektor lautet (die anderen Komponenten werden durch größere Zahlen geteilt):
− 51
x0
1
y0 =
8
3
z0
− 20
Die erste Iteration ergibt:
1
3
x1
− 15 − 80
− 200
1
1
3
y1 =
8 − 40 + 160
1
3
3
z1
− 100
+ 400
− 20
usw.
Das Verfahren konvergiert, falls für die Diagonalelemente |ai,i | >
X
|ai,k | gilt.
i6=k
Matrizenschreibweise (A wird in zwei Dreiecksmatrizen und eine Diagonalmatrix zerlegt):
~
A · ~x = (L + D + R) · x
= ~b
~ +D·x
~ +R·x
~
= L·x
= ~b
~
D · ~x = ~b − (L + R) · x
−1
~x = D · (~b − (L + R) · ~x )
iterativer Algorithmus
~ (k+1) = D−1 · (~b − (L + R) · ~x (k) )
x
Gauß-Seidel-Iteration
Das Jacobi-Verfahren (Gesamtschrittverfahren) kann so abgeändert werden (Gauß-Seidel, Einzelschrittverfahren), dass in einem Iterationsschritt die neu berechnete x-Koordinate schon gleich zur
Berechnung der y-Koordinate verwendet wird. Zur Bestimmung der z-Koordinate werden die schon
neu ermittelte x- und die y-Koordinate herangezogen.
5x − y + 2z =
12
3x + 8y − 2z = −25
x + y + 4z =
6
Wir formen nach den Variablen auf der Diagonale um und erhalten:
x =
12
5
+ 15 y − 25 z
3
2
y = − 25
8 − 8x + 8z
z =
Startvektor sei:
6
4
− 14 x − 41 y
0
x
0
y0 = 0 ,
z0
0
x1
2,4
−25 − 3 · 2,4 + 2 · 0
y1 =
= −4,03
8
6 − 2,4 + 4,03
z1
= 1,91
4
usw.
Matrizenschreibweise (A wird wieder zerlegt):
~ = (L + D + R) · x
~
A·x
= ~b
~ + D · ~x + R · ~x
= L·x
= ~b
~ = ~b − (L + R) · x
~
D·x
~ − R · ~x
= ~b − L · x
Das hatten wir schon.
In jedem Iterationsschritt gilt dann (Rechnung genau ansehen):
~ (k+1) = ~b − L · x
~ (k+1) − R · ~x (k)
D·x
~ (k+1) = ~b − R · x
~ (k)
(D + L) · x
~ (k+1) = (D + L)−1 · ~b − (D + L)−1 · R · x
~ (k)
x
Das Verfahren konvergiert wieder bei Diagonaldominanz, falls A symmetrisch und positiv definit
ist oder falls der Spektralradius (Betrag des betragsmäßig größten Eigenwerts) von −(D +L)−1 ·R
kleiner 1 ist. Der Startvektor ist beliebig.
Wird der Startvektor als Linearkombination von Eigenvektoren ~di (Eigenwert λi ) dargestellt,
entstehen bei der kten Iteration Terme wie ai λki ~di . Für |λ| < 1 streben sie gegen null.
Relaxation für Iterationsalgorithmen
(engl. Lockerung, Entspannung)
Die Schrittweite der Iteration können wir beeinflussen.
~ ∗(k+1)
Nehmen wir an, es liegt ~x (k) vor und wir führen den nächsten Iterationsschritt aus: x
Das Ergebnis wurde umbenannt, weil es noch abgeändert werden soll.
y
g
bc
bc
bc
~ ∗(k+1)
x
~ (k+1)
x
~ (k)
x
x
~ (k+1) wäre auch
Für das endgültige x
~ (k+1) = x
~ (k) + ω (~x ∗(k+1) − ~x (k) )
x
= (1 − ω)~x (k) + ω~x ∗(k+1)
mit einem geeignet gewählten ω ∈ R möglich. Das entspricht einem Punkt auf der Geraden g.
In
~ (k+1) = (1 − ω)~x (k) + ω~x ∗(k+1) wird für x
~ ∗(k+1) die rechte Seite des Verfahrens von Jacobi
x
bzw. Gauß-Seidel eingesetzt.
Für ω = 1 bleibt das Iterationsverfahren unverändert.
Für z. B. ω = 0,3 nähern wir uns verzögert (vielleicht monoton) der Lösung,
allgemein für 0 < ω < 1 (under-relaxation).
Das SOR-Verfahren (successive over-relaxation) verwendet ein ω mit 1 < ω < 2.
Das kann die Konvergenzgeschwindigkeit erhöhen.
Anhang
Jede Matrix lässt sich in eine untere Dreiecksmatrix L,
eine Diagonalmatrix D und eine obere Dreiecksmatrix R zerlegen:
a11 a12 a13 a14
a21 a22 a23 a24
a31 a32 a33 a34
a41 a42 a43 a44
0
0
0
0
a11
0
0
0
a21 0 0 0 0 a22 0 0
=
+
a31 a32 0 0 0 0 a33 0
a41 a42 a43 0
0 0 0 a44
|
{z
} |
{z
L
D
0 a12 a13 a14
0 0 a23 a24
+
0 0 0 a34
0 0 0 0
} |
{z
R
}
© Copyright 2024 ExpyDoc
