  When iteratively solving linear systems By=b with Hermitian positive
semi-definite $B$, and in particular when solving least-squares problems for
$Ax=b$ by reformulating them as $AA^\ast y=b$, it is often observed that
SOR-type methods (Gauss-Seidel, Kaczmarz) perform suboptimally for the given
equation ordering, and that random reordering improves the situation on
average.This paper is an attempt to provide some additional theoretical support
for this phenomenon. We show eerror bounds for two randomized versions, called
shuffled and preshuffled SOR, that improve asymptotically upon the best known
bounds fro SOR with cyclic ordering. Our results are based on studying the
behavior of the triangular truncation of Hermitian matrices with respect to
their permutations.
