计算科学 - 为什么要最小化 A 范数？ - 吾爱随笔录

为什么要最小化 A 范数？

计算科学迭代法共轭梯度克雷洛夫法格瑞斯

2021-12-14 04:57:09

假设求解线性系统 $A \textbf x = \textbf b$ ，与 $A$ 如此之大以至于只能使用迭代方法。假设 $A$ 引出一个范数，我意识到通常希望最小化由 $A$ （而不是，例如，2-范数）。

为什么会这样？使用有什么好处 $A$ -norm 与不同（一般）优化方法（GMRES、Gradient Decent/Bconjugate Gradient Decent 等）中的 2-norm 相比？

PS：我更像是一个视觉化的人，如果你想出一个更形象化的解释，我会很感激。:)

2个回答

Wolfgang Bangerth 的回答几乎已经说明了一切，但另一个微妙的细节是 GMRES/MINRES 最小化了残差的范数，即，而 CG 最小化了误差的 (A-) 范数，即。 $\|Ax_k-b\|$ $\|x_*-x_k\|_A$

在大多数情况下，您真正想要最小化的是误差，而残差充当了一个不完美的代理：回忆一下条件数限制仅暗示。 $\|r_k\|/\|b\| \leq \varepsilon$ $\|e_k\| / \|x_*\| \leq \kappa(A) \varepsilon$

我们不能最小化 2 范数中的误差，因为我们首先不知道精确解来计算目标函数。但是，如果切换到来计算它就足够了，它是常数，因此可以在最小化中忽略）。这个技巧只有在是正定的时候才有效，否则这个“ -范数”就不是一个真正的范数。 $x_*$ $A$ $Ax_*=b$ $x_*^TAx_*$ $A$ $A$

因此，尽可能减少误差的范数是有意义的，但对于一般，您所能做的就是最小化残差。 $A$ $A$

从某种意义上说，这并不重要：在有限维度上，所有范数都是等价的，所以如果一个算法方便地具有证明在一个范数上收敛很容易的性质，那么这就是人们会选择的。在实践中，人们经常希望将残差的范数减少某个因子，从实践的角度来看，一个范数的某种减少可能也意味着另一个范数已经缩小了一个合理相似的因子——范数等价不会' t 实际上规定是这样，但在实际经验中似乎是这样。

也就是说，至少对于正定矩阵和对称矩阵（即，正是那些 $A$ 内积实际上是一种规范），还有更多。在那些情况下，线性系统的解

A x = b

$Ax = b$ 也是函数的最小者

f (x) = \frac{1}{2} x^{T} A x - x^{T} b

$f(x) = \frac 12 x^T A x - x^T b$ 所以误差的（平方）A范数满足

‖ \tilde{x} - x ‖_{A}^{2} = (\tilde{x} - x)^{T} A (\tilde{x} - x) = {\tilde{x}}^{T} A \tilde{x} - 2 {\tilde{x}}^{T} A x + x^{T} A x = {\tilde{x}}^{T} A \tilde{x} - 2 {\tilde{x}}^{T} b + x^{T} b + \underset{= 0}{\underset{⏟}{(x^{T} b - x^{T} A x)}} = 2 [f (\tilde{x}) - f (x)] .

$\|\tilde x-x\|_A^2 = (\tilde x-x)^T A (\tilde x-x) = \tilde x^T A \tilde x - 2 \tilde x^T A x + x^T A x \\ = \tilde x^T A \tilde x - 2 \tilde x^T b + x^T b + \underbrace{(x^Tb - x^T A x)}_{=0} \\ = 2\left[f(\tilde x) - f(x)\right].$ 换句话说，误差的范数也是您试图最小化的函数中的误差。在很多情况下，这个功能有点像系统中储存的能量，所以它具有物理意义。

A

$A$

其它你可能感兴趣的问题

上一篇计算科学中最重要的定理是什么？下一篇使用平滑粒子流体动力学可以在 PC 上模拟什么规模问题？