即使每個輸入都能精確表示,長串求和仍可能失去小增量。前一單元區分了捨入誤差和總和本身的敏感度;這裏研究一種記住部分加法捨入影響、並在下一步加以補償的算法。
帶符號的修正
定義 1.4.1
(補償求和(Kahan 求和))
對已表示的輸入 ,令 、,每步按所示次序計算:
返回 。計算 時用的是舊的 。
精確算術下 ,修正項為零。有捨入時, 估計實際吸收的增量,因此 估計所吸收增量超出原定增量多少;下一步減去這個超額。上述每個運算均分別捨入,估計值一般並非精確誤差。
常見錯誤
(把修正項化簡為零)
若將表達式 按代數規則重組為零,便破壞這個計算,因為這種代數式只在精確算術中成立。實現,以及會重排浮點運算的編譯器,都必須保留指定的求值次序。
命題 1.4.2
(精確算術下修正項為零)
若每個運算都精確進行,則每步之後 ,並且第 步之後 。
證明
(對步數歸納)
設第 步之前 、。則 ,,,所以新的 是 ,且 。第一步之前 ,命題成立。
證明透視
修正的是甚麼?
只為理解符號,假想 和 精確,而唯一誤差來自捨入後的加法 。若 ,則 ,下一個輸入便用 修正。實際算法的兩次減法也會捨入:這個推論解釋符號,但不能證明所有誤差被消除,也不是誤差界。
小型十進制機器中的十個增量
例題 1.4.3
(在 1000 上加十個 1)
使用三位有效數字的十進制算術,每次運算捨入至最接近的數,平手取偶;假設指數範圍足夠。 的所有輸入均可精確表示,精確和為 。處理 後,普通和及補償和均為 ,且 。在這個尺度上, 上方相鄰可表示數相距十。
| 已處理的 1 的數目 | 普通和 | 補償和 | 修正項 |
|---|---|---|---|
| 1 | |||
| 4 | |||
| 5 | |||
| 6 | |||
| 10 |
第五個 1 時, 恰在中間,平手取偶選 ;第六次 , 捨入為 ,修正項是 。其後四個輸入使 減至零。普通和失去所有 1;這次補償結果恰巧精確。格式、捨入規則或次序改變,過程也可能不同。
例題 1.4.4
(兩個 4 的增量)
在同一機器中處理 ,精確和為 。普通求和得 ,再加一次仍是 :結果為 ,與精確和相差 。補償方法在處理 後 。第一個 給出 、、。第二個給出 、、,所以 ,與精確和只差 。在這兩條過程記錄的每一行中, 都等於精確的部分和(例如 ,)。這個恆等式只是對這些記錄的觀察,在 及 中的減法都精確時成立;下面的反例顯示它在哪裏失效。
例題 1.4.5
(沒有任何捨入的情形)
在同一機器處理 。每個中間量都至多有三位有效數字:;然後 ;再然後 。返回的和是 ,修正項始終為零,方法與普通求和一致,正如關於精確算術的命題所預言。
反例模式
補償並非精確累加器
在同一十進制機器處理 。前兩項後 ;第三項有 ,故返回 ,但已表示輸入的精確和是 。修正項與大得多的輸入結合時,本身也可能被捨入掉。
方法的作用與限制
每個輸入只需常數次算術運算和常數個儲存位置,所以運算量為 ,工作空間為 ,不計輸入儲存。此算法可大幅改善求和,但上面的例子並非普遍誤差界。
常見錯誤
(以為補償可以消除病態性)
相消可能使精確和對數據擾動敏感;補償不能恢復已表示輸入中不存在的數位。它改善的是算術,而不是問題本身的條件性。
溢出、下溢、非有限數及編譯器重組運算須另行分析。若應用需要經認證的誤差,須選擇適合實現的算術模型及誤差分析。
習題
快速檢查
(十個增量例子中處理第三個 1 後 是甚麼?)
依照表中最初幾行的規律。
解答 · 答案
:第三步有 、、。
快速檢查
(第六次修正項為何是正的?)
比較被吸收的增量與原定增量。
解答 · 答案
捨入步驟吸收 ,而調整後原定增量是 ,多出 。
快速檢查
(十個增量例子中處理第七個 1 後 是甚麼?)
從第六個之後的 開始。
解答 · 答案
,,。所以 。
快速檢查
(最後的反例是否證明所有補償和都失敗?)
數一數它用了多少個輸入、甚麼算術。
解答 · 答案
否;它只顯示指定算術與次序下的一次失敗,並非典型或普遍行為的證明。