The randomized Gauss--Seidel method and its extension have attracted much attention recently and their convergence rates have been considered extensively. However, the convergence rates are usually determined by upper bounds, which cannot fully reflect the actual convergence. In this paper, we make a detailed analysis of their convergence behaviors. The analysis shows that the larger the singular value of $A$ is, the faster the error decays in the corresponding singular vector space, and the convergence directions are mainly driven by the large singular values at the beginning, then gradually driven by the small singular values, and finally by the smallest nonzero singular value. These results explain the phenomenon found in the extensive numerical experiments appearing in the literature that these two methods seem to converge faster at the beginning. Numerical examples are provided to confirm the above findings.
翻译:随机的高斯- 赛德尔方法及其扩展最近引起了许多注意,它们的趋同率得到了广泛的考虑。 但是, 趋同率通常由上界决定, 无法充分反映实际趋同。 在本文中, 我们详细分析它们的趋同行为。 分析显示, 美元单值越大, 错误在相应的单矢量空间中越快地衰减, 趋同方向主要是由最初的大单值驱动, 然后由小单值逐渐驱动, 最后由最小的非零单值驱动。 这些结果解释了文献中出现的、 这两种方法在开始时似乎会更快地趋同的广泛数字实验中发现的现象。 提供了数字实例来证实上述结论。