Page 291 - Linear Models for the Prediction of Animal Breeding Values 3rd Edition

17.3.2 Gauss–Seidel iteration

Another iterative procedure commonly used is Gauss–Seidel iteration. This is similar
to Jacobi iteration except that most current solutions are calculated from the most
recent available solution rather than the solution from the previous round of itera-
tion. Using the same set of simultaneous equations as in Eqn 17.1, solutions for b ,
1
b and b in the first round of iteration become:
2 3
r+ 1 11 y - r r
1 cb -
1 b =( 1 /c ) ( 12 2 c b )
13 3
r+ 1 r+ 1 - r
2 b =( 1 /c ) ( 2 2 21 1 c 23 3 b ) (17.4)
22 y - cb
r+ 1 r+ 1 - r+1
3 b = ( 1 /c 33 y -) ( 3 cb c 32 2 b ) )
31 1
Thus the solution for b in the r + 1 round of iteration is calculated using the
2
most recent solution for b (b r+1 ) instead of the previous solution (b ), and the
r
1 1 1
current solution for b is calculated from the current solutions for b (b r+1 ) and
3 1 1
b (b r+1 ). If, in Eqn 17.3, L is strictly the lower triangular of C and D the diago-
2 2
nal of C, then Eqn 17.3 becomes the Gauss–Seidel iteration when M = L + D.
The convergence criteria could equally be defined as discussed in Section 17.3.1.
Generally, equations are guaranteed to converge with the Gauss–Seidel iterative
procedure. However, when iterating on the data, this iterative procedure
involves reading one data file for each effect in the model. With large data sets,
the setting up of data files for each effect could result in large memory require-
ment and the reading of several files in each round of iteration could increase
processing time.
Example 17.2
Using the same coefficient matrix, RHS and starting values as in Example 17.1 above,
the Gauss–Seidel iteration (Eqn 17.4) is carried out for the same number of iterations
as in Jacobi’s method and the results are shown below. The convergence criterion is
as defined in Example 17.1.

Rounds of iteration
Effects 0 1 2 3 4 16 17 18 19 20
b 4.333 4.333 4.400 4.372 4.364 4.359 4.359 4.359 4.359 4.359
1
b 3.400 3.400 3.392 3.403 3.407 3.405 3.405 3.405 3.405 3.405
2
u ˆ 0.000 0.333 0.194 0.149 0.115 0.098 0.098 0.098 0.098 0.098
1
u ˆ 0.000 −0.083 −0.035 −0.006 −0.008 −0.019 −0.019 −0.019 −0.019 −0.019
2
u ˆ 0.000 −0.021 −0.136 −0.109 −0.076 −0.041 −0.041 −0.041 −0.041 −0.041
3
u ˆ 0.167 −0.119 0.001 0.004 −0.003 −0.009 −0.009 −0.009 −0.009 −0.009
4
u ˆ −0.500 −0.376 −0.261 −0.218 −0.199 −0.186 −0.186 −0.186 −0.186 −0.186
5
u ˆ 0.500 0.392 0.254 0.204 0.185 0.177 0.177 0.177 0.177 0.177
6
u ˆ −0.833 −0.364 −0.284 −0.260 −0.253 −0.250 −0.250 −0.250 −0.250 −0.250
7
u ˆ 0.667 0.282 0.167 0.164 0.171 0.182 0.183 0.183 0.183 0.183
8
CONV 1.000 1.9 −2 3.4 −3 3.1 −4 1.0 −4 7 −10 4 −10 2 −10 1 −10 8 −11
CONV, convergence criterion.
Solving Linear Equations 275