Convergence of iterations for linear equations. (English) Zbl 0846.47008

Nevanlinna, Olavi

Lectures in Mathematics, ETH Zürich. Basel: Birkhäuser. 184 p. (1993).

These notes are based on lecture courses given at Helsinki University of Technology and at ETH Zurich. They are concerned with the study of iterative methods for the equation \(x^{k+1}= Lx^k+ g\), or, motivated by Krylov subspace methods, a general polynomial iteration method \(x^k= p_k (L) x^0+ q_{k-1} (L) g\), where \(p_k\) is a polynomial of degree at most \(k\), normalized so that \(p_k (1)= 1\) and \(p_k (\lambda)= 1-(1- \lambda) q_{k-1} (\lambda)\).
The aim is to help understand convergence of such methods for non-symmetric problems. Typically an iteration begins with a fast but slowing phase, sublinear behaviour. Then it may settle to a roughly linear speed (for nonsingular problems), followed possibly by a superlinear phase and finally terminates by reaching the exact solution or forced truncation.
An introductory section is followed by a section giving a good account of spectral theory before a section is devoted to each of the three types of behaviour.
The linear convergence chapter is interested in how polynomials may be chosen so as to obtain the best speed of convergence for the iteration \[ x^k= p_k (L) x^0+ q_{k-1} (L) g. \] The rate of convergence of \(|p_k (L)|\) to 0 is measured by \(\zeta (L)= \limsup |p_k (L) |^{1/k}\) and by \(\eta (L)\), the optimal reduction factor, where \(\eta (L)\) is the smallest value of \(\zeta (L)\) when \(L\) is fixed and \(\{p_k \}\) vary. \(\eta (L)\) depends only on the spectrum \(\sigma (L)\) whereas \(\zeta (L)\) has other dependencies. Calculating \(\eta (L)\) can be reduced to potential theory outside \(\sigma (L)\).
The sublinear section studies problems close to singular. The most interesting is when the spectral radius is 1 and \(1\in \sigma (L)\). Then \(|L^k (I- L) |\to 0\) either at least linearly, when \(1\in \sigma (L)\) is isolated, or slowly \((\sum |L^k (I-L) |= \infty)\) when 1 is not an isolated point of \(\sigma (L)\). If \(g\in (I-L) X\) typical sublinear speeds are governed by \(|p_k (L) (I-L) |\leq {M\over {k^\kappa}}\), for some \(\kappa\in (0, 2]\), but for \(g\) in better spaces, \(g\in (I-L)^s X\) (fractional powers), faster decay can be obtained. The geometry of \(\sigma (L)\) near the singularity 1 plays a key part in determining convergence rate.
Superlinear behaviour can only occur when the problem is nonsingular and the capacity of \(\sigma (L)\) is zero, that is, \(L\) is quasialgebraic. In this case a generating function \(G(\zeta, L)\) is an entire function of \(1/\zeta\). The growth properties of \(G\) (as \(\zeta\to 0\)) and the decay of its coefficients \(p_k (L)\) (as \(k\to \infty)\) are studied using some of the theory of entire functions.
The author writes that no attempt has been made to give a survey of known facts and that references are often omitted. Some new material is included.
The notes are well written, mostly self contained and are recommended to those interested in iteration processes.

Reviewer: J.L.R.Webb (Glasgow)

MSC:

47A50	Equations and inequalities involving linear operators, with vector unknowns
47-02	Research exposition (monographs, survey articles) pertaining to operator theory
65F10	Iterative numerical methods for linear systems
47J25	Iterative procedures involving nonlinear operators
47A10	Spectrum, resolvent
30D15	Special classes of entire functions of one complex variable and growth estimates

Keywords:

sublinear and superlinear phases; superlinear behaviour; iterative methods; Krylov subspace methods; polynomial iteration method; non-symmetric problems; spectral radius