Anderson加速方法中的松弛参数选取.docx

? ? Anderson加速方法中的松弛参数选取* ? ? 段晓宇，安恒斌 1. 中国工程物理研究院研究生院，北京 100088 2. 北京应用物理与计算数学研究所，北京 100094 3. 中国工程物理研究院高性能数值模拟软件中心，北京 100088 非线性方程的数值求解在很多科学与工程计算领域具有广泛的应用。求解非线性问题以迭代法为主，其中最主要的迭代法包括Newton 迭代法和不动点迭代方法［1］。Newton 迭代方法的每步迭代中需要计算Jacobi 矩阵，并求解Newton 线性方程组。Newton 迭代法的显著优点是该方法具有局部二阶收敛速度。不动点迭代法的算法实施相对简洁，但该方法的收敛速度较慢。在很多实际应用中，当采用不动点迭代方法求解非线性问题时，常常会出现迭代序列收敛缓慢甚至发散的现象。因此设计并采用有效的加速方法十分关键［2-4］。 在已有研究中，关于向量序列的加速方法可大致分为向量外推法［5-8］和Anderson 加速方法两类［9］。然而，直到近期（约2009 年之后），Anderson加速方法才吸引更多的关注［10-12］。 Anderson 加速方法是针对不动点迭代进行加速的一类算法［13-15］。在数学原理上与向量外推法不同，Anderson 加速方法不仅用到了迭代序列的信息，也用到了迭代算子的信息。一般的Anderson 加速迭代公式中包括函数值的线性组合和迭代值的线性组合两项，这两项的系数分别为p和1 -p，其中要求0 ＜p≤1. 目前对松弛参数的研究较少，并且在Anderson 加速方法的诸多应用中往往默认为p= 1［10，14-15］。Fang 和Saad 考虑了松弛参数为p= 1 之外的情形［16］，但没有进一步分析参数取值对该方法的收敛速度的影响。结合具体应用，近期部分研究者初步探讨了在区间（0，1］内不同松弛参数p的取值对迭代方法的影响［17-18］。 以上所有的研究工作均要求松弛参数在区间（0，1］内。本文重点关注Anderson 加速方法中松弛参数的选取，并且考虑适当扩大松弛参数p的选取范围。以求解非线性扩散方程的Picard 迭代为例，本文分析了松弛参数对Anderson 加速方法迭代收敛速度的影响。数值实验结果表明，Anderson加速方法中松弛参数的取值对迭代次数有较大的影响。对于不同的问题，最小迭代次数对应的参数取值是不同的。默认的参数取值p= 1 往往对应着较少的迭代次数。但在一些问题中，可以找到使迭代次数更少的参数取值p；并且参数可以不受0 ＜p≤1的限制。 本文第1节介绍Anderson加速方法的主要思想及算法实现［10，13］；第2 节介绍Anderson 加速方法中松弛参数的选取及具体实施；第3节给出非线性扩散方程的离散以及Picard迭代法的实现方式；第4 节通过数值实验，分析了松弛参数的选取对Anderson加速方法的影响；第5节给出本文的结论。 1 Anderson加速方法 Anderson 加速算法是加速不动点迭代收敛的一类方法。在科学和工程计算领域，许多问题都可以归结为不动点问题。不动点问题的一般形式如下： 基于上述不动点方程，可以构造如下的迭代公式。给定初始点u(0)，令 这种迭代方法叫做不动点迭代，G称为迭代函数。如果G是一个压缩映射，则由不动点迭代法得到的序列可以收敛到不动点问题的精确解。 在不动点迭代构造的压缩映射G(u)的基础上，Anderson加速方法的迭代公式可以表示为［10］ 其中mk= min{m，k}，称为Anderson 深度。mk决定了在迭代中利用的历史信息的数量，m的选择依赖于具体的应用。 Anderson 加速方法的思想是将第k+ 1 步迭代点定义为第k-mk，…，k- 1，k步函数值G的线性组合；线性组合的系数α是通过极小化残差向量的仿射组合的范数确定的，即求解约束最小二乘问题［13］ 其 中Fk=(fk-mk，…，fk)，残 差fk=G(u(k))-u(k)。由于不动点问题的精确解x*满足f(x*)= 0，所以通过极小化残差序列的组合向量范数定义组合系数。 为了方便求解上面的约束优化问题，将式（4）转化为无约束最小二乘问题［10-11，13］ 其 中?k=(Δfk-mk，…，Δfk-1)，Δfi=fi+1-fi，i=k-mk，…，k- 1，即采用残差向量的增量定义最小二乘问题。系数γ和α满足 基于无约束最小二乘问题，可得到Anderson加速方法的另一种表达形式 其 中?k=(ΔGk-mk，…，ΔGk-1)， ΔGi=G(u(i+1))-G(u(i)，i=k-mk，…，k- 1。公式（3）中采用函数值的线性组合定义迭代点，经过转换之后，公式（7）中新的迭代点由相应的函数值的增量定义。 在Anderson 加速方