计算科学 - 何时停止 Gauss-Seidel 迭代？ - 吾爱随笔录 - 问答

何时停止 Gauss-Seidel 迭代？

计算科学线性求解器收敛误差估计

2021-12-09 19:25:47

我想估计一下，我的解决方案有错误，比如说小于 1e-8。

通常，当残差“足够小”并且这已经是问题时，我会停止 Gauss-Seidel 算法。我怎么知道残差何时足够小，因为即使残差很小，解决方案仍然可能有太大的误差。所以这不是什么好方法。

你用什么作为停止标准？

在另一个网站 ( math-linux.com ) 上，我找到了一个停止标准：但是，这背后的理论是什么？

‖ r ‖ / ‖ b ‖ \leq ϵ

$\|r\|/\|b\|\leq \epsilon$

顺便说一句，这是我在上一个项目中使用的代码，仅供参考，我是如何做到的：

void relax(double epsilon, vector<double> &x, SparseMatrix &A, const vector<double> &f) {
    int maxIter = 100;
    int iter = 0;
    double residual = 1.0;
    double minResidual 0.000001; //I also tried 1e-14;

    while (iter < maxIter && residual >= minResidual) {
        for (int i = 0; i < A.dim; ++i) {
            double ls = A.lineScalar(i, x);
            x[i] = (1.0/A(i,i)) * (f[i] - ls);
        }
        vector<double> temp = A.multiply(x);
        residual = L2(temp - f);
    }
}

2个回答

无法从残差得出解决方案的准确度。在正常情况下的最佳和最坏情况之间，有一个恰好是条件数的因素。更准确地说，如果残差范数是 r 并且误差范数是 e 那么 , 并且两个界限都是可以达到的。取边界的商证明了这一主张。 $\|A\|^{-1}\le e/r \le \|A^{-1}\|$

逆范数的数量级通常可以通过 Lanczos/Arnoldi 方法的几个步骤来估计。因此可以应用界限。

然而，一般来说，模型方程无论如何都不是真正精确的，并且使残差小于不确定数据确定残差的精度被认为是科学正确的过程。根据数据，这可能比停滞更早。

这背后的理论称为后向误差分析。例如，如果不确定性的唯一来源是某个范数中 1e-4 右侧的测量误差，并且您的余数范数小于 1e-4，则无法将其与已解决问题的精确解的余数区分开来在具有相同精度的不同 rhs 的问题中用作近似值时会出现。

通常，当我估计线性方程组的解时，我会保存近似值并用它来计算在每个组件 i 上。这比计算残差要快，因为它不需要矩阵向量乘积。虽然，如果您的系统状况不佳，它仍然可能无法为您提供给定容差的正确解决方案。 $\vec x^{n-1}$ $x_{err}=max|x_i^n-x_i^{n-1}|$ $\epsilon$

其它你可能感兴趣的问题

上一篇获取对称矩阵的特征值和特征向量的简单 Lanczos 算法代码下一篇传播冲击波的动态网格与静态网格的效率