大型稀疏方程組可能難以直接分解,因為消元會產生新的非零項。迭代法則利用原方程反覆更新近似解。這可能發揮稀疏性的優勢,但更新規則不會自動收斂:矩陣、更新順序以及鬆弛參數都會影響迭代。
設 A ∈ R n × n A\in\mathbb R^{n\times n} A ∈ R n × n 的對角元素非零,b ∈ R n b\in\mathbb R^n b ∈ R n 。寫 A = D + L + U A=D+L+U A = D + L + U ,其中 D D D 為對角部分,L , U L,U L , U 分別為嚴格下、上三角部分;它們的符號與 A A A 中的項相同,有些教材則取相反符號。固定解 x ∗ x^* x ∗ 滿足 A x ∗ = b Ax^*=b A x ∗ = b 。討論收斂到唯一解時,非奇異性要麼是明確假設,要麼由其他假設推出。
三種更新方式
Jacobi 法只使用上一輪的分量計算每個新分量:
x i ( k + 1 ) = 1 a i i ( b i − ∑ j ≠ i a i j x j ( k ) ) , x ( k + 1 ) = B J x ( k ) + D − 1 b , B J = − D − 1 ( L + U ) . x_i^{(k+1)}=\frac{1}{a_{ii}}\left(b_i-\sum_{j\ne i}a_{ij}x_j^{(k)}\right),\qquad
x^{(k+1)}=B_Jx^{(k)}+D^{-1}b,\quad B_J=-D^{-1}(L+U). x i ( k + 1 ) = a ii 1 b i − j = i ∑ a ij x j ( k ) , x ( k + 1 ) = B J x ( k ) + D − 1 b , B J = − D − 1 ( L + U ) .
定義 3.1.2
(Gauss–Seidel 迭代)
Gauss–Seidel 法按 1 , … , n 1,\ldots,n 1 , … , n 的順序,一得到新分量便立即使用:
x i ( k + 1 ) = b i − ∑ j < i a i j x j ( k + 1 ) − ∑ j > i a i j x j ( k ) a i i , B G S = − ( D + L ) − 1 U . x_i^{(k+1)}=\frac{b_i-\sum_{j<i}a_{ij}x_j^{(k+1)}-\sum_{j>i}a_{ij}x_j^{(k)}}{a_{ii}},\qquad
B_{GS}=-(D+L)^{-1}U. x i ( k + 1 ) = a ii b i − ∑ j < i a ij x j ( k + 1 ) − ∑ j > i a ij x j ( k ) , B GS = − ( D + L ) − 1 U .
這裏的逆矩陣表示解一個三角方程組;實現時不必顯式構造它。改變排序通常會改變 L , U L,U L , U ,因此也改變迭代。Jacobi 的各分量更新可同時計算,而 Gauss–Seidel 在一輪中使用新近算出的值。
逐次超鬆弛法(SOR)將每個舊分量向當前 Gauss–Seidel 值移動一個加權步長。對實參數 ω \omega ω ,其分量公式為
x i ( k + 1 ) = ( 1 − ω ) x i ( k ) + ω a i i ( b i − ∑ j < i a i j x j ( k + 1 ) − ∑ j > i a i j x j ( k ) ) . x_i^{(k+1)}=(1-\omega)x_i^{(k)}+
\frac{\omega}{a_{ii}}\left(b_i-\sum_{j<i}a_{ij}x_j^{(k+1)}-\sum_{j>i}a_{ij}x_j^{(k)}\right). x i ( k + 1 ) = ( 1 − ω ) x i ( k ) + a ii ω ( b i − j < i ∑ a ij x j ( k + 1 ) − j > i ∑ a ij x j ( k ) ) . 矩陣形式為 x ( k + 1 ) = B ω x ( k ) + ω ( D + ω L ) − 1 b x^{(k+1)}=B_\omega x^{(k)}+\omega(D+\omega L)^{-1}b x ( k + 1 ) = B ω x ( k ) + ω ( D + ω L ) − 1 b ,其中
B ω = ( D + ω L ) − 1 ( ( 1 − ω ) D − ω U ) . B_\omega=(D+\omega L)^{-1}\bigl((1-\omega)D-\omega U\bigr). B ω = ( D + ω L ) − 1 ( ( 1 − ω ) D − ω U ) .
D + ω L D+\omega L D + ω L 是三角矩陣,且與 D D D 有相同的非零對角線,因此非奇異。ω = 1 \omega=1 ω = 1 時是 Gauss–Seidel;ω = 0 \omega=0 ω = 0 時不作更新。通常 1 < ω < 2 1<\omega<2 1 < ω < 2 稱為超鬆弛,0 < ω < 1 0<\omega<1 0 < ω < 1 稱為欠鬆弛。
譜半徑判據
對任意定常迭代 x ( k + 1 ) = B x ( k ) + c x^{(k+1)}=Bx^{(k)}+c x ( k + 1 ) = B x ( k ) + c ,若其不動點為 x ∗ x^* x ∗ ,誤差滿足
e ( k + 1 ) = B e ( k ) , e ( k ) = B k e ( 0 ) , e ( k ) = x ( k ) − x ∗ . e^{(k+1)}=Be^{(k)},\qquad e^{(k)}=B^ke^{(0)},\qquad e^{(k)}=x^{(k)}-x^*. e ( k + 1 ) = B e ( k ) , e ( k ) = B k e ( 0 ) , e ( k ) = x ( k ) − x ∗ .
在有限維空間中,迭代從每個初始向量收斂到 x ∗ x^* x ∗ ,當且僅當 ρ ( B ) < 1 \rho(B)<1 ρ ( B ) < 1 ;這裏 ρ ( B ) \rho(B) ρ ( B ) 是 B B B 的特徵值模的最大值。
若 ρ ( B ) < 1 \rho(B)<1 ρ ( B ) < 1 ,複 Jordan 分解將 B k B^k B k 表示為有限多個項的組合,每項可由 k k k 的多項式乘特徵值 λ \lambda λ 的 ∣ λ ∣ k |\lambda|^k ∣ λ ∣ k 來控制,故每項趨於零,B k → 0 B^k\to0 B k → 0 。反過來,若某個特徵值的模至少為一,矩陣冪作用於對應複特徵向量時不能趨於零。若對所有實初始向量都收斂,則由線性性對所有複向量也趨於零,矛盾。
若 ρ ( B ) < 1 \rho(B)<1 ρ ( B ) < 1 ,則 1 不是 B B B 的特徵值,故 I − B I-B I − B 可逆,不動點唯一存在且等於 ( I − B ) − 1 c (I-B)^{-1}c ( I − B ) − 1 c 。該判據討論的是每個 初始向量。某個特殊初始誤差若沒有不穩定方向的分量,可能表現得更好。另外,在某個從屬範數下 ∥ B ∥ < 1 \|B\|<1 ∥ B ∥ < 1 是充分條件;範數大於一卻不能證明發散,因為只要 ρ ( B ) < 1 \rho(B)<1 ρ ( B ) < 1 ,矩陣冪仍可能衰減。
設 B = ( 0 10 0 0 ) B=\begin{pmatrix}0&10\\0&0\end{pmatrix} B = ( 0 0 10 0 ) 。則 ∥ B ∥ ∞ = 10 > 1 \|B\|_\infty=10>1 ∥ B ∥ ∞ = 10 > 1 ,但 B 2 = 0 B^2=0 B 2 = 0 ,所以對任意初始向量都有 e ( 2 ) = B 2 e ( 0 ) = 0 e^{(2)}=B^2e^{(0)}=0 e ( 2 ) = B 2 e ( 0 ) = 0 ,迭代兩步便收斂。判據看的是 ρ ( B ) \rho(B) ρ ( B ) (這裏等於 0 0 0 ),而不是某一個範數:範數小於一是充分條件,範數大於一則甚麼也不能說明。
命題 3.1.5
(嚴格行對角佔優下的 Jacobi 法)
若每行都滿足 ∣ a i i ∣ > ∑ j ≠ i ∣ a i j ∣ |a_{ii}|>\sum\limits_{j\ne i}|a_{ij}| ∣ a ii ∣ > j = i ∑ ∣ a ij ∣ ,則 A A A 非奇異,∥ B J ∥ ∞ < 1 \|B_J\|_\infty<1 ∥ B J ∥ ∞ < 1 ,Jacobi 法從任意初值收斂。
B J B_J B J 第 i i i 行元素的絕對值之和為 ∑ j ≠ i ∣ a i j ∣ / ∣ a i i ∣ < 1 \sum\limits_{j\ne i}|a_{ij}|/|a_{ii}|<1 j = i ∑ ∣ a ij ∣/∣ a ii ∣ < 1 ,故 ∥ B J ∥ ∞ < 1 \|B_J\|_\infty<1 ∥ B J ∥ ∞ < 1 ,從而 ρ ( B J ) < 1 \rho(B_J)<1 ρ ( B J ) < 1 ,由譜半徑判據得收斂。若 A x = 0 Ax=0 A x = 0 且 ∣ x i ∣ = ∥ x ∥ ∞ > 0 |x_i|=\|x\|_\infty>0 ∣ x i ∣ = ∥ x ∥ ∞ > 0 ,第 i i i 行給出 ∣ a i i ∣ ∣ x i ∣ ≤ ∑ j ≠ i ∣ a i j ∣ ∣ x j ∣ < ∣ a i i ∣ ∣ x i ∣ |a_{ii}||x_i|\le\sum\limits_{j\ne i}|a_{ij}||x_j|<|a_{ii}||x_i| ∣ a ii ∣∣ x i ∣ ≤ j = i ∑ ∣ a ij ∣∣ x j ∣ < ∣ a ii ∣∣ x i ∣ ,矛盾;所以 A A A 非奇異。
同一假設下的 Gauss–Seidel 法。 Jacobi 的界只是直接的行和估計,因為 B J = − D − 1 ( L + U ) B_J=-D^{-1}(L+U) B J = − D − 1 ( L + U ) 的元素一目了然。Gauss–Seidel 矩陣 B G S = − ( D + L ) − 1 U B_{GS}=-(D+L)^{-1}U B GS = − ( D + L ) − 1 U 含有逆矩陣,無法用同樣方式讀出各行。有用的思路是:不構造逆矩陣,而是透過定義 y = B G S x y=B_{GS}x y = B GS x 的三角方程組來估計它。對每一行,把非對角權重分成對角線之前與之後兩部分:
α i = 1 ∣ a i i ∣ ∑ j < i ∣ a i j ∣ , β i = 1 ∣ a i i ∣ ∑ j > i ∣ a i j ∣ . \alpha_i=\frac1{|a_{ii}|}\sum_{j<i}|a_{ij}|,\qquad
\beta_i=\frac1{|a_{ii}|}\sum_{j>i}|a_{ij}|. α i = ∣ a ii ∣ 1 j < i ∑ ∣ a ij ∣ , β i = ∣ a ii ∣ 1 j > i ∑ ∣ a ij ∣.
嚴格行對角佔優恰好表示每個 i i i 都有 α i + β i < 1 \alpha_i+\beta_i<1 α i + β i < 1 ,並且 ∥ B J ∥ ∞ = max i ( α i + β i ) \|B_J\|_\infty=\max\limits_i(\alpha_i+\beta_i) ∥ B J ∥ ∞ = i max ( α i + β i ) 。
定理 3.1.6
(嚴格行對角佔優下的 Gauss–Seidel 法)
若 A A A 嚴格行對角佔優,則
∥ B G S ∥ ∞ ≤ γ : = max 1 ≤ i ≤ n β i 1 − α i ≤ ∥ B J ∥ ∞ < 1. \|B_{GS}\|_\infty\le\gamma:=\max_{1\le i\le n}\frac{\beta_i}{1-\alpha_i}\le\|B_J\|_\infty<1. ∥ B GS ∥ ∞ ≤ γ := 1 ≤ i ≤ n max 1 − α i β i ≤ ∥ B J ∥ ∞ < 1. 因此 Gauss–Seidel 從任意初始向量收斂到唯一解,且 ∥ e ( k ) ∥ ∞ ≤ γ k ∥ e ( 0 ) ∥ ∞ \|e^{(k)}\|_\infty\le\gamma^k\|e^{(0)}\|_\infty ∥ e ( k ) ∥ ∞ ≤ γ k ∥ e ( 0 ) ∥ ∞ 。
每個 α i < 1 \alpha_i<1 α i < 1 ,所以分母 1 − α i 1-\alpha_i 1 − α i 均為正,γ \gamma γ 有定義。固定滿足 ∥ x ∥ ∞ = 1 \|x\|_\infty=1 ∥ x ∥ ∞ = 1 的 x x x ,令 y = B G S x y=B_{GS}x y = B GS x 。則 ( D + L ) y = − U x (D+L)y=-Ux ( D + L ) y = − U x ,其第 i i i 行為
a i i y i = − ∑ j < i a i j y j − ∑ j > i a i j x j . a_{ii}y_i=-\sum_{j<i}a_{ij}y_j-\sum_{j>i}a_{ij}x_j. a ii y i = − j < i ∑ a ij y j − j > i ∑ a ij x j . 這正是對誤差 x x x 作一輪 Gauss–Seidel:j < i j<i j < i 的 y j y_j y j 是本輪已更新的分量。若 y = 0 y=0 y = 0 ,無需證明。否則取 i i i 使 ∣ y i ∣ = ∥ y ∥ ∞ |y_i|=\|y\|_\infty ∣ y i ∣ = ∥ y ∥ ∞ 。將第 i i i 行除以 ∣ a i i ∣ |a_{ii}| ∣ a ii ∣ ,並利用 ∣ y j ∣ ≤ ∥ y ∥ ∞ |y_j|\le\|y\|_\infty ∣ y j ∣ ≤ ∥ y ∥ ∞ 與 ∣ x j ∣ ≤ 1 |x_j|\le1 ∣ x j ∣ ≤ 1 :
∥ y ∥ ∞ ≤ α i ∥ y ∥ ∞ + β i , 故 ∥ y ∥ ∞ ≤ β i 1 − α i ≤ γ . \|y\|_\infty\le\alpha_i\|y\|_\infty+\beta_i,
\qquad\text{故}\qquad
\|y\|_\infty\le\frac{\beta_i}{1-\alpha_i}\le\gamma. ∥ y ∥ ∞ ≤ α i ∥ y ∥ ∞ + β i , 故 ∥ y ∥ ∞ ≤ 1 − α i β i ≤ γ . 對所有單位向量 x x x 取最大值,得 ∥ B G S ∥ ∞ ≤ γ \|B_{GS}\|_\infty\le\gamma ∥ B GS ∥ ∞ ≤ γ 。至於與 Jacobi 的比較,對每一行有
( α i + β i ) ( 1 − α i ) − β i = α i ( 1 − α i − β i ) ≥ 0 , (\alpha_i+\beta_i)(1-\alpha_i)-\beta_i=\alpha_i(1-\alpha_i-\beta_i)\ge0, ( α i + β i ) ( 1 − α i ) − β i = α i ( 1 − α i − β i ) ≥ 0 , 故 β i / ( 1 − α i ) ≤ α i + β i ≤ ∥ B J ∥ ∞ \beta_i/(1-\alpha_i)\le\alpha_i+\beta_i\le\|B_J\|_\infty β i / ( 1 − α i ) ≤ α i + β i ≤ ∥ B J ∥ ∞ 。從屬範數是譜半徑的上界,所以 ρ ( B G S ) ≤ γ < 1 \rho(B_{GS})\le\gamma<1 ρ ( B GS ) ≤ γ < 1 ,由譜半徑定理得收斂。前面的對角佔優論證說明 A A A 非奇異,所以極限就是唯一解。每輪使用一次範數界,即得所述誤差估計。
證明透視
更新後的分量在估計中的作用 證明說明了新算出的值所起的作用。在第 i i i 行中,已更新的分量以總權重 α i \alpha_i α i 出現,而它們又受正在估計的同一個未知量 ∥ y ∥ ∞ \|y\|_\infty ∥ y ∥ ∞ 控制。把這一項移到左邊後,所得因子不大於 Jacobi 的行和。該結論比較的是最大範數下最壞情形的一輪因子。它本身並不斷言每個對角佔優矩陣都有 ρ ( B G S ) ≤ ρ ( B J ) \rho(B_{GS})\le\rho(B_J) ρ ( B GS ) ≤ ρ ( B J ) ,也不斷言從任意初值出發每一輪 Gauss–Seidel 的誤差都較小。若用同一個置換同時重排方程與未知量,嚴格行對角佔優得以保持,因此對每種這樣的排序都收斂;但 γ \gamma γ 的值取決於哪些元素落在對角線之前。
取下文二階比較中的矩陣 A = ( 4 1 1 3 ) A=\begin{pmatrix}4&1\\1&3\end{pmatrix} A = ( 4 1 1 3 ) ,它滿足 4 > 1 4>1 4 > 1 與 3 > 1 3>1 3 > 1 ,因此嚴格行對角佔優。其行權重為 α 1 = 0 \alpha_1=0 α 1 = 0 、β 1 = 1 / 4 \beta_1=1/4 β 1 = 1/4 、α 2 = 1 / 3 \alpha_2=1/3 α 2 = 1/3 、β 2 = 0 \beta_2=0 β 2 = 0 。於是 ∥ B J ∥ ∞ = 1 / 3 \|B_J\|_\infty=1/3 ∥ B J ∥ ∞ = 1/3 ,γ = max { 1 / 4 , 0 } = 1 / 4 \gamma=\max\{1/4,0\}=1/4 γ = max { 1/4 , 0 } = 1/4 。下文算出的 B G S B_{GS} B GS 各行絕對值之和為 1 / 4 1/4 1/4 與 1 / 12 1/12 1/12 ,所以 ∥ B G S ∥ ∞ = 1 / 4 \|B_{GS}\|_\infty=1/4 ∥ B GS ∥ ∞ = 1/4 ,此例中界恰好取到。
反例模式
Gauss–Seidel 不一定優於 Jacobi 若沒有這類假設,兩種方法互不佔優,所以「Gauss–Seidel 總是不比 Jacobi 差」的預期並不成立。本文稍後有一個 SPD 矩陣的例子:Jacobi 發散而 Gauss–Seidel 收斂。反方向的例子是
A = ( 1 2 − 2 1 1 1 2 2 1 ) , B J = ( 0 − 2 2 − 1 0 − 1 − 2 − 2 0 ) , B G S = ( 0 − 2 2 0 2 − 3 0 0 2 ) . A=\begin{pmatrix}1&2&-2\\1&1&1\\2&2&1\end{pmatrix},\qquad
B_J=\begin{pmatrix}0&-2&2\\-1&0&-1\\-2&-2&0\end{pmatrix},\qquad
B_{GS}=\begin{pmatrix}0&-2&2\\0&2&-3\\0&0&2\end{pmatrix}. A = 1 1 2 2 1 2 − 2 1 1 , B J = 0 − 1 − 2 − 2 0 − 2 2 − 1 0 , B GS = 0 0 0 − 2 2 0 2 − 3 2 . 這裏 det A = 1 \det A=1 det A = 1 ,且沒有一行對角佔優。沿第一行展開 det ( λ I − B J ) \det(\lambda I-B_J) det ( λ I − B J ) 得 λ 3 \lambda^3 λ 3 ,故 B J 3 = 0 B_J^3=0 B J 3 = 0 :在精確算術下,Jacobi 從任意初值出發至多三輪便得到解。Gauss–Seidel 矩陣由逐行求解 ( D + L ) B G S = − U (D+L)B_{GS}=-U ( D + L ) B GS = − U 得到,它是上三角矩陣,特徵值為 0 , 2 , 2 0,2,2 0 , 2 , 2 。初始誤差 ( 1 , − 1 , 0 ) T (1,-1,0)^T ( 1 , − 1 , 0 ) T 滿足 B G S ( 1 , − 1 , 0 ) T = 2 ( 1 , − 1 , 0 ) T B_{GS}(1,-1,0)^T=2(1,-1,0)^T B GS ( 1 , − 1 , 0 ) T = 2 ( 1 , − 1 , 0 ) T ,所以該誤差每輪倍增。
對稱正定矩陣下的 Gauss–Seidel 與 SOR
現在假設 A A A 對稱正定(SPD),即每個非零 v v v 滿足 v T A v > 0 v^TAv>0 v T A v > 0 。則 A A A 非奇異,且所有 a i i > 0 a_{ii}>0 a ii > 0 。考慮二次函數
Q ( x ) = 1 2 x T A x − b T x . Q(x)=\frac12x^TAx-b^Tx. Q ( x ) = 2 1 x T A x − b T x .
更新第 i i i 個分量時,令 r i = b i − ( A x ) i r_i=b_i-(Ax)_i r i = b i − ( A x ) i 為當前混合向量的殘差分量:本輪較早的分量已更新。SOR 將該分量改變 d = ω r i / a i i d=\omega r_i/a_{ii} d = ω r i / a ii 。展開二次函數得
Q ( x + d e i ) − Q ( x ) = − d r i + 1 2 a i i d 2 = − ω ( 2 − ω ) 2 a i i r i 2 . Q(x+de_i)-Q(x)=-d r_i+\frac12a_{ii}d^2
=-\frac{\omega(2-\omega)}{2a_{ii}}r_i^2. Q ( x + d e i ) − Q ( x ) = − d r i + 2 1 a ii d 2 = − 2 a ii ω ( 2 − ω ) r i 2 .
當 0 < ω < 2 0<\omega<2 0 < ω < 2 ,每次分量更新都會降低 Q Q Q ,除非該時刻的殘差分量為零。一整輪嚴格降低 Q Q Q ,除非起始向量已解出 A x = b Ax=b A x = b :若每一步的下降量都為零,則遇到的每個殘差都為零、沒有分量改變,原殘差也就為零。
若 A A A 對稱正定且 0 < ω < 2 0<\omega<2 0 < ω < 2 ,則 SOR 從任意初值收斂到唯一解。結論適用於任意固定的座標順序;特別地,ω = 1 \omega=1 ω = 1 給出 Gauss–Seidel 的收斂性。
由 A x ∗ = b Ax^*=b A x ∗ = b ,有 Q ( x ) − Q ( x ∗ ) = 1 2 ( x − x ∗ ) T A ( x − x ∗ ) Q(x)-Q(x^*)=\tfrac12(x-x^*)^TA(x-x^*) Q ( x ) − Q ( x ∗ ) = 2 1 ( x − x ∗ ) T A ( x − x ∗ ) 。一整輪對誤差的作用是線性映射 B ω B_\omega B ω 。上述計算表明,對每個非零誤差,∥ B ω e ∥ A < ∥ e ∥ A \|B_\omega e\|_A<\|e\|_A ∥ B ω e ∥ A < ∥ e ∥ A ,其中 ∥ e ∥ A = e T A e \|e\|_A=\sqrt{e^TAe} ∥ e ∥ A = e T A e 。在此範數的緊單位球面上,連續函數 ∥ B ω e ∥ A \|B_\omega e\|_A ∥ B ω e ∥ A 達到一個最大值 q < 1 q<1 q < 1 。故 ∥ e ( k ) ∥ A ≤ q k ∥ e ( 0 ) ∥ A → 0 \|e^{(k)}\|_A\le q^k\|e^{(0)}\|_A\to0 ∥ e ( k ) ∥ A ≤ q k ∥ e ( 0 ) ∥ A → 0 。論證使用有限維性,才能把對每個向量的嚴格下降變成一個共同的壓縮因子。它證明了這種 q q q 存在,但沒有給出可計算的數值收斂速度。
參數範圍是對 SPD 矩陣的充分保證,不是對所有矩陣的普遍結論。若 A = I A=I A = I ,則 B ω = ( 1 − ω ) I B_\omega=(1-\omega)I B ω = ( 1 − ω ) I :ω = 2 \omega=2 ω = 2 時非零誤差永遠交替;ω > 2 \omega>2 ω > 2 或 ω < 0 \omega<0 ω < 0 時誤差大小增長;ω = 0 \omega=0 ω = 0 時不變。即使 ω ∈ ( 0 , 2 ) \omega\in(0,2) ω ∈ ( 0 , 2 ) ,任意選取也不保證比 Gauss–Seidel 更快。
在下面的二階比較中,ω = 6 / 5 \omega=6/5 ω = 6/5 給出 ρ ( B 6 / 5 ) = 1 / 5 \rho(B_{6/5})=1/5 ρ ( B 6/5 ) = 1/5 ,比同一矩陣的 Gauss–Seidel(1 / 12 1/12 1/12 )更差。定理只保證 0 < ω < 2 0<\omega<2 0 < ω < 2 時收斂,並沒有說 ω > 1 \omega>1 ω > 1 就更快。好的 ω \omega ω 必須針對手頭的矩陣來選。
計算比較
取
A = ( 4 1 1 3 ) , b = ( 1 2 ) , x ∗ = ( 1 / 11 7 / 11 ) . A=\begin{pmatrix}4&1\\1&3\end{pmatrix},\qquad b=\binom12,\qquad x^*=\binom{1/11}{7/11}. A = ( 4 1 1 3 ) , b = ( 2 1 ) , x ∗ = ( 7/11 1/11 ) . A A A 是 SPD,因為對非零 x x x 有 x T A x = 4 ( x 1 + x 2 / 4 ) 2 + ( 11 / 4 ) x 2 2 > 0 x^TAx=4(x_1+x_2/4)^2+(11/4)x_2^2>0 x T A x = 4 ( x 1 + x 2 /4 ) 2 + ( 11/4 ) x 2 2 > 0 。從零出發,一輪 Jacobi 得 ( 1 / 4 , 2 / 3 ) T (1/4,2/3)^T ( 1/4 , 2/3 ) T ;一輪 Gauss–Seidel 得 ( 1 / 4 , 7 / 12 ) T (1/4,7/12)^T ( 1/4 , 7/12 ) T 。誤差矩陣及其譜半徑為
B J = ( 0 − 1 / 4 − 1 / 3 0 ) , ρ ( B J ) = 1 / 12 , B G S = ( 0 − 1 / 4 0 1 / 12 ) , ρ ( B G S ) = 1 / 12. B_J=\begin{pmatrix}0&-1/4\\-1/3&0\end{pmatrix},\quad
\rho(B_J)=1/\sqrt{12},\qquad
B_{GS}=\begin{pmatrix}0&-1/4\\0&1/12\end{pmatrix},\quad
\rho(B_{GS})=1/12. B J = ( 0 − 1/3 − 1/4 0 ) , ρ ( B J ) = 1/ 12 , B GS = ( 0 0 − 1/4 1/12 ) , ρ ( B GS ) = 1/12. 取 ω = 6 / 5 \omega=6/5 ω = 6/5 的 SOR 從零出發一輪得到 ( 3 / 10 , 17 / 25 ) T (3/10,17/25)^T ( 3/10 , 17/25 ) T ,且
B 6 / 5 = ( − 1 / 5 − 3 / 10 2 / 25 − 2 / 25 ) . B_{6/5}=\begin{pmatrix}-1/5&-3/10\\2/25&-2/25\end{pmatrix}. B 6/5 = ( − 1/5 2/25 − 3/10 − 2/25 ) . 它的一對共軛特徵值之積為 1 / 25 1/25 1/25 ,因此模為 1 / 5 1/5 1/5 。三個譜半徑均小於一,但這個超鬆弛參數的漸近因子比 Gauss–Seidel 大。譜半徑描述最壞情形的漸近幾何因子;特殊初始誤差可能衰減得更快,也不能必然預言一輪之後哪種誤差較小。
例題 3.1.10
(單個 SOR 座標更新使 Q Q Q 下降)
取 A = ( 4 1 1 3 ) A=\begin{pmatrix}4&1\\1&3\end{pmatrix} A = ( 4 1 1 3 ) 、b = ( 1 , 2 ) T b=(1,2)^T b = ( 1 , 2 ) T 、x = 0 x=0 x = 0 ,更新第一個座標。殘差分量為 r 1 = b 1 − ( A x ) 1 = 1 r_1=b_1-(Ax)_1=1 r 1 = b 1 − ( A x ) 1 = 1 ,a 11 = 4 a_{11}=4 a 11 = 4 。取 ω = 6 / 5 \omega=6/5 ω = 6/5 ,則改變量 d = ω r 1 / a 11 = 3 / 10 d=\omega r_1/a_{11}=3/10 d = ω r 1 / a 11 = 3/10 ,而
Q ( x + d e 1 ) − Q ( x ) = − d r 1 + 1 2 a 11 d 2 = − 3 10 + 9 50 = − 3 25 , Q(x+de_1)-Q(x)=-dr_1+\frac12a_{11}d^2=-\frac3{10}+\frac9{50}=-\frac3{25}, Q ( x + d e 1 ) − Q ( x ) = − d r 1 + 2 1 a 11 d 2 = − 10 3 + 50 9 = − 25 3 , 與 − ω ( 2 − ω ) r 1 2 / ( 2 a 11 ) = − ( 6 / 5 ) ( 4 / 5 ) / 8 -\omega(2-\omega)r_1^2/(2a_{11})=-(6/5)(4/5)/8 − ω ( 2 − ω ) r 1 2 / ( 2 a 11 ) = − ( 6/5 ) ( 4/5 ) /8 一致。ω = 1 \omega=1 ω = 1 時 d = 1 / 4 d=1/4 d = 1/4 ,下降量為 − 1 / 8 -1/8 − 1/8 ,是沿此座標可達的最大下降。在端點 ω = 2 \omega=2 ω = 2 處,d = 1 / 2 d=1/2 d = 1/2 ,− 1 2 + 1 2 = 0 -\frac12+\frac12=0 − 2 1 + 2 1 = 0 :完全沒有下降,所以嚴格下降的論證需要開區間 0 < ω < 2 0<\omega<2 0 < ω < 2 。
僅有正定性不能保證 Jacobi 收斂
反例模式
正定矩陣上 Jacobi 也可以發散 令 A A A 為對角元素為 1、其他元素均為 3 / 4 3/4 3/4 的 3 × 3 3\times3 3 × 3 矩陣。其特徵值為 5 / 2 , 1 / 4 , 1 / 4 5/2,1/4,1/4 5/2 , 1/4 , 1/4 ,故為 SPD。Jacobi 的 D = I D=I D = I ,B J = I − A B_J=I-A B J = I − A 的特徵值為 − 3 / 2 , 3 / 4 , 3 / 4 -3/2,3/4,3/4 − 3/2 , 3/4 , 3/4 。初始誤差取 ( 1 , 1 , 1 ) T (1,1,1)^T ( 1 , 1 , 1 ) T ,則每輪乘以 − 3 / 2 -3/2 − 3/2 ,因而發散。這不與上面的 SPD 定理矛盾:該定理適用於 Gauss–Seidel 與 SOR,而非 Jacobi。嚴格對角佔優是 Jacobi 的一個充分條件,此矩陣不滿足它。
殘差與停止
不必知道 x ∗ x^* x ∗ 也能計算殘差 r ( k ) = b − A x ( k ) r^{(k)}=b-Ax^{(k)} r ( k ) = b − A x ( k ) 。它滿足 r ( k ) = − A e ( k ) r^{(k)}=-Ae^{(k)} r ( k ) = − A e ( k ) ,故 A A A 非奇異時,在相容範數下 ∥ e ( k ) ∥ ≤ ∥ A − 1 ∥ ∥ r ( k ) ∥ \|e^{(k)}\|\le\|A^{-1}\|\|r^{(k)}\| ∥ e ( k ) ∥ ≤ ∥ A − 1 ∥∥ r ( k ) ∥ 。只有尺度和條件性允許時,小殘差才能保證小的前向誤差。實際中可監控縮放殘差並設置最大迭代次數;相鄰迭代值之差很小也可能是停滯。有限精度還限制可達到的精度,而精確算術下的收斂證明並不給出通用停止閾值。
設 A = diag ( 1 , 10 − 3 ) A=\operatorname{diag}(1,10^{-3}) A = diag ( 1 , 1 0 − 3 ) 、e = ( 0 , 1 ) T e=(0,1)^T e = ( 0 , 1 ) T 。則 r = − A e = ( 0 , − 10 − 3 ) T r=-Ae=(0,-10^{-3})^T r = − A e = ( 0 , − 1 0 − 3 ) T 的範數為 10 − 3 10^{-3} 1 0 − 3 ,而 ∥ e ∥ = 1 \|e\|=1 ∥ e ∥ = 1 。這裏 ∥ A − 1 ∥ = 10 3 \|A^{-1}\|=10^3 ∥ A − 1 ∥ = 1 0 3 ,界 ∥ e ∥ ≤ ∥ A − 1 ∥ ∥ r ∥ \|e\|\le\|A^{-1}\|\|r\| ∥ e ∥ ≤ ∥ A − 1 ∥∥ r ∥ 恰好取等。
練習與解答
快速檢查
(對上述二階例子,從零出發求第二次 Jacobi 迭代,並驗證不動點為 ( 1 / 11 , 7 / 11 ) T (1/11,7/11)^T ( 1/11 , 7/11 ) T 。)
對 ( 1 / 4 , 2 / 3 ) T (1/4,2/3)^T ( 1/4 , 2/3 ) T 套用 Jacobi 公式。
解答 · 答案 從 ( 1 / 4 , 2 / 3 ) (1/4,2/3) ( 1/4 , 2/3 ) 再作 Jacobi 更新得到 ( 1 / 12 , 7 / 12 ) (1/12,7/12) ( 1/12 , 7/12 ) 。將 ( 1 / 11 , 7 / 11 ) (1/11,7/11) ( 1/11 , 7/11 ) 代入 A x = b Ax=b A x = b 即驗證不動點。
快速檢查
(對 SPD 矩陣,一次 SOR 分量更新在 ω = 1 \omega=1 ω = 1 時如何改變 Q Q Q ?ω = 2 \omega=2 ω = 2 時呢?)
解答 · 答案 ω = 1 \omega=1 ω = 1 時變化為 − r i 2 / ( 2 a i i ) -r_i^2/(2a_{ii}) − r i 2 / ( 2 a ii ) ,這是沿該座標的最小值。ω = 2 \omega=2 ω = 2 時變化為零,因此嚴格下降證明不適用。
快速檢查
(令 A = I A=I A = I 、ω = 3 / 2 \omega=3/2 ω = 3/2 ,求 k k k 輪後的誤差和收斂因子。)
A = I A=I A = I 時 B ω B_\omega B ω 是甚麼?
解答 · 答案 B ω = − I / 2 B_\omega=-I/2 B ω = − I /2 ,故 e ( k ) = ( − 1 / 2 ) k e ( 0 ) e^{(k)}=(-1/2)^ke^{(0)} e ( k ) = ( − 1/2 ) k e ( 0 ) ,因子為 1 / 2 1/2 1/2 。
快速檢查
(Jacobi 能否對 SPD 矩陣發散?給出具體矩陣和初始誤差。)
找一個 SPD 矩陣,使 I − A I-A I − A 有小於 − 1 -1 − 1 的特徵值。
解答 · 答案 上述 3 × 3 3\times3 3 × 3 SPD 矩陣在 ( 1 , 1 , 1 ) T (1,1,1)^T ( 1 , 1 , 1 ) T 方向的 Jacobi 特徵值為 − 3 / 2 -3/2 − 3/2 ,該初始誤差發散。
快速檢查
(對 A = ( 2 1 1 2 ) A=\begin{pmatrix}2&1\\1&2\end{pmatrix} A = ( 2 1 1 2 ) ,求 α i , β i \alpha_i,\beta_i α i , β i 、γ \gamma γ 與 ∥ B J ∥ ∞ \|B_J\|_\infty ∥ B J ∥ ∞ 。再求 B G S B_{GS} B GS 、它的最大範數以及兩個譜半徑。一輪範數界相等,是否意味著漸近因子相等?)
逐行解 ( D + L ) B G S = − U (D+L)B_{GS}=-U ( D + L ) B GS = − U 。
解答 · 答案 α 1 = 0 \alpha_1=0 α 1 = 0 、β 1 = 1 / 2 \beta_1=1/2 β 1 = 1/2 、α 2 = 1 / 2 \alpha_2=1/2 α 2 = 1/2 、β 2 = 0 \beta_2=0 β 2 = 0 ,故 γ = 1 / 2 = ∥ B J ∥ ∞ \gamma=1/2=\|B_J\|_\infty γ = 1/2 = ∥ B J ∥ ∞ 。解 ( D + L ) B G S = − U (D+L)B_{GS}=-U ( D + L ) B GS = − U 得第一行 ( 0 , − 1 / 2 ) (0,-1/2) ( 0 , − 1/2 ) 、第二行 ( 0 , 1 / 4 ) (0,1/4) ( 0 , 1/4 ) ,所以 ∥ B G S ∥ ∞ = 1 / 2 \|B_{GS}\|_\infty=1/2 ∥ B GS ∥ ∞ = 1/2 。其特徵值為 0 , 1 / 4 0,1/4 0 , 1/4 ,ρ ( B G S ) = 1 / 4 \rho(B_{GS})=1/4 ρ ( B GS ) = 1/4 ;而 B J B_J B J 的特徵值為 ± 1 / 2 \pm1/2 ± 1/2 ,ρ ( B J ) = 1 / 2 \rho(B_J)=1/2 ρ ( B J ) = 1/2 。因此一輪範數界相等並不意味著漸近因子相等。
快速檢查
(對上文不對角佔優的 3 × 3 3\times3 3 × 3 例子,在右端為零時對誤差 ( 1 , − 1 , 0 ) T (1,-1,0)^T ( 1 , − 1 , 0 ) T 作一輪 Gauss–Seidel,驗證 B G S ( 1 , − 1 , 0 ) T = 2 ( 1 , − 1 , 0 ) T B_{GS}(1,-1,0)^T=2(1,-1,0)^T B GS ( 1 , − 1 , 0 ) T = 2 ( 1 , − 1 , 0 ) T 。)
解答 · 答案 取 x = ( 1 , − 1 , 0 ) T x=(1,-1,0)^T x = ( 1 , − 1 , 0 ) T ,依次得 y 1 = − ( 2 x 2 − 2 x 3 ) = 2 y_1=-(2x_2-2x_3)=2 y 1 = − ( 2 x 2 − 2 x 3 ) = 2 ,y 2 = − ( y 1 + x 3 ) = − 2 y_2=-(y_1+x_3)=-2 y 2 = − ( y 1 + x 3 ) = − 2 ,y 3 = − ( 2 y 1 + 2 y 2 ) = 0 y_3=-(2y_1+2y_2)=0 y 3 = − ( 2 y 1 + 2 y 2 ) = 0 。故 y = ( 2 , − 2 , 0 ) T = 2 x y=(2,-2,0)^T=2x y = ( 2 , − 2 , 0 ) T = 2 x 。