Richardson's iteration for nonsymmetric matrices

To solve the linear N×N system (1) Ax=a for any nonsingular matrix A, Richardson's iteration (2) x_j+1=x_j-α_j(Ax_j-a), j=1,2,…,n, which is applied in a cyclic manner with cycle length n is investigated, where the α_j are free parameters. The objective is to minimize the error |x_n+1-x|, where x is the solution of (1). If the spectrum of A is known to lie in a compact set S, one is led to the Chebyshev-type approximation problem (3) min_p-1∈Vnmax_z∈S|p(z)|, where V_n is the linear span of z,z²,…,zⁿ. If p solves (3), then the reciprocals of the zeros of p are optimal iteration parameters α_j. 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 α_j. The stationary case n=1 is solved completely, i.e., for all compact sets S the problem (3) is solved explicitly. As a consequence, the converging stationary iteration processes can be characterized. For arbitrary closed disks S the problem (3) can be solved for all n∈$\text{N}$, and a simple proof is provided. The lemniscates associated with S are introduced. They appear as an important tool for studying the stability of the iteration (2).