Page 477 - A First Course In Stochastic Models

472 APPENDICES

complex conjugates of ln(z) and β(z) are given by ln(z) and β(z) (use that β(z)
is a power series in z with real coefficients). Thus, if z ℓ is a solution to (G.3) with
k = ℓ, then the complex conjugate z ℓ is a solution to (G.3) with k = −ℓ. Hence it
suffices to let k run only from 0 to ⌊c/2⌋. Further, note that the solution of (G.3)
with k = 0 is given by z 0 = 1. For each k with 1 ≤ k ≤ ⌊c/2⌋ the equation (G.3)
can be solved by using the well-known Newton–Raphson method. This powerful
method uses the iteration
h(z (n) )
(n+1) (n)
z = z −
h (z (n) )
′
when the equation h(z) = 0 has to be solved. Applied to the equation (G.3), the
iterative scheme becomes
(n) (n) (n)
(n) ′
1 − (λD/c)[1 + z β (z ) − β(z )] − ln(z ) + 2πik/c
(n+1) (n) k k k k
z = z × ,
k k (n) (n)
1 − (λD/c)z β (z )
′
k k
(0)
where β (z) is the derivative of β(z). The starting value z for the Newton–
′
k
Raphson iteration has to be chosen properly. To make an appropriate choice for
(0)
z , we have a closer look at the equation (G.3). Let us rewrite this equation as
k
ln(z) = (λD/c){β(z) − 1} + 2πik/c and analyse it for the case of light traffic with
λ → 0. Then the solution of the equation tends to e 2πik/c . Inserting z = e 2πik/c
on the right-hand side of the equation for ln(z) yields

(0) 2πik/c
z = exp (λD/c){β(e ) − 1} + 2πik/c .
k
We empirically verified that this is an excellent choice for the starting value of the
Newton–Raphson scheme. In the above approach the roots of (G.1) are calculated
by solving (G.3) separately for each value of k. If some roots are close together,
Newton–Raphson iteration may converge each time to the same root when this pro-
cedure is directly applied to (G.1). However, this numerical difficulty is eliminated
when (G.3) is used as an intermediary.
c λD{1−β(z)}
The above approach for solving 1 − z e = 0 can be modified to find
the roots of the equation
c
z − A(z) = 0
inside or on the unit circle when A(z) is the generating function of a non-negative,
integer-valued random variable. Assuming that A(0) = 0 (otherwise, z = 0 is a
c
root), the equation z − A(z) = 0 can be transformed into the equation
c ln(z) − ln(A(z)) = 2πik
where k is any integer. In general it is recommended to solve this equation by the
modified Newton–Raphson method; see Stoer and Bulirsch (1980). In the modified
Newton–Raphson method the step size is adjusted at each iteration in order to
c
ensure convergence. In the special case that z − A(z) is a polynomial in z, the