動機
數值答案由有限數據及有限次運算得到。推導精確公式後,我們仍須問:輸入如何表示?運算每一步的捨入會有甚麼影響?條件描述數學問題對數據擾動的敏感度;穩定性則描述算法引入的誤差。兩者是不同的問題。
表示與誤差
以 β 為底、保留 t 位有效數字的正規化非零浮點數可寫作
±(d0.d1⋯dt−1)ββe,1≤d0<β,0≤di<β.
指數範圍有限。實際機器亦有零,還可能有次正規數、無窮大和特殊值;此簡化模型並非完整的機器規格。數的量級愈大,相鄰可表示數的間距亦愈大。
十進制保留三位有效數字、取最接近值時,1.234 捨入為 1.23,而 1234 捨入為 1230。兩個絕對誤差 0.004 與 4 相差一千倍,相對誤差卻都約為 3.2×10−3,低於下文定義的單位捨入誤差 21⋅10−2。
定義 1.1.3
(絕對誤差、相對誤差與單位捨入誤差)
精確值 x 與近似值 x 的絕對誤差為 ∣x−x∣;若 x=0,相對誤差為 ∣x−x∣/∣x∣。接近零時,絕對誤差更有意義,因相對誤差在零處沒有定義。遠離溢出與下溢時,取最近值可用標準模型
fl(x)=x(1+δ),∣δ∣≤u=21β1−t.
這是一次捨入的界,並不代表整個多步計算的相對誤差也不超過 u;下溢時亦未必適用。
問題的敏感度
設 f 在 x=0 可微,且 f(x)=0。對小擾動 Δx,微分給出一階近似
∣f(x)∣∣f(x+Δx)−f(x)∣≈f(x)xf′(x)∣x∣∣Δx∣.係數 κf(x)=∣xf′(x)/f(x)∣ 是局部相對條件數。
它依賴問題、輸入和誤差尺度,並非任意大擾動的統一保證。若輸出為零,應改用合適的絕對誤差尺度。
概念視角幾何
條件數是對數座標下的斜率
寫 X=log∣x∣、Y=log∣f(x)∣。在 f 可微且不為零之處,鏈式法則給出 dY/dX=xf′(x)/f(x),所以 κf(x)=∣dY/dX∣。在一階近似下,相對變化就是對數之差,因此相對誤差與這個斜率自然配對。對 x,雙對數圖是斜率 1/2 的直線;對 x−1,在 x=1 附近斜率無界,那裏 log∣f∣→−∞。
對 f(x)=x、x>0,條件數為 1/2,故小的相對輸入變化約產生一半大小的相對輸出變化。相反,f(x)=x−1 的條件數 ∣x/(x−1)∣ 在 x 趨近 1 時無界。若輸入已經捨入,改寫減法也不能找回失去的數據。
消去與穩定公式
當 x 很小且為正時,g(x)=1+x−1 是兩個相近數的差,可能暴露運算元已有的捨入誤差。有理化得到完全相等的公式
g(x)=1+x+1x,
它避免相近數相減。
在每步均捨入至四位有效十進制數的模型中,取 x=0.0001,1+x 捨入為 1.000,第一公式得到零;第二公式的分母捨入為 2.000,結果為 0.00005000,接近精確值 0.00004999875…。實際硬件的運算規則可能不同。
消去本身並不必然產生誤差:若兩個運算元均精確表示,相減本身也可能精確。危險是小差值凸顯原有誤差。殘差小亦不能單獨保證病態問題的答案準確。
前向及後向誤差
定義 1.1.7
(前向誤差、後向誤差與後向穩定性)
對數據 d、精確答案 F(d) 和計算答案 y,前向誤差比較 y 與 F(d);後向誤差尋找使 y=F(d+Δd) 的小數據擾動。後向穩定算法的答案是附近數據的精確解,「附近」相對於指定的數據量度而言。
後向穩定性配合良好條件,才可得到有用的前向誤差界;單靠其中一項,並不能在所有情況下保證準確。
設 x>0,並設算法返回 y=x+Δx,其中 x+Δx≥0。則
x∣y−x∣=1+Δx/x+1∣Δx∣/x.特別地,若 ∣Δx∣/x≤ε≤1,相對前向誤差至多為 ε/(1+1−ε);當 ε 很小時,此值約為 ε/2。
記 r=Δx/x,則 r≥−1,且 y/x=1+r。於是
1+r−1=1+r+1∣(1+r)−1∣=1+r+1∣r∣.若 ∣r∣≤ε≤1,分子至多為 ε,分母至少為 1+1−ε,即得所述界。恆等式同時展示了一階近似忽略的部分:因子 1/(1+r+1) 只在 r=0 時等於 1/2。
因子 1/2 正是平方根的條件數。這是一般規律的縮影:在一階意義下,前向誤差至多為條件數乘以後向誤差。
誤差累積與運算次序
即使每個運算各自只有小相對誤差,多步運算也會累積誤差。若 n 次運算各貢獻因子 1+δi,其中 ∣δi∣≤u,則因子之積與一之差至多為 (1+u)n−1;當 nu 很小,此值約為 nu。這是該乘積的最壞情況界,不能直接當成包含加法及消去的任意算法之誤差界。
例如用三位有效十進制數求 1+0.004+0.004。先加兩個小數得 0.008,再加 1 並捨入得 1.01;逐一加到 1,每一步均捨入至 1.00。兩者都不等於精確和 1.008,但次序改變了損失。長和中把量級相近的數分組可能有幫助,效果仍依賴符號及數據,沒有一種次序可消除所有誤差。精確的數學和與次序無關,浮點計算過程則不然。
分析計算時應分別記下精確問題、實際儲存的數據、運算及捨入模型,以及輸出誤差尺度,從而把模型誤差與表示誤差、算法誤差區分開來。增加位數有助減少捨入,卻不能修正錯誤的測量或模型,也不改變問題本身的條件數。
擾動區間與測量
假設溫度計讀數 x=100,已知絕對不確定度不超過 0.1,相對輸入不確定度至多為 10−3。對倒數 f(x)=1/x,單調性給出嚴格輸出區間 [1/100.1,1/99.9]。條件數 1 則只預測小擾動下相對輸出不確定度約為 10−3。區間包含非線性餘項,可提供具體保證;條件數提供局部估計。兩者回答的問題不同。
有多個輸入時,條件數需要指定共同擾動尺度。對減法 s(a,b)=a−b,若 ∣Δa∣≤ε∣a∣ 且 ∣Δb∣≤ε∣b∣,三角不等式給出
∣Δs∣=∣Δa−Δb∣≤ε(∣a∣+∣b∣).
當 a=b,相對輸出誤差至多為 ε(∣a∣+∣b∣)/∣a−b∣。兩數相近時此界可能很大,它描述獨立擾動兩個運算元的敏感度;把它們的差看成一個已知輸入則是另一問題。必須說明數據是甚麼,才能有意義地談條件。
例如 a=1.0001、b=1.0000,各有獨立的 0.00005 絕對不確定度時,真差可介乎零及 0.0002,而名義差為 0.0001,所以絕對不確定度是名義差的 100%。若以真差為分母,相對誤差可以任意大;真差為零時則沒有定義。後續減法多保留數位,不能重建未知真值;如果運算元本來精確且精確儲存,就沒有這個測量不確定度。
捨入界的推導
在指數範圍不受限制的理想正規化模型中,設實數 x=0,而 fl(x) 是與 x 最接近的浮點數。則 fl(x)=x(1+δ),其中 ∣δ∣≤u=21β1−t。
在區間 [βe,βe+1) 內,相鄰數間距為 βe−t+1。捨入至最近值的絕對誤差不超過半個間距;由於區間內的數至少為 βe,相對誤差不超過 21β1−t。這證明正數的一次捨入界,負數由對稱性得到。在邊界附近間距改變,但所述理想模型的同一界仍成立。兩個最近值等距時須指定選擇規則;任選其一仍符合此界。
指數範圍有限時,模型在極端值處須額外處理:溢出沒有附近的有限正規化數,次正規數的間距固定,並不與量級成比例。故基於 ∣δ∣≤u 的證明須排除這些情況或另行處理。
反例模式
次正規數打破相對誤差界
斷言:指數範圍內的每個非零實數,捨入後的相對誤差都不超過 u。在 IEEE binary64 中,u=2−53≈1.1×10−16,最小的正次正規數是 2−1074,而零附近的次正規數間距為 2−1074。實數 x=3⋅2−1075 恰好位於 2−1074 與 2−1073 的正中,取偶捨入選出 2−1073。相對誤差為
3⋅2−10752−1073−3⋅2−1075=34−3=31,是 u 的 1015 倍以上。補救正是命題中已有的假設:相對誤差界只對正規化結果成立。在次正規範圍內,改為成立的是絕對誤差界 ∣fl(x)−x∣≤2−1075,即固定間距的一半。
二次方程根的表示
當 a=0 且 b2−4ac≥0,二次方程 ax2+bx+c=0 有實根。若直接計算兩個分子 −b±b2−4ac,其中一個可能是相近數之差而損失準確度。例如 a=1、b=−10000、c=1,小根為 (10000−99999996)/2,相減消去大部分前導數位。兩根之積為 c/a=1,因此先用相加的分子計算大根,再取其倒數得到小根。精確算術中兩種方法相同;浮點計算中後者避免了這次消去。
一般而言,當 b=0,可令 q=−21(b+sign(b)b2−4ac),在 q=0 時計算 q/a 和 c/q。b=0、q=0、重根及非實根等特殊情況須另行處理。形成判別式時仍可能溢出或嚴重消去;接近重根時,根本身對係數變化十分敏感,改寫算法不能消除所有困難。
如何理解顯示的數位
計算程序顯示 1.4142135623,並不證明每個數位都正確。可信的報告需要誤差界、配合敏感度數據的已驗證殘差,或其他有理據的誤差估計。先驗證區間再按所需位數捨入,比沒有依據地列出長小數更可靠。兩個算法的答案高度一致是有用證據,但若它們共用有偏差的輸入或不穩定步驟,一致仍不是證明。
不同誤差來源應分開追蹤。若模型使用測量參數,數值結果可能準確地對應那些參數,而參數本身仍偏離現實。減少算術誤差的細化實驗不能消除模型或測量誤差;誤差分析的目的,是判斷哪一項不確定度主導結論及結論所能支持的精度。
總結
數值分析首先確定數據及誤差尺度。浮點模型界定每次正常捨入;條件衡量數學映射對數據的敏感度。後向誤差問解的是哪個附近問題,前向誤差則衡量答案的差距。誤差模型的假設成立時,對條件良好的問題使用後向穩定算法,通常可得到小前向誤差。
即使代數上完全等價的改寫也須放在情境中判斷。有理化避免相近數相減,卻可能在其他步驟造成溢出;高精度計算也可能準確地解了記錄錯誤的數據。一份有用的結果報告應說明數據尺度、可能受擾動的量,以及有多少位數受到證據支持,而非混淆儲存精度與測量的確定性。
練習
快速檢查
(求 f(x)=1/x(x=0)的相對條件數並解釋。)
計算 xf′(x)/f(x)。
解答 · 答案
f′(x)=−1/x2,故條件數為 1:小相對擾動產生約同樣大小的相對輸出變化。
快速檢查
(用每步捨入至三位有效十進制數,計算 (100+0.4)−100 和 100+(0.4−100)。結果說明了甚麼?)
解答 · 答案
前者的和捨入為 100,結果為 0;後者括號為 −99.6,結果為 0.4。浮點加法不遵守實數加法的結合律。
快速檢查
(為大正數 x 改寫 x2+1−x,避免相近數相減。)
同乘及同除以 x2+1+x。
解答 · 答案
乘以共軛式得到 1/(x2+1+x)。實作時仍須防止極大 x 的 x2 溢出。
快速檢查
(正量的測量值為 10,絕對不確定度至多 0.01。用區間界定其平方,並與條件數的一階估計比較;解釋為何區間的結論較強。)
解答 · 答案
輸入落於 [9.99,10.01],故平方落於 [99.8001,100.2001]。名義輸出為 100,最大絕對偏差是 0.2001。f(x)=x2 的相對條件數為 2;相對輸入不確定度 0.001 預測相對輸出不確定度約 0.002,即絕對變化約 0.2。區間包括二次項,提供嚴格界而非僅為一階估計。