從圖像到誤差估計
設 ,其中 、。把它分為 列、 行等寬格子,、,其中 為正整數。每個格子 取中點 ,定義中點和
定義 7.1.1
(矩形上的 Lipschitz 函數)
若對所有 都有 ( 為 Euclidean 範數),則稱函數 以 為 Lipschitz 常數。
Lipschitz 函數在緊緻矩形上連續,因此 Riemann 可積。下面的估計只用到標準的積分比較,以及積分對格子的可加性。
定理 7.1.2
(中點網格誤差界)
若 在 上以 為 Lipschitz 常數,則
先控制一格,再相加
格內任一點到中點的 Euclidean 距離至多為格子對角線長的一半。於是先逐格得到界,再把各格的界相加。
證明
(局部半對角線界,再對各格求和)
閉格 中離中點最遠的點是一個角,距離為 。因此對 ,
由於 ,對 個格子使用積分的可加性,得
每個格子項的絕對值至多是 乘上述界(積分比較)。把 個格子相加並使用三角不等式:總面積為 ,便得所聲稱的估計。
證明透視
Lipschitz 假設用在哪裏
唯一不顯然的做法,是逐格減去常數 :中點和恰好是一個階梯函數的積分,所以誤差是各格 的積分之和;每一項都小,因為 離開 處的值不能太遠。
Lipschitz 假設只用一次,就是逐點界;選取中點也只用一次,作用是把對角線減半。若在格內任取樣本點,同一證明只得到完整對角線 ,界便大一倍。可積性只用來拆分及比較積分。論證能夠完結,是因為每一格貢獻相同的界乘以自己的面積,而面積之和為 。兩個網格寬度趨零時最終的界也趨零,所以既不需要也沒有假設中點公式有二階精度。
例子
例題 7.1.3
(多項式的正方形網格)
在 取 。對正方形中兩點,
所以可取 。對 網格,一般界為 。用累次積分計得精確積分為 。
此多項式的中點和可以更精確地算出: 的中點平均為 ,而
展開平方並使用 和 的有限求和公式,即得此恆等式。因此 。當 ,實際誤差為 ,一般界則為 。對整類函數有效的界,對某個特定函數未必銳利。
例題 7.1.4
(落在格邊上的尖點)
在 上令 ,它以 為 Lipschitz 常數,但沿 不可導。積分為 。取 ,唯一樣本是 ,該處 ,故 ,誤差為 ;界為 。取 、,中點的 為 ,兩處 都是 ,而 、,所以 :此和是精確的。尖點正好在兩格的公共邊上,所以 在每格內是仿射函數,而中點公式對仿射函數精確。此時的界 有效,但偏保守。
例題 7.1.5
(非正方形的矩形)
在 上取 ,、,所以 、。由於 ,可取 。兩個中點是 和 ,故
而 。實際誤差為 。定理給出 。雖然 完全不依賴 ,界仍然很大,原因是高格子()令半對角線很長。這個界控制的是格內最壞的方向,而不是 的實際變化。
反例模式
中點和並非對每個函數都精確
斷言:在每格中心取樣,中點和就等於積分。取 上的 ,其積分為 。當 ,唯一樣本在 ,和為 。當 ,和為 ,而 。一般而言,對每個 誤差都是 。修正:中點公式對仿射函數精確,因為在一格內 的積分由對稱性為零;但 一項是彎曲的,留下正的誤差。對一般的 Lipschitz 函數,只能依靠上面的界。
下面的互動圖對三個函數在 的任意 網格上精確計算中點和,並把真實誤差與 Lipschitz 界 比較。
有效的 Lipschitz 界與真實的中點誤差
在 R = [0,1]² 上,比較 m × n 網格的中點和 S 與精確積分。Lipschitz 界 (L/2)√(1/m² + 1/n²) 對每個網格都成立,但各函數的真實誤差表現迥異。
正方形分為 m 欄、n 行。圓點是取樣 f 的格子中點。下方表格列出 m = n = 1, …, 10 的相同資料。
網格: 1 × 1 = 1 個格子
| k | 中點和 S | |∫f − S| | 界 (L/2)√(1/m² + 1/n²) | 誤差 ÷ 界 |
|---|---|---|---|---|
| 1 | 3/4 | 1/12 | √10/2 ≈ 1.5811 | 0.0527 |
| 2 | 13/16 | 1/48 | √10/4 ≈ 0.7906 | 0.0264 |
| 3 | 89/108 | 1/108 | √10/6 ≈ 0.5270 | 0.0176 |
| 4 | 53/64 | 1/192 | √10/8 ≈ 0.3953 | 0.0132 |
| 5 | 83/100 | 1/300 | √10/10 ≈ 0.3162 | 0.0105 |
| 6 | 359/432 | 1/432 | √10/12 ≈ 0.2635 | 0.0088 |
| 7 | 163/196 | 1/588 | √10/14 ≈ 0.2259 | 0.0075 |
| 8 | 213/256 | 1/768 | √10/16 ≈ 0.1976 | 0.0066 |
| 9 | 809/972 | 1/972 | √10/18 ≈ 0.1757 | 0.0059 |
| 10 | 333/400 | 1/1200 | √10/20 ≈ 0.1581 | 0.0053 |
- 中點和 S
- 3/4
- 精確積分 ∫f
- 5/6
- 帶號誤差 ∫f − S
- 1/12
- 閉式誤差
- 1/12 (是)
- 界(精確值)
- √10/2
- 界(近似值)
- 1.5811
- |誤差| ≤ 界
- 是
- 誤差 ÷ 界
- 0.0527
1 × 1: S = 3/4, ∫f = 5/6. |∫f − S| = 1/12 ≤ √10/2 ≈ 1.5811. 誤差在 Lipschitz 界之內。 真實誤差是界的 5.27%。
界為何成立,又為何不銳利
在中點為 z 的格子上,每點到 z 的距離至多是格子對角線的一半 (1/2)√(h_x² + h_y²),所以 |f(w) − f(z)| ≤ (L/2)√(h_x² + h_y²)。在格子上積分再把各格相加,總面積為 (b − a)(d − c),此處等於 1,即得該界。
該界只用到 L,所以必須容許具有該 Lipschitz 常數的最壞函數。對 f = x² + y,中點和為 5/6 − 1/(12m²),真實誤差 1/(12m²) 為 1/m² 階,遠小於 1/m 階的界。對 f = xy,中點和精確。對絕對值函數,誤差為 [m 為奇數]/(4m²) + [n 為奇數]/(4n²),其中 [·] 在條件成立時為 1,否則為 0。
中點和能令每個非線性函數都精確嗎?
不能。對 x² + y 取 1 × 1 網格,唯一樣本在 (1/2, 1/2),得 3/4,而積分為 5/6,誤差為 1/12。乘積 xy 精確,只是因為它的中點平均可分解,且每個因子都是線性。
本圖固定 R = [0,1]²,並取三個 Euclidean 範數下 Lipschitz 常數已知的函數;網格有 1 至 20 欄及行。和、積分及誤差皆為精確分數,界以平方後作精確比較;只有小數形式的界及比值是近似值。其他矩形、其他範數及其他求積法不在範圍內。
檢查與練習
快速檢查
(在 的 網格上,每格的面積是多少?)
把兩個格寬相乘。
解答 · 答案
。
快速檢查
(在第一個例子中, 是多少?)
使用 。
解答 · 答案
。
快速檢查
(單憑一般界,可保證正方形網格有 誤差嗎?)
看看界如何隨 和 變化。
解答 · 答案
不能。在 網格上 、 都與 成正比,所以上述 Lipschitz 界是 。像 那樣誤差為 的更快衰減,需要關於 的更多資訊。
快速檢查
(若 為常數,可取 嗎?誤差界說甚麼?)
常數函數沒有變化。
解答 · 答案
可以,因為 。誤差界此時給出零,這是正確的:常數的每個中點和都等於積分。