動機
數值方法經常包含兩種競爭機制。減小步長可改善數學近似,卻可能放大輸入誤差;增加運算可消去截斷主項,卻同時引入更多捨入。因此,準確性陳述需要一個統一的誤差預算,各項都針對同一個最終量,並明確說明各自假設。
本節先從中心差分構造四階公式,證明其誤差常數,再研究組合樣本時的算術。求和說明一個關鍵現象:算法可以後向穩定,但若真實和接近抵消,其相對前向誤差仍可能很大。成對求和與補償求和改善問題的不同部分。
定義
定義 8.1.1
(Richardson 外推的中心差分)
假設所需位置都可取樣,定義
展開即得五點公式
中心點係數為零,所以只需四次偏離中心的函數求值。「五點」指包括中心的等距模板。Richardson 外推利用已知的步長冪消去主誤差項,不是簡單平均兩個答案。
定義 8.1.2
(浮點捨入模型)
算術部分假設採用最近捨入,單位捨入誤差為 ,並且討論中的每次運算滿足
定理排除溢出及不適用正常相對誤差模型的運算。若 ,記 。
定義 8.1.3
(求和條件數)
對精確輸入 ,令 。當 ,分量相對擾動下的求和條件數為
即使每次加法捨入很小,這個數仍可能很大。真實和為零時,除以 的相對誤差沒有定義;絕對誤差依然有意義。
定理/命題
定理 8.1.4
(四階微分及獨立的數據界)
設 、,且該區間 。則
若四個函數輸入值各有絕對誤差至多 ,對這些輸入精確計算公式,則
當 ,這個上界在所有正步長中於 取最小值,前提是該步長下的取樣域及導數假設有效。
定理 8.1.5
(捨入模型下求和的後向穩定性)
順序求和 個數,共使用 次捨入加法。若 ,結果可寫為
因此 ;當 ,相對前向誤差至多 。若使用最大深度 的平衡成對樹,在相同模型及 下,絕對界改為 。
後向陳述表示答案是輕微擾動輸入的精確和,不表示原問題的相對誤差一定小。條件數正是連接兩個陳述所缺的資訊。
概念視角結構
統一分配誤差預算
外推消去近似主項;成對求和縮短捨入因子鏈;補償把丟失的低位傳給後續計算;條件性描述輸入中已有的誤差如何影響目標。這些機制發生在不同階段,合理組合需要把各自貢獻寫入同一個最終絕對或相對誤差陳述。
證明思路或證明
消去微分誤差主項
連續五階導數的 Taylor 展開給出
換成 可見 消去二階項,因此 。這識別了漸近主係數,但尚未證明定理中對整個餘項的上界。
證明
(五點公式的 Peano 核誤差界)
先縮放到 ,令 。直接代入發現它消去所有次數不超過四的多項式。以 為基點的積分 Taylor 公式,把 函數寫成四次多項式加上 的積分。作用 後得到
核為偶函數,其非負半軸表達式是
對非負 ,截斷冪在零點的導數貢獻為零,代入兩個正取樣點便得上式;負半軸直接代入給出相同數值。在 ,,故分子非正;另一段顯然非正。積分為
於是 。令 ,則 ,五階導數提供 因子,除以 即得界。樣本誤差的絕對權重和為 ,故再加獨立數據項。對合併上界關於 求導,得到所述極小點。它優化的是這個模型的上界,不是所有機器計算的普遍最佳步長。
證明透視
單一符號的核為何給出最佳常數
證明靠兩個想法。公式對次數不超過四的多項式精確,使 Peano 表示可以丟掉整個 Taylor 多項式,於是 只取決於 。其次,核從不改變符號,這把粗略估計 變成 ,而這個數可用任何一個五次式算出:對 ,,同時 。由於 ,只要 為常數便取到等號,所以 不能再改進,而正的五階導數必然給出負誤差。假設 的用處在於核支撐於 ;偶性只是把計算減半。縮放時 帶來 , 帶走一個 ,剩下 。
展開捨入因子
證明
(展開捨入因子)
記 、。逐次代入後,每個輸入都乘上至多 個 因子。包含 個因子的乘積偏離一至多 :其最大值不超過 ,最小值不少於 ,並且
第一個不等式可在 下歸納,第二個是 Bernoulli 不等式。因此每個輸入都對應一個有界乘法擾動,取絕對值給出前向界,再除真實和的絕對值便出現條件數。成對樹中的每個葉子最多通過 次加法,相同論證把 換成 。整個證明不需要隨機捨入假設。
成對界改善的是最壞深度依賴,不能保證每組數據都比所有順序次序嚴格準確。全正輸入的條件數為一,接近抵消的和在兩種算法下都可能敏感。輸入本身也必須已按預期表示;外部十進制數據轉換造成的擾動需另計。
補償究竟記錄甚麼
一種常用補償方法保存和 與修正量 ,初始均為零。對每個輸入 ,依順序執行
修正量估計最近加法丟失的低位,並從下一輸入減去它。運算順序和每次捨入很關鍵;若把 的代數式簡化成零,便破壞了算法。補償經常顯著改善累加,但這裏的解釋不是「總能返回精確和的正確捨入」的證明。更強誤差界需要針對具體實作及捨入假設的獨立分析,不能把順序求和的定理直接附到不同遞推上。
誤差預算還說明更多測量能做到甚麼。儀器固定的絕對不確定性,不會因為取樣距離縮短便自動減小。重複測量在合理統計模型下可能改善估計,但確定性絕對界不能僅憑樣本數量增加而縮小。上面的優化把兩個常數視為固定;若它們隨步長改變,必須重新分析。
顯示很多小數位也不證明每一位準確。接近零的導數或抵消的和,經過驗證的絕對區間通常比相對誤差更清楚。相對誤差適合尺度差異大的非零結果。報告應同時說明量、範數、假設和界,讀者才能判斷哪些數字及後續決定有依據。
例題詳解
例題 8.1.6
(達到微分常數的五次函數)
在零點取 ,五點分子為 ,故 ,真導數為零。由於五階導數為 ,誤差恰為 。外推 等於間距 的同一模板,所以誤差為 。更小截斷誤差伴隨更近取樣及更大的數據不確定性權重。
例題 8.1.7
(小型二進制系統中的補償)
使用三位有效二進制數字、最近捨入且中點取偶。求一加四個 。在一附近間距為 ,普通順序加法每次遇到中點又回到一,因此返回一,真值卻為 。補償遞推在各個小輸入後依次得到 、、、。修正保留了足夠的低位,在本例恢復精確和。
例題 8.1.8
(後向穩定遇上敏感的和)
輸入 的真和為一,條件數為 。順序定理給出相對誤差界 。若模型中 ,該界約為四,儘管每次加法的相對捨入都很小。這不是某具體十進制或二進制格式的輸出斷言,而是說明抵消問題中的後向穩定只能提供較弱的相對保證。
常見錯誤
反例模式
補償不是普遍精確求和算法
在標準 binary64 最近捨入、中點取偶下,上述補償遞推處理 會返回零,實數精確和卻為一。加入一後修正量為 ,但形成下一個修正輸入時, 又捨入回 ,保存的一在此丟失。因此成功的小例子不能支持無條件準確性聲明。
常見錯誤
(對高階公式取盡量小的步長)
四階不表示步長越小越好。截斷項按 減小,數據項卻按 增長,而且浮點座標 最終可能等於 。微分定理及其數據項沒有包含形成座標、求函數值、加權求和和相除的完整硬件分析。
常見錯誤
(把後向穩定理解為相對誤差小)
後向誤差小也不能克服病態問題:對接近抵消的和,相對前向界是 ,而 可以極大。誤差報告應明確模型、最終量,以及哪些誤差已被計入。
總結
Richardson 消去二階項產生四階模板,其單符號核給出具有可達常數的導數界。樣本誤差另加反比步長項。正常捨入模型下順序求和分量後向穩定,但抵消可放大相對前向誤差。成對樹改善深度依賴,補償保留低位,卻需獨立分析,不能普遍保證精確和。
練習
快速檢查
(在零點將 應用於 和 ,解釋前者準確及後者的誤差符號。)
利用分子 。
解答 · 答案
三次函數的分子為 ,與真導數一致;公式重現所有四次以內多項式的導數。五次函數的結果為 。五階導數正、核非正,故有符號誤差為負。
快速檢查
(設 ,每個函數樣本的絕對不確定性為 。寫合併上界,求最優正步長,並說明實際中該步長可能不適用的兩個原因。)
把定理中的 與 相加。
解答 · 答案
上界為 。極小點滿足 ,約 。取樣點可能超出定義域,或者導數及數據界未覆蓋整個取樣區間。座標捨入與求值誤差也需獨立預算。這個步長優化所寫的界,而非未指定的全部硬件計算。
快速檢查
(若 、,比較順序及平衡樹的 常數。若輸入都非負且和為正,條件數是多少?)
有 個葉子的平衡樹深度為 。
解答 · 答案
順序深度為 ,常數為 。平衡深度為十,常數為 。非負輸入且正和給出 。比較的是最壞界的常數,不是每個數據集的嚴格誤差排名。
快速檢查
(三個數的精確和為零,為甚麼相對前向誤差沒有定義?給出順序求和的適當絕對界,並說明它是否要求計算結果為零。)
用後向穩定定理的絕對誤差形式,取 。
解答 · 答案
絕對誤差除以真實零和沒有定義。若 ,定理給出 。這個區間可以包含非零計算答案。後向穩定允許各輸入受到輕微分量擾動,而這些擾動不必保持原有的精確抵消關係。