鞍点问题的修正非线性近似Uzawa算法研究

摘要

鞍点问题在计算科学和工程领域有着极其广泛的应用，比如计算流体力学，约束和带权最小二乘估计，约束优化，参数识别和椭圆型偏微分方程的混合有限元逼近等领域的许多问题都归结为大规模稀疏鞍点问题的求解.在过去的多年里，国内外学者提出了很多求解鞍点问题的数值方法，常见的算法分为直接法和迭代法．在实际应用中，鞍点问题通常是大规模且稀疏的，由于巨大的计算量和内存需求，直接法往往失效，因此可行的方法是基于迭代求解大规模稀疏鞍点问题．
　　 Uzawa方法作为一种经典的定常迭代方法，受到很多的学者的关注，已取得很大的进展涉及不同的推广和改进形式，比如预条件Uzawa算法，线性近似Uzawa算法和非线性近似Uzawa算法.由于Uzawa型方法具有易操作性和极小的存储需求的优点，适合求解大规模稀疏鞍点问题．Uzawa型算法，特别是非线性近似Uzawa算法，可视为内外迭代法，其中内迭代用于非精确求解系数矩阵为A或S的线性方程．现有文献中通常利用矩阵范数和常数精度定义理想的内迭代终止条件，只讨论了常精度的非线性近似Uzawa算法的收敛性，其不足之处在于两方面：一是误差分析依赖于内迭代精度相关的误差范数，所用的分析方法可移植性较弱，并不适用于分析变精度的非线性近似Uzawa算法的收敛性；二是理论证明中所给出的算法的收敛域相对较小．在实际计算中，为了减少计算代价，我们通常采用2范数定义实际的内迭代终止标准，理论上不论是常精度还是变精度的内迭代标准必然隐式地对应理想的变精度的内迭代终止条件.利用变精度定义内迭代的终止标准，通过适当地选取变精度序列，将会有助于减少常精度内迭代算法中经常出现的阶梯或停滞现象，从而减少内迭代的计算量.引入松弛参数修正Uzawa算法，也有助于加快Uzawa型算法的收敛速度.而如何选取内迭代的变精度序列，如何确定最佳的松弛参数，用于修正现有的非线性近似Uzawa法，这是非常困难的问题．基于统一的误差衡量标准，给出修正非线性近似Uzawa算法的收敛性分析，这将是非常有意义的工作.特别地，国内外尚未有学者讨论过变精度的Uzawa型算法的收敛性，因此，提出变精度的修正非线性近似Uzawa算法收敛的充分条件将会是Uzawa型算法收敛性分析领域的重大进展.在本文中，我们将通过研究求解鞍点问题的修正非线性近似Uzawa算法的收敛性，对上述问题给出相对完善的解答．我们相信文中提出的方法对分析求解非线性鞍点问题的非线性近似Uzawa方法的收敛性能够提供启发和帮助.本文的主要贡献如下：
　　 (1)我们利用变精度的内迭代和可变的松弛参数改进Uzawa型算法的收敛性，提出了A型，S型和AS混合型修正非线性近似Uzawa法.基于松弛参数校正非线性近似Uzawa算法的x和y分量，我们给出了一类xy型的广义修正Uzawa算法．
　　 (2)我们提出一种适合常精度或变精度的Uzawa型算法的误差分析的能量范数，使得分析非线性近似Uzawa算法的收敛性时具有统一的刻画标准．
　　 (3)在统一的框架下，我们利用一致的能量范数，从理论上证明了修正非线性近似Uzawa算法的收敛性，这是非线性近似Uzawa算法的收敛性分析方面的重大进展．对于变精度的A型修正Uzawa算法，通过估计迭代矩阵的谱范数，说明收敛速度只依赖于内迭代精度和松弛参数.我们给出了最优松弛参数的表达式，并在此基础上提出了修正Uzawa法收敛的充分条件．收敛分析表明，变精度的A型修正Uzawa算法在一个比较大的区域内收敛(见定理3.2.6)，即使采用常精度，较原来的A型非线性近似Uzawa算法的收敛域也由初始的0＜δ＜(1/3)改进为0＜δ＜1．我们还给出了实际计算中最佳松弛参数的估计方法，数值结果表明采用这一估计参数可以有效地求解鞍点问题．区别于A型修正Uzawa算法，AS混合型修正Uzawa算法涉及非精确求解两个线性方程，我们通过将AS型修正Uzawa算法隐式地转化为可变预条件的Uzawa算法，给出了变精度情形下算法的收敛性结论.通过和原来的常精度的AS型非线性近似Uzawa算法的对比，常精度的AS型修正Uzawa算法的收敛域也改进为0＜δ＜1和0＜ε＜1．作为AS型修正Uzawa算法的特殊形式，S型修正Uzawa算法也有类似的改进．至于xy型广义的修正Uzawa算法，理论分析表明采用最佳的松弛参数ω*时，只需要保证另一松弛参数τ满足简单的约束条件，算法就收敛到鞍点问题的精确解．
　　 (4)我们给出了大量的数值例子，包括模拟例子和来自Stokes方程的实际例子，通过将我们提出的修正非线性近似Uzawa算法与原来的非线性近似Uzawa算法，块对角预条件的MINRES方法，基于埃米特/反埃米特分解的预条件GMRES和可变的GMRES算法的对比和分析，从理论和实际两种角度说明了本文所提出的这些方法的有效性．
　　 (5)基于文献[庞宏奎，黎稳，求解对称鞍点问题的修正Uzawa方法．计算数学，31(3)(2009)，pp.231-242]，我们提出了一种理想的修正Uzawa算法．我们分析了理想的修正Uzawa算法的收敛性，并利用非线性算子的性质重新讨论了上述文献中求解对称鞍点问题的修正Uzawa算法的收敛性．