2-块AOR迭代解最小二乘问题的最优收敛性 (1994年)

最小二乘问题是最优化问题的一种重要形式，在科学计算、数据分析、信号处理等领域有着广泛的应用。它旨在从一组观测数据中找到最符合这些数据的函数。在1994年发表的这篇文章中，作者讨论了如何使用一种特定的迭代算法——2-块AOR迭代法（Alternating Over-Relaxation迭代方法的简称）来求解大规模稀疏最小二乘问题，并分析了其收敛性问题。 需要了解最小二乘问题的基本概念。给定一个超定方程组Ax=b，其中A是一个m×n的矩阵，b是一个m维向量，且m>n。通常情况下，这样的线性方程组没有精确解，最小二乘法的目标是找到一个向量x，使得b与Ax之间的差的二范数最小。这个问题可以通过求解正规方程ATAx=ATb来得到解，其中ATA是A的转置乘以A，ATb是A的转置乘以b。 文章提到了几种不同的迭代方法用于求解最小二乘问题。1975年Chen和Gentleman首先提出了3-块SOR迭代法，而后来Markham, Neumann和Plemmons等人提出了2-块SOR方法。文章的作者带曾文平进一步研究了2-块AOR迭代法，旨在寻找比已有的迭代方法更加优越的算法。 AOR迭代法是SOR（Successive Over-Relaxation）迭代法的一种推广。SOR法是一种用于求解线性方程组的迭代技术，特别是在处理大型稀疏矩阵时非常有效。AOR法允许调整迭代过程中的松弛因子，从而有可能提高收敛速度。在文章中，作者特别讨论了2-块AOR迭代法，并给出了收敛的充要条件以及收敛域。这意味着，对于任意给定的Jacobi矩阵，都存在一个谱半径ρ(J2)，使得2-块AOR迭代法收敛。 文章还提到了AOR迭代矩阵和Jacobi迭代矩阵特征值之间的关系。如果A是一个列满秩矩阵，那么总可以通过适当的排列得到矩阵C的分块形式。这样的分块形式使得可以将矩阵C进一步分解为AOR迭代矩阵Lzγ，这样可以得到一个迭代格式Z(K+1)=LγZ(K)+(Dz−ωLz)−1ld。这里，Lzγ是AOR迭代矩阵，而Dz是对应于C的对角块，Lz和Uz是由C的其余块组成的矩阵。通过分析这些矩阵的特征值，作者给出了迭代过程收敛的条件，并通过适当的参数ω选择，可以使得AOR迭代矩阵的谱半径ρ(Lzγ)=0，这将极大地提高算法的效率。 文章进一步指出，当ω接近1时，可以找到使得AOR迭代的谱半径ρ(Lzγ)=0的ω值。这意味着，在这种情况下，2-块AOR迭代法要比之前提到的最优SOR方法更为优越，因为AOR方法的谱半径更小。 总结起来，1994年的这篇文章介绍了2-块AOR迭代法在解决最小二乘问题上的应用，并给出了收敛性分析。通过理论推导和实际案例分析，作者证明了2-块AOR迭代法在特定条件下能够达到比现有的其他迭代方法更好的收敛性能。这篇工作对于推动最小二乘问题迭代求解方法的研究具有重要意义，对于需要处理大规模稀疏线性系统的领域具有深远的影响。