消去法透過改變方程來解線性系統;定常迭代則固定更新規則,反覆改進一個向量。對稀疏矩陣,一輪更新可以只處理非零係數,避免因子分解可能產生的填入。不過,反覆使用一條看似合理的公式,不代表數值一定會接近解。
Jacobi 與 Gauss–Seidel 從同一組重新排列的方程出發,差別在於一輪中讀取哪些值。本節先精確說明這個差別,證明一個充分收斂條件,再回答實際問題:觀察到的改變很小,何時真的保證解誤差很小?這裏的 Jacobi 是解線性系統的迭代,不是特徵值問題中的 Jacobi 旋轉法。
重新排列方程,但不要隱藏相依關係
設 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 i i ≠ 0 a_{ii}\ne0 a ii = 0 。我們要找滿足 A x = b Ax=b A x = b 的向量。重新排列第 i i i 行得到
x i = b i − ∑ j ≠ i a i j x j a i i . x_i=\frac{b_i-\sum_{j\ne i}a_{ij}x_j}{a_{ii}}. x i = a ii b i − ∑ j = i a ij x j .
用 k k k 記錄完整更新輪數。Jacobi 的右方全部讀取上一個向量;Gauss–Seidel 則依次走訪第 1 , 2 , … , n 1,2,\ldots,n 1 , 2 , … , n 行,立即使用本輪已更新的分量。
寫成 A = D + L + U A=D+L+U A = D + L + U ,其中 D D D 為對角矩陣,L L L 為嚴格下三角矩陣,U U U 為嚴格上三角矩陣。三者保留 A A A 各項原來的符號。
Jacobi 使用
x i ( k + 1 ) = b i − ∑ j ≠ i a i j x j ( k ) a i i , x ( k + 1 ) = B J x ( k ) + D − 1 b , B J = − D − 1 ( L + U ) . x_i^{(k+1)}=\frac{b_i-\sum_{j\ne i}a_{ij}x_j^{(k)}}{a_{ii}},
\qquad
x^{(k+1)}=B_Jx^{(k)}+D^{-1}b,
\qquad B_J=-D^{-1}(L+U). x i ( k + 1 ) = a ii 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 ) . Gauss–Seidel 使用
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 , x ( k + 1 ) = B G x ( k ) + ( D + L ) − 1 b , B G = − ( 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
x^{(k+1)}=B_Gx^{(k)}+(D+L)^{-1}b,
\qquad B_G=-(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 ) , x ( k + 1 ) = B G x ( k ) + ( D + L ) − 1 b , B G = − ( D + L ) − 1 U . 這裏的三角逆矩陣記號是在描述映射;實現 Gauss–Seidel 是作代入計算,不是顯式建立該逆矩陣。
把含新值的項移到左邊,就得到矩陣式。由於 D D D 與 D + L D+L D + L 都可逆,兩種規則的一個向量是不動點,當且僅當它解出 A x = b Ax=b A x = b 。這證明了不動點與方程解的對應,但尚未證明迭代序列會收斂到它。
一個陣列的更新,可能悄悄換了算法
以下偽代碼描述單輪更新,前提是對角項非零。刻意不加外層停止迴圈,因為停止精度的說法還需要後面的估計。
jacobi_sweep(A, b, old):
allocate next with n entries
for i = 1,...,n:
next[i] = (b[i] - sum(A[i,j] * old[j] for j != i)) / A[i,i]
return next
gauss_seidel_sweep(A, b, x):
for i = 1,...,n:
x[i] = (b[i] - sum(A[i,j] * x[j] for j != i)) / A[i,i]
return x
第二種更新中,小索引分量已是新值,大索引分量仍是舊值。Jacobi 的各個輸出可以獨立計算;Gauss–Seidel 的指定次序則有前後依賴。
常見錯誤
(覆寫輸入陣列會把 Jacobi 變成 Gauss–Seidel)
如果把 old 換成一邊讀一邊覆寫的向量,就變成 Gauss–Seidel 式的相依關係,而不是 Jacobi,而且結果還取決於各行的走訪次序。Jacobi 更新需要兩個陣列:一個只讀,一個只寫。
用稀疏行表示時,只把已儲存的非零非對角項加起來。一輪工作量是 O ( nnz ( A ) + n ) O(\operatorname{nnz}(A)+n) O ( nnz ( A ) + n ) ,包括走訪各行及對角除法;稠密實現則是 O ( n 2 ) O(n^2) O ( n 2 ) 。達到指定精度需要多少輪,是另一部分成本。單輪便宜,不表示整個求解一定便宜。
證明一個不要求對稱的充分條件
使用向量範數 ∥ z ∥ ∞ = max i ∣ z i ∣ \|z\|_\infty=\max\limits_i|z_i| ∥ z ∥ ∞ = i max ∣ z i ∣ ,及其誘導矩陣範數 ∥ B ∥ ∞ = max i ∑ j ∣ b i j ∣ \|B\|_\infty=\max\limits_i\sum\limits_j|b_{ij}| ∥ B ∥ ∞ = i max j ∑ ∣ b ij ∣ 。逐行使用三角不等式,可得 ∥ B z ∥ ∞ ≤ ∥ B ∥ ∞ ∥ z ∥ ∞ \|Bz\|_\infty\leq\|B\|_\infty\|z\|_\infty ∥ B z ∥ ∞ ≤ ∥ B ∥ ∞ ∥ z ∥ ∞ 。
假設
q = max i ∑ j ≠ i ∣ a i j ∣ ∣ a i i ∣ < 1. q=\max_i\frac{\sum_{j\ne i}|a_{ij}|}{|a_{ii}|}<1. q = i max ∣ a ii ∣ ∑ j = i ∣ a ij ∣ < 1. 則 A A A 可逆,具有唯一解 x ∗ x^* x ∗ 。Jacobi 及上述排序的 Gauss–Seidel 都從任意初始向量收斂,並滿足
∥ x ( k ) − x ∗ ∥ ∞ ≤ q k ∥ x ( 0 ) − x ∗ ∥ ∞ . \|x^{(k)}-x^*\|_\infty\leq q^k\|x^{(0)}-x^*\|_\infty. ∥ x ( k ) − x ∗ ∥ ∞ ≤ q k ∥ x ( 0 ) − x ∗ ∥ ∞ . 這是充分條件,不是說每個不滿足它的矩陣都令迭代發散,也不要求矩陣對稱。
若 A z = 0 Az=0 A z = 0 且 z ≠ 0 z\ne0 z = 0 ,選 ∣ z i ∣ = ∥ z ∥ ∞ > 0 |z_i|=\|z\|_\infty>0 ∣ z i ∣ = ∥ z ∥ ∞ > 0 的一行。該行給出 ∣ a i i ∣ ∣ z i ∣ ≤ ∑ j ≠ i ∣ a i j ∣ ∥ z ∥ ∞ |a_{ii}||z_i|\leq\sum\limits_{j\ne i}|a_{ij}|\|z\|_\infty ∣ a ii ∣∣ z i ∣ ≤ j = i ∑ ∣ a ij ∣∥ z ∥ ∞ ,與嚴格行佔優矛盾。因此方陣可逆。
把解所滿足的方程,從 Jacobi 更新式中相減,每個新誤差分量都不超過該行非對角比率乘以舊的最大誤差,所以整個新誤差範數至多是舊值的 q q q 倍。
對 Gauss–Seidel,令舊最大誤差為 E E E ,沿更新次序歸納。假設已更新分量的誤差不超過 q E qE q E ,則下一行有
∣ e i n e w ∣ ≤ ∑ j < i ∣ a i j ∣ q E + ∑ j > i ∣ a i j ∣ E ∣ a i i ∣ ≤ q E , |e_i^{\mathrm{new}}|\leq
\frac{\sum_{j<i}|a_{ij}|qE+\sum_{j>i}|a_{ij}|E}{|a_{ii}|}
\leq qE, ∣ e i new ∣ ≤ ∣ a ii ∣ ∑ j < i ∣ a ij ∣ q E + ∑ j > i ∣ a ij ∣ E ≤ q E , 因為 q ≤ 1 q\leq1 q ≤ 1 ,而全部非對角比率至多是 q q q 。第一行的較小索引和為空,所以歸納起點也成立。反覆使用單輪誤差界,就得到定理。
把輸入向量與解之差,換成任意兩個輸入向量之差,同一個論證亦證明每個更新映射在無窮範數下都是收縮,因子至多為 q q q 。
證明透視
嚴格佔優用在哪裏 嚴格性在兩個不同的地方出現。在零空間向量的論證中,它產生矛盾 ∣ a i i ∣ ∣ z i ∣ ≤ ( ∑ j ≠ i ∣ a i j ∣ ) ∣ z i ∣ < ∣ a i i ∣ ∣ z i ∣ |a_{ii}||z_i|\leq(\sum\limits_{j\ne i}|a_{ij}|)|z_i|\lt|a_{ii}||z_i| ∣ a ii ∣∣ z i ∣ ≤ ( j = i ∑ ∣ a ij ∣ ) ∣ z i ∣ < ∣ a ii ∣∣ z i ∣ ,所以非嚴格不等式不能排除零空間向量。在收縮步驟中,它提供使幾何界趨於零的因子 q < 1 q\lt1 q < 1 。證明中不易察覺的一步是 Gauss–Seidel 的歸納:剛更新的分量只知道誤差至多為 q E qE q E ,而不是 E E E ;正是 q ≤ 1 q\leq1 q ≤ 1 使行的估計能吸收這個較弱的資訊而不損失因子 q q q 。選用最大範數,使每一行成為獨立的估計,行與行之間沒有耦合。
這個證明沒有比較兩種方法的實際收斂速度。若能證明 ∥ B J ∥ ∞ \|B_J\|_\infty ∥ B J ∥ ∞ 或 ∥ B G ∥ ∞ \|B_G\|_\infty ∥ B G ∥ ∞ 更小,就可以得到更好的界;排序亦會改變 Gauss–Seidel 的分裂。因此,某個矩陣及某個排序的結論,不能直接變成所有算法的普遍快慢排名。
用同一系統比較兩種新舊值規則
例題 10.1.3
(一個 Gauss–Seidel 立即利用新資訊的小系統)
取
A = ( 4 1 2 3 ) , b = ( 1 2 ) , x ∗ = ( 1 / 10 3 / 5 ) . A=\begin{pmatrix}4&1\\2&3\end{pmatrix},
\qquad b=\begin{pmatrix}1\\2\end{pmatrix},
\qquad x^*=\begin{pmatrix}1/10\\3/5\end{pmatrix}. A = ( 4 2 1 3 ) , b = ( 1 2 ) , x ∗ = ( 1/10 3/5 ) . 佔優界是 q = 2 / 3 q=2/3 q = 2/3 。從 ( 0 , 0 ) T (0,0)^T ( 0 , 0 ) T 出發:
例如,Gauss–Seidel 第一行先算出 1 / 4 1/4 1/4 ,第二行立即使用它,得到 ( 2 − 2 ( 1 / 4 ) ) / 3 = 1 / 2 (2-2(1/4))/3=1/2 ( 2 − 2 ( 1/4 )) /3 = 1/2 ;Jacobi 的第二行仍讀取舊零值,所以得到 2 / 3 2/3 2/3 。
迭代矩陣為
B J = ( 0 − 1 / 4 − 2 / 3 0 ) , B G = ( 0 − 1 / 4 0 1 / 6 ) . B_J=\begin{pmatrix}0&-1/4\\-2/3&0\end{pmatrix},
\qquad
B_G=\begin{pmatrix}0&-1/4\\0&1/6\end{pmatrix}. B J = ( 0 − 2/3 − 1/4 0 ) , B G = ( 0 0 − 1/4 1/6 ) . 它們的無窮範數分別是 2 / 3 2/3 2/3 、1 / 4 1/4 1/4 ,所以本例可用較小的 Gauss–Seidel 範數改善收縮保證。單看這個表,並不能證明任意數據的收斂性。
概念視角 代數
把收斂看作譜的性質 誤差滿足 e ( k ) = B k e ( 0 ) e^{(k)}=B^ke^{(0)} e ( k ) = B k e ( 0 ) ,所以迭代對每個初始向量都收斂,當且僅當譜半徑 ρ ( B ) < 1 \rho(B)<1 ρ ( B ) < 1 。在某個誘導範數下 ∥ B ∥ < 1 \|B\|<1 ∥ B ∥ < 1 是這個條件的充分證明,而不是等價條件。對於 B J = ( 0 − 2 − 1 / 10 0 ) B_J=\begin{pmatrix}0&-2\\-1/10&0\end{pmatrix} B J = ( 0 − 1/10 − 2 0 ) ,無窮範數是 2 2 2 ,但特徵值是 ± 1 / 5 \pm1/\sqrt5 ± 1/ 5 。在上述例題的方程組中,ρ ( B J ) = 1 / 6 ≈ 0.408 \rho(B_J)=1/\sqrt6\approx0.408 ρ ( B J ) = 1/ 6 ≈ 0.408 ,ρ ( B G ) = 1 / 6 \rho(B_G)=1/6 ρ ( B G ) = 1/6 。
從步差推出解誤差保證
設 F ( x ) = B x + c F(x)=Bx+c F ( x ) = B x + c ,∥ B ∥ ∞ ≤ θ < 1 \|B\|_\infty\leq\theta<1 ∥ B ∥ ∞ ≤ θ < 1 (這可以是佔優界 q q q ,或針對特定矩陣證明的更小上界),並設 x ( k ) = F ( x ( k − 1 ) ) x^{(k)}=F(x^{(k-1)}) x ( k ) = F ( x ( k − 1 ) ) 。令 Δ k = ∥ x ( k ) − x ( k − 1 ) ∥ ∞ \Delta_k=\|x^{(k)}-x^{(k-1)}\|_\infty Δ k = ∥ x ( k ) − x ( k − 1 ) ∥ ∞ ,x ∗ x^* x ∗ 為不動點。則對每個 k ≥ 1 k\geq1 k ≥ 1 ,
∥ x ∗ − x ( k ) ∥ ∞ ≤ θ 1 − θ Δ k . \|x^*-x^{(k)}\|_\infty\leq\frac{\theta}{1-\theta}\Delta_k. ∥ x ∗ − x ( k ) ∥ ∞ ≤ 1 − θ θ Δ k .
相鄰迭代值之差滿足 x ( m + 1 ) − x ( m ) = B ( x ( m ) − x ( m − 1 ) ) x^{(m+1)}-x^{(m)}=B(x^{(m)}-x^{(m-1)}) x ( m + 1 ) − x ( m ) = B ( x ( m ) − x ( m − 1 ) ) ,所以第 k k k 輪後,第 j j j 個未來步驟的長度至多是 θ j Δ k \theta^j\Delta_k θ j Δ k 。由於 θ < 1 \theta\lt1 θ < 1 ,迭代收斂到 x ∗ x^* x ∗ ,因此可把未來步驟望遠鏡相加:
∥ x ∗ − x ( k ) ∥ ∞ ≤ ∑ j = 1 ∞ θ j Δ k = θ 1 − θ Δ k . \|x^*-x^{(k)}\|_\infty
\leq\sum_{j=1}^\infty\theta^j\Delta_k
=\frac{\theta}{1-\theta}\Delta_k. ∥ x ∗ − x ( k ) ∥ ∞ ≤ j = 1 ∑ ∞ θ j Δ k = 1 − θ θ Δ k . 若 θ = 0 \theta=0 θ = 0 ,映射是常數,第一輪便到達不動點;對 k ≥ 1 k\geq1 k ≥ 1 ,零誤差界仍然正確。
證明透視
為甚麼求和從第一個未來步驟開始 求和從 j = 1 j=1 j = 1 而不是 j = 0 j=0 j = 0 開始,因為目前向量已包含長度為 Δ k \Delta_k Δ k 的那一步:只有尚未走的步驟才對誤差有貢獻。收縮因子只透過相鄰步差之間的關係起作用,所以更小的已證明 θ \theta θ 會直接改善保證,而沒有依據的 θ \theta θ 則使保證失效。乘數 θ / ( 1 − θ ) \theta/(1-\theta) θ / ( 1 − θ ) 把觀察到的一步換成對未觀察尾部的界,並隨 θ → 1 \theta\to1 θ → 1 而爆增。
對 0 < θ < 1 0<\theta<1 0 < θ < 1 ,若要保證解誤差至多為 ε \varepsilon ε ,一個充分停止條件是 Δ k ≤ ε ( 1 − θ ) / θ \Delta_k\leq\varepsilon(1-\theta)/\theta Δ k ≤ ε ( 1 − θ ) / θ 。
沒有已證明的收縮因子,只因 Δ k \Delta_k Δ k 低於容差就停止,甚麼也保證不了:乘數可能很大。例如 θ = 0.99 \theta=0.99 θ = 0.99 時,乘數為 99,所以 10 − 6 10^{-6} 1 0 − 6 的步差只能保證誤差至多 9.9 × 10 − 5 9.9\times10^{-5} 9.9 × 1 0 − 5 。
用殘差及其尺度控制解誤差
嚴格行對角佔優還給出另一種保證,對任何 近似值 z z z 都適用,不論它如何產生。
設 A A A 嚴格行對角佔優,並定義
γ = min i ( ∣ a i i ∣ − ∑ j ≠ i ∣ a i j ∣ ) > 0 , r = b − A z . \gamma=\min_i\left(|a_{ii}|-\sum_{j\ne i}|a_{ij}|\right)>0,
\qquad r=b-Az. γ = i min ∣ a ii ∣ − j = i ∑ ∣ a ij ∣ > 0 , r = b − A z . 則
∥ z − x ∗ ∥ ∞ ≤ ∥ r ∥ ∞ γ . \|z-x^*\|_\infty\leq\frac{\|r\|_\infty}{\gamma}. ∥ z − x ∗ ∥ ∞ ≤ γ ∥ r ∥ ∞ .
令 e = z − x ∗ e=z-x^* e = z − x ∗ ,便有 A e = − r Ae=-r A e = − r ,再選 ∣ e i ∣ = ∥ e ∥ ∞ |e_i|=\|e\|_\infty ∣ e i ∣ = ∥ e ∥ ∞ 的一行。三角不等式給出 ∣ a i i ∣ ∥ e ∥ ∞ ≤ ∥ r ∥ ∞ + ∑ j ≠ i ∣ a i j ∣ ∥ e ∥ ∞ |a_{ii}|\|e\|_\infty\leq\|r\|_\infty+\sum\limits_{j\ne i}|a_{ij}|\|e\|_\infty ∣ a ii ∣∥ e ∥ ∞ ≤ ∥ r ∥ ∞ + j = i ∑ ∣ a ij ∣∥ e ∥ ∞ 。把非對角項移到左邊,再用下界 γ \gamma γ 即可。證明不要求對稱、正定或某一種迭代映射。
殘差本身有尺度。對 A = diag ( 1 , ε ) A=\operatorname{diag}(1,\varepsilon) A = diag ( 1 , ε ) 、b = ( 1 , ε ) T b=(1,\varepsilon)^T b = ( 1 , ε ) T 、0 < ε ≤ 1 0<\varepsilon\leq1 0 < ε ≤ 1 ,解為 ( 1 , 1 ) T (1,1)^T ( 1 , 1 ) T ,近似值 ( 1 , 0 ) T (1,0)^T ( 1 , 0 ) T 的殘差為 ( 0 , ε ) T (0,\varepsilon)^T ( 0 , ε ) T ,範數是 ε \varepsilon ε ,解誤差卻是 1。此時 γ = ε \gamma=\varepsilon γ = ε ,誤差界正確給出 ε / ε = 1 \varepsilon/\varepsilon=1 ε / ε = 1 ,並沒有把小殘差誤當成小前向誤差。
例題 10.1.7
(保證第三個 Gauss–Seidel 迭代值)
在前面的 Gauss–Seidel 例子中,第三輪步差為 Δ 3 = 1 / 48 \Delta_3=1/48 Δ 3 = 1/48 。用已證明的 θ = 1 / 4 \theta=1/4 θ = 1/4 ,得到誤差至多 ( 1 / 3 ) ( 1 / 48 ) = 1 / 144 (1/3)(1/48)=1/144 ( 1/3 ) ( 1/48 ) = 1/144 ;因為此例另外知道精確解,可以算出實際誤差為 1 / 240 1/240 1/240 。若改用較鬆的共同因子 q = 2 / 3 q=2/3 q = 2/3 ,則只得到 2 ⋅ ( 1 / 48 ) = 1 / 24 2\cdot(1/48)=1/24 2 ⋅ ( 1/48 ) = 1/24 。有效的保證可以保守,而改善已證明的常數確實有用。
系統有唯一解,迭代仍可能發散
反例模式
解的存在唯一性,不是迭代收斂保證 令 A = ( 1 2 2 1 ) A=\begin{pmatrix}1&2\\2&1\end{pmatrix} A = ( 1 2 2 1 ) 、b = ( 3 , 3 ) T b=(3,3)^T b = ( 3 , 3 ) T 。行列式為 − 3 -3 − 3 ,所以唯一解是 ( 1 , 1 ) T (1,1)^T ( 1 , 1 ) T 。
Jacobi 從零出發給出 ( 0 , 0 ) T , ( 3 , 3 ) T , ( − 3 , − 3 ) T , ( 9 , 9 ) T , … (0,0)^T,(3,3)^T,(-3,-3)^T,(9,9)^T,\ldots ( 0 , 0 ) T , ( 3 , 3 ) T , ( − 3 , − 3 ) T , ( 9 , 9 ) T , … 。沿 ( 1 , 1 ) T (1,1)^T ( 1 , 1 ) T 的誤差每輪乘以 − 2 -2 − 2 ,愈來愈大。重新排列的方程有正確不動點,但更新反而把向量推離它。
另一方面,不通過佔優測試亦不能證明發散。對 A = ( 1 2 1 / 10 1 ) A=\begin{pmatrix}1&2\\1/10&1\end{pmatrix} A = ( 1 1/10 2 1 ) ,Jacobi 無窮範數為 2,卻有 B J 2 = ( 1 / 5 ) I B_J^2=(1/5)I B J 2 = ( 1/5 ) I 。每兩輪都把任何誤差縮至 1 / 5 1/5 1/5 ,所以任意起點都收斂。單輪範數測試可能失敗,兩輪論證卻成功。
分清精確算術定理與程式算出的診斷量
程式計算的殘差可能含捨入誤差,每輪更新也可能有算術擾動。本節證明的是精確映射與精確殘差。完整的浮點誤差保證還須控制這些擾動;單是印出「殘差」二字,不會自動提供該誤差界。
稀疏求解可以定期重新計算殘差,而不只從最新步差猜測。每一行殘差都須使用同一個完整迭代向量。
在 Gauss–Seidel 中,最後走訪的方程剛剛為新值解出,所以一輪結束時恰好滿足,但較早的方程已因後面分量改變而重新出現誤差。在例子中,第三個迭代值的第二行殘差為 0 0 0 ,第一行殘差卻是 − 1 / 72 -1/72 − 1/72 。只讀取最後一行的殘差測試因此並不足夠。
兩種保證的假設不同:步差界要求更新映射有已證明的收縮因子;殘差界則要求已證明的殘差至解誤差控制,本節用嚴格行對角佔優提供它。兩者都不能單靠設定一個小容差推出。
練習與解答
快速檢查
(在例子的 2 × 2 2\times2 2 × 2 系統中,說明第一個 Jacobi 向量為何是 ( 1 / 4 , 2 / 3 ) T (1/4,2/3)^T ( 1/4 , 2/3 ) T ,第一個 Gauss–Seidel 向量卻是 ( 1 / 4 , 1 / 2 ) T (1/4,1/2)^T ( 1/4 , 1/2 ) T 。偽代碼中哪種修改會無意間把第一種方法變成第二種?)
解答 · 答案 兩者先得到第一分量 1 / 4 1/4 1/4 。Jacobi 第二行讀舊 x 1 = 0 x_1=0 x 1 = 0 ,得到 2 / 3 2/3 2/3 ;Gauss–Seidel 讀剛更新的 x 1 = 1 / 4 x_1=1/4 x 1 = 1/4 ,得到 ( 2 − 1 / 2 ) / 3 = 1 / 2 (2-1/2)/3=1/2 ( 2 − 1/2 ) /3 = 1/2 。若把 Jacobi 輸出直接寫回輸入陣列,並在後面行讀取這個已修改陣列,就改變了相依關係。分開的 old/next 陣列正是為了避免這件事。
快速檢查
(在例子的第三個 Jacobi 迭代值 ( 1 / 8 , 11 / 18 ) T (1/8,11/18)^T ( 1/8 , 11/18 ) T ,分別用 θ = 2 / 3 \theta=2/3 θ = 2/3 的步差界及 γ = min ( 4 − 1 , 3 − 2 ) \gamma=\min(4-1,3-2) γ = min ( 4 − 1 , 3 − 2 ) 的殘差界估計誤差。哪一個能保證誤差至多 1 / 5 1/5 1/5 ?)
分別計算 Δ 3 \Delta_3 Δ 3 和殘差 b − A x ( 3 ) b-Ax^{(3)} b − A x ( 3 ) 。
解答 · 答案 第二個迭代值是 ( 1 / 12 , 1 / 2 ) T (1/12,1/2)^T ( 1/12 , 1/2 ) T ,所以 Δ 3 = max { ∣ 1 / 8 − 1 / 12 ∣ , ∣ 11 / 18 − 1 / 2 ∣ } = max { 1 / 24 , 1 / 9 } = 1 / 9 \Delta_3=\max\{|1/8-1/12|,|11/18-1/2|\}=\max\{1/24,1/9\}=1/9 Δ 3 = max { ∣1/8 − 1/12∣ , ∣11/18 − 1/2∣ } = max { 1/24 , 1/9 } = 1/9 。步差界為 2 / 3 1 / 3 ⋅ 1 9 = 2 / 9 ≈ 0.222 > 1 / 5 \dfrac{2/3}{1/3}\cdot\dfrac19=2/9\approx0.222>1/5 1/3 2/3 ⋅ 9 1 = 2/9 ≈ 0.222 > 1/5 。
殘差是 b − A x ( 3 ) = ( 1 − 1 / 2 − 11 / 18 , 2 − 1 / 4 − 11 / 6 ) T = ( − 1 / 9 , − 1 / 12 ) T b-Ax^{(3)}=(1-1/2-11/18,\ 2-1/4-11/6)^T=(-1/9,-1/12)^T b − A x ( 3 ) = ( 1 − 1/2 − 11/18 , 2 − 1/4 − 11/6 ) T = ( − 1/9 , − 1/12 ) T ,γ = 1 \gamma=1 γ = 1 ,得到界 1 / 9 ≈ 0.111 < 1 / 5 1/9\approx0.111<1/5 1/9 ≈ 0.111 < 1/5 。因此這裏是殘差界能證明所需精度,步差界則不能。實際誤差是 1 / 40 1/40 1/40 ;一個充分界未通過,不代表近似值不準確。
快速檢查
(對 A = ( 1 2 1 / 10 1 ) A=\begin{pmatrix}1&2\\1/10&1\end{pmatrix} A = ( 1 1/10 2 1 ) ,用兩輪更新證明 Jacobi 收斂。對 m ≥ 1 m\ge1 m ≥ 1 ,由第 2 m 2m 2 m 與第 2 m − 2 2m-2 2 m − 2 個迭代值的差,推導第 2 m 2m 2 m 個值的停止誤差界。)
計算 B J 2 B_J^2 B J 2 ,並把步差保證用於兩輪映射。
解答 · 答案 A A A 的行列式為 4 / 5 4/5 4/5 ,所以解唯一。此時 B J = ( 0 − 2 − 1 / 10 0 ) B_J=\begin{pmatrix}0&-2\\-1/10&0\end{pmatrix} B J = ( 0 − 1/10 − 2 0 ) ,故 B J 2 = ( 1 / 5 ) I B_J^2=(1/5)I B J 2 = ( 1/5 ) I 。兩輪仿射映射 F ∘ F F\circ F F ∘ F 的收縮因子是 1 / 5 1/5 1/5 ,不動點與原方法相同且唯一。因此偶數子序列收斂;奇數子序列是把連續映射 F F F 作用在偶數子序列上,所以亦收斂。
把步差保證用於兩輪映射,而不是單輪映射,得到 ∥ x ( 2 m ) − x ∗ ∥ ∞ ≤ ( 1 / 4 ) ∥ x ( 2 m ) − x ( 2 m − 2 ) ∥ ∞ \|x^{(2m)}-x^*\|_\infty\leq(1/4)\|x^{(2m)}-x^{(2m-2)}\|_\infty ∥ x ( 2 m ) − x ∗ ∥ ∞ ≤ ( 1/4 ) ∥ x ( 2 m ) − x ( 2 m − 2 ) ∥ ∞ 。若把兩輪常數配上一輪步差,就不是已證明的結果。
快速檢查
(設 A = diag ( 1 , ε ) A=\operatorname{diag}(1,\varepsilon) A = diag ( 1 , ε ) 、b = ( 1 , ε ) T b=(1,\varepsilon)^T b = ( 1 , ε ) T 、0 < ε ≤ 1 0<\varepsilon\le1 0 < ε ≤ 1 ,近似值 z = ( 1 , 0 ) T z=(1,0)^T z = ( 1 , 0 ) T 。求精確解、殘差、誤差及 γ \gamma γ 。為甚麼小殘差本身不能保證小前向誤差?)
解答 · 答案 精確解是 ( 1 , 1 ) T (1,1)^T ( 1 , 1 ) T ,殘差 b − A z = ( 0 , ε ) T b-Az=(0,\varepsilon)^T b − A z = ( 0 , ε ) T ,解誤差的無窮範數為 1。嚴格行佔優給出 γ = ε \gamma=\varepsilon γ = ε ,所以殘差界是 ε / ε = 1 \varepsilon/\varepsilon=1 ε / ε = 1 ,與實際誤差一致。小殘差出現在矩陣係數很小的方向,必須除以有依據的尺度。
Jacobi 對這個對角系統只需一輪精確更新,因為迭代矩陣為零。但這不表示題目的初始近似值準確,也不能因未縮放的殘差很小,就在修正前提早停止。