一個迴圈可以因為兩個顯示出來的數值看似接近而停止,可以因為迭代次數上限已用盡而停止,亦可以因為誤差界達到所要求的容許誤差而停止。這些是不同的事件。一個數值方法應當報告發生的是哪一種事件,以及在甚麼假設下其停止準則才具有意義。
數學上的契約
定義 13.1.1
(不變區間上的壓縮映射)
設 為閉區間。若 且
則稱映射 是 上常數為 的壓縮映射。包含關係 稱為不變性:它使每個迭代值 都留在壓縮估計已知成立的範圍內。對 ,記 為觀察到的步長。
定理 13.1.2
(不動點迭代的後驗誤差界)
設 是 上常數為 的壓縮映射,且 。則所有迭代值都在 內,,其中 是唯一的不動點,並且對每個 都有
證明
(用幾何級數界定尾項)
由不變性,用歸納法得所有 。對 ,把壓縮不等式用於 ,得 ,因此 。對 ,裂項相消再用三角不等式,得
同一估計表明 是柯西(Cauchy)序列,故收斂到某個 ;因 是閉集,。 連續,所以 。若 是 中另一個不動點,則 ,因 而得 。最後在上面的不等式中令 :,即得所求。若 ,則 在 上為常數,第一次更新已經得到不動點。
證明透視
每一行用了哪個假設
關鍵一步是裂項求和:未知的誤差 被換成一串觀察到的步長之和,而壓縮不等式把這個和變成幾何級數。不變性只用來保證每個階段的 和 都在 內,使 每次都可使用;沒有它,鏈條在第一個離開 的迭代值處就斷了。條件 用了兩次:求級數和,以及令不動點唯一。最後的極限 需要緊接之前證明的收斂性;單憑細小的 ,沒有壓縮常數,根本得不出任何尾項估計。因子 是不知道往後步長所付的代價:恰在 接近一時它才很大。
這個界適用於新的迭代值 ,即在量度它與 的距離之後。單憑差值細小並不是一個普遍適用的證書:這個界用到一個已證明的壓縮常數以及區間的不變性。
計算示例
例題 13.1.3
(常數為二分之一的映射)
取 、 及 。其像為 ,且 ,故 。不動點滿足 ,因此 。首幾個迭代值為
在 時,,所以證書為 。這裏實際誤差亦是 。等號成立是這個例子的性質,並非一般地保證這個界是精確的。
下面的互動圖在五個映射上執行這個迴圈,並比較每一步的步長 、證書 與真實誤差,讓你看出細小的步長在何時才有保證。
細小的步長能保證甚麼
在五個映射上執行本節的迴圈,比較步長 d_n、證書 (q/(1−q))·d_n 與真實誤差,並看停止準則在甚麼時候才有意義。
曲線為 y = g(x),虛線為 y = x,折線連接 (x_{n−1}, x_{n−1})、(x_{n−1}, x_n)、(x_n, x_n)。下表列出相同的迭代值。
| n | x_n | d_n = |x_n − x_{n−1}| | 證書 (q/(1−q))·d_n | 真實誤差 |x_n − x*| | 真實誤差 ÷ 證書 |
|---|---|---|---|---|---|
| 0 | 0 | 沒有 | 沒有 | 2 | 沒有 |
| 1 | 1 | 1 | 1 | 1 | 1 |
| 2 | 3/2 | 1/2 | 1/2 | 1/2 | 1 |
| 3 | 7/4 | 1/4 | 1/4 | 1/4 | 1 |
| 4 | 15/8 | 1/8 | 1/8 | 1/8 | 1 |
| 5 | 31/16 | 1/16 | 1/16 | 1/16 | 1 |
開首的 ≈ 表示四捨五入的小數,其餘項目均為精確值。
- 狀態
- ok(達標)
- 已證明的壓縮常數 q
- 1/2
- g 在 I 上的最佳利普希茨常數
- 1/2
- 不動點 x*
- 2
- 算術
- 精確有理數
- 停止的指標 n
- 5
- 首個 d_n ≤ tol 的 n
- 5
- 最後一列的證書
- 1/16
- 最後一列的真實誤差
- 1/16
- 每一列的真實誤差 ≤ 證書
- 是
狀態 ok。迴圈在 n = 5 停止,因為證書 1/16 不大於 tol = 10⁻¹。在已證明的 q = 1/2 下,定理給出 |x* − x_n| ≤ 1/16;真實誤差為 1/16。
只用步長的檢驗 d_n ≤ tol 會在 n = 5 停止,此時 d_n = 1/16。該處的真實誤差為 1/16,是 d_n 的 1 倍。
證書為何成立,又在何時失效
若 g(I) ⊆ I,且 |g(x) − g(y)| ≤ q|x − y|,其中 0 ≤ q < 1,則 d_{n+1} ≤ q d_n,故 d_{n+j} ≤ qʲ d_n。因 x_m → x*,由三角不等式及幾何級數的尾項得 |x* − x_n| ≤ d_{n+1} + d_{n+2} + … ≤ (q/(1−q)) d_n。
對 g(x) = 1 + x/2,由於每一步的方向相同,證書在每個 n 都等於真實誤差;對 cos x,比值保持小於 1。等號成立是這些例子的性質,並非這個界一般為精確界的承諾。
對 g(x) = 1 + 0.999(x − 1),常數 q = 999/1000,所以 q/(1−q) = 999,真實誤差為 999 d_n:10⁻³ 的步長可以與接近 1 的誤差同時存在。對 2 − x,迭代值在 x₀ 與 2 − x₀ 之間來回;對 x + 10⁻⁶,步長永遠是 10⁻⁶,但根本沒有不動點。
餘弦預設使用 q = sin 1,即 |g′| 在 [0, 1] 上的最大值,而 g([0, 1]) = [cos 1, 1] ⊆ [0, 1]。它以雙精度浮點數運算,所以其證書並不是嚴格的機器算術界;仿射預設則以精確數計算。
起始值為區間 I 內的 x₀ = k/8,容許誤差為 10⁻ᵉ(e 由 1 至 8),最多執行 60 步。表列在首個證書不大於 tol 的 n 處結束。真實誤差使用已知的不動點 2、1、1 及 0.7390851332151607。
例題 13.1.4
(容許誤差需要多少步?)
對同一個映射及 ,有 ,故 ;又因 ,證書等於 。我們要它不超過 ,即 。由於 而 ,第一個合格的 是 ,證書為 ,真實誤差 。若步數上限為 maxSteps = 10,迴圈便無法證明這個容許誤差,狀態必須如實報告。
例題 13.1.5
(由導數得出壓縮常數)
設 ,。則 ,且在 上 ,所以由中值定理得到以此 為常數的壓縮,並且 。由 出發:、、,所以 ,證書約為 。這個證書是有效的,因為真實誤差為 ,但它比 的長度還大,並沒有提供有用的資訊。常數接近一令適中的步長成為缺乏說服力的證書;要把證書壓小,需要多得多的迭代。
一個會報告狀態的有界迴圈
以下的 MATLAB 函數是針對這個特定的 及區間的簡潔示範。它接受位於 [0,2] 內的有限實數純量 x0、正而有限的 tol,以及正整數 maxSteps。這裏假設輸入符合上述契約;正式使用的函數應在執行迴圈前先驗證輸入。
function [x, ok, n, bound] = fixed_demo(x0, tol, maxSteps)
% Mathematical x_n is returned after n updates.
q = 1/2;
x = double(x0);
ok = false;
bound = Inf;
for n = 1:maxSteps
xnew = 1 + x/2;
bound = (q/(1-q))*abs(xnew-x);
x = xnew;
if bound <= tol
ok = true;
return
end
end
end
迭代計數器計算的是已完成的更新次數。若沒有任何一個界達到容許誤差,ok 會保持為 false,並傳回最後一個近似值,連同最後一個界及已用盡的次數。maxSteps 為正數這項契約確保即使迴圈從未提早返回,n 亦已被賦值。在精確算術下,ok=true 在已證明的壓縮假設下證明了所述的距離界。浮點捨入會帶來該證明未有涵蓋的影響,所以單憑顯示出來的 bound 並不是一個嚴格的機器算術證書。
對於不同的 ,在未有證明相關區間上的有效界之前,切勿沿用 q=1/2。特別地,若 在 上連續、在其內部可微,且在整個內部均有 ,則中值定理給出壓縮不等式。不變性 仍需另行檢查;只在單一點檢查導數是不足夠的。
細小的步長可能造成誤導
反例模式
步長細小而誤差很大
斷言:若 小於 ,則 與不動點相差約不超過 。取 上的 。其像為 ,故 ,,。由 得 ,所以 ,但真實誤差是 ,即 。一般地,,而 。這與定理一致:證書 在此恰好等於真實誤差。只有當 適中時,細小的步長才證明誤差細小;當 時,這個因子至多為一。
常見錯誤
(契約不成立時仍把最後一個迭代值當作根)
映射 把 映入自身,並有不動點 ,但它不是一個常數小於一的壓縮映射:。由 出發,序列為 ,每一步都是 ,所以步長測試從不觸發,迴圈只會在最大步數處結束。最後的迭代值 或 並不是不動點 。最大步數上限可防止迴圈無止境地執行,但並不會把這個輸出變成一個已收斂的答案。同樣, 的步長細小,但它沒有不動點,亦沒有所需類型的不變有界區間。當假設不成立時,正確的做法是報告其局限,而不是把最後一個迭代值標示為已證明的根。
小測
快速檢查
(對 上的 及 ,在 時證書是多少?)
利用 和 。
解答 · 答案
,且 ,所以證書是 。真實誤差為 。
快速檢查
(某映射是壓縮映射,,最後一步為 。定理給出甚麼誤差界?)
計算 。
解答 · 答案
,故 。在步長為 時停止,只能證明約 ,而不是 。
快速檢查
(當 取甚麼值時,停止測試 本身就是誤差不超過 的證書?)
解 ,其中 。
解答 · 答案
,即 。 較大時,步長應與 比較。
快速檢查
(對 上的 ,定理的哪一個假設不成立?)
取 、 檢驗壓縮不等式。
解答 · 答案
不變性成立,但 ,所以不存在 。迭代 並不收斂。