動機
插值要求精確重現選定樣本,另一種目標卻是在整個區間上讓最大誤差儘可能小。兩者可能不同:多項式離開樣本值,將誤差更平均地分配,反而可以降低最壞誤差。要判斷這種取捨,需要先說清楚使用甚麼範數、優化哪個量。
一致近似有一個具體的最優證書:最佳 次以內多項式的誤差,在至少 個有序點以交替符號達到最大絕對值。這個點數來自競爭多項式之差所能具有的零點數。本節用連續性、緊緻性和初等多項式事實證明兩個方向,以及存在和唯一性,不要求目標可微。
定義
定義 16.1.1
(最佳一致近似)
固定非退化閉區間 、實連續函數 及整數 。 表示次數不超過 的實多項式,包括零多項式。定義
連續性和緊緻性保證最大值存在。達到下確界的多項式稱為最佳一致近似,也稱極小極大近似:把最大絕對誤差最小化。本節不加權。
定義 16.1.2
(交錯極值點列)
對候選 ,記 、。當 ,若有
稱它們為交錯極值點列。這些點的誤差達到極值,而非插值節點上的誤差零點。次數界包括常數係數。若 ,則最佳誤差為零,唯一最佳多項式就是 ,無需正誤差的交錯論證。
定義 16.1.3
(Chebyshev 多項式)
Chebyshev 多項式由 定義。遞推 ,起點 ,證明它是多項式。當 ,首項係數為 ,在 的值交替為一和負一。
定理/命題
定理 16.1.4
(存在、交錯與唯一性)
閉區間上的每個實連續函數,在 中都有唯一最佳一致近似。若候選 的誤差 ,則它最佳,當且僅當誤差具有至少 個交錯極值點,等價於包含長度 的交錯點列。
這裏涉及整個區間及精確的極值幅度,有限網格中看到交替圖案,本身不是連續問題的證書。
推論 16.1.5
(Chebyshev 極值對應實際最佳近似)
在 上, 的唯一最佳 次以內近似為
等價地, 是唯一具有最小一致範數的首一 次多項式。在 ,相應首一餘項為
最佳近似為 ,誤差為 。
證明思路或證明
先證明最優值確實達到
證明
(由係數空間的緊緻性得出最優值達到)
取極小化序列 ,使 。去掉有限項後可假設這些誤差至多 。在區間中固定 個相異點,所有 在這些點的值都被 控制。
從多項式係數到這組值的線性映射可逆:核內多項式具有 個相異零點且次數至多 ,所以只能為零。因此係數向量在有限維空間中有界,存在收斂子序列。極限係數定義多項式 ;區間有界,各單項式有界,所以係數收斂推出一致收斂。範數的反三角不等式給出 。注意無需整個極小化序列都收斂。
交錯排除更好的競爭者
證明
(以差的零點數證明充分性)
設 具有 個交錯極值點。若 的誤差嚴格更小,令 。在 處, 強迫 ;在 處則強迫 。因此 在每兩個相鄰極值點之間變號,介值定理給出 個相異零點,與非零 次以內多項式的次數矛盾。零多項式也不具有要求的嚴格符號,所以不存在更好的 。
交錯不足時構造一致改進
證明
(以同號擾動證明必要性)
這個方向不能只看幾個局部峰值。設
它們都是緊緻集, 非空。若兩種符號都有,兩個不交緊緻集的距離嚴格為正。從 最左點出發,取其右方第一個反號極值點,繼續重複。每次轉換至少跨過該正距離,所以只能轉換有限次;若只有一個符號,就只有一組。
這樣將有序極值集分成連續的同號組,組間符號交替。在下一組首點之前,上一組有最後一個極值點;緊緻性和正距離排除了同號點向反號點聚集的可能。因此相鄰組之間存在不含 的非空間隙。若不存在長度 的交錯點列,組數只能是 。
在每個間隙中選一個分隔點 。取
讓它在第一組與 同號。跨過間隙時兩者都翻號,所以在全部極值組同號。若僅一組,取適當常數。 次數至多 ,在 上沒有零點,故緊緻性給出 。另記 。
連續性保證 有相對開鄰域 ,其中 同號、、。取足夠小的 ,使 ,相減便不會越過零,於是 內
若補集 非空,它緊緻且不含極值點,所以存在 使該處誤差至多 。再要求 ,便有
兩個一致上界合起來說明 的全局誤差嚴格更小。因此最佳正誤差多項式必須具有足夠交錯。關鍵不僅是移動最壞點,還要保護其他位置,避免產生新的更壞誤差。
證明透視
區塊數目與次數在哪裏相遇
必要性的證明是逆否命題:由交錯不足,構造嚴格更好的多項式 。它需要三個不同的成分,各自用到不同的假設。
第一,把極值集合 分成至多 個同號區塊。這裏 的連續性不可缺少:它使 與 緊緻且不相交,因而相距為正,於是區塊只有有限個,而且相鄰區塊之間有真正的間隙。 正是「不存在長度 的交錯點列」的否定形式。
第二是關鍵一步:每個間隙取一個分隔點,得到次數 的 ,所以 是 中容許的方向;而且它在整個 上與 同號,不只是在幾個看得見的峰值處。次數界只在這裏用到,而且與充分性證明的計數相同:在那裏, 個交錯點迫使次數至多 的多項式有 個零點。
第三是步長。在 附近,因為符號一致,且 防止越過零,減去 會降低 。遠離 時, 的緊緻性給出嚴格餘量 ,而 使擾動留在餘量之內。沒有這個餘量,一個在 之外但 接近 的點便可能成為新的最壞點。
最佳多項式為甚麼唯一
證明
(以平均兩個最佳近似證明唯一性)
若兩個不同多項式 都最佳、誤差為正數 ,其平均也最佳:凸性給出誤差至多 ,最小性又迫使等號。在平均誤差達到 或 的點,原來兩個誤差都必須等於同一個端點,因為兩個 中數的平均只有這樣才到達端點。因此 在平均的所有極值點相同。必要性給出 個這種點,迫使 恆零,矛盾。零誤差情況已直接處理。
從節點乘積上界到真正的優化解
證明
(Chebyshev 餘項是最優的)
與 的首項抵消,所以 次數至多 。其誤差在有序餘弦點達到 個交錯極值,定理給出最佳性及唯一性。每個首一 次多項式都可寫為 、,所以首一極值問題等價。仿射變換給出一般區間公式,其中係數恰保證首項為一。
例題詳解
例題 16.1.6
(二次函數的最佳直線是常數)
在 近似 ,取 。誤差介於 和 ,並在 取 。三個交錯極值認證它不僅是最佳常數,也是 中唯一最佳。端點插值給出直線一,最大誤差為一,是最優值的兩倍。若在 插值,則恰得到 。所以插值與最佳近似可以相同,卻不是必然。
例題 16.1.7
(最佳二次近似不一定有二次項)
,所以 在 中的最佳近似為 ,誤差為 。餘項在 依次為 ,也認證它在較小空間 中最佳。規定的是次數上界,不要求實際使用最高次項。
例題 16.1.8
(不可微函數也有交錯證書)
對 ,取 。令 ,則
因此誤差絕對值至多 。在 ,誤差從負開始交替,任取連續四點便認證最佳二次近似;完整五點甚至認證它在 中最佳。零點處的尖角不影響定理,因為只要求連續,不要求導數。
常見錯誤
反例模式
積分誤差範數小不能控制峰值
在 令 ,其中 。零多項式的一致誤差為一,但平方 誤差為 ,趨近零。優化積分範數與優化最大誤差是不同問題。狹窄連續峰值對積分平均或粗網格可能幾乎不可見。
常見錯誤
(變號不等於交錯)
交錯要求誤差在每個列出的點都達到完整的 (其中 ),而不只是變號若干次。對 上的 與常數 ,誤差 在 的值為 :三點的符號交替,但 。其範數 大於最優值 ,所以即使只在常數中比較,它也不是最佳近似。
誤差的任何交錯符號模式都給出最佳誤差的下界,交換算法正是藉此監察進度。
自然延伸的下一個問題
不是最佳的候選多項式還能證明甚麼?
誤差的任何交錯符號模式都給出最佳誤差的下界,交換算法正是藉此監察進度。
若 在有序點 處取符號交錯的非零值,則 :若某競爭者 的誤差更小, 在每一點都與 同號,於是有 個零點。連同上界 ,便把 夾在中間。對上面的 ,有 。Remez 交換算法透過移動這些點來收窄這個區間。
定理提供證書,不是尋找極值點的完整數值算法。網格最大值可能漏掉中間峰值。若誤差已知是 -Lipschitz,且任意點離最近檢查網格點至多 ,三角不等式給出 。這才是有依據的網格到連續域上界;單有連續性不給出明確數值餘量。
概念視角結構
零點規定插值,交替峰值認證最優
插值在指定節點使誤差為零,極小極大近似在由解決定的位置讓最大誤差交替。因此最佳多項式可以不通過樣本值,卻降低最壞誤差。兩者都利用多項式維數,使用方式卻不同。
總結
係數空間的緊緻性證明存在,交錯極值通過零點數排除更好競爭者。反之,符號組太少時可用多項式擾動實現一致改善,再用平均證明唯一。Chebyshev 餘項解決首一極值問題,並產生冪函數的顯式最佳近似;有尖角的連續目標也適用。
練習
快速檢查
(連續實函數在緊緻區間的最小最大值為 。求最佳常數及誤差,包含 ,並證明唯一性。)
解答 · 答案
常數 的最大誤差為 ,唯一最小值 在 達到。更小半徑無法同時覆蓋兩個極值,而最小半徑強迫中心為中點。若 ,精確常數是唯一零誤差選擇。
快速檢查
(求 上 的最佳二次以內近似,展開係數,列出四個交錯極值點及其誤差。)
解答 · 答案
最優首一餘項為 。因此近似為 ,誤差為 。在 ,誤差依次為 ,認證二次最佳性。
快速檢查
(證明 是 上 的最佳二次近似。比較它與節點 插值的最大誤差。)
解答 · 答案
誤差為 ,範數為 。在 交替達到正負極值,故對二次空間適用定理。指定三節點的插值為 ,誤差 在 與零之間,範數為 ,是最優誤差的兩倍。
快速檢查
(對一次以內近似,兩個交錯極值點是否足夠?檢驗 上目標 、候選 ,並解釋定理需要的零點數。)
解答 · 答案
候選誤差為 ,端點極值為一和負一,但候選範數誤差為一,而零多項式完全準確。兩個點只強迫競爭差有一個零點,非零一次多項式可以做到。一次空間需要三個交錯極值點,強迫兩個相異零點才產生矛盾。