On hybrid iterative methods for nonsymmetric systems of linear equations (Q1923300): Difference between revisions

To solve large nonsymmetric systems of linear equations of the form \(A {\mathbf x} = {\mathbf b}\), where \(A\in\mathbb{R}^{N \times N}\), iterative methods may be relatively inexpensive, although the matrix \(A\) itself might be very large. In recent years, the class of so-called polynomial iterative methods is developed for this purpose. It consists of the iterations of the form \[ {\mathbf x}_n = {\mathbf x}_0+ \varphi_{n-1} (A) {\mathbf r}_0 \] where \(\varphi_{n-1} (A)\) is a polynomial of the degree \(n-1\) in \(A\), and where \({\mathbf r}_0={\mathbf b}-A{\mathbf x}_0\) \(({\mathbf x}_0 \in\mathbb{R}^N\) denotes an initial guess, that is \({\mathbf r}_0\) is the initial residual). The authors concern Chebyshev-like (also called semi-iterative) methods. Here the iteration polynomial \(\varphi_{n-1}\) is constructed beforehand, based on some information about the matrix \(A\), in a way to reduce some norm of the error as much as possible. In practice, Chebyshev-like methods are implemented as hybrid schemes consisting of two phases. The first one acquires information about the matrix \(A\). The second one uses the information to design the polynomial iteration and solve the system. In such a way, the first phase may be executed only once, when we solve a series of linear systems differing only in right hand sides. Most of the hybrid methods base in the first phase on estimates to the eigenvalues of \(A\), obtained using \textit{W. E. Arnoldi}'s method [Quart. Appl. Math. 9, 17-29 (1951; Zbl 0042.12801)]. The purpose of the paper is to propose an alternative to the use of Arnoldi eigenvalue estimates which avoids its drawbacks using more information about the matrix \(A\); namely the authors replace eigenvalue estimates by an approximation to the field of values of \(A\) in the Krylov subspace. This approach leads to three types of domains which have to be treated differently in order to construct a convergent iterative method in the second phase of the hybrid algorithm. Some issues associated with the actual implementation of the resulting polynomial iteration and some numerical examples are also presented.