Graphics Programs Reference
In-Depth Information
Solving for
x
i
, we get
⎛
⎝
⎞
⎠
n
1
A
ii
x
i
=
b
i
−
A
i j
x
j
,
i
=
1
,
2
,...,
n
j
=
1
j
=
i
The last equation suggests the following iterative scheme
⎛
⎝
⎞
⎠
n
1
A
ii
x
i
←
b
i
−
A
i j
x
j
,
i
=
1
,
2
,...,
n
(2.34)
j
=
1
j
=
i
Westart by choosing the starting vector
x
. If agoodguess for the solutionis not
available,
x
can be chosen randomly. Equation (2.34) is thenused to recompute each
elementof
x
, always using the latest available values of
x
j
. Thiscompletes one iteration
cycle. The procedure is repeateduntil the changes in
x
between successive iteration
cycles becomesufficiently small.
Convergence of the Gauss-Seidel method can be improvedbyatechniqueknown
as
relaxation
. The ideaistotake the newvalueof
x
i
as aweightedaverageofits previous
value and the value predictedbyEq. (2.34). The corresponding iterativeformulais
⎛
⎝
⎞
⎠
+
n
A
ii
x
i
←
b
i
−
A
i j
x
j
(1
−
ω
)
x
i
,
i
=
1
,
2
,...,
n
(2.35)
j
=
1
j
=
i
where the weight
1,
no relaxation takes place, since Eqs. (2.34) and (2.35) produce the same result. If
ω<
ω
iscalled the
relaxation factor
. It can be seen that if
ω
=
,
Eq. (2.35) represents interpolationbetween the old
x
i
and the value givenby
Eq. (2.34). This iscalled
underrelaxation
. In cases where
1
ω>
1, wehaveextrapolation,
or
overrelaxation
.
There is no practical method of determining the optimal valueof
ω
beforehand;
x
(
k
)
be the magnitude of the change in
x
during the
k
th iteration (carried out without
relaxation; i.e., with
=
x
(
k
−
1)
x
(
k
)
however, agood estimate can becomputed during run time.Let
−
5), itcan be shown
2
that
ω
=
1). If
k
issufficiently large(say
k
≥
an approximation of the optimal valueof
ω
is
2
ω
opt
≈
1
(2.36)
−
x
(
k
)
1
/
p
1
+
x
(
k
+
p
)
/
where
p
is apositive integer.
2
See, for example, Terrence J.Akai,
Applied Numerical Methods for Engineers
,JohnWiley & Sons
(1994), p. 100.
Search WWH ::
Custom Search