动机
许多计算问题不能一步解决。非线性模型被替换成一连串线性模型;每个大型线性方程组又可能要以迭代方法求解。分开考察两层,才能问清楚:非线性近似在什么情况下准确?每次线性方程应解到多精确?残差小是否意味误差小?本节讨论牛顿(Newton)法、对称正定系统,并把同样想法推广至未知量本身为矩阵的方程。
前面的一元牛顿法与定常迭代是有用的准备。局部误差估计漂亮,并不代表方法从任何起点都收敛;初值、Jacobian 的条件及线性求解成本都重要。
定义
设可微函数 F : R n → R n F:\mathbb R^n\to\mathbb R^n F : R n → R n 。在 x k x_k x k ,若 J k = F ′ ( x k ) J_k=F'(x_k) J k = F ′ ( x k ) 非奇异,牛顿步满足
J k s k = − F ( x k ) , x k + 1 = x k + s k . J_k s_k=-F(x_k),\qquad x_{k+1}=x_k+s_k. J k s k = − F ( x k ) , x k + 1 = x k + s k . 对线性系统 A x = b Ax=b A x = b 的近似 x k x_k x k ,残差为 r k = b − A x k r_k=b-Ax_k r k = b − A x k 。若 x ∗ x_* x ∗ 是精确解,误差 e k = x ∗ − x k e_k=x_*-x_k e k = x ∗ − x k 满足 A e k = r k Ae_k=r_k A e k = r k 。
牛顿方程令一阶模型 F ( x k ) + J k s F(x_k)+J_ks F ( x k ) + J k s 为零;它是一个待解的线性系统,并不要求显式构造 J k − 1 J_k^{-1} J k − 1 。若 J k J_k J k 奇异,步长可能不存在或不唯一。线性残差小只有配合 A − 1 A^{-1} A − 1 的信息及所用范数,才能控制误差。
令 r 0 = b − A x 0 r_0=b-Ax_0 r 0 = b − A x 0 ,第 k k k 个 Krylov 空间为 K k ( A , r 0 ) = span { r 0 , A r 0 , … , A k − 1 r 0 } \mathcal K_k(A,r_0)=\operatorname{span}\{r_0,Ar_0,\ldots,A^{k-1}r_0\} K k ( A , r 0 ) = span { r 0 , A r 0 , … , A k − 1 r 0 } 。其中向量可由矩阵与向量相乘产生,无须存储稠密逆矩阵。空间若不再增长,便达到不变子空间;实现时须依具体算法处理这种中断(breakdown)。
主要结果
假设 F F F 在零点 x ∗ x_* x ∗ 附近连续可微,J ∗ = F ′ ( x ∗ ) J_*=F'(x_*) J ∗ = F ′ ( x ∗ ) 可逆,且该处 F ′ F' F ′ 满足 Lipschitz 条件 ∥ F ′ ( x ) − F ′ ( y ) ∥ ≤ L ∥ x − y ∥ \|F'(x)-F'(y)\|\le L\|x-y\| ∥ F ′ ( x ) − F ′ ( y ) ∥ ≤ L ∥ x − y ∥ 。若 x 0 x_0 x 0 充分接近 x ∗ x_* x ∗ ,所有牛顿步均有定义,并且
∥ x k + 1 − x ∗ ∥ ≤ C ∥ x k − x ∗ ∥ 2 \|x_{k+1}-x_*\|\le C\|x_k-x_*\|^2 ∥ x k + 1 − x ∗ ∥ ≤ C ∥ x k − x ∗ ∥ 2 其中常数 C C C 与 k k k 无关。
因 F ′ F' F ′ 连续且 J ∗ J_* J ∗ 可逆,存在 x ∗ x_* x ∗ 的一个球,使其中的 J ( x ) J(x) J ( x ) 均可逆且 ∥ J ( x ) − 1 ∥ ≤ M \|J(x)^{-1}\|\le M ∥ J ( x ) − 1 ∥ ≤ M 。例如,当 J ∗ − 1 ( J ( x ) − J ∗ ) J_*^{-1}(J(x)-J_*) J ∗ − 1 ( J ( x ) − J ∗ ) 的范数小于一时,可由 Neumann 级数得到此结论。令 ε = x − x ∗ \varepsilon=x-x_* ε = x − x ∗ ;一阶展开的积分形式给出
F ( x ) − F ( x ∗ ) − J ( x ) ε = ∫ 0 1 [ J ( x ∗ + t ε ) − J ( x ) ] ε d t . F(x)-F(x_*)-J(x)\varepsilon=\int_0^1[J(x_*+t\varepsilon)-J(x)]\varepsilon\,dt. F ( x ) − F ( x ∗ ) − J ( x ) ε = ∫ 0 1 [ J ( x ∗ + tε ) − J ( x )] ε d t . Lipschitz 条件把右边范数限制在 L ∥ ε ∥ 2 / 2 L\|\varepsilon\|^2/2 L ∥ ε ∥ 2 /2 以内。由 F ( x ∗ ) = 0 F(x_*)=0 F ( x ∗ ) = 0 ,下一次误差为 ε + = J ( x ) − 1 [ J ( x ) ε − F ( x ) ] \varepsilon_+=J(x)^{-1}[J(x)\varepsilon-F(x)] ε + = J ( x ) − 1 [ J ( x ) ε − F ( x )] ,因此 ∥ ε + ∥ ≤ M L ∥ ε ∥ 2 / 2 \|\varepsilon_+\|\le ML\|\varepsilon\|^2/2 ∥ ε + ∥ ≤ M L ∥ ε ∥ 2 /2 。选取足够小的初始球,使此界把球映回自身,再以归纳法完成证明。定理并未给出该球的具体大小,也没有保证任意初值收敛。
证明透视
为何非线性证明需要一致的逆矩阵界 证明结合了两种不同的估计。积分恒等式纯属微积分:它把线性化缺陷 J ( x ) ε − F ( x ) J(x)\varepsilon-F(x) J ( x ) ε − F ( x ) 精确写出,而 Lipschitz 条件把它化为 L ∥ ε ∥ 2 / 2 L\|\varepsilon\|^2/2 L ∥ ε ∥ 2 /2 ,因为 J ( x ∗ + t ε ) J(x_*+t\varepsilon) J ( x ∗ + tε ) 与 J ( x ) J(x) J ( x ) 的取值点相距 ( 1 − t ) ∥ ε ∥ (1-t)\|\varepsilon\| ( 1 − t ) ∥ ε ∥ 。这个二次量随后要乘上 J ( x ) − 1 J(x)^{-1} J ( x ) − 1 ,所以第二个估计必须是当前迭代点处的界 ∥ J ( x ) − 1 ∥ ≤ M \|J(x)^{-1}\|\le M ∥ J ( x ) − 1 ∥ ≤ M ,而不是根处的界。仅凭 J ∗ J_* J ∗ 可逆,并不能在附近各点给出数值;F ′ F' F ′ 的连续性加上 Neumann 级数才在一个球上提供这个界。
使论证完成的一步,是选取该球的半径 ρ \rho ρ ,必要时把它缩小,使 M L ρ / 2 ≤ 1 2 ML\rho/2\le\tfrac12 M L ρ /2 ≤ 2 1 。于是 ∥ ε + ∥ ≤ ( M L ∥ ε ∥ / 2 ) ∥ ε ∥ ≤ 1 2 ∥ ε ∥ \|\varepsilon_+\|\le(ML\|\varepsilon\|/2)\|\varepsilon\|\le\tfrac12\|\varepsilon\| ∥ ε + ∥ ≤ ( M L ∥ ε ∥/2 ) ∥ ε ∥ ≤ 2 1 ∥ ε ∥ ,下一个迭代点仍在同一个球内,两个界都可以再次使用;定理中的常数为 C = M L / 2 C=ML/2 C = M L /2 。若 J ∗ J_* J ∗ 不可逆,界 M M M 可能不存在:对 F ( x ) = x 2 F(x)=x^2 F ( x ) = x 2 ,根是重根,牛顿迭代 x k + 1 = x k / 2 x_{k+1}=x_k/2 x k + 1 = x k /2 只线性收敛。
若 A A A 为实对称正定矩阵,精确算术下共轭梯度法的 x k x_k x k 在 x 0 + K k ( A , r 0 ) x_0+\mathcal K_k(A,r_0) x 0 + K k ( A , r 0 ) 上最小化 ∥ x ∗ − x ∥ A = ( ( x ∗ − x ) T A ( x ∗ − x ) ) 1 / 2 \|x_*-x\|_A=((x_*-x)^TA(x_*-x))^{1/2} ∥ x ∗ − x ∥ A = (( x ∗ − x ) T A ( x ∗ − x ) ) 1/2 。其残差与该 Krylov 空间正交,并且至多 n n n 步到达 x ∗ x_* x ∗ ;也可能更早终止。
对 q ( x ) = 1 2 x T A x − b T x q(x)=\tfrac12x^TAx-b^Tx q ( x ) = 2 1 x T A x − b T x ,有 q ( x ) − q ( x ∗ ) = 1 2 ∥ x − x ∗ ∥ A 2 q(x)-q(x_*)=\tfrac12\|x-x_*\|_A^2 q ( x ) − q ( x ∗ ) = 2 1 ∥ x − x ∗ ∥ A 2 。在仿射子空间上最小化时,梯度 A x − b = − r Ax-b=-r A x − b = − r 必须与子空间的所有方向正交;正定性保证最小点唯一。共轭梯度法构造互相 A A A -正交的非零搜索方向,张成逐步增大的 Krylov 空间,并沿每个方向取精确线搜索的最小点;得到的梯度与它们的张成空间正交,故为上述最小点。最多只有 n n n 个非零且互相 A A A -正交的向量。若 Krylov 空间较早停止增长,它就是 A A A 的不变空间;由 A A A 可逆,A − 1 r 0 A^{-1}r_0 A − 1 r 0 也在其中,故精确解已在仿射空间内。有限步结论依赖精确算术;舍入误差会破坏精确正交性。
更明确地,g k + 1 = g k + α k A p k g_{k+1}=g_k+\alpha_kAp_k g k + 1 = g k + α k A p k 。由 j < k j<k j < k 时 p j T A p k = 0 p_j^TAp_k=0 p j T A p k = 0 ,这次更新保留先前所有 p j T g k = 0 p_j^Tg_k=0 p j T g k = 0 的条件。新的精确直线最小化再给出 p k T g k + 1 = 0 p_k^Tg_{k+1}=0 p k T g k + 1 = 0 ,所以梯度与至今使用的每个方向正交,不只是最后一个方向。
证明透视
k 次线搜索如何合成一次 k 维极小化 恒等式 q ( x ) − q ( x ∗ ) = 1 2 ∥ x − x ∗ ∥ A 2 q(x)-q(x_*)=\tfrac12\|x-x_*\|_A^2 q ( x ) − q ( x ∗ ) = 2 1 ∥ x − x ∗ ∥ A 2 是关键:它把涉及未知 x ∗ x_* x ∗ 的误差,换成可以计算的二次函数 q q q ,而 q q q 的梯度是 − r -r − r 。正定性使 ∥ ⋅ ∥ A \|\cdot\|_A ∥ ⋅ ∥ A 成为范数,所以在仿射子空间上的极小点存在且唯一,也使每次线搜索有定义。真正的想法是 A A A 正交性。沿 p k p_k p k 走一步,梯度改变 α k A p k \alpha_kAp_k α k A p k ,而它与每个先前的 p j p_j p j 正交,因此先前的线极小化不会被破坏,k k k 次一维搜索便给出整个 k k k 维空间上的极小点。论证以计数收尾:非零且两两 A A A 正交的向量线性无关,至多有 n n n 个;若更早停止增长,就得到一个已包含 A − 1 r 0 A^{-1}r_0 A − 1 r 0 的不变子空间。
例题
令 F ( x , y ) = ( x 2 + y 2 − 5 , x − y − 1 ) T F(x,y)=(x^2+y^2-5,x-y-1)^T F ( x , y ) = ( x 2 + y 2 − 5 , x − y − 1 ) T 。在 ( 2 , 1 ) (2,1) ( 2 , 1 ) 残差为零。在 ( 1 , 1 ) (1,1) ( 1 , 1 ) ,F = ( − 3 , − 1 ) T F=(-3,-1)^T F = ( − 3 , − 1 ) T ,J = ( 2 2 1 − 1 ) J=\begin{pmatrix}2&2\\1&-1\end{pmatrix} J = ( 2 1 2 − 1 ) 。解 J s = ( 3 , 1 ) T Js=(3,1)^T J s = ( 3 , 1 ) T 得 s = ( 5 / 4 , 1 / 4 ) T s=(5/4,1/4)^T s = ( 5/4 , 1/4 ) T ,故 ( x 1 , y 1 ) = ( 9 / 4 , 5 / 4 ) (x_1,y_1)=(9/4,5/4) ( x 1 , y 1 ) = ( 9/4 , 5/4 ) 。这一步不会精确解出二次方程;它消去的是线性化残差。在 ( 2 , 1 ) (2,1) ( 2 , 1 ) 处 Jacobian 行列式为 − 6 -6 − 6 ,因此充分靠近该点时可应用局部定理。
设 A = diag ( 1 , 4 ) A=\operatorname{diag}(1,4) A = diag ( 1 , 4 ) 、b = ( 1 , 1 ) T b=(1,1)^T b = ( 1 , 1 ) T 、x 0 = 0 x_0=0 x 0 = 0 。则 r 0 = p 0 = b r_0=p_0=b r 0 = p 0 = b ,精确线搜索步长为 α 0 = ( r 0 T r 0 ) / ( p 0 T A p 0 ) = 2 / 5 \alpha_0=(r_0^Tr_0)/(p_0^TAp_0)=2/5 α 0 = ( r 0 T r 0 ) / ( p 0 T A p 0 ) = 2/5 。因此 x 1 = ( 2 / 5 , 2 / 5 ) T x_1=(2/5,2/5)^T x 1 = ( 2/5 , 2/5 ) T ,r 1 = ( 3 / 5 , − 3 / 5 ) T r_1=(3/5,-3/5)^T r 1 = ( 3/5 , − 3/5 ) T ,与 r 0 r_0 r 0 正交。精确解是 ( 1 , 1 / 4 ) T (1,1/4)^T ( 1 , 1/4 ) T ;精确算术下第二步可达精确解。第一步不一定最小化欧氏(Euclidean)误差,而是在线 x 0 + span { r 0 } x_0+\operatorname{span}\{r_0\} x 0 + span { r 0 } 上最小化 A A A -范数误差。
例题 1.2.6
(一个小型 Sylvester 方程)
求解 A X + X B = C AX+XB=C A X + X B = C ,其中 A = diag ( 1 , 2 ) A=\operatorname{diag}(1,2) A = diag ( 1 , 2 ) 、B = diag ( 3 , 4 ) B=\operatorname{diag}(3,4) B = diag ( 3 , 4 ) 、C = ( 4 5 10 12 ) C=\begin{pmatrix}4&5\\10&12\end{pmatrix} C = ( 4 10 5 12 ) 。第 ( i , j ) (i,j) ( i , j ) 项满足 ( a i + b j ) X i j = C i j (a_i+b_j)X_{ij}=C_{ij} ( a i + b j ) X ij = C ij ,故 X = ( 1 1 2 2 ) X=\begin{pmatrix}1&1\\2&2\end{pmatrix} X = ( 1 2 1 2 ) 。这种逐项分离依赖两个矩阵在所选基底中均已对角化。若 a i + b j = 0 a_i+b_j=0 a i + b j = 0 ,相应方程可能不相容或不能确定该项;唯一解并非自动存在。
方法与推理
阻尼与不精确步
离根太远时,完整牛顿步可能失败。阻尼步以 λ k s k \lambda_k s_k λ k s k 代替 s k s_k s k ,其中 0 < λ k ≤ 1 0<\lambda_k\le1 0 < λ k ≤ 1 ;线搜索可利用 1 2 ∥ F ( x ) ∥ 2 \frac12\|F(x)\|^2 2 1 ∥ F ( x ) ∥ 2 等优值函数选择 λ k \lambda_k λ k 。要证明收敛仍须给出接受规则及假设,阻尼并非万能保证。
大型系统通常只作近似求解。令线性求解残差 d k = J k s k + F ( x k ) d_k=J_ks_k+F(x_k) d k = J k s k + F ( x k ) ,记 e k = x ∗ − x k e_k=x_*-x_k e k = x ∗ − x k ,则更新给出 e k + 1 = e k − s k e_{k+1}=e_k-s_k e k + 1 = e k − s k ,因此
e k + 1 = J k − 1 ( J k e k + F ( x k ) − d k ) . e_{k+1}=J_k^{-1}\bigl(J_ke_k+F(x_k)-d_k\bigr). e k + 1 = J k − 1 ( J k e k + F ( x k ) − d k ) .
在前述局部假设下,若 ∥ d k ∥ ≤ η k ∥ F ( x k ) ∥ \|d_k\|\le\eta_k\|F(x_k)\| ∥ d k ∥ ≤ η k ∥ F ( x k ) ∥ ,除二次项外,还有与 η k ∥ e k ∥ \eta_k\|e_k\| η k ∥ e k ∥ 成比例的线性误差项。固定非零的容许比例一般只保证线性局部收敛;在适当的界下令 η k → 0 \eta_k\to0 η k → 0 可恢复超线性收敛。若局部要求 ∥ d k ∥ = O ( ∥ e k ∥ 2 ) \|d_k\|=O(\|e_k\|^2) ∥ d k ∥ = O ( ∥ e k ∥ 2 ) ,便足以维持二次收敛;由局部 Jacobian 界,这等价于要求 O ( ∥ F ( x k ) ∥ 2 ) O(\|F(x_k)\|^2) O ( ∥ F ( x k ) ∥ 2 ) 。早期线性系统解得远比非线性模型所需精确,可能浪费计算量。
预处理与停止准则
对对称正定 A A A ,选择容易求解的对称正定预处理矩阵 M M M 。转换后系统为
M − 1 / 2 A M − 1 / 2 y = M − 1 / 2 b , x = M − 1 / 2 y . M^{-1/2}AM^{-1/2}y=M^{-1/2}b,\qquad x=M^{-1/2}y. M − 1/2 A M − 1/2 y = M − 1/2 b , x = M − 1/2 y .
它仍为对称正定;实际预处理共轭梯度法使用 M − 1 M^{-1} M − 1 ,无须显式计算平方根。有用的 M M M 使转换后特征值更集中,但构造及应用它也有成本。不能假设 M − 1 A M^{-1}A M − 1 A 在欧氏内积下对称,然后直接套用普通共轭梯度法:即使 M , A M,A M , A 均对称正定,乘积也未必对称。
若 A A A 的特征值位于 [ λ min , λ max ] [\lambda_{\min},\lambda_{\max}] [ λ m i n , λ m a x ] ,则 ∥ e k ∥ 2 ≤ ∥ r k ∥ 2 / λ min \|e_k\|_2\le\|r_k\|_2/\lambda_{\min} ∥ e k ∥ 2 ≤ ∥ r k ∥ 2 / λ m i n ,且 ∥ e k ∥ A 2 = r k T A − 1 r k \|e_k\|_A^2=r_k^TA^{-1}r_k ∥ e k ∥ A 2 = r k T A − 1 r k 。这说明已知谱信息时残差能证明什么。取 A = diag ( 1 , 10 − 8 ) A=\operatorname{diag}(1,10^{-8}) A = diag ( 1 , 1 0 − 8 ) 、r = ( 0 , 10 − 8 ) T r=(0,10^{-8})^T r = ( 0 , 1 0 − 8 ) T ,残差范数是 10 − 8 10^{-8} 1 0 − 8 ,误差却是 ( 0 , 1 ) T (0,1)^T ( 0 , 1 ) T 。解读相对残差要考虑条件数、数据尺度及目标精度;停止准则亦不应盲目要求远超离散化或测量误差的精度。
矩阵方程与向量化
按列向量化有 vec ( A X B ) = ( B T ⊗ A ) vec ( X ) \operatorname{vec}(AXB)=(B^T\otimes A)\operatorname{vec}(X) vec ( A X B ) = ( B T ⊗ A ) vec ( X ) 。所以 A X + X B = C AX+XB=C A X + X B = C 等价于
( I ⊗ A + B T ⊗ I ) vec ( X ) = vec ( C ) . (I\otimes A+B^T\otimes I)\operatorname{vec}(X)=\operatorname{vec}(C). ( I ⊗ A + B T ⊗ I ) vec ( X ) = vec ( C ) .
检查单个矩阵元素,或把 X X X 按矩阵单位基展开,便可证明该恒等式。它把可解性问题化为关于一个大矩阵的问题。
定理 1.2.7
(Sylvester 方程的唯一可解性)
设 A ∈ C m × m A\in\mathbb C^{m\times m} A ∈ C m × m 、B ∈ C n × n B\in\mathbb C^{n\times n} B ∈ C n × n 。方程 A X + X B = C AX+XB=C A X + X B = C 对每个 C C C 都有唯一解 X ∈ C m × n X\in\mathbb C^{m\times n} X ∈ C m × n ,当且仅当对 A A A 的每个特征值 λ \lambda λ 与 B B B 的每个特征值 μ \mu μ 都有 λ + μ ≠ 0 \lambda+\mu\ne0 λ + μ = 0 。
证明
(把 Kronecker 和的两个因子三角化)
由向量化恒等式,方程就是线性方程组 K vec ( X ) = vec ( C ) K\operatorname{vec}(X)=\operatorname{vec}(C) K vec ( X ) = vec ( C ) ,其中 K = I n ⊗ A + B T ⊗ I m K=I_n\otimes A+B^T\otimes I_m K = I n ⊗ A + B T ⊗ I m ;因此“对每个 C C C 唯一可解”等价于 K K K 非奇异。取 Schur 形式 A = U T A U ∗ A=UT_AU^* A = U T A U ∗ 、B T = V T B V ∗ B^T=VT_BV^* B T = V T B V ∗ ,其中 U , V U,V U , V 为酉矩阵,T A , T B T_A,T_B T A , T B 为上三角矩阵;T B T_B T B 的对角线列出 B T B^T B T 的特征值,也就是 B B B 的特征值。令 W = V ⊗ U W=V\otimes U W = V ⊗ U ,由混合积法则得
K = W ( I n ⊗ T A + T B ⊗ I m ) W ∗ . K=W\bigl(I_n\otimes T_A+T_B\otimes I_m\bigr)W^*. K = W ( I n ⊗ T A + T B ⊗ I m ) W ∗ . 括号内两个 Kronecker 积都是上三角矩阵,与 ( i , j ) (i,j) ( i , j ) 对应的对角元为 λ i ( A ) + λ j ( B ) \lambda_i(A)+\lambda_j(B) λ i ( A ) + λ j ( B ) 。三角矩阵非奇异,当且仅当所有对角元都非零。
反例模式
系数矩阵可逆并不保证 Sylvester 方程可解 人们容易以为只要 A A A 与 B B B 都可逆,A X + X B = C AX+XB=C A X + X B = C 就有唯一解。取 A = diag ( 1 , 2 ) A=\operatorname{diag}(1,2) A = diag ( 1 , 2 ) 、B = diag ( − 1 , 3 ) B=\operatorname{diag}(-1,3) B = diag ( − 1 , 3 ) ,两者都可逆。逐元素方程为 ( a i + b j ) X i j = C i j (a_i+b_j)X_{ij}=C_{ij} ( a i + b j ) X ij = C ij ,而 a 1 + b 1 = 1 − 1 = 0 a_1+b_1=1-1=0 a 1 + b 1 = 1 − 1 = 0 。若 C C C 是全一矩阵,( 1 , 1 ) (1,1) ( 1 , 1 ) 元方程变成 0 ⋅ X 11 = 1 0\cdot X_{11}=1 0 ⋅ X 11 = 1 ,无解。若 C = ( 0 1 1 1 ) C=\begin{pmatrix}0&1\\1&1\end{pmatrix} C = ( 0 1 1 1 ) ,其余各元为 X 12 = 1 / 4 X_{12}=1/4 X 12 = 1/4 、X 21 = 1 X_{21}=1 X 21 = 1 、X 22 = 1 / 5 X_{22}=1/5 X 22 = 1/5 ,而 X 11 X_{11} X 11 可任意取值,所以有解但不唯一。正确的假设是定理中的特征值和条件,它同时涉及 A A A 与 B B B 。
通常不必显式构造大型 Kronecker 矩阵:迭代法可直接作用 X ↦ A X + X B X\mapsto AX+XB X ↦ A X + X B ,保留矩阵结构。非对称矩阵方程需要 GMRES 等合适方法,不能直接假定上述正定定理适用。
共轭梯度递推及其假设
由 x 0 x_0 x 0 、r 0 = b − A x 0 r_0=b-Ax_0 r 0 = b − A x 0 、p 0 = r 0 p_0=r_0 p 0 = r 0 开始。当 r k ≠ 0 r_k\ne0 r k = 0 ,精确算术下递推为
α k = r k T r k p k T A p k , x k + 1 = x k + α k p k , r k + 1 = r k − α k A p k . \alpha_k=\frac{r_k^Tr_k}{p_k^TAp_k},\quad x_{k+1}=x_k+\alpha_kp_k,\quad r_{k+1}=r_k-\alpha_kAp_k. α k = p k T A p k r k T r k , x k + 1 = x k + α k p k , r k + 1 = r k − α k A p k .
若新残差非零,取 β k = ( r k + 1 T r k + 1 ) / ( r k T r k ) \beta_k=(r_{k+1}^Tr_{k+1})/(r_k^Tr_k) β k = ( r k + 1 T r k + 1 ) / ( r k T r k ) ,再令 p k + 1 = r k + 1 + β k p k p_{k+1}=r_{k+1}+\beta_kp_k p k + 1 = r k + 1 + β k p k 。当 p k ≠ 0 p_k\ne0 p k = 0 ,正定性保证 p k T A p k > 0 p_k^TAp_k>0 p k T A p k > 0 。若 r k = 0 r_k=0 r k = 0 就停止:已找到精确解,无须计算下一个商。此递推在精确算术下无须存储所有旧基向量便能达到最小化定理。浮点运算中,递推更新的残差可能偏离直接计算的 b − A x k b-Ax_k b − A x k ;看似收敛时重新计算后者,是有用的诊断。
一个小例子可说明预处理的目的。对 A = diag ( 1 , 100 ) A=\operatorname{diag}(1,100) A = diag ( 1 , 100 ) ,取 M = A M=A M = A 使转换矩阵为单位矩阵,因此精确算术下一步共轭梯度已足够。然而只有 M − 1 M^{-1} M − 1 容易作用时,这个理想预处理才实用;对一般系统,选取整个原矩阵并未减少求解难度。实用预处理要平衡谱改善、内存及应用成本。
概念视角 代数
共轭梯度作为最佳多项式 由于 x k − x 0 x_k-x_0 x k − x 0 属于 K k ( A , r 0 ) \mathcal K_k(A,r_0) K k ( A , r 0 ) 而 r 0 = A e 0 r_0=Ae_0 r 0 = A e 0 ,误差可写成 e k = p ( A ) e 0 e_k=p(A)e_0 e k = p ( A ) e 0 ,其中 p p p 是次数至多为 k k k 、满足 p ( 0 ) = 1 p(0)=1 p ( 0 ) = 1 的多项式。因此极小化定理说
∥ e k ∥ A = min deg p ≤ k , p ( 0 ) = 1 ∥ p ( A ) e 0 ∥ A . \|e_k\|_A=\min_{\deg p\le k,\ p(0)=1}\|p(A)e_0\|_A. ∥ e k ∥ A = d e g p ≤ k , p ( 0 ) = 1 min ∥ p ( A ) e 0 ∥ A . 若 A A A 有 d d d 个不同的特征值(全为正),多项式 ∏ i ( 1 − λ / λ i ) \prod\limits_i(1-\lambda/\lambda_i) i ∏ ( 1 − λ / λ i ) 在谱上为零,所以精确共轭梯度至多 d d d 步便终止。取 M = A M=A M = A 时变换矩阵是 I I I ,d = 1 d=1 d = 1 。
非对称系统的另一选择
对一般非对称矩阵,GMRES 在相同的仿射 Krylov 空间中寻找迭代点,却最小化欧氏残差范数,而不是共轭梯度使用的能量范数。常见 Arnoldi 构造把新的矩阵向量乘积与现有基底正交化,因此不重启时存储量与计算量随步数增加。重启可限制存储,却可能减慢收敛或导致停滞。残差最小化本身不能克服病态条件:前述 e = A − 1 r e=A^{-1}r e = A − 1 r 仍控制残差与前向误差的关系。离散化或预处理后产生非对称算子时,这区别尤其重要。
常见误解
残差是方程缺陷,本身不是前向误差估计;把两者联系起来的是关系式 A e = r Ae=r A e = r 。以下三个错误则是本节方法特有的。
牛顿法的二次速率描述的是已经充分接近正则根的迭代点。它不保证根存在,不保证任意初值收敛,也不保证定理中的球很大。共轭梯度法有限步终止同样只是精确算术及对称正定矩阵下的结论。
即使 M M M 与 A A A 都对称正定,M − 1 A M^{-1}A M − 1 A 一般也不对称:取 M = diag ( 1 , 2 ) M=\operatorname{diag}(1,2) M = diag ( 1 , 2 ) 、A = ( 2 1 1 2 ) A=\begin{pmatrix}2&1\\1&2\end{pmatrix} A = ( 2 1 1 2 ) ,则 M − 1 A = ( 2 1 1 / 2 1 ) M^{-1}A=\begin{pmatrix}2&1\\1/2&1\end{pmatrix} M − 1 A = ( 2 1/2 1 1 ) 。对它套用普通共轭梯度法并没有最小化定理。预处理共轭梯度法改为处理对称正定矩阵 M − 1 / 2 A M − 1 / 2 M^{-1/2}AM^{-1/2} M − 1/2 A M − 1/2 ,等价于使用内积 ⟨ u , v ⟩ M = v T M u \langle u,v\rangle_M=v^TMu ⟨ u , v ⟩ M = v T M u (M − 1 A M^{-1}A M − 1 A 在此内积下自伴),并且只需作用 M − 1 M^{-1} M − 1 。
把 A X + X B = C AX+XB=C A X + X B = C 左乘 A − 1 A^{-1} A − 1 ,得到 X + A − 1 X B = A − 1 C X+A^{-1}XB=A^{-1}C X + A − 1 X B = A − 1 C ,其中 X X X 仍夹在双侧乘积之内;除非利用额外结构,单侧相乘不能把 X X X 分离出来。方程必须看作关于 X X X 全部元素的线性方程组,通过向量化或结构化求解器来处理。
快速检查
快速检查
(设 M M M 与 A A A 对称正定。为什么 M − 1 A M^{-1}A M − 1 A 即使不对称,仍有正实特征值?)
解答 · 答案 M − 1 A = M − 1 / 2 ( M − 1 / 2 A M − 1 / 2 ) M 1 / 2 M^{-1}A=M^{-1/2}\bigl(M^{-1/2}AM^{-1/2}\bigr)M^{1/2} M − 1 A = M − 1/2 ( M − 1/2 A M − 1/2 ) M 1/2 ,所以 M − 1 A M^{-1}A M − 1 A 与对称正定矩阵 M − 1 / 2 A M − 1 / 2 M^{-1/2}AM^{-1/2} M − 1/2 A M − 1/2 相似,特征值相同,都是正实数。相似性并不使 M − 1 A M^{-1}A M − 1 A 的欧氏特征向量互相正交。
习题
练习 1.2.8
(对 F ( x , y ) = ( x 2 + y 2 − 5 , x − y − 1 ) T F(x,y)=(x^2+y^2-5,x-y-1)^T F ( x , y ) = ( x 2 + y 2 − 5 , x − y − 1 ) T ,求 ( 1 , 1 ) (1,1) ( 1 , 1 ) 处的牛顿步,并验证其线性化残差为零。)
解答 · 答案 在 ( 1 , 1 ) (1,1) ( 1 , 1 ) ,F = ( − 3 , − 1 ) T F=(-3,-1)^T F = ( − 3 , − 1 ) T ,Jacobian 为 ( 2 2 1 − 1 ) \begin{pmatrix}2&2\\1&-1\end{pmatrix} ( 2 1 2 − 1 ) 。步长满足 2 s 1 + 2 s 2 = 3 2s_1+2s_2=3 2 s 1 + 2 s 2 = 3 、s 1 − s 2 = 1 s_1-s_2=1 s 1 − s 2 = 1 ,得 s = ( 5 / 4 , 1 / 4 ) T s=(5/4,1/4)^T s = ( 5/4 , 1/4 ) T 。代回得 F + J s = ( − 3 + 5 2 + 1 2 , − 1 + 5 4 − 1 4 ) T = ( 0 , 0 ) T F+Js=(-3+\tfrac52+\tfrac12,\,-1+\tfrac54-\tfrac14)^T=(0,0)^T F + J s = ( − 3 + 2 5 + 2 1 , − 1 + 4 5 − 4 1 ) T = ( 0 , 0 ) T 。
练习 1.2.9
(对 A = diag ( 1 , 4 ) A=\operatorname{diag}(1,4) A = diag ( 1 , 4 ) 、b = ( 1 , 1 ) T b=(1,1)^T b = ( 1 , 1 ) T 、x 0 = 0 x_0=0 x 0 = 0 ,验证例题中第一次共轭梯度残差与 r 0 r_0 r 0 正交,并求其欧氏范数。)
解答 · 答案 r 1 = ( 3 / 5 , − 3 / 5 ) T r_1=(3/5,-3/5)^T r 1 = ( 3/5 , − 3/5 ) T ,所以 r 1 T r 0 = 3 / 5 − 3 / 5 = 0 r_1^Tr_0=3/5-3/5=0 r 1 T r 0 = 3/5 − 3/5 = 0 ,且 ∥ r 1 ∥ 2 = 18 / 25 = 3 2 / 5 \|r_1\|_2=\sqrt{18/25}=3\sqrt2/5 ∥ r 1 ∥ 2 = 18/25 = 3 2 /5 。
练习 1.2.10
(求解 A X + X B = C AX+XB=C A X + X B = C ,其中 A = diag ( 1 , 2 ) A=\operatorname{diag}(1,2) A = diag ( 1 , 2 ) 、B = diag ( 1 , 3 ) B=\operatorname{diag}(1,3) B = diag ( 1 , 3 ) ,C C C 是 2 × 2 2\times2 2 × 2 全一矩阵。)
解答 · 答案 每个元素满足 ( a i + b j ) X i j = 1 (a_i+b_j)X_{ij}=1 ( a i + b j ) X ij = 1 ,故 X i j = 1 / ( a i + b j ) X_{ij}=1/(a_i+b_j) X ij = 1/ ( a i + b j ) ,X = ( 1 / 2 1 / 4 1 / 3 1 / 5 ) X=\begin{pmatrix}1/2&1/4\\1/3&1/5\end{pmatrix} X = ( 1/2 1/3 1/4 1/5 ) 。四个和 2 , 4 , 3 , 5 2,4,3,5 2 , 4 , 3 , 5 都非零,由可解性定理,解唯一。
练习 1.2.11
(给出一个 A x = b Ax=b A x = b 的例子,其残差范数为 10 − 6 10^{-6} 1 0 − 6 而误差范数为一,并说明什么额外信息可以导出前向误差界。)
解答 · 答案 取 A = diag ( 1 , 10 − 6 ) A=\operatorname{diag}(1,10^{-6}) A = diag ( 1 , 1 0 − 6 ) 、b = 0 b=0 b = 0 、x = ( 0 , 1 ) T x=(0,1)^T x = ( 0 , 1 ) T 。精确解为零,误差范数为一,残差 b − A x = ( 0 , − 10 − 6 ) T b-Ax=(0,-10^{-6})^T b − A x = ( 0 , − 1 0 − 6 ) T 的范数为 10 − 6 10^{-6} 1 0 − 6 。若已知最小奇异值的正下界,则 ∥ e ∥ 2 ≤ ∥ r ∥ 2 / σ min ( A ) \|e\|_2\le\|r\|_2/\sigma_{\min}(A) ∥ e ∥ 2 ≤ ∥ r ∥ 2 / σ m i n ( A ) ;这里 σ min = 10 − 6 \sigma_{\min}=10^{-6} σ m i n = 1 0 − 6 ,界恰好取到。
延伸学习
全局化牛顿法、非对称 Krylov 求解器、有限精度下的正交性损失、预处理矩阵的构造及大型稀疏 Sylvester 算法都需要独立分析。本节只建立若干工具,并非完整的数值线性代数课程。