為甚麼保留整個 Krylov 基底?
前一篇筆記討論了對稱正定矩陣的共軛梯度法。對稱性與正定性在其中有實際作用:它們提供能量範數,並容許短遞推式。離散化的輸運算子或一般牛頓(Newton)法的 Jacobian 矩陣未必具備這些性質。我們仍希望只用矩陣向量乘積來求解,但需要改用另一個最小化問題,並建立不依賴對稱性的基底。
設 A∈Rn×n 非奇異,要求解 Ax=b。選定初始近似 x0,計算 r0=b−Ax0。若 r0=0,直接停止。否則令 β=∥r0∥2 及 v1=r0/β。本篇一律採用歐幾里得(Euclid)內積與範數,而且所有代數運算均在精確算術下進行。非奇異假設會在證明中明確使用,並非可有可無的附帶條件。
GMRES 第 k 步所用的修正空間是
Kk(A,r0)=span{r0,Ar0,…,Ak−1r0}.
即使這些冪向量在代數上線性無關,它們也可能幾乎平行,不適合直接作為計算基底。Arnoldi 方法改為建立同一空間的標準正交基底;GMRES 再從這組基底的線性組合中,選出殘差最小的修正。我們先證明有限維的精確恆等式;浮點穩定性需要另外分析。
Arnoldi 正交化及其停止條件
定義 1.3.1
(一次精確 Arnoldi 步驟)
假設 v1,…,vj 為標準正交。從 w=Avj 開始,依次對 i=1,…,j 計算
hij=viTw,w←w−hijvi.(1)令 hj+1,j=∥w∥2。若此數為正,定義 vj+1=w/hj+1,j;若為零,停止建立基底,因為把 w 規一化會除以零。
在精確算術下,減去新方向的分量會保留對較早方向的正交性。具體來說,若 ℓ<i,更新把 vℓTw 改變了 −hijvℓTvi=0。所以最後的 w 與所有已建立的 vi 都正交。此外,較早的減法不會改變與 vi 的內積,故儲存的係數等於 hij=viTAvj。這個等式使用了精確正交性,不能直接假定浮點計算所得向量也完全滿足它。
若這一步沒有停止,把 (1) 重排可得
Avj=i=1∑j+1hijvi.(2)
寫成 Vk=[v1 ⋯ vk]。若 j=1,…,k 都有 hj+1,j>0,便已有 k+1 個標準正交向量,因此必須有 k<n。把係數排成 (k+1)×k 的上 Hessenberg 矩陣 Hk:當 i≤j+1 時,其 (i,j) 項為 hij;當 i>j+1 時則為零。「上 Hessenberg」表示主對角線以下只有第一條次對角線可以非零。逐列合併 (2),得到
AVk=Vk+1Hk,Vk+1TVk+1=Ik+1.(3)
命題 1.3.2
(Arnoldi 向量確實生成所需空間)
在上述沒有中斷的假設下,對 1≤j≤k+1,Vj 的各列構成 Kj(A,r0) 的標準正交基底。
j=1 時結論成立。假設結論對 j 成立。因為 vj∈Kj,故 Avj∈AKj⊆Kj+1。被減去的各向量也屬於該空間,所以 (1) 中下一個非零 w 仍屬於 Kj+1。規一化後,它與原有 j 個向量正交,故增加了一個獨立方向。Kj+1 由 j+1 個向量生成;其中這 j+1 個獨立向量因此已是基底。歸納完成。特別地,非零次對角線係數代表真正出現了新的方向。
概念視角代數
把 Arnoldi 看作 Krylov 矩陣的 QR 分解
由歸納法,vj 等於 Aj−1r0 的正倍數加上 Kj−1 中的向量,所以 Ajr0 垂直於 Kj 的分量是 vj+1 的正倍數。因此 Arnoldi 正好給出精簡 QR 分解
Kk=[r0 Ar0 ⋯ Ak−1r0]=VkRk,(Rk)jj=βh21h32⋯hj,j−1>0,而從不需要構造 Kk。對 (11),K2=(01M1),R2=(101M)。Krylov 矩陣可能嚴重病態;Arnoldi 直接給出它的標準正交因子。
殘差就是一個小型最小二乘問題的殘差
x0+Kk 中每個候選值均可唯一寫成 x=x0+Vky。令 e1(k+1)=(1,0,…,0)T∈Rk+1。因為 r0=βv1,由 (3) 得
b−A(x0+Vky)=r0−AVky=Vk+1(βe1(k+1)−Hky).(4)
對任意 z∈Rk+1,標準正交性給出 ∥Vk+1z∥22=zTVk+1TVk+1z=∥z∥22。所以 (4) 證明了精確等式
∥b−A(x0+Vky)∥2=∥βe1(k+1)−Hky∥2.(5)
定理 1.3.3
(精確算術下不重啟的 GMRES)
設 A 非奇異、r0=0,且 Arnoldi 直到第 k 步都沒有中斷。唯一的最小二乘極小值點
yk=y∈Rkargmin∥βe1(k+1)−Hky∥2(6)定義 xk=x0+Vkyk;它是 x0+Kk 中使 ∥b−Ax∥2 最小的唯一向量。其殘差滿足
(AVk)Trk=0,rk=b−Axk.(7)
Hk 具有滿列秩。若 Hky=0,由 (3) 得 AVky=0;A 非奇異及 Vk 各列獨立遂給出 y=0。因此,最小二乘的二次目標函數嚴格凸,並有唯一極小值點:其 Hessian 矩陣為 2HkTHk,而此矩陣正定。由 (5),這個最小化問題與原來仿射空間上的殘差最小化完全等價。
把降維後的殘差範數平方對 y 微分,極小值點必須滿足
HkT(βe1(k+1)−Hkyk)=0.(8)利用 (3) 及 (4),(8) 正是 (7)。故 rk 垂直於 AKk,即修正空間經 A 映射所得的空間。一般而言,它不會垂直於 Kk 本身。修正 Axk−Ax0 正是 r0 在 AKk 上的正交投影。
證明透視
非奇異性與標準正交性在哪裏起作用
證明有三步,各用一個假設。唯一性需要 Hk 滿列秩,非奇異性正是用在這裏:Hky=0 給出 AVky=0,只有單射的 A 才能把它變成 Vky=0。從小問題轉回原問題靠恆等式 (5),其關鍵是 Vk+1TVk+1=I:任意基底 W 仍有 r=Wz,但通常 ∥Wz∥2=∥z∥2,所以單有 Hessenberg 關係並不足夠。最後,正規方程 (8) 經 (3) 拉回,給出 rk 垂直於 AKk 而非 Kk,因為殘差只經由 A 的像依賴修正量。在有限精度下,(3) 與正交性都有偏差,此時 (5) 需要擾動分析或明確重算殘差。
上述正規方程是數學推導,並不是建議實際計算時形成正規矩陣。對 Hk 作 QR 分解,並常以平面旋轉逐步更新,便可避免明確把條件數平方。本篇不推導這些實作的有限精度誤差界。
共軛梯度法的 Galerkin 條件使殘差垂直於 Kk;GMRES 施加的卻是 rk⊥AKk。在下面 M=2 的例子中,r1=(−2/5,4/5)T 滿足 (Av1)Tr1=(2,1)⋅r1=0,但 v1Tr1=4/5=0。若以 VkTrk=0 檢驗 GMRES 程式,會把正確的實作誤判為錯誤。
因為 Kk⊆Kk+1,不重啟的殘差最小值隨 k 增加不會上升,但未必嚴格下降。這個結論只是比較嵌套空間上的最小值,並沒有給出定量的收斂速度。
Arnoldi 次對角線為零代表甚麼?
定理 1.3.4
(在不變 Krylov 空間成功終止)
設 A 非奇異且 r0=0。若第一個為零的次對角線係數是 hq+1,q=0,則 GMRES 迭代 xq 精確解出 Ax=b。這樣的 q≤n 必定存在,所以在精確算術下,完整不重啟的 GMRES 至多 n 步終止。
假設第一個零係數是 hq+1,q=0,而此前已建立 q 個獨立基底向量。(2) 對 j=q 仍成立,只是不再產生新向量,於是
AVq=VqHq,Hq∈Rq×q.(9)故 AKq⊆Kq:修正空間已是不變子空間。因為 A 非奇異,它在這個有限維空間上的限制映射是單射,從而也是滿射。等價地,Hq 非奇異:Hqy=0 會推出 AVqy=0,再推出 y=0。求解 Hqy=βe1(q),便有
b−A(x0+Vqy)=Vq(βe1(q)−Hqy)=0.(10)此時殘差範數為零,已是最小可能值,故 x0+Vqy 正是第 q 步的 GMRES 極小值點;A 非奇異保證它唯一。這是成功終止,有時稱為「幸運中斷」。最遲在建立 n 個獨立向量後,已不可能再出現正交的新方向,故下一個 Arnoldi 次對角線係數必為零,而 (10) 適用。
這是非奇異方程組在精確算術下、完整而不重啟的 GMRES 的有限步終止定理。它既不提供大型問題的實用迭代次數,也不保證浮點運算中的同樣結果。若矩陣奇異,不變空間未必包含解;其中一題練習會展示這一點。
令 A=(2013)、b=e1、x0=0。則 v1=e1、Av1=(2,0)T,所以 h11=2,餘量 w=(2,0)T−2e1 為零:h21=0、q=1。此時 H1=(2),降維方程 2y=1 給出 y=1/2,而 x1=(1/2,0)T 滿足 Ax1=e1=b。第一步中斷恰好在 r0 是 A 的特徵向量時發生;非奇異性保證其特徵值非零,所以除法合法。
一個完整的非正規例子
例題 1.3.6
(兩個特徵值都是一,第一步殘差卻改善甚少)
令 M>0、x0=0,以及
A=(10M1),b=(01).(11)此時 β=1、v1=(0,1)T。第一次 Arnoldi 步驟給出
Av1=(M1),h11=1,h21=M,v2=(10),H1=(1M).降維目標函數是 (1−y)2+M2y2。導數在 y1=1/(1+M2) 處為零,因此
x1=1+M21(01),r1=1+M21(−MM2),∥r1∥2=1+M2M.(12)正交條件可以直接看出:(M,1)r1=0,但 v1Tr1=M2/(1+M2)=0。當 M=2,x1=(0,1/5)T、r1=(−2/5,4/5)T,殘差範數是 2/5。當 M 增大,比例 ∥r1∥2/∥r0∥2 趨近一。
第二步有 Av2=(1,0)T。減去沿 v1 的分量時沒有改變;再減去沿 v2 的分量後則得到零。因此 h12=0、h22=1、h32=0,而
H2=(1M01),H2(1−M)=(10).最後的修正是 x2=v1−Mv2=(−M,1)T;直接相乘可驗證 Ax2=b。第一步可以幾乎沒有進展,但第二個精確步驟就已求得解。
令 A 為循環置換:Ae1=e2、Ae2=e3、Ae3=e1,並取 b=e1、x0=0。Arnoldi 給出 v1=e1、v2=e2、v3=e3,其中 h21=h32=1、h13=1,其餘算出的元素(包括 h43)皆為零。第一步的降維目標是 1+y2,第二步是 1+y12+y22,所以 x1=x2=0,∥r1∥2=∥r2∥2=1。第三步 H3y=e1 迫使 y=(0,0,1)T,故 x3=e3 且 Ax3=e1=b。這個 A 是正交矩陣,因而正規,特徵值是三個立方單位根 ωj。對次數至多二的 p,有 31j=0∑2p(ωj)=p(0),所以 p(0)=1 迫使 jmax∣p(ωj)∣≥1:取 κ2(X)=1 的界 (14) 預測第三步之前毫無進展。停滯並非只屬於非正規矩陣。
計算時必須留意 Arnoldi 基底的次序。原矩陣在座標次序 e1,e2 下是上三角形;H2 卻是在 v1=e2,v2=e1 的次序下表示。同一算子換了基底,不能不管次序而直接抄寫原矩陣的元素。
殘差多項式與特徵值圖像的限制
這裏所有多項式最小化都限制在實係數多項式中。Kk 中任意修正都可寫成 s(A)r0,其中實多項式 s 的次數不超過 k−1。相應殘差為
r0−As(A)r0=p(A)r0,p(z)=1−zs(z).
反過來,每個次數不超過 k 且 p(0)=1 的多項式 p 都有這種形式,因為 1−p(z) 可被 z 整除。因此
∥rk∥2=degp≤kp(0)=1min∥p(A)r0∥2.(13)
若 A=XΛX−1 可對角化,容許 X 與 Λ 為複矩陣並對它們採用複數歐幾里得範數,則
∥r0∥2∥rk∥2≤κ2(X)degp≤kp(0)=1minimax∣p(λi)∣,κ2(X)=∥X∥2∥X−1∥2.(14)
理由是 p(A)=Xp(Λ)X−1,且對角矩陣 p(Λ) 的範數等於 imax∣p(λi)∣。先對每個容許的 p 使用範數界,再取最小值即可。前面的因子取決於所選的特徵向量矩陣。正規矩陣可選用標準正交的複特徵基底,使此因子為一;必要時採用複數歐幾里得範數。一般非正規矩陣的因子卻可能很大,甚至矩陣根本不可對角化。使用 (14) 時,不能省略它的假設或這個因子。
反例模式
在每個特徵值處為零,未必使矩陣多項式為零
矩陣 (11) 唯一的特徵值是 1,重數為二。然而對 p(z)=1−z,
p(A)=I−A=(00−M0)=0,p(A)b=(−M0).故純量條件 p(1)=0 並不推出零殘差。當 M>0,此矩陣不可對角化,而且非正規:AAT 與 ATA 的第一個對角元素分別為 1+M2 與 1。它的非零冪零部分 N=A−I 滿足 N2=0,因此 (1−z)2 確實使 A 的矩陣多項式為零。這與兩步求解相符,而 (12) 則量化了第一步進展不足的程度。正確做法是在明確結構假設下分析 p(A),不能單憑特徵值推斷一般 GMRES 的收斂率。
儲存、重啟,以及殘差能證明甚麼
進行 k 個不重啟步驟後,Arnoldi 保留 k+1 個長度為 n 的向量。下一步需要一次矩陣向量乘積,以及對所有保留向量作正交化。成本隨步數增加,促使我們考慮重啟 GMRES:先進行固定數目的步驟,保留所得近似,再以其殘差重新建立 Krylov 空間。每個精確週期都把起始近似包含在候選集合中,所以跨週期的殘差範數仍不會增加。不過,之前完整空間的有限步終止證明已不適用,因為重啟丟棄了方向。它甚至可能重複同一條毫無進展的一維搜尋,正如下面旋轉矩陣的練習所示。
預處理也會改變正在最小化的問題。若固定的右預處理矩陣 P 可逆,寫成 x=x0+P−1z,求解 AP−1z=r0;GMRES 在生成的修正空間中最小化真正的殘差 r0−AP−1z。若改用左預處理,求解 P−1Ax=P−1b,所最小化的範數便是 ∥P−1(b−Ax)∥2;它對近似值好壞的排序未必與 ∥b−Ax∥2 相同。這些是精確代數上的差異,並不表示任一預處理矩陣必然有效。
最後,前向誤差滿足 x∗−xk=A−1rk,所以 ∥x∗−xk∥2≤∥A−1∥2∥rk∥2。殘差必須配合適當的逆矩陣範數或條件數數據,才可證明誤差達到目標。
對 A=diag(1,10−6) 及 b=(0,10−6)T,解為 x∗=(0,1)T。近似 x=0 的殘差範數是 10−6,誤差範數卻是 1;因子 ∥A−1∥2=106 正是殘差看不見的部分。
應監察與原模型相應的殘差,並配合數據及離散化誤差設定容許值。殘差最小化不會消除這些考慮。
練習
練習 1.3.8
(在 (11) 取 M=1。計算第一次降維問題的極小值點、殘差,以及 r1Tv1 與 r1TAv1。直接驗證第二次迭代。)
基礎
解答(3)
1最小化降維目標
目標函數為 (1−y)2+y2,在 y=1/2 取得最小值。因此 x1=(0,1/2)T、r1=(−1/2,1/2)T。
2計算兩個內積
r1Tv1=1/2,而 r1TAv1=(−1/2,1/2)(1,1)T=0。
3驗證第二次迭代
第二次迭代為 x2=(−1,1)T,相乘得 Ax2=(0,1)T=b。
練習 1.3.9
(假設 Arnoldi 尚未中斷。證明 rk=0 會迫使 hk+1,k=0,與沒有中斷矛盾。此推論不需要非奇異假設。說明它為甚麼與 A 非奇異時的成功終止相容。)
核心證明
解答(4)
1把零殘差轉為降維方程組
rk=0 推出 Hkyk=βe1(k+1)。
依據: 恆等式 (4) 及 Vk+1 的標準正交性。
2由最後一行向上回代
關鍵一步
最後一行為 hk+1,k(yk)k=0,故 (yk)k=0。上一行繼而給出 hk,k−1(yk)k−1=0。逐行向上得到所有分量為零。當 k=1,最後一行直接給出 y1=0。
依據: 每個次對角線元素 hi+1,i 均為正。
3在第一行得出矛盾
第一行變成 0=β,與 β>0 矛盾。過程中沒有用到非奇異性。
4與成功終止相容
所以當這些次對角線元素均為正時,不可能已求得精確解。對非奇異的 A,精確解出現在不變空間的終止步,此時以 (9) 取代沒有中斷時的長方形方程組。
∎
練習 1.3.10
(設 A=(01−10)、b=(1,0)T、x0=0。計算一步 GMRES 的極小值點,說明每一步後都重啟的 GMRES 為甚麼停滯。再建立不重啟的兩步解。)
核心
解答(3)
1執行一步 Arnoldi
v1=e1、Av1=e2、h11=0、h21=1。降維目標是 1+y2,所以 y=0、x1=0、r1=e1。
2解釋重啟為何停滯
關鍵一步
一步重啟後的近似與殘差完全相同,故每個週期都重複這次計算。
3不重啟繼續
v2=e2、Av2=−e1,給出 H2=(01−10)。解 H2y=e1 得 y=(0,−1)T,故 x2=−e2 且 Ax2=e1。
練習 1.3.11
(去掉非奇異假設:設 A=diag(1,0)、b=(0,1)T、x0=0。執行第一次 Arnoldi 步驟。中斷是否代表已求得解?指出成功終止證明中哪個推論失效。)
核心
解答(3)
1執行第一次 Arnoldi 步驟
v1=e2、Av1=0,故 h11=h21=0。不變空間是 span{e2},但 A 把它全部映至零。
2檢驗降維方程與原方程
降維方程為 0⋅y=1,不相容。原方程也不相容,因為第二行要求 0=1。
3找出失效的推論
失效的是「限制映射為單射,從而為滿射」這一步:A 奇異,而此處的限制映射不是單射。每個 y 都是最小二乘極小值點,殘差一律為 e2;因此唯一性也失效,而且沒有極小值點能產生零殘差。
練習 1.3.12
(對 (11),把 x1 表示為 s(A)b,並寫出其殘差多項式 p1。給出一個常數項為一、可產生零殘差的二次多項式。說明為甚麼 p(z)=1−z 是容許的一次選擇,卻一般不是極小值點。)
綜合
解答(3)
1讀出一步的多項式
s(z)=1/(1+M2)、p1(z)=1−z/(1+M2) 正好給出 (12)。
2零化矩陣
多項式 p2(z)=(1−z)2 滿足 p2(A)=0。
3與在特徵值處為零的選擇比較
選擇 1−z 等於取 x=b,其殘差是 (−M,0)T、範數為 M;對每個 M>0,此值都大於 M/1+M2。所以在唯一特徵值處為零,仍可比真正使殘差最小的一次多項式更差。
本篇推導的範圍
我們證明了非奇異有限維方程組在精確算術下的基底構造、殘差最小化及不變子空間終止。實際的正交性損失、重新正交化準則、穩定的旋轉更新、可變預處理、區塊方法及大型稀疏矩陣方程求解器仍待進一步討論。