计算科学 - 梯度下降和线性与非线性定点迭代的收敛 - 吾爱随笔录

梯度下降和线性与非线性定点迭代的收敛

计算科学线性代数矩阵线性求解器迭代法

2021-12-06 17:27:17

假设一个系统

A x = b

$Ax=b$ 给出，与

A \in R^{n \times n}

$A\in\mathbb{R}^{n\times n}$ 是一个对称的正定矩阵，并且一些非零

b \in R^{n}

$b\in\mathbb{R}^n$ . 具有最优步长的梯度法可写为

x_{k + 1} = x_{k} - α_{k} \cdot g_{k},

$x_{k+1}=x_k-\alpha_k\cdot g_k,$ 和

g_{k} = A x_{k} - b

$g_k=Ax_k-b$ 和

α_{k} = \frac{g_{k}^{T} g_{k}}{g_{k}^{T} A g_{k}}

$\alpha_k=\frac{g_k^Tg_k}{g_k^TAg_k}$ .

是否可以证明上述迭代过程收敛于 $\bar{x}=A^{-1}b$ ，不管初始化？

上面的迭代方案可以看成是线性定点迭代吗？实际上，术语线性定点迭代中线性的确切含义是什么？

3个回答

这是一种阻尼理查森方法。由于该操作的一步，不是线性操作，它不是平稳迭代。与只需要一个算子应用并具有更好收敛性的 Krylov 子空间方法相比，每次迭代的额外矩阵乘法和额外缩减的存在使得该方法非常没有吸引力。 $x_k \mapsto x_{k+1}$

这被称为最速下降法，它收敛于任何对称和正定矩阵（线性速率取决于其条件数），与初始化无关；请参阅 Saad 的稀疏线性系统迭代方法的第 5.3.1 章。

它是一种非线性迭代方法，因为新的迭代 $x_{k+1}$ 不是的线性函数 $x_k$ （例如，在 Jacobi 或 Gauss-Seidel 迭代中）因为它出现（通过 $g_k$ ) 在定义中 $\alpha_k$ . 应该指出的是，共轭梯度法（参见 Saad 书中第 200 页的顶部）需要基本相同的工作量，并且（在实践中）具有更好的收敛特性。

很容易验证确实是迭代的不动点。问题是迭代算子是否是一个收缩。如果是 SPD，如果小于或等于就是这种情况。 $x=A^{-1}b$

I - α A

$I - \alpha A$

A

$A$

α

$\alpha$

\frac{1}{λ_{max}}

$\frac{1}{\lambda_{\textrm{max}}}$

另一方面，我们只能用简单的参数来推断。这不足以保证使用线性迭代的常用参数收敛。换句话说，是迭代的非线性确保了它实际上收敛，如果它确实收敛的话。人们需要更复杂的分析来证明收敛。 $\alpha\le\frac{1}{\lambda_{\textrm{min}}(A)}$

其它你可能感兴趣的问题

上一篇病态革兰氏基质组装下一篇我的四阶 Runge-Kutta 方法实现中的错误在哪里？