Convergence of asynchronous iteration with arbitrary splitting form (Q1113609)

Let \(x_ i=\sum^{n}_{j=1}a_{ij}x_ j+b_ i\), \(i=1,2,...,n\) be a linear system and \(\{p_{ik}\}^{\infty}_{k=0}\), \(\{q_{ik}\}^{\infty}_{k=0}\), \(i=1,2,...,n\) integer sequences such that \(0=q_{i0}\leq p_{i1}<q_{i1}\leq p_{i2}<... \). The following iterative method defined for integer \(t\geq 0\) and \(i=1,2,...,n\) by \(x_{it}=x^ 0_ i\quad if\quad t=0,\quad x_{it}=\sum^{n}_{j=1}a_{ij}x_{j,p_{ik}}+b_ i\) if \(t=q_{ik}\), \(k=1,2,...\), and \(x_{it}=x_{i,q_{ik}}\) if \(q_{ik}<t<q_{i,k+1}\), \(k=0,1,2,..\). is an asynchronous iterative method. The convergence of \(x_{it}\) to \(x_ i\) for \(t\to \infty\) is guaranteed if \(\rho (| A|)<1\), where \(A=(a_{ij})\), \(| A| =(| a_{ij}|)\) and \(\rho\) (\(\cdot)\) denotes the spectral radius. This result is proved using a new method and is then generalized to an iterative method of the same form obtained from splitting the matrix A in such a way that \(A=A_ 1+A_ 2=(a_{ij}^{(1)}+(a_{ij}^{(2)})\) with \(a_{ij}^{(1)}a_{ij}^{(2)}=0\) for every \(i,j=1,2,...,n\). Further extension of the result to the case of iteration with relaxation parameter is also proved.