動機
離散化模型、擬合係數或同時滿足多個限制,都會產生線性方程組 Ax=b。方程本身不會告訴我們計算向量是否準確:我們既需要求解方法,也需要判斷數據擾動的影響。本節 A 是實方陣,除非另有說明,向量和矩陣範數互相相容。
消元及選主元
精確算術下,高斯(Gauss)消去法以等價的上三角系統取代原系統。在第 k 列,用第 k 行的倍數消去下方該列的元素。得到 Ux=c 後,從最後一個方程向上回代。除法要求主元非零;即使原矩陣非奇異,原有行次序也可能產生零主元,此時交換行可能讓計算繼續。
例如
[0213][x1x2]=[15]原次序的第一主元為零。交換兩行後,方程是 2x1+3x2=5、x2=1,回代得 x1=x2=1。因此特定次序出現零主元本身並不代表矩陣奇異。
定義 3.1.2
(部分選主元與 PA=LU)
部分選主元法在當前列的主元行及其下各行中,選絕對值最大的元素,並把其行移到主元位置。若這些元素均為零,方陣必為奇異;非奇異方陣不會出現此情況。用置換矩陣 P 記錄換行,得到 PA=LU,其中 L 為對角線全為一的下三角矩陣,U 為上三角矩陣。先解 Ly=Pb,再解 Ux=y;多個右端可重用同一分解。
選大主元的原因之一是部分選主元法的消元乘數絕對值不超過一,減少一個誤差放大來源。但演算中的矩陣元素仍可能增長,病態問題亦仍對擾動敏感;選主元不是萬能的準確性保證。
殘差與誤差
設 A 非奇異,x 是 Ax=b 的精確解,x 是計算向量,其殘差為 r=b−Ax。對一個向量範數及與之相容的矩陣範數,A 的條件數為 κ(A)=∥A∥∥A−1∥。
因為 Ax=b,
A(x−x)=r,x−x=A−1r.
由範數相容性得 ∥x−x∥≤∥A−1∥∥r∥。若 b=0,結合 ∥b∥≤∥A∥∥x∥,可得
∥x∥∥x−x∥≤κ(A)∥b∥∥r∥,κ(A)=∥A∥∥A−1∥.
條件數、殘差和誤差必須使用相容的同一範數。此界可能偏鬆,但指出條件數大時,小相對殘差未必意味小相對誤差;此外上式假設殘差精確計算,實際計算的殘差本身也有捨入誤差。
具體反例:令 A=diag(1,10−6)、b=(1,10−6)T、x=(1,0)T。精確解為 (1,1)T,而 r=(0,10−6)T。無窮範數下相對殘差為 10−6,相對誤差卻是 1;κ∞(A)=106,上述界容許此情況。第二方程的絕對殘差雖小,對應解分量卻完全錯誤。
數據擾動
固定 A,將 b 改為 b+Δb,新解為 x+Δx。兩組方程相減得 AΔx=Δb。取範數並利用 ∥b∥≤∥A∥∥x∥,對 b=0 得
∥x∥∥Δx∥≤κ(A)∥b∥∥Δb∥.
這是容許任意方向擾動的最壞情況界,不代表每個擾動都被完整條件數放大。若 A 也受擾動,需要另一個界及確保擾動後矩陣非奇異的條件。改變單位會改變座標,也可能改變範數條件數,卻不會憑空為數據增添資訊。與其引用一個不說明範數及縮放的條件數,不如審視實際的測量不確定度與關心的變量。
另一個消元計算
例題 3.1.5
(2×2 系統的部分選主元)
取 A=[2413]、b=(5,13)T。由於 ∣4∣>∣2∣,部分選主元法先換行;第二行的乘數為 1/2,得到 4x+3y=13 和 −y/2=−3/2。回代得 y=3、x=1。相應分解為
P=[0110],L=[11/201],U=[403−1/2].直接相乘可驗證 LU=PA,同時檢查乘數及行次序。右端亦須置換;解 Ly=b 而非 Ly=Pb 會得到另一系統。求解時毋須明確計算 A−1,直接使用三角系統即可;逆矩陣則有助分析敏感度。
奇異例子 A=[1224] 的行相依。若 b=(1,2)T,有無限多個解滿足 x1+2x2=1;若 b=(1,3)T,兩式矛盾。奇異性因此可能意味解不唯一或無解,視右端而定;奇異矩陣沒有有限的普通逆矩陣條件數。
範數與矩陣擾動
誘導矩陣範數定義為 ∥A∥=v=0max∥Av∥/∥v∥,因此 ∥Av∥≤∥A∥∥v∥。無窮向量範數的誘導矩陣範數等於絕對行和的最大值。非奇異矩陣的條件數至少為一,因為 1=∥I∥=∥AA−1∥≤∥A∥∥A−1∥。在此範數意義下,一是最佳條件數;分量尺度或其他誤差度量仍可能呈現不同敏感度。
現在設矩陣與右端都改變,(A+E)(x+Δx)=b+Δb,其中 Ax=b 且 A 非奇異。整理得
(I+A−1E)Δx=A−1(Δb−Ex).
若 ∥A−1E∥<1,則 I+A−1E 可逆,且 ∥(I+A−1E)−1∥≤1/(1−∥A−1E∥)。因此擾動後的系統有唯一解,且對 b=0,
∥x∥∥Δx∥≤1−∥A−1E∥κ(A)(∥b∥∥Δb∥+∥A∥∥E∥).
證明
(先用 Neumann 級數,再用誤差恆等式)
令 F=−A−1E,則 ∥F∥<1。由於 ∥Fk∥≤∥F∥k,級數 k≥0∑Fk 的部分和構成 Cauchy 序列,故收斂到某個 S,且 ∥S∥≤k∑∥F∥k=1/(1−∥F∥)。相消求和給出 (I−F)k=0∑KFk=I−FK+1→I,因子次序相反時亦然,所以 S=(I+A−1E)−1。於是 A+E=A(I+A−1E) 是可逆矩陣之積,擾動後的系統有唯一解 x+Δx。
把 S 作用於整理後的恆等式,得
∥Δx∥≤1−∥A−1E∥∥A−1∥(∥Δb∥+∥E∥∥x∥).由 b=0 亦有 x=0。兩邊除以 ∥x∥,並把 ∥b∥≤∥A∥∥x∥ 寫成 ∥Δb∥/∥x∥≤∥A∥∥Δb∥/∥b∥。提出 ∥A∥∥A−1∥=κ(A) 便得所述的界。
證明透視
哪個假設確保擾動後仍可求解
論證有兩個不同任務。條件 ∥A−1E∥<1 先令 Neumann 級數收斂,從而確立擾動後的系統有唯一解。完成這一步,才可在誤差恆等式兩側乘以逆矩陣並估計範數。額外假設 b=0 是為了定義相對誤差的比值,並非可逆性所需。大條件數表示可容許數據誤差可能被放大,不代表解的代數恆等式失效。
分母十分重要:若擾動可以使矩陣奇異,就無法由此得到統一有限界。此條件充分而非必要,某些更大的擾動仍可保持可逆。這也解釋了即使右端精確,矩陣的不確定度仍會影響解。
反例模式
極小的相對擾動也可能令矩陣奇異
很容易想把假設換成「矩陣的相對擾動很小」。取 A=diag(1,10−6)、E=diag(0,−10−6)。在無窮範數下 ∥E∥/∥A∥=10−6,但 A+E=diag(1,0) 奇異,(A+E)y=(0,1)T 無解。定理的假設恰好不成立:A−1E=diag(0,−1) 的範數為一。正確的小量條件是 ∥A−1E∥<1;由於 ∥A−1E∥≤κ(A)∥E∥/∥A∥,條件 ∥E∥/∥A∥<1/κ(A) 足以保證它。
縮放例子
令 A=diag(1000,1)、b=(1000,1)T。解是 (1,1)T,而 κ∞(A)=1000。把第一條方程乘以 1/1000,矩陣變為單位矩陣,其無窮範數條件數為一。精確解沒有改變,但兩個新右端分量發生同樣大小絕對擾動的含義改變了。若原本以物理單位量度不確定度,必須隨方程一起轉換,然後才比較誤差界。縮放可改善數值行為,但原始測量仍限制準確度。
計算解的後向誤差
殘差也有後向解釋。給定 x 和 r=b−Ax,同一向量是 Ax=b−r 的精確解。因此 b=0 時,∥r∥/∥b∥ 衡量一個足以解釋結果的右端擾動。若也容許改變 A,它未必是最小後向誤差;當 A 和 b 的不確定度或單位不同時,這個區別尤其重要。
例如 A=[2112]、b=(3,3)T、x=(1,0.99)T,則 Ax=(2.99,2.98)T,r=(0.01,0.02)T。無窮範數下右端後向誤差為 0.02/3。精確解為 (1,1)T,相對前向誤差為 0.01。由 ∥A∥∞=3 及 ∥A−1∥∞=1,條件數為 3,殘差界給出至多 3(0.02/3)=0.02,與實際誤差一致。誤差界不必達到等號才有用。
消元為何保持方程組
交換方程、以非零數乘方程,以及把一條方程的倍數加到另一條,都是可逆行運算。對係數矩陣及右端同時運算,可保持解集。每個運算相當於左乘可逆基本矩陣;這些矩陣的乘積把 A 化成 U,整理乘積並記錄換行,便得到 PA=LU。次序十分重要:較後的換行也須反映在建構 L 所記錄的先前乘數中。
對角線非零的三角系統有唯一解:最後一條方程決定最後一個未知數,然後以歸納法逐個向上決定。若對角元素為零,普通回代公式不能除以它;須另行檢查是否相容及有否自由變量。軟件遇到奇異或數值困難時應報告,而非悄悄除以極小或零主元並聲稱結果可靠。
條件與算法品質
A=I 時,問題在任何誘導範數下都有最佳條件;但若算法故意返回 2b,誤差仍然很大。這說明良好條件本身不保證任意方法準確。相反,穩定求解病態系統可以得到小後向誤差,前向誤差卻大得多;當輸入數據不確定時,後者可能無法避免。區分兩者有助判斷應改善算法、取得更精確測量,還是改變問題的表述。
下面最後一題練習使用對角矩陣 A=diag(1,0.01),因此可以直接看出誤差方向及放大。b 的第二分量很小,絕對擾動 0.001 是該分量的十分之一;除以對應對角元素 0.01 後,解改變 0.1。範數相對殘差卻把 0.001 與 b 最大分量一比較,所以可能掩蓋某個分量的大相對擾動。當分量尺度不同時,逐分量分析可能更能反映測量模型。無論選用哪個尺度,都須清楚說明它如何對應實際數據。
常見錯誤
沿用選主元的 2×2 例子的因子,若解 Ly=b 而非 Ly=Pb,得 y=(5,21/2)T,再得 x=(17,−21)T。這個向量解的是 4x1+3x2=5、2x1+x2=13:A 的行已交換,右端卻保留原次序。只有先把 b 置換成 Pb=(13,5)T,才得到正確解 (1,3)T。
精確消元成立,浮點版本仍可能失敗。對 [ε111]x=(1,2)T,取 ε=10−20,精確解兩個分量與一的距離都小於 10−19。若不換行,二進制雙精度使用乘數 1020,把 1−1020 和 2−1020 都捨入為 −1020,得 x2=1,再得 x1=(1−1)/ε=0。部分選主元法先交換兩行,乘數變為 ε,在工作精度下兩個分量都是一。
總結
精確算術中,消元及回代可解非奇異方陣系統;部分選主元法選較大的可用主元,並以 P 記錄換行。重用分解 PA=LU 時,須把相同置換施於每個右端。有限算術中,即使精確消元有效,也須留意小主元、中間元素增長和捨入。
殘差顯示候選向量多接近滿足所寫方程,也提供右端後向誤差。條件數在指定範數下界定擾動對解的影響;小殘差配合大條件數,仍可能容許可觀的前向誤差。條件界描述最壞情況,並非預測每個誤差方向都被同樣放大。
比較兩個系統時,除矩陣和範數外,還應記錄單位與縮放。重新縮放方程會改變擾動的範數描述,卻不改變產生數據的物理測量。數據不確定時,賦予顯示位數意義之前,須先結合這些不確定度解讀數值結果。
練習
快速檢查
(消元求解 2x+y=5、4x+3y=13,並檢查殘差。)
解答 · 答案
第二式減第一式兩倍得 y=3,故 x=1;代入兩式均成立,殘差為零。
快速檢查
(求 A=diag(2,0.5) 的 κ∞(A)。)
計算 A 及 A−1 的行和。
解答 · 答案
無窮範數是絕對行和最大值:∥A∥∞=2,∥A−1∥∞=2,條件數為 4。
快速檢查
(若非奇異系統的計算向量在精確算術下殘差為零,可得甚麼結論?)
利用 A(x−x)=r。
解答 · 答案
由 A(x−x)=0 和非奇異性得 x=x。這要求精確零殘差;捨入後顯示零並不足以證明。
快速檢查
(對 A=diag(1,0.01)、b=(1,0.01)T,取 x=(1,0.9)T。求精確解、殘差、相對無窮範數殘差及相對無窮範數誤差,與條件數界比較;並說明為何殘差可視為僅擾動右端的後向誤差。)
解答 · 答案
精確解為 x=(1,1)T。因 Ax=(1,0.009)T,所以 r=(0,0.001)T;∥b∥∞=1,相對殘差為 0.001。誤差為 (0,0.1)T,相對無窮範數為 0.1。由 ∥A∥∞=1、∥A−1∥∞=100,條件數界為 100(0.001)=0.1,本例恰達等號。最後 Ax=b−r,故 x 精確地解了右端擾動 −r 後的系統。即使前向誤差是相對殘差的一百倍,這個後向結論仍然成立。