Richardson's iteration for nonsymmetric matrices (Q1058810): Difference between revisions

Let \(A\in {\mathbb{C}}^{N\times N}\) be a given nonsingular complex \(N\times N\) matrix and \(a\in {\mathbb{C}}^ N\) a given vector. For solving the linear system (1) \(Ax=a\), there is an iteration scheme \((2)\quad x_{j+1}=x_ j-\alpha_ j(Ax_ j-a),\) \(j=1,2,...,n\), called Richardson's iteration. It is applied in a cyclic manner by setting \(\alpha_{kn+j}=\alpha_ j\). The object of the present paper is to optimize the iteration parameters \(\alpha_ j\). For \(\epsilon_ j=x_ j-x\), the error of \(x_ j\) with respect to the solution x of (1), holds the relation \(\epsilon_{n+1}=p(A)\epsilon_ 1\) and thus \((4)\quad \| \epsilon_{n+1}\| \leq \| p(A)\| \| \epsilon_ 1\|.\) Here p(A) is a polynomial of degree n in the matrix A. The optimization leads to the following extremum problem: \((5)\quad \min_{p-1\in V_ n}\| p\| =\min_{p-1\in V_ n}\max_{z\in S}| p(z)|,\) where \(V_ n\) is the linear span of \(z,z^ 2,...,z^ n\) and S a compact set in \({\mathbb{C}}\), known to contain the spectrum \(\sigma\) (A) of A. (5) has always solutions, called optimal polynomials for S (for a fixed n). They have the property: \(\min_{p-1\in V_ n}\| p\| \leq 1.\) If p solves (5), then the reciprocals of the zeros of p are optimal iteration parameters \(\alpha_ j\). In case \(0\not\in S\) the optimal polynomial p is unique, and (2) converges for any compact set S and for arbitrary \(x_ 1\in {\mathbb{C}}^ N\) to the solution of (1), provided that \(\| p\| <1.\) In the present paper the stationary case, cycle length \(n=1\), is solved completely (Theorem 5.2, Corollary 5.1). For arbitrary \(n\in {\mathbb{N}}\), the problem (5) can be solved in the special case that \(S\not\ni 0\) is a closed disk (Theorem 4.1, Corollary 4.1). A notion ''Lemniscate with respect to p'', defined by the set \(L=\{z\in {\mathbb{C}}:\quad | p(z)| \leq \| p\| \}\) is introduced here, with p an optimal polynomial for a given S. It turns out that p is optimal also for \(L\supset S\), and that \(\max_{L}| p(z)| =\| p\|\). Thus, S can be enlarged to L without changing the iteration process or the error behaviour of the iterates. Consequently, the set L appears as a tool for studying the stability of the iteration (2) with respect to some perturbations of the matrix A. Furthermore, it is shown that for a real problem (1) the iteration (2) can be carried out with real arithmetic alone, even when there are complex \(\alpha_ j\).