计算科学 - 为什么我们不选择误差解决范数作为迭代方法的标准？ - 吾爱随笔录

为什么我们不选择误差解决范数作为迭代方法的标准？

计算科学迭代法线性系统格瑞斯

2021-12-19 17:53:53

用于求解线性系统

A x = b,

$Ax=b,$ 使用迭代方法，我们经常使用终止标准如下：

\frac{‖ r_{k} ‖}{‖ r_{0} ‖} = \frac{‖ b - A x_{k} ‖}{‖ b - A x_{0} ‖} < e p s .

$\frac{\|r_k\|}{\|r_0\|}=\frac{\|b-Ax_k\|}{\|b-Ax_0\|}<eps.$ 其中是初始猜测，是第步迭代。

x_{0}

$x_0$

x_{k}

$x_k$

k

$k$

我的问题是为什么我们不使用真正的终止标准，如下所示：因为其中 k(A) 是条件数。我想问：是否存在满足残差标准但条件数太大以至于第 k 步迭代仍然远离实际解决方案的情况？

\frac{‖ x_{k} - x^{*} ‖}{‖ x_{0} - x^{*} ‖} \leq k (A) \frac{‖ r_{k} ‖}{‖ r_{0} ‖}

$\frac{\|x_k-x^*\|}{\|x_0-x^*\|}\leq k(A)\frac{\|r_k\|}{\|r_0\|}$

x^{*}

$x^*$

1个回答

我们不能在实践中使用您最后展示的标准，因为它要求我们知道是什么。但是计算条件数通常比求解线性系统更昂贵。因此，您展示的标准是不切实际的。 $\kappa(A)$

这只给我们留下了标准我认为这不是一个好的标准，因为最终迭代的准确性现在取决于您对初始猜测的选择。特别是，如果您碰巧已经有了一个非常好的初始猜测，您仍然需要进行多次迭代才能使该比率低于您的容差。相反，通常需要这样，您可以将所有内容归一化为从开始时所获得的比率——但如果您碰巧有一个更好的开始猜测，那很好，您只需要进行更少的迭代。

\frac{‖ r_{k} ‖}{‖ r_{0} ‖} = \frac{‖ b - A x_{k} ‖}{‖ b - A x_{0} ‖} \leq e p s .

$\frac{\|r_k\|}{\|r_0\|}=\frac{\|b-Ax_k\|}{\|b-Ax_0\|}\le eps.$

x_{0}

$x_0$

\frac{‖ r_{k} ‖}{‖ b ‖} = \frac{‖ b - A x_{k} ‖}{‖ b ‖} \leq e p s .

$\frac{\|r_k\|}{\|b\|}=\frac{\|b-Ax_k\|}{\|b\|}\le eps.$

x_{0} = 0

$x_0=0$

其它你可能感兴趣的问题

上一篇数值有限差分的时间复杂度下一篇稀疏矩阵求逆