有限機器中的數
數學上的實數可能需要無限位數字才能表示。計算機格式只能儲存有限位,因此即使是簡短計算也可能混合兩種不同的偏差來源:數據在表示時可能改變,此後的每次運算也可能將結果捨入。為了理解答案,必須說明哪個問題是精確的,以及哪些運算是近似的。
以下例子採用捨入到最近值;正好處於中間時,選擇有效數字最後一位為偶數的可表示值。這是針對所述格式的理想化規則;實際軟件還涉及精度、中間運算、下溢、上溢和特殊值的選擇。下文分析不保證每個編程環境都以同樣方式計算表達式。
表示與局部捨入模型
基數為 β、精度為 p 的規格化浮點數形如
±(d0.d1⋯dp−1)ββe,1≤d0<β,0≤dj<β,其中各數字和指數是整數,指數在格式允許的範圍內。零另行表示。固定 e 時,相鄰有效數字的間距為 βe−p+1。
間距隨數量級改變。有限指數範圍還導致上溢;系統對極小的數可能使用次正規數。邊界情況很重要,但下述簡單相對誤差模型不能自動涵蓋它們。
採用捨入到最近值時,單位捨入誤差為 u=21β1−p。對基本運算 ∘,若其精確結果有定義且處於正規範圍,捨入模型為
fl(a∘b)=(a∘b)(1+δ),∣δ∣≤u.該模型把計算出的運算與對所提供操作數作精確運算的結果比較。如果操作數已經近似其他量,還須另行計算它們的誤差。當精確結果為零時,相對表達式需要單獨理解;在通常模型中,精確零被表示為零。
若非零實數 z 的捨入結果處於正規範圍,且沒有上溢或下溢使估計失效,則
fl(z)=z(1+δ),∣δ∣≤u=21β1−p.
取 e 使 βe≤∣z∣<βe+1。在這個數量級區間內,可表示數的間距為 βe−p+1,捨入到最近值至多把 z 移動半個間距,即 21βe−p+1。由於 ∣z∣≥βe,相對改變至多為 21βe−p+1/βe=21β1−p=u。
基數為二、p=3 時,1 與 2 之間的正規數為 1、1.25、1.5、1.75,且 u=1/8。1.125 正好位於 1.002 與 1.012 中間;中點取偶規則將它捨入為 1.002=1。相對誤差為 (1−1.125)/1.125=−1/9,其絕對值不超過 u。下一個數 1.25 可被精確表示,誤差為零。u 是正規捨入的最壞情況保證,並不是每個數的實際誤差。
快速檢查
(在基數二、p=3 的格式中,將 1.375 按最近值、中點取偶規則捨入。求相對捨入誤差,並與 u 比較。)
解答 · 答案
1.375 正好位於 1.012=1.25 和 1.102=1.5 中間。後者末位為偶,故捨入為 1.5。相對誤差為 (1.5−1.375)/1.375=1/11<1/8=u。
前向誤差、後向誤差與條件性
設問題把數據 d 映為精確結果 F(d),算法返回 y。前向誤差為 y−F(d);當 ∥F(d)∥ 非零時,除以它可得相對前向誤差。後向誤差則問:輸入至少需要改變多少,才能使 y=F(d+Δd) 精確成立?其數值取決於哪些數據允許擾動及如何衡量擾動。
後向誤差小說明答案解的是鄰近問題;它本身並不說明鄰近問題的答案也相近。
設 A 非奇異且固定,b=0,且只允許擾動 b。對計算解 x,殘差為 r=b−Ax,使 x 精確成立的右端項改變唯一,為 Δb=−r,相對大小為 ∥r∥/∥b∥。在誘導範數下,精確解 x 滿足
∥x∥∥x−x∥≤∥A∥∥A−1∥∥b∥∥r∥.
由 Ax=b−r 得 Δb=−r;A 可逆,所以這是唯一選擇。其次,x−x=A−1r 給出 ∥x−x∥≤∥A−1∥∥r∥,而 ∥b∥=∥Ax∥≤∥A∥∥x∥ 給出 ∥x∥≥∥b∥/∥A∥。把前一個界除以後一個界,即得所述不等式。
因此在此擾動模型下,即使後向誤差很小,也可能被很大的條件數放大。若同時允許擾動 A,後向誤差的定義和數值便會改變;上述殘差比不自動等於更寬模型中的最小值。
看到 ∥r∥/∥b∥ 很小,就接受 x,是很誘人的做法。但上面的命題顯示,x 的相對誤差仍可能達到該殘差比的 ∥A∥∥A−1∥ 倍。判斷答案是否可靠,要同時看殘差和問題的條件性。
快速檢查
(對 A=diag(1,10−6)、b=(1,10−6)T 和 x=(1,0)T,求殘差、精確解,以及只允許改變 b 時以無窮範數衡量的後向誤差。)
解答 · 答案
r=(0,10−6)T,x=(1,1)T。唯一允許的改變是 Δb=−r,故相對後向誤差為 ∥r∥∞/∥b∥∞=10−6;但相對無窮範數前向誤差為一。
若有限維賦範空間之間的映射 F 在非零點 d 可微且 F(d)=0,則局部相對條件數為 ∥DF(d)∥∥d∥/∥F(d)∥,其中使用誘導算子範數。
條件性屬於問題本身。 它衡量精確輸入的微小改變使精確輸出發生多大變化。它描述一階敏感性,依賴輸入、範數及容許的擾動;它不是算法造成的誤差。
對純量減法 F(a,b)=a−b=0,設 a=a(1+δa)、b=b(1+δb),且 ∣δa∣,∣δb∣≤u。即使隨後精確計算兩者的差,也有
∣a−b∣∣(a−b)−(a−b)∣≤u∣a−b∣∣a∣+∣b∣.
相減得 (a−b)−(a−b)=aδa−bδb,其絕對值至多為 u(∣a∣+∣b∣)。再除以 ∣a−b∣ 即可。
當 a 與 b 很接近時,右側的比值可能很大。這是減法對輸入相對擾動的敏感性,並不意味著對兩個已儲存操作數執行減法時,該運算本身必然產生很大的相對捨入誤差。消去會暴露已有誤差;辨認其來源需要追蹤整個計算過程。
消去與代數等價公式
考慮捨入到三位有效數字的十進制運算。精確輸入 a=1234 和 b=1233 均捨入為 1230。精確相減儲存值所得為零,原始輸入之差卻為一。損失發生在輸入捨入時;其後的儲存值相減是精確的。最終答案多列印幾位並不能恢復原始數據中已經丟失的數字。
快速檢查
(在三位有效數字十進制運算中,先分別捨入 a=1234 和 b=1233,然後相減。求計算差和精確差。此例是否說明兩個儲存操作數相減不準確?)
解答 · 答案
兩個輸入都捨入為 1230,故計算差為零,原始差為一。兩個儲存值的減法是精確的;偏差由輸入捨入造成。
兩個非常接近的數相減後,結果失去全部有效數字,此時減法本身通常是精確的。出錯的是更早的步驟:操作數在捨入或計算時已帶有誤差。減法的敏感度界說明了這些早先的誤差為何變得可見,卻沒有指出是哪一步運算造成了它們。
公式也可能在計算內部產生類似困難。對 x>0,以下兩個表達式在實數運算中相等:
x2+1−x=x2+1+x1.
x 很大時,第一個表達式相減的兩個正數非常接近;第二個避免了相減。
反例模式
代數上相等的公式可以算出不同的值
命題:在實數運算中相等的兩個表達式,在浮點運算中也返回同一個值。在 IEEE 754 binary64 捨入到最近值的運算中,取可精確表示的輸入 x=108,並分別計算各基本運算。此時 x2=1016 精確成立,而 fl(x2+1)=1016:增量落在該處相鄰 binary64 數的中點,取偶選擇 1016。直接公式 x2+1−x 於是得到 108−108=0,儘管精確值為正且約等於 5×10−9。在此例中,有理化公式給出有用的非零近似。此比較假設所示運算順序,且沒有融合運算或編譯器重新組合;它不能證明有理化公式對所有 x 都安全,因為 x2 本身可能上溢。
在每步分別捨入的 binary64 運算中,(1016+(−1016))+1=1,但 1016+((−1016)+1)=0。在第二個表達式中,−1016+1 不可表示:1016 附近的數相隔 2,而 −1016 與 −1016+2 之間的平局取偶選擇有效數字為偶的 −1016,所以內層和被捨入回 −1016。兩種括號的精確實數和都是一。因此運算順序是算法規格的一部分。
穩定性屬於算法
非正式地說,對於指定問題和輸入模型,如果算法的計算結果是某個鄰近輸入的精確答案,並且相對於數據的擾動有受控的小上界,就稱算法後向穩定。「鄰近」必須通過範數、允許的擾動以及依賴精度和問題規模的界來說明。
穩定性定理可能只在特定輸入和中間值範圍條件下成立。穩定性並不意味著每個計算數字都準確:病態問題可能放大很小的後向誤差;反之,條件良好的問題也可能被不穩定算法算壞。
設 sn=i=1∑nxi 從可表示的輸入出發,令 s1=x1 後按給定次序逐次相加,n≥2;每個非零精確運算 sk−1+xk 都滿足同一 u 的相對捨入模型,並且沒有上溢或下溢。若 (n−1)u<1,則
∣sn−sn∣≤γn−1i=1∑n∣xi∣,γk=1−kuku.此外 sn=i∑(xi+Δxi),其中 ∣Δxi∣≤γn−1∣xi∣。
展開遞推式:每個 xi 都乘上至多 n−1 個因子 1+δj 的乘積。對 k≤n−1,此乘積與一之差的絕對值至多為 (1+u)k−1≤ku/(1−ku)。三角不等式給出上述界。精確為零的中間和沒有捨入誤差,可單獨處理。同一展開也將 sn 寫為 i∑(xi+Δxi),這是關於求和輸入的逐分量後向誤差結論。
證明透視
把每個誤差記到輸入上
每次加法帶來一個因子 1+δj,所以把遞推展開後,x1 和 x2 各乘上 n−1 個這樣的因子,x3 乘上 n−2 個,xn 只乘上一個。這種記賬方式才是關鍵想法:誤差記在輸入上而不是部分和上,於是自然得到 xi+Δxi 這種後向形式。捨入模型(連同範圍假設)每次加法用一次;(n−1)u<1 只是使 γn−1 有限。前向界其後只需三角不等式,而因為它含有 ∑∣xi∣,精確和中的抵消在其中看不出來。
上式是絕對前向誤差界。若真實和相比 ∑∣xi∣ 很接近零,該界可能允許很大的相對誤差;它不能保證有消去的求和仍保留準確數字。
快速檢查
(在逐次求和的捨入模型下,寫出四個數的絕對誤差界,並解釋為何它不一定給出小的相對誤差界。)
解答 · 答案
若 3u<1 且滿足所述範圍條件,界為 γ3i=1∑4∣xi∣,其中 γ3=3u/(1−3u)。精確和相對於各項絕對值之和可以任意小,故除以精確和的絕對值可能得到很大的界;精確和為零時,相對誤差甚至無定義。
1 的相鄰浮點數及其不對稱性
假設。 採用規格化二進制格式,精度 p≥2(含首位),指數 0 與 −1 均可用,捨入方式為就近捨入、平局取偶。不考慮範圍限制,以下內容不涉及次正規數或溢出。
在此格式中,1 的後繼是 1+21−p,前驅是 1−2−p。1 下方的間隙是上方間隙的一半。
區間 [1,2) 內的數形如 1.b1b2…bp−1×20。最後一位小數位改變一個單位,數值改變 21−p,所以 1 之後的下一個數是 1+21−p。
區間 [1/2,1) 內的數形如 1.b1…bp−1×2−1,間距為 21−p⋅2−1=2−p。其中最大者的有效數字各位全為 1,即 1−2−p。所以 1 下方的間隙為 2−p,是上方間隙的一半。
本文記 ε間隙=21−p 為 1 上方的間隙。它與單位捨入誤差 u=2−p 不同,後者是前者的一半。不同作者用「機器精度」(machine epsilon)指這兩個量中的任何一個,因此使用前必須明確定義。
把函數庫中名為「epsilon」的常數當作單位捨入誤差 u 使用,會使本文每個估計中的誤差界加倍。代入數值前,先確認來源所指的是 1 上方的間隙(21−p),還是相對捨入誤差的上界(2−p)。
對 binary64,p=53。1 的相鄰數為 1−2−53 與 1+2−52,且 u=2−53。
1 上方的中點是 1+2−53。一個候選是 1,其有效數字末位為 0(偶);另一個是 1+2−52,末位為 1(奇)。平局取偶選 1。1 下方的中點是 1−2−54,候選為 1−2−53(53 個 1,奇)與 1(偶),結果仍為 1。下方的平局點距 1 只有 2−54,是上方平局點距離的一半。
上述平局針對的是對一個給定的精確實數進行捨入。在運算中,操作數本身已是浮點數,只有每次運算的精確結果會被捨入。由於 2−53 可表示,fl(1+2−53)=1。因此由左至右計算 (1+2−53)+2−53 得到 1,儘管 1+2−52 本身可以表示。
快速檢查
(取 p=4,求 1 的相鄰浮點數和 u,並將精確中點 1+1/16 和 1−1/32 捨入。)
解答 · 答案
前驅為 1−2−4=15/16=1.1112×2−1,後繼為 1+2−3=9/8=1.0012,u=1/16。精確數 1+1/16 是 1 與 9/8 的中點。1.0002 為偶,1.0012 為奇,所以它捨入為 1。精確數 1−1/32 是 15/16(有效數字 1.1112,奇)與 1 的中點,同樣捨入為 1。