小殘差並不等於精確解
數值求解 A x = b Ax=b A x = b 時,我們需要算法、計算成本估計,以及判斷輸出意義的方法。精確的數學問題可能對數據的微小變化十分敏感;算法也可能在處理本來並不敏感的問題時引入可避免的誤差。這兩種不同的現象分別涉及條件性 和穩定性 ,不能混為一談。
除非另有說明,A A A 是 n × n n\times n n × n 實矩陣。若 A A A 非奇異,則精確解唯一:x = A − 1 b x=A^{-1}b x = A − 1 b 。實際計算通常無需顯式形成 A − 1 A^{-1} A − 1 ;可以先分解 A A A ,再求解三角方程組。計算結果 x ^ \widehat x x 的殘差為 r = b − A x ^ r=b-A\widehat x r = b − A x ,因此
A ( x − x ^ ) = r , x − x ^ = A − 1 r . A(x-\widehat x)=r,\qquad x-\widehat x=A^{-1}r. A ( x − x ) = r , x − x = A − 1 r .
殘差衡量計算結果滿足給定方程的程度。它也是右端項的精確擾動:A x ^ = b − r A\widehat x=b-r A x = b − r 。但殘差本身不是前向誤差 x − x ^ x-\widehat x x − x 。
高斯(Gauss)消去法與 LU 分解
假設消元過程中無需交換行,也沒有零主元。用每個主元行的倍數減去它下方的各行,得到上三角矩陣 U U U 。將倍數放入對角線為一的下三角矩陣 L L L ,便有 A = L U A=LU A = LU 。先用前代求解 L y = b Ly=b L y = b ,再用回代求解 U x = y Ux=y U x = y 。例如
A = ( 2 1 4 3 ) = ( 1 0 2 1 ) ( 2 1 0 1 ) . A=\begin{pmatrix}2&1\\4&3\end{pmatrix}
=\begin{pmatrix}1&0\\2&1\end{pmatrix}
\begin{pmatrix}2&1\\0&1\end{pmatrix}. A = ( 2 4 1 3 ) = ( 1 2 0 1 ) ( 2 0 1 1 ) .
若 b = ( 1 , 1 ) T b=(1,1)^T b = ( 1 , 1 ) T ,前代給出 y = ( 1 , − 1 ) T y=(1,-1)^T y = ( 1 , − 1 ) T ,回代得到 x = ( 1 , − 1 ) T x=(1,-1)^T x = ( 1 , − 1 ) T 。對於稠密矩陣,分解的運算量為 n 3 n^3 n 3 的量級;之後每增加一個右端項,求解的運算量為 n 2 n^2 n 2 的量級。因此,同一係數矩陣對應多個右端項時,只需分解一次。
非奇異矩陣仍可能有零首主元:( 0 1 1 0 ) \left(\begin{smallmatrix}0&1\\1&0\end{smallmatrix}\right) ( 0 1 1 0 ) 的逆就是自身。交換行可處理這種情況。部分選主元 在當前列的可用元素中選取絕對值最大的元素作為下一個主元,交換行後繼續。其分解形式為 P A = L U PA=LU P A = LU ,其中 P P P 是累計的置換矩陣。先解 L y = P b Ly=Pb L y = P b ,再解 U x = y Ux=y U x = y 。選主元還能避免除以不必要地小的主元,但不保證對所有矩陣都有小誤差:消元中元素仍可能大幅增長。
反例模式
非奇異矩陣未必有 LU 分解 斷言:每個非奇異矩陣都可分解為 A = L U A=LU A = LU ,其中 L L L 為單位下三角矩陣,U U U 為上三角矩陣。取 A = ( 0 1 1 0 ) A=\begin{pmatrix}0&1\\1&0\end{pmatrix} A = ( 0 1 1 0 ) ,det A = − 1 \det A=-1 det A = − 1 。若 A = ( 1 0 ℓ 1 ) ( u 11 u 12 0 u 22 ) A=\begin{pmatrix}1&0\\\ell&1\end{pmatrix}\begin{pmatrix}u_{11}&u_{12}\\0&u_{22}\end{pmatrix} A = ( 1 ℓ 0 1 ) ( u 11 0 u 12 u 22 ) ,由 ( 1 , 1 ) (1,1) ( 1 , 1 ) 元得 u 11 = 0 u_{11}=0 u 11 = 0 ,再由 ( 2 , 1 ) (2,1) ( 2 , 1 ) 元得 ℓ u 11 = 0 ≠ 1 \ell u_{11}=0\ne1 ℓ u 11 = 0 = 1 ,矛盾。對非奇異的 A A A ,LU 分解存在,恰好當 1 , … , n − 1 1,\dots,n-1 1 , … , n − 1 階的順序主子式都不為零;交換行便得到 P A = L U PA=LU P A = LU 。
後續選主元時,先前乘子也要隨行交換
在精確算術中對下列矩陣做部分選主元消元:
A = ( 4 2 0 2 2 2 − 2 1 1 ) . A=\begin{pmatrix}4&2&0\\2&2&2\\-2&1&1\end{pmatrix}. A = 4 2 − 2 2 2 1 0 2 1 . 第 1 列最大絕對值是 4 4 4 ,因此不換行。主元下方的乘子是 ℓ 21 = 1 / 2 \ell_{21}=1/2 ℓ 21 = 1/2 和 ℓ 31 = − 1 / 2 \ell_{31}=-1/2 ℓ 31 = − 1/2 。各行減去相應乘子倍的第 1 行,得到
( 4 2 0 0 1 2 0 2 1 ) . \begin{pmatrix}4&2&0\\0&1&2\\0&2&1\end{pmatrix}. 4 0 0 2 1 2 0 2 1 . 第 2 列尚未處理的元素中,2 2 2 的絕對值大於 1 1 1 ,所以交換第 2、3 行;活動行變成 ( 0 , 2 , 1 ) (0,2,1) ( 0 , 2 , 1 ) 和 ( 0 , 1 , 2 ) (0,1,2) ( 0 , 1 , 2 ) 。同時交換兩行已經保存的第 1 列乘子 :− 1 / 2 -1/2 − 1/2 現在屬於第 2 行,1 / 2 1/2 1/2 屬於第 3 行。下一個乘子是 1 / 2 1/2 1/2 ;第 3 行減去第 2 行的一半後得到 ( 0 , 0 , 3 / 2 ) (0,0,3/2) ( 0 , 0 , 3/2 ) 。因此
P = ( 1 0 0 0 0 1 0 1 0 ) , L = ( 1 0 0 − 1 / 2 1 0 1 / 2 1 / 2 1 ) , U = ( 4 2 0 0 2 1 0 0 3 / 2 ) . P=\begin{pmatrix}1&0&0\\0&0&1\\0&1&0\end{pmatrix},\qquad
L=\begin{pmatrix}1&0&0\\-1/2&1&0\\1/2&1/2&1\end{pmatrix},\qquad
U=\begin{pmatrix}4&2&0\\0&2&1\\0&0&3/2\end{pmatrix}. P = 1 0 0 0 0 1 0 1 0 , L = 1 − 1/2 1/2 0 1 1/2 0 0 1 , U = 4 0 0 2 2 0 0 1 3/2 . 不要只背規則,可以核對各行的歷史:
L U = ( 4 2 0 − 2 1 1 2 2 2 ) = P A . LU=\begin{pmatrix}4&2&0\\-2&1&1\\2&2&2\end{pmatrix}=PA. LU = 4 − 2 2 2 1 2 0 1 2 = P A . 如果把原有乘子留在原位,所得乘積的第 2 行將是 ( 2 , 3 , 1 ) (2,3,1) ( 2 , 3 , 1 ) ,而不是 ( − 2 , 1 , 1 ) (-2,1,1) ( − 2 , 1 , 1 ) ,於是 P A = L U PA=LU P A = LU 不成立。乘子記錄當前行曾如何被先前的主元行改變,因此必須隨這一行移動。在 L L L 中,只交換當前主元之前各列裏已經保存的元素;若交換最終單位下三角矩陣 L L L 的整行,就會移動對角線上的 1,破壞其形式。
一般地,在第 k k k 步,從第 k , … , n k,\ldots,n k , … , n 行的第 k k k 列中選取絕對值最大的元素。交換相應的活動行,以及 L L L 中第 1 , … , k − 1 1,\ldots,k-1 1 , … , k − 1 列已經保存的元素,若交換矩陣為 S S S ,則更新 P ← S P P\leftarrow SP P ← S P (從 P = I P=I P = I 開始)。然後把主元下方各元素除以主元,再從對應活動行中減去所得乘子倍的主元行。如果可選元素的最大絕對值為零,就不能做除法:活動列無法提供主元。對方陣而言,在精確消元中這表明矩陣奇異。這裏討論的是精確算術;捨入與元素增長需要另行分析。
得到 P A = L U PA=LU P A = LU 後,前代必須使用 P b Pb P b 。對上面的矩陣和 b = ( 6 , 6 , 0 ) T b=(6,6,0)^T b = ( 6 , 6 , 0 ) T ,先解 L y = b Ly=b L y = b 再解 U x = y Ux=y U x = y ,得 y = ( 6 , 9 , − 15 / 2 ) T y=(6,9,-15/2)^T y = ( 6 , 9 , − 15/2 ) T 、x = ( − 2 , 7 , − 5 ) T x=(-2,7,-5)^T x = ( − 2 , 7 , − 5 ) T 。A x Ax A x 的第二行為 2 ( − 2 ) + 2 ⋅ 7 + 2 ( − 5 ) = 0 2(-2)+2\cdot7+2(-5)=0 2 ( − 2 ) + 2 ⋅ 7 + 2 ( − 5 ) = 0 ,不是 6 6 6 ,所以這個向量不是解。
快速檢查
(用上面的因子解 A x = ( 6 , 6 , 0 ) T Ax=(6,6,0)^T A x = ( 6 , 6 , 0 ) T 。為甚麼兩次三角求解的第一個右端項是 P b Pb P b 而非 b b b ?)
解答 · 答案 換行給出 P b = ( 6 , 0 , 6 ) T Pb=(6,0,6)^T P b = ( 6 , 0 , 6 ) T 。對 L y = P b Ly=Pb L y = P b 作前代得到 y = ( 6 , 3 , 3 / 2 ) T y=(6,3,3/2)^T y = ( 6 , 3 , 3/2 ) T ;對 U x = y Ux=y U x = y 作回代得到 x = ( 1 , 1 , 1 ) T x=(1,1,1)^T x = ( 1 , 1 , 1 ) T 。因子代表的是 P A x = P b PAx=Pb P A x = P b ;除非 P b = b Pb=b P b = b ,否則 L y = b Ly=b L y = b 求解的是另一個方程組。
三角方程組如何求解
簡寫 L y = b Ly=b L y = b 、再解 U x = y Ux=y U x = y ,隱藏了未知量逐個得到的次序。設 L L L 為對角元素均非零的下三角矩陣。第 i i i 行只含 y 1 , … , y i y_1,\ldots,y_i y 1 , … , y i ,因此前代法按以下次序計算:
y i = b i − ∑ j = 1 i − 1 ℓ i j y j ℓ i i , i = 1 , … , n . y_i=\frac{b_i-\sum_{j=1}^{i-1}\ell_{ij}y_j}{\ell_{ii}},\qquad i=1,\ldots,n. y i = ℓ ii b i − ∑ j = 1 i − 1 ℓ ij y j , i = 1 , … , n .
空和為零,故第一步是 y 1 = b 1 / ℓ 11 y_1=b_1/\ell_{11} y 1 = b 1 / ℓ 11 。歸納地,右邊各項都已算出;每一行唯一確定一個 y i y_i y i ,這也證明了解的存在與唯一性。對於對角元素非零的上三角矩陣 U U U ,從最後一行開始,回代法同理得到
x i = y i − ∑ j = i + 1 n u i j x j u i i , i = n , n − 1 , … , 1. x_i=\frac{y_i-\sum_{j=i+1}^{n}u_{ij}x_j}{u_{ii}},\qquad i=n,n-1,\ldots,1. x i = u ii y i − ∑ j = i + 1 n u ij x j , i = n , n − 1 , … , 1.
稠密三角方程組各需計算 n ( n − 1 ) / 2 n(n-1)/2 n ( n − 1 ) /2 個乘積,另有減法和至多 n n n 次除法;對角線全為一時無需除法。因此,已有分解後,兩次求解共需 O ( n 2 ) O(n^2) O ( n 2 ) 次運算。這裏統計的是精確算術運算,不包括讀取數據的代價,也不保證精度;浮點求解還會產生捨入誤差。
設消元已經得到 P A = L U PA=LU P A = LU ,其中 P P P 交換第一、三行,且
L = ( 1 0 0 2 1 0 − 1 3 1 ) , U = ( 2 1 − 1 0 3 2 0 0 4 ) , b = ( 3 14 5 ) . L=\begin{pmatrix}1&0&0\\2&1&0\\-1&3&1\end{pmatrix},\quad
U=\begin{pmatrix}2&1&-1\\0&3&2\\0&0&4\end{pmatrix},\quad
b=\begin{pmatrix}3\\14\\5\end{pmatrix}. L = 1 2 − 1 0 1 3 0 0 1 , U = 2 0 0 1 3 0 − 1 2 4 , b = 3 14 5 . 由 P A x = P b PAx=Pb P A x = P b ,第一步的右端是 P b = ( 5 , 14 , 3 ) T Pb=(5,14,3)^T P b = ( 5 , 14 , 3 ) T ,不是 b b b 。前代得到 y 1 = 5 y_1=5 y 1 = 5 ,y 2 = 14 − 2 ( 5 ) = 4 y_2=14-2(5)=4 y 2 = 14 − 2 ( 5 ) = 4 ,y 3 = 3 + y 1 − 3 y 2 = − 4 y_3=3+y_1-3y_2=-4 y 3 = 3 + y 1 − 3 y 2 = − 4 。從 U x = y Ux=y U x = y 的最後一行回代,得 x 3 = − 1 x_3=-1 x 3 = − 1 ,x 2 = ( 4 − 2 x 3 ) / 3 = 2 x_2=(4-2x_3)/3=2 x 2 = ( 4 − 2 x 3 ) /3 = 2 ,x 1 = ( 5 − x 2 + x 3 ) / 2 = 1 x_1=(5-x_2+x_3)/2=1 x 1 = ( 5 − x 2 + x 3 ) /2 = 1 。所以 x = ( 1 , 2 , − 1 ) T x=(1,2,-1)^T x = ( 1 , 2 , − 1 ) T 。不必構造 A A A 即可驗算:U x = ( 5 , 4 , − 4 ) T Ux=(5,4,-4)^T U x = ( 5 , 4 , − 4 ) T 且 L U x = P b LUx=Pb LU x = P b ;由於 P P P 可逆,故 A x = b Ax=b A x = b 。
對角元素為零時,上面的除法無效,三角矩陣也奇異。但這不意味著對應方程組一定無解:diag ( 1 , 0 ) x = ( 1 , 0 ) T \operatorname{diag}(1,0)x=(1,0)^T diag ( 1 , 0 ) x = ( 1 , 0 ) T 有無窮多解,而右端改為 ( 1 , 1 ) T (1,1)^T ( 1 , 1 ) T 則無解。分解過程中若有合適的行,選主元可避開零主元;這不意味著三角求解時可以除以零。
快速檢查
(對下面的矩陣求解 L y = ( 2 , 1 , 4 ) T Ly=(2,1,4)^T L y = ( 2 , 1 , 4 ) T ,再求解 U x = y Ux=y U x = y 。)
L = ( 2 0 0 1 1 0 − 1 2 1 ) , U = ( 1 2 0 0 1 1 0 0 2 ) . L=\begin{pmatrix}2&0&0\\1&1&0\\-1&2&1\end{pmatrix},\qquad
U=\begin{pmatrix}1&2&0\\0&1&1\\0&0&2\end{pmatrix}. L = 2 1 − 1 0 1 2 0 0 1 , U = 1 0 0 2 1 0 0 1 2 .
解答 · 答案 前代得 y 1 = 1 y_1=1 y 1 = 1 、y 2 = 0 y_2=0 y 2 = 0 、y 3 = 5 y_3=5 y 3 = 5 ;回代得 x 3 = 5 / 2 x_3=5/2 x 3 = 5/2 、x 2 = − 5 / 2 x_2=-5/2 x 2 = − 5/2 、x 1 = 6 x_1=6 x 1 = 6 。第二次求解的右端是 y y y ,不是原來的向量。
對於實對稱正定矩陣,可以使用更專門的分解 A = L L T A=LL^T A = L L T ,其中 L L L 是對角線為正的下三角矩陣。正定意味著每個非零實向量 z z z 均滿足 z T A z > 0 z^TAz>0 z T A z > 0 。每一步所需的對角線平方根都是正的;例如
( 4 2 2 5 ) = ( 2 0 1 2 ) ( 2 1 0 2 ) . \begin{pmatrix}4&2\\2&5\end{pmatrix}
=\begin{pmatrix}2&0\\1&2\end{pmatrix}
\begin{pmatrix}2&1\\0&2\end{pmatrix}. ( 4 2 2 5 ) = ( 2 1 0 2 ) ( 2 0 1 2 ) .
僅有對稱性並不足夠:( 1 0 0 − 1 ) \left(\begin{smallmatrix}1&0\\0&-1\end{smallmatrix}\right) ( 1 0 0 − 1 ) 對稱,卻不可能等於 L L T LL^T L L T ,因為 z T L L T z = ∥ L T z ∥ 2 2 ≥ 0 z^TLL^Tz=\|L^Tz\|_2^2\geq0 z T L L T z = ∥ L T z ∥ 2 2 ≥ 0 。對於複 Hermitian 正定矩陣,轉置需改為共軛轉置。
思想史
作為數學問題的捨入誤差 Alan Turing 在其1948 年關於矩陣運算捨入誤差的論文 中,研究了若干線性方程求解和矩陣求逆方法的誤差,包括消元法。他的分析說明,統計運算次數與評估有限精度結果的準確性是兩個不同問題。這裏關於殘差和條件數的討論採用現代記號,並非將這些定義歸功於該論文。
條件數與誤差界
使用一個向量範數及其誘導矩陣範數。
設 A A A 非奇異,並固定一個向量範數及其誘導矩陣範數。A A A 的條件數為 κ ( A ) = ∥ A ∥ ∥ A − 1 ∥ \kappa(A)=\|A\|\,\|A^{-1}\| κ ( A ) = ∥ A ∥ ∥ A − 1 ∥ 。
設 A A A 非奇異,A x = b Ax=b A x = b 且 b ≠ 0 b\ne0 b = 0 ,x ^ \widehat x x 的殘差為 r = b − A x ^ r=b-A\widehat x r = b − A x 。則
∥ x − x ^ ∥ ∥ x ∥ ≤ κ ( A ) ∥ r ∥ ∥ b ∥ . \frac{\|x-\widehat x\|}{\|x\|}
\leq \kappa(A)\frac{\|r\|}{\|b\|}. ∥ x ∥ ∥ x − x ∥ ≤ κ ( A ) ∥ b ∥ ∥ r ∥ .
因為 x − x ^ = A − 1 r x-\widehat x=A^{-1}r x − x = A − 1 r ,所以 ∥ x − x ^ ∥ ≤ ∥ A − 1 ∥ ∥ r ∥ \|x-\widehat x\|\le\|A^{-1}\|\,\|r\| ∥ x − x ∥ ≤ ∥ A − 1 ∥ ∥ r ∥ 。又因為 ∥ b ∥ = ∥ A x ∥ ≤ ∥ A ∥ ∥ x ∥ \|b\|=\|Ax\|\le\|A\|\,\|x\| ∥ b ∥ = ∥ A x ∥ ≤ ∥ A ∥ ∥ x ∥ ,所以 1 / ∥ x ∥ ≤ ∥ A ∥ / ∥ b ∥ 1/\|x\|\le\|A\|/\|b\| 1/∥ x ∥ ≤ ∥ A ∥/∥ b ∥ 。把兩個不等式相乘即得所述的界。
該界可能高估實際誤差,但說明了為甚麼相對殘差小,單憑這一點不能保證相對前向誤差小。取 A = diag ( 1 , 10 − 8 ) A=\operatorname{diag}(1,10^{-8}) A = diag ( 1 , 1 0 − 8 ) 、b = ( 1 , 10 − 8 ) T b=(1,10^{-8})^T b = ( 1 , 1 0 − 8 ) T 和 x ^ = ( 1 , 0 ) T \widehat x=(1,0)^T x = ( 1 , 0 ) T 。精確解為 ( 1 , 1 ) T (1,1)^T ( 1 , 1 ) T ,殘差為 ( 0 , 10 − 8 ) T (0,10^{-8})^T ( 0 , 1 0 − 8 ) T 。在 Euclidean 範數下,相對殘差約為 10 − 8 10^{-8} 1 0 − 8 ,相對前向誤差卻為 1 / 2 1/\sqrt2 1/ 2 。這裏 κ 2 ( A ) = 10 8 \kappa_2(A)=10^8 κ 2 ( A ) = 1 0 8 。
若只擾動右端項,則 A ( x + Δ x ) = b + Δ b A(x+\Delta x)=b+\Delta b A ( x + Δ x ) = b + Δ b 給出 Δ x = A − 1 Δ b \Delta x=A^{-1}\Delta b Δ x = A − 1 Δ b ,把上述殘差換成 Δ b \Delta b Δ b 便得到同樣的相對界。擾動 A A A 還需額外條件:若某誘導矩陣範數滿足 ∥ A − 1 Δ A ∥ < 1 \|A^{-1}\Delta A\|<1 ∥ A − 1 Δ A ∥ < 1 ,則由收斂的 Neumann 級數可知 A + Δ A = A ( I + A − 1 Δ A ) A+\Delta A=A(I+A^{-1}\Delta A) A + Δ A = A ( I + A − 1 Δ A ) 可逆。沒有這類條件,微小擾動也可能使近奇異矩陣變為奇異。
在明確的誤差模型下,如果算法的計算結果是某個鄰近問題的精確解,而且數據的相對擾動受到控制,則稱該算法後向穩定。問題本身病態時,即使方法後向穩定,前向誤差仍可能很大;反之,條件良好的問題也可能受到不穩定算法的損害。「殘差小」必須相對於某個尺度來理解,不能單憑這句話確認其中任何一種性質。
近乎相關的方程
例題 2.1.5
(趨於零的擾動卻使解發生固定變化)
考慮
A ε = ( 1 1 1 1 + ε ) , b ε = ( 2 2 + ε ) , 0 < ε ≤ 1. A_\varepsilon=\begin{pmatrix}1&1\\1&1+\varepsilon\end{pmatrix},\qquad b_\varepsilon=\binom{2}{2+\varepsilon},\qquad 0<\varepsilon\le1. A ε = ( 1 1 1 1 + ε ) , b ε = ( 2 + ε 2 ) , 0 < ε ≤ 1. 第二個方程減去第一個得到 ε x 2 = ε \varepsilon x_2=\varepsilon ε x 2 = ε ,故精確解為 x = ( 1 , 1 ) T x=(1,1)^T x = ( 1 , 1 ) T 。若將 b ε b_\varepsilon b ε 的第二個分量增加 ε \varepsilon ε ,新解為 x ^ = ( 0 , 2 ) T \widehat x=(0,2)^T x = ( 0 , 2 ) T 。數據擾動隨 ε \varepsilon ε 趨於零,但解的變化始終是 ( − 1 , 1 ) T (-1,1)^T ( − 1 , 1 ) T 。這不違反在固定非奇異矩陣處的連續性:這裏矩陣本身也在變化,並趨於奇異矩陣。
若把 x ^ \widehat x x 看作原方程的近似解,則 r = b ε − A ε x ^ = ( 0 , − ε ) T r=b_\varepsilon-A_\varepsilon\widehat x=(0,-\varepsilon)^T r = b ε − A ε x = ( 0 , − ε ) T 。直接計算得到
A ε − 1 = 1 ε ( 1 + ε − 1 − 1 1 ) , κ ∞ ( A ε ) = ( 2 + ε ) 2 ε , ∥ r ∥ ∞ ∥ b ε ∥ ∞ = ε 2 + ε , ∥ x − x ^ ∥ ∞ ∥ x ∥ ∞ = 1. A_\varepsilon^{-1}=\frac1\varepsilon\begin{pmatrix}1+\varepsilon&-1\\-1&1\end{pmatrix},\qquad
\kappa_\infty(A_\varepsilon)=\frac{(2+\varepsilon)^2}{\varepsilon},\qquad
\frac{\|r\|_\infty}{\|b_\varepsilon\|_\infty}=\frac{\varepsilon}{2+\varepsilon},\qquad
\frac{\|x-\widehat x\|_\infty}{\|x\|_\infty}=1. A ε − 1 = ε 1 ( 1 + ε − 1 − 1 1 ) , κ ∞ ( A ε ) = ε ( 2 + ε ) 2 , ∥ b ε ∥ ∞ ∥ r ∥ ∞ = 2 + ε ε , ∥ x ∥ ∞ ∥ x − x ∥ ∞ = 1.
一般殘差界在此容許相對前向誤差達到 2 + ε 2+\varepsilon 2 + ε ;實際誤差為 1,說明最壞情形界不必取等號。取 ε = 10 − 4 \varepsilon=10^{-4} ε = 1 0 − 4 時,相對殘差約為 5.0 × 10 − 5 5.0\times10^{-5} 5.0 × 1 0 − 5 ,相對前向誤差仍為 1。部分選主元雖可改善消元的穩定性,卻無法消除問題本身的敏感性。
迭代方法與停止條件
對於大型稀疏方程組,分解可能產生大量新的非零元素。另一種方法是將 A = M − N A=M-N A = M − N 分裂,其中關於 M M M 的方程容易求解,並迭代
M x ( k + 1 ) = N x ( k ) + b , x ( k + 1 ) = B x ( k ) + c , B = M − 1 N . Mx^{(k+1)}=Nx^{(k)}+b,\qquad
x^{(k+1)}=Bx^{(k)}+c,\quad B=M^{-1}N. M x ( k + 1 ) = N x ( k ) + b , x ( k + 1 ) = B x ( k ) + c , B = M − 1 N .
假設 M M M 非奇異,迭代才有定義。當 A A A 非奇異時,精確解是一個不動點。誤差滿足 e ( k + 1 ) = B e ( k ) e^{(k+1)}=Be^{(k)} e ( k + 1 ) = B e ( k ) ,故 e ( k ) = B k e ( 0 ) e^{(k)}=B^ke^{(0)} e ( k ) = B k e ( 0 ) 。對每個初值都收斂,當且僅當 B k → 0 B^k\to0 B k → 0 ,等價於譜半徑 ρ ( B ) < 1 \rho(B)<1 ρ ( B ) < 1 。一個方便的充分條件是某個誘導範數滿足 ∥ B ∥ < 1 \|B\|<1 ∥ B ∥ < 1 。即使某個特定範數下 ∥ B ∥ > 1 \|B\|>1 ∥ B ∥ > 1 ,譜半徑條件仍決定最終收斂;收斂之前可能出現暫時增長。
Jacobi 迭代將 A = D + L + U A=D+L+U A = D + L + U 分為對角、嚴格下三角和嚴格上三角部分,並取 M = D M=D M = D 。所有對角元素都必須非零。若 A = ( 4 1 1 3 ) A=\left(\begin{smallmatrix}4&1\\1&3\end{smallmatrix}\right) A = ( 4 1 1 3 ) 、b = ( 1 , 2 ) T b=(1,2)^T b = ( 1 , 2 ) T ,則
x 1 ( k + 1 ) = 1 − x 2 ( k ) 4 , x 2 ( k + 1 ) = 2 − x 1 ( k ) 3 . x_1^{(k+1)}=\frac{1-x_2^{(k)}}4,\qquad
x_2^{(k+1)}=\frac{2-x_1^{(k)}}3. x 1 ( k + 1 ) = 4 1 − x 2 ( k ) , x 2 ( k + 1 ) = 3 2 − x 1 ( k ) .
從零開始,第一步得到 ( 1 / 4 , 2 / 3 ) (1/4,2/3) ( 1/4 , 2/3 ) 。迭代矩陣的無窮範數為 1 / 3 1/3 1/3 ,所以對每個初值都收斂;精確不動點為 ( 1 / 11 , 7 / 11 ) (1/11,7/11) ( 1/11 , 7/11 ) 。Gauss–Seidel 立即使用新計算的分量,即取 M = D + L M=D+L M = D + L 。其迭代矩陣不同,不能不檢查條件就僅由 Jacobi 收斂斷定它也收斂。
實際停止測試在 b ≠ 0 b\ne0 b = 0 時常使用 ∥ r k ∥ / ∥ b ∥ \|r_k\|/\|b\| ∥ r k ∥/∥ b ∥ ,並設置最大迭代次數。步長 ∥ x ( k + 1 ) − x ( k ) ∥ \|x^{(k+1)}-x^{(k)}\| ∥ x ( k + 1 ) − x ( k ) ∥ 很小可能表示停滯,而非準確。條件數決定殘差如何轉化為前向誤差,而有限精度最終限制可達到的精度。
考慮純量方程 0.01 x = 0.01 0.01x=0.01 0.01 x = 0.01 ,取分裂 M = 1 M=1 M = 1 、N = 0.99 N=0.99 N = 0.99 ,則 x ( k + 1 ) = 0.99 x ( k ) + 0.01 x^{(k+1)}=0.99x^{(k)}+0.01 x ( k + 1 ) = 0.99 x ( k ) + 0.01 ,精確解為 1 1 1 。從 x ( 0 ) = 0 x^{(0)}=0 x ( 0 ) = 0 出發,第一步 x ( 1 ) = 0.01 x^{(1)}=0.01 x ( 1 ) = 0.01 :步長為 0.01 0.01 0.01 ,誤差卻是 0.99 0.99 0.99 。一般地,x ( k + 1 ) − x ( k ) = ( B − I ) e ( k ) x^{(k+1)}-x^{(k)}=(B-I)e^{(k)} x ( k + 1 ) − x ( k ) = ( B − I ) e ( k ) ,所以當 ρ ( B ) \rho(B) ρ ( B ) 接近 1 1 1 時,很小的步長可能掩蓋很大的誤差。
練習與解答
快速檢查
(不選主元,將 A A A 分解為 L U LU LU ,並求解 A x = ( 3 , 10 ) T Ax=(3,10)^T A x = ( 3 , 10 ) T 。)
A = ( 1 2 3 7 ) . A=\begin{pmatrix}1&2\\3&7\end{pmatrix}. A = ( 1 3 2 7 ) .
解答 · 答案 L = ( 1 0 3 1 ) L=\left(\begin{smallmatrix}1&0\\3&1\end{smallmatrix}\right) L = ( 1 3 0 1 ) ,U = ( 1 2 0 1 ) U=\left(\begin{smallmatrix}1&2\\0&1\end{smallmatrix}\right) U = ( 1 0 2 1 ) 。前代得 ( 3 , 1 ) T (3,1)^T ( 3 , 1 ) T ,回代得 x = ( 1 , 1 ) T x=(1,1)^T x = ( 1 , 1 ) T 。
快速檢查
(對下面的數據,計算殘差和精確前向誤差。)
A = diag ( 1 , 10 − 6 ) , b = ( 1 10 − 6 ) , x ^ = ( 1 0 ) . A=\operatorname{diag}(1,10^{-6}),\qquad b=\begin{pmatrix}1\\10^{-6}\end{pmatrix},\qquad \widehat x=\begin{pmatrix}1\\0\end{pmatrix}. A = diag ( 1 , 1 0 − 6 ) , b = ( 1 1 0 − 6 ) , x = ( 1 0 ) .
解答 · 答案 r = ( 0 , 10 − 6 ) T r=(0,10^{-6})^T r = ( 0 , 1 0 − 6 ) T ;精確解為 ( 1 , 1 ) T (1,1)^T ( 1 , 1 ) T ,故 x − x ^ = ( 0 , 1 ) T x-\widehat x=(0,1)^T x − x = ( 0 , 1 ) T 。
快速檢查
(對下面的 Jacobi 例子,利用無窮範數證明收斂,並計算從零出發的第二次迭代。)
A = ( 4 1 1 3 ) , b = ( 1 2 ) . A=\begin{pmatrix}4&1\\1&3\end{pmatrix},\qquad b=\begin{pmatrix}1\\2\end{pmatrix}. A = ( 4 1 1 3 ) , b = ( 1 2 ) .
解答 · 答案 B = ( 0 − 1 / 4 − 1 / 3 0 ) B=\left(\begin{smallmatrix}0&-1/4\\-1/3&0\end{smallmatrix}\right) B = ( 0 − 1/3 − 1/4 0 ) 滿足 ∥ B ∥ ∞ = 1 / 3 < 1 \|B\|_\infty=1/3\lt1 ∥ B ∥ ∞ = 1/3 < 1 。代入更新式可得 x ( 2 ) = ( 1 / 12 , 7 / 12 ) T x^{(2)}=(1/12,7/12)^T x ( 2 ) = ( 1/12 , 7/12 ) T 。
矩陣與右端項的聯合擾動
實際計算中,矩陣與數據往往同時帶有誤差。因此我們要問:當 A A A 與 b b b 同時受到擾動時,解最多會改變多少?
設定。 設 A A A 非奇異,b ≠ 0 b\neq 0 b = 0 ,x = A − 1 b x=A^{-1}b x = A − 1 b ,從而 x ≠ 0 x\neq 0 x = 0 。設 ( A + E ) ( x + δ x ) = b + d (A+E)(x+\delta x)=b+d ( A + E ) ( x + δ x ) = b + d 。用下文向量範數所誘導的矩陣範數,記 κ = κ ( A ) = ∥ A ∥ ∥ A − 1 ∥ \kappa=\kappa(A)=\|A\|\,\|A^{-1}\| κ = κ ( A ) = ∥ A ∥ ∥ A − 1 ∥ ,並令 α = ∥ E ∥ / ∥ A ∥ \alpha=\|E\|/\|A\| α = ∥ E ∥/∥ A ∥ ,β = ∥ d ∥ / ∥ b ∥ \beta=\|d\|/\|b\| β = ∥ d ∥/∥ b ∥ 。假設 κ α < 1 \kappa\alpha<1 κ α < 1 。
在上述假設下,A + E A+E A + E 可逆,且
∥ δ x ∥ ∥ x ∥ ≤ κ ( α + β ) 1 − κ α . \frac{\|\delta x\|}{\|x\|}\le\frac{\kappa(\alpha+\beta)}{1-\kappa\alpha}. ∥ x ∥ ∥ δ x ∥ ≤ 1 − κ α κ ( α + β ) .
證明
(Neumann 級數、吸收項與對 b 的估計)
由於 ∥ A − 1 E ∥ ≤ ∥ A − 1 ∥ ∥ E ∥ = κ α < 1 \|A^{-1}E\|\le\|A^{-1}\|\,\|E\|=\kappa\alpha<1 ∥ A − 1 E ∥ ≤ ∥ A − 1 ∥ ∥ E ∥ = κ α < 1 ,由前面的結果知 I + A − 1 E I+A^{-1}E I + A − 1 E 可逆,故 A + E = A ( I + A − 1 E ) A+E=A(I+A^{-1}E) A + E = A ( I + A − 1 E ) 可逆,δ x \delta x δ x 唯一確定。減去 A x = b Ax=b A x = b 得 A δ x = d − E x − E δ x A\,\delta x=d-Ex-E\,\delta x A δ x = d − E x − E δ x ,於是
∥ δ x ∥ ≤ ∥ A − 1 ∥ ( ∥ d ∥ + ∥ E ∥ ∥ x ∥ + ∥ E ∥ ∥ δ x ∥ ) . \|\delta x\|\le\|A^{-1}\|\big(\|d\|+\|E\|\,\|x\|+\|E\|\,\|\delta x\|\big). ∥ δ x ∥ ≤ ∥ A − 1 ∥ ( ∥ d ∥ + ∥ E ∥ ∥ x ∥ + ∥ E ∥ ∥ δ x ∥ ) . 因為 ∥ A − 1 ∥ ∥ E ∥ = κ α \|A^{-1}\|\,\|E\|=\kappa\alpha ∥ A − 1 ∥ ∥ E ∥ = κ α ,把最後一項移到左邊得 ( 1 − κ α ) ∥ δ x ∥ ≤ ∥ A − 1 ∥ ( ∥ d ∥ + ∥ E ∥ ∥ x ∥ ) (1-\kappa\alpha)\|\delta x\|\le\|A^{-1}\|(\|d\|+\|E\|\,\|x\|) ( 1 − κ α ) ∥ δ x ∥ ≤ ∥ A − 1 ∥ ( ∥ d ∥ + ∥ E ∥ ∥ x ∥ ) 。1 − κ α > 0 1-\kappa\alpha>0 1 − κ α > 0 正是假設本身,所以可以兩邊相除。最後,由 ∥ b ∥ = ∥ A x ∥ ≤ ∥ A ∥ ∥ x ∥ \|b\|=\|Ax\|\le\|A\|\,\|x\| ∥ b ∥ = ∥ A x ∥ ≤ ∥ A ∥ ∥ x ∥ 得 ∥ A − 1 ∥ ∥ d ∥ / ∥ x ∥ ≤ ∥ A − 1 ∥ ∥ A ∥ ∥ d ∥ / ∥ b ∥ = κ β \|A^{-1}\|\,\|d\|/\|x\|\le\|A^{-1}\|\,\|A\|\,\|d\|/\|b\|=\kappa\beta ∥ A − 1 ∥ ∥ d ∥/∥ x ∥ ≤ ∥ A − 1 ∥ ∥ A ∥ ∥ d ∥/∥ b ∥ = κ β 。不等式 ∥ b ∥ / ∥ x ∥ ≤ ∥ A ∥ \|b\|/\|x\|\le\|A\| ∥ b ∥/∥ x ∥ ≤ ∥ A ∥ 只在這一步用到。□ \square □
證明透視
各個假設用在哪裏 證明有三步。第一,κ α < 1 \kappa\alpha\lt1 κ α < 1 給出 ∥ A − 1 E ∥ < 1 \|A^{-1}E\|\lt1 ∥ A − 1 E ∥ < 1 ,從而 A + E A+E A + E 可逆,δ x \delta x δ x 才存在。第二,減去 A x = b Ax=b A x = b 後得到的方程右邊也通過 E δ x E\,\delta x E δ x 含有 δ x \delta x δ x ;這一項被移到左邊吸收,除以 1 − κ α 1-\kappa\alpha 1 − κ α 則要求該因子為正。第三,∥ b ∥ ≤ ∥ A ∥ ∥ x ∥ \|b\|\le\|A\|\,\|x\| ∥ b ∥ ≤ ∥ A ∥ ∥ x ∥ 只用一次,把 ∥ d ∥ / ∥ x ∥ \|d\|/\|x\| ∥ d ∥/∥ x ∥ 轉成 ∥ d ∥ / ∥ b ∥ \|d\|/\|b\| ∥ d ∥/∥ b ∥ ;含 ∥ E ∥ ∥ x ∥ \|E\|\,\|x\| ∥ E ∥ ∥ x ∥ 的項不需要這一步,因為 ∥ x ∥ \|x\| ∥ x ∥ 直接約去。
此界是精確算術下的最壞情形上界。它不涉及捨入誤差,具體問題中實際量度到的誤差可能小得多。
取 ∞ \infty ∞ -範數,A = diag ( 1 , ε ) A=\operatorname{diag}(1,\varepsilon) A = diag ( 1 , ε ) ,0 < ε ≤ 1 0<\varepsilon\le1 0 < ε ≤ 1 ,b = ( 1 , ε ) b=(1,\varepsilon) b = ( 1 , ε ) ,E = diag ( 0 , − ε / 2 ) E=\operatorname{diag}(0,-\varepsilon/2) E = diag ( 0 , − ε /2 ) ,d = 0 d=0 d = 0 。則 x = ( 1 , 1 ) x=(1,1) x = ( 1 , 1 ) ,κ = 1 / ε \kappa=1/\varepsilon κ = 1/ ε ,α = ε / 2 \alpha=\varepsilon/2 α = ε /2 ,κ α = 1 / 2 \kappa\alpha=1/2 κ α = 1/2 ,β = 0 \beta=0 β = 0 ,所以上界為 ( 1 / 2 ) / ( 1 / 2 ) = 1 (1/2)/(1/2)=1 ( 1/2 ) / ( 1/2 ) = 1 。解 diag ( 1 , ε / 2 ) y = ( 1 , ε ) \operatorname{diag}(1,\varepsilon/2)\,y=(1,\varepsilon) diag ( 1 , ε /2 ) y = ( 1 , ε ) 得 y = ( 1 , 2 ) y=(1,2) y = ( 1 , 2 ) ,故 δ x = ( 0 , 1 ) \delta x=(0,1) δ x = ( 0 , 1 ) ,實際相對誤差為 1 1 1 。上界恰好取到。
反例模式
去掉對 A 的擾動須足夠小的假設 一個誘人的說法是:只要 α = ∥ E ∥ / ∥ A ∥ \alpha=\|E\|/\|A\| α = ∥ E ∥/∥ A ∥ 很小,擾動後的方程組就有相近的解。在 ∞ \infty ∞ -範數下取 A = diag ( 1 , ε ) A=\operatorname{diag}(1,\varepsilon) A = diag ( 1 , ε ) 、E = diag ( 0 , − ε ) E=\operatorname{diag}(0,-\varepsilon) E = diag ( 0 , − ε ) 、b = ( 1 , ε ) b=(1,\varepsilon) b = ( 1 , ε ) 。則 α = ε \alpha=\varepsilon α = ε 可以任意小,但 κ α = ( 1 / ε ) ε = 1 \kappa\alpha=(1/\varepsilon)\,\varepsilon=1 κ α = ( 1/ ε ) ε = 1 ,A + E = diag ( 1 , 0 ) A+E=\operatorname{diag}(1,0) A + E = diag ( 1 , 0 ) 是奇異的。方程組 ( A + E ) y = b (A+E)y=b ( A + E ) y = b 要求 0 ⋅ y 2 = ε ≠ 0 0\cdot y_2=\varepsilon\ne0 0 ⋅ y 2 = ε = 0 ,因此無解。修正就是定理的假設 κ α < 1 \kappa\alpha\lt1 κ α < 1 :α \alpha α 的小必須相對於 1 / κ 1/\kappa 1/ κ 衡量,而不是相對於 1 1 1 。
快速檢查
(在 ∞ \infty ∞ -範數下取 A = I A=I A = I ,E = diag ( 0 , 1 / 10 ) E=\operatorname{diag}(0,1/10) E = diag ( 0 , 1/10 ) ,b = ( 1 , 1 ) b=(1,1) b = ( 1 , 1 ) ,d = ( 0 , 1 / 10 ) d=(0,1/10) d = ( 0 , 1/10 ) 。求上界與實際誤差。)
先算 κ \kappa κ 、α \alpha α 和 β \beta β 。
解答 · 答案 此時 κ = 1 \kappa=1 κ = 1 ,α = β = 1 / 10 \alpha=\beta=1/10 α = β = 1/10 ,上界為 ( 2 / 10 ) / ( 9 / 10 ) = 2 / 9 (2/10)/(9/10)=2/9 ( 2/10 ) / ( 9/10 ) = 2/9 。然而由 ( A + E ) y = ( 1 , 11 / 10 ) (A+E)y=(1,11/10) ( A + E ) y = ( 1 , 11/10 ) 得 y = ( 1 , 1 ) = x y=(1,1)=x y = ( 1 , 1 ) = x ,實際誤差為 0 0 0 。兩個擾動互相抵消,而最壞情形上界無法察覺這一點。