Direct methods 653Here Yj and f3j are vectors of order N 1 - 1, Ci'j and Care square matrices
of the same size ( N 1 - 1) x (N 1 - 1). Then the unique sufficient condition
of stability is
11c-^111 < o.5.
This is certainly true, since C > 2E.
Proper evaluation of the necessary actions in solving problem (5) by
the matrix elin1ination method is stipulated, as usual, by the special struc-
tnres of the matrices involved. Because all the matrices Ci'i are complete in
spite of the fact that C is a tridiagonal matrix, O(Nj3) arithmetic opera-
tions are required for determination of one matrix O'j+J on the basis of Ci'j
all of which are known to us in advance. Thus, it is necessary to perform
O(Nf N2) operations in practical implen1entations with all the matrices
Ci' J, J = 1, 2, ... , N 2. Further, O(N[) arithrnetic operations are required
for detern1ination of one vector ,6 1 +l with knowledge of {3 1 and O(N[ N 2 )
operations for determination of all vectors {3 1.
vVith regard to all the Y 1 's, the same number of operations suffice
and so the tot.al volurne is still Q = O(Nf N 2 ).10.2 TWO-LAYER ITERATION SCHEMES- Two-layer iteration schemes. The problem statement. In what follows
it is required to solve a first kind equation of the form
(1) Att=f,
where A : H r-+ H is a linear operator in a finite-dimensional real space H
of the dimension N with an inner product (, ) and associated norm II y II =
VCii:Y}. In a common setting it is supposed that A= A* > 0, where f EH
is an arbitrtary vector. From the viewpoint of possible applications, any
iterative rnethod provides proper guidelines for successive determination
of approxin1ate solutions y 1 ,y 2 , ... ,Yk>Yk+l,. .. to equation (1) with the
.starting point (the initial approximation) Yo EH. Any such approximations
are known as iterations with relevant iteration numbers k = 1, 2, .... The
essence of these methods is that the value Yk+r can be obtained through the
preceding iterations Yk- 1 , Yk> .... An iterative method is called a one-step
inethod or a two-step inethod if only one or two preceding iterations
are needed in finding every value Yk+r · As we will see later, these methods
fall within the category of two-layer and three-layer methods, respectively,
on the same footing as in Chapter 6. vVhat is more, the one-step iterative
method coincides in fonn with a two-layer scheme designed in Chapter G.