§24-2  階梯與折線逼近

任給一個連續函數與一個容許誤差,能不能找到一個結構簡單得多的函數,在定義域的每一點都落在誤差之內?兩種最簡單的工具,效率差多少?

用簡單的函數逼近

無障礙坡道要做得平順,可是施工時是一階一階砌出來的。只要每一階夠矮,走起來與真正的斜坡沒有差別——而「差別」可以量化成一個數字:實際的高度與理想的高度最多差幾公分。

把這件事寫成數學:給一個連續函數 f 與一個容許誤差 ε,能不能找到一個結構簡單得多的 g,使得定義域上的每一點都滿足 ‖g(x) − f(x)‖ < ε?

「每一點都滿足」這句話正是上一篇的 uniform norm:‖g − f‖_D ≤ ε。所以逼近與均勻收斂是同一件事的兩種說法——找得到一列越來越好的 g,就等於找到一列均勻收斂到 f 的函數。本篇給出兩種最簡單的逼近工具,而兩者的證明用的都是上一節的均勻連續定理。

說 g 在 D 上均勻逼近 f 到誤差 ε 以內,意思是
  ‖g − f‖_D = sup {‖g(x) − f(x)‖ : x ∈ D} ≤ ε。
說 f 可以被某一類函數 𝒢 均勻逼近,意思是每個 ε > 0 都有 𝒢 中的某個 g_ε 辦到這件事——等價地,𝒢 中存在一列函數在 D 上均勻收斂到 f。
24.3  DEFINITION
A function g with domain ℝᵖ and values in ℝ^q is a step function in case it takes only finitely many distinct values, each non-zero value being taken on a finite union of cells in ℝᵖ.
階梯函數只認得有限多個值,而且每一個非零的值都佔著方格——可以不只一塊,可是總共有限塊。它幾乎處處不連續——每一塊方格的邊界上都可能跳一階——可是它結構極簡:有限多個數字加有限多塊區域就交代完了。
正例:g(x) = 1(−2 ≤ x < 0)、3(0 ≤ x < 1)、−5(1 ≤ x ≤ 3)、其餘為 0,是一個階梯函數。反例:h(x) = 1(x 為有理數)、0(其餘)只取兩個值,可是值為 1 的那一堆點不是任何一塊 cell,所以不是階梯函數。
24.4  THEOREM
Let f be continuous with domain a compact cell D in ℝᵖ and values in ℝ^q. Then step functions approximate f uniformly on D.
任何在方格上連續的函數,都可以用階梯函數逼到要多準有多準。證明是一句話的翻譯:均勻連續說「靠得夠近的點,值也夠近」,那就把定義域切成一塊塊夠小的方格,每塊派一個代表值。
正例:f(x) = x² 於 [0, 1],誤差 0.1 只需把區間切成 25 段(例 3 逐步算)。反例:定義域必須 compact——f(x) = x 在 ℝ 上不能被階梯函數均勻逼近,因為階梯函數只取有限多個值因而有界,而 f 無界。
PROOF

定義域 D 是 compact cell,所以 §23-2 的 23.3 直接給出 f 在 D 上均勻連續。

證明計畫 · 由所求想起
所求是一個階梯函數,也就是「有限多塊方格 + 每塊一個值」。方格由 δ 決定,值由代表點決定:均勻連續交出的 δ(ε) 說「距離小於 δ 的兩點,值差小於 ε」,所以只要每一塊方格的直徑小於 δ,塊內任一點與代表點的值就自動夠近。切法是把每一條邊等分成 m 段,m 夠大即可——這也保證塊數有限。

Proof.  Let ε > 0. By 23.3 there is δ(ε) > 0 such that ‖f(x) − f(y)‖ < ε whenever x, y ∈ D and ‖x − y‖ < δ(ε). Cut each edge of D into m equal parts, where m is chosen so large that (1/m) · diam(D) < δ(ε). This produces mᵖ subcells I₁, ⋯, Iₙ, made disjoint by assigning each shared face to just one of the two neighbours.
這一步的所求:把定義域切成夠小又有限多塊。邊長縮成 1/m 倍時,方格的對角線也縮成 1/m 倍——直徑由對角線決定,所以一個 m 就同時管住所有維度。這與 §10-1 反覆對分方格時算的是同一件事。「不重疊」那一句是邊界簿記:兩塊相鄰的方格共用一個面,把那個面判給其中一塊即可,判給誰不影響結論。
Choose any x_k ∈ I_k and define g_ε(x) = f(x_k) for x ∈ I_k, and g_ε(x) = 0 for x ∉ D. This is a step function. If x ∈ D, then x lies in exactly one I_k, and since ‖x − x_k‖ < δ(ε) we get
  ‖g_ε(x) − f(x)‖ = ‖f(x_k) − f(x)‖ < ε.
這一步兌現。代表點 x_k 可以在方格內任取——左下角、中心、隨便哪裡都行,因為估計只用到「同一塊方格內兩點的距離小於 δ」,與代表點的位置無關。要留意這裡用的是均勻連續:同一個 δ 得對所有方格通用,若 δ 隨位置改變,方格就切不出統一的大小。估計對每個 x ∈ D 成立,所以 ‖g_ε − f‖_D ≤ ε。
連續函數與階梯函數之間的距離可以壓到任意小。∎
每一段取起點的值 段越窄誤差越小

這張圖在說 24.4 的作法:把定義域切成等寬的小段,每一段整段取同一個值(這裡取起點的值)。誤差不會超過該段內函數值的最大落差,而均勻連續正好把這個落差壓在 ε 以下——條件是段寬小於 δ(ε)。要留意階梯函數在每個分界點都跳一階,它並不連續;下一個定理把這些跳階抹平。

DEFINITION
A function g defined on a compact cell J = [a, b] in ℝ with values in ℝ is piecewise linear in case there are points a = c₀ < c₁ < ⋯ < cₙ = b and constants A_k, B_k such that g(x) = A₁x + B₁ for c₀ ≤ x ≤ c₁, and g(x) = A_k x + B_k for c_{k−1} < x ≤ c_k when k ≥ 2.
把定義域切成有限多段,每一段上都是一條直線(第一段連左端點一起收進來,否則 g(a) 會沒人管)。各段的直線不必接得起來——要它連續得另外要求相鄰兩段在分界點上取同一個值,也就是各段的端點相連。本篇要用的正是連續的那一種。
正例:絕對值函數 g(x) = |x| 於 [−1, 1]——分界點取 c₀ = −1、c₁ = 0、c₂ = 1,兩段分別是 −x 與 x,而它們在 0 接得起來,所以連續。反例:g(x) = x² 不是折線函數——任何一段上它都不是一次式,切再多段也一樣。
24.5  THEOREM
Let f be continuous with domain a compact cell J in ℝ and values in ℝ. Then f can be uniformly approximated on J by continuous piecewise linear functions.
把上一個定理的「水平段」換成「傾斜段」,逼近的工具就變得連續了。作法只是把曲線上的一串點依序連起來,而誤差的估計與上一個定理幾乎一字不差。這裡只做 p = q = 1 的情形,高維有對應的說法但形式繁瑣。
正例:f(x) = x² 於 [0, 1],只要兩段折線誤差就小於 0.1(例 3 算給你看,比階梯函數省得多)。反例:定理只保證誤差小,不保證形狀像——折線在每個分界點都有尖角,而 f 可能處處平滑。逼近說的是距離,不是外觀。
PROOF

與上一個定理同樣的起手式:J compact,所以 f 在其上均勻連續,取 δ(ε)。

證明計畫 · 由所求想起
所求是一個連續的折線函數。最省事的造法是讓折線與 f 在每個分界點上取同一個值——連續自動成立(相鄰兩段共用端點),而誤差只需在每一段內部估計。段內的折線值是兩個端點值的加權平均,兩個端點都離 x 不超過段寬,所以只要段寬小於 δ(ε),兩個端點值都離 f(x) 不到 ε,它們的加權平均也就不到 ε。

Proof.  Write J = [a, b] and insert points a = c₀ < ⋯ < cₙ = b with c_k − c_{k−1} < δ(ε) for each k. Let g_ε be the function whose graph consists of the line segments joining (c_{k−1}, f(c_{k−1})) to (c_k, f(c_k)). It is piecewise linear and continuous, since consecutive segments share an endpoint.
這一步的所求:把逼近函數造出來。連續這件事是免費的——折線的每一段都以 f 在分界點的值為端點,所以相鄰兩段在該點取同一個值,接縫不會裂開。段數有限也是自動的:直接把 [a, b] 等分即可,段數 n 只要大於 (b − a)/δ(ε) 就使每段的寬度小於 δ(ε)。
Let x ∈ [c_{k−1}, c_k]. Then g_ε(x) = (1 − t) f(c_{k−1}) + t f(c_k) for some t ∈ [0, 1], so
  |g_ε(x) − f(x)| ≤ (1 − t)|f(c_{k−1}) − f(x)| + t|f(c_k) − f(x)|.
Both |x − c_{k−1}| and |x − c_k| are less than δ(ε), so both differences are less than ε, and hence so is the weighted average.
這一步的所求:把段內的誤差壓住。拆解靠的是 f(x) = (1 − t)f(x) + t f(x) 這個看似無用的恆等式——把它插進去,差就整齊地分成兩份加權。之後兩個權重非負且相加為 1,所以加權平均不超過兩者中較大的那個。要留意 x 與兩個端點的距離都不超過段寬,所以同一個 δ 管兩邊。
把曲線上的點依序連起來,就得到一個連續而且夠準的替身。∎
節點取在曲線上,接縫自動不裂 段內是兩端值的加權平均

這張圖在說 24.5 的造法:節點全部取在曲線上,所以相鄰兩段共用端點,連續是免費附送的,不必額外檢查。段內的折線值是兩個端點值的加權平均;只要段寬小於 δ(ε),兩個端點的值都離該處的 f(x) 不到 ε,它們的加權平均也就不到 ε。誤差最大的位置通常在段的中間,因為兩端剛好被釘死。

例 3同一條拋物線,兩種工具差了十倍
兩個定理都保證「切得夠細就夠準」。可是同樣的誤差要求,兩種工具各要切幾段?
  1. 取 f(x) = x² 於 [0, 1],容許誤差 ε = 0.1。先量均勻連續的 δ:|x² − u²| = |x + u||x − u| ≤ 2|x − u|,所以 δ(ε) = ε/2 = 0.05 可用。
  2. 階梯函數:段寬要小於 0.05,取 25 段(段寬 0.04)。每段取起點的值,段內誤差不超過 2 × 0.04 = 0.08 < 0.1,過關。要更準就得更多段——誤差與段數成反比。
  3. 折線函數:這次直接算誤差。在 [c_{k−1}, c_k] 上,連接兩端的直線是 L(x) = c_{k−1}² + (c_{k−1} + c_k)(x − c_{k−1}),而
      L(x) − x² = (x − c_{k−1})(c_k − x)。
    兩個因子相加是段寬 h,所以乘積在中點最大,等於 h²/4。
  4. 於是折線的誤差是 h²/4:要小於 0.1 只需 h < 0.632,切成 2 段就夠了(h = 0.5 時誤差 0.0625)。與階梯函數所需的段數相差一個數量級。(25 是照 δ 保守推出來的;直接估末段誤差 2h − h² 會發現 20 段就夠——可是仍然遠多於 2。)
  5. 差距的來源:階梯函數的誤差與段寬成正比,折線函數的誤差與段寬的平方成正比。段寬減半時,前者的誤差減半,後者只剩四分之一。
兩個定理都只承諾「辦得到」,可是實際的效率差很多。第 5 步那個「正比 vs 平方成正比」是逼近理論的核心議題:用越貼近原函數形狀的工具,達到同樣精度所需的段數就越少。下一篇要換上一種比折線更貼身的工具——多項式,而它連分段都不必。
階梯:段數多 折線:兩段就夠

這張圖在說例 3 的差距:左右兩邊是同一條曲線與同一個誤差要求。階梯只能用水平段去追一條在上升的曲線,所以每一段的落差全部算進誤差;折線的每一段本身就在上升,只剩曲線的彎曲程度沒被追上。誤差因此從「與段寬成正比」降到「與段寬的平方成正比」,段數相差一個數量級。

—— 第二階段到此結束 ——

本篇把「逼近」寫成 uniform norm 的語言,並給了兩件工具。24.4 用階梯函數:把方格切成直徑小於 δ(ε) 的小塊,每塊派一個代表值。24.5 用連續折線:把曲線上的一串點依序連起來,連續是免費的,而段內誤差是兩個端點誤差的加權平均。兩個證明的入口都是上一節的均勻連續定理——沒有那個「通用的 δ」,方格與分段就切不出統一的大小。例 3 比較了兩件工具的效率,差了一個數量級。喝口水、動一動,下一篇要換上多項式,而且是一組寫得出公式的多項式。