求解大型稀疏鞍點問題的對稱超松弛方法

摘要:為了快速有效地求解大型稀疏鞍點問題，在SOR-like迭代算法的基礎(chǔ)上，結(jié)合SSOR分裂，構(gòu)造了一種解鞍點問題的SSOR-like迭代算法，并研究了該算法的收斂性。數(shù)值例子證明:通過參數(shù)值的選擇，SSOR-like算法比SOR-like算法具有更快的收斂速度和更小的迭代次數(shù)，選擇了合適的參數(shù)值后，可以大大提高算法的收斂效率。

關(guān)鍵詞:鞍點問題;迭代法;SOR-like 方法;SSOR-like方法

中圖分類號:O241文獻標識碼:A文章編號:1009-3044(2010)21-5979-04

The SSOR Iterative Algorithms for Large Sparse Saddle Point Problems

PAN Chun-ping

(Zhejiang Industry Polytechnic College， Shaoxing 312000， China)

Abstract: In this paper， we mainly study the iterative algorithms for large sparse saddle point problems(SPP).It is of great interest to develop fast and efficient iterative methods for saddle point problems.Based on the SOR-like iterative scheme and the SSOR splitting， we present the SSOR-like iterative scheme. The convergence results are also given. The numerical results show that our new method is more efficient than SOR-like method.

Key words: saddle-point problems; SOR-like method; SSOR-like method; iterative method

大型稀疏鞍點問題的求解非常重要，在很多領(lǐng)域都應(yīng)用過。如電磁學(xué)Maxwell方程的有限元離散和計算流體力學(xué)中的Stokes方程以及二階橢圓方程問題的混合有限元方法，含有圖像處理問題，限制條件的二次優(yōu)化問題，最小二乘問題，線性彈性力學(xué)問題等等。本文主要考慮具有如下形式的鞍點問題:

(1)

其中A∈Rm×m為對稱正定矩陣(SPD)，B∈Rm×m為列滿秩矩陣，即 rank(B)=n ，向量x，p∈Rm，向量y，q∈Rn (這里我們假定m≥n)。BT是B的轉(zhuǎn)置矩陣。P，q是已知向量。在這樣的假設(shè)下，鞍點問題(2)有唯一解[1]。

目前，求解鞍點問題已經(jīng)存在很多方法，其中包括直接法、Uzawa 算法、SOR-like 算法[10-11]、HSS 算法、GAOR 算法[12] 等。由于直接法在求解大型稀疏線性方程組時，可能會產(chǎn)生許多非零元，從而導(dǎo)致運算量大量增加。同時，對于條件數(shù)很大的系數(shù)矩陣，直接法往往會產(chǎn)生很大的誤差。 因此在求解大型稀疏線性方程組時，我們通常會選擇迭代法。考慮(1)的系數(shù)矩陣:

(2)

這說明鞍點問題的系數(shù)矩陣有正和負的特征值。它的另一個特點是對角塊中有零矩陣。綜上所述，鞍點問題(1)是對稱不定的、系數(shù)矩陣對角塊中含有奇異矩陣的線性系統(tǒng)。它的這些特點使得一些著名的迭代算法，如PCG [3] 算法和SOR算法[4] 難以直接應(yīng)用。Golub等人通過對系數(shù)矩陣進行適當(dāng)?shù)姆纸猓瑯?gòu)造出了一種SOR-like迭代方法[6]。為了表示上的方便，我們將方程組(1)等價表示為:

(3)

將方程組(3)的系數(shù)矩陣 作如下分裂:

(4)

其中:

(5)

這里Q∈Rn×n是對稱非奇異矩陣。 設(shè)ω>0為松弛參數(shù)，考慮如下迭代格式，得到

SOR-like算法:

(6)

1)SSOR-like迭代算法:

下面仍將方程組(3) 的系數(shù)矩陣A 作如下分裂:

(7)

其中:

(8)

這里Q∈Rn×n是對稱非奇異矩陣。考慮如下的SSOR 迭代格式:

(9)

(10)

迭代格式(9)可以簡記為:

(11)

其中迭代矩陣:

(12)

其中J=Q-1BTA-1B。由此我們可以得到以下的SSOR-like 迭代算法:

設(shè)Q∈Rn×n是對稱非奇異矩陣， 給定初始向量x(0)∈Rm，y(0) ∈Rn和一個松弛參數(shù) ω>0.令k=0，1，2，…，直到迭代序列{(x(k)T，y(k)T)T}收斂， 計算

(13)

2 算法的收斂性分析

引理1. [7] 實二次方程λ2-bλ+c=0的兩個根的模均小于1當(dāng)且僅當(dāng)|c|<1，|b|<1+c。

引理2. 設(shè)μ是J=Q-1BTA-1B 的一個特征值。如果λ滿足

(14)

那么λ是Mω的一個特征值。反之，設(shè)λ≠1是Mω的一個特征值且λ≠(1-ω)2，若 滿足(14)， 則μ是J 的一個非零特征值。

證: 假設(shè)λ是迭代矩陣Mω的一個非零特征值，是其對應(yīng)的特征向量。則由(12)可得

(15)

即: (16)

于是: (17)

由于A 是對稱正定的，Q 是非奇異的，進一步可得到

(18)

設(shè)μ是J=Q-1BTA-1B的一個特征值，可得

(19)

反之，我們可以同理證明引理的后半部分。

定理1. 設(shè)A∈Rm×m，Q∈Rn×n是對稱正定矩陣， B∈R m×n為列滿秩矩陣。令μmin， μmax分別為J=Q-1BTA-1B的最小和最大特征值. 若ω滿足

(20)

則SSOR-like迭代算法收斂。

證: 由引理(2) 中的等式(14) 得:

(21)

其中 。根據(jù)引理(1)當(dāng)且僅當(dāng)

(22)

于是可得:

(23)

解這個不等式組可以得到

(24)

定理得證。

3 數(shù)值例子

下面我們給出上面算法的數(shù)值例子。設(shè)A是一個m×m的矩陣。定義如下:

(25)

設(shè)B是一個m×n的矩陣。滿足:

(26)

向量p ，q可以任意選擇。 對于SOR-like 方法，SSOR-like 方法，我們均選擇預(yù)處理矩陣Q=BTB。計算終止的條件是，其中

(27)

對于SOR-like 方法的最優(yōu)參數(shù)的確定根據(jù)前面的結(jié)論。對SSOR-like 方法的參數(shù)我們是通過嘗試和誤差比較的方法獲得的。下面給出數(shù)值實驗的結(jié)果。所有的結(jié)果都是在Intel E2180 2.0GHZ CPU， 2.0G Memory 條件下獲得的。

從表中可以看出，在同一精度的條件下，通過ω值的選擇，SSOR-like 算法比SOR-like 算法具有更快的收斂速度和更小的迭代次數(shù)?？偟膩碚f，SSOR-like算法是一種較SOR-like 算法很有競爭力的算法， 特別是選擇了合適的參數(shù)值后， 可以大大提高算法的收斂效率。數(shù)值試驗還表明當(dāng)ω取值接近1時，該算法接近最佳的收斂速度。當(dāng)然ω的最優(yōu)取值還需進一步的研究確定。

參考文獻:

[1] Benzi M，Golub G H， Liesen J. numerical solution of saddle point problems，Acta Numerica，2005(14):1-137.

[2] Li C J，Li B J， Evans D J.A generalized successive overrelaxation method for least squares problems.BIT，1998(38):347-356.

[3] Golub G H， Van Loan C F. Matrix Computations.3rd Edition，The Johns Hopkins University Press，Baltimore and London，1996.

[4] Axelsson O. Iterative Solution Methods.Cambridge University Press， Cambridge，1994.

[5] Bramble J H， Pasciak J E， Vassilev A T.Analysis of the inexact Uzawa algorithm for saddle point problem.SIAM J.Numer.Anal.，1997，3(3):1072-1092.

[6] Golub G H，Wu X，Yuan J Y. SOR-like methods for augmented systems.BIT，2001(41):71-85.

[7] Young D M. Iterative Solutions of Large Linear Systems.Academic Press，New York，1971.

[8] Bai Z Z， Parlett B N， Wang Z Q. On generalized successive Overrelaxation methods for augmented linear systems，2005(102):1-38.

[9] Zhang G F， Lu Q H， On generalized SSOR method for augmented systems， Accepted manuscript， J.Comput.，2007.

[10] 曹志浩， 數(shù)值線性代數(shù)[M].上海:復(fù)旦大學(xué)出版社，1996.

[11] 曹志浩，變分迭代法[M].北京:科學(xué)出版社，2005.

[12] 邵新慧.求解鞍點問題的一般加速超松弛方法[J].數(shù)值計算與計算機應(yīng)用，2006(4):241-248.

注:本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文