为什么保留整个 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。所以在唯一特征值处为零,仍可能比真正使残差最小的一次多项式更差。
本篇推导的范围
我们证明了非奇异有限维方程组在精确算术下的基构造、残差最小化及不变子空间终止。实际的正交性损失、重新正交化准则、稳定的旋转更新、可变预处理、块方法及大型稀疏矩阵方程求解器仍待进一步讨论。