论文标题
关于用于求解方程非线性线性系统的随机和贪婪松弛方案的收敛性
On the Convergence of Randomized and Greedy Relaxation Schemes for Solving Nonsingular Linear Systems of Equations
论文作者
论文摘要
我们扩展了针对某些类别的非铁属矩阵的遗传和正定矩阵的情况，以随机高斯 - 西德尔和高斯 - 南威尔方法为之已知的结果。我们获得了整个参数范围的收敛结果，这些参数描述了随机方法中的概率或高斯 - 南威尔型方法中的贪婪选择策略。我们确定那些使我们的收敛范围最大的选择。我们的主要工具是使用加权L1-核心来测量残差。一个主要的结果是，我们在随机算法中获得的预期值获得的最佳收敛界限与确定性但更昂贵的高斯 - 南威尔河类型算法一样好。数值实验说明了该方法的收敛性和所获得的边界。还提供了与随机Kaczmarz方法的比较。
We extend results known for the randomized Gauss-Seidel and the Gauss-Southwell methods for the case of a Hermitian and positive definite matrix to certain classes of non-Hermitian matrices. We obtain convergence results for a whole range of parameters describing the probabilities in the randomized method or the greedy choice strategy in the Gauss-Southwell-type methods. We identify those choices which make our convergence bounds best possible. Our main tool is to use weighted l1-norms to measure the residuals. A major result is that the best convergence bounds that we obtain for the expected values in the randomized algorithm are as good as the best for the deterministic, but more costly algorithms of Gauss-Southwell type. Numerical experiments illustrate the convergence of the method and the bounds obtained. Comparisons with the randomized Kaczmarz method are also presented.
