定義明確的和,計算起來也可能難以準確
把一長串數相加看似比解線性方程組簡單,但每次加法都會發生捨入。此外,抵消現象可使結果對輸入的擾動極為敏感。這是兩個不同的問題:一個關乎數學上的和,另一個則關乎用來計算它的算法。
對於實數 ,記 。
定義 1.2.1
(和的條件數)
當 時,針對分量相對擾動 , 的相對條件數定義為
若 ,則非零的絕對擾動以 為基準時沒有有限的相對誤差,因此 沒有定義。
命題 1.2.2
(和對分量擾動的敏感度)
若對每個 都有 ,且 ,則
對實數輸入而言,此界是尖銳的(sharp)。
證明
(三角不等式與同向擾動)
由 及三角不等式,得 ;再除以 即得相對形式。取 ,所有擾動便朝同一方向累加,,等號成立。
標準模型下的順序加法
定義 1.2.3
(捨入模型與常數 )
假設計算中的每一次浮點加法均滿足
其中 為單位捨入誤差(unit roundoff)的上界。此相對模型要求各運算保持在其有效範圍內;上溢、下溢及例外值需另行處理。對 ,定義
設 是對已表示的輸入依次相加所得的結果,即 、,並假設 。
定理 1.2.4
(順序求和的誤差界)
對於 ,
此模型適用於已表示的輸入;表示原始數據時所引入的誤差須另行計算。
證明
(展開遞推式)
對 ,寫 ,其中 。逐步展開得
每個乘積有 個因子。由於 ,每個乘積與 之差至多為 。對指數 使用 Bernoulli 不等式,得 ;故當 時 ,從而 。又 隨 遞增,所以每個乘積與 之差至多為 。因此
證明透視
每個假設用在哪裏
假設 只用一次,用來保證 Bernoulli 步驟中的 為正。範圍假設則每次加法都要用,因為每次加法都有各自的因子 。關鍵一步,是把捨入因子的乘積換成與各 符號無關的單一上界 。由於這個界分別附在每個 上,證明最後得到的是 ,而不是 。
若 ,相除可得
因此,當求和問題病態時,即使後向擾動很小,也可能產生很大的相對前向誤差。反過來說,較大的條件數只是最壞情況的警示,並不表示每一種次序或每一次捨入的實現都會有很大的誤差。因子 來自算術模型以及捨入步驟的數目;因子 則來自輸入數值及其抵消程度。改進求和算法可以減小前者,但無法改變底層求和對不確定數據的敏感度。
快速檢查
(計算 的 。)
解答 · 答案
和為 ,絕對值之和為 ,故 。
快速檢查
(對於和非零的正數輸入, 是多少?)
解答 · 答案
為 ,因為所有 皆為正時 。
次序與例子
例題 1.2.5
(抵消與加法次序)
的精確和為 。在滿足 的算術中,由左至右求和得到零;而先將 與 相加,再加上 ,則得到一(假設這些運算可被精確表示)。具體的次序相關行為取決於浮點格式與捨入模式。此處 ,正是次序可能有影響的警示。
例題 1.2.6
(達到敏感度界的擾動)
取 ,則 、、。取 及 ,擾動後的和為 ,故 ,且 。等號成立,所以對這組輸入,比 更小的常數都不可行。
例題 1.2.7
(無抵消的情形,以及精確和為零)
若所有輸入皆非負且至少有一個為正,則 。對 ,相對誤差界即為 ,但實際捨入後的結果仍可能取決於次序。成對求和(pairwise summation)構成平衡樹,常能把一條路徑上的加法次數由 減至約 ;相應的證明須考慮實際的樹結構與捨入模型。
邊界情形是 :此時 , 沒有定義。然而 恰好成立,所以絕對誤差界 綽綽有餘。絕對誤差界仍然有意義,失去的只是相對誤差的陳述。
反例模式
很小的相對輸入擾動可能導致答案中的巨大誤差
命題:若輸入的相對準確度為 ,則其和的相對準確度也接近 。考慮 及 。它們的和為 ,而各項絕對值之和約為 。因此 約為 。只把 擾動相對量 :,則和變為 ,相對改變為 。對不確定的輸入數據使用精確算術,也無法還原這些數據本身並未決定的數位。只有在 不大時,上述命題才成立。
常見錯誤
(補償求和不能修復不確定的數據)
補償求和(compensated summation)會追蹤先前步驟中損失的部分捨入量,可提高準確度,但上文所證明的界針對的是一般的順序加法。它並不構成對某一特定補償算法誤差界的證明,也不會消去因子 :若輸入本身不確定,任何累加次序都無法補回缺失的數位。
練習與解答
快速檢查
(在所述模型下,給出對四個已表示的值求和的絕對誤差界。)
解答 · 答案
誤差界為 ,並假設 。
快速檢查
(為何精確和為零時,相對條件數沒有定義?)
解答 · 答案
其分母為 ;絕對誤差界仍然有意義,但除以零無法定義相對誤差。