Citation
Implementation of the conjugate gradient method using short multiple recursions

Material Information

Title:
Implementation of the conjugate gradient method using short multiple recursions
Creator:
Barth, Teri L
Place of Publication:
Denver, CO
Publisher:
University of Colorado Denver
Publication Date:
Language:
English
Physical Description:
vi, 150 leaves : illustrations ; 29 cm

Subjects

Subjects / Keywords:
Conjugate gradient methods ( lcsh )
Matrices ( lcsh )
Numerical analysis ( lcsh )
Conjugate gradient methods ( fast )
Matrices ( fast )
Numerical analysis ( fast )
Genre:
bibliography ( marcgt )
theses ( marcgt )
non-fiction ( marcgt )

Notes

Bibliography:
Includes bibliographical references (leaves 148-150).
Thesis:
Submitted in partial fulfillment of the requirements for the degree, Doctor of Philosophy, Applied Mathematics
General Note:
Department of Mathematical and Statistical Sciences
Statement of Responsibility:
by Teri L. Barth.

Record Information

Source Institution:
|University of Colorado Denver
Holding Location:
|Auraria Library
Rights Management:
All applicable rights reserved by the source institution and holding location.
Resource Identifier:
37296541 ( OCLC )
ocm37296541
Classification:
LD1190.L622 1996d .B37 ( lcc )

Downloads

This item has the following downloads:


Full Text
IMPLEMENTATION OF THE CONJUGATE
GRADIENT METHOD USING SHORT MULTIPLE
RECURSIONS
by
Teri L. Barth
B. S., Colorado State University, 1977
M. S., University of Colorado at Denver, 1992
A thesis submitted to the
University of Colorado at Denver
in partial fulfillment
of the requirements for the degree of
Doctor of Philosophy
Applied Mathematics
1996


This thesis for the Doctor of Philosophy
degree by
Ten L. Barth
has been approved
by


William L. B
Date
12/


Barth, Teri L. (Ph.D., Applied Mathematics)
Implementation Of The Conjugate Gradient
Method Using Short Multiple Recursions
Thesis directed by Professor Thomas A. Manteuffel
ABSTRACT
Iterative methods are important mechanisms for solving linear systems of
equations of the form, Ax = 6, when A is a large sparse nonsingular matrix. When
an efficient implementation exists, the conjugate gradient (CG) method is a popu-
lar technique of this type. This method is implemented via the construction of an
orthogonal basis for the underlying Krylov subspace. When this basis can be con-
structed using recursions that involve only a few terms at each step, then a practical
CG algorithm exists. The current theory from Faber and Manteuffel regarding the
economical implementation of the conjugate gradient method does not take into ac-
count all possible forms of short recurrences. By considering a more general form of
recursion, we will extend the class of matrices for which a practical CG algorithm is
known to exist.
This study begins with a review of the conjugate gradient method, and the
existing theory regarding its economical implementation. An overview of previous
work concerning unitary and shifted unitary matrices will be presented since this
motivates our definition of a more general form of short multiple recursion. Sufficient
and partial necessary conditions on the matrix A will be determined in order that a
iii


CG method can be implemented using this type of recursion. One sufficient condition
is for the matrix A to be 2?-normal(£, m). These are normal matrices whose adjoint
can be expressed as the ratio of two polynomials in A. Another sufficient condition
is for A. to be a low rank perturbation of a J3-normal(£, m) matrix. Am important
example of this type is a matrix that is self-adjoint plus low rank. These results will
be illustrated with a few numerical examples. In addition to extending the class of
matrices for which a practical CG algorithm exists, this research opens the door to
the possibility that other forms of short recurrences may exist that would admit an
efficient CG algorithm for even a wider class of matrices.
This abstract accurately represents the content of the candidates thesis. I recom-
mend its publication.


CONTENTS
Chapter
1. Introduction....................................................... 1
1.1 Motivation And Organization.................................... 1
1.2 Notation....................................................... 4
2. The Conjugate Gradient Method.................................... 5
2.1 Introduction................................................... 5
2.2 Derivation Of The Conjugate Gradient Method.................... 5
2.3 Implementation................................................. 9
2.4 Economical Conjugate Gradient Algorithms...................... 13
3. Unitary And Shifted Unitary Matrices.............................. 19
3.1 Introduction.................................................. 19
3.2 A Short Double Recursion For Unitary Matrices................. 20
3.3 A Minimal Residual Algorithm For Shifted Unitary Matrices . 22
3.4 Conjugate Gradient Algorithms For General
B-Unitary And Shifted Shifted B-Unitary Matrices........... 25
3.5 A New Minimal Residual Algorithm For Shifted Unitary Matrices 27
4. Multiple Recursion Formulation.................................... 31
4.1 Introduction.................................................. 31
4.2 B-Normal(£, m) Matrices....................................... 33
4.3 A Multiple Recursion For B-Normal(£, m) Matrices.............. 39
4.4 A Multiple Recursion For Generalizations
Of B-Normal(f, m) Matrices.................................... 47
4.5 Breakdown In The Single (s, i)-Recursion ..................... 58
v


4.6 Concluding Remarks .......................................... 60
5. Implementation And Numerical Results.............................. 62
5.1 Introduction................................................. 62
5.2 B-NormaI(£, m) Matrices...................................... 62
5.3 Generalizations Of B-Normal(£, m) Matrices................... 71
5.4 Concluding Remarks........................................... 90
6. Necessary Conditions.............................................. 91
6.1 Introduction................................................. 91
6.2 Preliminaries................................................ 92
6.3 Proof Of Necessary Conditions............................... 112
7. Conclusion....................................................... 144
Appendix
A. Properties Of Determinants....................................... 146
References.............................................................. 148


1. Introduction
1.1 Motivation And Organization
A conjugate gradient method for the solution of an TV x N linear system of
equations
Ax = b,
is defined with respect to an inner product matrix B, and the matrix A. It is a
Krylov subspace method in which the B-norm of the error is minimized at each step
(see Section 2.2). A conjugate gradient method is implemented via the construction
of a B-orthogonal basis {pt)i=o for ICj+\(rQ, A), where
£j+i(Tj,,A) =sp{ro, Aro, ..., A-'Vo),
is the Krylov subspace of dimension j + 1 generated by the initial residual and
the matrix A. The p.s are called direction vectors. There are many algorithms
for implementing the method, for example: Orthodir, Orthomin, Orthores, and
GMRES.
If a B-orthogonal basis can be constructed with some form of a short recur-
sion, then the work and storage requirements to implement the method axe minimal,
and we say an economical conjugate gradient algorithm exists. In 1984, Faber and
Manteuffel [5] proved that the class of matrices for which a conjugate gradient method
can be implemented via a single short (5 -1- 2)-term recursion of the form
j
E;+1 = APj £ VijRv
ijs
for the direction vectors, is limited to matrices that are B-normal(s) or to matrices
1


with only a small number of distinct eigenvalues (see Section 2.4). It became appar-
ent in the work done by Gragg [10] that this form of recursion is not general enough
to account for all possible short recurrences. The unitary matrix is an example of a
matrix for which am orthonormal basis cannot be constructed with a short (s + 2)-
term recursion, however, Gragg demonstrated that this basis can be constructed
using a pair of recurrence formulas. Shifted unitary matrices have the form
A = pU + £I,
where U is unitary, I is the identity matrix, and p and £ are complex scalars.
Jagels and Reichel ([16],[17]) observed that for matrices of this form, £J+1(r0, A) =
£i+i(ro,CO, and thus, the same double recursion as for the unitary case, can be
used to construct an orthonormal basis. They continued, showing how to derive
an efficient minimal residual algorithm. This motivates the work in this thesis con-
cerning alternate forms of short recurrences. By considering a more general form
of recursion, we will show that the class of matrices for which a practical conjugate
gradient algorithm is known to exist, can be extended.
In Chapter 2, the conjugate gradient method is defined. We then discuss
how the method is implemented. An overview of previous work concerning econom-
ical conjugate gradient algorithms is given. Chapter 3 summarizes the work done by
Gragg, Jagels and Reichel on unitary and shifted unitary matrices.
The double recursion for unitary and shifted unitary matrices can be rewrit-
ten as a single (s, £)-recursion of the form
i-i j
pj+1 = APj + £ &jA2i £ vijSi-
i=j~t i=j-s
If A is unitary, t = 1 and s = 0; if A is shifted unitary, t = 1 and s = 1. We
notice that if A is unitary, its adjoint, A* = AT, can be written as the ratio of two
2


polynomials,
A* = A~l =
Po(A)
91 (A)
where po(A) = I, and gi(A) = A. The degrees of these polynomials correspond to
the number of terms needed in the single (s, t)-recursion to construct an orthogonal
basis.
In Chapter 4, we will define and characterize a more general class of normal
matrices, called B-normal(£, m) matrices. The B-adjoint of these matrices, A*, (see
Section 2.4), can be expressed as the ratio of two polynomials,
t= PM
9m(A)
of degrees t and m respectively. In the absence of a condition we call breakdown,
if A is B-normal(l, m), then a B-orthogonal basis can be obtained using a single
(s, f)-recursion, with (s, t) = (£, m). This result can be extended to more general
matrices, which include low rank perturbations of B-normal(£, m) matrices. An
important example of this type is a matrix that is self-adjoint plus low rank.
Since breakdown is possible using the single (s, t)-recursion, we will show
how the problem can be reformulated as a multiple recursion that avoids the possi-
bility of breakdown. Sufficient conditions on the matrix A are then stated in order
that a B-orthogonal basis can be constructed using this form of multiple recursion.
In Chapter 5, we will discuss the details on how to implement the method
using this form of recursion. Numerical examples are given comparing the results to
those using a full conjugate gradient algorithm.
To determine if there are any other matrices for which a B-orthogonal
basis can be constructed using this form of multiple recursion, we must answer the
question of whether the sufficient conditions are also necessary. This is a much more
difficult problem which we will answer in Chapter 6 for only a restricted subset of
3


the multiple recursions derived earlier. A brief summary is given in Chapter 7.
1.2 Notation
The notation will be explained when it is first introduced. For convenience,
we summarize this below.
Kn, Cn Vector spaces of real and complex n tuples.
jjnxm gnxm _ Vector spaces of real and complex n x m matrices.
K\ V,... Other calligraphic letters denote subspaces of 72." or C1.
A, J5,... Upper case Roman (Greek) letters denote matrices.
Underlined lower case Roman (Greek) letters denote vectors.
Gt, . Lower case Roman (Greek) letters denote scalars.
<. >. Ml Euclidean inner product on Cn and induced norm.
(*,) INI* - Binner product on Cn and induced Bnorm.
-1-B ~ Represents orthogonality in the B inner product.
A* Euclidean adjoint of A, A = AF.
At Badjoint of A, A^ = B~lA*B.
SP {%} The linear span of the vectors Xj.
S(A) Spectrum of A.
A) sp{Eo> Aro,..., A*-1ro}. Krylov subspace of dimension L
dito, A) Degree of the minimal annihilating polynomial of £q.
d(A) Degree of the minimal polynomial of A.
4


2. The Conjugate Gradient Method
2.1 Introduction
Consider the linear system of equations
4e = £, (2.1)
where A is a general N x N nonsingular matrix, and z and k G CN. This chapter is
concerned with the solution of (2.1) using a conjugate gradient method.
After some background on polynomial iterative methods, a general defi-
nition of the conjugate gradient method will be given. Next, we describe how the
method is implemented. Of particular interest will be the conditions under which a
conjugate gradient method can be implemented with some form of a short recursion,
thus requiring only minimal amounts of computation and storage. An overview of
previous results on this topic is given. We conclude this chapter by noting that
the current theory on economical implementation of the conjugate gradient method
does not take into account all possible forms of short recursions. This motivates
the further study of conjugate gradient algorithms using alternate forms of short
recursions.
2.2 Derivation Of The Conjugate Gradient Method
Given an initial guess zq to (2.1), an iterative method produces a sequence
of approximations {zq, xx, ...} to the exact solution z = A~lb. Iterative methods
are important techniques for obtaining a solution when A is large and sparse.
Consider an iterative method where for j = 0,1,..., the new iterate is
5


defined by,
where,
Zi = b-Azi = A{£ xt) = A^,
(2.2)
(2.3)
is the residual at step t, and g, denotes the error at step t. Bach new iterate is
updated with some linear combination of previous residuals. By subtracting both
sides of (2.2) from the exact solution x, and using (2.3), we obtain an expression for
the error at step j + 1,
j
Sj+1 = So ^
i=0
Let IN denote the N x N identity matrix, and note that
So = fjvSo =Po(A)e0,
where po(0) = 1- Suppose that for t = 0,..., j, e,- = Pi(A)eo, and pi(0) = 1. By
induction, we obtain
j
j+i ~ So 2 aijA Pi(A)eo
t=0
= (2'4)
= Pj+i(A)so.
for some polynomial, pJ+i(p) = [1 p py(p)], of degree < j + 1. Furthermore, we
see that pj-+i(0) = 1. Notice that the residual at step j 4-1 can be written as
Lj+1 = A pi+i(A)eo =pJ+i(A)r0.
The polynomials pj+\ (ji) are known as residual polynomials. Since the error at each
step can be written as a polynomial in A times the initial error, iterative methods
of this form are called polynomial methods.
6


Define the (j + l)st Krylov subspace generated by and the matrix A as
£j+i(Eo, >1) = sp{ro, Ar, ..., A3to). (2.5)
The vectors {At^}^_0 are called Krylov vectors.
Denote d(A) as the degree of the minimal polynomial of A, that is,
d(A) = min (deg p : p(A) = 0}.
pi p monic
Define d = d(z_, A) to be the maximum dimension of the Krylov subspace generated
by z and the matrix A. This is the degree of the minimal annihilating polynomial
of z,
d = d(z, >1) = min {deg p : p(A)z = 0}.
pi p monic
Since the Krylov subspaces are nested, and for every i, r{ = Pi(A)r0 E
A), it follows that (2.2) can be rewritten as,
£j+1 = £o+Pj(A)ro
= So + Ij, where zy G /Cy+i(t^, A),
or equivalently,
Sj+l =Sj +Sji
for some Zy G £y+i(£o, A). We make the following definition:
DEFINITION 2.1 A Krylov subspace method is an iterative method
whose iterates are defined by:
Sy+i = Sy+Sy, Zy G £y+i(ro, A),
%+i = Pj+i(4)eo, P/(0) = 1.
There are many Krylov subspace methods. What distinguishes a method
is the way in which the vector zy is chosen from /Cy-fifo, A). Since our goal is to
find a solution to (2.1), a logical strategy would be to choose zy G £y+i(lo, A) so
7


that the error is as small as possible. However, we would also like to accomplish this
with a relatively small amount of work. As we will see later, these two goals are not
always compatible.
Since ||£J+i|| = ||pj+i(A)£o|| < ||pJ+i(A)|| ||£o||, we differentiate two basic
strategies for making the error small:
(1) Make ||p/+i(A)|| small,
(2) make ||pj+i(-4)foll small.
Methods that employ the first strategy involving matrix norms, are often referred to
as Chebychev-like methods. They require some knowledge of the spectrum of A to
implement. Methods that utilize the second strategy are called conjugate gradient-
like methods. They are based upon optimization in an inner product norm, or on
some orthogonalization property. No knowledge of the spectrum is required for their
implementation.
As the name suggests, conjugate gradient methods utilize the second strat-
egy. They are Krylov subspace methods in which the error is minimized at every step
in an inner product norm. We will define this method with respect to a Hermitian
positive definite inner product matrix B, and the system matrix A, and denote it as
CS(B,A).
DEFINITION 2.2 A conjugate gradient method, CQ(B, A), is a Krylov
subspace method whose iterates are defined uniquely as follows:
Zj+l = S.j+Zj, £jG*d+i(Eo,A),
(2.6)
IlSj+illfl is minimized over K,j+ i(rjj, A).
The second condition is equivalent to requiring
§.j+i -Lb z, Vz ICj+i(tq, A).
There are many conjugate gradient methods. Consider for example, if A
is symmetric positive definite, (A-, ) defines an inner product, and we could take
8


B = A. CQ(B,A) minimizes the A norm of the error, which results in the origi-
nal conjugate gradient method of Hestenes and Stiefel [14]. Another example of a
conjugate gradient method is given by taking B = A*A. Notice that since we are
assuming that A is nonsingular, A* A is Hermitian positive definite. In this case,
CQ(B,A) minimizes
11%+iIUm = (A*Agy+1, £y+1)* = (Cy+i, Lj+l)*,
yielding a minimal residual method. A detailed taxonomy of conjugate gradient
methods can be found in [1].
2.3 Implementation
A conjugate gradient method is implemented via the construction of a B-
orthogonal basis for the Krylov subspace. This follows directly from the definition
of the method. To see this, first, we obtain an expression for the error at each step
in terms of the error at the previous step by subtracting the first equation in (2.6)
from the exact solution yielding
ei+i = ey zj. (2.7)
According to Definition 2.2, at each step j -I- 1, we must choose Zy G /Cy+i(r^, A) so
that
ey+1 -Lb Z> Vz £y+1 (r,), A).
Since ACj(ro- A) C £y+i(tq, A), it follows that for every z /Cy(rjj, A),
0 = (Bej+l,z)
= (Bey, z) (Bzy, z),
where the second equality results from substituting in (2.7). Prom the definition,
it follows that for every z G /Cy(rQ, A), (Bey, z) = 0, which implies (Bzy, z) = 0.
9


Therefore, we obtain two conditions:
2.j e /CJ+1(ro,A), and
= 0, Vz £ JCj(ro,A).
These conditions say at each step, we must choose zy £ /Cj+i(lo> A) such that zy is
B-orthogonal to everything in A). This means a conjugate gradient method
can be implemented by constructing a B-orthogonal basis for £j+i(rg, A).
Here, p. £ /C,+i(£o> A), and p^ b AC,-(ro, A), for i = 0, The p^'s are known as
direction vectors. Given an initial vector, Pq = rg, a B-orthogonal basis is unique
up to scale, or the length of the vectors. At step j + 1, let
Zj = aJPr
where ay is known as the step length.
To determine the step length, notice that Pj £ Ky+ifo, A). It follows from
the definition that
0 = (Bej+l, p.) = (Bey, p.) aj(Bp., p.).
Since B is Hermitianpositive definite, (Bp., p^.) ^ 0, and we can solve for ay yielding,
_ (B&j, gy)
aj ~ (BPy, Py) '
Summarizing the above, to implement CQ{B,A), given p^, at each step, compute:
1) Py 6 ACy+i^.A) such that p^. b ^(pjj.A),
2) Xy+1 = Xj + OCjPj, aj = jgg^y.
Since the computation of ay involves the unknown quantity of the error,
the inner product matrix B must be chosen so that ay is computable. For example,
if A is Hermitian positive definite, we could choose B = A, and
^ (^Py Py)
10


By choosing B A* A, we obtain
(rj, Ap.)
03 ~ (Apj, ApJ
From the above, we see that the work involved in implementing a con-
jugate gradient method is in the construction of a B-orthogonal basis {pt-}j_0 for
£j+i(£o,j4). There may be many different ways of writing the recursion for con-
structing such a basis. However, since this basis is unique up to scale, as long as
the vectors are scaled the same, the recursions can always be rewritten in terms of
a Gram-Schmidt process,
Eo = Eo.
A (g^Pn'gn)
Hi = AEo-ff *0,0=
(2.8)
Pj+i = A*i ~
Suppose that d{p^, A) = N, where N is the dimension of A. The matrix form of this
recursion at step N is given by:
&v-i] = [So2i
HjV-l]
0o,o 1 <71,1
1
0-O.JV-l
, (2.9)
which we denote as,
1 0"JV-1,AT-1
APn = PnHn-
In general, Hfj is a full upper Hessenberg matrix. By equating the columns in the
matrix equation, we obtain the individual formulas for the direction vectors given
in (2.8). Note that at any given step fc, after computing the recursions can be
written in matrix form as
APk = Pk+iHk+hk, (2.10)
11


where P* is the matrix containing the first k columns of Py, and Hk+ij: is the upper
left (k +1) x k comer of Hir.
The various ways of writing the recursions for the direction vectors will
yield different algorithms for implementing a given conjugate gradient method. We
list the Orthodir algorithm below. It is an example where the direction vectors are
obtained using a full Gram-Schmidt process generalized to the B-inner product.
Table 2.1: Orthodir Algorithm
lo = k-Axo,
£0 = Eo>
£j+i = Xj + ajpp ~ {Bp.]p.)
£j+1 = Zj ctjAp^
Sh-i i = Ap £ djp 3 i=0 Notice that in the Orthodir algorithm, the recursion for the direction vector
p.+1 utilizes the term Ap. G ICj+zila, A), to bring the recursion up to the next higher
dimension Krylov subspace. When BA is definite, the residuals span the Krylov
subspace [1],
£j+2(Eo,A) = sp^, pv ..., Pi+1} = sp{ro, Hx, ..., ri+1}.
Instead of using the term Ap. to bring us up to ^+2(101 A), we can use rJ+l. An
example of am algorithm that uses this approach is the Orthomin algorithm, given
in Table 2.2.
Both of these algorithms utilize all the previous direction vectors to con-
struct p..,. In the next section, we will see that for certain kinds of matrices A. a
P-orthogonal basis can be constructed with a short recursion that uses only a few
previous direction vectors.
12


Table 2.2: Orthomin Algorithm
Eo = k-Axo,
Eo = Eo.
= Xj+Ctjp., (Bej,p)
£j+i a3 ~ (Bp.,p.)'
£#+1 = Lj-ctjApj,
Hi+i 3 = Ej'+l ~ S aijPi> 1=0 (Brj+1,p.
2.4 Economical Conjugate Gradient Algorithms
Before discussing when a conjugate gradient method can be implemented
with a short recursion for the direction vectors, we review some terminology on
normal matrices.
First, the concept of an adjoint of a matrix A is generalized to the B-inner
product. The B-adjoint of A is the unique matrix A* satisfying,
(BAx, y) = (Bx, Afy), Vx, yeCN.
This yields, A* = B~lA*B.
The following conditions are generalizations of those for normal matrices.
A matrix A is B-normal if it satisfies the following equivalent conditions:
(1) AA* = A*A,
(2) A and A* have the same complete set of B-orthogonal eigenvectors,
(3) A* can be written as a polynomial of some degree in the matrix A.
We say that A is B-normal(s), if it is B-normal, and s is the degree of the
polynomial, ps(A), of smallest degree for which A* = p*(A). For example, if A is
B-normal(l), then A* can be written as a first degree polynomial in A.
Recall the matrix equation in (2.9) for the construction of a B-orthogonal
13


basis. The entries of the Hessenberg matrix Hn ate given by,
{BAp.,p.) (BPi>Ei) if j > t
1 if j = i
0 if j If A is fi-normal(l), A* = pi(A), and thus
A^. Ki+2(s0,A) = sp^, p^}.
It follows that if j > i -f 1,
Pj -Lb ICi+2^, A),
which means cr,j = 0, yielding a tridiagonal matrix Hu- The recursion in (2.8)
naturally truncates to the 3-term recursion,
i
Pj+i = AEj ~ £
i=j-i
A special case of B-normal(l) matrices are B-self-adjoint matrices. They
satisfy:
A* = A, or
BA = (BA)* = AmB.
Consider an (s -I- 2)-term recursion of the form:
J (BAp.,p.)
Ej+i=aE,- E no = (2.11)
1=75 '
DEFINITION 2.3 The matrix A is in the class CQ(s) if for every r^, a
single (s + 2)-term recursion of the form given in (2.11) can be used to construct a
B-orthogonal basis for KdiZo, A).
THEOREM 2.1 A e= CQ(s) if and only if
d(A) < s + 2 or A is Bnormal(s).
14


Proof: The proof is a result from Faber and Manteuffel [5].
This result was extended in 1988 by Joubert and Young [18], who showed
that the recursions for the direction vectors in the Orthomin implementation of
CQ(ByA) also naturally truncate for B-normal(s) matrices.
In their 1984 paper, Faber and Manteuffel characterized B-normal(s) ma-
trices. These results are given in the following lemma.
LEMMA 2.2 If A is B-normal(s);
1) . if s > 1, then d(A) < s2,
2) . if s = 1, then either d(A) = 1, A = A*t or
A = e(,|/ + G),
where i = y/l, r > 0 is a real number, 0 < 6 < 27t, and G = G*.
Proof: The proof is given in [5].
Summarizing, if A is B-normal(s), and s > 1, then A has at most s2
distinct eigenvalues. If s = 1 and A has more than 1 distinct eigenvalue, then all
the eigenvalues of A lie on some straight line in the complex plane. Note that in
the case that A is B-self adjoint, all the eigenvalues of A are real. Otherwise, the
eigenvalues of A can be obtained by shifting and then rotating the eigenvalues of a
B-self adjoint matrix G, yielding collinear eigenvalues.
These results say that an economical recursion for the direction vectors, of
the form given by (2.11), can only be applied to a very small class of matrices. In
Tables 2.3 and 2.4 we list two algorithms that are applicable when A is B-normal(l).
The Omin algorithm carries the further restriction that BA be definite.
We might ask if there are other forms of short recursions that cant be
15


Table 2.3: Odir Algorithm
Eo h. Axq,
£o = ^o
-J+1 ~ % + 0ti£y> a3 ~ '
cy+i = r, aj^Py,
, (B4pv,p.)
Ej+1 ^Sy TBp~Zfp~j' aij ~ (Bp/.P^
written as a short (s + 2)-term recursion of the form given in (2.11). Instead of
computing one recursion at each step for the new direction vector, consider the
multiple recursion:
(2.12)
where pj+[ denotes the new direction vector at this step, and PJ+1., for = 2,..., t
denotes t 1 auxiliary vectors. Each recursion involves the vectors {jo^. }*=1 from the
previous step, and their products with A, {Apj_}\=l. By denoting the matrix
2*
the recursions at each step j + 1 can be written as,
Qj+i = AQjR QjS, (2.13)
where R and S are t x t matrices containing the recursion coefficients. Faber and
Manteuffel conjectured that any such recursion can be rewritten in the form (2.11),
for some s > t. However, we will show below that there are short multiple recursions
16


I
Table 2.4: Omin Algorithm
£o = A^Oi
£o = Eoi
. _ -j+1 ~ -i + a^p ai ~
Ei+x = Zj-a3APj
s,+i - ij+i-pify h
of the form (2.13) that cant be rewritten as a single short (s + 2)-term recursion
of the form (2.11). More importantly, we will show that the class of matrices for
which these recursions admit a conjugate gradient method, is wider than the class
described by Faber and Manteuffel [5].
For any matrix A, the direction vectors can be computed using a full Gram-
Schmidt process. After N steps, this may result in a dense upper Hessenberg matrix
Hjf. We note here, that given that Hs is unique. If Hu can be factored as
Hff = TffBff,
where Bu is nonsingular, B#1 is banded upper triangular, and TV is banded upper
Hessenberg, then the matrix equations (2.9) can be rewritten in the form,
AP^BJf1 =
or,
APfj * ... * = Pu * *
* * *
where the *s denote possible nonzero entries. By equating the columns in the above
17


matrix equation, we obtain an equation at each step, of the form,
si+i Pj+i = S ? *£, (2-14)
i=j-t i=j-s
In the next chapter, we will see that the unitary matrix is an example of a
matrix whose direction vectors can be computed using either a short multiple recur-
sion of the form (2.12), or a short single recursion of the form (2.14). The multiple
recursion for unitary matrices is a result from Gragg, who showed the process for
constructing an orthonormal basis simplifies for isometric operators, yielding a short
double recursion for the direction vectors. Jagels and Reichel extended these results.
By using Graggs algorithm, they showed how to construct an efficient minimal resid-
ual algorithm for unitary and shifted unitary matrices (see Section 3.3). Although
the unitary matrix is normal, it is not normal(s) for some small degree s, and thus,
no short recursion of the form (2.11) exists. By considering other recursions, we will
to extend the class of matrices for which we know a practical conjugate gradient
algorithm exists.
18


3. Unitary And Shifted Unitary Matrices
3.1 Introduction
In the previous chapter, we saw that a practical implementation of a con-
jugate gradient method depended on the construction of a B-orthogonal basis for
the Krylov subspace. If this basis can be computed with a short recursion of some
form, then an economical conjugate gradient algorithm exists.
In 1984, Faber and Manteuffel [5] determined the class of matrices for which
a B-orthogonal basis {p.JyTo fr £<*(Eo, A) could be constructed with a single (s+2)-
term recursion of the form
j
Pj+i = APj- £
iJs
This class of matrices is limited to matrices that are B-normal(s), or to matrices
with only a small number of distinct eigenvalues.
That the above recursion is not general enough to account for all possible
short recursions, became apparent in the work done by Gragg [10] on unitary ma-
trices. Gragg showed that if U is unitary, then an orthonormal basis for the Krylov
subspace can be constructed using two short recursions at each step. Jagels and Re-
ichel ([16],[17]) extended this work to obtain an economical minimal residual method
for unitary and shifted unitary matrices.
A shifted unitary matrix has the form
pU + £I, (3.1)
where U is a unitary matrix, / is the identity matrix, and p and £ are complex scalers.
It is easy to verify that these matrices are normal by noting that A A* = A* A. If
19


Aj is an eigenvalue of U, then p\j + £ is an eigenvalue of A. This means that the
eigenvalues of shifted unitary matrices lie on a circle in the complex plane. Although
unitary and shifted unitary matrices are normal matrices, they are not normal(s)
for some small degree s, and thus, a short (s + 2)-term recursion of the form (2.11)
cannot be used to construct am orthonormal basis.
The results from Gragg, Jagels and Reichel, will be extended to matrices
that are unitary with respect to any inner product, (B-, ). We conclude this chapter
by presenting another algorithm for a minimal residual method for shifted unitary
matrices.
3.2 A Short Double Recursion For Unitary Matrices
Suppose that U is an N x N unitary matrix, and d = d(r0, U) = N. It was
shown by Gragg [10] that an orthonormal basis for ICn(Lq, U) can be constructed
with two short recursions. To see this, we first consider a Gram-Schmidt process to
construct an orthonormal basis {p^}^1 for K.n{lq, U). Note that this is the same
process as given in (2.8) with B I, except the vectors are normalized to have
length 1. The recursions for the g.s may be written in matrix notation as
UPn = PnHn, (3.2)
where H# is the N x N upper Hessenberg matrix.
Since U is unitary, and by construction Pn is unitary, it follows from (3.2)
that PnHn is unitary and
{PsHff)*PifHfr = H*nHn = In,
where /jv is the N xN identity matrix. Therefore, Hn is a unitary, upper Hessenberg
matrix. A QR factorization of Hn yields
Hn = QnP-n,
20


where Qn Is N x TV unitary, and Rn is N x N upper triangular. Since Rn = Qnhh i
it follows that Rn is also unitary. Rn being unitary and upper triangular implies
that
Rn = diag(- e,fl' ),
for some 6j, j = 1, ..., N.
The upper Hessenberg structure of Hn allows for the QR factorization to
be computed efficiently using elementary unitary, or Givens matrices,
Hn = G1G2 Gn-iRni (3.3)
where,

4-1
-7i
a, 7j
iN-j-1
and 7j C, \fj\ < 1, and crj = (1 I7/I2)1/2. Since each Gj is a rank 2 correction of
the identity matrix, it follows that the information content of Hn is of order N. By
substituting (3.3) into (3.2) and equating columns, we obtain:
uBo = -TiPq +0-1^,
71 = ~{UpQ, p0),
URi = -72(o-lPo + 71PJ + a2pv
72 = -(Upv |2)1/2,
Rearranging yields the Gragg algorithm for constructing an orthonormal basis for
unitary matrices. This algorithm is given in Table 3.1.
See ([10],[16],[17]) for a more complete presentation. Another derivation of this
double recursion for unitary matrices is given by Watkins [24].
21


Table 3.1: The Gragg Algorithm for unitary matrices
5o = £o = lfil>
7i = -(^pQ. £o>.
^i = (l-|7i|2)*,
\PX = Ufy + 7iPqi
Bi = 7i+i = -(UPj, Pj)>
^j+i = (1 I7j+i|2)1/2,
j+i£j+i = C7Pi + 7j+iPi,
Hj+i = ^+iPJ+7i-fiPJ+1.
3.3 A Minimal Residual Algorithm For Shifted Unitary Matrices
Jagels and Reichel ([16],[17]) use the Gragg algorithm to construct an effi-
cient minimal residual algorithm for the solution of the linear system, Ax = b, where
A is a shifted unitary matrix (3.1). They observe that /Cjv(iio, A) = /Cjv(ro> U). Thus,
the Gragg algorithm can be used to construct an orthonormal basis for £//(ro, A).
This basis is then used to construct a minimal residual algorithm as follows:
At step k in the construction of the orthonormal basis using the Gragg
algorithm, the recursions for the basis vectors, {pt}*=0, can be written in matrix
form as
UPk = Pi+i where is the {k + 1) x k upper Hessenberg matrix,
Hg}hk = G1G2-Gk.lGk,
where for t = 1,..., k 1,
' /t-1 h-i
-7 CTi , and Gk Ik
Oi 7i
h-i-\ Gk
22


Using (3.1) and (3.4) we see that
APt = {pu+(i)Pt = n+.(pff£'u+e/*) = n+itfliU'
where,
ik =
h
oT
g Q{k+\)xk
We remark here, that instead of deriving frm Hk+ifi one could obtain
Hk+ijc directly by substituting U = ^(A £/) into the Gragg algorithm. Now,
the standard argument for constructing a GMRES algorithm (c.f.[23]) is employed.
Since HeqIIPq = lo, we have for some Cfc
Lk=ro~ APkVt = Pk+1 [llrollli Hk+\,k Kjt] >
where 6j = [1, 0, ..., 0]T. The objective is to choose to minimize llr^H- Since
Pk+1 has orthonormal columns, this may be accomplished by solving the (k + 1) x k
least squares problem
llrolld yk-
Since + Zh) = Hk+ijc ^ uPPer Hessenberg, a QR factorization of k
is accomplished by Givens matrices. The relationship between k and k
allows the least squares problem to be solved using an algorithm that involves five
short recursions. The algorithm is given in Table 3.2. We note here, that the Vj's in
this algorithm are the same as our p^.s. See ([16],[17]) for details.
23


Table 3.2: Minimal Residual Algorithm: A = pU + £/ (Jagels and Reichel)
Input: *<,, Eo = b Axq, e;
*o = IIeoII; Hi = Hi = Eo/ for m = 1,2,... until |fm+i| < £,
u = Uvm;
7m = CTm = ((1 |7m|)(l + |7ml))1/25
&m = ~7m<$ml!
rml,m Qm^m1 "b ^m1 C/Pi ^m,m + Cml C/Pi
Cm = fm,m/(|fm,m|2 + |am|2)1/2; sm = -crm/(|fm,m|2 + ItTml2)1/2;
rm,m = cmrm,m ~h
T~m fn+1 = sm^m\
Wm = 7m/r'm,mi ^^m1 = l"m l,m/rm l,m1
SHm-1 = 0£m£m_2 ~ Offim-2 -£m-l)*m-i;
PTO_1 = Pm 2 (Him2 Hml)Amli
2m ~ 2m1 ~ (Him1 Hm)Pm)
if om = 0 then x = xm; exit.
^m ~ <5mlOmi Pm = ~Cm(Pm + sm7m/^mi Am =
(Pm+1 = ~f~ Cm7m/^mi
Hm+1 = fn (H + 7mHm)i
Hm+1 = amVm + 7mHm+l >
24


3.4 Conjugate Gradient Algorithms For General
B-Unitary And Shifted Shifted B-Unitary Matrices
A matrix Ub is B-unitary, or isometric with respect to the inner product,
<£,), if
(BUbx, UBy) = (Bx, y), Vrc, y <= CN. (3.5)
Gragg [10] gave a more general result than what we presented in Section 3.2. This
result says that if a matrix UB is isometric with respect to any inner product, (B-, ),
then a B-orthonormal basis for /C^(^0, Ub) can be constructed with a short double
recursion of the form given in Table 3.1. The derivation of this recursion is similar
to that for the unitary case.
After step N of a Gram-Schmidt process which constructs a B-orthonormal
basis {p^ilo1 fr Ub) we have
UbPn PnHn> (3-6)
where Hu is an N x N upper Hessenberg matrix. Multiplying through on the left
by PffUgB yields,
P^U'bBUbPn = P'nU'bBPnHn. (3.7)
Since UB is B-unitary, UbBUb = B. Using (3.6) it follows that P^Ug = H^Pf..
Substituting these quantities into (3.7) yields
P'nBPn = H'nP*nBPnHn.
Since P^BPn = Iff by construction, it follows that Hn is /-unitary. Therefore,
Hff can be written as a product of elementary unitary matrices. Analogous to the
unitary case in Section 3.2, the substitution of this factorization for Hff into (3.6),
and equating the columns, yields the recursion formulas for the p.'s. The iteration
to produce a B-orthonormal basis is exactly like the Gragg algorithm except the
standard inner product (, ) is replaced by (B-, ). The algorithm is given in Table 3.3.
25


Table 3.3: The Gragg algorithm for isometric operators
£o = =WllrollB,
7i = -{BUbPq, Pq),
0-1 = (1 -|7l|2)*,
= UbPq + 7i£qi
£i = ^lio + liPv
7j+i = -(BUBp., pj,
j+1 = (1 ITj'+i|2)*i
CTi+iPJ+1 = uBPj + Tj+iPjt
Pi+i = aj+iPj "* 7j+iPJ+1-
From Chapter 2, we know that an algorithm for CQ(B, UB), can be obtained
as follows: Construct a B-orthonormal basis for K.n{zq,Ub) using the the algorithm
given in Table 3.3. At each step, perform the additional recursions,
(BC-yP.)
Zj+1 = % + ttjPj. = (Bej,Pj),
r.j+1 = Lj ajApj.
Notice that since the computation of the ctj's involves the unknown quantitiy of the
error, B must be chosen so that ctj is computable.
A shifted B-unitary matrix has the form
A = pUs 4- (,!
Since ICn{Lq, A) = AC/v(ro, [/#), the same B-orthonormal basis for ICn(LoiUb) can
26


be used for /Cjv(To, A). Thus a conjugate gradient method for shifted B-unitary
matrices can also be implemented with short recursions.
3.5 A New Minimal Residual Algorithm For Shifted Unitary Matrices
In this section, we present an alternative minimal residual algorithm for
shifted unitary matrices. This reformulation will motivate the development in Chap-
ter 4. First, let us restate the minimal residual method for the solution of the linear
system, Ax = b, as a conjugate gradient method CQ(B, A), with B = A* A. The
iterates produced by this method are uniquely defined by:
2lj+1 = 2y' ^jPj' Pj ^ ^/+l(£o>^)>
£7+1 -Lam £7+1(14), A).
In this context, it is clear that the direction vectors, pSs, must satisfy
Pj £ £7+1(101 A),
Pj J-A'A £7(1431 A).
Suppose that dfa, A) = N. We seek a basis, {pQ, pt, ..., PJV_1}> for £jv(Eo, A), such
that
0 i ^ j,
1 i = j.
Now, suppose that A is shifted unitary. Note that in this case £7+1(24), A) =
£3+1(143, U). Thus, it is sufficient to find an A* A orthogonal basis for £7+1 (r0, U).
Next, note that if U is unitary with respect to /, and A = pU + £/, then
(A*Apjt Pt) =
A9AU = UA*A.
(3.8)
It follows that U is A*A-unitary. In other words, U is isometric with respect to the
inner product (A*A-,-), that is,
(A'ACfe, Uy) = (UAm Ax, Uy) = (A*Ax,y), Vx, y £ CN.
27


From Section 3.4 it follows that the algorithm given in Table 3.3, with B = A* A and
Ub U, can be used to construct an AM-orthononnal basis. Given the basis
thus computed can be used to solve the linear system, Ax = b, by adding at each
step the recursions,
i+i % + ai£j ai (A'ApjiPj) ~
£i+1 = Lj-otjAp..
Note that the algorithm above requires multiplications by both U and A.
To rearrange the algorithm to one requiring only multiplication by U, define the
quantities
q. = Ap. and q. = Ap..
-3 -3 -3 3
Notice that for A = pU + £/, A and U commute. By multiplying the equations for
Pj, and Pj given in Table 3.3 by A, we obtain
*jgj = uij-i + y&j-v 311(1 ij ~ 1 + 7igj)
Also, since Ap. = pUPj + we can write
vej-fa-ty)-
Using this information we rewrite the above minimal residual algorithm for shifted
unitary matrices.
ALGORITHM 3.1 A Minimal Residual Algorithm
for Shifted Unitary Matrices:
So = So = Eo/IIeoIUm,
£o = 2o= ASo>
£i = So + QqPq, ao = (£o>
28


Li = Co - ao£o,
Ti = -<£%_!,
Oj = (1 - l7il2)1/!,
% = hWq-- -1 +Wj-i)<
Hi =
= aiij-i + Wf
Pi = aiZj-i +7i£i>
i+i = £i + aiZf ai = ^i> lj)'
Li+i = Ci ~ aiij-
This algorithm requires the storage of 7 vectors:
-v -v Zj-v Zj-v lj-v ij-v ^lj-v
The approximate cost per iteration is:
(1) 1 Matrix vector multiplication: Ug._1,
(2) 2 inner products: (e,-, g.), (Uq^q^),
(3) 7SAXPY.
The computational and storage requirements are comparable to the Jagels and Re-
ichel algorithm (Table 3.2), which requires approximately 1 matrix vector multipli-
cation, 1 inner product, 6 SAXPY, and the storage of 6 vectors.
29


Computationaly, there is no advantage over the Jagels and Reichel algo-
rithm. However, put in this context, it is clear that the direction vectors are A* A-
orthonormal. Thus, unitary, and shifted unitary matrices are examples of matri-
ces that are not A*A-normal(s), for some small degree 5, but for which an A* A-
orthonormal basis can be constructed using a short multiple recursion. Therefore,
the class of matrices for which an economical conjugate gradient algorithm exists
is wider than that given by Faber and ManteufFel [5]. This motivates the study of
alternate forms of recursions for constructing a B-orthogonal basis.
30


4. Multiple Recursion Formulation
4.1 Introduction
In Chapter 3, we saw that if a matrix A is either of the form
A = pUb + or A = Ub,
where Ub is B-unitary, then a double recursion,
"a* = Vstj-i+nij-v (41)
Pj =
can be used to construct a B-orthonormal basis for ICdfa, A). It was noted that a
short (s+2)-term recursion of the form given in (2.11) could not be used to construct
this basis since these matrices are not B-normal(s) for some small degree s. That
is, the B-adjoint of A cannot be written as
At (A), for s small.
However, notice that if A is B-unitary, A* = A~l. If Aj is an eigenvalue of A, then
jt is an eigenvalue of A\ and we obtain,
,t Po(A) I t __ Po(Aj)
qi(A) A' 3 q^y
where poip) = 1 and qi(p) = p- This motivates the exploration of a more general
class of normal matrices, whose B-adjoint can be written as a ratio of two polynomi-
als. We call this class B-normal(£, m) matrices. They are defined and characterized
in Section 4.2.
Consider the recursions in (4.1) for constructing a B-orthonormal basis. At
step ; + 1, form
*i+i Pj+l = UBPj + lj+\Py
31


For g., substitute the second equation in (4.1) to obtain
J+iPj+i = UBPj +7j+i +7j£y)-
Solving the first equation in (4.1) for Pj_v and making this substitution into the
above yields the recursion,
1
l
&j+1
UBPj ~
7j+i0j
7/0*+1

+
flj+ioj t 7j+i7j
VTj^i+i CTi+i
fir
(4.2)
Recall from Section 3.2, that the unitary and shifted B-unitary matrices, the recursions in (4.1) can be rewritten as the
above single recursion as long as the 7s are nonzero. When A = pUs + another
way of writing the single recursion follows from substituting Ub = ^(A £/), into
(4.2) yielding,
2/+i
1
Pj+1
APj ~
Z^i-Ap. y
~3
7j+ij_______f 7j-+i7jA t 7i+igj^
7,-Oj+l po-j+l (4.3)
In Section 4.3, we begin by considering general recursions of the form,
j j
Pj+1 = L PijASi H a i=j-t i=j-s
where s and t can be any integers > 0. We will refer to this type of a recursion
as a single (s, i)-recursion. The recursions given in (4.2) and (4.3) for B-unitary
and shifted B-unitary matrices are of this type. By taking t = 0, we notice that
the (5 + 2)-term recursion in (2.11) for B-normal(s) matrices is also of this form.
We can view the single (s, <)-recursion as a more general form of short recursion,
since it includes the short recurrences for B-normal(s) matrices, as well as those for
B-unitary and shifted B-unitary matrices.
32


In the absence of a condition we call breakdown, which is analogous to
the 7s being zero in (4.2) and (4.3), this section demonstrates that a single (s, t)-
recursion can be used to construct a £-orthogonal basis for ^(rg, A) when A is £-
normal(l, m). This result is then extended to more general matrices which includes
low rank perturbations of £-normal(l, m) matrices. Since breakdown is possible in
the single (s, t)-recursion, which is illustrated by an example given in Section 4.5,
we show how the computations can be reorganized as a set of multiple recursions
that avoids the problem of breakdown. Sufficient conditions on the system matrix
A are then given in order for a B-orthogonal basis to be constructed using this form
of multiple recursion.
We conclude this chapter with a brief summary, along with a few words
about the likelihood of a breakdown occuring in the single (5, ^-recursion.
4.2 £-Nonnal(l, m) Matrices
The unitary matrix was given as an example in Section 4.1 as a normal
matrix whose adjoint can be expressed as the ratio of two polynomials,
PoW I
qi(A) A'
This section considers a general class of normal matrices of this type, called B-
normal(£, m) matrices.
DEFINITION 4.1 A is B-normal(£,m) if A is B-normal and there exists
polynomials pt(\) and gm(A), of degree l and m respectively, such that
A^qm{A) =pe{A). (4.4)
Since At = £$, we say A is B-normal with rational degree l/m.
Notice that if m = 0, (4.4) becomes
Af = pi(A),
33


and A is i?-normal(£).
Next we characterize B-normal(£, m) matrices. 2?-normal(£, m) matrices
satisfy
t pi{A) aeAe + + 01A + op I
flm(A) bmAm + + &i A + bol' 1
for some polynomials,
pe(ji) = atiie + -- + aiii + ao and qm{p) = bmpm 4- + bx + 60,
of degree £ and m respectively. In the following Theorem, which characterizes B-
normal(£,m) matrices, we will assume that £ and m are the smallest degrees for
which (4.5) holds. This means that a/, bm ^ 0, and that pt(p) and qm(p) have no
common roots, since otherwise, (4.5) would hold for some smaller degrees £' and m!.
THEOREM 4.1 Let A be B-normal(£, m), where £ and m are the small-
est degrees for which
At = MdI
fai(A)*
Let d{A) be the degree of the minimal polynomial of A. Then,
(1) If £ > m + 1, then d{A) < £2,
(2) if £ = m + 1, then d(A) < P or A is 2?-normal(l, 0),
(3) if £ < m, and &o ¥= 0> then d{A) < m2 +1,
(4) if £ < m 1 and &o = then d{A) < m2,
(5) if £ = m 1 and bo = 0, then d(A) < m2, or A is B-normal(0,1),
(6) if £ = m, then d{A) < m2 + 1, or A is B-normal(l, 1).
Proof: Prom (4.5) it follows that the eigenvalues of a B-normal(£, m) matrix can be
written as:
A = ^TT> VAf E E(A). (4.6)
34


We assume that pt(Xi) # 0, VA,- G E(A), since otherwise, (4.6) would imply that
A* = 0 and A is singular. We further assume that 9m(A,-) ^ 0, VA,- E(A), since
9m(At) = 0 and p/(A,) ^ 0 for some A,- G E(A) would imply that A,- = oo. Taking
conjugates in (4.6) yields
A =
Pt(*i) ^(jli$&)
*m(A,) ** (SM)
VAi 6 E(A).
This can be expanded into
_ +s<-i(^i) +'"+a
---5----^---------------
Ai = r
ms)
, (£dL\
+bo
_ (qm(At))m a<(pf(At))<+af-i(pf(At))<~'1gm(At)+-+ao(qm(A1-))^
W(A i)) 6m(p<(A,))"+6m-i(p<(A,))'n-1gm(Ai)+-..+6o(?m(Al))'"
VA,- G E(A). Cross multiplication and collection of terms on one side yields
A(9m(A,))< [6m(p<(A,))m + 6m-l(Pf(A,))m-lgm(At) + + 6o(gm(A,))m]
-(9m(At))m [oe(p(A,-))^ + a<-i(p<(A,))f-1gm(A,) + 4- ao(<7m(A,-))*] = 0,
VA, G E(A).
First, consider the case when A is B-normal(l!, m) with l > m. Since
9m(At) 7^ 0, VA,- G E(A), we can divide (4.7) by (9m(At))m. It follows that the
polynomial
P(Qm(ji))e~m [*m(P£(p))m + + + bo(9m(p))m]
(4.8)
-ae{pt(fi))e at-iiptifi))*'1 qm(n)------SofanOO)* = 0,
whenever p = A,-, and A,- G E(A).
Proof of 1): If £ > m + 1 and m = 0, A is B-normal(^). In [5] it was shown
that these matrices have less that or equal to l2 distinct eigenvalues. Therefore,
d{A) < e.
35


If l > m +1 and m > 0, the highest degree term of the polynomial in (4.8)
is
with degree l2. By hypothesis, a* ^ 0, which implies (4.8) has at most l2 distinct
roots. Thus, Proof of 2): If f = m + 1 and m 0, A is B-normal(l). It was shown in [5] that
the eigenvalues of these matrices are collinear, that is, they lie on a straight line in
the complex plane.
If £ = m +1 and m > 0, the highest degree term of the polynomial in (4.8)
is
with degree f2. Either the polynomial has at most i2 distinct roots, or (4.8) holds
for all fi. In particular, (4.8) holds for the roots of qm(fi), say fij, for j = l,...,m.
Plugging fij into (4.8) yields
at(pi{fij)Y = 0, for j = 1,..., m.
This means that either at = 0 or pt(jij) = 0, for j = 1,..., m, or both are zero. By
hypothesis, at ^ 0 and pt{p) and qm(p) have no common roots, so it follows that
(4.8) cannot hold for all p, thus d(A) < f2.
Next, consider the case when A is B-normal(£,m), with l < m. Since
qm(Xi) 7^ 0, VAi 2(A), we can divide (4.7) by (<7m(At-))*. We obtain the polynomial
fi [6m(p*M)m + 6m-i(p/(/i))m_19m(/i) + + M9m(p))m] ,,
(4.9)
-(9m(p))m_< [a*(p(A*))* + at^iptiriy-'qmifi) + + a0(9m(/i))*] = 0,
whenever p = A,-, and At- 2(A). Since p/(A) and qm(X) are polynomials of degree
l and m respectively, at and bm are nonzero. However, it is possible that any of the
other coefficients, ao, ...,a*_i and 6q, ..., 6m_i, could be zero.
36


Proof of 3): If £ < m and &o # 0, the highest degree term of the polynomial in (4.9)
is
60p(6mpm)m,
with degree m2 4- I. By hypothesis, fro, ^^0, and it follows that d(A) < m2 +1.
Proof of 4): Suppose that £ < m 1 and fro = 0. We assume that ao ^ 0, for
otherwise we could could factor p out of both pe(p) and qm(p)i showing that A is
really £?-normal (£ l,m 1). The highest degree term of the polynomial in (4.9) is
O0(frm/im)m-'(frmAim)< = 50(frm/im)m,
with degree m2. By hypothesis, ao, frm # 0, and it follows that (4.9) cannot be zero
for all p, thus, d(A) < m2.
Proof of 5): Suppose that £ = m 1 and fro = 0. We assume that ao # 0, since
otherwise this would imply that A is £-normal(£ I, m 1). There are 2 possibilities
to consider, £ > 0 and £ = 0.
If £ > 0, then m > 1 and it is possible for fri to be zero. If fri = 0, the
highest degree term of the polynomial in (4.9) is
So (frmAim)m~ W"1)* = 0(frmOm,
with degree m2. Since ao and 6m are nonzero by hypothesis, it follows that the
polynomial has at most m2 distinct roots, thus d(A) < m2. If fri ^ 0, the highest
degree term of the polynomial in (4.9) is
friA*(&mOm-1(a^) ~ So(frmAm)mi
with degree m2. Again, either d(A) < m2, or (4.9) holds for all p. In particular, it
must hold for the roots of p/(/x), say fij> for j = 1, ...,£. Plugging pj, for j = 1, ...,£
into (4.9) yields
So(?m(Ai))m = i J = 1* -i *
37


To satisfy (4.9) for all fi, requires that either ao = 0, or gm(/fj) = 0, for j = 1,I, or
both are zero. By hypothesis, ao ^ 0, and and qm{p) have no common roots,
thus, d(A) < m2.
If £ = 0, then m = 1, and it follows by hypothesis that bm = b\ # 0, at =
ao ^ 0, and 6o = 0. These matrices are B-normaI(0,1), where in addition, ho = 0.
Therefore, po(p) = ao and qm(p) = but, and it follows that (4.6) becomes
At = VA, S(A),
hi A,
or,
AjA,- = VA, 6 £(A).
o1
Therefore, must be positive and real. Matrices that are B-normaI(0,1), with
6o = 0, have eigenvalues that lie on a circle of radius That is, they are scaled
unitary matrices.
Proof of 6): When A is B-normal(£, m) with £ = m, (4.5) becomes
if Pm{A) Am Pm1 (A)
where the second equality follows upon division of pm(A) by qm{A). Denoting A =
(A £J), where £ the above can be rearranged yielding
_ Pm-l(A) Pm-l(A)
This shows that if A is B-normal(m, m), then there exists a constant C, such
that A £/ is B-normal(m l,m). We apply the results from the £ < m case to
the matrix A. It follows that if A is B-normal(m,m), the only cases that yield more
that m2 + 1 distinct eigenvalues are B-normal(l, 1) matrices whose eigenvalues can
be obtained by shifting the eigenvalues of a scaled unitary matrix by some constant
£. These are the shifted unitary matrices described in Section 2.
38


The above Theorem shows that if A is B-normal(£, m) and either £ or m
are greater than one, then A has a relatively small number of distinct eigenvalues.
Furthermore, from the proof, we see that if £, m < 1, the only matrices that have
more than 2 distinct eigenvalues sue B-normal(l), B-unitary, and shifted B-unitary
matrices.
4.3 A Multiple Recursion For B-Normal(l, m) Matrices
In this section, we will begin by considering general recursions of the form,
where s and t can be any integers > 0. We refer to this as a single (s, t)-recursion.
Related work involving alternate forms of short recursions can be found in
([31, [4], [11], and [13]). The work in ([3] and [4]) is based upon a generalized Krylov
subspace. The vectors that span this subspace involve powers of both A and A*. The
methods studied in [13] differ from the work in this thesis in that these methods are
not conjugate gradient-like methods (see Chapter 2). The work in [11] relates to the
work in this thesis because conjugate gradient methods can be viewed as operator
coefficient methods.
At each step in the (s, £)-iteration, the term PjjA^ brings the recursion
up to the next higher dimension Krylov subspace yielding 2.j+\ E £j+2(Eo,A). I*1
order for the above recursion to yield a B-orthogonal basis, 0jj ^ 0 for every j.
Since fyj is usually a normalization constant, for simplicity of this presentation, we
will assume to =1 for every j, and denote the single (s, t)-recursion as,
(4.10)
where s and t can be any integers > 0. Notice that, g.+1 can always be computed
39


by a recursion of the form
Pj+x = ARj + 5Z fojApk-'52aijPv
k=j-t t=0
because, given any PJ+1 can be constructed so it is B-orthogonal to
sp{p, Pj} by choosing
j-i
(Ap + £ PkjAPuiP^B
k=zjt
*ij = 7~ ~T * = 0,j.
(2i P)b
However, we are interested in determining when a S-orthogonal basis for IC^lxo, A)
can be constructed using a short recursion of the form (4.10), that is, with both s
and t small. Notice that in order for this to be the case, at each step, j +1, cr, j = 0,
for t = 0,...,/ s 1.
To be more precise, we say that a B-orthogonal basis for IC^Lq, A) can be
constructed using the single (s, t)-recursion (4.10) if for every and every 0 < j <
d(pQ, A) 2, there exists coefficients such that
j-i
(Apj+ £ PkjAp^, pJB
&ij =---------~7J~t 7--------=0, for t = 0,..., j s 1,
(Pt-> P,)b
or equivalently,
j-1
{p. + 53 A*p.)b = o, for t = 0,...,j -s- 1. (4.11)
k=j-t
Suppose A is B-normal (£, m). According to Definition 4.1, there exists
polynomials p*(p) and qm(p), of degrees £ and m respectively, such that
,t = Pt(A)
9m (A)
Since for every i, p. G ICi+i (p, A), p. can be written as r/>,-(A)p_, for some polynomial
ipi of exact degree t. There exists polynomials, and r^_j such that
p. = ^.(A)^ = gm(A)^i_m(A)p0 + rJJ.itAJpjj,
40


where the second equality follows upon division of by qm[p), resulting in a
quotient term, and a remainder term, r^Li(-<4). Since by hypothesis,
A*qm(A) = pt(A), it follows that
^Pi = ^qm(A)rpi^m(A)p0 + Air^_l{A)p0
= + AtrjZli (AJPq.
Recall that in order for an (s, t)-recursion of the form (4.10) to yield a B-orthogonal
basis, at each step j + 1, there must exist coefficients {0kj}k^j-t satisfying (4.11).
By letting (s, t) = {£, m) in (4.11), and then substituting in the expression for A^p.
given in (4.12), it follows that for = 0,...,/ £ 1, we must satisfy
iPj + ]£ PkjSt' Pt{A)i>i-m(A)pfl + 4tr^_1(j4.)pQ)B = 0.
k=jm
Since r^_x (A) is a polynomial of degree < m 1,
rm-i(^)£o 6sP(Po> A£o> = sp^Eo -> &-!>
and thus,
A'rm-i(a)£o 6 sp{Atp0, A'pv ..., A*pm_x}.
For t = 0,..., j £ 1,
PeiAtyi-miA)^ sp^, pv ...,
By orthogonality, sp^, pv P^.J is B-orthogonal to sp{p._m, ..., p.}, and it
follows that we only need to choose {/3fcj}xI.*_m so that
J'-1 ...
(Pj+ 12 0kjPk,Atr%_1(A)pQ)B = O, fort = 0,...,/-£-l.
fc=jm
This can be accomplished by choosing {Pkj}k=j-m to satisfy
(e,-i>At£o>B ft-mj ( o\
0J-1J K 1 ) 0 < 0 /
41


or equivalently, to satisfy
*
<£,_!>At £>
. Af£,_>* - -
ft-
. \
mj
V ft-xj /
A <£,> A^s \
. (4.13)
If the above system is consistent at every step, then an (s, £)-recursion, with (s, t) =
(l, m) can be used to construct a B-orthogonal basis for B-normal(l, m) matrices.
We say that a breakdown occurs in the single (s, f)-recursion if the above
system becomes inconsistent at some step in the iteration. If this happens, the
matrix in (4.13) is singular. Recall the matrix equation (2.10) obtained after a given
step in the iteration using a full Gram-Schmidt process to construct a B-orthogonal
basis. After constructing p^., this is given by,
APj = Pj+iHj+ij-
Notice that the matrix in (4.13) corresponds to the upper right m x m corner of the
Hessenberg matrix Hj+ij- We can correlate breakdown in the single (s, t)-recursion
to the singularity of a minor of the Hessenberg matrix. We will discuss the likelihood
of these matrices being singular in Chapter 6, since this will become important later
in our analysis.
For now, we note that in the absence of breakdown, an (s, t)- recursion,
with (s, t) = (£, m), can be applied to any B-normal(£, m) matrix. However, in
order for this construction to be economical, i and m must not be too large.
Next, we will show how to reformulate this iteration in terms of multiple
recursions to avoid the problem of breakdown. Suppose ^(Pq, A) = IV, and recall that
for any matrix A, a B-orthogonal basis can always be computed with a full recursion
given by (2.8). After N steps we obtain the corresponding matrix equation (2.9),
42


I
where Hu is an upper Hessenberg matrix, with entries:
hu = '
(p pa%)b if j > t
i, if j = i
0, if j (4.14)
Consider the upper triangular part of Htt- Substituting the expression for A^p. given
in (4.12) into yields

i-m(A)p + {A)pJb
= -J------------7t-----------------, for j > i.
Note that
sp{pQ, Ap^, .... A,'-m+ so that for j >i m + t, p. Lb p/(A)t/>i_m(A)p0, and
(gj. (A)p0)g (Ap., r^)_1(A)p0)B
(gt-,Pi>B
Since rJJ.^A)^, 6 sp^, px, ..., p^}, we can write
Ji)
*ij =
rm1 (^)P0 = (P*)m-1 Em-1 + *' + <£> SO
for some vector of coefficients,
£i ~ [(P,-)o> > (P,)m-i]T G Cm
Denote
and note that
(Ap-, (Ap., Pn^B + + (^)o(A£J1 P^B
= (Vp Pt>-
(4.15)
Zj = MPy. Po>B. (APj., P1)bi .... MPy. Pm_i)B]T e CT71, (4.16)
43


It follows that the entries of Hu simplify, yielding:
hid
(Ap^pJb
1
0
j > max{t 1, t m +£}
j = t,i m + £ (if l > m)
j = i- 1
/<*- 1
Consider the following decomposition of the Hessenberg matrix Hu-
Hn = T + U,
where U is an N x N upper triangular matrix whose entries are given by:
3>*
j and T is N x N upper Hessenberg with entries given by:
0
Mg
<£,£>
1
0
j > max{t 1, t m + £}
j = t,i m + l (if £ > m)
j = t 1
j < t 1
Notice that T has an upper bandwidth of max{0, £ m + 1}, so that if m > £, T
has only a nonzero subdiagonal consisting of all ones. This way of decomposing Hu
yields a banded Hessenberg matrix T, and an upper triangular matrix U, that can
(Eo'Eo')*
<3*-!&>
be factored as follows:
<£o>£o>a
17 =
J=ii=iL
(Un-iEn-i)
(En-i'2.n-0b -
44


# £ fiT £o
b 5
{£1>£1)b
fiT
\ n
r ,r 1
£n B 7m
pt Hn-1
^£v-i£w-i^b .
lil
U.N-1
'-IQ
-lN-\ J
= MED.
The dimensions of the above matrices are given by:
M is N x (JV x m),
E is (JV x m) x (JV x m), and
D is (N x m) x JV.
The matrix £7 consists of the blocks Im, on and above the diagonal, where each Im
is an m x m identity matrix. Combining this information, we obtain
APn = PnHn
= PnT + PnU
= PnT + PnMED.
Define
Q = PnME.
Notice that QisaniVx(jVxm) matrix. In particular, we denote
I I I I I
(4.17)
(4.18)
Q =
% 2om-i 2i0 ii^, In-i0 "
Substituting Q into (4.17) yields,
APn PjvT + QD.
45


I
Notice that the matrix B, being upper triangular with all ls on the diag-
onal, is nonsingular. It is easily verified that the inverse of E is given by the upper
triangular, banded matrix,
B~l =
1
-1
1
-1
1
An "Ai
An An
An An
An
(4.19)
with ls on the diagonal, and ls on the m 4* lst superdiagonal.
By multiplying (4.18) on the right by E~y, we obtain
QE~l = PffM.
When A is B-normal(£,m), the equations
APn = PnT + QD,
QE~l = PffM,
define the matrix form of a set of multiple recursions to construct a B-orthogonal
basis. By equating the columns in the two equations in (4.20), we obtain the formulas
for the recursions at each step of the iteration. These are given by:
(4.21)
(4.20)
J+i = Ap ~ £ tijSi~ [JO -J1 -Jm-l] J
*#+h _ -J+1 +-Ji for i = 0, ...,m 1,
where p_. and are specified in (4.16) and (4.15), and the Ujs denote elements of the
Hessenberg matrix T. Notice that these quantities may be zero, but stay bounded.
Therefore, the problem with breakdown in the corresponding single (s, t)-recursion
is avoided. More will be said in the next chapter about the computation of these
quantities.
46


The following Theorem summarizes these results.
THEOREM 4.2 If A is £-normal(l, m), then for every £q, a B-orthogonal
basis for ICd(£oi A) can be constructed using the multiple recursion given in (4.21).
Proof: See above discussion.
Recall that if breakdown in the single (s, i)-recursion occurs at step j +1,
the matrix given in (4.13) is singular. Using (4.16), this matrix can be rewritten as:
'I I
Vm Vi (4-22)
L I I J
4.4 A Multiple Recursion For Generalizations
Of B-Normal(£, m) Matrices
Next, we will see that a short single (s, t)-recursion and a similar set of
multiple recursions can actually be applied to more general matrices. When A is
£-normal (£, m), there exists polynomials pi(p) and qmM satisfying
At9m(A) p/(A) = 0.
Suppose instead that these polynomials satisfy
Afgm(A) pe{A) = Qb(A), where, Rank(QB(A)) = k. (4.23)
We refer to a matrix that satisfies this relationship as a generalization of a B-
normal(£, m) matrix.
We first consider the construction of a B-orthogonal basis using a single
(s, f)-recursion (4.10) for matrices satisfying (4.23). Recall that if a B-orthogonal
basis can be constructed using a single (s, t)-recursion, then (4.11) must be satis-
fied at each step. Analogous to the £-normal(l, m) case, there exits polynomials,
Vj, Vi-m, and rjj_i such that
Pt = MA)Pa = 9m(A)t/j,_m(A)p0 + r^L^A)^,
47


where the second equality follows from dividing the polynomial V'i(A) by qm(A).
Multiplying through by A* and then adding and subtracting p/(A)t^,_m(A)p0 yields
A'p. = [A^qm(A)-pt(A)]^m(A)p0+pt(A)rj;i^m(A)p0 + A^_1{A)pQ
= QB(A)&-m(A)g, + pi^AWi-miA)^ + AV^L^A)^.
For an (s, f)-recursion to exist, at every step, there must exist coefficients
satisfying (4.11). By substituting (4.24) into (4.11), it follows that for
t = 0, ...,j s 1, the 0's must satisfy
J-1 . _ ...
(Pj + ^2 PkjPf., QB(A)t/)i_m(A)p0 +P/(A)t/;,_m(A)p0 + Atr^)_1(A)p0)B = 0.
k=j-t
Recall that AVjL^A)^ splA^, .... A'p^}, and let {^, £v ..., £t_1} be a
basis for the range of Qg(A). It follows that
QB(A)^t_m(A)p0 = {u)k-\ + + 0&)o 0Q,
for some vector of coefficients, r,- = [(r,)o, ..., (r,),c-i]r G
By choosing s and t to satisfy
$ i>t m>K, (4.25)
we have for t = 0,..., j s 1 that
t m + £ < {j s 1) m + £ = j 1 m (s t)
< j 1 m (£ m) = j 1 t,
and thus,
Pr(A)^i_m(A)p0 sp^, ..., P,-_m+/} C spJpjj, pv ..., p^J.
Therefore,
pdAWi-miA)^ B J2 PtJEkj
48


and it follows that we only need to choose the 0k j's so that for i = 0,j s 1,
i-1
(gj + £ fe> Atrm-l(A)Po + QB(A)lpi-m(A)pQ)B = o.
b=jt
This can be accomplished by choosing to satisfy
(Ey_x> At5>> (e,*At£>
AtEi>* " At£i>*
(Zj-tio)* Ce,-_i ^o>fl (e,
(Pj-t.-j)
or equivalently,
( A-u \ 0
\ 1 /
/ n \
0
V 0 /
(P,_!> A'pJb ^ <£,> A'pJb ^
AtR._,>* ( /%-* \
K ft-w j <£, &> )b
\ tej'L-J* /
(4.26)
This system has m + k equations in t unknowns. From (4.25) we see that t was
chosen so that k < t m, which means the system has t (m + k) degreees of
freedom. Up to this point, we have only specified that s and t must satisfy (4.25).
There is some flexibility in choosing s find t. To make s and t as small as possible,
yielding the most economical (s, £)-recursion, we would choose
t k + m, and s = k + £,
so the system in (4.26) is (m + k) x (m + n). If this system is nonsingular for
every step, then an (s, £)-recursion will yield a B-orthogonal basis. Notice that the
number of terms s and t depends on the rank of Qb(A), as well as the degrees of
the polynomials p*, and qm.
49


Analogous to the B-normal(£, m) case, we say that breakdown occurs in
the single (s, t)-recursion if the above system becomes inconsistent at some step in
the iteration. If this happens, the matrix in (4.26) is singular.
A derivation similar to that used in the B-normal(f, m) case, yields another
way of constructing a B-orthogonal basis for matrices of this form. This formula-
tion also involves several short recursions at each step, and avoids the possibility of
breakdown.
Suppose d^, A) = N. Recall that a B-orthogonal basis could be computed
using a Gram-Schmidt process (2.8) which yields at step N the corresponding matrix
equation (2.9). The Hessenberg matrix Hs has entries given by:

hij = -
1,
0,
if j > i
if j = t 1
if j < i 1
(4.27)
Consider the upper triangular part of Hn- Substituting in the expression for A^.
given in (4.24) yields,
ipjiQB{A)ipi^m(A)p{i+pi{A)^i-m(A)p0 + Air^l{A)pQ}B
^ ~ SI> '
Sincep/(A)^t_m(A)p0 Gsp^,glt ..., for j>i-m + £,
Pj -Lb Pr(A)V,t-m(A)p0,
and,
_ (gj, QB(A)^t_m(A)p0 + Atr^)_1(A)g0)g
(&. Pi)B
id =
Since r^L^A)^ G spfg,,, pv ..., p^}, we can write,
rm-M)Pjo = (fif)m-l £m_! + + (&)0 Pq,
50


for some vector of coefficients,
£i = [(&)o, i (£,-)m-i]T Cm.
Next, by denoting
Rj = P£y Pq)bi iAPv Px>b, (Apf Pm_l)B]T CT",
we obtain
fey. AV^)_i(>1)p0)b = MPj. ^)_1(^)p0)b
= (^Jm-l^Pj-, Pm_!>B + + (p^ofy^., Pq)b
= (%&)
Let {^j, <£j, ..., ^c_1} be a basis for the range of Qb(A). It follows that
= (r,)0 ^ + + (Zt)/c-i
for some vector
U = [Cr,-)o> ^ C".
Denote
My ~ [(Py ^o)b, (py, ^j)b, (Py, e £*
It follows that we can write
(£y, QB(A)Vf_m(>l)P0) = (/£y, Xi)-
Therefore, the entries of Hpf simplify as:
hid = '
<2,. £,)+<£,.x<)
1
0
V
j > max{; 1, t m + £}
j = t,..., i m + t (if £ > m)
j = i-l
j < i 1
(4.28)
(4.29)
(4.30)
(4.31)
51


Let
u>, = I ~3
3
, and v, =
1
£1
<&> &)b

\a /
(4.32)
be vectors of length m + k, and notice that
+ (/£,) Zi>
Consider the following decomposition of the Hessenberg matrix
Hn = T + U,
where,
(jo. 2o)
C/ =
and T is upper Hessenberg with entries,
o)
J
(yiAf-ii v.n-\)
J

0
M£,~ ,g,.)a-(5t- £,)- <£,->£,>b
1
0
j > max{: 1, t m + £}
j = t,..., t m 4- £ (if £ > m)
j = t 1
j < i 1
(4.33)
Notice that T has an upper bandwidth of max{0, l m + 1}, so that if m > £, T
has only a nonzero subdiagonal consisting of all ones. The matrix U can be further
decomposed as
U = UX+ U2,
where,
[ B <£oEo>B i 1
Ux = II £ . I
1 1 % > /v-i)
(Eat-i'Ejv-i)
52


I
Analogous to the 5-normal (£, m) case, the matrices U\ and U2 can be
factored as follows:
Ux =
&
aT
i
f"m "' fir
Rn-
X J
= MED,
and
U2 =
In
fT
-N-l
Qbv-i'Rn-i^b
Ho
B.N-1
= MED.
The dimensions of the matrices in the factorizations are as follows:
M is N x (N x m), M is N x (N x k),
5 is (Nxm)x(Nxm), E is {N x k) x (AT x k),
D is (N x m) x N, D is (N x k) x N.
The matrices 5 (E), consist of the blocks Im (/*), on and above the diagonal. Each
block Tm (Tic) is and m x m (k x k) identity matrix. Notice that E and E are both
nonsingular. Except for the size, the structure of E~l and 5-1, are the same as
that given for the 5-normal(£, m) case in (4.19). They both have ls on the main
diagonal, but E~l has ls on the m + lst super diagonal, whereas E~l has ls
on the k + lst superdiagonal.
Using the above factorizations for U\ and U2, we obtain the matrix equation:
APn = PnHn
= PnT 4- PnU\ + PnU2
= PffT + PfjMED + PfjMED.
53


Next, we define two matrices of auxiliary vectors:
Q = PffME, and
Q = PNME.
Making these substitutions into the above matrix equation, yields,
APN = PffT + QD + QD.
Notice that the dimensions of Q and Q are Nx(Nxm) and Nx(Nxk), respectively.
In particular, we will denote
Q =
Q =
I I I I I I
£oo ^Om-i 2i0 Him.i 2n-i0 2n-im.j
I I I I I I
2oo *' 2o_i 2i0 2i_i " 2n-i0 2-n-i^
LI II I I I
Multiplying the matrix equations for Q and Q through by E 1 and f?-1,
respectively, we obtain
QE~X = PffM, and
QE~l = PffM.
It follows that the equations,
APff = PffT + QD + QD,
QE-1 = PNM,
QE~1 = PffM,
(4.34)
define the matrix form of a set of multiple recursions that can be used to construct
a B-orthogonal basis for tCffip^, A). Equating the columns in the three matrix
equations yields the formulas for the recursions at each step of the iteration. These
54


are given by:
£j+i J = Ap 2 Uj Pi ~ [4 4-J Hi'
-i+li for i 0, ...,m 1, (4.35)
3-i+h 2i+1 + In > for t = 0,..., k 1,
where, g., and Tj are specified in (4.28-4.31), and the f,-js are the elements
of the Hessenberg matrix T. As in the B-normal(l, m) case, these quantities stay
bounded, thus, the problem of breakdown in the corresponding single (s, f)-recursion
is avoided. More will be said about the actual computation of these quantities in
the next chapter.
At each step, m + k + 1 recursions are needed. The recursion for the
direction vector P]+l involves one matrix vector multiplication with the previous
direction vector, and m + K terms involving auxiliary vectors from the previous step.
In addition, if £ > m, it requires i + m + l previous direction vectors. The m + k
recursions for the auxiliary vectors each involve only two terms. The work involved
with this implementation is dependent on the degree of the polynomials p/, and gm,
as well as the rank of Qb(A).
This result is summarized in the following Theorem:
THEOREM 4.3 If there exists polynomials, p*(A) and <7m(A), of degree
£ and m respectively, such that
Qb(A) = AtqmiA)-pe(A), and Rank(QB(A)) = , (4.36)
then, for every ro, a B-orthogonal basis for A) can be constructed using the
multiple recursions given in (4.35).
55


Proof: See above discussion.
Recall that if breakdown in the single (s, t)-recursion (4.10) occurs at step
j +1, the matrix given in (4.26) is singular. Notice from (4.29) and (4.31) that this
matrix is equivalent to
(4.37)
What type of matrices satisfy (4.36)? Suppose the matrix A has the form:
A = A + ZT,
where A is B-aormal(£, m) and ZT is a rank r matrix, that is, A is a rank r pertur-
bation of a B-normal (£, m) matrix. It follows from Definition 4.1, that
ftqm(A) pi(A) = 0.
Notice that
9m(-4) = 7m(A + zr) = am(A + Zr)m -I-----b ai(A + ZT) -b aoI-
By expanding each of these terms, we see that
7m (A) = 7m (A) -b Zfrn,
where is an accumulation of all terms involving ZT. It is easy to show that
m1
Range(Zmr) C |J ^ Range(AJ' Zr).
i=o
Each of the terms involving ZT has rank at most r. Since there are m of these terms,
the rank of Zrm < rm.
56


Similarly,
Pt(A) = pi(A + ZT) = pt(A) + Zrt,
where the rank of Zr/ < r£. Using this information, we obtain
Qb(A) = Aiqm(A) pi{A)
= (At + Z}){qm(A) + Zrm] [p,(A) + Zrl\
= [Atgm(A) pt{A)\ + A^Zm + Zrt[?m(A) + Z] Zr,
= A^Zrm + Z£[qm(A) + Zrm] Zrit
which yields
Rank(Qs(A)) < (£ + m + l)r.
To summarize, if A is a rank r perturbation of a B-normaI(£, m) matrix,
there exists polynomials, pt{A) and qm{\), of degree £ and m respectively, such that
^qm(A) pt{A) = Qb{A), and,
Rank(Qs(A)) < {£ + m + l)r.
COROLLARY 4.4 If A = A+Zr, where A is B-normal(£, m), and Zr has
rank r, then a B-orthogonal basis can be constructed using the multiple recursions
given in (4.35), where k <{£ + m + l)r.
Proof: The proof follows from Theorem 4.3 and the above discussion.
The recursions given by (4.35) could be applied to any low rank perturba-
tion of a £-normal (£, m) matrix. Since
Rank((?ff(A)) = k < (£ + m + l)r,
when r is large, k can be large, and the number of recursions, and the number of
terms needed to compute the basis increases. This means the practical application
57


of this form of recursion is limited to low rank perturbations of B-normal(l, m)
matrices.
From the previous section, we know that only certain B-normal (£, m) ma-
trices have more than a few distinct eigenvalues. Suppose A = A + Zr, where A is
B-normal(l, m) with d(A) = k, and Zr has low rank r. There exists a polynomial
Pk of degree k, such that p*(A) = 0. Notice that
pk(A + Zr) = Pk{A) + Zkr,
where the rank(2)tr) < kr. It follows that there exists a polynomial qkr+i of degree
at most (kr 4- 1), such that ?(fcr+i)(^fcr) = 0. By combining this information, we
obtain
which implies that d(A+Zr) < k2r+k. This means that any low rank perturbation of
a matrix with only a few distinct eigenvalues, still has only a few distinct eigenvalues.
Therefore, only a few cases will be of interest. These are the matrices of the form
A = A + Zr,
where A is either B-normal(l), B-unitary, or shifted B-unitary, and ZT has low rank.
4.5 Breakdown In The Single (s, £)-Recursion
The next example illustrates that breakdown can occur during the (s, t)-
iteration for B-normal(£, m) matrices. Recall that breakdown occurs in the (s, t)-
recursion for some if the system (4.13) is inconsistent at some step in the iteration.
Consider the unitary matrix
0 0 ^2 0 1 75
1 0 0 0 0
0 1 0 0 0
0 0 l 72 0 1 72
0 0 0 1 0
58


Since U is unitary with respect to the standard Euclidean inner product,
B = /, and we have
rrt u* = =
u qi{UY
By Definition 4.1, U is /-normal(0, 1). In the absence of breakdown, Section 4.3
shows an /-orthogonal basis {Pj}j-o for ICsip^, U) can be computed with the single
(0, l)-recursion,
Pj+i = UPj + Pj-ijUp^ (TjjPj, for j = 0,..., 3.
We set 0-ifi = 0. If j > 1, 0j-ij is chosen to satisfy
(UPj-v PoW-'J = 2s)'
and then (UPj + Pj-ijUPj-v Pj)
id '
Since an /-orthogonal basis is unique up to scale, the same basis can be obtained
using any other recursion that constructs an /-orthogonal basis. For example, the
full Gram-Schmidt process given by (2.8).
Let Pq = [1, 0, 0, 0, Of. By computing {Pj}^ o using (2.8), we obtain:
£i> 2y 2z'
I I I
I
(1 \ /0 \ /o \ f 0 \ ( 0 \ '
0 1 0 0 0
0 1 0 1 1 1 0 1 0
0 0 0 l/v/2 0
lo ) ^0,1 lo j l 0 ) l 1/n/2 j 4
(4.38)
59


The computation of px is identical using the (0, l)-recursion. To compute
p2, we must choose /3o,i to satisfy
(UPt, Po)fo,i = -(Upv a,)-
Since (£/pg, Pg) = {Upv Pg) = 0, /3o,i can be chosen arbitrarily. Any choice of /3o,i
will yield Pj = [0,0,1,0,0]T. Similarly, to compute Pj, we choose fa# to satisfy
{Upv PqWi,2 = ~{Up2, a,),
Since (E/gj, Pg) = 0> a^d (17p2, gg) = ^, this is impossible, and breakdown occurs
at this step. Recall from Section 4.3, that the multiple recursion given in (4.21) will
also yield the basis vectors given by (4.38), without breakdown.
4.6 Concluding Remarks
This chapter considered general (s, ^-recursions of the form (4.10). In the
absence of a condition called breakdown, a B-orthogonal basis can be constructed
using this form of recursion when the matrix A is either B-normal(£, m), or when
there exists polynomials pt and qm satisfying (4.36). Low rank perturbations of
B-normal(£, m) matrices are an example of the latter case.
Since breakdown is possible using the single (s, t)-recursion in exact arith-
metic, and near breakdown can also pose numerical problems, a multiple recur-
sion was developed that avoids the problem of breakdown. Sufficient conditions
on the matrix A were given in Theorem 4.2 and Theorem 4.3 to guarantee that a
B-orthogonal basis can be constructed using a multiple recursion for every gg.
Breakdown corresponds to the inconsistency of the systems given in (4.13)
and (4.26). In Chapter 6, we will show that these systems can be singular either for
every gg, or only for a set of initial vectors gg of measure zero. If A is B-normal(£, m),
with £, m < 1, breakdown can be limited to a set of gg of measure zero. This will
60


become important in establishing necessary conditions on the matrix A under which
a multiple recursion will yield a B-orthogonal basis for every p^.
61


. I
5. Implementation And Numerical Results
5.1 Introduction
In Theorem 4.2 and Theorem 4.3, sufficient conditions on the matrix A
were given in order that a B-orthogonal basis can be constructed using the multiple
recursions given in (4.21) and (4.35), respectively. This chapter is concerned with the
implementation of the conjugate gradient method using the above multiple recur-
sions. Numerical examples are given that compare this implementation using short
multiple recurssions to that using a full conjugate gradient iteration, (Orthodir) (see
Table 2.1).
5.2 B-Normal(£, m) Matrices
We will first consider the construction of a JB-orthogonal basis {Pj}jZo for
B-normal(^, m) matrices using the multiple recursion given by:
2j+i j = Ap £ tij Pi - k 1* £*..]
H-i, - -J+1+* for t = 0, ...,m 1.
Recall from Section 4.3, that for any k,
Uk = [(^E*> £o>S (^Ea* £i)b> > (A2k. Emi>Blr (5-2)
and,
Pj. = [(£^)o> > (P*)m l]^ Cm, (5-3)
62


is the vector of coefficients of the remainder term, r^i^AJpg, that results from
dividing, = ^(A)^, by the polynomial
9m(A) = bmAm + + &1A + &0/. (5-4)
If m < f, the coefficients, Uj, are given by
, _ ^ (& &>b
for i=j (£ m),...,j.
(5.5)
In this section, we will specify how these quantities can be computed.
The r^s are obtained directly by computing the vector of inner products.
If £ > m, we must compute Uj, for i = j (f m), This could be done directly
as specified by (5.5), but that would require storing p., for t = j (£ m),..., j, and
the computation of additional inner products. Instead, at each step, we compute
%+i =
= sJ+i_fa;4L>w£i
(5.6)
£;<+g*- fcr< = 0m-1.
It is clear that the tij's must enforce fl-orthogonality f£J+110 sP{Pj-_(*_m)i > Pj}-
This is accomplished more efficiently by computing,
.&>b
#. = -i+v
J (&, a)s
for t = j (£-m),...,j.
(5.7)
The p^s, whose components (p^),- are used in the recursions for the auxiliary
vectors, for t = 0,..., m 1, are computed recursively. We will assume that A is
S-normal(£, m), with m ^ 0, since if m = 0, there is no remainder resulting upon
division of = ^(A)^ by the constant polynomial go (A). The vectors p^ = (3, Vfc,
and the multiple recursion simplifies to the single recursion,
V- MP,- Pt)B
£;+i = where ^ = -^~g)g
j
E
<=i-<
63


for B-normal(l) matrices [5].
Given an initial vector Pg, recall that Pg and each subsequent direction
vector, Pj+V for j = 0,1,..., can be written as
£j+1 = ^+i(A)p0,
for some polynomial Vj+i of exact degree j + 1. Each auxiliary vector, being the
sum of the current direction vector and a previous auxiliary vector, can also be
expressed as a polynomial in A times pQ. Given any vector z that can be written as,
z = C(A)pg, its remainder upon division by qm{A) is a polynomial in A, with degree
at most m 1, times £g, which means it can be expressed as a linear combination
of the Pjs, for j = 0,..., m 1. We will denote this as,
rem(z) = a0Pg + + ctm_ipm_1,
and the corresponding vector of coefficients as,
rz [&0) Oil, Otm l] G C
If z is expressed as a sum of polynomials in A times Pg,
* = <{a)Pq = ft Ci (4) + + 5S C5(4)]£o,
for some polynomials £i,..., Cs> then the remainder could be obtained by dividing
the individual polynomials by qm(A) and then adding the corresponding remainder
terms. Notice that each of the recursions in (5.6) involves a sum of polynomials in
A times Pg. This yields the following formulas for obtaining the remainder terms:
m
Tem(y.j+1) = rem(-A£f) £(!?,)* rem(gii l),
i
rem(p. ) = rem(y )- £ Uj rem(p.),
rem(£y+li) = rem(£i+1) + rem(q.), for i = 0,...,m 1,
64


and the recursions for the corresponding vectors of coefficients,
aw = ^, -2
£Etti = 3/+1-. t .<£& (5-8>
t=3-(t-m)
Oj+i. = gj-fi +rgj,- rori = 0.m"1-
We note here that
Pk~T2k' Vfc
Some startup information is required to begin the recursive computation
for the £j.'s. This information can be obtained by computing the first m +1 direction
vectors {p^, pv pm} using a full Gram-Schmidt process (2.8), or some modified
version of it. This yields the corresponding matrix equation,
APm ~ Ffn+lHm+lw (5-9)
The Hessenberg matrix Hm+i)fn is formed and stored for later use in the recursive
update of the p^s. In addition to computing the direction vectors, the s and the
remainder terms (5.8) will also need to be updated during these steps for later use
in the iteration.
No computation is necessary to obtain, p^, ...,pm_1. First, Pq = Lo =
7^0(A)p(). Notice that the remainder ofj^ upon division by gm(A) is itself, rem^) =
1 Pjj, which yields,
a,=&, = [1o.--o]reC.
The auxiliary vectors and the corresponding remainder terms are computed as:
_ (£q) . (£q)-
(£oEo >Bo ^ ^Pn)B
'£0> 03'
Similarly, for j = 0,..., m 2 remQj^) = p .+1
Pq, for i = 0,
, which yields,
, m 1.
TEj+i = Pj+\ = [ - 0 1 0 Of G C"*,
65


which is a vector of all zeros, except for a 1 in the j + lst position. The auxiliary
vectors and their corresponding remainder terms can be computed using (5.6) and
(5.8).
The computation of ^ is more complicated. To facilitate this, we write the
polynomial qm(A) given in (5.4) as a linear combination of the Vfcs, for k = 0, ...,m,
Qm{A) = 7mlMA) + "-+7i^i(A)+7o^o(A)
[D1U]
= 6mXm-(------
This requires that we accumulate the polynomials, ipo, ..., t/>m, during the iteration,
where,
Pj+1 = ipj+dA)^j = [ai+1AJ+1 + ajAj + +ax A + a0/]p0-
The coefficients of ipj+\(fi) are stored in the vector of length m + 1,
PPj 11 [0i ij > ji oy+i, 0,..., 0] .
Since
A^y+^A)^ = [oy+iAJ+2 + QyAJ+1 +---------h £*1 A2 + aoA]^,
the corresponding vector of coefficients is obtained by shifting the vector cp ,+1 to
the right one place, i.e.,
cAPj^i [0) 0i > oy, oy+i, 0, ..., 0]^^.!-
Starting with = ^o(A)pQ = lpg, we obtain
srq = [i o o]£+1.
Using (2.8), we see that a recursion for the vector of coefficients for the polynomials,
ipj+1, for j = 0, ...,m 1, is given by,
j
Wj+! = cAPj ~ H cfr.
i=0
66


The vectors, cpQ,cpm, are stored in the matrix K, which has the following form:
K =
SEo Sti
a
1 * ................... *
0 1 **. :
: 0 :

Â¥
0 ................. 0 1
where the *s denote possible nonzero entries. Finally, the 7s in (5.10) can be
obtained by solving the system,
K

V7m /

\bm J
using backsubstitution.
Using this form for qm(A), it is easy to see that the remainder of upon
division by qm(A) is given by,
/ \ 7m1
remfej = P,
7l 70
7m_1 7m-0
and thus,
£m =
70 7l 7m-1
7m 7m 7m .
(5.11)
Once is computed, qm, and rgm;, for i = 0,..., m 1, can be computed according
to (5.6) and (5.8).
When j = m, we can begin the recursive update of rpj+1 = PJ+1 using
(5.8). First, notice that
rem(>lpj.)
rem(AV>j(A)p0)
rem (a [i>j-.m{A)qm{A)pJ0 + rJjLiCAJpJ)
rem {A rem(g.)).
67


Since rem^.) = (g^oSo + the matrix equation in (5.9) can be
used to write,
where,
A rem(pj) = ;%,...,p^] = fe,, --pjffm+i.m £j
= CqPq + Cl Px + CmPm,
Qj ~ [CQi Ci, ..., Cm] = ^m+l,m Pj-
Therefore,
rem(i4pj.) = rem(A vem{p^))
= co remO^)+ ci rem^j)+ 4-Cm rem^)
= <*£o+ci£i + *" + cp£rPm-i----------------fe]>
which yields
rAp. = CoPq + CiPj + + CrnP^-
When j > m, we can compute p^.+1 and the auxiliary vectors using (5.6),
and the remainder terms can be updated recursively using (5.8).
This process describes the construction of a B-orthogonal basis for B-
normaI(l, m) matrices. To obtain a conjugate gradient algorithm for CQ(B, A), at
each step, we compute the additional recursions:
*J+i = Xj + ajp., = 75^7,
(5.12)
Lj+i = Tj-ajAp..
For clarity of the order of computations, we outline the algorithm below.
ALGORITHM 5.1 CG algorithm for B-normal(£, m) matrices:
Imput: A, xq, Tj) = 6 Axq, coefficients of gm(A) = 0 = [6m,..., 6o]T.
Po=^
^0 = [1 0 0]£+i, Po = [1 0 0]£,
68


69
lVH3(
.(;5-fsg> _
(dl!Sg)
ddJdg) _
(d-*8)
-l-VI - 0 = !fe+ x+f3 = W?u
-l3 (tU 3 'f x+fin = l+f3 1 >(f5)T3 fdyl = l+;/EZ
r
,UV* + + dtb = -dyjL l fd UiI+ta# = %
= j?5 rj(1U 3 f-? l+f7i = x+f3
t_Uid IU
-fdyfxj -f2 = l+f3 l~d-X) + x = l+f3f
iu = £ JOJ
6o
l m...o = %+ ,+f? = ,,+fK
1 (?5j (d'dyg)
^dyfo c7 = t+f2
.Â¥k i+.f:
X iul'"o = * '6 +
>{ 1}
?d C+Jllt!M = !x+fs
ta
j;

r t ..... A- ] x+fo
[T^T- -5T-J -
fA# = £
X ui = £ ji
Jtfo --o I o - o] =x+f^
I U1 > f JI
-*55 3 'dV = t+f
c
lTd r>A3- cdy = x+f3
c
l'dfxj + -x = x+/x
X tii o = C JOj
.3 LilJhil *053
J(?)
.05 ( *\ X tii 0 = t


Recall from Section. 4.2 that if A is £-normal(l, m), and either £ or m is
greater than 1, then A has a relatively small number (max{£2, m2} + 1) of distinct
eigenvalues. For this reason, we are mainly interested in the cases when (£, m) <
(1, 1). Although there are already economical conjugate gradient algorithms for
these cases, we will illustrate the algorithm with an example.
First, if A is 7-normal(£, m), A*A = AA*, and
A qm (A) Pe(A) 0,
for some polynomials pi and qm of degrees £ and m, respectively. Notice that if
B = A* A,
A* = B~lA*B = A*,
and it follows that
A^qm{A)-pt{A) = 0,
and A is B-normal(£, m), with B = A*A.
Example 1: Consider the shifted unitary matrix given by,
A = 10 IT + (8+ 8i) 7.
This matrix is 7-normal(l, 1). From the above, A is also B-normal(l, 1), for B =
A*A. Thus, a minimal residual method, CQ{A*A, A), can be implemented using
Algorithm 5.1. The eigenvalues of A are plotted in Figure 5.1. In Figure 5.2, we
compare the convergence measured in the relative residual norm of Algorithm 5.1
to that obtained by using a full conjugate gradient iteration, Orthodir, given in
Table 2.1. The curves lay exactly on top of each other, as our theory predicts.
70


30
Figure 5.1: Spectrum of problem given in Example 1.
5.3 Generalizations Of £-Normal(l, m) Matrices
In Section 4.4 it was demonstrated that if polynomials, pi and qm, of degrees
l and m respectively exist so that
Qb(A) = A^qm(A) -Pi(A),
and,
Rank(Qfi(-A)) =
then a 5-orthogonaI basis could be constructed using the multiple recursion:
5;+1 = A? l I £ *v7 Pj i-(t-m) g. q. L-rJO -Jm-l ] s, [iJ0 4.J tf
<£i+i£i+i TT +2ji for t = 0,.. -,m 1, (5.13)
Uh, = <2*+.*2*+i JZRj+x + £* for t = 0,.. ..,K~ 1.
For any fc,
2* = [Mg*, Po) Bt , C4pk, (5.14)
Bk = [(&>£,>* i > (Pk, 4^. _1)a]r e c*,
71


t
I
I
i
i
i
i
Figure 5.2. Convergence of Orthodir (solid line), Algorithm 5.1 (dashed line, plotted
on top of solid line), on Example 1.
72


where the vectors {^j, form a basis for the range of Qb(A). If m < £, the
coefficients tij are given by,
_ (Apjt 2i)B ~ --------------Ml '
for = j (£ m),..., j. (5.15)
The vector
Pj. KflfcJo, > (P^)ml] C",
is the vector of coefficients of the remainder term, (A)^, that results from
dividing Pj. by qm(A), and = (t*^ + + for
some vector of coefficients,
Ifc = Krfc)o, (z*)k-i]T CK.
In this section, we will be concerned with computing a basis for the range of Qb(A),
as well as computing the tijs, and the quantities: r^, f^, p^, and r*. The order
of the computations will become important as the information needed to compute
them may not be available until some later step in the iteration.
Recall that A* = B~1A*B, so that
Qb(A) = (B-lA'B) qm(A) -pe(A).
A basis for the range of Qb(A) could be obtained by first computing Qb(A), then,
since Qb{A) is rank deficient, a basis for its range can be obtained using a QR
decomposition routine with column pivoting (see [9], pp. 233-236). The computation
of Qb{A) and a basis for its range may be very simple in some cases. For example,
if
A A + Zn
where A is /-self-adjoint, and ZT is a rank r matrix that can be written as an outer
product,
= WrVT\
73


for some N x r matrices Vr and Wr of rank r. Since A is /-self-adjoint,
This yields qm(A) = I, and pt(A) = A. Let B = A* A. Notice that
A* = B~lA*B = (A*A)~lA*A*A = A"1 A* A,
and
Qa-a(A) = A'qm(A)-pe(A)=Ai-A
= A-1 A* A A = A-1 (A* A) A
= A~l{vrw; wrv;)A.
Denote {,}_! as the linearly independent columns from the matrices Vr and Wr.
Now,
The quantities rj^ and are computed as specified by (5.14). Analogous to
the B-normal(£, m) case, the p^s can be computed recursively after the information
needed to start the recursion is available.
At any step k + 1, the recursion for the direction vector in (5.13) involves
both sets of auxiliary vectors, q.'s and q, s. Before we can compute the q. s, we
must know the vector r*. The method we will describe for computing this vector is
not possible at step k + 1, and will actually be done at a later step in the iteration.
This means that the multiple recursion (5.13) must be modified in a way that allows
the computation of the auxiliary vectors to be delayed. After describing how to
compute Tjt, we will show how this can be done. An outline of the algorithm will
then be given to clarify the order of the computations.
Range (Qa-a{A)) = sp{A li,}=1 = sp^,, ..., (5.16)
The algorithm will only require that we compute the vectors
<£o)b, ..., (p*, 0,5_1)bJ j where
(A*Apk, £.) = (Apk, A(A~lVi)) = (Ap^, ii).
(5.17)
74


1? =
Recall from the development in Section 4.4 that led to the multiple recur-
sions in (5.13), that the entries in the Hessenberg matrix Hn simplify yielding,
<*&> + <**>. + (5.18,
(Pjfc, PjjB (Pjc, PjjB
Denote
1 if m > £
m i if m < £
Notice that if j > k i?, we can compute,
ittj, rk) = (Ap., pJb (Vj, £*>
All the entries to the right of column (fc i?) in the fcth row of H# involve the same
vector Tf.. By moving to the right k places, we can obtain k equations involving tj..
At step j + 1 = k i? + /t + l, we obtain the system,
" Hi
~ Hi-
Z.j-K+1
(
1* =
(Ap^ pjs ~ (Vp £*)
\
(5.19)
< ^Ej-n+v h)B &j-K+v£*) /
for r^. For generalizations of B-normal(£, m) matrices, theory guarantees that (5.18)
holds. Thus, if we have chosen {4^, ..., ^K_1} properly, that is, if they form a basis
for the range of Qb(A), it follows that the above system is consistent.
From the above, we see that when j = k 1?, we can compute using
(5.19), and when j = k 1? + 1, we can compute fl, and so forth. Denote
9 = k 1?,
and notice that whenever j > 9, X.j-g is computable using (5.19). The auxiliary
vectors can then be computed as:
Ij-ft = for = 0, ...,m 1,
(5.20)
Ej-e+ij-e-,'
for t = 0,..., 1.
75


However, at this step, the multiple recursion in (5.13) requires us to compute
-i+i ^ **j Ei [Sjp* 5ym_i] Hj [^io ?7-i] j'
Unless 0 = 0, fj cant be computed using (5.19). Substituting in the quantities,
(£,)
it T£foi£i+*i-V fori = 0.m_1'
and
it = £/+ij-V =
from the previous step yields,
3
pj+i = APj- E tijPi-SjPj-
for some constant 8j which will be determined later. This process of substituting in
auxiliary vectors from previous steps can be repeated until we obtain:
i

7 E H 1 CrT 0 fH 1 Hi"

£j+i
= APj~ E Ei ~ s3 Pj-------------------s3-e+i Pj-e+i (5-21)
9.j-e0"lj-e m_,
2i"

Hi
where, fj_g can be computed using (5.19), and the, Qj_g. s and g._frs, can be
computed using (5.20). The tij's jure given by (5.15), and
<* = ( E (&) + E (M.-)i) for n = j 6 + 1, ...J.
<£- p)b /
At first glance, it looks like the information needed to compute the ans and the
tij's is not available. Let
j 6 + 1 if m > £
min^' (£ m), j 0 + 1} if m < i
Instead of calculating the ans and Uj's as specified, we rewrite (5.21) as,
hj+i =

(5.22)
(5.23)
3 .
Pj+i y.j+\ Xj+d p.v
76


where the Uj's must enforce 5-orthogonality of p}.+1 to sp{p^,p^.}, which yields,
(yi+vPi)B
U4 = (5-24)
The computation of the ps is the same as in the 5-normal (£, m) case when
j j
£j+i = HAS-j ~ 5Z *j £i'
i=0
where the quantity rAp. is computed the same as in the 5-normal(£, m) case. When
j > max{m, 0}, we can begin the recursive computation of all the remainder terms.
This process differs from that in the 5-normal (l, m) case in that additional recur-
sions are needed to compute the remainder terms associated with the £s. These
recursions are given by:
U!i+I =
£j+i = 12,+! £ l'j Ei
X=V
(5.25)

£2,-., = 1,- fo = 0,.
An algorithm is given below to clarify the order of the computations.
77


ALGORITHM 5.2 CG algorithm for generalizations of
£-normal(l, m) matrices:
Input: A, Xq, r, 0, -,£c_1}, 0, 2o = [l 0 ]m+l> £0 = ^ 0 " 0lm
for j = 0,0 1,
_ j _ _ p.)
£j+1 j "* aiPp Zj+l ~ ~j ajAPp aj ~ {Bp .,Pj)
if j if j < m 1
? < m 1
if j = m 1
7 = *\/3,
if j >m
Qj = Pp rAPj = CoPq + + Cmp^
3
After computing
Solve (5.19) for xo,
for j = 0,...
3Zj+i = £j + ajPji i+l = j ~
if j < m
Zj+i = Zj <*;>%,
(Se^-.p.)
aj~TSpptj7>
(BAp.,p.)
aiJ ~ (bR??>
if j < m 1
78


if j = m 1
7 = K\fr>
2j+i= [~w -2^r]m
if j > m
Zj+I = AZj [/-. 1, [i-fc
ay = Mey> £o>> (ARp Em-
Hj ~ [(Sy> (P/> iti_i)b]k>
Ej+i = Ey+1 .£ *J £,-1 = ~(Sp^r>
Cj = Hm+l,m Pp rApj = COP,, + + CmPmt
DLj+i = EdE, ~ £(2y)f ~ .§(if;)* ISy-*.,.
£i+i=r£i+i-.E Solve (5.19) for ry_ff+1,
2y-+ii = Ej-fl+i + Sj-e+i; = ->m ~ !*
Sj-o+i; = Ey-fl+i + ij-e+i-,' = K~1'
^+1+^--*+v '=0...........m
ro. = 7t-i o. ..+rd. -... t = 0..............k 1.
Suppose
A = A + Zr,
where A is /-normal(£, m), and Zr is a rank r matrix. It follows from Corollary 4.4
that there exists polynomials pi and gm, of degrees t and m, respectively, such that
A*gm(A) pi{A) = Q/(A), where,
Rank((3/(A)) < (£ + m + l)r.
Let B = A* A, and notice that
A* = B~l A* B = A~l A* A,
79


and
Qa-a(A) = A^qm(A)-pe{A)
= A-l[AV(^)-p,(A)]A
= A-lQr(A)A,
and thus
Rank(Q>lM(i4)) = Rank(Q/(A)) <(£ + m + l)r.
It follows from Theorem 4.3 that a minimal residual method, CQ{A*A, A), can be
implemented using the Algorithm 5.2.
We note here, if A is /-self-adjoint, and B = A* A, then
Qa-a(A) = A-1 [A*/ A] A
= A~l[Z Zr\A,
which is A* A skew adjoint.
One useful application of Algorithm 5.2 is on matrices that result from a
discretization of a partial differential equation that is formally self-adjoint, where
nonstandard boundary conditions are applied to a portion of the boundary. The
next example is of this type.
Example 2: Suppose
A = A + Zft
where A is the symmetric pentadiagonal matrix that results from discretizing Pois-
sons equation on the unit square with homogeneous Dirchlet boundary conditions,
-Au = /, on (0,1) x (0,1),
u = Q, on dQ,
using a 5-point difference scheme with a uniform mesh size, hx = hy = -jj. The
matrix ZT is a nonsymmetric, rank 8 matrix that was chosen to correspond to per-
turbing the boundary conditions at a few points in the 4 corners of the domain fi.
80


Note that the matrix A is /-normal(l) (self-adjoint) plus rank 8. The spectrum
is plotted in Figure 5.3. Notice that the matrix is slightly indefinite, with a few
eigenvalues off the real line.
Figure 5.3: Spectrum of matrix given in Example 2.
From Corollary 4.4, we know that there exists polynomials, pi (A) = A and
go (A) = I, such that
A*qo(A) pi(A) = A* A = Z* Zr = Qr(A), where Rank(Q/(A)) < 2r.
Algorithm 5.2 could be run on the problem using B = I, however, we note that this
would not yield a computable algorithm, since at each step we must compute,
(Bzj, Pj)
aj~ &p., Rjy
where ej denotes the error at step j (see Section 2.3). To obtain a computable
algorithm, let B = A* A. From the discussion before Example 2, it follows that
Qa'a(A) = A~lQi{A)A, where
Rank(Q,4-A(A)) < 2r.
81


Since A is /-self-adjoint, a basis for the range of Qa-a(A) could be obtained us-
ing (5.16). However, all that is necessary in the computations are the quanti-
ties, (p^, which are computed using (5.17). A minimal residual method,
CQ{A*A,A), is implemented using Algorithm 5.2. Figure 5.4 compares the con-
vergence measured in the relative residual norm using Algorithm 5.2 to that using
a full conjugate gradient iteration (Orthodir). As theory predicts, these two curves
are identical. In addition, we plot the convergence using the Odir algorithm given
in Table 2.3.
Recall that the Odir algorithm will yield the same iterates in exact arith-
metic as Orthodir, if the matrix A is B-normal(l). This would be the case if we did
not add the low rank matrix RT, and A = A.
We might consider how Algorithm 5.2 compares to other iterative methods
for nonsymmetric matrices. The quasi-minimal residual (QMR) method of Freud
and Nachtigal [7] is a method of this type. In contrast to the conjugate gradient
method, CQ(B, A) with B A* A, which minimizes the 2 norm of the residual,
QMR is based upon a quasi-minimization of the residual norm. QMR can be viewed
as a variable metric conjugate gradient method [2]. This is a conjugate gradient
method where the inner product matrix B is dependent upon the initial residual.
Regardless of how we view this method, for nonsymmetric matrices, QMR is not a
true minimal residual method. Thus, when convergence is measured in the residual
norm, QMR cannot do any better than CQ(A*A, A).
Figure 5.5 compares the convergence of CQ(A*A, A) implemented using
Algorithm 5.2 to the QMR method, on Example 2. For this problem, the number of
QMR iterations is comparable to the number of iterations used by Algorithm 5.2.
If we consider the main work involved in these two implementations, to
be the number of matrix vector multiplications, then Algorithm 5.2 produces quite
82


I
I
i
I
i
!
j
i
I
Figure 5.4. Convergence of Orthodir (solid line), Algorithm 5.2 (dashed line, plotted
on top of solid line), and Odir (dashed-dotted line), on Example 2.
83


a savings over the QMR iteration. QMR is implemented via the nonsymmetric
Lanczos method, often, using a look-ahead stategy [8]. This process generates two
sequences of vectors, and {to,-}^, such that
sp{i,Vtf} = ICn{£i, A), and
spl^,..., wN} = K.n(wi, A*).
This involves 2 matrix vector multiplications at each step. The computations in
Algorithm 5.2 can be arranged so that only 1 matrix vector multiplication is re-
quired at each step. In Figure 5.6, we compare the main work (measured in the
number of matrix vector multiplications) involved between the QMR iteration and
Algorithm 5.2, on Example 2.
84


Relative Residua)
j
i
I
i
I
I
i
Figure 5.5. Convergence of Algorithm 5.2 (solid line), and QMR (dashed line), on
Example 2.
85


Relative Residual
1
I
j
I
I
i
l
j
j
i
Figure 5.6. Work in matrix vector multiplications for Algorithm 5.2 (solid line), and
QMR (dashed line), on Example 2.
86
I


Example 3: The next example is the matrix
A = A + Zr,
where A is the shifted unitary matrix in Example 1, and Zr is a rank 2 matrix.
Figure 5.7 plots the eigenvalues of this matrix.
Figure 5.7: Spectrum of problem given in Example 3.
Again, we will take B = A*A, and run Algorithm 5.2. We compare the
convergence of Algorithm 5.2 to the Orthodir algorithm and the QMR iteration in
Figure 5.8. Note that the convergence curves of Orthodir and Algorithm 5.2 are plot-
ted on top of one another, as expected. In Figure 5.9, we compare the main work
(measured in the number of matrix vector multiplications) between Algorithm 5.2
and the QMR iteration, on the problem given in Example 3. Notice that the work
involved using the QMR iteration is more than double the amount used by Algo-
rithm 5.2.
87


Figure 5.8. Convergence of Orthodir (solid line), Algorithm 5.2 (dashed line, plotted
on top of solid line), and QMR (dashed-dotted line), on Example 3.
88


Relative Residual
I
1
I
|
i
I
i
i
Figure 5.9. Work in matrix vector multiplications of Algorithm 5.2 (solid line), and
QMR (dashed line), on Example 3.
89


5.4 Concluding Remarks
In this chapter, we presented general algorithms for implementing the con-
jugate gradient method using the multiple recursions given in (4.21) and (4.35). We
note here, that in certain special cases, these algorithms simplify. For example, if A
is self-adjoint plus low rank, the polynomial is a constant polynomial. Since no
remainder results upon division by a constant polynomial, the vector is the zero
vector. The multiple recursion involves only one set of auxiliary vectors, the q^ 's.
Only small numerical examples have been run to validate the theory. No
attempt has been made to analyze the effect of numerical round off on the iteration.
It may be possible in some cases, for example, if A is self-adjoint plus low rank, to
extend the analysis done by Greenbaum ([12]).
90


6. Necessary Conditions
6.1 Introduction
In this chapter, we will be concerned with determining necessary conditions
on the matrix A required for multiple recursions of the form introduced in Chapter 4,
to yield a £?-orthogonaI basis for K&fo, A), for every r^. This is a difficult problem,
and we will confine our analysis to a few special cases of recursions of this form.
Sufficient conditions on the matrix A have already been established for
multiple recursions of the forms given in (4.21) and (4.35). These conditions are for
A to be either B-normaI(£, m), or a generalization of a B-normal(£, m) matrix (see
Section 4.4). We recall that for these matrices, in the absence of breakdown, a single
(s, t)-recursion could also be used to construct this basis.
Since the tools we will use in this analysis are based upon the single (s, t)-
recursion, we will begin the next section with some results pertaining to the likelihood
of a breakdown occuring at some step in the (s, f)-iteration.
Based upon the formulation of the multiple recursions in Chapter 4, for
B-normal(£, m) and generalizations of B-normal(£, m) matrices, we will define a
general form of multiple recursion. The relationship between breakdown in the
single (s, f)-recursion and the corresponding multiple recursion will be discussed.
In particular, it will be shown that for a restricted subset of multiple recursions of
this form, breakdown in the corresponding single (s, t)-recursion can be limited to a
set of initial vectors of measure zero in CN. These are the multiple recursions that
will be analyzed in this chapter. After developing some tools to use in this analysis,
the remainder of the chapter will contain the main proof establishing necessary
91


conditions.
6.2 Preliminaries
We begin with some preliminary material that will be used throughout this
chapter.
LEMMA 6.1 If p is a complex nonzero multivariate polynomial, then
p(xi, ...,xjv) 0 for almost every a = [xi, ...,xw]T G CN.
Proof: The proof can be found in [20].
In other words, this lemma says that if a polynomial is not the zero polynomial, then
the set of x £ CN for which the polynomial can be zero, is a set of measure zero in
CN.
Consider the multivariate rational function
/(*i.
. p(Xj,..., Xfj )
N) q(xi,...,xNy
Notice that if / is finite anywhere, then q cannot be the zero polynomial, and it
follows that / is finite almost everywhere. Farther, if / is finite, it can either be zero
on a set of vectors x CN of measure zero, or it can be identically zero.
Given an initial vector pg, recall that an ascending B-orthogonal basis
{Pj}jZo fr £(i(Po,-A) is unique up to scale. In some cases, this basis may be com-
puted with some form of a short recursion. The same basis can always be computed
using a full Gram-Schmidt process generalized to the B-inner product (2.8).
In [5], Faber and Manteuffel proved that fort < d(A), that p. is a continuous
function of Pg, and that
ll&ll < Mil llHi-ill-
92


A similar line of proof can be used to show each component of is a bounded
rational function of the components of p^.
LEMMA 6.2 Suppose^, is computed as in (2.8). Let p^ = [zlt ...,zw]T,
where Zj 6 C. Then for all i < d(A), each component, {p^j of p. is a bounded
rational function of (zi,...,zn).
Proof: Bach component of p^, being a linear function of its real and imaginary
parts, is rational. Next, consider the computation for pv
(a£o> 2d)b
-l = A&~ Palis20'
Denoting the (j, fc)th element of the matrix A as (a + bi)^*, we see that the jth
component of Ap^ is given by
N
(4Po); = 'H(a + bi)j,k zk-
k=l
This is a first degree polynomial in the components of £0. It follows that the inner
products, (A£0,£0)b and (PqiPq)bi are each the sum of terms involving the products
of two first degree polynomials, yielding second degree polynomials in (zi,..., z^). By
combining this information it follows that the jth component of px can be written
as,
~ ~w( r
?2 i-,^)
for some polynomials and of degrees three and two, respectively. FVom the
proof in [5], we know that (px)j is finite.
Suppose that for i < d(A), and that, for £ < :, # 0 and
Ji) mg)(z1,...,zy)
Pi ~ {j). . >
for some polynomials and of degrees t( and S(, respectively. Consider
2i+i
= ARi ~ Z 2i
t=o
93


The jth component of Ap. is given by,
(A2i)j = H( + w)jVk (£i)k
k=l
V*fa I mti\zU>zN)
Since this is a sum of bounded rational functions, it is also bounded and rationed.
Notice that inner products of the form (Ap^ pj b and (p^, p^)b are bounded and
rational since they involve sums and products of bounded rational functions. The
terms for £ = 0,..., t, are quotients of rational functions, thus ratio-
nal. Since p^ ^ Q, and B is Hermitian positive definite, (p^g^s # 0, and it follows
that the terms o*it- are also bounded. Therefore, the jth component of p^,
(&+i)j = (&)*
/=o
involves sums and products of bounded rational functions, yielding a bounded ratio-
nal function.
Suppose that A is B-normal(£, m), or a generalization of a i?-normal(£, m)
matrix (see Sections 4.3 and 4.4). In Chapter 4, we saw that a single (s, t)-recursion
could be used to construct a B-orthogonal basis for A), if the corresponding
systems given in (4.13) and (4.26) were consistent at each step. We note here, that
the elements of the system matrices in (4.13) and (4.26) Me of the form,
(*i(Po), *2(Po)),
where t\ and <2 are bounded rational functions of p. Since these inner products
-U
involve sums and products of bounded rational functions, they are bounded and
rational. The determinant of a matrix involves sums and products its elements.
Thus, the determinants of the matrices in (4.13) and (4.26) are bounded rational
functions of the components of p^. From the discussion following Lemma 6.1 we see
94


Full Text

PAGE 1

? +@**4$&4&A,*0&4#B$* B6$C*4*,&C#:4B:,&6#@+@* 6*0#6:&4: @ :0:#"9/<< :#"0C"9//> $ #"0C" C+ $ 9//

PAGE 2

C+ @ D@ +A :A0! A6

PAGE 3

@'+C$( &0EB #:6 +$ $ :6$0 "" $F $D E'0B(G H"DG "" 0BA E!G 0B "E $""" ": $

PAGE 4

0B& I )'J E $ $!2)'J($ )E! 0B 0B" KG :L $

PAGE 5

0&4*4: 0 99 99 "$&%9 9>47 >0EB= >9= >>C"&0EB= >2/ >7*0EB$92 2#$:#9/ 299/ 2>$:C6A#>3 22$6$A:#>> 270EB$AB )#$:: )#>= 2=$46$A:#>< 76A29 7929 7> )4'J(22 72$6A )4'J(2/ 77$6AB% & )4'(7< 7= !:'()6=8

PAGE 6

7-06!-3 =$46-> =9-> => J)4'J(-> =2B%&:)4'J(<9 =706!/3 40/9 -9/9 ->+/> -2+&4099> <0977 $ $+&C976978

PAGE 7

$E F H" )% ':>>($E" )M(F;0EN'$( 0EN0$(FM $O H" 9 P&&& B6*: )G E9/87A Q=R"E > () E JE)F )'( 9

PAGE 8

"':>7(G !BQ93R 'N > () "B :" 6'Q9-RQ9ED $"""!G E"02%! B6 G 'J() ) F NJ J 9F3S F9 F9D E # F $

PAGE 9

#%& T U<9'$(K '$(F;'$(F '() 07% )'J( )E # :>7( /'$(K "! $ )'( ) '()' F )'L($ )E! :!'() "G !: ) 0= 4" E ) 0 2

PAGE 10

"$"0< A" % <>. ( TVT <>.W0TV ) VT&<>. $2 % #6'B!( T#6'B!(" ;XT@6'B!( 'YZW(Y[* ( + )Y(\\Y\\T + T ( +% I@T6 +% $WT*E$$WF$ $WT + TE$$F +&#+ M]EOT" *'$(T:$ )-. $(TM^$$W) 9 OH" '* % C '$(TC$ 7

PAGE 11

!" # 0 '>9( / B > 9 (E $!"G E"4 & E $"" ""D E !" E $ % !" # B"' > 9 (" 'LOF & 0" F39 =

PAGE 12

, F N=>'>)>L _F3 JF )$LF T(F$'>2( JYW '>>( '>2( N 9 L W9 E$E F3 @ F F+'$( '3(F9: F3E)F+'$('3(F9 !& C !01 9 '$( 3 F3 & 2-# F 34 N'(FQ9T+E'(RUEN9A N'3(F 9 4 7)9 F)N'$(3 '(!: $"

PAGE 13

C N(KH" 56 7 '*$(FM$EE 89 '>=( "M$` LOLI3 H"" C 1 1 FM P'$( 3O C 1 F 1. H" . 1 F 1. FM :. F3O :H"" 5 F 54 B LN'$(' > > ( JSN9 FJN+E'$(* F () ; B +,)-."/0/ +")1&"23" BJEN'*$(D!P $ >9$H"" P & < ; 4")-110/ aN9F+N'$(+'3(F9 H"D ; 9 93 : '>9( ; BJN'$( <

PAGE 14

,"! "!$ :\\JN\\F\\N'$(J\\U\\EN'$(\\\\J\\ !P '9(!\\N'$(\\ > (!N0$(L?? "" 0")!!$ %EG !% %4! $E%G H"%" D, + 4+ C*A4&4>>$E 4+ H" P 5ENF:EN5E5EbJEN'$( -'0 %" ) '$( 0EN V%b$0EN E0$ "'$)Y(! 8

PAGE 15

+4+ % G E,:Q97R$ E"! + F # 4 $W$," 4+ % 99aN#F'$W$N9JN9(WF'0EN ?ZW $E Q 9 R 5671 6 $E" + H" "' > ( N9 F) '><( $C>> N95B =56 $( ] :V%b '$( : "9 'L$(0 > '$("%b '$( 3F +-* %( F'Ja .+. %( '><(+ "%B ;! $( +-. 3':%%(F3

PAGE 16

P 54 $( F3V% ;0E' % JN' % )";0'$(E )MOL 54 JN 9 97 $( J_')$(F3LK! "B""+F ) "$ )A9 ; F ?#5 JN 3F +' @+ : ," + L3" I +A ( & +B; :%" 4+ "LP 9 (+ JN0+$( C+ L'+$( > ( %7B7% :""! A ," + E 8

PAGE 17

+ F # 5 D8&E c A"!""G E )M MOJI3 N9 ')$()G ," B): +F*& J9 F 7FG@ '' +( dKd[K 9 0 +:)&4 : 1 F "P 333U390E") 2! 9 JE")RFQ, YYY*)R 9 ?$ 9 '>/( F """ '>8(4" / F /H// '>93(

PAGE 18

+W / I H/: / N9( / HI "" "ED &" B):% ) >9P&$ F JF*Z >;N9 ;J4 ) +@ F 0" + EN9 F$)\Z 7 4&" % b ) < 7 $ (3 H"D + H" Q 9 R JEN > '$(FM'( K +N9OFM N9O $(N9$ &" >> %""G e!$ T EN ) ""

PAGE 19

>>P&$ ,F G! F* N9 5 ( JWNf(JS 7B$5 ;7 ;61!" # 16< E "" AE$% ) % '2( D )'( ) $WF A$ )'($W$ 6'>/( ) )E$$W + (F' $(V I$WF 9 $W $$ )"P '9($$F$$ '>($$" )" 92

PAGE 20

, HL 1 FK 9 3 $ )'($WF'$( F T9 T9 $Lb ).MN LN9O EZ)9 )@ < $( )EF3 E"'>8( 2) $ )'( ))E C*A4&4>2$ 4 "E( 'N > ()"' > 99 ( )L'$( ,*&6*>9$UF ? >$ T'( 8 J OE P $WF$ $F' $(WF$W 0 ))>()P 0 97

PAGE 21

=%> AQ=Rg 9/88hQ98R "& 4+ )'( 9/87A% )'(G @*$>> )'(S 9( B 9 1?< >( 9 1 F9 F $F_'\;NB( FZ;T9 5 Z33U P? <5 Q F Q# =%> "Q=Rg :% )'(Z9 > F9 9" 4 )E" & " )E Q " "'>99(" >2>7 )'( & + D!K 9=

PAGE 22

>2P&$ *TTL JFJ_ d) (K TT 3)? +"@ *NF 57 *E N9 ) U *E' ;+( 'N>()"'>99( P -0 >ENF EN9 "JN9ZWF > T9"*"""M\HOE F9 9 iEFQ*JW*EZ 9 4%4R T 4 '>92( R " A E'>99( B" ," 9

PAGE 23

>7P&$ F /4 JF*_ I )N. N 7<7& JENF !0 ( A")& '>92(K'N>() '>99( E AQ=R A "B) :$ H> D"+ H HA H>>$>>+>> :E" +S* V ,'>/( +E>* F >$>> cWW # YYYW WY > # # F W WW WK% 9<

PAGE 24

8 8 9 F #$ E< #$ 7R '>)97( "G '>9>('>97( B "6 BKG ':22($ '( '>99( !E 98

PAGE 25

5,% < 5 "G E ) H" E 9/87AQ=R )MJOFdJUW'*_ 7 'N > () J )'( " !BQ93RG B H" 6) 'Q9-RQ9
PAGE 26

$ NJ" "$ '( N > ()' > 99 ( B6 + Y(D 5$B1 <, < : 1 F'3 BQ 93 R )( N B): M LOL9 )>>5 4 "'>8( +% "%" 9LK F (H( '2>( HS : '2>( F >> >> H>> $^6% H>> H>>4>>R>> 8

PAGE 27

" V # : # F # # # ')YYYYY( P F9 ^6% B" H( F Q Q < YYY Q(R( 9 '22( )9 T< 8 7 < 8 9 < B ? 9 05 F'9TE>(9L>): Q > '22('2>(P G! Ff+NX?) <9 F % 3 G & )<>'KJU(N+EN <>F %& LN<9L( U>F'9)\<=Z\>(9;> *B "29 :'Q93RQ9-RQ97R

PAGE 28

29PB$ <7 FJF 9 ?5 $ T@ (9;> L NEN+E) JN+EN < NJN9) 22$6$A:# 6'Q9-RQ9 YYWB;)BE F 9 / T 9 $) T< J < Q/ F / A/

PAGE 29

#'29('27( // N FNE D$ 4// D!"d H/>DVH/0 F %* B4 B6*:'Q>2R( :,%,EFJZ"b / !F*) /I F / Q?) HA/ EFQ933RE"%\\W\\: / / 9 ( / C ()*+, :',WNEN / FL,^6% B" / H/"/ """" "2>D O@ LK:'Q9-RQ92

PAGE 30

2>P6$P N'6( P]EF )$S FS ) ;SF PD=WX' +, ". FF$F3IF 3 S3(F <3 FFF 9 S ,F,F*;US %6& // 1%6). / LKW S F[(% 9jA=T90;+LFNLT90;+ !6&%6/6D-6/6)E60D:C6&F.G-6/6)E60DH 5 F &5 N $% %5(E L N9 F $Y O <$c?LLT9FT;TT9 ,T9Fi +6I [3,)> %* & 3 'T 3 T,T(LT Z >[>T9'TT9,LX %6&8 ?&?6H ? % U=TdK(f+FN=&<;LF =5 U+NF=U+jA0<;L ,N9FL9'LN<,(S ,N9FLLN<,NZ >F>) >7

PAGE 31

5;!" # 16<# 1 JF,% % JF, < $ ) U ))( %+ F .+ /.+ UF '2=( BQ93R":2> % )Y( ) "29" $ 0 B): ) ;0E"'LE F 1 '2-( 0 0 2% F 1 '2<( : % ) F #'2-( (,, :'2<( F 1 : (+( F ( H( ;) $ :2>% '2-( @ )!B 'YY(' )Y("22 >=

PAGE 32

22PB +F; (W )X?F N(W !)=:)& % )K")="L =")1&!:)=")K)=,)F AV0>! 4+ 9< B 0/ P0 ) "22$ 4K""! $ ) F 7)J<) : % F & ) & >

PAGE 33

;0E"' E ) 5( *61 <116% < ""0G 7A F E 4+ +# P N9 F ,0"IZ= A / 0 / J;N'$() +K JJEN'U(( [ &cL(W :U' D! K 4I9O ( > 8 K4 U$(F TE T9 Q9 4 4;0EN' JEN'*L() # 4 ; F NJ; @@ '28( $) '$))( '$# I F #I F'$W$(V I ><

PAGE 34

A:27"22 +# F $W7)B" F N9F !" 4" $ F$ N 88%88 4$F NJ;$ "22$ F L )9NNE() $$LF NE OK>\ #" $@B&6,29$6$ :#P 0 F FJ;#Z F F*Z ,, F N+E( 7D F'EEJ( >8

PAGE 35

' *F0)^J N < N'KN' F'9)<;(9;> &4F)KH+F0/ FL' > ))L)(NL)K N] 7 )N ,0"7 F'EX( J;T Q4 *EN) <"P F@,F@"FMF+ <)9 M4+DF P '9(9"P 6 K > ( > P 5NM'KN '2(<:$]+h 6) '2>(9"G 9 :$]+h >/

PAGE 36

0""6) ,"" # G $W$)'( # N PE E "AQ=R" ) 23

PAGE 37

;171 <61 ; 02$ F )A F ) NY_J)'79( F ^" N<;+E)) ) 15 $( 'N > ()"' > 99 ( )'( )E WF'$( ," )$WF$)9$ "$ I+'L(I I+'$E( '$($K /'$ F9 NI F" )EG D )'J(% :7> 0'79( )$ 9 4 F NEN+E) 29

PAGE 38

A '79( O:)1=")1& % ) K"P)1 )K"+,0F :"'79( ''K F %+ ) '7>( )EN EN ) I0 ) 9 VDNN E 6:2>UK%%A ) )'79( < K%D F W )J;( '7>( 9 ) N9 )EN 5>?5& N '72( k K &EN9 # N9EN; &E +DN) F :72 G F H Z3D '()"'7>('72( ) ) F3 -( N > ()'>99( )'( D"'U() )'( ) ) 2>

PAGE 39

! < K%'7>('72('J() :)L' + '( !J)'(:! '()":7= % "!: ) D !!' L) ;+F1-1/60 < ":79 E M@ + 'b( C*A4&479 )'J( ) $(X'$( N'77( : # F )J; 4 F3'77( # F+'$( 22

PAGE 40

=)'J( 4%X)'J( )'J( 7">-T7(7! N> F NYYYN N1 "% + '( '7=(; L3 N '7=( @ ,*&6*79@ )'J( G @ 1 '9( Z N9 1? J> '>( 9 1? > 2)'3( '2( U / W3 1 U > N9 '7( ?% 91F 1 U> '=( T9 F3 1?< J)'39( ( F 1?< 9 )'9( +P+'7=(" )'J P I+U')$(IW)A^)LN; '7=( $F$( % -0Q '7-( 27

PAGE 41

D ", l3V$)BJ'$('7-( $F3$D'$W(L 3 V$WbJ'$( '$(F3;'$W(L3$WB*'$($F! E'7-( V$WB*'$(0 )'X'$W(Q:J'+'$((JN D","&*N NYYYN'/'$W((RF 3 V$WB*'$( A$ )'( B : 4 '$W( P 3V$)B*'$("'7<('UX'$W(( L'/'((;IQW'+J'((N1)';'(('(NYWYN ?Y '78( **5* F.I-7H-D00QF6-D0FFFFFFFFF678* &O@ F$W$WB*'$( +9(P B N 9 F3$ )'L(Q=R < 1? ''$W(( .-=%-/00.).F-7%-Q00.R6-%0)3)-S-004 T '$W(VZ'U'$i((NZ) '+'$((I '$(,A 'U K '$((K $W''$)((UQ 'U'$W((N )''$(()'$(NYYYN ''$((jWR 2=

PAGE 42

B N9Z3'78( > WL3'78( > 1 U> +>(P F 9F3U7 )'(Q=R JF N9Z3'78( >* < '78( > '78( N E F + > '78( 71H* FdZ & 9 ) 7" F3 F3 & // % 7" L 3 N '78( 1 U> 4 )'J( U: N, l3V$ b* "'7<('L'$((WD +Q 'W'((N)'+;'((I 9 /'(NmWYN/'((RL )'/'((IUQ;'+'((WN;)'+'((;) 9 '(NYYYN 3 / '((WRF 3 "F$)$)B*'$(:;'$(X'$( " 7" %," TW)1 )% 2

PAGE 43

+2(PJU1l3'7/( D > 7) L3 1 U > N9 +7(P:JUT91F 3 D 3 N )'JTT9('7/( 1!& F 1!> > C 3'7/(% >" 1 U> +=(P:JF T9 F3Dl3 )'JT T9(> B 3 JF 3 JZ3 B 9 % 3 '7/( >>F='D(jk >: % > 1?< L3 '7/( >>&7->-14> >$ 1 U>'7/( ;';%( >" 9J+ 9J '7/( 4 F3 9J 2<

PAGE 44

'7/( > F3F3 F 9 % L3 N2 U'$( ? > F3F 9 F l3 7" L3 !D )'39( F3 F 78 1;'7-( $FV$U*:'$( &$ $$FJV$) :'$( )'39( 1F3"" + (PD )'( F'7=( I 1% &N (f N N K N C TJ;(0F" I 8 I+)'$( N&N $ )'(J $TJ< )'T(D "? $$ )'( > N9" )'9(" J:>g 28

PAGE 45

" )'J( \ "" ?A U 9 >" )'( ) ) ;5171 0/ 9 Z3D'J() 6!"" 'Q2RQ7RQ99RQ92R(!'Q2RQ7R(%H" """ $W Q92R! E)!'0>(!Q99R !E" $'J() H" B;0N > '$( ) D L3" : 8 % D F 9 "E'J() ) N*)*'7)93( 9 Z34 2/

PAGE 46

* G N = 5 D//@?$ /" F3 "+ N9 ) MeZ+EO ) '$NJ /+ f /%" J[E& ) N `/ +( M+)Z 1 E) =2 /EG/@ FdZWFdZ)ZmXc[:.@'7)( /" : )'J($C79 N ( $ )))))))))))))))))< )))))))))))))))FWF) 9 9 F /'$( :" 4 (;'$( T7#T9T# LI F 5> FX'$(LI'$( 3 NLL$+ 73

PAGE 47

'79>( ";Z)';( N VZ)I'$(J@'$(: #N ( $F$'$(LI'$( 3 N$:I'$( 3 F F $JI'$( 6'()'793( ) 9 //" '799( '799( "'79>(WF3;) )9 N ]7 ^ T 3 V 9 k 3 ; 79

PAGE 48

" U*I$ZYYUJIY V '+$JeIZ; ""'()' F '( ) )'* D!'()" '792(6'>93(" B): ) $ 4'792( ,ENE)D!'J() ,D! 0 A!'J() F'J( )'J(," 4 "!:L'+ ) "'>8($ '>/( ( 7>

PAGE 49

HL ,P '+Z YXC&;/F /0X/% #" # 9 FT 9 Y'7)97( U) 0 HL : '79>(UE -5'*+ $E )))))))))))))))))5%)))))))))))))))))))))))) B" <+ 4 "4 BM $c)NU 3 OFM3J9 '9 B% 12 S'$(LI'$( 'E$L(I'$(3( L(I'$(3( U*Wi & '1ZJZ :UFL & +LO _))')$(:F* F NWWYN'(:&K &Z% 0-+06F1N 8 -;(0 C F++Z +J?Z)9++I( R0jk'79-( :284, F')() : +LL NYmYN'J)(' 7 ++L F R 1ZY 72

PAGE 50

HL P F % 'JZ( 9 FWT 3 EUWT 9 0, HL 3 "P F 3 ? $ ,"P 3 B MT T 9 E< 9 3 % B ? T 9 4 $ M3 % 9OZJ $ % HL $ P F U^Z > $Z * 1 > )KJ( 4 U > L)_1Z bb

PAGE 51

""P 'V( + 'V 'V( V V J93 Y 4 N 93 JE") : 4 '79<( '79<( '798( 7=

PAGE 52

4 + KG "" G G& F 9 )9 9 )9 9 && '79/( KTK7WK '798( G& '7>3( ;<"# F D )'J( F =;> ;<22? ) '7>3( "P )NI LLT&)9)E)R '7>9( 3 ZF F 3 ) 9 5' '79-('79=( c $ 4% !'() 7

PAGE 53

% ,*&6*7>$J)'(" ) 0E$("'7>9( +P:"g 6! () )9 "'792(#'79-(P \ )VY'7>>( 77$6AB% & )4'J( 4'() D$ + 'J( $ / '$();'$(F3 : $'$() F (6!'^ '$((F;'7>2( D% + 'J( D ) '()'793('7>2(6 ) '()'799(G $J)'J( LI F F / '$(;EI'$( 3 NLI'$(L 7<

PAGE 54

" N # U'$(LI'$( 3 @ F 2&"Y9DUD5'*4 F 4+"I N'Z?(J A'()" /`/" '799( '7>7('799( F 3 %% ; 3 K '+EN=2$EK ;:8 N;'$(V_I'$(3N ,:,,, 3 /" 6$LI'$( 3 bM$3$L ?>K JI9O ^ '$(LI'$(3F NYWWN'](3^ "EFQ'%W(_ % '%E&;) R< J ) T B"%B 7 '7>=( "F 3 TT TNJU 2%% 9 (T % 9 TT'T U T 9 T T'T ( F T 9 T ;'$(LI'$( 3 b+)IN;O0L K +E?O) "IC+ =2$E: E W 78

PAGE 55

1EK F3 TT &* 'JSN*$ "5! ^ '$(L)I'$(3( F 3 9 S)K$*Z '*U$Z YYY)K1Z UJYZJZ )(YYT 3 [ OD @J .+/@ "@, A4 B" =6F@J -%F .+/@+/@J UUU.+/ILUCI@J L -( 7 !+'7>=( 7 ?"% T'Ni( #" '7>=( " '() F ) 7 '7>-('N 'N !( "'() )4 !^'$( W N 7/

PAGE 56

$ )'(! 'U()" '7>-( $" )'( )G """" :L$(F 6 ) B):'>8( '>/(, "P '+E^ '$(LI'$(3N N$L@9'$(3( U11mZW :;'$(LI'$( 3 L K +)INU B )@+;'$(LI'$(3 FU 9 3 FT 9 Y ? T 9 '7><( 0 H Y:$L "'7>7( 'E^ '$(L)'$( 3 )$VL(I 9 '$(3( U1Z G+ :L$(LB K +LO 6F1-0=&-="0631=6I)UUM)-\0 =3

PAGE 57

" 4 '+EF'L+E)')L(+Z F'+L)'L+E)+I( NYYYN E! + @ ?*?O LI9O F' (3 JNYYYN $ (H)9 FQ'%()0(;)R0j C H FQ'+KL(L'ZL('+LI 9 ( RJ0W U* 4+F FE( ;E"P ZNUJ]U()Y<) [TEZMT 9 TNJO -4@R &Q/R/QF6)%Q@60 9 &3 3 EUT 9 WEFc =9 '7>8( '7>/( '723( '729(

PAGE 58

"N R> N';JZUZ <Y L C 9 3 %" Z( & ? 9 4 $ M3 TN9O B$ % ,< F:6 1 9 P%1<%]0 .P+@< 1W = @@ .M@J &9 < F(LU / .+*I 4 = FQ*F4B '# 08 1 =>

PAGE 59

$J)'( < P @[[9 9 )W7X 9 F GV / U:(Z*Zi9 LYY 9(2= E") & GV %P V 'V( V 'V !( G 'V ('V (=X'V!('V!( C'V(V V 'V V J G )!( "* ';H('!!(4 G G *% G& >X)9 )'J('79/("K G& TK K G&* TK 7 NK #"% < P ( F (H( ($ 7) ( N (N & =2

PAGE 60

4"P 4 F >>G 5 !" ($4V4V 4 4 4 9 '9 7 ; F ; F J33 L&)9> 8**8 ,: @ >Wcm>iI 6 2Imj=)3W. 4 4 G 9 G& 4G& F 5 4G& F 5 > F+E"N 4V N 4V 4G* F 5 ", 5 '727( ) $(* =7

PAGE 61

; '7>8)729( @ $ $ )' !'() $N 7 7)9 N9 """" ( """" Z "" 7 """!"" N %P ,*&6*72W'$(X'$( " F$D$();'$(6!'^ '$((Fi'72-( ) 1 "'72=( ==

PAGE 62

+P:"g 6!'()'793( N9"'7>-(4'7>/('729( ,) Y +* '72<( D'72-(X: P % N ;$ )'J(5!$! 5 G ) C79 RN 3 4 N F N;$7;5Y 7;$ N F N N ;> 5n""5 T9 L 6'5(0\L6'$5( "" ;5 !: ;5?5 =

PAGE 63

: "N ;5";5" ;5" ?5 # F N T F'$N ;2N N ;5Y & QX;'$(N ;5 FQ$'$();'$(RN ";5 N ;2N N ;;5 F ;5 N ;62N N ;5Y&;56!'^'$((U N N( %$! +7!57 '$( $ < '$( F 6!'^'$((U N)N)( 0&6&@@$6h77$F ;5 $ )'J( ;$ !=) "'72=( 7 ? ( +P72"g "'72=(!G =)L(: 6! 7 ? ( 7 =<

PAGE 64

! )'( A"! )'() "": : )'( F 9 : / W'$(F34 +0LN B: F+!'$(N D*: !'5EL(U 9: N=05 /5 7)9(X'N('L(F3 9:9 N = % 3 : U 9$:9 "" 4 )'( ) ) = 7= !:'()6 !' )'J(6!' D '792( 0 8 8 K( 8 1 YK( 8 8 88 8 8 8 8 8 8 K( 8 K( 88 8 8 =8

PAGE 65

: + F;" @@ '7'+ C79 ;)'39(!:72 ;) 9! 3 () F N +' ) ?51 F32 DF3 B 9 D %& & +@M ?$ P I LK 0 E F :;) ;)A B):"'>8( @JFQ933 3 & MOE)'>8(P 99 JZ 8 : 46 1 3 4 ;";> b =/

PAGE 66

L'3() >;2 !> F 2' *: K F3;2$;2 FQ33933R:E >S K : ; F &< ,( : K 3 < 6:72"'7>9( ""'728(! 7-06! 'J()'793( ) )'J( 78 '72-(@! )'J( :!'J()G !G ""!: "7>72 )"^ !"'792( '7>-(0 " M % )'J( JU9!+% -3

PAGE 67

)" 9

PAGE 68

(671 6 6 1 <1< ( 7>72 ) "'7>9('72=(" E"G 4" E'&(' >9( (JF61-+/60 < D ) 9;! d )'J("P NF ,( =Q&Z-7Q0/-7Q06FN# 8 ( 5 0 ->

PAGE 69

"LL$(L L'$(L / '$(F D '=7( UJE" JYZWfU__)( F)))))8%)))))))5%*)))))) ( '==( '+)Z + LK" Z B %% '==( T'JT( IH F '=-( 7 T)+)N / ) F 3 T 9 U >N9JN9 Z ) N9 ) ) JEN9 MEILIE I #K %% ( '=<( '1 + LK N F3 T9"D$ H )'J( 3F3 F Vc'$(3 /3 '$("F ^V W'$ *ENF)L*E)5_Y -2

PAGE 70

)'(Q=R B""+ F 3 // *ENF # 'L( > Z N 9 """ B"" . F0'E7(+" N T 9 + K F 3 T9D '%(F+NYYYNII9 5. FQ3&IR + JF0'7(+F+0')$(NYYYN c 0'$(R J 0Z "'$( 4'=-("" +P $-I 9(F*'>E( '(F'()J '( '>N(F'EN9(N'E(WF 3 ) 9 -7

PAGE 71

" J > ENF aN[ J #L? U=)8Z > 'NF F 3I9c D $8( d%H '=)/( H (" LK" N@ '=8( 4 JZTA +FF VKL+)4" N (F 9 +EE /&&Z% "P I 'J(_e'J(ic F + JJ F 9 F3 8 9 c' 9 ; 0 'K < : 3 T>^EL( F EO $G FN9 FQdYYWd93YYY3RB0n -=

PAGE 72

"%9 K "'=-( '=8( L '$("'=7(KF3 N F < VK'$(N j)Nc < L'$(N < L'$( 'E F T ! + N9 F QN #* N 77 3 ;R3) V_N'(" 9 G 4cfWYYYZdR) : 5 '$(LF 27<0"* 7< =! "" LN9 0* FQ3N 3 3 RJN9 :F #$ % F+ F 9 3 Yj 3 RLN9 #'>8(" F 3 ) 9 aYN9F #&`G F3 ''

PAGE 73

" I ) P ) J* R YYY 9 W 3 9 > 8 WW 3 9 WK%A < K'=93( ) 4 < = # N "'$("
PAGE 74

:'EH(F G!4 ,9) 'K '=/( $FZa)))+IR+E FL>YYYJN9ZJ F0+N0 NKYY0+ a[QZYYYZ0RI fZFL<)'=9>( ; F "7>I A $@B&6,=90B )'J(P P$J !% ')L(F D FQ1ZYYYZ1R) +F F Q9 3 YYY 3 RJN9LF Q9 3 YYY 3 RJ '9

PAGE 75

\0U IIIIIIIIII> f ) > < > KLf ?0< W F3<<9T9 J;NFN*ENF A,AI ]+ *;& J 71 J_YZ 7#E Fc F07)J&E:)Z 9F3 EUT 9 JN9 &Z3FH/ FT *)D / T EN >NF @ JNN>WKWFdZYYYc) lNiF +G&(*B"8#@ WKF) [99 F<<9 JENFaN+ENF AA + 7Q@Q&6F?0 T b>("% I&A E& '(Z FTT<9 YY F+E 5 F0+,N0+ `+/)/&/F > > @Q/U+,)@& 3 L,)F% > 04\U am_F>NN>VUF_)_Y)9 > ENFJE N9 NWFdZYYYm &* -/ 3 <<9T E)( I +5@ '+5 & U *)ZJK c

PAGE 76

6:7>$J)'( 9 "'>>ON9( "A'(U 9 9($E A$<)'J( # F$$W N T -% 3 N "4 + $W$ $WF +&#+ F$W N" 3 $ )'J( + F$W$ *9P0" $F939 ""$=9 E&" >9" <3

PAGE 77

U8 Y: A=9P:"*9 (5# 1<%JF61-+/60 < :77 N " 4 N%" 6!'^ '$((F 7 )P #b 9 i ) N N 3 ) 9 DTK '=92( A >WF 2 @ '$WLAb0 ;JEFQUJWL 3 Z 'W 0H '=97( <9

PAGE 78

)> 93 c /F5 m=93c ) 933 /3 <3 73=3 8 A=>0"&'($=9' (*9 <>

PAGE 79

" ? " )))))))))))))< %%)))))))))))))))))WF 8 T ( '=9=( '1Z "+ 0EI +T & % ( '+()R22)>2-( "A $F$N ; $;))E ;5 5F F5O5 <2

PAGE 80

O5 F5 !:$;))E / '$(F;'$( @ + F # 4 $F +&#+ '$W$(I]$W$W$F$f]$W$ 477 $'$()+;'$(F$)$ )*)*+ )+VSW($ CMO.F O5 F5 4 '=97($ )'J(LK" $ / 9 "'=92("" "K N K N K TWWfW !"W" / 9 '=92( "$ E$ 6 477 FM$LOjFFL'=9-( $ % T'+L '$K$EJ(F'$L$'$)#E((F'$L '=9<( <7

PAGE 81

6":77G '=92(, H / /+ 'JWZN'JJW( FT)TTFT)T)))))))5# EZMT 9 /%9 '=98( # <+ '+EZ #+ C 9 Z % ? 4 B/% X XF "/ F O JWZY $ / TX(K HS "" $> 7 7 "" $NF)XN;N / 5 1 2 JW( '=9/( H) N9 : k ')K 4)K/ LA% )'J('=98( "LHI9O A" F 7 T9/ '=9/( F 7 TXN9 > C e F 7 T 9 X Z e J '=9/( "P FWF 3 T 9 '=>3( *)** Z <=

PAGE 82

,"'=92( ,ENF )J>)!j>)Q 7 ccYaIR H5 #3F3 > K'=9/(: F=L<9*ENF3T9 afL>;N>)K.cF3i) "" TT 93 TT)] > Wf 7;) 3 ""P '=>9( [ & <&R" D* W KW \3 > ;f ") @)E'=9/( N K N K '=>3( "@ E"'=9=( F'*'E(N*;)jVZFET3N9E $!!K EK"@ > >( MET'J % T3N9O ? eKEK'=>9( '=>2( T
PAGE 83

c ) N9 ML 9 K )'( ? U ?D EN9 5 :)'(D B M e9 ) G K "P 9 1& dWJZ D NF < )J 9 8 '=>=( F 3 T 9 $" <<

PAGE 84

$@B&6,=>0B% J)'(P P e D )JI9O3 :F Q93 YYY 3 RJN9LF Q9 3 YYY 3 RL F 3 3 T 9 ++H)&a) 7 +")?&"F 7@78 & +@ 8+ &>>#E<[>>E & +f :M ? \&0& ++="M EUT 9 + N9 FQ 3 ))) 3 3 ) 3 RL FT 9 &Q^% JENF B 4%H5 &!=S)) 0 $@"71 $ :"'=9/( \ j ZcY)3 F3 W)9 P +* FaN ?# *ENF*E)UWSZaYZ 78 F' cc(cZ ? + &?+"F:@b: [ !C:&.J7P7Y0P U<<9T 9 JN9 FQ 3)3 93 ) 3 RL <8

PAGE 85

FT 9 ENF B% JEN@ EN) I WWYZ)U 7 W(W JF (88E4 JLJEfL&+NYYWN ,8 JE `L)/F; /F+-LL/X0.%QF/ # -!0F//X >NF?N)JZc) :"'=9/(IN9 +HFCC)FW)bb&OMFP62PU :E)NF >E)_N N:)/NcW F3 )9 # YVLWN?a)_NVWcF 3 ) 9 :)iNj:E)NN)cF3?) : $F$N ; $;)'J( ;5 !077 N J" $W'$( %" ^;'$( 6!'^;'$((U'JNN( @ +# @+&g+*#
PAGE 86

" / / F @NF 2#N"Y F &4 6!'^Z'7((F6!'^;'$(( ? ( 72 4# $=> D$;))E + F ["-( 47@7 F$) 9 Q$W; % Y F 4CK ) ;5Y $W$!E &$=> %)E *>P: $F$N ;> X-5$%+) KC T$ L F;' 3 9 (' 3 9 ( F^2 =)% I )EE ;$ 8 G 7 98

PAGE 87

4 ;)'(')E(! 8 A=24 A=2P:"*> A077! '$(F; #N! T'$(F # T F ;# T ;54 (6!'^;'$((U> $=> + F +.1 ':>2( + F # A*> ^'$(F &4 6!'^7)$'$((U> 89

PAGE 88

:$;))E 477 G '=9-(,"G 'L 4+ '=9<($ 4# $($=>A=7G ""$=> E'&($" "&" >2 6&G & )'( R$ F D$=>" )'^6(A 4Q ^6)%^6" f".EQ>RE + 6"^6 ^6 4# $( A==" 4@ $=>^6*>A ^6$=> !"" "$=> 8>

PAGE 89

" 93 c m:^) 93 c 93 j 933 /3 -3 73 8 A=70"&'($=>' (&')(*> 82

PAGE 90

""^6^6" @%f!).Q 8 R "M"OJ@M)OL <7% // O>>9 &D!-C/ $( & >>9 F >>I $W( "">" $=> 9 "G A=-!' "(""^6 $=>*> 87

PAGE 91

6"6(F 8 j A==0"$=>'(^6'( *> 8=

PAGE 92

93 mp 93 c ) 9>3 933 D! A=-D!"$=>'( ^6'(*> 8

PAGE 93

?671 5> % N ;5 *9 ;5 !> A=<" )73 eD A=D "$=>&^6 A=84""&$=>G A=/! '"($=> ^6"*24! ""^6$G => 8<

PAGE 94

)< 9>3 88 A=80"&'($=>' (^6')(*2 99

PAGE 95

93 93 c )2 ) m< 93 c 88 >=3 933 9=3 D! A=/D!"$=>'( ^6'(*2 8/

PAGE 96

(;!1 6E< G E"'7>9('72=(D A )E! N : ""% """"LK &""4 % )E! B'Q9>R( /3

PAGE 97

' <<,!< 07 ) E1 !B : "'7>9('72=( $ )'J(% )'J(' :77(D! '() :' !'() 07 )'J(% )'J( '() !'() "% %$" /9

PAGE 98

->+ D @*$-9%" '( < L3"JFQRB 4 +PQ>3Rg % B %% 0" > F 1 ( 4; N % ;"A;% B %% B""L) >14 )$(G B):% )'>8( Q=RA"U 1 + )U$,I) />

PAGE 99

$ @*$->:L'>8(@ Q% .Y$ ; U'$( '% .( +P K 4 'L+ *(Wo3c C (K$'N WEK 7)3 > +(SFJ'ND(EW ./ / F9 ^ '$ 3 ( 3 3 ("" '% EK Lc('%%E"( OY& K N "Ah Q=R!'(E :U 1 U L3 'h-..> %" YZL N"I M "0 9 NF$Jf?ZiWYJW UF /2

PAGE 100

EK $ &A-O)*0"^Q-+/0Q / > ZN (W i5)))))))))))Q&T 4 A A : 4'$L 'L + "" LFd D G :+Ll^ + ,"'LLl 3 L)EK -)0"& $( -+/0H@ ;F ""G g : )'J(% )'J( ':7277(07'() )$0'E($( "'792('7>-(D '792('7>-( 'W'+(W > '+(( U> ^: "" "" '792('7>-( A@-9 /7

PAGE 101

%"+ %J)'(% J)'(!' = () "+%"J !"+ !!'() :'$(F $ ) 1" Z$(B):'>8( $+E"F $ )'L(, F $ N $ M3 T7)9O P & > L[W 3 ? J"A:72 $ + '7>9(""" $% )'J(':77( ,P 3 N0; > /=

PAGE 102

$ ,K M3 TN9O < "P C 7 A "$ < )F ^ iWEFc 5(5. 7 \ 5 'aY2_Z B 3 ? (22 '72=("" 81 )'J(% + 'J(: B): : cJ 3 J 3 c 9 UWJKJZW JJZo UJc*Ld 'WJZmJZ 'JJZ '5 7 ) 9 ( UJI cJi) L P ,E"FN9< /

PAGE 103

$ K iEF -'0 AB W 3 U " F 9 NNS6 F K "" '
PAGE 104

FM 3 % 9O*)'J( F "E'79-(%*)'J( JF N " "'7>/('729( C*A4&4-9$$ 4R "* ) R "'-7( "07 D ,*&6*-2:0 # 0J6' ": -0 )'J( # AR J( FM3 % c/ '>( N " # 4R" ( FM3 )N9O ") +P:7>7207g 4) ( # 4R" G "% ) # 4R" >N& 6!'^'$((F / /8

PAGE 105

:) >>! R (D'() 6'() ) 8 N9 F J / )R OEGK '-)=( /" ) )15 3$(" D??1 T> /`/" L )9 NJI // 1 # / E ))))))))))))))F / F 3 %% U* 1 P UJZ>ZiU*c*Z ; R ) F ) / 0 % 1 k UJ)JZ UWJYJiIZ 223 1 4"5672 ))))))Z Z UWJYJ)))))Z UJ))KJE))Z UJII)JII?Zi : kUJ)))))9)J))))))Z ; b 4R" '-9(: B N + F' H 1(" F 6 '>8( F
PAGE 106

$ H > EN D F <" N T9 " 9( H < "P I : UJWJZ E+U*)J( mW[ 8 9 ))i)Z )Z1I?ZW 'E))LUI_IZi i 3 Z -,IC0-"/0 'E)2)(YYY0)2IZ'iEVIZ ;Z NU" U*ZJL UJIJIZ j IIIZ JI 9 3( UJZJZ ( UJWJZ 'ED)]#)('E#)( F NT 9 '-<( 4 88

PAGE 107

L I" F F) ):I) ) O%% ) '-<( UJZJZ )) 9 _3( UJiJZ UI)IZo @" 4 E Z ;_( UZZ 'L) )4'-=(E FNFN! 'J() b 4" J( 8 (" B" 'J() "% ) @*$-7: 4R" B):'-9( 3 N 8

PAGE 108

" $ "'->( B'-/( B" '()'-=( F "%* )L' =%> :"g : O "! YYYZ '+(Z 79L '-/( +6%"+ % # 4R W(Z! 'U() F *% 9 "+ %D # AR" U9 !" % 0 4R" "? 9 F3 R" "'-7( F3 RD 3(" 4 ) 5! : "L L" % 8

PAGE 109

-Z3 R2 3(" +ENFcWJE E R ] 1W _FE)' )( 4'E()F T9 "D 'N > ()' > 99 ( F T9AQ=R J) 'T9( 1 UN9'>9( b AR" F9! U() F 9 F J%! aI'+(FJZYDF3"+ ,*&6*-=: B 4) 9(, H>> M;!EOEFZ B): 9 ( 3 $ "'->("'+(9 E B N9!' () "J > iE)'+(F3"+ ) ')9( 1? +PA F3 E)F': E)>Z(F3 "+:"+"+ '+ F M+YYY+<)IO" F H 932

PAGE 110

H8 '# >3 ,; 25( 9 H :E)'+(F3ZEK %@F Q3YYY39R B J F H F 3 :EK E I9 L3 : Z3 E)F K H 3(d"((+ Q=R;E)F3VL )'ET>( 1? 1? F^ F N9$ ) 'T9( : B 9 H > 8 (P H ) 0 < $" UL)9 )Z UJ3J3ZTWZK UWJWYJ9 B+ UJIWYJ I Z -'80 937

PAGE 111

:a)P'+(F3 F'E) F 3 F 3 % -T94 B 9 U RKG!+ F F 3 &-="FM0&OQ "'J$(F @ VFM^$L 8*9 EEE K L :$ )'ET>(! # F+ET > '$( < N bM$E$<)>LOFL =,Ic '-9>( 4$ 9 F$L$L)+('-99( Q RB+ &-="IM@1=@<&.="I4%0J&8 4 'EI > '$(3( L$EE / $<)9LO FL / L :$$LqEI9 $$LbE$3$LO #'-9>( $ 3 B$EE$<)2LOV+L$(F A@>Q=R$\" )'ET2($\ $V:" L$(F Q=R$ )3KT2( E )> F'E) > Z(FdZV = ) 93=

PAGE 112

!"I > '3(F3V E FN>$J) 'T9( ZN> $:)'T7( $J) 'T9(g 6-=$B0J' " F9 $ ) 'T9('()' F 'T93( )'()' F' 9( %^ C*A4&4->$B 4R" ""3U ?% > U+)NJ / 0 1 F[ EF))))))))<< T))))))))))))))))F 3 F 3 %* $B Q 'iU("'()'-=( )L'$( 0&6&@@$6h -$ # 4) ( U9'$(U ')/ $ # 0J:6' " 0/ $ # Q5" F -' ) / 3 ( +P F3-= 1 U N9 $J) 'T9($ ) 'T9($B 4) T93( 1 UN9 F9-= F'4 F3"'$(U N9$ ) 'T9($B0J:' 'T93( &(I 9 '3(F 3 %$B Q 'U( ' 9 (g 8'

PAGE 113

4" %" B C B" "VM 'Q>9R==2)=-3( YYYiJW(F$$))) $ ( 'X'W( $ "Mi?O Qi I< YYYiR K 'L(*S! O : 'L( L 'L( F $K K E O : #E(F 3 m7FL)ME>T#( 29'( $ "$$ \$\ $! C "E" 1=1"" Y/-8 UUU1/7-8 )UU) /-8UU /7F-8P1=-8 Y7/1-8Y7/-8 YV/-8UU @#6 Y7/7-8 93<

PAGE 114

@% 4 :' " @*$-<$ 0J:6'J(" Z 1M "< DD 0 $L $)YY$ 0 / 0 F^'-97( $$ O" < F'e M $ NN9 O'-9=( +P:$ Z %D C7 C +C->" 3'() ) $(:" F 1 'Q9/R->( 1B N 7)> M '^(Z N>'J()'-=( + A M 'J() @&L3 )1 FNJN > '-=( ") ())1 *NN> F R" N9 N,$'iNN(L:f = 7"R '-9-( FENWFN N D/"9/.@ LL 'LiNJJ# /"/@ JiZ_ &'NN([ '1Y + F 3 _UJN? *" () DU'*(F'+LNNN H $!LNNE+ 0 1 3 U 9 A F3 "FM P D^ !NNK$JZWYYY )? C '-9<( U+N / E 6NN ) N=NN 8 938

PAGE 115

4 N9( N9(" :%"$b %& ( J(" +'(Z N>D^E(F3F3 Q=R" +: F3D'(+ '(U 7 N > '+(Z N N>+'(UNN> % AF3 !D)% "+%:D)+D) %"VV'(F3V 1 (U > :'3( > V NN> FM 8" OFMJ < +N9YYYZ+LNN() VWN N> C O = G :NN )"VNN > F OO#+O&O+ )E O8" N> 'Q9=R++)8)93(" K B KG VNN > KG VNN > K F K @ $VNN > )D $F 4 $F # 9
PAGE 116

$F "> VN N> "$$WA" ^+EE(F > 3 O D(F ?" NJ /" 1 / 9 WN FLJNWN?N* FiN9 <) FUJNUN9N*LWNiN(:L( F3) FN M$L #K $LO )" 3 + < 9L #=d+)1M JEN K AV_N N> "$W M$L >"K $LO0VNN > ) 4L )LJLO:L! 4 JN9ZT+ENNON>"B):G UN9" )+N9(T*NNL) 0 VNFL K E M K LO K E ) [<))& =73/="/= =7="cF :M$L+$W+$LO )+" M$L$+$0M K +E d=@+@F@+/c<=-+M <& F@+ = M+ 9 QFU+Q@U 8

PAGE 117

NN>"NN VNN > "ML K L K T9 )LE : M+Z & YYYYJZL*KL*KL*E FL N $c$L$#$#7LO "'(F N9 N > ; !"# @ / )" )" I 6MLOF ME;OMF I N I N $ 'Q>>R>39>=<)>->( !$ > ()VN N> VNN > ): + -U/U0&F/U0/ VNN > ):K'Q >> R2>-) 2>8(VNN > + Y( $'N N>('N N>( R E" 4 0 N7N> VNN > ^[k 4R4& 4@+4 F b'WN`N > (W'WN`N > ( '(

PAGE 118

6$WF +&*#+ A'-98( 4#+4& # $F 4R4& '-97( )A'+ FJe $ 4R4& $ $ 4>54& $ 4R#4@ $ ))Y $ 4j$R@4* F #$ B &L$(FN N>:" "L B0 7NN> F4&! ) $(F^EC$ 4RX $YmY$ 4RX $ 4R#X $YYY$ 4R#jAX FJ( "B07NN>: 4 Lm'+EE$(F #$ N( $(F N> %&'$ R X RL G R#RX >OAX "#$ "B0NN>"$'))J)>('N N > ( -2+&40 D" $B 4R" 4R" 4R" "? 9 9 (D" QR" U'99(0-/ 4R" (U'99(" ,*&6* -8 $B 4 6'(' "? '99( 9 ('$(U2

PAGE 119

'>($ )' U'99( +P:"07 1 U2 1 U2"'9() );0' L K >OA :72! )' '() )"'792( D' "? '99(-= '792( d% C -> Z4 ' "? '99( : b 0J:'9 9(0+b L F7 $V 7 V 7 FL$E $2LO A@-<"+B 1 F7 52 % FJ$$$$^$$$F3'-9/( @-<'-9/( $XR F:$ E=$ WE$F3'->3( XQb R $ :K 4 R 77: R \C RX W= R#R F307' >9 ( '->9($ 992

PAGE 120

'->9( @$" '->9('T$( \E R/ # ( ## T$;(\F3VEJ b :"'T$( 'T$( \_ & 4P '6)$;(: 3 4P4 F3VJ07 A'T$( \ R )$;(= 3 ) $ GP )$ D $(J\F3 /& J b Q $;( Q F 5 3 )$;( 1 RPQ3PQQS \F3V=J b '->>( *" X J b XL N A& & J b J C QA \iNi Q'A+Q3'A&Q3Q'A& '->2( Q7 F3"ESJ07" 7 J : Q7 %" 997

PAGE 121

"" Q7 %C Q '-92(P Q@7 F\E QL7KQL7KQ#QL7I 'N(BEE(B'EJ)A(BB')((\ N\N(B'N(( Q#IQ#Q7I N\N( QL7IQL7I BB(\F3 L i07" 7Z C 7 F 3 P J_#FF > \ > ( QOQQYQ8" N>\( QL BW( QQ N>\ QQ QQI N>Q QOQOQQ \ N>\ QIQQ#QI N>\ QQOQQI F3 LI b07Ab07"% I b 70 L FL" R "$ R F$ Q F 3 L "G % QIQ"QQI F 8/[e 4" T> \ QQIQ#QI F3 [C b b -';0 4$ R#R,$IRR ) ,D0 F3 [0 b -'(0 (

PAGE 122

"'->7('->=( A" >+$ %+ 0U<:'99( 1B 2 "" +$P: % : %" R A';' F7 7"D R ;)" R "$" R# "$C" R# -CW G 0&O@%Q4:F @ R "$E6 -'(0 9$F$ +1/ R#KR KR@R ) K0 F3 [' b -''0 C U;$ >$7 $ : RR% $;( R#% $ FMO $"R% FM>L7O*" Xb XR,jKIK

PAGE 123

EEb0 7 < G 0'->-( < < \ KR#KX>X 9F3V G '-><( A XG 7 FN%%B07 b C A \J 3&+AC 3+EAC Q7 F3";% 07" 0:X'( 7 %" 4@7 %!"" 7 F 3 4@7 \FF GK WW,KJZLNJZ ##GKA FdZ"JKW'-)>8( 0F RN< F$ > J>'->8( \J RTK J > R#.KR#OA LJ 2 ?F3V% G 07 K WW*i K 'WW ]>L!F3V%07'->/( : N< RT "$ > RR# T < G >R T < LO RR# )$ > FMJJ 2 N '->/( < \ R#O J>FdV G 07 4T$ \J'W)$;(JJ>\F3 OXGb 99<

PAGE 124

" & 3 T $ G& b0 7 \ 3J& 7& \l3 & WT J4G& J> 3 $ M 9= EO'-23( 4F J2 '->8( R# F$ 2 J 2 W )$ G. bMJ 2 O'-29( : J> J 2 N< J2 R# )$;(MJ>OMJ 2 OFMO 3 T$ G. F +& < T D "" W "'->=( R "$ 3 "$ 3 " 07 A'-98(EE" 3 F ;; F$ : 4 F$ 4 4 #'-98( "; F :) 9 '^) 9 (W,W^ '^( F ^L^) 9 '^( F 4R#4I 9 9

PAGE 125

4 "$"$$ $W""A 4 4 3:3 "$$ +44 F 4#+45 +EE(F3 $$" )" $ )V 7 *""$7)"G $$ )"G $$"$$A" )$ ) :$ ):'Q>>R2>/( 4R4&4#+4'-2>( R "$ 4 ) 0 $XR F X RX R#X R#RL E F $ X C X Q )9 f 99/

PAGE 126

$F'E RXR#X F =J=2J= $$_< / $ $ $ $ $ '-22( O,>>9>,>>$>>,(,>>$> 6 jIR $ !$";'L(*; 7 $! 'L(% R (F^" ;" R X 07+@-< R %E;2b b dj 9 R ^ L % 7"F7RX N 'F R#X N R@RX F3 *"'-22( E$99<9$9<9 JJ= O< $>> ,$><> '-27( + J2222 $$E"<" ?D*E & 8 '-2=( 8

PAGE 127

4" E4EL'-2=( O( /0 9 $$$$ 9 $ > $ > $ > $ > 9$$ >> $E"$" > i 7 F) '-2-( :'-2-("E 2K @ *N & Z / UUUW NF $ m 9$$$$ 9$ $ $ $ PPP P $ >>,>>,> 8 '-2<( '-2<('-2-( X X '-27(" X R#2R N ./ Q)6N; R#NRXRX '$(X'$("9 X R@NRR '-28( C79 R ;)'J( ? '99(

PAGE 128

D$ )'J 'J(U '99(A'-2>( R#4#4&*` 4@+ F 4& : F ) 9 $W $WF +#+& #'-28( 4 @N 44&4 $'$(F'$( U <9 9CG 79$ )'J( ? '99( % + P:$% D" D D$B0'X'99( 1B 2$" :$b0J'99( 1B 20L$(F7 $$ V ; V 7 FL$L G<8; @

PAGE 129

6"'->7('->=(6 :K Q '6 %, D6" 0 9 P:$" 7 '$(F'$)$(7 6"%7@L < +2J7( "%"6"$ :L'>9SEL("%" 6W"$6"% 6WP '6W)$;(F3 '6W)$;( > F '6W)$;(]F > '6W)$;(F '-2/( '6T$;(F^ '6)$;( > F '6)$<(F > '6)$;( 7 F 2 ) 4 L Q4 L Q4 6 6" $9 $9 $9 $ NN4 F N "%"6: 9>2

PAGE 130

':)9(W'E:c)9(G "%" R# 4 ':K)9(W"'=)9(WF NNX E'-2/( WW7_>2_>>ZJEF 2X >2K>_W> $ 9 $ 9 $ 9 $ AP =)9:F ) > ) ) & & f ) & ,, F; '-73( 77D N8N J]"'%"( 9 R EK "'%"( R# E c:j9 A'->7( F+L$EF$ =? Q3 @ Q3 00 1 F3V"b b '-79( B Q #'-2/(BW 0 KQb QKN8UNL '-7>( < QK L < FT(Y '-2/( BSBF > '-72( 9>7

PAGE 131

D!'-72(! QQ E Q : Q BWB]" QQ ABWB]'BWB](W B]B]BWB]" b )LOA" q N QQ :'-7>('-72('-79( ()* *+,*-* 4 1+/W :]B'LBKL(F Q F3 A'-73(L N J) '-77("J+]J N ./$++,* ;2 < %F 3 N N T9> QL b NLN<9 BW]F3L" R# "$ N R# "$'-73(L N L:BW]L3 9>=

PAGE 132

'-73( > MJ]J>O UXJY 3 F QL. F Q F'L+L( ," R R 7 '$(F '$)$(7 0>P: R 7 '$(F '$)$ 9 ( 2 '$)$>( CL' > +2("%" R "$>E" R "$>: J'X>ZJ2("%" R# "$J>E" R# "$>6 "%" R R#: R T$ 9 ;(F3 R$, 3 [$;( > F L 'W)$ ?;(J> FJ R $;( 2 F > R#,N8 J R% $ > ;(>F3 '$W)$ >;(J>F3 + R R# R F E&R `F'=I 9 (VW=W '-7=( 9>

PAGE 133

"P & F C F F%F // 51 3 %R &D '-7-( : >$F$ > '->7( P \+> Q < <* @ B>L>2Z\F3V(b0 7 '-7<( :<>)'B>( Q# FM>OZL'-7-( Q ML 2O)$" X b b QK< 9 "b0 7 < b0 '-7<( < < %$ \>Br>E XQX \F3V07'-78( @ X FL'-7=( QX FL: \+>Kr*" > >KEFd) :M>E>LO"G % Q< b C* ; ZJ>Z>PO)A >E)@MB > +>>JO BL>BM>O'-7/( 9><

PAGE 134

4 2 FJ'-7=(BF / L: '-78( :'> NN9 >E)@MB > J>EJ2J>( MX? @$U" 0-W=3( '-7/('-=3( Q<< '<7d+1/ NL c<7-+15/+1c 10 ;" < BLFJ :BLF 7N ;3+'-78( \>J> FQ F3VB07 4 FJNJ]E"'-7=( :">EJJ2JL 7 F 3 BE = >F 4 B=eF3I" R# "$ > L9 T >BM>EOA"'-7-(>E)@ M+2O)4 R B > 9

PAGE 135

J _]2 3 P $T$ > > < W 92 3 b $ 2 3 / B > F $ T $ > 2 3 $ 3 ( $ > 3 $ > I 3 R 6'->>($ $ > QC Q!XQ,XQ,Q!X & 3V+ Q# 4 XL7K -H %I 7Q \N"0X > 'N !0K B&NS(B\B > 'N ^ 5 (\F 3 KQb 7Q 7 7 F 3 P \" Q < BBrB > i\N\ Q < O BrB > B > # \i(B > (BLEB = B > i\N\ Q < QLQQL F 3 KQ :>" R lW K >E "" \>B > i H G DGD5 F 3 V 0 4LMB > #BLB > B > #O" Q!L Br QQ!L Q!L $BL$B > B > #T3V b '-=9( C $)$ > 2 $T$ > 2$ 29 W 9$ B > F 4 R "%$ R AB > "% 9>/

PAGE 136

$T$ > :B > Q "% '-=9( Q!. $ Q < $ QQ!. F\ Q!. BrJ QfQ. F3 Z8 4 Q\ "%@ .%Q 'BW(W HBLE QX E\F3V 8 Q B 9 \ QXQ#X F3VZ07'-=>( @ JZ' > i > > Z "%"BBW"4 7 <7L ,(Fd) : Q#XL F XQL F'E3(F3 QgX >(F XQ( J A %" ,KLEJ>,ZEFd) 923

PAGE 137

:J N ;XF3 RN" R# J R ""% R 7 '$(F'$)$ 9 ( 2 '$)$>( 02P:$" =;-0 F'$)$?( > '$)$>(> CL'J("'%"( R "$J>'>>(Z 2= L"'%"( R "$>:'("'%"( R# "$J>E NE "%G ""$>" %" R R#: R,EL F3 R T$;(JFJ 2 3 4 3 F R )$ > ;(J >> FJ> R$,(M F 4G$ F -%QFD0+& R@ ) 3$ 99 9 Y 0\ 9 '-=2( '-=7( 929

PAGE 138

: FL$ $'->7( P \ QK BBi\F 3 V"07'-==( KQ# BJF > N < QK qMJEO#'-=2( Q4Q' FJ) : QK QQK '-==( 1? 41?F/<8F UW 9 > 32 37 % JNBLN 2J> N7JF'-=-( > F3J% %" N J:^L3 4 2 3)7 %]F3 D 2 L3LE@ < L:L '-==('-=2( \J(JB QQ F3VB07 :JB" K B0 7 FB2N

PAGE 139

Jb b < 0" < QQK &#-#)Kf10 "" X B b >JE(BKEF3 4 X J>E QN< F N< N'$ > T$ N< : J"J 9 KJ >> Z >> F3) ,""G > L3'-=-( BWJLMJ9cJ>ZJZ'-)=<( F>E$ F$ > '->7( Q kJ> B M> N > N >O'-=8( '-==('$T$>(; \" QLQKQQA F3V"b b '-=/( :P 9 (>EJ>EU < L > ( < >E N 922 ?

PAGE 140

;X QK L: B"'-=/( J_ ;7%>EO B* > >Z) 4 > ]M>E>EOBc+L] 3 & Q@BGE?GB H ;< & [GI L" R >EL>EA >EL% > :>E>E N >E LA'->7( < WFL \>r> QKQBr> Q7.Q07" 7 C 7 7 F 3 @!7! F\>Z QfG< K Q < < N\>B=>B > (F3 927

PAGE 141

"ZJB07:>Eq]E]EB> B0 7 Q!X F]E:" > ZL > L > ?Z 'L9 [L >(L9 N 9L9 BL]B\'X >> F 3 "%B07 1KL>>>Z>?KLL > \F3V%B07 :>E]E!%B0 7 Q<.NLUN< < l3 Q < )@M>(:" )@ L > +>_ > > >FdW :>E]>"" Br>BM>>O)'-=8( BLBM>O'--9( $ Q# BM]]E>EO '-=<( = 0 BM]O'-->( B]EF3Br>F3 >'L > LWL" R# $'$>( BJ>F 7N< QLDNL '--2( % 7 ;24'-=7('LBLL(F '>(F3: 3F'"Br>(F'B > ]>(F'$)$ > (']>( 92=

PAGE 142

$L$ > LC >E A'-=7( < ]ESB0 7 Q(< '-)-7( :'--7('--2('-=/( J"J )*VJ>Fd) "ML>>EO R + 7 '$(F'$T$(>'$T$ > (> 07P: R 7 '$(F '$)$ 9 ( > '$)$ > ('$)$2( C9R'("'%"( R "$L2E" R "$ > $ 2 ":L'>("'% "( R# "$>2E" R# "$ > $2" 6"% R R#: R,JGL F ^ -+UF .>@ F 3 R,LL '6W)$;( > F R T$ > ;(>F 3 '6W)$ > ;(>F^ R, F 3 R@ F '--=( 92

PAGE 143

$ R R W"'G %"( R R# P & F )1) 9999 )1) 999 (e J?,EX>J2 > % T>T 9999 9 9? &D -'''0 P : L$ F$'->7( '--<( \*E QXQKQQ F3 V07 : Q Q2 MJ( KQb BiFJ > NJ>Z *LD >3P2 3P7 % f+ NB:N2J9N7J F>) L99 T '9 0 7. F3L < L 7 F 3 J> 7 3 2f7k & 7I 92<

PAGE 144

4 U>2 37 %LF^$ 32 L 3 L f N :L'--<( '--=( \X>J_ Q4& BB"\F3V07 :U < LB"E 0 7 X BEEN < L K 0 7 K b0" K QQK FB'B7) KT L( "" 93 # 07 JZBF 3 T '$> T $ (; 47$ >L 8Q4P4 F3VB07 : X FN / TUL9 T" > >ZJJ> >2 Fd > L 3 -8 ( Q;L +KJ >= '-`-/( :U < LD J>EL4J>E B K b0 7 BiFJ > N
PAGE 145

< l3 Q( :BW>EF'$ > T $(>'--=( QQK F'$ > )$(J> :'--<( J" B:W :ML / LLO"G % Q, MJJ>O'-<3( / / '--/('-<3( WfY9 Wf QL MJJ> LL J J>O F:+'*X?OY 4J>E / L / L J]E / LJ>E / / T&TW)9 BJ LLO '-<9( :JE)@MBJ / LOBLFL 7 F3JE R# $ L& BWJ'--<( + J] BBEBF3V b :JE Q# Ab FBN
PAGE 146

( # b K # K QQK F QQK N < ( > Zi_ QX Fd_VE7) "'$T$ > H R # J] QX F 3 OX # b '-<>( @ X FJ>NL" W JZ>>K J 2 9 FdW ,"ME N LJ>EU < LOG M>U < LO :>E2E '--<('$T$ > \J QLQQQ F3V # b '-<2( :)B K # b TL9T2W B)F J>9 N J29 Y 4'--=( QQK F'$ 2 T$ > N8d $ QK Q < Q O '-<2( W Q J2EF3W 973

PAGE 147

:L M< QL <=d+/@ '$)$ > ('$)$2( R ": R $$" % : ; ;< $ .< F %,.% ^ ""L'+ F7 V 7 FE 9 979

PAGE 148

%CM9>2LO"V 7 )@ V 7 FL> .. O $ V7V 7 7)" $W" " %g 0&6&@@$6h-/ B 4) (' U'99( '9( 1? 2 > ( )'3 9 ( )'9( =%> :-2A -2' U'99( )'33( )'39( )'9(4 )'33(" + '&($W $F;B0 $9"$! -2077!9 )'&( 4)" '99(: + '&(""! 9 )'&(">" 1?< 4 1? 2 114? 2 JW'+$(FL$EE$>LOFM3 K >O R 99( ) > 97>

PAGE 149

?: b 4R W(E' 7(U' 9 9 (0 -2 E 1 ? 2 b VN 7(F 7F9+ 8 \ 1? 2 =)'9 (g E D 4R ;0 ;0. '9 0/ 4) ;0 \ -/;0 U -/0/ )'( 4 - 80 972

PAGE 150

<0 E" )H"" E AQ=RG 'N>()'>99( E'N > () )'(Q=R! B6'Q93RQ9-RQ9 () A ')>()!" R" '-7(# E : ) )'J(% )'J ':7277( )'( %Q=R 'Q93RQ9-RQ9
PAGE 151

>X)'($! )E ) R "? '99(A "B 9 R """ "JN9_F3UT9 ""DJN9c %$"0>'>9>( R J(A 97=

PAGE 152

=7 <%$ 6< !'Q>>R9=8)9<7( :$ \$\ '9( '(%\$\F3 '>( '(\$\F3 '2(A DDD '7(\$\F\$\ '=( V $'($ V F'T 9 (\$\ ( V $'($ D '(\C\F D '<( V $'($ '('(\5(\F\$Q 8 ($ V @" '( $ V EK '(EK'($ V V '/(\$C\F\$\\C\ 97

PAGE 153

'93(' 1=1" (\$'(\ P UW99DYYY dDYYY)'i( YYY YYY NYYYN YYY 'W(YYY A DYYYo)'(

PAGE 154

6*A*6*40*: Q 9 R:A$$+*:$0E B:$4$>-'9//3(9=7>)9=-8 Q>R $V0EB +$+0G $"4@::@*G 493H#"'9//7( Q2R@*HC!"&0A4 A:#:#" DB+/7)3<< Q7R@*HC!"&46G AA:*# :#" DB+/-)338 Q=RVA$4:0 *0EB:$4$G V>94>'9/87(2=>)2-> Q RVA$&*:$4 $V>749'9/8<(9<3)98< Q
PAGE 155

Q99RAB&0@*: 4@6:$4C8/)8-/9'4"9/8/( Q9>R$B ":+@%0E) B6@$$992'9/8/( <)-2 Q92R,B!:$:"';(): @4:*4 =-'9/8/(992 Q97R6,*@:0EB :"@:64 :V7/'9/=>( 73/)72Q9=R$:,4$ +04h!'9/-7( Q9-R0A@6$G "" @$6 +B*"$ '9//>(2-9)2-/ Q92804$#" $]'9//3( Q>3RDC@%:4 :@*:$$$" 922'9//>(/>-)/72 Q>9RBC,:)+A: $B),4h!'9/-2( Q>>R 4DC$@$+),4 '9/-8( 97/

PAGE 156

Q>2Rh:,:%B6*:P% ":$:: 0'9/8-(4<8=-)8-/ Q>7RC:D!:+"&*"+:$ 6"':9//2(V2=42723)7<9 9=3



PAGE 1

? +@**4$&4&A,*0&4#B$* B6$C*4*,&C#:4B:,&6#@+@* 6*0#6:&4: @ :0:#"9/<< :#"0C"9//> $ #"0C" C+ $ 9//

PAGE 2

C+ @ D@ +A :A0! A6

PAGE 3

@'+C$( &0EB #:6 +$ $ :6$0 "" $F $D E'0B(G H"DG "" 0BA E!G 0B "E $""" ": $

PAGE 4

0B& I )'J E $ $!2)'J($ )E! 0B 0B" KG :L $

PAGE 5

0&4*4: 0 99 99 "$&%9 9>47 >0EB= >9= >>C"&0EB= >2/ >7*0EB$92 2#$:#9/ 299/ 2>$:C6A#>3 22$6$A:#>> 270EB$AB )#$:: )#>= 2=$46$A:#>< 76A29 7929 7> )4'J(22 72$6A )4'J(2/ 77$6AB% & )4'(7< 7= !:'()6=8

PAGE 6

7-06!-3 =$46-> =9-> => J)4'J(-> =2B%&:)4'J(<9 =706!/3 40/9 -9/9 ->+/> -2+&4099> <0977 $ $+&C976978

PAGE 7

$E F H" )% ':>>($E" )M(F;0EN'$( 0EN0$(FM $O H" 9 P&&& B6*: )G E9/87A Q=R"E > () E JE)F )'( 9

PAGE 8

"':>7(G !BQ93R 'N > () "B :" 6'Q9-RQ9ED $"""!G E"02%! B6 G 'J() ) F NJ J 9F3S F9 F9D E # F $

PAGE 9

#%& T U<9'$(K '$(F;'$(F '() 07% )'J( )E # :>7( /'$(K "! $ )'( ) '()' F )'L($ )E! :!'() "G !: ) 0= 4" E ) 0 2

PAGE 10

"$"0< A" % <>. ( TVT <>.W0TV ) VT&<>. $2 % #6'B!( T#6'B!(" ;XT@6'B!( 'YZW(Y[* ( + )Y(\\Y\\T + T ( +% I@T6 +% $WT*E$$WF$ $WT + TE$$F +&#+ M]EOT" *'$(T:$ )-. $(TM^$$W) 9 OH" '* % C '$(TC$ 7

PAGE 11

!" # 0 '>9( / B > 9 (E $!"G E"4 & E $"" ""D E !" E $ % !" # B"' > 9 (" 'LOF & 0" F39 =

PAGE 12

, F N=>'>)>L _F3 JF )$LF T(F$'>2( JYW '>>( '>2( N 9 L W9 E$E F3 @ F F+'$( '3(F9: F3E)F+'$('3(F9 !& C !01 9 '$( 3 F3 & 2-# F 34 N'(FQ9T+E'(RUEN9A N'3(F 9 4 7)9 F)N'$(3 '(!: $"

PAGE 13

C N(KH" 56 7 '*$(FM$EE 89 '>=( "M$` LOLI3 H"" C 1 1 FM P'$( 3O C 1 F 1. H" . 1 F 1. FM :. F3O :H"" 5 F 54 B LN'$(' > > ( JSN9 FJN+E'$(* F () ; B +,)-."/0/ +")1&"23" BJEN'*$(D!P $ >9$H"" P & < ; 4")-110/ aN9F+N'$(+'3(F9 H"D ; 9 93 : '>9( ; BJN'$( <

PAGE 14

,"! "!$ :\\JN\\F\\N'$(J\\U\\EN'$(\\\\J\\ !P '9(!\\N'$(\\ > (!N0$(L?? "" 0")!!$ %EG !% %4! $E%G H"%" D, + 4+ C*A4&4>>$E 4+ H" P 5ENF:EN5E5EbJEN'$( -'0 %" ) '$( 0EN V%b$0EN E0$ "'$)Y(! 8

PAGE 15

+4+ % G E,:Q97R$ E"! + F # 4 $W$," 4+ % 99aN#F'$W$N9JN9(WF'0EN ?ZW $E Q 9 R 5671 6 $E" + H" "' > ( N9 F) '><( $C>> N95B =56 $( ] :V%b '$( : "9 'L$(0 > '$("%b '$( 3F +-* %( F'Ja .+. %( '><(+ "%B ;! $( +-. 3':%%(F3

PAGE 16

P 54 $( F3V% ;0E' % JN' % )";0'$(E )MOL 54 JN 9 97 $( J_')$(F3LK! "B""+F ) "$ )A9 ; F ?#5 JN 3F +' @+ : ," + L3" I +A ( & +B; :%" 4+ "LP 9 (+ JN0+$( C+ L'+$( > ( %7B7% :""! A ," + E 8

PAGE 17

+ F # 5 D8&E c A"!""G E )M MOJI3 N9 ')$()G ," B): +F*& J9 F 7FG@ '' +( dKd[K 9 0 +:)&4 : 1 F "P 333U390E") 2! 9 JE")RFQ, YYY*)R 9 ?$ 9 '>/( F """ '>8(4" / F /H// '>93(

PAGE 18

+W / I H/: / N9( / HI "" "ED &" B):% ) >9P&$ F JF*Z >;N9 ;J4 ) +@ F 0" + EN9 F$)\Z 7 4&" % b ) < 7 $ (3 H"D + H" Q 9 R JEN > '$(FM'( K +N9OFM N9O $(N9$ &" >> %""G e!$ T EN ) ""

PAGE 19

>>P&$ ,F G! F* N9 5 ( JWNf(JS 7B$5 ;7 ;61!" # 16< E "" AE$% ) % '2( D )'( ) $WF A$ )'($W$ 6'>/( ) )E$$W + (F' $(V I$WF 9 $W $$ )"P '9($$F$$ '>($$" )" 92

PAGE 20

, HL 1 FK 9 3 $ )'($WF'$( F T9 T9 $Lb ).MN LN9O EZ)9 )@ < $( )EF3 E"'>8( 2) $ )'( ))E C*A4&4>2$ 4 "E( 'N > ()"' > 99 ( )L'$( ,*&6*>9$UF ? >$ T'( 8 J OE P $WF$ $F' $(WF$W 0 ))>()P 0 97

PAGE 21

=%> AQ=Rg 9/88hQ98R "& 4+ )'( 9/87A% )'(G @*$>> )'(S 9( B 9 1?< >( 9 1 F9 F $F_'\;NB( FZ;T9 5 Z33U P? <5 Q F Q# =%> "Q=Rg :% )'(Z9 > F9 9" 4 )E" & " )E Q " "'>99(" >2>7 )'( & + D!K 9=

PAGE 22

>2P&$ *TTL JFJ_ d) (K TT 3)? +"@ *NF 57 *E N9 ) U *E' ;+( 'N>()"'>99( P -0 >ENF EN9 "JN9ZWF > T9"*"""M\HOE F9 9 iEFQ*JW*EZ 9 4%4R T 4 '>92( R " A E'>99( B" ," 9

PAGE 23

>7P&$ F /4 JF*_ I )N. N 7<7& JENF !0 ( A")& '>92(K'N>() '>99( E AQ=R A "B) :$ H> D"+ H HA H>>$>>+>> :E" +S* V ,'>/( +E>* F >$>> cWW # YYYW WY > # # F W WW WK% 9<

PAGE 24

8 8 9 F #$ E< #$ 7R '>)97( "G '>9>('>97( B "6 BKG ':22($ '( '>99( !E 98

PAGE 25

5,% < 5 "G E ) H" E 9/87AQ=R )MJOFdJUW'*_ 7 'N > () J )'( " !BQ93RG B H" 6) 'Q9-RQ9
PAGE 26

$ NJ" "$ '( N > ()' > 99 ( B6 + Y(D 5$B1 <, < : 1 F'3 BQ 93 R )( N B): M LOL9 )>>5 4 "'>8( +% "%" 9LK F (H( '2>( HS : '2>( F >> >> H>> $^6% H>> H>>4>>R>> 8

PAGE 27

" V # : # F # # # ')YYYYY( P F9 ^6% B" H( F Q Q < YYY Q(R( 9 '22( )9 T< 8 7 < 8 9 < B ? 9 05 F'9TE>(9L>): Q > '22('2>(P G! Ff+NX?) <9 F % 3 G & )<>'KJU(N+EN <>F %& LN<9L( U>F'9)\<=Z\>(9;> *B "29 :'Q93RQ9-RQ97R

PAGE 28

29PB$ <7 FJF 9 ?5 $ T@ (9;> L NEN+E) JN+EN < NJN9) 22$6$A:# 6'Q9-RQ9 YYWB;)BE F 9 / T 9 $) T< J < Q/ F / A/

PAGE 29

#'29('27( // N FNE D$ 4// D!"d H/>DVH/0 F %* B4 B6*:'Q>2R( :,%,EFJZ"b / !F*) /I F / Q?) HA/ EFQ933RE"%\\W\\: / / 9 ( / C ()*+, :',WNEN / FL,^6% B" / H/"/ """" "2>D O@ LK:'Q9-RQ92

PAGE 30

2>P6$P N'6( P]EF )$S FS ) ;SF PD=WX' +, ". FF$F3IF 3 S3(F <3 FFF 9 S ,F,F*;US %6& // 1%6). / LKW S F[(% 9jA=T90;+LFNLT90;+ !6&%6/6D-6/6)E60D:C6&F.G-6/6)E60DH 5 F &5 N $% %5(E L N9 F $Y O <$c?LLT9FT;TT9 ,T9Fi +6I [3,)> %* & 3 'T 3 T,T(LT Z >[>T9'TT9,LX %6&8 ?&?6H ? % U=TdK(f+FN=&<;LF =5 U+NF=U+jA0<;L ,N9FL9'LN<,(S ,N9FLLN<,NZ >F>) >7

PAGE 31

5;!" # 16<# 1 JF,% % JF, < $ ) U ))( %+ F .+ /.+ UF '2=( BQ93R":2> % )Y( ) "29" $ 0 B): ) ;0E"'LE F 1 '2-( 0 0 2% F 1 '2<( : % ) F #'2-( (,, :'2<( F 1 : (+( F ( H( ;) $ :2>% '2-( @ )!B 'YY(' )Y("22 >=

PAGE 32

22PB +F; (W )X?F N(W !)=:)& % )K")="L =")1&!:)=")K)=,)F AV0>! 4+ 9< B 0/ P0 ) "22$ 4K""! $ ) F 7)J<) : % F & ) & >

PAGE 33

;0E"' E ) 5( *61 <116% < ""0G 7A F E 4+ +# P N9 F ,0"IZ= A / 0 / J;N'$() +K JJEN'U(( [ &cL(W :U' D! K 4I9O ( > 8 K4 U$(F TE T9 Q9 4 4;0EN' JEN'*L() # 4 ; F NJ; @@ '28( $) '$))( '$# I F #I F'$W$(V I ><

PAGE 34

A:27"22 +# F $W7)B" F N9F !" 4" $ F$ N 88%88 4$F NJ;$ "22$ F L )9NNE() $$LF NE OK>\ #" $@B&6,29$6$ :#P 0 F FJ;#Z F F*Z ,, F N+E( 7D F'EEJ( >8

PAGE 35

' *F0)^J N < N'KN' F'9)<;(9;> &4F)KH+F0/ FL' > ))L)(NL)K N] 7 )N ,0"7 F'EX( J;T Q4 *EN) <"P F@,F@"FMF+ <)9 M4+DF P '9(9"P 6 K > ( > P 5NM'KN '2(<:$]+h 6) '2>(9"G 9 :$]+h >/

PAGE 36

0""6) ,"" # G $W$)'( # N PE E "AQ=R" ) 23

PAGE 37

;171 <61 ; 02$ F )A F ) NY_J)'79( F ^" N<;+E)) ) 15 $( 'N > ()"' > 99 ( )'( )E WF'$( ," )$WF$)9$ "$ I+'L(I I+'$E( '$($K /'$ F9 NI F" )EG D )'J(% :7> 0'79( )$ 9 4 F NEN+E) 29

PAGE 38

A '79( O:)1=")1& % ) K"P)1 )K"+,0F :"'79( ''K F %+ ) '7>( )EN EN ) I0 ) 9 VDNN E 6:2>UK%%A ) )'79( < K%D F W )J;( '7>( 9 ) N9 )EN 5>?5& N '72( k K &EN9 # N9EN; &E +DN) F :72 G F H Z3D '()"'7>('72( ) ) F3 -( N > ()'>99( )'( D"'U() )'( ) ) 2>

PAGE 39

! < K%'7>('72('J() :)L' + '( !J)'(:! '()":7= % "!: ) D !!' L) ;+F1-1/60 < ":79 E M@ + 'b( C*A4&479 )'J( ) $(X'$( N'77( : # F )J; 4 F3'77( # F+'$( 22

PAGE 40

=)'J( 4%X)'J( )'J( 7">-T7(7! N> F NYYYN N1 "% + '( '7=(; L3 N '7=( @ ,*&6*79@ )'J( G @ 1 '9( Z N9 1? J> '>( 9 1? > 2)'3( '2( U / W3 1 U > N9 '7( ?% 91F 1 U> '=( T9 F3 1?< J)'39( ( F 1?< 9 )'9( +P+'7=(" )'J P I+U')$(IW)A^)LN; '7=( $F$( % -0Q '7-( 27

PAGE 41

D ", l3V$)BJ'$('7-( $F3$D'$W(L 3 V$WbJ'$( '$(F3;'$W(L3$WB*'$($F! E'7-( V$WB*'$(0 )'X'$W(Q:J'+'$((JN D","&*N NYYYN'/'$W((RF 3 V$WB*'$( A$ )'( B : 4 '$W( P 3V$)B*'$("'7<('UX'$W(( L'/'((;IQW'+J'((N1)';'(('(NYWYN ?Y '78( **5* F.I-7H-D00QF6-D0FFFFFFFFF678* &O@ F$W$WB*'$( +9(P B N 9 F3$ )'L(Q=R < 1? ''$W(( .-=%-/00.).F-7%-Q00.R6-%0)3)-S-004 T '$W(VZ'U'$i((NZ) '+'$((I '$(,A 'U K '$((K $W''$)((UQ 'U'$W((N )''$(()'$(NYYYN ''$((jWR 2=

PAGE 42

B N9Z3'78( > WL3'78( > 1 U> +>(P F 9F3U7 )'(Q=R JF N9Z3'78( >* < '78( > '78( N E F + > '78( 71H* FdZ & 9 ) 7" F3 F3 & // % 7" L 3 N '78( 1 U> 4 )'J( U: N, l3V$ b* "'7<('L'$((WD +Q 'W'((N)'+;'((I 9 /'(NmWYN/'((RL )'/'((IUQ;'+'((WN;)'+'((;) 9 '(NYYYN 3 / '((WRF 3 "F$)$)B*'$(:;'$(X'$( " 7" %," TW)1 )% 2

PAGE 43

+2(PJU1l3'7/( D > 7) L3 1 U > N9 +7(P:JUT91F 3 D 3 N )'JTT9('7/( 1!& F 1!> > C 3'7/(% >" 1 U> +=(P:JF T9 F3Dl3 )'JT T9(> B 3 JF 3 JZ3 B 9 % 3 '7/( >>F='D(jk >: % > 1?< L3 '7/( >>&7->-14> >$ 1 U>'7/( ;';%( >" 9J+ 9J '7/( 4 F3 9J 2<

PAGE 44

'7/( > F3F3 F 9 % L3 N2 U'$( ? > F3F 9 F l3 7" L3 !D )'39( F3 F 78 1;'7-( $FV$U*:'$( &$ $$FJV$) :'$( )'39( 1F3"" + (PD )'( F'7=( I 1% &N (f N N K N C TJ;(0F" I 8 I+)'$( N&N $ )'(J $TJ< )'T(D "? $$ )'( > N9" )'9(" J:>g 28

PAGE 45

" )'J( \ "" ?A U 9 >" )'( ) ) ;5171 0/ 9 Z3D'J() 6!"" 'Q2RQ7RQ99RQ92R(!'Q2RQ7R(%H" """ $W Q92R! E)!'0>(!Q99R !E" $'J() H" B;0N > '$( ) D L3" : 8 % D F 9 "E'J() ) N*)*'7)93( 9 Z34 2/

PAGE 46

* G N = 5 D//@?$ /" F3 "+ N9 ) MeZ+EO ) '$NJ /+ f /%" J[E& ) N `/ +( M+)Z 1 E) =2 /EG/@ FdZWFdZ)ZmXc[:.@'7)( /" : )'J($C79 N ( $ )))))))))))))))))< )))))))))))))))FWF) 9 9 F /'$( :" 4 (;'$( T7#T9T# LI F 5> FX'$(LI'$( 3 NLL$+ 73

PAGE 47

'79>( ";Z)';( N VZ)I'$(J@'$(: #N ( $F$'$(LI'$( 3 N$:I'$( 3 F F $JI'$( 6'()'793( ) 9 //" '799( '799( "'79>(WF3;) )9 N ]7 ^ T 3 V 9 k 3 ; 79

PAGE 48

" U*I$ZYYUJIY V '+$JeIZ; ""'()' F '( ) )'* D!'()" '792(6'>93(" B): ) $ 4'792( ,ENE)D!'J() ,D! 0 A!'J() F'J( )'J(," 4 "!:L'+ ) "'>8($ '>/( ( 7>

PAGE 49

HL ,P '+Z YXC&;/F /0X/% #" # 9 FT 9 Y'7)97( U) 0 HL : '79>(UE -5'*+ $E )))))))))))))))))5%)))))))))))))))))))))))) B" <+ 4 "4 BM $c)NU 3 OFM3J9 '9 B% 12 S'$(LI'$( 'E$L(I'$(3( L(I'$(3( U*Wi & '1ZJZ :UFL & +LO _))')$(:F* F NWWYN'(:&K &Z% 0-+06F1N 8 -;(0 C F++Z +J?Z)9++I( R0jk'79-( :284, F')() : +LL NYmYN'J)(' 7 ++L F R 1ZY 72

PAGE 50

HL P F % 'JZ( 9 FWT 3 EUWT 9 0, HL 3 "P F 3 ? $ ,"P 3 B MT T 9 E< 9 3 % B ? T 9 4 $ M3 % 9OZJ $ % HL $ P F U^Z > $Z * 1 > )KJ( 4 U > L)_1Z bb

PAGE 51

""P 'V( + 'V 'V( V V J93 Y 4 N 93 JE") : 4 '79<( '79<( '798( 7=

PAGE 52

4 + KG "" G G& F 9 )9 9 )9 9 && '79/( KTK7WK '798( G& '7>3( ;<"# F D )'J( F =;> ;<22? ) '7>3( "P )NI LLT&)9)E)R '7>9( 3 ZF F 3 ) 9 5' '79-('79=( c $ 4% !'() 7

PAGE 53

% ,*&6*7>$J)'(" ) 0E$("'7>9( +P:"g 6! () )9 "'792(#'79-(P \ )VY'7>>( 77$6AB% & )4'J( 4'() D$ + 'J( $ / '$();'$(F3 : $'$() F (6!'^ '$((F;'7>2( D% + 'J( D ) '()'793('7>2(6 ) '()'799(G $J)'J( LI F F / '$(;EI'$( 3 NLI'$(L 7<

PAGE 54

" N # U'$(LI'$( 3 @ F 2&"Y9DUD5'*4 F 4+"I N'Z?(J A'()" /`/" '799( '7>7('799( F 3 %% ; 3 K '+EN=2$EK ;:8 N;'$(V_I'$(3N ,:,,, 3 /" 6$LI'$( 3 bM$3$L ?>K JI9O ^ '$(LI'$(3F NYWWN'](3^ "EFQ'%W(_ % '%E&;) R< J ) T B"%B 7 '7>=( "F 3 TT TNJU 2%% 9 (T % 9 TT'T U T 9 T T'T ( F T 9 T ;'$(LI'$( 3 b+)IN;O0L K +E?O) "IC+ =2$E: E W 78

PAGE 55

1EK F3 TT &* 'JSN*$ "5! ^ '$(L)I'$(3( F 3 9 S)K$*Z '*U$Z YYY)K1Z UJYZJZ )(YYT 3 [ OD @J .+/@ "@, A4 B" =6F@J -%F .+/@+/@J UUU.+/ILUCI@J L -( 7 !+'7>=( 7 ?"% T'Ni( #" '7>=( " '() F ) 7 '7>-('N 'N !( "'() )4 !^'$( W N 7/

PAGE 56

$ )'(! 'U()" '7>-( $" )'( )G """" :L$(F 6 ) B):'>8( '>/(, "P '+E^ '$(LI'$(3N N$L@9'$(3( U11mZW :;'$(LI'$( 3 L K +)INU B )@+;'$(LI'$(3 FU 9 3 FT 9 Y ? T 9 '7><( 0 H Y:$L "'7>7( 'E^ '$(L)'$( 3 )$VL(I 9 '$(3( U1Z G+ :L$(LB K +LO 6F1-0=&-="0631=6I)UUM)-\0 =3

PAGE 57

" 4 '+EF'L+E)')L(+Z F'+L)'L+E)+I( NYYYN E! + @ ?*?O LI9O F' (3 JNYYYN $ (H)9 FQ'%()0(;)R0j C H FQ'+KL(L'ZL('+LI 9 ( RJ0W U* 4+F FE( ;E"P ZNUJ]U()Y<) [TEZMT 9 TNJO -4@R &Q/R/QF6)%Q@60 9 &3 3 EUT 9 WEFc =9 '7>8( '7>/( '723( '729(

PAGE 58

"N R> N';JZUZ <Y L C 9 3 %" Z( & ? 9 4 $ M3 TN9O B$ % ,< F:6 1 9 P%1<%]0 .P+@< 1W = @@ .M@J &9 < F(LU / .+*I 4 = FQ*F4B '# 08 1 =>

PAGE 59

$J)'( < P @[[9 9 )W7X 9 F GV / U:(Z*Zi9 LYY 9(2= E") & GV %P V 'V( V 'V !( G 'V ('V (=X'V!('V!( C'V(V V 'V V J G )!( "* ';H('!!(4 G G *% G& >X)9 )'J('79/("K G& TK K G&* TK 7 NK #"% < P ( F (H( ($ 7) ( N (N & =2

PAGE 60

4"P 4 F >>G 5 !" ($4V4V 4 4 4 9 '9 7 ; F ; F J33 L&)9> 8**8 ,: @ >Wcm>iI 6 2Imj=)3W. 4 4 G 9 G& 4G& F 5 4G& F 5 > F+E"N 4V N 4V 4G* F 5 ", 5 '727( ) $(* =7

PAGE 61

; '7>8)729( @ $ $ )' !'() $N 7 7)9 N9 """" ( """" Z "" 7 """!"" N %P ,*&6*72W'$(X'$( " F$D$();'$(6!'^ '$((Fi'72-( ) 1 "'72=( ==

PAGE 62

+P:"g 6!'()'793( N9"'7>-(4'7>/('729( ,) Y +* '72<( D'72-(X: P % N ;$ )'J(5!$! 5 G ) C79 RN 3 4 N F N;$7;5Y 7;$ N F N N ;> 5n""5 T9 L 6'5(0\L6'$5( "" ;5 !: ;5?5 =

PAGE 63

: "N ;5";5" ;5" ?5 # F N T F'$N ;2N N ;5Y & QX;'$(N ;5 FQ$'$();'$(RN ";5 N ;2N N ;;5 F ;5 N ;62N N ;5Y&;56!'^'$((U N N( %$! +7!57 '$( $ < '$( F 6!'^'$((U N)N)( 0&6&@@$6h77$F ;5 $ )'J( ;$ !=) "'72=( 7 ? ( +P72"g "'72=(!G =)L(: 6! 7 ? ( 7 =<

PAGE 64

! )'( A"! )'() "": : )'( F 9 : / W'$(F34 +0LN B: F+!'$(N D*: !'5EL(U 9: N=05 /5 7)9(X'N('L(F3 9:9 N = % 3 : U 9$:9 "" 4 )'( ) ) = 7= !:'()6 !' )'J(6!' D '792( 0 8 8 K( 8 1 YK( 8 8 88 8 8 8 8 8 8 K( 8 K( 88 8 8 =8

PAGE 65

: + F;" @@ '7'+ C79 ;)'39(!:72 ;) 9! 3 () F N +' ) ?51 F32 DF3 B 9 D %& & +@M ?$ P I LK 0 E F :;) ;)A B):"'>8( @JFQ933 3 & MOE)'>8(P 99 JZ 8 : 46 1 3 4 ;";> b =/

PAGE 66

L'3() >;2 !> F 2' *: K F3;2$;2 FQ33933R:E >S K : ; F &< ,( : K 3 < 6:72"'7>9( ""'728(! 7-06! 'J()'793( ) )'J( 78 '72-(@! )'J( :!'J()G !G ""!: "7>72 )"^ !"'792( '7>-(0 " M % )'J( JU9!+% -3

PAGE 67

)" 9

PAGE 68

(671 6 6 1 <1< ( 7>72 ) "'7>9('72=(" E"G 4" E'&(' >9( (JF61-+/60 < D ) 9;! d )'J("P NF ,( =Q&Z-7Q0/-7Q06FN# 8 ( 5 0 ->

PAGE 69

"LL$(L L'$(L / '$(F D '=7( UJE" JYZWfU__)( F)))))8%)))))))5%*)))))) ( '==( '+)Z + LK" Z B %% '==( T'JT( IH F '=-( 7 T)+)N / ) F 3 T 9 U >N9JN9 Z ) N9 ) ) JEN9 MEILIE I #K %% ( '=<( '1 + LK N F3 T9"D$ H )'J( 3F3 F Vc'$(3 /3 '$("F ^V W'$ *ENF)L*E)5_Y -2

PAGE 70

)'(Q=R B""+ F 3 // *ENF # 'L( > Z N 9 """ B"" . F0'E7(+" N T 9 + K F 3 T9D '%(F+NYYYNII9 5. FQ3&IR + JF0'7(+F+0')$(NYYYN c 0'$(R J 0Z "'$( 4'=-("" +P $-I 9(F*'>E( '(F'()J '( '>N(F'EN9(N'E(WF 3 ) 9 -7

PAGE 71

" J > ENF aN[ J #L? U=)8Z > 'NF F 3I9c D $8( d%H '=)/( H (" LK" N@ '=8( 4 JZTA +FF VKL+)4" N (F 9 +EE /&&Z% "P I 'J(_e'J(ic F + JJ F 9 F3 8 9 c' 9 ; 0 'K < : 3 T>^EL( F EO $G FN9 FQdYYWd93YYY3RB0n -=

PAGE 72

"%9 K "'=-( '=8( L '$("'=7(KF3 N F < VK'$(N j)Nc < L'$(N < L'$( 'E F T ! + N9 F QN #* N 77 3 ;R3) V_N'(" 9 G 4cfWYYYZdR) : 5 '$(LF 27<0"* 7< =! "" LN9 0* FQ3N 3 3 RJN9 :F #$ % F+ F 9 3 Yj 3 RLN9 #'>8(" F 3 ) 9 aYN9F #&`G F3 ''

PAGE 73

" I ) P ) J* R YYY 9 W 3 9 > 8 WW 3 9 WK%A < K'=93( ) 4 < = # N "'$("
PAGE 74

:'EH(F G!4 ,9) 'K '=/( $FZa)))+IR+E FL>YYYJN9ZJ F0+N0 NKYY0+ a[QZYYYZ0RI fZFL<)'=9>( ; F "7>I A $@B&6,=90B )'J(P P$J !% ')L(F D FQ1ZYYYZ1R) +F F Q9 3 YYY 3 RJN9LF Q9 3 YYY 3 RJ '9

PAGE 75

\0U IIIIIIIIII> f ) > < > KLf ?0< W F3<<9T9 J;NFN*ENF A,AI ]+ *;& J 71 J_YZ 7#E Fc F07)J&E:)Z 9F3 EUT 9 JN9 &Z3FH/ FT *)D / T EN >NF @ JNN>WKWFdZYYYc) lNiF +G&(*B"8#@ WKF) [99 F<<9 JENFaN+ENF AA + 7Q@Q&6F?0 T b>("% I&A E& '(Z FTT<9 YY F+E 5 F0+,N0+ `+/)/&/F > > @Q/U+,)@& 3 L,)F% > 04\U am_F>NN>VUF_)_Y)9 > ENFJE N9 NWFdZYYYm &* -/ 3 <<9T E)( I +5@ '+5 & U *)ZJK c

PAGE 76

6:7>$J)'( 9 "'>>ON9( "A'(U 9 9($E A$<)'J( # F$$W N T -% 3 N "4 + $W$ $WF +&#+ F$W N" 3 $ )'J( + F$W$ *9P0" $F939 ""$=9 E&" >9" <3

PAGE 77

U8 Y: A=9P:"*9 (5# 1<%JF61-+/60 < :77 N " 4 N%" 6!'^ '$((F 7 )P #b 9 i ) N N 3 ) 9 DTK '=92( A >WF 2 @ '$WLAb0 ;JEFQUJWL 3 Z 'W 0H '=97( <9

PAGE 78

)> 93 c /F5 m=93c ) 933 /3 <3 73=3 8 A=>0"&'($=9' (*9 <>

PAGE 79

" ? " )))))))))))))< %%)))))))))))))))))WF 8 T ( '=9=( '1Z "+ 0EI +T & % ( '+()R22)>2-( "A $F$N ; $;))E ;5 5F F5O5 <2

PAGE 80

O5 F5 !:$;))E / '$(F;'$( @ + F # 4 $F +&#+ '$W$(I]$W$W$F$f]$W$ 477 $'$()+;'$(F$)$ )*)*+ )+VSW($ CMO.F O5 F5 4 '=97($ )'J(LK" $ / 9 "'=92("" "K N K N K TWWfW !"W" / 9 '=92( "$ E$ 6 477 FM$LOjFFL'=9-( $ % T'+L '$K$EJ(F'$L$'$)#E((F'$L '=9<( <7

PAGE 81

6":77G '=92(, H / /+ 'JWZN'JJW( FT)TTFT)T)))))))5# EZMT 9 /%9 '=98( # <+ '+EZ #+ C 9 Z % ? 4 B/% X XF "/ F O JWZY $ / TX(K HS "" $> 7 7 "" $NF)XN;N / 5 1 2 JW( '=9/( H) N9 : k ')K 4)K/ LA% )'J('=98( "LHI9O A" F 7 T9/ '=9/( F 7 TXN9 > C e F 7 T 9 X Z e J '=9/( "P FWF 3 T 9 '=>3( *)** Z <=

PAGE 82

,"'=92( ,ENF )J>)!j>)Q 7 ccYaIR H5 #3F3 > K'=9/(: F=L<9*ENF3T9 afL>;N>)K.cF3i) "" TT 93 TT)] > Wf 7;) 3 ""P '=>9( [ & <&R" D* W KW \3 > ;f ") @)E'=9/( N K N K '=>3( "@ E"'=9=( F'*'E(N*;)jVZFET3N9E $!!K EK"@ > >( MET'J % T3N9O ? eKEK'=>9( '=>2( T
PAGE 83

c ) N9 ML 9 K )'( ? U ?D EN9 5 :)'(D B M e9 ) G K "P 9 1& dWJZ D NF < )J 9 8 '=>=( F 3 T 9 $" <<

PAGE 84

$@B&6,=>0B% J)'(P P e D )JI9O3 :F Q93 YYY 3 RJN9LF Q9 3 YYY 3 RL F 3 3 T 9 ++H)&a) 7 +")?&"F 7@78 & +@ 8+ &>>#E<[>>E & +f :M ? \&0& ++="M EUT 9 + N9 FQ 3 ))) 3 3 ) 3 RL FT 9 &Q^% JENF B 4%H5 &!=S)) 0 $@"71 $ :"'=9/( \ j ZcY)3 F3 W)9 P +* FaN ?# *ENF*E)UWSZaYZ 78 F' cc(cZ ? + &?+"F:@b: [ !C:&.J7P7Y0P U<<9T 9 JN9 FQ 3)3 93 ) 3 RL <8

PAGE 85

FT 9 ENF B% JEN@ EN) I WWYZ)U 7 W(W JF (88E4 JLJEfL&+NYYWN ,8 JE `L)/F; /F+-LL/X0.%QF/ # -!0F//X >NF?N)JZc) :"'=9/(IN9 +HFCC)FW)bb&OMFP62PU :E)NF >E)_N N:)/NcW F3 )9 # YVLWN?a)_NVWcF 3 ) 9 :)iNj:E)NN)cF3?) : $F$N ; $;)'J( ;5 !077 N J" $W'$( %" ^;'$( 6!'^;'$((U'JNN( @ +# @+&g+*#
PAGE 86

" / / F @NF 2#N"Y F &4 6!'^Z'7((F6!'^;'$(( ? ( 72 4# $=> D$;))E + F ["-( 47@7 F$) 9 Q$W; % Y F 4CK ) ;5Y $W$!E &$=> %)E *>P: $F$N ;> X-5$%+) KC T$ L F;' 3 9 (' 3 9 ( F^2 =)% I )EE ;$ 8 G 7 98

PAGE 87

4 ;)'(')E(! 8 A=24 A=2P:"*> A077! '$(F; #N! T'$(F # T F ;# T ;54 (6!'^;'$((U> $=> + F +.1 ':>2( + F # A*> ^'$(F &4 6!'^7)$'$((U> 89

PAGE 88

:$;))E 477 G '=9-(,"G 'L 4+ '=9<($ 4# $($=>A=7G ""$=> E'&($" "&" >2 6&G & )'( R$ F D$=>" )'^6(A 4Q ^6)%^6" f".EQ>RE + 6"^6 ^6 4# $( A==" 4@ $=>^6*>A ^6$=> !"" "$=> 8>

PAGE 89

" 93 c m:^) 93 c 93 j 933 /3 -3 73 8 A=70"&'($=>' (&')(*> 82

PAGE 90

""^6^6" @%f!).Q 8 R "M"OJ@M)OL <7% // O>>9 &D!-C/ $( & >>9 F >>I $W( "">" $=> 9 "G A=-!' "(""^6 $=>*> 87

PAGE 91

6"6(F 8 j A==0"$=>'(^6'( *> 8=

PAGE 92

93 mp 93 c ) 9>3 933 D! A=-D!"$=>'( ^6'(*> 8

PAGE 93

?671 5> % N ;5 *9 ;5 !> A=<" )73 eD A=D "$=>&^6 A=84""&$=>G A=/! '"($=> ^6"*24! ""^6$G => 8<

PAGE 94

)< 9>3 88 A=80"&'($=>' (^6')(*2 99

PAGE 95

93 93 c )2 ) m< 93 c 88 >=3 933 9=3 D! A=/D!"$=>'( ^6'(*2 8/

PAGE 96

(;!1 6E< G E"'7>9('72=(D A )E! N : ""% """"LK &""4 % )E! B'Q9>R( /3

PAGE 97

' <<,!< 07 ) E1 !B : "'7>9('72=( $ )'J(% )'J(' :77(D! '() :' !'() 07 )'J(% )'J( '() !'() "% %$" /9

PAGE 98

->+ D @*$-9%" '( < L3"JFQRB 4 +PQ>3Rg % B %% 0" > F 1 ( 4; N % ;"A;% B %% B""L) >14 )$(G B):% )'>8( Q=RA"U 1 + )U$,I) />

PAGE 99

$ @*$->:L'>8(@ Q% .Y$ ; U'$( '% .( +P K 4 'L+ *(Wo3c C (K$'N WEK 7)3 > +(SFJ'ND(EW ./ / F9 ^ '$ 3 ( 3 3 ("" '% EK Lc('%%E"( OY& K N "Ah Q=R!'(E :U 1 U L3 'h-..> %" YZL N"I M "0 9 NF$Jf?ZiWYJW UF /2

PAGE 100

EK $ &A-O)*0"^Q-+/0Q / > ZN (W i5)))))))))))Q&T 4 A A : 4'$L 'L + "" LFd D G :+Ll^ + ,"'LLl 3 L)EK -)0"& $( -+/0H@ ;F ""G g : )'J(% )'J( ':7277(07'() )$0'E($( "'792('7>-(D '792('7>-( 'W'+(W > '+(( U> ^: "" "" '792('7>-( A@-9 /7

PAGE 101

%"+ %J)'(% J)'(!' = () "+%"J !"+ !!'() :'$(F $ ) 1" Z$(B):'>8( $+E"F $ )'L(, F $ N $ M3 T7)9O P & > L[W 3 ? J"A:72 $ + '7>9(""" $% )'J(':77( ,P 3 N0; > /=

PAGE 102

$ ,K M3 TN9O < "P C 7 A "$ < )F ^ iWEFc 5(5. 7 \ 5 'aY2_Z B 3 ? (22 '72=("" 81 )'J(% + 'J(: B): : cJ 3 J 3 c 9 UWJKJZW JJZo UJc*Ld 'WJZmJZ 'JJZ '5 7 ) 9 ( UJI cJi) L P ,E"FN9< /

PAGE 103

$ K iEF -'0 AB W 3 U " F 9 NNS6 F K "" '
PAGE 104

FM 3 % 9O*)'J( F "E'79-(%*)'J( JF N " "'7>/('729( C*A4&4-9$$ 4R "* ) R "'-7( "07 D ,*&6*-2:0 # 0J6' ": -0 )'J( # AR J( FM3 % c/ '>( N " # 4R" ( FM3 )N9O ") +P:7>7207g 4) ( # 4R" G "% ) # 4R" >N& 6!'^'$((F / /8

PAGE 105

:) >>! R (D'() 6'() ) 8 N9 F J / )R OEGK '-)=( /" ) )15 3$(" D??1 T> /`/" L )9 NJI // 1 # / E ))))))))))))))F / F 3 %% U* 1 P UJZ>ZiU*c*Z ; R ) F ) / 0 % 1 k UJ)JZ UWJYJiIZ 223 1 4"5672 ))))))Z Z UWJYJ)))))Z UJ))KJE))Z UJII)JII?Zi : kUJ)))))9)J))))))Z ; b 4R" '-9(: B N + F' H 1(" F 6 '>8( F
PAGE 106

$ H > EN D F <" N T9 " 9( H < "P I : UJWJZ E+U*)J( mW[ 8 9 ))i)Z )Z1I?ZW 'E))LUI_IZi i 3 Z -,IC0-"/0 'E)2)(YYY0)2IZ'iEVIZ ;Z NU" U*ZJL UJIJIZ j IIIZ JI 9 3( UJZJZ ( UJWJZ 'ED)]#)('E#)( F NT 9 '-<( 4 88

PAGE 107

L I" F F) ):I) ) O%% ) '-<( UJZJZ )) 9 _3( UJiJZ UI)IZo @" 4 E Z ;_( UZZ 'L) )4'-=(E FNFN! 'J() b 4" J( 8 (" B" 'J() "% ) @*$-7: 4R" B):'-9( 3 N 8

PAGE 108

" $ "'->( B'-/( B" '()'-=( F "%* )L' =%> :"g : O "! YYYZ '+(Z 79L '-/( +6%"+ % # 4R W(Z! 'U() F *% 9 "+ %D # AR" U9 !" % 0 4R" "? 9 F3 R" "'-7( F3 RD 3(" 4 ) 5! : "L L" % 8

PAGE 109

-Z3 R2 3(" +ENFcWJE E R ] 1W _FE)' )( 4'E()F T9 "D 'N > ()' > 99 ( F T9AQ=R J) 'T9( 1 UN9'>9( b AR" F9! U() F 9 F J%! aI'+(FJZYDF3"+ ,*&6*-=: B 4) 9(, H>> M;!EOEFZ B): 9 ( 3 $ "'->("'+(9 E B N9!' () "J > iE)'+(F3"+ ) ')9( 1? +PA F3 E)F': E)>Z(F3 "+:"+"+ '+ F M+YYY+<)IO" F H 932

PAGE 110

H8 '# >3 ,; 25( 9 H :E)'+(F3ZEK %@F Q3YYY39R B J F H F 3 :EK E I9 L3 : Z3 E)F K H 3(d"((+ Q=R;E)F3VL )'ET>( 1? 1? F^ F N9$ ) 'T9( : B 9 H > 8 (P H ) 0 < $" UL)9 )Z UJ3J3ZTWZK UWJWYJ9 B+ UJIWYJ I Z -'80 937

PAGE 111

:a)P'+(F3 F'E) F 3 F 3 % -T94 B 9 U RKG!+ F F 3 &-="FM0&OQ "'J$(F @ VFM^$L 8*9 EEE K L :$ )'ET>(! # F+ET > '$( < N bM$E$<)>LOFL =,Ic '-9>( 4$ 9 F$L$L)+('-99( Q RB+ &-="IM@1=@<&.="I4%0J&8 4 'EI > '$(3( L$EE / $<)9LO FL / L :$$LqEI9 $$LbE$3$LO #'-9>( $ 3 B$EE$<)2LOV+L$(F A@>Q=R$\" )'ET2($\ $V:" L$(F Q=R$ )3KT2( E )> F'E) > Z(FdZV = ) 93=

PAGE 112

!"I > '3(F3V E FN>$J) 'T9( ZN> $:)'T7( $J) 'T9(g 6-=$B0J' " F9 $ ) 'T9('()' F 'T93( )'()' F' 9( %^ C*A4&4->$B 4R" ""3U ?% > U+)NJ / 0 1 F[ EF))))))))<< T))))))))))))))))F 3 F 3 %* $B Q 'iU("'()'-=( )L'$( 0&6&@@$6h -$ # 4) ( U9'$(U ')/ $ # 0J:6' " 0/ $ # Q5" F -' ) / 3 ( +P F3-= 1 U N9 $J) 'T9($ ) 'T9($B 4) T93( 1 UN9 F9-= F'4 F3"'$(U N9$ ) 'T9($B0J:' 'T93( &(I 9 '3(F 3 %$B Q 'U( ' 9 (g 8'

PAGE 113

4" %" B C B" "VM 'Q>9R==2)=-3( YYYiJW(F$$))) $ ( 'X'W( $ "Mi?O Qi I< YYYiR K 'L(*S! O : 'L( L 'L( F $K K E O : #E(F 3 m7FL)ME>T#( 29'( $ "$$ \$\ $! C "E" 1=1"" Y/-8 UUU1/7-8 )UU) /-8UU /7F-8P1=-8 Y7/1-8Y7/-8 YV/-8UU @#6 Y7/7-8 93<

PAGE 114

@% 4 :' " @*$-<$ 0J:6'J(" Z 1M "< DD 0 $L $)YY$ 0 / 0 F^'-97( $$ O" < F'e M $ NN9 O'-9=( +P:$ Z %D C7 C +C->" 3'() ) $(:" F 1 'Q9/R->( 1B N 7)> M '^(Z N>'J()'-=( + A M 'J() @&L3 )1 FNJN > '-=( ") ())1 *NN> F R" N9 N,$'iNN(L:f = 7"R '-9-( FENWFN N D/"9/.@ LL 'LiNJJ# /"/@ JiZ_ &'NN([ '1Y + F 3 _UJN? *" () DU'*(F'+LNNN H $!LNNE+ 0 1 3 U 9 A F3 "FM P D^ !NNK$JZWYYY )? C '-9<( U+N / E 6NN ) N=NN 8 938

PAGE 115

4 N9( N9(" :%"$b %& ( J(" +'(Z N>D^E(F3F3 Q=R" +: F3D'(+ '(U 7 N > '+(Z N N>+'(UNN> % AF3 !D)% "+%:D)+D) %"VV'(F3V 1 (U > :'3( > V NN> FM 8" OFMJ < +N9YYYZ+LNN() VWN N> C O = G :NN )"VNN > F OO#+O&O+ )E O8" N> 'Q9=R++)8)93(" K B KG VNN > KG VNN > K F K @ $VNN > )D $F 4 $F # 9
PAGE 116

$F "> VN N> "$$WA" ^+EE(F > 3 O D(F ?" NJ /" 1 / 9 WN FLJNWN?N* FiN9 <) FUJNUN9N*LWNiN(:L( F3) FN M$L #K $LO )" 3 + < 9L #=d+)1M JEN K AV_N N> "$W M$L >"K $LO0VNN > ) 4L )LJLO:L! 4 JN9ZT+ENNON>"B):G UN9" )+N9(T*NNL) 0 VNFL K E M K LO K E ) [<))& =73/="/= =7="cF :M$L+$W+$LO )+" M$L$+$0M K +E d=@+@F@+/c<=-+M <& F@+ = M+ 9 QFU+Q@U 8

PAGE 117

NN>"NN VNN > "ML K L K T9 )LE : M+Z & YYYYJZL*KL*KL*E FL N $c$L$#$#7LO "'(F N9 N > ; !"# @ / )" )" I 6MLOF ME;OMF I N I N $ 'Q>>R>39>=<)>->( !$ > ()VN N> VNN > ): + -U/U0&F/U0/ VNN > ):K'Q >> R2>-) 2>8(VNN > + Y( $'N N>('N N>( R E" 4 0 N7N> VNN > ^[k 4R4& 4@+4 F b'WN`N > (W'WN`N > ( '(

PAGE 118

6$WF +&*#+ A'-98( 4#+4& # $F 4R4& '-97( )A'+ FJe $ 4R4& $ $ 4>54& $ 4R#4@ $ ))Y $ 4j$R@4* F #$ B &L$(FN N>:" "L B0 7NN> F4&! ) $(F^EC$ 4RX $YmY$ 4RX $ 4R#X $YYY$ 4R#jAX FJ( "B07NN>: 4 Lm'+EE$(F #$ N( $(F N> %&'$ R X RL G R#RX >OAX "#$ "B0NN>"$'))J)>('N N > ( -2+&40 D" $B 4R" 4R" 4R" "? 9 9 (D" QR" U'99(0-/ 4R" (U'99(" ,*&6* -8 $B 4 6'(' "? '99( 9 ('$(U2

PAGE 119

'>($ )' U'99( +P:"07 1 U2 1 U2"'9() );0' L K >OA :72! )' '() )"'792( D' "? '99(-= '792( d% C -> Z4 ' "? '99( : b 0J:'9 9(0+b L F7 $V 7 V 7 FL$E $2LO A@-<"+B 1 F7 52 % FJ$$$$^$$$F3'-9/( @-<'-9/( $XR F:$ E=$ WE$F3'->3( XQb R $ :K 4 R 77: R \C RX W= R#R F307' >9 ( '->9($ 992

PAGE 120

'->9( @$" '->9('T$( \E R/ # ( ## T$;(\F3VEJ b :"'T$( 'T$( \_ & 4P '6)$;(: 3 4P4 F3VJ07 A'T$( \ R )$;(= 3 ) $ GP )$ D $(J\F3 /& J b Q $;( Q F 5 3 )$;( 1 RPQ3PQQS \F3V=J b '->>( *" X J b XL N A& & J b J C QA \iNi Q'A+Q3'A&Q3Q'A& '->2( Q7 F3"ESJ07" 7 J : Q7 %" 997

PAGE 121

"" Q7 %C Q '-92(P Q@7 F\E QL7KQL7KQ#QL7I 'N(BEE(B'EJ)A(BB')((\ N\N(B'N(( Q#IQ#Q7I N\N( QL7IQL7I BB(\F3 L i07" 7Z C 7 F 3 P J_#FF > \ > ( QOQQYQ8" N>\( QL BW( QQ N>\ QQ QQI N>Q QOQOQQ \ N>\ QIQQ#QI N>\ QQOQQI F3 LI b07Ab07"% I b 70 L FL" R "$ R F$ Q F 3 L "G % QIQ"QQI F 8/[e 4" T> \ QQIQ#QI F3 [C b b -';0 4$ R#R,$IRR ) ,D0 F3 [0 b -'(0 (

PAGE 122

"'->7('->=( A" >+$ %+ 0U<:'99( 1B 2 "" +$P: % : %" R A';' F7 7"D R ;)" R "$" R# "$C" R# -CW G 0&O@%Q4:F @ R "$E6 -'(0 9$F$ +1/ R#KR KR@R ) K0 F3 [' b -''0 C U;$ >$7 $ : RR% $;( R#% $ FMO $"R% FM>L7O*" Xb XR,jKIK

PAGE 123

EEb0 7 < G 0'->-( < < \ KR#KX>X 9F3V G '-><( A XG 7 FN%%B07 b C A \J 3&+AC 3+EAC Q7 F3";% 07" 0:X'( 7 %" 4@7 %!"" 7 F 3 4@7 \FF GK WW,KJZLNJZ ##GKA FdZ"JKW'-)>8( 0F RN< F$ > J>'->8( \J RTK J > R#.KR#OA LJ 2 ?F3V% G 07 K WW*i K 'WW ]>L!F3V%07'->/( : N< RT "$ > RR# T < G >R T < LO RR# )$ > FMJJ 2 N '->/( < \ R#O J>FdV G 07 4T$ \J'W)$;(JJ>\F3 OXGb 99<

PAGE 124

" & 3 T $ G& b0 7 \ 3J& 7& \l3 & WT J4G& J> 3 $ M 9= EO'-23( 4F J2 '->8( R# F$ 2 J 2 W )$ G. bMJ 2 O'-29( : J> J 2 N< J2 R# )$;(MJ>OMJ 2 OFMO 3 T$ G. F +& < T D "" W "'->=( R "$ 3 "$ 3 " 07 A'-98(EE" 3 F ;; F$ : 4 F$ 4 4 #'-98( "; F :) 9 '^) 9 (W,W^ '^( F ^L^) 9 '^( F 4R#4I 9 9

PAGE 125

4 "$"$$ $W""A 4 4 3:3 "$$ +44 F 4#+45 +EE(F3 $$" )" $ )V 7 *""$7)"G $$ )"G $$"$$A" )$ ) :$ ):'Q>>R2>/( 4R4&4#+4'-2>( R "$ 4 ) 0 $XR F X RX R#X R#RL E F $ X C X Q )9 f 99/

PAGE 126

$F'E RXR#X F =J=2J= $$_< / $ $ $ $ $ '-22( O,>>9>,>>$>>,(,>>$> 6 jIR $ !$";'L(*; 7 $! 'L(% R (F^" ;" R X 07+@-< R %E;2b b dj 9 R ^ L % 7"F7RX N 'F R#X N R@RX F3 *"'-22( E$99<9$9<9 JJ= O< $>> ,$><> '-27( + J2222 $$E"<" ?D*E & 8 '-2=( 8

PAGE 127

4" E4EL'-2=( O( /0 9 $$$$ 9 $ > $ > $ > $ > 9$$ >> $E"$" > i 7 F) '-2-( :'-2-("E 2K @ *N & Z / UUUW NF $ m 9$$$$ 9$ $ $ $ PPP P $ >>,>>,> 8 '-2<( '-2<('-2-( X X '-27(" X R#2R N ./ Q)6N; R#NRXRX '$(X'$("9 X R@NRR '-28( C79 R ;)'J( ? '99(

PAGE 128

D$ )'J 'J(U '99(A'-2>( R#4#4&*` 4@+ F 4& : F ) 9 $W $WF +#+& #'-28( 4 @N 44&4 $'$(F'$( U <9 9CG 79$ )'J( ? '99( % + P:$% D" D D$B0'X'99( 1B 2$" :$b0J'99( 1B 20L$(F7 $$ V ; V 7 FL$L G<8; @

PAGE 129

6"'->7('->=(6 :K Q '6 %, D6" 0 9 P:$" 7 '$(F'$)$(7 6"%7@L < +2J7( "%"6"$ :L'>9SEL("%" 6W"$6"% 6WP '6W)$;(F3 '6W)$;( > F '6W)$;(]F > '6W)$;(F '-2/( '6T$;(F^ '6)$;( > F '6)$<(F > '6)$;( 7 F 2 ) 4 L Q4 L Q4 6 6" $9 $9 $9 $ NN4 F N "%"6: 9>2

PAGE 130

':)9(W'E:c)9(G "%" R# 4 ':K)9(W"'=)9(WF NNX E'-2/( WW7_>2_>>ZJEF 2X >2K>_W> $ 9 $ 9 $ 9 $ AP =)9:F ) > ) ) & & f ) & ,, F; '-73( 77D N8N J]"'%"( 9 R EK "'%"( R# E c:j9 A'->7( F+L$EF$ =? Q3 @ Q3 00 1 F3V"b b '-79( B Q #'-2/(BW 0 KQb QKN8UNL '-7>( < QK L < FT(Y '-2/( BSBF > '-72( 9>7

PAGE 131

D!'-72(! QQ E Q : Q BWB]" QQ ABWB]'BWB](W B]B]BWB]" b )LOA" q N QQ :'-7>('-72('-79( ()* *+,*-* 4 1+/W :]B'LBKL(F Q F3 A'-73(L N J) '-77("J+]J N ./$++,* ;2 < %F 3 N N T9> QL b NLN<9 BW]F3L" R# "$ N R# "$'-73(L N L:BW]L3 9>=

PAGE 132

'-73( > MJ]J>O UXJY 3 F QL. F Q F'L+L( ," R R 7 '$(F '$)$(7 0>P: R 7 '$(F '$)$ 9 ( 2 '$)$>( CL' > +2("%" R "$>E" R "$>: J'X>ZJ2("%" R# "$J>E" R# "$>6 "%" R R#: R T$ 9 ;(F3 R$, 3 [$;( > F L 'W)$ ?;(J> FJ R $;( 2 F > R#,N8 J R% $ > ;(>F3 '$W)$ >;(J>F3 + R R# R F E&R `F'=I 9 (VW=W '-7=( 9>

PAGE 133

"P & F C F F%F // 51 3 %R &D '-7-( : >$F$ > '->7( P \+> Q < <* @ B>L>2Z\F3V(b0 7 '-7<( :<>)'B>( Q# FM>OZL'-7-( Q ML 2O)$" X b b QK< 9 "b0 7 < b0 '-7<( < < %$ \>Br>E XQX \F3V07'-78( @ X FL'-7=( QX FL: \+>Kr*" > >KEFd) :M>E>LO"G % Q< b C* ; ZJ>Z>PO)A >E)@MB > +>>JO BL>BM>O'-7/( 9><

PAGE 134

4 2 FJ'-7=(BF / L: '-78( :'> NN9 >E)@MB > J>EJ2J>( MX? @$U" 0-W=3( '-7/('-=3( Q<< '<7d+1/ NL c<7-+15/+1c 10 ;" < BLFJ :BLF 7N ;3+'-78( \>J> FQ F3VB07 4 FJNJ]E"'-7=( :">EJJ2JL 7 F 3 BE = >F 4 B=eF3I" R# "$ > L9 T >BM>EOA"'-7-(>E)@ M+2O)4 R B > 9

PAGE 135

J _]2 3 P $T$ > > < W 92 3 b $ 2 3 / B > F $ T $ > 2 3 $ 3 ( $ > 3 $ > I 3 R 6'->>($ $ > QC Q!XQ,XQ,Q!X & 3V+ Q# 4 XL7K -H %I 7Q \N"0X > 'N !0K B&NS(B\B > 'N ^ 5 (\F 3 KQb 7Q 7 7 F 3 P \" Q < BBrB > i\N\ Q < O BrB > B > # \i(B > (BLEB = B > i\N\ Q < QLQQL F 3 KQ :>" R lW K >E "" \>B > i H G DGD5 F 3 V 0 4LMB > #BLB > B > #O" Q!L Br QQ!L Q!L $BL$B > B > #T3V b '-=9( C $)$ > 2 $T$ > 2$ 29 W 9$ B > F 4 R "%$ R AB > "% 9>/

PAGE 136

$T$ > :B > Q "% '-=9( Q!. $ Q < $ QQ!. F\ Q!. BrJ QfQ. F3 Z8 4 Q\ "%@ .%Q 'BW(W HBLE QX E\F3V 8 Q B 9 \ QXQ#X F3VZ07'-=>( @ JZ' > i > > Z "%"BBW"4 7 <7L ,(Fd) : Q#XL F XQL F'E3(F3 QgX >(F XQ( J A %" ,KLEJ>,ZEFd) 923

PAGE 137

:J N ;XF3 RN" R# J R ""% R 7 '$(F'$)$ 9 ( 2 '$)$>( 02P:$" =;-0 F'$)$?( > '$)$>(> CL'J("'%"( R "$J>'>>(Z 2= L"'%"( R "$>:'("'%"( R# "$J>E NE "%G ""$>" %" R R#: R,EL F3 R T$;(JFJ 2 3 4 3 F R )$ > ;(J >> FJ> R$,(M F 4G$ F -%QFD0+& R@ ) 3$ 99 9 Y 0\ 9 '-=2( '-=7( 929

PAGE 138

: FL$ $'->7( P \ QK BBi\F 3 V"07'-==( KQ# BJF > N < QK qMJEO#'-=2( Q4Q' FJ) : QK QQK '-==( 1? 41?F/<8F UW 9 > 32 37 % JNBLN 2J> N7JF'-=-( > F3J% %" N J:^L3 4 2 3)7 %]F3 D 2 L3LE@ < L:L '-==('-=2( \J(JB QQ F3VB07 :JB" K B0 7 FB2N

PAGE 139

Jb b < 0" < QQK &#-#)Kf10 "" X B b >JE(BKEF3 4 X J>E QN< F N< N'$ > T$ N< : J"J 9 KJ >> Z >> F3) ,""G > L3'-=-( BWJLMJ9cJ>ZJZ'-)=<( F>E$ F$ > '->7( Q kJ> B M> N > N >O'-=8( '-==('$T$>(; \" QLQKQQA F3V"b b '-=/( :P 9 (>EJ>EU < L > ( < >E N 922 ?

PAGE 140

;X QK L: B"'-=/( J_ ;7%>EO B* > >Z) 4 > ]M>E>EOBc+L] 3 & Q@BGE?GB H ;< & [GI L" R >EL>EA >EL% > :>E>E N >E LA'->7( < WFL \>r> QKQBr> Q7.Q07" 7 C 7 7 F 3 @!7! F\>Z QfG< K Q < < N\>B=>B > (F3 927

PAGE 141

"ZJB07:>Eq]E]EB> B0 7 Q!X F]E:" > ZL > L > ?Z 'L9 [L >(L9 N 9L9 BL]B\'X >> F 3 "%B07 1KL>>>Z>?KLL > \F3V%B07 :>E]E!%B0 7 Q<.NLUN< < l3 Q < )@M>(:" )@ L > +>_ > > >FdW :>E]>"" Br>BM>>O)'-=8( BLBM>O'--9( $ Q# BM]]E>EO '-=<( = 0 BM]O'-->( B]EF3Br>F3 >'L > LWL" R# $'$>( BJ>F 7N< QLDNL '--2( % 7 ;24'-=7('LBLL(F '>(F3: 3F'"Br>(F'B > ]>(F'$)$ > (']>( 92=

PAGE 142

$L$ > LC >E A'-=7( < ]ESB0 7 Q(< '-)-7( :'--7('--2('-=/( J"J )*VJ>Fd) "ML>>EO R + 7 '$(F'$T$(>'$T$ > (> 07P: R 7 '$(F '$)$ 9 ( > '$)$ > ('$)$2( C9R'("'%"( R "$L2E" R "$ > $ 2 ":L'>("'% "( R# "$>2E" R# "$ > $2" 6"% R R#: R,JGL F ^ -+UF .>@ F 3 R,LL '6W)$;( > F R T$ > ;(>F 3 '6W)$ > ;(>F^ R, F 3 R@ F '--=( 92

PAGE 143

$ R R W"'G %"( R R# P & F )1) 9999 )1) 999 (e J?,EX>J2 > % T>T 9999 9 9? &D -'''0 P : L$ F$'->7( '--<( \*E QXQKQQ F3 V07 : Q Q2 MJ( KQb BiFJ > NJ>Z *LD >3P2 3P7 % f+ NB:N2J9N7J F>) L99 T '9 0 7. F3L < L 7 F 3 J> 7 3 2f7k & 7I 92<

PAGE 144

4 U>2 37 %LF^$ 32 L 3 L f N :L'--<( '--=( \X>J_ Q4& BB"\F3V07 :U < LB"E 0 7 X BEEN < L K 0 7 K b0" K QQK FB'B7) KT L( "" 93 # 07 JZBF 3 T '$> T $ (; 47$ >L 8Q4P4 F3VB07 : X FN / TUL9 T" > >ZJJ> >2 Fd > L 3 -8 ( Q;L +KJ >= '-`-/( :U < LD J>EL4J>E B K b0 7 BiFJ > N
PAGE 145

< l3 Q( :BW>EF'$ > T $(>'--=( QQK F'$ > )$(J> :'--<( J" B:W :ML / LLO"G % Q, MJJ>O'-<3( / / '--/('-<3( WfY9 Wf QL MJJ> LL J J>O F:+'*X?OY 4J>E / L / L J]E / LJ>E / / T&TW)9 BJ LLO '-<9( :JE)@MBJ / LOBLFL 7 F3JE R# $ L& BWJ'--<( + J] BBEBF3V b :JE Q# Ab FBN
PAGE 146

( # b K # K QQK F QQK N < ( > Zi_ QX Fd_VE7) "'$T$ > H R # J] QX F 3 OX # b '-<>( @ X FJ>NL" W JZ>>K J 2 9 FdW ,"ME N LJ>EU < LOG M>U < LO :>E2E '--<('$T$ > \J QLQQQ F3V # b '-<2( :)B K # b TL9T2W B)F J>9 N J29 Y 4'--=( QQK F'$ 2 T$ > N8d $ QK Q < Q O '-<2( W Q J2EF3W 973

PAGE 147

:L M< QL <=d+/@ '$)$ > ('$)$2( R ": R $$" % : ; ;< $ .< F %,.% ^ ""L'+ F7 V 7 FE 9 979

PAGE 148

%CM9>2LO"V 7 )@ V 7 FL> .. O $ V7V 7 7)" $W" " %g 0&6&@@$6h-/ B 4) (' U'99( '9( 1? 2 > ( )'3 9 ( )'9( =%> :-2A -2' U'99( )'33( )'39( )'9(4 )'33(" + '&($W $F;B0 $9"$! -2077!9 )'&( 4)" '99(: + '&(""! 9 )'&(">" 1?< 4 1? 2 114? 2 JW'+$(FL$EE$>LOFM3 K >O R 99( ) > 97>

PAGE 149

?: b 4R W(E' 7(U' 9 9 (0 -2 E 1 ? 2 b VN 7(F 7F9+ 8 \ 1? 2 =)'9 (g E D 4R ;0 ;0. '9 0/ 4) ;0 \ -/;0 U -/0/ )'( 4 - 80 972

PAGE 150

<0 E" )H"" E AQ=RG 'N>()'>99( E'N > () )'(Q=R! B6'Q93RQ9-RQ9 () A ')>()!" R" '-7(# E : ) )'J(% )'J ':7277( )'( %Q=R 'Q93RQ9-RQ9
PAGE 151

>X)'($! )E ) R "? '99(A "B 9 R """ "JN9_F3UT9 ""DJN9c %$"0>'>9>( R J(A 97=

PAGE 152

=7 <%$ 6< !'Q>>R9=8)9<7( :$ \$\ '9( '(%\$\F3 '>( '(\$\F3 '2(A DDD '7(\$\F\$\ '=( V $'($ V F'T 9 (\$\ ( V $'($ D '(\C\F D '<( V $'($ '('(\5(\F\$Q 8 ($ V @" '( $ V EK '(EK'($ V V '/(\$C\F\$\\C\ 97

PAGE 153

'93(' 1=1" (\$'(\ P UW99DYYY dDYYY)'i( YYY YYY NYYYN YYY 'W(YYY A DYYYo)'(

PAGE 154

6*A*6*40*: Q 9 R:A$$+*:$0E B:$4$>-'9//3(9=7>)9=-8 Q>R $V0EB +$+0G $"4@::@*G 493H#"'9//7( Q2R@*HC!"&0A4 A:#:#" DB+/7)3<< Q7R@*HC!"&46G AA:*# :#" DB+/-)338 Q=RVA$4:0 *0EB:$4$G V>94>'9/87(2=>)2-> Q RVA$&*:$4 $V>749'9/8<(9<3)98< Q
PAGE 155

Q99RAB&0@*: 4@6:$4C8/)8-/9'4"9/8/( Q9>R$B ":+@%0E) B6@$$992'9/8/( <)-2 Q92R,B!:$:"';(): @4:*4 =-'9/8/(992 Q97R6,*@:0EB :"@:64 :V7/'9/=>( 73/)72Q9=R$:,4$ +04h!'9/-7( Q9-R0A@6$G "" @$6 +B*"$ '9//>(2-9)2-/ Q92804$#" $]'9//3( Q>3RDC@%:4 :@*:$$$" 922'9//>(/>-)/72 Q>9RBC,:)+A: $B),4h!'9/-2( Q>>R 4DC$@$+),4 '9/-8( 97/

PAGE 156

Q>2Rh:,:%B6*:P% ":$:: 0'9/8-(4<8=-)8-/ Q>7RC:D!:+"&*"+:$ 6"':9//2(V2=42723)7<9 9=3