事件與連續插值
求解微分方程時,我們可能需要知道物體何時到達指定高度。以純量函數 表示條件,真實解 的事件時刻滿足 。已接受步的端點通常不會剛好是事件時刻。
定義 2.4.1
(稠密插值與數值事件函數)
已接受步 的稠密插值是定義在 上、在整步內逼近解的函數 ,通常由該步的數據構成。數值事件函數是 ,而數值事件是 的零點。
我們能計算的是 的零點,而非直接計算未知的 的零點。以下假設 及有關區域上的 連續,故 連續。
先檢查端點:若 或 ,該端點已是數值事件。否則,端點異號時可以二分。應使用已接受步的插值,而不是把被拒絕的試探步當成數值軌跡。若應用需要區分向上和向下穿越,可記錄符號變化的方向。
定理 2.4.2
(二分法的數值事件夾逼)
設 在 連續且 。以精確算術反覆取區間中點;若中點是零點則停止,否則保留端點異號的半區間。經過 次未停止的二分後,區間 包含 的一個零點 ,長度為 ;其中點 滿足 。
證明
(對保留區間作歸納)
原區間由介值定理包含零點。若中點不為零,它的符號必與原來兩個異號端點中的一個相同,故另一半仍然異號。歸納可知每次都保留異號,區間長度每次減半;由連續性及介值定理,新區間仍有零點。中點到該零點不超過半個區間長。這並不保證零點唯一,也不保證多個事件中找到的是第一個。
證明透視
證明控制了哪一種誤差?
上面的論證始終處理 。 的連續性只經由介值定理使用,而符號的記錄正是歸納所保持的不變量。縮小夾逼區間,只會使回報的中點靠近 的零點;插值誤差及之前累積的數值誤差,仍要另行估計,才能判斷與真實事件的距離,這正是下一節的內容。
與真實事件比較
以下的條件估計把所需假設明確寫出。
命題 2.4.3
(事件時刻的擾動估計)
設 在區間 上連續, 在 內部可微且 ,並且整個 上 。若 、,其中 ,則
證明
(在數值零點使用中值定理)
因為 ,所以 。若 ,無須再證。否則對 之間使用中值定理,得嚴格介於兩者之間的 ,使 ,故 。兩個不等式合起來給出 。
假如二分所得夾逼區間包含於 ,其中點 因而滿足 。這裏已假設真實事件存在,並非從數值異號自動得出。例如,若 上 ,且對所有 及包含兩條軌跡的集合中的 有 ,便可取 。當 很小時,事件時刻對擾動很敏感;當真實曲線與零線相切時,導數下界失效,不能套用此線性時間誤差界。
算例
例題 2.4.4
(數值零點定位準確,仍可能有偏移)
令 、,事件為 。真實事件是 。假設已接受步 的插值為 ,則 ;這個偏移可代表起始數值已有 的累積誤差。先檢查端點異號,再計算 、、,依次保留 、、。下一中點 是 的零點,比真實事件早 。此處 且 ,上述誤差界恰好取等。
例題 2.4.5
(Euler 步上的門檻事件及可計算的誤差界)
取 、,作一個步長 的 Euler 步,得 。它在 上的線性插值是 。對門檻事件 ,得 ,數值事件 ;而 ,真實事件 。兩者都在 內,而且是向下穿越。
由 、 開始二分:,保留 ;,保留 。中點 與 相距不超過 。
至於誤差估計, 在 上的導數 ,故最大值為 。又 。因此 。實際距離 ,遠在界內。此界偏保守,但其中每個常數都由這一步算出。
例題 2.4.6
(端點皆正卻藏有兩次穿越)
令 ,區間為 。兩端點值都是 ,端點測試沒有發現任何事件。在中點取樣得 ,於是產生兩個夾逼區間 與 。先處理較早的區間,其中點給出 ,算法即停於數值事件 ,不必再減半;這正是定理中的停止情況。較後的區間同樣給出 。這次額外取樣能找到兩次穿越,只因取樣點恰好落在兩者之間。
符號測試會漏掉甚麼
異號只是充分條件,不是必要條件。例如 在 的端點都為正,卻在中間接觸零; 的端點也都為正,中間卻穿越兩次。僅看端點會漏掉這些事件。額外取樣或限制步長有幫助,但沒有額外假設時,任何固定的有限取樣都不能找出所有連續函數的零點。反之,數值插值異號也不保證真實事件落在這一步內。
反例模式
數值有穿越而該步內沒有真實穿越
聲稱:若 在某已接受步上變號,真實事件函數 必在該步內有零點。再取 、、步長 的一個 Euler 步及線性插值 ,但門檻改為 。則 滿足 、,二分夾住數值事件 。真實函數 遞減,且 ,所以 在整個 上為正;真實事件 位於下一步。修正正是擾動估計的假設:必須先知道真實事件位於該區間內,或把區間擴大至包含它, 才能控制事件時刻誤差。
浮點計算應先處理端點為零的情況,直接比較符號而非相乘,以免溢出;達到時間區間容許寬度便停止。如果中點已不能與端點區分,或函數值非有限,應明確報告而非宣稱夾逼成功。
常見錯誤
(把函數值小當成時間誤差小)
在平坦零點附近, 的值很小並不說明時間誤差小。對 ,在 的值是 ,時間誤差卻是 。二分應以夾逼區間的寬度作停止準則,這才是定理所控制的量。
常見錯誤
(在被拒絕步的插值上搜尋事件)
被拒絕的試探步不屬於計算軌跡。在它的插值上夾到的事件,未必存在於較短的已接受步;已接受步的事件亦可能因此漏掉。只應搜尋已接受步的稠密插值。
練習與解答
快速檢查
(對 在 二分兩次,並寫出所得區間。)
解答 · 答案
,保留 ;,保留 。其中點 與 的某個零點(此處為 )相距最多 。
快速檢查
(若在一個同時包含真實零點與數值零點的區間上 、,數值夾逼區間包含於該區間且寬度為 ,求其中點與真實事件的距離界。)
解答 · 答案
中點與某個數值零點相距不超過 ,由擾動估計,該數值零點與真實零點相距不超過 ;所以界為 。
快速檢查
(,,其中 。事件怎樣變化?)
解答 · 答案
在 有事件,而 沒有。任意小的一致擾動也可能消除相切事件;由於 ,擾動估計所需的導數下界在該根處失效。