1、Krylov子空間、優(yōu)化問(wèn)題與共軛梯度法自動(dòng)化富曉鵬工程實(shí)踐中經(jīng)常需要求解大型線(xiàn)性系統(tǒng)KU=F。在很多情況下矩陣K是非常 稀疏的，比如來(lái)自偏微分方程的離散化等，此時(shí)矩陣中每行僅有較少的非零元素。 面臨這樣的問(wèn)題，我們首先面對(duì)的問(wèn)題是，應(yīng)該采用直接消元法還是迭代方法。 對(duì)前者來(lái)說(shuō)，為充分利用系數(shù)特性，節(jié)點(diǎn)重編號(hào)是重要的；而對(duì)后者來(lái)說(shuō)，適當(dāng) 的預(yù)處理是關(guān)鍵。本文將重點(diǎn)放在后一類(lèi)方法中的一種進(jìn)行介紹與分析，即共軛梯度法。共軛 梯度法適用于矩陣K為對(duì)稱(chēng)陣的情況，算法本身簡(jiǎn)潔高效，且與一些其他的數(shù) 學(xué)理論、概念相緊密聯(lián)系，本文分析了共軛梯度法與Krylov子空間，以及優(yōu)化 問(wèn)題之間隱含的聯(lián)系，并簡(jiǎn)要給出

2、算法框架。1.線(xiàn)性方程組迭代解法與Krylov子空間我們考慮迭代法求解線(xiàn)性方程組Ax=b。假定未采用預(yù)處理矩陣P，或P矩 陣已經(jīng)隱含在A與b中。迭代法求解格式如下： TOC o 1-5 h z P - x = (P 一 A) - x + b(1)為說(shuō)明問(wèn)題，我們考慮簡(jiǎn)單的迭代格式P=I，并且x1=b。則迭代的最初幾步 為：x = (I - A)b + b = 2b - Ab(2)x3 = (I - A)x2 + b = 3b - 3Ab + A2b(3) 由上面幾個(gè)式子可得，以上迭代格式第j步的解Xj是b，Ab，Aj-Ib的線(xiàn) 性組合。當(dāng)A矩陣稀疏時(shí)，這些向量可以采用矩陣向量乘法的稀疏技巧很快

3、得 到。以上發(fā)現(xiàn)自然與Krylov子空間的概念相聯(lián)系起來(lái)。Krylov 矩陣：K. = b Ab 血b Aj_1bKrylov子空間：K = b，Ab，Aj-ib的所有線(xiàn)性組合Krylov命名了向量b，Ab，A-ib的全部線(xiàn)性組合構(gòu)成的子空間，并認(rèn)為在這一子空間中，有比上例中特定元素更與線(xiàn)性方程組的解相接近的元素。共 軛梯度法就是在這一子空間中，每一步迭代都依照某種標(biāo)準(zhǔn)尋求最優(yōu)元素的線(xiàn)性 方程組解法。對(duì)于每一步的余項(xiàng)rk=b-Axk,這一標(biāo)準(zhǔn)的不同就衍生出不同的解法:. K.中選取Xj，使得余項(xiàng)rk與子空間K.正交= Conjugate Gradients. %中選取，使得余項(xiàng)rk有最小范數(shù)=

4、 GMRES和MINRES. K.中選取 Xj，使得 rk 與子空間 Kj(AT)正交= BiConjugate Gradients2.共軛梯度法與Krylov子空間通常來(lái)說(shuō)，Krylov基底指其經(jīng)過(guò)Arnoldi算法生成的正交基底qq?.,%。在Arnoldi算法中，新的基向量由t=Aqj-1與基向量q1,.,qj-1得到。也即，對(duì) i = 1, 2,j-1, q.Tq.=0(4)對(duì)于第k步迭代，由于b屬于子空間K，xk屬于子空間Kk，余項(xiàng)rk=b-Axk 應(yīng)該在子空間Kk+1中。又由于共軛梯度中rk與Kk正交，rk一定是qk+的倍數(shù)。 rk和qk+1的不同僅在于qk+1是規(guī)范化的。這就是共

5、軛梯度法與Krylov子空間的隱 含聯(lián)系?；谶@一點(diǎn)，基向量q互相正交即可得出余項(xiàng)r也應(yīng)互相正交。也即， TOC o 1-5 h z 對(duì) i k, riTrk = 0(5)類(lèi)似的，rk-1是qk的倍數(shù)，那么dr=rk-rk-1應(yīng)該與更早的子空間Ki相正交，ik。又因?yàn)閐x=xi-xi-1屬于子空間虬，那么，dxTdr=0o 將 dr展開(kāi)，得rk - rk-1 = (b - Axk)- (b AxJ = -A(xk - Xk)(6)那么，x的更新量是“A正交”的或“共軛”的，(xi - xi.1)T A 伉-xk-1)= 0, for i k(7)這也就是共軛梯度法的名字由來(lái)。3.共軛梯度法與優(yōu)

6、化問(wèn)題為說(shuō)明共軛梯度法與優(yōu)化問(wèn)題的關(guān)系，以下首先偽碼形式給出共軛梯度算法。% for linear equation Ax = bd0 = r0 = b, x0 = 0for k = 1,2,., k7 77 maxak=rk-1Trk-1/dk-1TAdk-1(8)xk=xk-1 +ak dk-1(9)rk=rk-1 -akAdk-1(10)Pk=rkTrk/rk-1Trk-1(11)dk=rk +Pk dk-1(12)對(duì)于線(xiàn)性方程組Ax=b，定義能量函數(shù)E(x) = 1/2xtAx - xTb，則當(dāng)A是正定 陣時(shí)，最小化能量函數(shù)E(x)等價(jià)于求解Ax=b。共軛梯度法在漸次增大的Krylov

7、 子空間中搜索E(x)的最小值。第一個(gè)子空間K1是沿方向d0=b的直線(xiàn)，在這條直線(xiàn)上x(chóng)=ab使能量函數(shù)最 小，即得到 a1： E(ab) = 1/2a2bTAb - abTb 在 a1 = bTb/bTAb 處取極值。這一 a1 就 是共軛梯度法偽碼式(8)中的值。能量函數(shù)E(x) = 1/2xtAx - xTb的梯度為Ax-b，若使用梯度下降法，則使用 負(fù)梯度方向rk = b-Axk即可。然而梯度下降法局部收斂性能較好，全局收斂性能 卻較差。上述偽碼采用的(12)的更新方法是保證搜索方向d1 = r1 +p1 d0與原方向 依式(7)的含義“A正交”。依照更新方向和更新步長(zhǎng)，即可得到下一步的值xk = xk-1 +ak dk-1。以此迭代求解，直到滿(mǎn)足停止條