Post-processing of Gauss-Seidel iterations (Q2760347)

The basic idea presented in the paper is backed by the convergence behaviour of a sequence of vectors \(x^k\) generated by an iterative method \(x^{k+1}=Bx^k+ c\), \(k=0,1,2,\dots \), solving a system \(Ax=b\) of \(n\) linear algebraic equations. It has been observed that the sequence \(\{x_i^{k+1}-x_i^k \}_{k=1}^\infty \), where \(i\) is a fixed index, becomes almost geometric if \(k\) is large. Approximate quotients \(q_i^k\), defined as the rate of two successive members of the sequence, converge to an \(i\)-independent number \(q\). NEWLINENEWLINENEWLINEThe proposed post-processing is based on a summing formula, and reads \(\widetilde x^{k+1}=x^k+(x^{k+1}-x^k)/(1-q^k)\), where \(q^k\) is the arithmetic mean of \(q_i^k\). NEWLINENEWLINENEWLINEUnder some assumptions put on the eigenvectors and the dominant eigenvalue of \(B\), convergence \(\widetilde x^k\to x\) is proved. It is also shown that the convergence is faster than that of \(\{x^k\}_{k=1}^\infty \). A numerical example illustrates the efficiency of this cheap acceleration algorithm grafted on the Gauss-Seidel method. Applications to other iterative methods are also evaluated and discussed.