Convergence of iterations for linear equations.

*(English)*Zbl 0846.47008
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.

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 |