计算科学 - 如果 CG 方法的步长减少一半，为什么迭代步长会变成两倍？ - 吾爱随笔录

计算科学共轭梯度

2021-12-01 20:49:16

对于SPD 矩阵的CG方法，（由具有齐次边界条件的 Poisson 方程产生的 Ax = b）我们知道收敛定理：经过 m 步迭代，误差满足 $e^{(m)}=x-x_m$

‖ e^{(m)} ‖_{A} \leq 2 (\frac{\sqrt{k} - 1}{\sqrt{k} + 1})^{m} ‖ e^{(0)} ‖_{A},

$\|e^{(m)}\|_A\leq 2(\frac{\sqrt{k}-1}{\sqrt{k}+1})^m \|e^{(0)}\|_A,$

k = c o n d_{2} (A) = λ_{m a x} / λ_{m i n} .

$\quad k = cond_2(A)=\lambda_{max}/\lambda_{min}.$

我的问题是当步长减少一半，条件数为时，为什么迭代步长增加两次以使相对误差满足预先选择的容差？有人可以给我一些证据吗？非常感谢。 $h$ $O(h^{-2})$ $\epsilon$

1个回答

假设原始矩阵的条件数为，细化网格后的条件数为。然后，您想要比较达到容差所需的迭代次数。因此，假设您对相对容差感兴趣，在第一种情况下，您会得到产生因为通常条件数很大，对数中的分数将略小于 1，您可以围绕进行泰勒展开以找到 $k_1$ $k_2=4k_1$ $\varepsilon$

{(\frac{\sqrt{k_{1}} - 1}{\sqrt{k_{1}} + 1})}^{m_{1}} = ε

$\left(\frac{\sqrt{k_1}-1}{\sqrt{k_1}+1}\right)^{m_1} = \varepsilon$

m_{1} = \frac{\log ε}{\log (\frac{\sqrt{k_{1}} - 1}{\sqrt{k_{1}} + 1})} .

$m_1 = \frac{\log\varepsilon}{\log \left(\frac{\sqrt{k_1}-1}{\sqrt{k_1}+1}\right)}.$

k = \infty

$k=\infty$

m_{1} \approx - (\log ε) \sqrt{k_{1}} .

$m_1 \approx -(\log\varepsilon)\sqrt{k_1}.$ （负号说明小的对数为负。）

ε

$\varepsilon$

通过同样的论点，你会得到

m_{2} \approx - (\log ε) \sqrt{k_{2}} = 2 m_{1} .

$m_2 \approx -(\log\varepsilon)\sqrt{k_2} = 2 m_1.$

其它你可能感兴趣的问题