為甚麼係數精度重要
譜方法用有限個波來近似函數。即使知道應保留哪些模態,其係數仍由積分定義;電腦通常只看到有限個位置的測量值。若位置不等距,簡單平均會讓每個測量值有相同影響力,即使它們代表的區間長度不同。我們必須說明數據近似甚麼積分,以及每個樣本應佔多大權重。
以下採用簡單的左端點法。這不一定是最佳求積法,但它的誤差可以直接證明,權重也清楚反映網格幾何。它適用於任何有限分割,毋須假設相鄰區間長度相若;它是離散傅立葉(Fourier)係數的加權推廣:等距網格上的權重均為 ,便回到通常等權的離散傅立葉變換。以下估計控制 近似誤差,不能自動控制最大誤差或導數誤差。
連續係數與加權求積法
設 是 上端點值相同的複值函數,寫作
整數 決定保留的空間。
定義 2.3.1
(加權左端點傅立葉求積法)
取有限分割 ,令 ,。對 ,假設觀測值為 。定義
所以 使用精確樣本,但積分由數值求積近似; 還包含測量誤差。權重 均為正,總和為一。
的樣本代表其右方的區間;若改用中點或梯形法,規則會改變,必須另行分析誤差。
定理 2.3.2
(有限網格上的係數界)
假設 ,且在 上 。對每個整數 ,
若每個 都滿足 ,則 。更一般而言,該量至多為 。
證明
(在每個左端點凍結被積函數)
令 。由 和 ,三角不等式給出
從求積值減去積分,按網格分段並逐段估計:
因為 和 ,便得到第二個界。噪聲的貢獻為 ,其絕對值至多為 ;在一致誤差界下,此值至多為 。加權 Cauchy–Schwarz 不等式及 給出均方根界。這些是確定性界,並未假設噪聲獨立或均值為零。
證明透視
每個假設在係數界中的位置
唯一的關鍵一步,是在 右方的單元上把 與其凍結值 比較。 的 Lipschitz 常數提供 ;之所以需要上界 ,只因相位 亦以速度 移動,並與 相乘。在一個單元上積分距離 得到 ,所以估計是單元長度平方之和:一個寬單元會受到平方的懲罰,但毋須要求相鄰單元長度相若。步驟 收結論證,代價是放棄這項資訊。噪聲部分完全不用正則性,只需要權重為正且總和為一。因此加密網格會令每個固定 的求積項縮小,而 的上界則原封不動地傳遞下去。
先做精確分解,再取上界
在上述歸一化內積下,指數函數構成標準正交系,而有界的 屬於 。
定理 2.3.3
(精確誤差分解)
對每個三角多項式 ,
證明
(殘差的正交性)
寫 。對 , 與 的內積為 ,所以第一項與保留的指數函數所生成的空間正交,而第二項正屬於該空間。畢氏(Pythagoras)定理給出 ,再由標準正交性得最後一個範數為 。
取 便得到
再使用三角函數系的完備性,第一項等於 。這是 Parseval 尾和,使用的是精確係數。有限分解本身只需要正交性,不需要完備性。第二項可逐個係數拆成
兩個複數誤差可能互相增強或抵消。
常見錯誤
(把求積誤差和噪聲誤差的平方直接相加)
很容易仿照精確分解寫出 。但那個恆等式來自函數的正交性,兩個複數沒有這種性質。若兩個誤差分別為 和 且方向相同,真正的平方是 ,而不是 。應先用三角不等式估計和的模,然後才取平方。
令 和 ,三角不等式給出可用的誤差界
固定 時, 令求積部分趨零;固定的噪聲上界則不一定趨零。若同時令 和 ,只有整個係數誤差和也趨零,上式才證明收斂。例如,固定 並採用一致噪聲界 時,充分條件是 和 。這些條件充分而非必要;實際誤差可能抵消,更好的求積法也可能改進估計。有限多項式在每點的絕對誤差可由各係數誤差的絕對值之和控制,但 尾項本身不提供逐點尾項界。
算例:三個不等長單元
例題 2.3.4
(虛假的低頻係數)
取 ,分割點為 、、、。單元權重為 ,樣本為 。當 ,精確係數是 和 。求積法卻給出
而 的值依次為 ,所以
這裏沒有截斷誤差:。樣本沒有噪聲時,正交性給出精確的平方誤差
頻率 的係數恰好精確,因為相應被積函數是常數;這不代表其他計算係數也精確。這裏 ,,而 ;定理給出零頻誤差上界 ,大於實際值 。即使存在很大的網格間隙,界仍成立;但很大的上界不能證明誤差小於某個小容許值。
係數的標籤不能消除混疊
反例模式
不同函數有相同樣本
取等距節點 ,並令 。每個樣本都等於 ,與常數函數的樣本一樣。若 ,精確投影 為零,但取樣求積卻給出 。因此,即使沒有噪聲,也會產生虛假的常數分量。在 下,其他保留的離散係數也為零,重建多項式便是 ,歸一化 平方誤差為 :其中一單位來自精確截斷,另一單位來自係數誤差。
這個函數族隨 改變,其 Lipschitz 常數為 ,因此不違反以下結論:固定一個 Lipschitz 函數及固定頻率時, 會令求積收斂。不等距節點可能消除這個例子的精確樣本相同現象,但有限測量仍需對未知函數作假設;非均勻性本身不是消除混疊的定理。
常見錯誤
(以相等權重平均不等距樣本)
把 換成 ,近似的是對節點密度的積分,而不是對 的積分。在 上放 個等長單元,在 上放 個,並取 ,所以 。當 ,網格尺寸趨於零,加權求積收斂到 ;但等權平均由左半段的 個樣本主導,收斂到 在那裏的平均值 。加密網格不能修正錯誤的權重。
噪聲、微分和解讀
例題 2.3.5
(常數偏移在加密後仍然存在)
假設每個測量值都帶有相同的加性誤差 。則
當 ,權重之和為一,所以無論分割多細,零頻誤差都恰為 。在等距網格上 ,而當 不整除 時 ,所以偏移只留在常數模態。在三單元分割 上,偏移卻會洩漏:
每個的模平方為 。取 時,單是噪聲就對係數誤差貢獻 ,小於由 得出的粗略上界 。概率噪聲模型可能給出較小的典型誤差,但那需要額外假設,不能從確定性界直接得出。
例題 2.3.6
(為光滑信號解讀誤差界)
取 、、 的等距網格,以及 。此時 ,而由於 ,尾項為零。在等距網格上 ,所以 ,即 、。誤差界為
即 誤差至多約 。這個界在此遠非精確。對 ,每個被積函數 都是 的 的組合,而等距左端點法能精確積分這些函數,所以 。剩下的只有噪聲,其貢獻至多 ,即 誤差小於 。誤差界仍然成立;更精確的數值用到了這個特定求積法的精確性。
對計算出的多項式求導時,係數誤差的影響可能更大。對非負整數 ,正交性給出
這裏 時也取 。這是兩個有限多項式之間的恆等式。除非 具有所需的弱導數且導數尾項另受控制,否則它不是 的導數與重建函數導數之差的界。因子 說明微分為甚麼會放大微小的高頻係數誤差。
習題
快速檢查
(對 和分割 ,計算 、,並與精確係數比較。)
單元權重為 。
解答 · 答案
。此外 ,但 。不等長區間的權重不可忽略;能精確積分常數不表示能精確積分振盪的被積函數。
快速檢查
(假設 、、 且 。用最大網格界求 的保證上界。)
用三角不等式合併求積部分與噪聲部分。
解答 · 答案
求積界為 。噪聲貢獻至多 ,因此由三角不等式可得 。實際誤差未必達到此上界。
快速檢查
(取 、保留 ,並假設計算出的非零係數只有 及 。求精確的歸一化平方誤差。)
使用精確誤差分解。
解答 · 答案
精確投影為零,且 。正交性給出 。
快速檢查
(次數為 的多項式中,僅有的係數誤差為 及 。求計算多項式與 之差,以及兩者一階導數之差的歸一化 平方值。為甚麼後者不一定是近似 的誤差?)
微分把 的係數乘以 。
解答 · 答案
多項式的平方誤差為 。微分使常數誤差消失,並把第二模態誤差乘以 ,因此平方誤差為 。若要判斷 的誤差,還必須考慮被捨去尾項的導數,並先證明該導數有意義。
延伸閱讀
本節只處理一維週期區間上的確定性一階求積。高階及自適應求積、多維取樣、浮點捨入、統計噪聲模型及穩定的非均勻快速變換都需要另行分析。