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 加速方法中，函數值增量矩陣?與殘差增量矩陣? 的列向量個數最多不超過m個。在第k步迭代，如果k＜m，那么在上一步迭代矩陣的右端需要添加最新的向量；如果k≥m，那么在添加新向量的同時，還需要刪除矩陣中最左端的向量［13］。在Anderson 加速方法中，采用QR 分解求解無約束最小二乘問題。Anderson 加速不動點迭代的算法描述如表1。

表1 Anderson加速不動點迭代的算法-1（p=1）Table 1 Anderson accelerated fixed point iteration algorithm（p=1）

在迭代公式（3）的基礎上，考慮更加一般的Anderson加速形式，即［10］

其中p是松弛系數，且0 ＜p≤1。迭代公式由迭代點u的線性組合和函數值G(u)的線性組合兩部分組成，也就是在迭代公式（3）的基礎上加入了歷史迭代點的信息。顯然，當p= 1 時算法流程如表1所示。目前，很多應用中均選取p= 1［11，19-23］。

2 Anderson 加速方法中松弛參數的選取

在Anderson 加速迭代一般形式（8）的基礎上，探討Anderson 加速方法中松弛參數對迭代方法的影響，并且適當擴大參數p的取值范圍，使其不受0 ＜p≤1的限制。

為了方便討論，首先將公式（8）中迭代點的加權平均uˉ(k)和函數值的加權平均Gˉ(k)記為

那么迭代公式可寫為

通過調整p的取值，分析參數取值對Anderson加速方法的影響。由式（9）可知，Gˉ(k)實際上是Anderson 加速算法1（參數p= 1）計算得到的迭代值，可以記=. 于是，迭代公式進一步寫為

其中?k=(Δu(k-mk)，…，Δu(k-1))，Δu(i)=u(i+1)-u(i)表示迭代點的增量。又因為u(k)=G(u(k))-fk，?k=?k- ?k，代入式（12）可得

將式（13）代入式（11），得到迭代公式的最終形式為

于是，含松弛參數的Anderson 加速算法可描述如表2。

3 非線性擴散方程的離散及求解

考慮二維區域Ω =(0，1) ×(0，1) 上的擴散方程

其中κ(u)為擴散系數，f(x，y)為源項。如果κ與u有關，偏微分方程（15）為非線性方程

將區域Ω劃分為N×N的均勻網格，對于方程（15），擴散算子采用五點有限差分離散。令ui，j表示u(xi，yj)的近似，則(xi，yj)處的離散形式為

對于式（16）中擴散系數在半點處的值，我們用兩端點處的平均值代替半點處的函數值，即

將未知量按自然序排列，將式（16）寫成F(u) = 0的形式，F為非線性方程的殘差向量。

采用Picard 迭代法求解非線性擴散方程［24］。Picard 迭代的關鍵是構造一個壓縮映射G，把非線性擴散方程的求解問題轉化為映射G的不動點問題。用u(k+1)表示下一個迭代點，構造Picard迭代

為了表示方便，把函數G(u)定義為

第k+ 1 步非線性迭代對應的Picard 迭代線性化方程組為

計算第k+ 1 步迭代點時，擴散系數用第k步的結果表示。同樣，使用五點有限差分法離散擴散算子。 對于網格中的任意節點i，j=1，2，…，N，離散格式為即構成一個N2階線性方程組，方程組的解就是下一個迭代點，這也意味著每一步迭代都要求解一個線性方程組。將未知量u(k+1)按照自然序方式排列，方程組可用矩陣形式表示為

系數矩陣P中各元素是關于上一步迭代點u(k)的函數，矩陣P可以寫為塊三對角形式

其中Aj為三對角矩陣，Bj和Cj都是對角矩陣。

對方程P(u(k))u(k+1)=b進行處理，引入d(k)=u(k+1)-u(k)，則線性方程組（22）可表示為

實際上，方程（23）的右端項是殘差向量F，即P(u(k))d(k)= -F(u(k))。于是，不動點函數可以表示為G(u(k+1))=u(k)+d(k)。求解非線性擴散方程的Picard迭代算法如表3所示。

表3 求解非線性擴散方程的Picard迭代算法Table 3 A Picard iterative algorithm for solving nonlinear diffusion equations

綜上推導可以看出，Picard 迭代法的系數矩陣不涉及導數項的計算，形式簡單。但Picard迭代法收斂速度通常較慢，且在許多情況下僅僅是線性收斂的。特別是涉及到非線性問題的求解，Picard迭代法常常會出現迭代序列收斂緩慢甚至發散的情況，需要尋求一些有效的迭代收斂加速方法。

4 數值實驗

將Picard迭代及不同松弛參數的Anderson加速方法應用到非線性擴散方程的求解中。實驗中，選取兩類含參數的擴散系數進行數值測試，分別是κ(u) = 1 +uβ和κ(u) = eγu， 記 作 模 型1 和模型2。

模型1 中，擴散系數為κ(u) = 1 +uβ(β≥1).令方程的精確解為u(x) = sin(πx)ey，對應的右端項為

邊界條件為

擴散系數中參數的選取是β∈{ }1，3，5 ，參數越大，表示方程的非線性越強。

模型2 中，取擴散系數κ(u) = eγu(γ＞0)，同樣令方程的精確解為u(x) = sin(πx)ey，對應的右端項為

邊界條件為

擴散系數中參數γ∈{ 0.75，1.00，1.25} 。

為了方便討論，本文中涉及到的方法記號為：①Picard 表示用Picard 迭代法求解。②AA（1）表示Anderson加速-1，即按照表1的流程實現Anderson 加速（p= 1）。③AA（2）表示Anderson 加速-2，即Anderson 加速迭代公式中含有松弛參數p，并按照表2對每一步迭代點進行更新。

另外，Anderson加速方法還涉及到加速深度m的選擇。實驗發現，m∈[4，10]時迭代次數較少。為提高計算效率，之后的相關實驗中取m= 5。

在數值實驗中，設置初始迭代點u0的分量全為1，收斂準則為‖F‖2≤10-8，即在殘差的2-范數小于預設精度時迭代終止。實驗過程中，記錄不同方法求解擴散方程的數值結果，迭代次數用IT表示，求解問題的時間用CPU表示。

4.1 松弛參數選取的數值實驗

對于Anderson加速Picard迭代法，選取不同的松弛參數p，使其在［-1，2］內變化，變化間隔為0.005。求解二維非線性擴散方程模型1 和模型2 問題，規模設定為64 × 64，分析參數對求解效果的影響。

由數值實驗可知，對于一些問題，調整松弛參數p，可以使Anderson 加速方法的迭代次數更少，提高收斂速度；對于不同的問題，松弛參數p的取值不同。當p為負數時，相較于p= 1 時的情況，迭代次數并不會減少，反而會增加，甚至不收斂；當p在1 附近變化時，迭代次數相對較少。分別選取模型1 和模型2 的兩類擴散系數的數值結果進行展示。其中，模型1 選取β= 1 和5 的情況，迭代次數隨參數變化的結果如圖1 所示；模型2 選取γ= 0.75和1.00的情況，結果如圖2所示。

圖1 Anderson加速中松弛參數選取對迭代次數的影響（模型1）Fig.1 Influence of relaxation parameter choice on iteration number of Anderson acceleration method （model 1）

圖2 Anderson加速中松弛參數選取對迭代次數的影響（模型2）Fig.2 Influence of relaxation parameter choice on iteration number of Anderson acceleration method(model 2)

圖1 給出了在網格規模為64 × 64 下，求解非線性擴散方程模型1 時p對迭代次數的影響。圖1（a）說明，當β= 1 時，Anderson 加速-1 需要迭代11次；擴大p的取值范圍后，當p∈[0.815，1.145]時，迭代次數仍為11。其中p＞1 時，意味著迭代值這一項的系數1 -p為負數。此外，當p為負數時，迭代次數較多甚至不能收斂。圖1（b）展示了β= 5 時的求解情況，曲線前半段說明迭代不能收斂，曲線后半段說明了迭代次數隨參數p的變化震蕩，Anderson 加速-1 的迭代次數為54，有一些取值能夠使迭代次數減少；當p= 0.995 時，迭代次數最少為39，相對Anderson 加速-1 的迭代次數而言，減少了1/4以上。

圖2給出了求解第二類模型的數值結果。從圖中可以看出，當p為負數時，迭代次數較多甚至不收斂；當p∈[0.5，2.0]時，迭代次數相對較少，并且均能找到使迭代次數更少的參數p的取值。圖2（a）展示了γ= 0.75的情況，Anderson加速-1的迭代次數為13，p在1 左右一小段區間能使迭代次數減少1 次。圖2（b）是γ= 1.0 的情況，Anderson 加速-1 的迭代次數為15；而當p∈[0.885，0.94]時，迭代次數為14。

綜上可以發現，p的選取對收斂效果的影響較大。但參數p的影響不是單調的，對于非線性強的問題，迭代次數的變化十分震蕩。Anderson加速-1中，參數p= 1 往往對應著較少的迭代次數。在一些情形下，還可以找更好的p取值，使迭代次數更少。并且，參數p可以不受0 ＜p＜1 的限制；對于一些問題，可以在p＞1 的情況找到使迭代次數最少的參數取值。

在小規模情況下對Anderson 加速方法進行不同松弛參數選取測試，得到了參數選取對方法效果有一定影響的結論。進一步，選定一些具有代表性的參數值，應用到較大規模的非線性擴散方程求解中。選擇3 種典型取值，記為p1，p2和p3，參數p的選取準則是能夠使迭代次數較少或p值較為遠離1。兩類模型的典型參數取值及相應的迭代次數IT 見表4，表4 中給出了規模為64 × 64的情況下，Anderson 加速中松弛參數的典型取值。

表4 兩類模型的典型參數取值及相應的迭代次數Table 4 Typical parameter values of the two types of models and the corresponding number of iterations

4.2 典型松弛參數的Anderson 加速方法在較大規模問題的上應用

根據4.1節的分析，選出較優的松弛參數，并比較Anderson加速方法和Picard迭代在求解更大規模問題上的應用效果。本節中，網格規模為128 ×128，256 × 256 和512 × 512。不同算例中，固定典型參數取值用于測試，統計選取固定典型參數求解模型問題的迭代次數和求解時間。求解模型1時，擴散系數中的參數β分別取1，3 和5，對應的數值結果見表5～7。為方便表述，N= 128 表示網格規模為128 × 128。

表5 不同方法求解模型1（κ = 1 + uβ，β = 1）的迭代次數和時間Table 5 Iteration numbers and solution time for model 1（κ = 1 + uβ，β = 1）by different methods

表6 不同方法求解模型1（κ = 1 + uβ，β = 3）的迭代次數和時間Table 6 Iteration numbers and solution time for model 1（κ = 1 + uβ，β = 3）by different methods

表5～7 均列出了3 種網格規模下，分別用Picard 迭代、3 種松弛參數取值的Anderson 加速求解模型1 的迭代次數和時間，3 個表分別對應3 種擴散系數的情況。從表中可以看出，對于同一個問題，網格規模越大、計算量越大，計算時間顯著增加。對比Picard迭代，不同網格規模下Anderson 加速方法均可減少約一半甚至一半以上的迭代次數。從求解時間來看，Anderson 加速方法求解更快。隨著β的增大，即問題的非線性增強，Anderson加速和Picard迭代的迭代次數均增加。

在小規模問題中使迭代次數最少的參數取值p，用于大規模問題的求解時，迭代次數不一定最少。由表5～6 可以看出，當β= 1 和3 時，迭代次數和Anderson加速-1的迭代次數相差不超過1；由表7 可知，當β= 5 時，p的3 種取值均能減少Anderson加速-1的迭代次數。

表7 不同方法求解模型1（κ = 1 + uβ，β = 5）的迭代次數和時間Table 7 Iteration numbers and solution time for model 1（κ = 1 + uβ，β = 5）by different methods

表8～10 展示了不同方法求解模型2 的結果，三個表分別對應擴散系數為γ= 0.75，1.00 和1.25的情況。從表中可以看出，同求解模型1時基本類似，當模型問題的非線性越強，迭代次數越多；對于同一問題，規模越大，迭代次數增加或不變。由表8～9 可知，當擴散項參數為γ= 0.75 和1.00時，Anderson 加速的迭代次數減少了一半以上；由表10 可知，當擴散項參數為1.25 時，加速后的迭代次數大約是Picard 迭代次數的1/3。從求解時間上看，Anderson 加速方法求解更快。松弛參數p的取值使迭代次數與Anderson 加速-1 的迭代次數相差不超過1；且p距離1 較遠、1 -p為負數的情況，也能使迭代收斂。

表8 不同方法求解模型2（κ = eγu，γ = 0.75）的迭代次數和時間Table 8 Iteration numbers and solution time for model 2（κ = eγu，γ = 0.75）by different methods

表9 不同方法求解模型2（κ = eγu，γ = 1.0）的迭代次數和時間Table 9 Iteration numbers and solution time for model 2（κ = eγu，γ = 1.0）by different methods

表10 不同方法求解模型2（κ = eγu，γ = 1.25）的迭代次數和時間Table 10 Iteration numbers and solution time for model 2（κ = eγu，γ = 1.25）by different methods

5 結 論

本文探討了Anderson 松弛參數的選取，并適當擴大參數p的范圍，將其應用到二維非線性擴散方程的求解中。首先，求解網格規模為64 × 64 的問題，分析數值結果、選取典型參數取值；然后，將其應用到網格規模為128 × 128，256 × 256 和512 × 512 的問題中。通過數值實驗，得出如下主要結論：

1）p的取值對Anderson迭代次數有影響。當p接近于0 或為負數時，迭代次數很多甚至不收斂。當p∈[0.5，2.0]時，迭代次數相對少一些。當p在1 附近時，往往對應著最少的迭代次數；但對于非線性強的問題，迭代次數較為震蕩。

2）Anderson加速中默認p= 1，這一取值往往對應著少的迭代次數。

3）合適的松弛參數可以有效提高Anderson 加速方法的效果。在很多情況下，可以找到使迭代次數比Anderson加速-1更少的參數p，最優的松弛參數選取依賴于具體的問題；對于非線性強的問題，不同的參數取值對應的迭代次數相差較大，更有可能找到使迭代次數大幅度減少的松弛參數p。

4）參數p的選取可以不受傳統0 ＜p≤1 的限制。在1 ＜p≤2 的范圍內，迭代也均能收斂。對于一些問題，甚至可以在p＞1 的情況找到迭代次數最少的參數取值。