A Gauß-Seidel procedure for accelerating the convergence of a generalized method of the root iterations type of $(k+2)$-th order ($k\in N)$ for finding polynomial complex zeros, introduced by the first author [Computing 27, 37-55 (1981; Zbl 0442.65030)], is considered. It is shown that the R-order of convergence of the accelerated method is at least $k+1+σ\sb n(k)$, where $σ\sb n(k)>1$ is the unique positive zero of the equation $σ\sp n-σ-k-1=0$ and n is the polynomial degree. The convergence analysis is performed using circular arithmetic and it is applicable to the interval simultaneous methods in terms of circular regions as well as to the ordinary (noninterval) simultaneous methods. In the second case, for $k=1$, the results due to {\it G. Alefeld} and {\it J. Herzberger} [SIAM J. Numer. Anal. 11, 237-243 (1974; Zbl 0282.65038)] are obtained. The cases of multiple zeros and clusters of zeros are also discussed. Examples of algebraic equations in ordinary and circular arithmetic are given.