胡宏伶,陳傳淼

(湖南師范大學(xué)數(shù)學(xué)與計算機科學(xué)學(xué)院,高性能計算與隨機信息處理教育部重點實驗室(HPCSIP),中國 長沙 410081)

如何求解由有限元或差分法所導(dǎo)出的大型線性方程組是現(xiàn)代科學(xué)與工程計算中的重要問題之一. 考慮n階對稱正定線性方程組

Ax=b.

(1)

當未知數(shù)超過數(shù)百萬后, 一般直接法因工作量浩大而失效了, 而各種迭代法受到特別關(guān)注. 除經(jīng)典的Jacobi迭代,Gauss-Siedel迭代, 超松弛迭代法(SOR)外, 還有Hestenes和Stiefel于1951年提出共軛梯度法(ConjugateGradient,CG)[1]. 利用CG算法求解n階對稱正定線性方程組, 理論上最多n步即可求得準確解, 從這個意義上講CG算法是一種直接法. 但在舍入誤差存在的情況下, 即使計算n步也無法得到準確解. 從這個意義上講,CG是一種有效的迭代法, 也有收斂性問題. 1971年,Reid發(fā)現(xiàn)CG算法具有壓縮作用, 即迭代次數(shù)m遠小于n即可達到精度要求[2]. 由于CG法是A正交意義下的投影, 因此CG迭代法按A范數(shù)有2個經(jīng)典估計(單調(diào)性和收斂性)[3-5], 這是CG法的2個基本結(jié)果. 然而, 人們有時更關(guān)心迭代解誤差的l2模估計. 因此,需要在l2范數(shù)意義下重新研究CG迭代法的收斂性問題. 本文給出了CG迭代法在l2范數(shù)意義下的單調(diào)性和收斂性定理, 對結(jié)合CG法來求解大規(guī)模線性方程組的多重網(wǎng)格法, 特別是外推瀑布式多重網(wǎng)格法(EXCMG)按l2模的收斂性有重要作用[6-13].

1 共軛梯度法

在n維歐氏空間Rn中定義內(nèi)積, 能量模和l2模

共軛梯度法的計算格式如下:

1) 任取x0∈Rn, 計算r0=b-Ax0并取p1=r0.

2) 對k=1,2,…, 采用以下公式計算

(2)

3) 若rk-1=0或(pk,Apk)=0, 計算終止, 此時xk-1=x*.

算法中x*為線性方程組(1)的準確解,xk為第k次迭代解. 記迭代誤差ek=x*-xk. 則CG迭代格式(2)按能量模有如下2個熟知的結(jié)論[2, 7, 11]:

引理1(單調(diào)性).‖ek+1‖A≤‖ek‖A.

2 CG法的l2模單調(diào)性與收斂性

引理3(范數(shù)等價性[6]). 若A是n階對稱正定矩陣, 則對任意n維列向量x, 有

其中λ1,λn分別為矩陣A的最小和最大特征值.

定理1(l2模收斂性). 若A是對稱正定陣,則CG迭代按l2模有收斂性估計

證結(jié)合引理2和3即得

注意到對稱正定矩陣ρ(A)=λn/λ1, 上式整理即得

引理4對迭代誤差ek+1及任意的rj(j≤k), 以下內(nèi)積與j無關(guān)

(3)

證由(2)知

(4)

由殘量正交性(ri,rj)=0(i≠j)[8]知

(5)

由j≤k并利用(5)得

(6)

其中

(ej,rj)=(ej-1-cipj,rj)=(ej-1,rj)=…=(e0,rj)=(e0,rj-1-cjApj)=(e0,rj-1)-cj(Ae0,pj)=

(e0,rj-1)-cj(pj,r0)=(e0,rj-1)-cj‖rj-1‖2=(e0,rj-2)-cj-1‖rj-2‖2-cj‖rj-1‖2=

(7)

結(jié)合(6)和(7)即得(3)式, 引理得證.

引理5引理4中定義的序列Bk為嚴格單調(diào)下降的正序列, 即

Bk>Bk+1>0.

(8)

證由(2)知ck+1>0, 利用(3)易得

Bk+1=Bk-ck+1‖rk‖2

(9)

由定理1知CG迭代按l2模收斂, 即‖ek‖→0, 因此

|Bk|=|(ek,r0)|≤‖ek‖·‖r0‖→0

(10)

結(jié)合(9)和(10)知，引理得證.

定理2(l2模單調(diào)性). 若A是對稱正定陣,則CG迭代誤差按l2模嚴格單調(diào)下降

‖ek+1‖<‖ek‖.

(11)

證由引理4及(4), (8)知

因此,

‖ek+1‖2=(ek+1,ek)+(ek+1,ek+1-ek)<(ek+1,ek)≤‖ek+1‖·‖ek‖.

由此即得(11), 定理2得證.

參考文獻：

[1] HESTENES M R, STIEFEL E. Methods of conjugate gradients for solving linear systems[J].J Res Nat Bur Stand, 1952,49(6):409-436.

[2] REID J K. On the method of conjugate gradients for the solution of large systems of linear equations[C]//REID J K. Large sparse sets of linear equations[M]. London: Academic Press, 1971.

[3] HACKBUSCH W. Iterative solution of large sparse systems of equation[M]. New York:Springer-Verlag, 1994.

[4] YOUNG D M. Iterative solution of large sparse systems[M]. New York: Academic, 1971.

[5] GOLUB G H, O’LEARY D P. Some history of the conjugate gradient and Lanczos methods[J].SIAM Rev, 1989, 31(1):50-102.

[6] 李慶揚, 王能超, 易大義. 數(shù)值分析[M]. 北京：清華大學(xué)出版社, 2008.

[7] 曹志浩, 張玉德, 李瑞遐．矩陣計算和方程求根[M]. 北京: 高等教育出版社, 1994.

[8] 胡家贛. 線性代數(shù)方程組的迭代法[M]. 北京：科學(xué)出版社, 1997.

[9] SHAIDUROV V. Some estimates of the rate of convergence for the cascadic conjugate gradient method[J]. Comp Math Appl, 1996,31(4-5):161-171.

[10] SHAIDUROV V, TOBISKA L. The convergence of the cascadic conjugate-gradient method applied to elliptic problems in domains with re-entrant corners[J]. Math Comput, 1999,69:501-520.

[11] CHEN C M, XIE Z Q, LI C L,etal. Study of a new extrapolation multigrid method[J].Natur Sci J Hunan Normal Univ, 2007,30(2):1-5.

[12] CHEN C M, HU H L, XIE Z Q,etal.l2-error of extrapolation cascadic multigrid[J]. Acta Math Sci Ser B, 2009,29(3): 539-551.

[13] CHEN C M, SHI Z C, HU H L. On extrapolation cascadic multigrid method[J]. J Comput Math, 2011,29(6):684-697.