引言
有限差分把微分方程化為代數方程,但我們仍須求解所得的線性系統。本節以正方形上的 Dirichlet Poisson 問題為例,分清三個對象:連續問題的精確函數、網格方程的精確解,以及迭代所得的近似解。前兩者之差是離散誤差;後兩者之差則是線性求解器誤差。
動機
假設薄板的邊界溫度已知,板內有穩定熱源,適當規範化後可用 建模。五點差分格式比較每個內部節點與四個鄰點的數值。即使某鄰點緊接內部未知量,邊界值仍是已知數據。我們會證明離散系統解的存在唯一性,估計網格誤差,並解釋簡單迭代為何在細網格上可能很慢。
定義與設定
定義 3.5.1
(五點 Dirichlet 問題)
令 ,,,網格點為 。當 或 等於 或 時,指定邊界值 。對 ,定義
離散方程為 ,其中 。上式直接保留邊界節點;若矩陣只作用於內部未知量,必須把已知邊界項移至右邊。下文最大範數包括邊界節點。對零邊界向量,內部歐氏範數為 。
定義 3.5.2
(Jacobi 迭代)
由任意內部初值 出發,保持邊界值固定,並同時更新所有內部點;右邊只使用第 步的值:
這是把內部方程 對中心值解出,而鄰值取自上一次迭代。
定理/命題
定理 3.5.3
(最大值原理與二階誤差)
若每個內部節點均滿足 ,而邊界上 ,則整個網格上 。因此離散 Dirichlet 問題恰有一解。設 滿足 及邊界條件 ,並有 、。若邊界值及 的取樣均精確,則
定理 3.5.4
(正方形上 Jacobi 迭代的收斂性)
固定 時,從任何內部初值開始的 Jacobi 迭代都收斂至離散解。若 是第 次迭代值減去精確離散解,則
此因子依賴網格,當 時趨近一;因此此估計不能保證與網格無關的迭代次數。
證明或證明思路
證明
(鄰點傳播與單向障礙函數)
先證最大值原理。假設正的最大值出現在內部節點。網格節點經由鄰點步可以連通,所以每個內部節點都有一條鄰點路徑通往邊界。四個鄰值均不大於它,故 減去四鄰值之和非負;假設又使該差非正。因此四個鄰點都取相同的最大值。沿通往邊界的路重複此推理,便與邊界非正矛盾。將此原理用於兩個解之差及其相反數,得到唯一性。內部系統是方陣,核空間只有零向量亦保證對每個右端項都有解。
沿兩個座標方向分別作中心 Taylor 展開,對精確解的取樣得到
設 ,。雖然 在水平兩邊不必為零,但在整個邊界非負。它只依賴 ,所以 方向的差分為零,而 方向的差分對二次式 精確;因此恰有 。因此 且邊界上 ; 亦然。最大值原理給出 ,即得定理常數。同一論證也表明:零邊界網格向量若滿足 ,則 。
證明透視
邊界上不必為零的障礙函數
比較論證只需要單邊的邊界資訊。由於邊界上 而 ,不論 是否為零, 與 在邊界上都非正。正因有此自由,障礙函數可以只依賴 :五點算子作用其上時化為一維二階差分,而它對二次式精確,所以不會產生新的誤差項。
假設在三處起作用。 的光滑性提供相容性界 。精確邊界數據令 在邊界為零。網格經鄰點步連通,使最大值形成的平臺能一直傳播到邊界。由於殘差界是雙邊的,最大值原理要用兩次,分別作用於 與 。常數 是 Taylor 定理的 乘以 。
Jacobi 估計依賴另一種工具:以正交特徵向量基底代替比較論證。
證明
(正弦模式把 Jacobi 誤差對角化)
離散解是 Jacobi 更新的不動點,把它減去。邊界誤差為零,內部誤差滿足 。正弦陣列 ,,構成內部向量空間的正交基底。Jacobi 誤差矩陣作用於各陣列時,只會乘上
其最大絕對值為 ,在 與 均達到。由於 ,而正弦在 、 為零,邊界零值得以保持。把 按正交基底展開,每一步各係數都乘上 ,再用 Parseval 恆等式便得範數估計。高頻模式可以一邊衰減一邊交替變號;收斂並不表示每點都單調變化。
概念視角算法
Jacobi 即顯式偽時間推進
對輔助熱問題 (邊界數據相同)使用顯式前向時間格式,以五點 Laplace 算子及比例 :
取 ,即五個權重全部非負的最大比例,中心權重 為零,且 ;這一步正好就是 Jacobi 更新。換言之,用 Jacobi 解 Poisson 系統,就是以保持權重非負的最大步長,把熱方程推進至穩態。偽時間步長為 ,而最慢的光滑模式衰減所需時間與 無關,所以迭代次數按 增長。事實上 。
例題
例題 3.5.5
(只有一個內點的完整計算)
取 、零邊界值及 ,則 。唯一內點處 ,格式給出 ,故 ,恰為精確取樣值。這裏兩個純四階偏導數皆為零;此多項式的精確性不能推廣到所有光滑解。
例題 3.5.6
(代數殘差控制甚麼誤差)
設 具有正確邊界值,且內點上 。若 是精確網格解,則 的邊界為零,故 。這是求解器誤差,不能單獨當作 的誤差;應加上離散誤差界。若求解器回報的是未縮放矩陣 的殘差,應先除以 才能使用此估計。
例題 3.5.7
(收斂為何仍可能緩慢)
當 ,最慢 Jacobi 因子為 ;當 ,它約為 。因此在較細網格上,一百次迭代只能把最差誤差分量減少約 。對每個固定網格說「Jacobi 收斂」是正確的,卻不能單憑這句話判斷網格加密的計算成本。更快方法需要另行分析。
常見錯誤
常見錯誤
(把邊界值從右端項漏掉)
當矩陣只作用於內部未知量時,內部節點的每個邊界鄰點都會在右端貢獻已知項 。漏掉這些項等於解零邊界數據的問題,那是另一個邊值問題,而不是同一問題精度稍差的版本。
常見錯誤
(在 Jacobi 掃描中混用新舊值)
Jacobi 右邊只使用第 次迭代的值。若就地覆寫陣列,令部分鄰點已是第 次的值,所得的是 Gauss–Seidel 掃描。那是另一種方法,上面的因子 不再描述它。
反例模式
更新量小不代表誤差小
常見的停止準則聲稱:一旦 低於容許值,迭代值與離散解的距離也同樣小。取 ,並設誤差在最慢模式上:,故 。由於更新量等於 ,
更新量通過 的容許值,誤差卻約為更新量的二千倍。修正要用到譜:誤差矩陣 對稱,特徵值的絕對值不超過 ,所以 的每個特徵值至少為 ,從而
在此例中這個界給出 ,是精確的。
此外,上述誤差定理不能不經額外論證便套用於不光滑解、不精確數據、不規則區域或非正方網格。
總結
五點算子滿足離散最大值原理;配合二次障礙函數,可在明確的光滑條件下證明唯一性與二階節點誤差界。Jacobi 在每個固定正方形網格上收斂,但其最差收斂因子隨加密趨近一。離散誤差與求解器誤差必須分開計算。
練習
快速檢查
(在單位正方形取 、 和邊界值 。求內點值並解釋為何它是精確值。)
記得使用四個邊界鄰點。
解答 · 答案
四個鄰點值為 、、、,平均數為 。調和函數 滿足給定邊界,其取樣也滿足差分格式;由唯一性,數值即精確值。
快速檢查
(設 、、。求定理給出的離散誤差界。若具正確邊界值的近似解 在內點滿足 ,求總節點誤差界。)
以三角不等式合併兩種不同的誤差界。
解答 · 答案
離散誤差至多為 ;代數誤差至多為 。因此在定理所列光滑和精確數據條件下,總節點誤差至多為 。
快速檢查
( 時求模式 的 Jacobi 因子。經兩次迭代後,該誤差模式有何變化?)
因子的符號和絕對值都重要。
解答 · 答案
。每次迭代使該模式變號並將振幅減半;兩次之後成為初始值的 。只要絕對值小於一,負因子並不妨礙收斂。