動機
數學模型常以方程作結,而不是直接給出答案。邊值問題離散化後可能得到大型稀疏線性系統 Ax=b;平衡模型則可能要求解非線性方程 F(x)=0。計算所得的近似值必須分別接受三個問題的檢驗:原問題是否有唯一解?算法在精確算術下是否收斂?有限精度如何影響結果?單憑殘差小,不能完整回答這些問題。
我們先研究可重用於不同右端項的矩陣分解,再透過誤差方程研究迭代,最後利用局部線性近似推導牛頓(Newton)法。雖然例子可以手算,這些區別對大型計算同樣重要。
定義
設 A∈Rn×n 可逆,真解為 x∗=A−1b,近似解為 x。誤差 e=x∗−x,殘差 r=b−Ax,因此 Ae=r。對任何誘導範數,∥e∥≤∥A−1∥∥r∥。若 b=0 且 x∗=0,則
∥x∗∥∥e∥≤κ(A)∥b∥∥r∥,κ(A)=∥A∥∥A−1∥.
即使不知道真解,我們仍能計算殘差;誤差一般不能直接計算。條件數描述問題對擾動的敏感程度,穩定性則描述算法。更換算法不會使本來病態的問題變得良態,但穩定方法可避免不必要的捨入誤差放大。
概念視角幾何
條件數作為到奇異矩陣的距離
在歐幾里得(Euclid)範數下,κ2(A)=σmax/σmin,即最大與最小奇異值之比。等價地,它的倒數是 A 到最近奇異矩陣的相對距離:
min{∥A∥2∥δA∥2:A+δA 奇異}=κ2(A)1.對 A=diag(1,ε),把 ε 換成 0 是大小為 ε=1/κ2(A) 的相對改變。病態矩陣就是只須很小的相對擾動便會變成奇異的矩陣。
主要結果
若 A∈Rn×n 的每個左上角主子矩陣均可逆,消元法給出唯一分解 A=LU,其中 L 是對角線為一的下三角矩陣,U 是上三角矩陣;每一步主元均非零。
每一步主元是相鄰左上角主子式之比,故假設保證除法合法。將消元乘數放在對角線下形成 L,逆轉消元操作即得 A=LU。若 LU=LU,則 L−1L=UU−1 同時是單位下三角和上三角矩陣,必為單位矩陣,所以分解唯一。
這定理並不表示浮點算術中不需要交換行。部分主元法在目前處理的列中選絕對值最大的元素交換至主元位置,得到 PA=LU。先用前代法解 Ly=Pb,再用回代法解 Ux=y。同一分解可處理多個右端項,通常不必顯式計算逆矩陣。
設 x(k+1)=Bx(k)+c 有固定點 x∗。從每個初值均收斂到 x∗,當且僅當譜半徑 ρ(B)<1。特別地,只要某個誘導範數滿足 ∥B∥<1,便足以保證收斂。
誤差滿足 e(k+1)=Be(k),故 e(k)=Bke(0)。Jordan 標準形顯示 Bk→0 當且僅當所有特徵值的絕對值小於一:Jordan 塊的冪由 k 的多項式乘特徵值的冪組成。反之,若 Bv=μv,v=0 且 ∣μ∣≥1,則 Bkv=μkv 不趨於零;若 v 是複向量,其實部或虛部便是一個不收斂的實初始誤差。範數條件則直接給出 ∥Bk∥≤∥B∥k→0。
證明透視
從仿射迭代到矩陣的冪
不動點方程 x∗=Bx∗+c 只用了一次,用來消去 c:誤差服從線性遞推 e(k)=Bke(0);由於 x(0) 任意,「從所有初值收斂」恰好等於 Bk→0。真正的工作在充分性。Jordan 塊 μI+N(N 冪零)的 k 次冪是 j∑(jk)μk−jNj,只有有限多項,每項都是 k 的多項式乘 μk−j;當 ∣μ∣<1,幾何衰減勝過多項式增長。必要性只需一個特徵向量,μ 為複數時再用取實部的技巧。範數條件完全繞過特徵值,所以只是充分條件:ρ(B)≤∥B∥。
若 A=D+L+U 的對角元素非零,Jacobi 迭代取 B=−D−1(L+U),c=D−1b。若每行嚴格對角佔優,B 每行絕對值和均小於一,因此 ∥B∥∞<1。這只是充分條件:例如 B=(0020) 的無窮範數為 2,但 B2=0,仍從所有初值收斂。
例題
令 A=(2413),第二行減第一行的兩倍,得到
L=(1201),U=(2011).當 b=(1,1)T,前代得 y=(1,−1)T,回代得 x=(1,−1)T。當 b=(3,7)T,同一分解給 y=(3,1)T 及 x=(1,1)T。直接相乘可核對兩個答案。
取 A=(4213)、b=(1,2)T。Jacobi 更新為 x1(k+1)=(1−x2(k))/4、x2(k+1)=(2−2x1(k))/3。由零向量開始,前兩步為 (1/4,2/3)T 和 (1/12,1/2)T。此處 ∥B∥∞=2/3,唯一固定點是 (1/10,3/5)T。幾何誤差上界不一定在每一步都取等號。
對 f(x)=x2−2,在非零 xk 處更新為 xk+1=(xk+2/xk)/2。從 x0=1 得 x1=3/2、x2=17/12。令 α=2;若 xk>0,則
xk+1−α=2xk(xk−α)2.接近 α 時,誤差大致每步平方。這是局部結論,並非對所有初值的保證。
方法與推理
牛頓法以 F(xk)+JF(xk)s 近似 F(xk+s),解 JF(xk)s=−F(xk),再令 xk+1=xk+s;應直接解線性系統,而非形成逆 Jacobian。純量情況下,當導數非零,更新為 xk+1=xk−f(xk)/f′(xk)。若 f 在根 α 附近二次連續可微且 f′(α)=0,連續性使附近的 ∣f′∣ 有正下界。Taylor 定理遂給 ∣ek+1∣≤C∣ek∣2;初值必須足夠接近,鄰域亦須選得使迭代留在其中。重根不滿足非零導數假設:f(x)=x2 給出 xk+1=xk/2,只有線性收斂。
即使函數光滑且根為單根,序列仍可失敗。f(x)=x3−2x+2 從 0 開始會到 1,再回到 0,形成循環。導數亦可能在到達根之前為零。阻尼或保持括區的方法可能有幫助,但其保證需要另外的假設。實用停止規則應檢查經尺度調整的殘差和最新修正量,並設迭代上限;線性求解失敗或無進展時應報告。修正量小亦可能只是停滯。
從殘差到可解釋的證據
關係式 Ae=r 有兩種讀法。第一,x 精確地解了右端受擾問題 Ax=b−r,故 ∥r∥/∥b∥ 是矩陣固定時的一種相對後向誤差。第二,原問題透過 A−1 把擾動映射成解的誤差;這便解釋了條件數上界。若同時允許矩陣與右端改變,必須另行指定後向誤差的定義。
例如 A=diag(1,ε),其中 0<ε<1,在二範數或無窮範數下有 κ(A)=1/ε。右端第二個分量擾動 δ,解的第二個分量便改變 δ/ε;即使方程精確求解,這也是模型本身的敏感性。第一個分量的擾動卻不被放大,因此條件數是最壞情況上界,不必準確預測每次擾動。
主元與運算量
取 Aε=(ε111),其中 ε 非零且很小。不交換行便會使用乘數 1/ε,產生 1−1/ε;浮點計算中,大的中間值可能在回代時造成消去誤差。先交換兩行則主元絕對值為一,避免這次小除數。當 ε=1,矩陣可逆,所以這是數值問題,不是不存在解的證明。
稠密 n×n 消元約需 n3 階運算,其後每次三角求解約需 n2 階。固定矩陣配多個載荷時,重用分解很重要。稀疏消元可能產生原來為零的新元素,稱為填充;成本與儲存還依賴排序。部分主元法改善實用穩健性,卻不能保證病態問題一定有小前向誤差。
Jacobi 與順序更新
Jacobi 每個新分量都取自舊向量;Gauss–Seidel 立即使用已算出的新分量。當 A=D+L+U,其方程為 (D+L)x(k+1)=b−Ux(k)。左側是對角非零的下三角系統,用前代法即可,無須求逆。其迭代矩陣為 −(D+L)−1U,同一譜半徑準則適用,但收斂因子一般不同。
對前述矩陣從零開始,第一分量先得 1/4,立即代入第二分量得 (2−2(1/4))/3=1/2。第一步為 (1/4,1/2),不同於 Jacobi 的 (1/4,2/3)。這個例子不能證明哪一方法永遠較快;收斂、排序、平行性及成本都取決於具體問題。
若已知 ∥B∥≤q<1,對 k≥1,幾何級數尾和給出事後上界 ∥x∗−x(k)∥≤q∥x(k)−x(k−1)∥/(1−q)。因每一步之差至多是上一步的 q 倍,把其後差值相加即可。此證書依賴已知收縮上界;只觀察到一步很小並不足夠。
牛頓法的局部估計
選好鄰域之後,上一節的局部說法便成為定理。
設 f 在包含根 α 的開區間上二次連續可微,且 f′(α)=0。設 ρ>0 使得在 I=[α−ρ,α+ρ] 上 ∣f′∣≥m>0、∣f′′∣≤M,並令 C=M/(2m)。若 C=0,令 δ=ρ;否則令 δ=min(ρ,1/(2C))。若 ∣x0−α∣≤δ,則每個牛頓迭代值都有定義、都屬於 I,並滿足
∣xk+1−α∣≤C∣xk−α∣2≤21∣xk−α∣.特別地,xk→α。
這樣的 ρ 存在:f′ 連續且 f′(α)=0,所以在 α 附近某個小閉區間上 ∣f′∣≥∣f′(α)∣/2,而連續函數 f′′ 在該區間上有界。設 ∣xk−α∣≤δ,則 xk∈I,故 f′(xk)=0,xk+1=xk−f(xk)/f′(xk) 有定義。在 xk 處用泰勒定理,存在介於 xk 與 α 之間(因而屬於 I)的 ξ,使
0=f(α)=f(xk)+f′(xk)(α−xk)+21f′′(ξ)(α−xk)2.除以 f′(xk) 並代入更新式,得
xk+1−α=2f′(xk)f′′(ξ)(xk−α)2,因此 ∣xk+1−α∣≤C∣xk−α∣2≤Cδ∣xk−α∣≤21∣xk−α∣,特別是 ∣xk+1−α∣≤δ。由 k=0 起歸納,可知所有迭代值都留在 I 內,誤差每步至少減半,而二次界始終成立。
證明透視
哪個假設使迭代留在好區域內
假設 f′(α)=0 只透過下界 m 進入證明,並用了兩次:一次使更新式有定義,一次出現在誤差恆等式的分母。f′′ 的界 M 控制泰勒餘項。展開在 xk 處進行、在 α 處取值,而不是在 xk+1 處,所以恆等式只涉及目前的誤差。
不明顯的一步是選取 δ≤1/(2C)。單有二次界並不能阻止迭代值離開 I,而在 I 外 m 與 M 不再適用;因子 Cδ≤21 把二次界變成收縮 ∣xk+1−α∣≤21∣xk−α∣,歸納正是靠這個收縮才得以完成。對 f(x)=x2 的重根,在 0 附近任何區間上都找不到下界 m;迭代 xk+1=xk/2 仍然收斂,但只是線性收斂。沒有這些界時,切線可能指向遠處或近乎水平。
矩陣的擾動
右端項的擾動只是不確定性的一個來源。設 x 解 Ax=b,而 x+δx 解 (A+δA)(x+δx)=b+δb。兩式相減得
Aδx=δb−δA(x+δx).
若 ∥A−1∥∥δA∥<1,由三角不等式及誘導範數的界可得
∥δx∥≤1−∥A−1∥∥δA∥∥A−1∥(∥δb∥+∥δA∥∥x∥).
此界假設受擾解存在;嚴格不等式亦透過 (I+A−1δA)−1 的收斂 Neumann 級數保證受擾矩陣可逆。它顯示相對誤差同時取決於數據擾動與條件數。分母接近零時,上界可能很弱,但這並不證明實際擾動已造成大誤差。
二元牛頓系統
取 F(x,y)=(x2+y2−5,x−y−1)T,其 Jacobian 為 J=(2x12y−1)。從 (x0,y0)=(2,0) 出發,殘差為 (−1,1)T。解 Js=(1,−1)T:第一條方程給 s1=1/4,第二條給 s2=5/4,所以下一點是 (9/4,5/4)。Jacobian 行列式是 −2(x+y),在直線 x+y=0 上該步無法定義。根 (2,1) 存在,但單憑根的存在並不保證任意初值收斂。實際計算中若內層線性求解是近似的,亦應檢查線性系統的殘差。
殘差與停止規則的限制
在大型問題中,計算精確解以檢查誤差通常與原問題一樣困難,因此殘差是可計算的證據。然而殘差大小要與數據尺度一起解讀:若把整個方程乘以一個很小的常數,真解不變,絕對殘差卻同樣縮小。相對殘差在右端非零時較有意義,但仍要結合條件數;當右端為零或不同方程具有不同物理單位,應另選適當尺度。停止時同時記錄迭代次數、殘差和最新修正量,有助分辨收斂與停滯。有限精度下計算所得的殘差本身亦受捨入影響,因此到達捨入水平附近後不能期待持續改善。
常見誤解
消元與迭代中有兩個常見錯誤。
矩陣 (0110) 可逆(它就是自己的逆),但普通消元一開始就停下,因為第一個主元為零。LU 定理的假設針對左上角主子矩陣,而不是可逆性;一次行交換給出 PA=LU,便可處理這個矩陣。
取 B=diag(1/2,2)、c=0。初值 x(0)=(1,0)T 收斂到固定點 0,但 (0,1)T 每步加倍。譜半徑定理說的是每一個初值;一次成功的計算只檢驗了其初始誤差中出現的分量。
殘差小也不一定表示誤差小;尺度與條件數都有影響,下例把失敗具體化。
反例模式
微小殘差可掩蓋一個單位的誤差
錯誤說法是絕對殘差小於 10−8 必定使誤差小於 10−8。取 A=diag(1,10−10)、b=(1,0)T、x=(1,1)T,殘差範數是 10−10,誤差範數卻為 1。修正後須使用 ∥e∥≤∥A−1∥∥r∥,不能省略很大的逆矩陣範數。方程單位改變也能改變絕對殘差,故應考慮相對、配合問題的容差。
快速檢查
快速檢查
(若 ∥B∥∞=0.4,初始誤差的無窮範數不大於 5,則 x(k+1)=Bx(k)+c 三步後的誤差有甚麼上界?)
利用 e(k)=Bke(0) 及誘導範數的次乘性。
解答 · 答案
∥e(3)∥∞≤∥B∥∞3∥e(0)∥∞≤0.43⋅5=0.32。這是保證上界,而非必然的實際誤差。
習題
練習 1.1.8
(將 (3614) 分解為 LU,其中 L 對角線為一,並解 b=(4,10)T。)
解答 · 答案
消元乘數為 6/3=2,故 L=(1201),U=(3012)。前代得 y=(4,10−2⋅4)T=(4,2)T;回代得 x2=1 及 3x1+1=4,因此 x=(1,1)T。驗算:(3+1,6+4)T=(4,10)T。
練習 1.1.9
(求 B=(01/91/40) 的譜半徑。迭代 x(k+1)=Bx(k)+c 是否從每個初值收斂?)
解答 · 答案
特徵多項式為 λ2−1/36,特徵值為 ±1/6。譜半徑 1/6<1,故從每個初值都收斂。
練習 1.1.10
(對 f(x)=x2−3,從 x0=2 作兩步牛頓迭代。)
解答 · 答案
更新式為 xk+1=(xk+3/xk)/2。於是 x1=(2+3/2)/2=7/4,x2=(7/4+12/7)/2=97/56≈1.73214,而 3≈1.73205。迭代值非零,兩次除法均合法。
練習 1.1.11
(令 A=diag(1,10−6)、b=(1,0)T、x=(1,1)T。求殘差與誤差的無窮範數,並解釋兩者的差距。)
解答 · 答案
真解為 x∗=(1,0)T,r=b−Ax=(0,−10−6)T,e=x∗−x=(0,−1)T,範數分別為 10−6 和 1。由於 ∥A−1∥∞=106,界 ∥e∥≤∥A−1∥∥r∥ 恰好取到:逆矩陣將第二座標放大 106 倍。
延伸學習
稀疏儲存、主元增長、後向誤差、非線性系統及預處理 Krylov 方法都需要進一步假設與分析;這些小例子不足以證明實際求解器穩定。