動機
許多計算問題不能一步解決。非線性模型被替換成一連串線性模型;每個大型線性方程組又可能要以迭代方法求解。分開檢視兩層,才能問清楚:非線性近似在甚麼情況下準確?每次線性方程應解到多精確?殘差小是否意味誤差小?本節討論牛頓(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 算法均需要獨立分析。本節只建立若干工具,並非完整數值線性代數課程。