求解奇異鞍點問題的參數(shù)化預(yù)條件HSS方法

呂月燕，張乃敏

(溫州大學(xué)數(shù)學(xué)與信息科學(xué)學(xué)院，浙江溫州 325035)

求解奇異鞍點問題的參數(shù)化預(yù)條件HSS方法

呂月燕，張乃敏?

(溫州大學(xué)數(shù)學(xué)與信息科學(xué)學(xué)院，浙江溫州 325035)

利用參數(shù)化預(yù)條件HSS迭代方法對奇異的大型稀疏線性系統(tǒng)進行了求解，分析了該方法的半收斂性和參數(shù)的最優(yōu)選取問題，并且與其它方法進行了比較．?dāng)?shù)值實驗結(jié)果表明：參數(shù)化預(yù)條件HSS迭代方法在求解奇異鞍點問題時比其它方法更有效．

奇異鞍點問題；預(yù)條件；迭代方法；半收斂性；線性系統(tǒng)

考慮以下線性系統(tǒng)的迭代解：

其中B?Cp×p是Hermitian正定矩陣，E?Cp×q是列秩虧的，p≥q，E*為E的共軛轉(zhuǎn)置，f?Cp，g?Cq．（1）形式的線性系統(tǒng)統(tǒng)稱為鞍點問題，在現(xiàn)代科學(xué)的諸多領(lǐng)域都有廣泛應(yīng)用[1-2]．

當(dāng)大型稀疏線性系統(tǒng)（1）的系數(shù)矩陣為非奇異時，那么矩陣E是列滿秩的，系統(tǒng)（1）被稱為非奇異鞍點問題．解決此類問題的迭代方法已有不少，例如，白中治等提出了一系列的預(yù)條件Hermitian和Non-Hermitian分裂方法（PHSS）[3]及加速Hermitian和Non-Hermitian分裂方法（AHSS）[4]．當(dāng)線性系統(tǒng)（1）的系數(shù)矩陣為奇異時，即E為列秩虧矩陣，被稱為奇異鞍點問題．解決此類問題的方法也有不少，例如，鄭兵等提出了參數(shù)Uzawa方法[5]，馬海鳳等研究了塊對角PPIU方法[6]等．本文將利用參數(shù)化預(yù)條件HSS迭代方法（PPHSS）對奇異鞍點問題進行求解，數(shù)值實驗結(jié)果表明，參數(shù)化預(yù)條件HSS迭代方法在求解奇異鞍點問題時比其它方法更有效．

1 參數(shù)預(yù)條件HSS方法

對線性方程組（1）的系數(shù)矩陣A進行如下HSS分裂[7]：

PPHSS迭代方法：記n=p+q，令x(0)?Cn為初始向量，采用如下的迭代形式：

其中α和β是給定的正實數(shù)，矩陣P取如下形式：

此處C是一個Hermitian正定矩陣．顯然，PPHSS方法的迭代格式（2）可以等價于

其中，

這里的T(α,β)是PPHSS方法的迭代矩陣，Ip和Iq是階數(shù)分別為p和q的單位矩陣．實際上，（4）可由下面的分裂得到：

經(jīng)過簡單的計算，可得：

顯然，矩陣M(α,β)可以作為一個預(yù)條件子用來求解線性方程組（1），稱為PPHSS預(yù)條件子．為了進一步分析PPHSS迭代的半收斂性，用另一種等價的形式來替代該迭代．記

2 PPHSS方法的半收斂性分析

對于定常迭代（4），我們知道如果系數(shù)矩陣A是非奇異的，那么定常迭代收斂當(dāng)且僅當(dāng)?shù)仃囎V半徑小于1．若系數(shù)矩陣A是奇異的，迭代矩陣有特征值1，所以它的譜半徑不會比1小，對于這種情況的迭代矩陣T，我們介紹它的擬譜半徑ν(T)：ν(T)=max｛|λ|:λ?σ(T),λ≠1｝，其中σ(T)表示迭代矩陣T特征值的集合．對于任何矩陣K?Cn×n，如果i是使得rank(Ki)=rank(Ki+1)成立的最小非負整數(shù)，那么i稱做矩陣K的指標，記為i=index(K)．實際上，index(K)是矩陣K的零特征值對應(yīng)的最大Jordan塊的階數(shù)．

引理1[8]迭代方法（4）半收斂當(dāng)且僅當(dāng)index(I-T(α,β))=1且ν(T(α,β))＜1．

引理2[9]index(I -T(α,β))=1，當(dāng)且僅當(dāng)，對任意的0≠Y?R(A)，Y ?N(AM-1)，其中，R(·)和N(·)分別為相應(yīng)矩陣的值域和零空間．

定理1 對于（4）中的迭代矩陣T(α,β)，有index(I-T(α,β))=1成立．

證明：令

引理4 迭代矩陣T(α,β)的特征值λ按以下情形分布：

引理6[9]實二次方程x2-bx+c=0的根均小于1，當(dāng)且僅當(dāng)|c|＜1和|b|＜1+c．

定理2 如果迭代參數(shù)α和β滿足：

那么，PPHSS方法迭代矩陣的擬譜半徑滿足ν(T(α,β))＜1．

3 數(shù)值實驗

本節(jié)將給出一個例子，通過與其它有效的迭代方法比較迭代步數(shù)（IT）、CPU耗時（CPU）、迭代殘差（RES）來判斷PPHSS方法及其作為預(yù)條件子（PPHSS-GMRES）的有效性．在下面的實驗中，初始向量x(0)取為令向量，一旦迭代滿足條件

或者迭代次數(shù)超過1 000則迭代終止．所有實驗將利用Matlab[version 7.0.0.19920(R14)]解決，在Intel(R)Celeron(R)CPU 1000M @1.80GHz，內(nèi)存2GB的個人電腦上運行．

例1[5]對于奇異鞍點問題（1）中的塊矩陣有如下形式：

關(guān)于矩陣P，對其中的C取兩種情況．情況I：C=I；情況II：其中B*是矩陣B的塊對角陣．兩種情況下，各迭代方法的最優(yōu)參數(shù)和擬譜半徑見表1，IT，CPU，RES分別見表2和表3．從表1可以發(fā)現(xiàn)，l越大，相同方法的擬譜半徑也越大．從表2和表3可以發(fā)現(xiàn)，在給定合適的參數(shù)后，PPHSS方法不管是在迭代步數(shù)還是迭代時間上都比其它方法少，這說明PPHSS方法是比較有效的．從表2和表3還可以看出，PPHSS預(yù)條件子和SPPHSS預(yù)條件子都能夠很有效地改善GMRES算法的收斂速度．注意，

表1 實驗例1中各方法的最優(yōu)參數(shù)和擬譜半徑

表2 情況I時各迭代方法的IT, CPU, RES

迭代方法 項 目 l=8 l=16 l=24 l=32數(shù) 值IT 883 2560 5450 10376 GMRES CPU 0.524 3.179 12.572 16.264 RES(10-9)9.824 3 9.992 5 9.990 3 9.995 0 IT 18 27 31 35 PHSS-GMRES CPU 0.052 0.344 1.350 3.656 RES(10-9)5.990 0 5.371 9 3.321 7 8.675 5 IT 9 12 13 14 SPPHSS-GMRES CPU 0.033 0.295 1.310 3.497 RES(10-9)3.702 2 1.574 3 4.132 4 7.064 2 IT 10 12 14 15 PPHSS-GMRES CPU 0.035 0.296 1.333 3.501 RES(10-9)5.916 1 9.087 0 5.526 2 9.202 2

表3 情況II時各迭代方法的IT, CPU, RES

本文主要對參數(shù)化預(yù)條件HSS方法求解奇異鞍點問題的半收斂性進行了研究，并分析了參數(shù)的最優(yōu)選取方法．在上述內(nèi)容的研究過程中也遇到了一些問題，有待于日后進一步研究探索．

[1] Elman H C, Ramage A, Silvester D J. A Matlab toolbox for modelling incompressible flow [J]. ACM Trans Math Softw, 2007, 33: 1-18.

[2] Wright S. Stability of augmented system factorization in interior-piont methods [J]. SIAM J Matrix Anal Appl, 1997, 18: 191-222.

[3] Bai Z Z, Golub G H, Pan J Y. Preconditioned Hermitian and skew-Hermitian Splitting methods for non-Hermitian positive semidefinite linear systems [J]. Numer Math, 2004, 98: 1-32.

[4] Bai Z Z, Golub G H. Accelerated Hermitian and skew-Hermitian splitting iteration methods for saddle-point problems [J]. SIAM J Numer Anal, 2007, 27: 1-23.

[5] Zheng B, Bai Z Z, Yang X. On semi-convergence of parameterized Uzawa methods for singular saddle point problems [J]. Linear Algebra Appl, 2009, 431: 808-817.

[6] Ma H F, Zhang N M. A note on block-diagonally preconditioned PIU methods for singular saddle point problems [J]. Int J Comput Math, 2011, 88: 3448-3457.

[7] Bai Z Z, Golub G H, Ng M K. On inexact Hermitian and skew-Hermitian splitting methods for non-Hermitian positive definite linear systems [J]. Linear Algebra Appl, 2008, 428: 413-440.

[8] Abraham B, Plemmons R J. Nonnegative Matrices in the Mathematical Science [M]. New York: SIAM, 1994: 43-52.

[9] Zhang N M, Wei Y M. On the convergence of general stationary iterative methods for Range-Hermitian singular linear systems [J]. Numer Linear Algebra Appl, 2010, 17: 139-154.

[10] Li X, Yang A L, Wu Y J. Parameterized preconditioned Hermitian and skew-Hermitian splitting iteration method for saddle-point problems [J]. Int J Comput Math, 2014, 91: 1224-1238.

[11] Golub G H, Van Loan C F. Matrix Computions [M]. 3rd ed. Baltimore: The Johns Hopkins University Press, 1996: 23-27.

The Study of the Parameterized Preconditioned HSS Method to Solve Singular Saddle Point Problems

LV Yueyan, ZHANG Naimin
(College of Mathematics and Information Science, Wenzhou University, Wenzhou, China 325035)

In this paper, the HSS iterative method is used to solve the large-scale singular sparse linear system by means of the parameterized precondition. The method of the semi-convergence and the optimal parameter selection problem is analyzed and meanwhile compared with other methods. Numerical experimental results show that the parameterized preconditioned HSS iterative method in the field of the singular saddle point problemsolution is more effective than other methods.

Singular Saddle Point Problem; Precondition; Iterative Method; Semi-convergence; Linear System

O241

A

1674-3563(2016)04-0001-08

10.3875/j.issn.1674-3563.2016.04.001 本文的PDF文件可以從xuebao.wzu.edu.cn獲得

(編輯：王一芳)

2015-09-29

國家自然科學(xué)基金(61572018)；浙江省自然科學(xué)基金(LY15A010016)

呂月燕(1991- )，女，江西九江人，碩士研究生，研究方向：計算數(shù)學(xué)．?通訊作者，nmzhang@wzu.edu.cn