從譜空間走到實際計算
譜方法用遍及整個區間的基底函數表示近似解;要真正計算,還須決定怎樣取得係數,以及網格無法分辨的頻率會發生甚麼事。考慮實值或複值、週期為 的函數,取等距網格。先取奇數個網格點,避開偶數網格需要另行指定的 Nyquist 頻率慣例。
定義 5.6.1
(離散係數、三角插值與譜導數)
設 ,,並取 ,。對樣本 ,定義
樣本的譜導數是向量 ,其分量為 。
係數的正規化和指數的正負號都不可隨便更改。我們先微分插值多項式 ,再取網格值。對選定頻率範圍內的三角多項式,這給出精確導數;但對產生同一組樣本的任意函數,未必如此。
為甚麼插值公式成立?
定理 5.6.2
(離散正交性與插值)
若整數 都在 ,則 在 個網格點的平均值,在 時為一,否則為零。因此每個樣本向量都滿足 ,而且其插值函數在 、 生成的空間內唯一。
證明
(以等比和證明)
這個平均值是公比為 的等比和:當 整除 時為一,否則為零。由 ,只有兩指數相等才會整除。同理,反向求和得到
因為這 個連續整數恰好代表模 的所有餘數。代入係數公式便得 。若兩個插值函數有相同樣本,用正交性恢復其差的各係數:每個係數都是零樣本的離散平均,故全為零,所以兩者相同。
證明透視
頻率窗口在證明中的作用
論證靠兩個事實:除非 整除頻率差,等比和為零;而窗口 恰好含 個連續整數。窗口用了兩次,方向相反。對正交性,它夠小: 排除了 的所有非零倍數。對插值,它夠大:它與模 的每個剩餘類都相交,所以對 的和是完整的和,給出 。唯一性只用到第一個事實。
若把窗口放寬,第一個用途便失效。頻率 與 相差 ,所以在五點網格上兩個指數函數重合,任何一個的係數都無法恢復,這就是混疊。因此唯一性只在選定的有限維空間內成立,而不是在所有三角多項式之中。
用係數求導十分直接:一階導數把 換成 ,二階導數則換成 ;再反變換便得網格值。快速 Fourier 變換能加快這些求和,卻不會改變插值函數,也不能補回網格沒有解析的資訊。
反例模式
偶數網格破壞對稱窗口
很容易以為偶數個網格點也可沿用同一公式,取窗口 。取 ,即 ,以及 的樣本 。由於 ,五個頻率共用四個網格點,離散平均給出 ,其餘為零。所得 的樣本是 ,為數據的兩倍,插值失敗;而 在每個節點均為零,唯一性也失敗。修正方法是 Nyquist 慣例:在偶數網格上,兩個頻率 各取權重 ,此例便還原為 。
熱方程及其能量
對週期邊界的 ,其中 ,空間配點後得到常微分方程 。這裏 指套用同一譜導數兩次。由於 已屬於 、 生成的空間,第二次套用再把係數乘以 。網格函數以 度量。
命題 5.6.3
(半離散能量衰減)
設 滿足 ,。則
而且平均係數 不隨時間改變。
證明
(由離散 Parseval 等式證明)
第一個等號是離散 Parseval 等式:寫 ,把 展開為對 的二重和,對 取平均,再用剛證明的正交性,只保留 的項。各係數滿足 ,因此
對 求和得能量恆等式;取 則得 。
概念視角代數
把譜導數看成反對稱矩陣
把定義作用於單位樣本向量,可把 寫成明確的循環矩陣:當 為奇數時,
各元素為實數,交換 與 時變號,所以 ;其特徵向量是網格上的指數函數,特徵值為 。記 ,反對稱性不用係數也給出能量衰減:。
平均值模式保持不變,其餘已表示的模式衰減。這是在精確算術下、只離散空間的結論,不能單憑它推斷未解析初值的準確度,也不能推斷某個時間積分法必定穩定。若用步長 的向前 Euler,每個係數乘上 。因此所有模式均不放大的充要條件是 。向後 Euler 的因子則是 ,對任何正步長均不放大;但時間誤差仍須控制。
常見錯誤
(把半離散衰減搬到時間步進法上)
不等式 是常微分方程組的性質,並非積分它的方法的性質。取 、,向前 Euler 步長 ,模式 每步乘以 ,振幅大小每步變為三倍,而半離散能量卻在衰減。完全離散的方法需要自己的條件,這裏是 ,或改用隱式方法。
例題 5.6.4
(分開空間誤差與時間誤差)
設 、,初值為 。兩個頻率都在空間中,半離散問題的精確解為 ;對這組初值,它也等於連續解的樣本。若用向前 Euler,,一步後兩個振幅變為 和 ;該時刻精確振幅卻是 和 。網格雖解析了初始函數,時間步長仍帶來明顯誤差。
混疊不是微小的捨入誤差
例題 5.6.5
(兩個不同波形,完全相同的樣本)
在同一五點網格上,,因此 。由 的樣本得到的插值函數是 ,計算導數為 。真實導數卻是 。在 ,兩者分別是 和 。只使用這些樣本的任何算法都無法判斷原來是哪個波形。
即使相乘前的函數都已表示,相乘也會產生同樣問題:,但在五點網格上 。因此逐點相乘後再插值得到 ,而不是原來含頻率四的多項式。針對非線性運算設計的補零和濾波可以處理混疊;僅僅對乘積做快速變換不會自動消除它。
常見錯誤
(把 當成任何被取樣函數的導數)
譜導數微分的是插值函數,所以只有當被取樣的函數屬於 、 生成的空間時才精確。對五點網格上的 ,在 的計算值是 ,真實導數卻是 。快速變換或雙精度都不能改變這一點:誤差來自網格無法表示的頻率,只有加密網格或採用已解析的表示才能消除。
甚麼條件下加密網格有用?
命題 5.6.6
(由係數尾和控制網格導數誤差)
設 ,且 、;令 為 中與 模 同餘的唯一整數。則
證明
(把頻率摺回窗口來證明)
絕對收斂容許取樣及逐項微分,所以 。在網格上 ,因此 。用正交性並交換絕對收斂的求和,得 。於是
相減得 。 的項為零,因為此時 ,由此得第一個不等式。當 ,有 ,所以 。
當 ,右邊尾和趨向零。係數衰減更快可以帶來更快的收斂,但「譜」一字本身不保證指數收斂,尤其當週期延拓不光滑。此估計假設樣本精確,並未計入捨入誤差。
例題 5.6.7
(等比係數給出等比收斂速度)
取 。令 ,把兩個等比級數相加得
假設成立:。尾和為 ,所以界變為
當 (),界為 ,並不比平凡界 好:網格這麼粗時,估計沒有提供資訊。 時界為 , 時為 , 時為 。每多加一對網格點,界大約減半,這就是從係數繼承的等比速度。
練習與解答
快速檢查
(當 , 樣本的譜導數是甚麼?)
把頻率對 取餘數。
解答 · 答案
在節點上 ,所以插值函數是 ,導數樣本是 。真實導數樣本則是 ,一般不同。
快速檢查
(當 、,向前 Euler 步長 ,求 模式的因子。)
每個模式乘以 。
解答 · 答案
因子為 ,反覆步進時該模式的大小會增長。半離散能量不等式不能照搬到這個不穩定的時間離散法。
快速檢查
(譜導數對常數向量做甚麼?)
找出唯一非零的係數。
解答 · 答案
只有零頻率係數非零,而它乘以 ,故結果為零。在熱方程中同一模式保持不變,對應離散平均值守恆。
快速檢查
(在五點網格上,比較 的樣本平方後再插值,與先插值再平方。)
利用 。
解答 · 答案
的插值函數就是 本身,所以先插值再平方得 ;樣本平方後再插值則得 。它們在五個節點相同,但一般點不同,所以插值和相乘不可交換次序。