Iterative refinement techniques for solving block linear systems of equations (Q1946150)

If \(x_0=S_0(b)\) is an algorithm to solve a nonsingular linear system \(Ax=b\), then a \(k\)-fold iterative refinement (\(k\geq 1\)) computes \(x_k=S_k(b)\) with \(S_{j+1}(b)=x_j+p_j\), \(p_j=S_j(r_j)\), \(r_j=Ax_j-b\), \(j=k-1,\ldots,0\). This paper discusses the numerical stability of this method when \(A\) is a block matrix with square blocks. The analysis is based on a special norm for block matrices: first each block in \(A\) is replaced by its 2-norm, giving a matrix \(\mu(A)\) and then the overall 2-norm \(\|\mu(A)\|_2\) is taken. The main theorem states that the algorithm is blockwise forward stable. If \(x^*\) is the exact solution, then a condition number is \(\text{cond}(A;x^*)=\|\mu(A^{-1})\mu(A)\mu(x^*)\|_2/\|x^*\|_2\leq \kappa_\mu(A)=\|\mu(A^{-1})\mu(A)\|_2\).