计算科学 - 共轭梯度 - 病态和数值公差 - 吾爱随笔录

计算科学线性求解器迭代法共轭梯度精确条件数

2021-12-22 03:15:13

我想解决系统，其中是 SPD，但非常病态（）。我有兴趣使用共轭梯度法的未经预处理的版本。 $Ax=b$ $A$ $\text{cond}(A)>10^{11}$

是否有任何关于残差范数的估计，哪种方法实际上可以在双精度算术中收敛？我对数值求解系统不感兴趣。我正在寻找包含有限精度浮点运算的错误界限。

1个回答

令表示的解，让表示计算的解。我们不能希望比的浮点表示。在这种情况下，最有利的情况是其中和是单位舍入。因此，。现在，让表示由我们有 $x$ $Ax=b$ $\hat{x}$

\hat{x} = fl (x),

$\hat{x} = \text{fl}(x),$

x

$x$

{\hat{x}}_{j} = x_{j} (1 + δ_{j})

$\hat{x}_j = x_j(1+\delta_j)$

| δ_{j} | \leq u

$|\delta_j| \leq u$

u

$u$

‖ x - \hat{x} ‖_{2} \leq u ‖ x ‖_{2}

$\|x-\hat{x}\|_2 \leq u \|x\|_2$

r

$r$

r = b - A \hat{x} = A (x - \hat{x}) .

$r = b - A\hat{x} = A(x-\hat{x}).$

‖ r ‖_{2} \leq ‖ A ‖_{2} ‖ x - \hat{x} ‖_{2} \leq u ‖ A ‖_{2} ‖ x ‖_{2} \leq u ‖ A ‖_{2} ‖ A^{- 1} ‖_{2} ‖ b ‖_{2} .

$\|r\|_2 \leq \|A\|_2 \|x-\hat{x}\|_2 \leq u \|A\|_2 \|x\|_2 \leq u \|A\|_2 \| A^{-1} \|_2 \|b\|_2.$ 我们得出结论，相对残差满足其中的 2-范数条件数。

\frac{‖ r ‖_{2}}{‖ b ‖_{2}} \leq u κ_{2} (A),

$\frac{\|r\|_2}{\|b\|_2} \leq u \, \kappa_2(A),$

κ_{2} (A) = ‖ A ‖_{2} ‖ A^{- 1} ‖_{2}

$\kappa_2(A) = \|A\|_2 \| A^{-1} \|_2$

A

$A$

上述估计对于一般矩阵是正确的。在实践中，您会发现迭代方法的相对残差停滞在的水平上。一般来说，CG算法没有希望做得更好。

A

$A$

u κ_{2} (A)

$u \kappa_2(A)$

其它你可能感兴趣的问题