Convergence in finite precision of successive iteration methods under high nonnormality (Q1923869)

The simplest linear iterative scheme: given \(x_0\), \(x_{k+1}=Ax_k+b\) for \(k\geq 0\), where \(A\) is a real or complex matrix of order \(n\) and \(b\) is a real or complex vector of size \(n\), converges theoretically (i.e. when calculating in exact arithmetic) for any real or complex vector \(x_0\) if and only if the spectral radius of \(A\), \(\rho(A)\) is less than 1. But this condition is not sufficient in many cases, when the scheme is run on a computer with finite precision arithmetic. Two simultaneous factors decide in practice: the finite precision of the computer arithmetic and the nonnormality of \(A\), but the nature of their synergetic influence (or a more subtle interplay) during the iteration process is not sufficiently understood so far. The authors present the analysis of the convergence of the process in finite precision, exploring instead two convergences as \(k\to\infty\): the convergence \((C_1)\): \(A^k\to 0\) and the -- equivalent and simultaneous in exact arithmetic -- convergence \((C_2)\): \(\sum^k_{i=0}A^i\to(I-A)^{(-1)}\). These two are not equivalent in practice of computing in finite precision. The authors investigate the first one for a matrix \(A\) with high nonnormality and a triangular matrix \(S\), being the Schur form of \(A\), i.e. \(A= QSQ^H\) for unitary matrix \(Q\) and \(S=D +N\), where \(D \) is the diagonal of eigenvalues and \(N\) is a strictly upper triangular matrix, such that its norm represents the nonnormality of \(A\). The convergence \((C_2)\) is explored only for the matrix \(S\), because of the good behaviour of \(S^k\) in finite precision. On the basis of the obtained results, the authors present some conjectures about the convergence of the original iteration process and the process \(y_{k+1} = Sy_k+d\), where \(y_0= Q^Hx_0\) and \(d= Q^Hb\). Synthetic results of numerical experiments and conclusions, showing how and when the equivalence of the two investigated convergences \((C_1)\) and \((C_2)\) is not valid in finite precision, complete the paper.