×

Projection methods for systems of equations. (English) Zbl 0889.65023

Studies in Computational Mathematics. 7. Amsterdam: Elsevier. vii, 400 p. (1997).
In the major part of this book, the author considers iterative methods of the form \[ x_{n+1}= x_n+\lambda_n z_n,\quad r_{n+1}= r_n- \lambda_n Az_n\tag{1} \] for solving the linear system of equations \(Ax= b\), where \(\lambda_n\) is a suitably chosen parameter, \(z_n\) an arbitrary vector, and \(r_n\) the residual vector. (Related methods for nonlinear systems are treated in the final Chapter 8, see below.)
Let \(u_n\) be an additional, for the moment arbitrary vector. If the parameter \(\lambda_n\) is chosen such that \((u_n, r_{n+1})= 0\), i.e., \[ \lambda_n= {(u_n, r_n)\over(u_n, Az_n)}, \] then the method (1) is called a projection method. Moreover, by transforming the sequence \(\{x_n\}\) into a new sequence \(\{y_n\}\) by setting \[ y_n= x_n+\lambda_n z_n,\quad \rho_n= r_n- \lambda_n Az_n\tag{2} \] such that \(\{y_n\}\) converges faster than \(\{x_n\}\), defines a (convergence) acceleration procedure.
By choosing \(\lambda_n\) in different ways, one obtains completely different methods (1) resp. (2). It is the main emphasis of the book under review to discuss several methods of this type, some very prominent ones, but also some others which cannot be found elsewhere; special emphasis is laid on numerical questions, such as stopping rules or stability.
The contents in some detail: In the preliminary Chapter 1, basic definitions are given, and some connections for example with extrapolation methods and best \(l_2\)-approximation are discussed. Chapter 2 is devoted to the concept of biorthogonality. In particular, several (bi-)orthogonalization processes are studied. In Chapter 3, unified approach for deriving various projection methods for solving linear systems of equations is given. Building on the results of Chapter 2, the author discusses in Chapter 4 a variety of Lanczos-type methods. Chapter 5 is mainly devoted to a hybrid procedure (a combination of the CGS method and Lanczos’ method) and generalizations of it. Semi-iterative methods are discussed in Chapter 6. Here, semi-iterative method means a procedure of the form \[ y^{(k)}_n= \sum^k_{i= 0}a^{(k, n)}_i x_{n+ i} \] with coefficients \(a^{(k,n)}_i\) satisfying \[ \sum^k_{i= 0}a^{(k, n)}_i= 1, \] and vectors \(x_j\) which come from an arbitrary iterative procedure. Another idea, different from the ones given in the previous chapter, is introduced in Chapter 7; honouring L. F. Richardson, the author calls these methods Richardson iterative methods resp. projections. The final Chapter 8 is devoted to systems of nonlinear equations; here, some of the previously discussed methods for the linear case are extended to the nonlinear one. In a short appendix, Schur’s complement and two determinantal identities are recalled. A large bibliography completes this monograph.
In the authors words, “this book is mainly intended for researchers in the field”. The reviewer would add: “but it is also very interesting for students as well as for researchers in other fields”.
I have learned a lot from this book, it is well written, it contains nice theoretical results as well as many algorithms and numerical examples. I think that it is a valuable contribution to Numerical Linear Algebra.
Reviewer: G.Walz (Mannheim)

MSC:

65F10 Iterative numerical methods for linear systems
65-02 Research exposition (monographs, survey articles) pertaining to numerical analysis
65H10 Numerical computation of solutions to systems of equations
65B05 Extrapolation to the limit, deferred corrections
65F35 Numerical computation of matrix norms, conditioning, scaling
PDFBibTeX XMLCite