Page 117 - A First Course In Stochastic Models

COMPUTATION OF THE EQUILIBRIUM PROBABILITIES 109

 
i−1 N
(k) (k−1) (k) (k−1)
x = (1 − ω)x + ω  a ij x + a ij x  .
i i j j
j=1 j=i+1
Step 2. If the stopping criterion

N
N
(k) (k−1) (k)

x − x ≤ ε x
i i i
i=1 i=1
is satisfied with ε > 0, a prespecified accuracy number, then go to step 3. Otherwise
k := k + 1 and go to step 1.
Step 3. Calculate the solution to (3.4.1) and (3.4.2) from
(k)
x
∗ i
x = , 1 ≤ i ≤ N.
i
N
(k)
x
j
j=1
The specification of the tolerance number ε typically depends on the particular
problem considered and the accuracy required in the final answers. In addition to
the stopping criterion, it may be helpful to use an extra accuracy check for the
equilibrium probabilities of the underlying Markov chain. An extra accuracy check
may prevent a decision upon a premature termination of the algorithm when the
tolerance number ε is not chosen sufficiently small. Notice that the normalizing
equation (3.4.2) is used only at the very end of the algorithm. In applying succes-
sive overrelaxation it is highly recommended that all of the equilibrium equations
(3.4.1) are used rather than omitting one redundant equation and substituting the
normalizing equation (3.4.2) for it.
The convergence speed of the successive overrelaxation method may dramati-
cally depend on the choice of the relaxation factor ω, and even worse the method
may diverge for some choices of ω. A suitable value of ω has to be determined
experimentally. Usually 1 ≤ ω ≤ 2. The choice ω = 1.2 is often recommended.
The optimal value of the relaxation factor ω depends on the structure of the partic-
ular problem considered. It is pointed out that the iteration method with ω = 1 is
the well-known Gauss–Seidel method. This method is convergent in all practical
cases. The ordering of the states may also have a considerable effect on the con-
vergence speed of the successive overrelaxation algorithm. In general one should
order the states such that the upper diagonal part of the matrix of coefficients is as
sparse as possible. In specific applications the transition structure of the Markov
chain often suggests an appropriate ordering of the states.

Krylov iteration method
The Gauss–Seidel iteration method can further be refined to obtain orthogonal basis
vectors for a so-called Krylov space. The construction of an appropriate Krylov