為甚麼停止準則需要誤差界?
迭代求解器輸出的是向量,不是未知的誤差。殘差看似細小,要先說明尺度,以及矩陣如何把誤差轉成殘差,才可判斷它有多大意義。有限元素問題常關心能量範數;相對於未加權的歐幾里得(Euclid)範數,預處理矩陣可提供更合適的殘差尺度。以下推導適用於任何近似解,不限於共軛梯度法產生的向量。
設 對稱正定(SPD),, 是近似解。記 、,並定義 和 。無須顯式求逆:解 後即可用 求後者的平方。
定義 1.6.1
(譜等價)
假設已知常數 ,對所有 均有
這等價於 的特徵值都在 內。界不必最緊,但必須確實適用於所用矩陣。
定理 1.6.2
(由殘差控制誤差)
在 (1) 下,對任意 ,
若 ,相對能量誤差亦滿足
證明
(把預處理矩陣對角化)
令 。由 ,誤差平方為 ,預處理殘差平方為 。把對稱正定矩陣對角化為 ,並令 ,則 ,。每個特徵值 都滿足 ;對各座標求和得 ,即 (2)。
把 (2) 用於近似解 (其殘差為 ),可知 介於 與 之間。以分子的上界除以分母的下界,反之亦然,即得 (3); 保證分母非零。
證明透視
平方根從何而來?
證明只用到譜包含條件 (1),而且只透過 的特徵值使用它。決定性的一步是變量代換 :它把誤差與預處理殘差放進 的同一組標準正交特徵基,在相同的平方座標上分別配上權 與 。逐個座標比較 與 ,便在平方範數上得到介於 與 之間的因子,因而範數本身出現平方根。
相對界 (3) 需要另一個獨立的想法: 本身就是一個殘差為 的近似解,所以同一不等式也控制分母 。常數合成 ,是因為分子的上界與分母的下界配對。沒有任何一步涉及 如何得來,所以這些界對任何方法的任何迭代值都成立。
所以在精確算術下, 是保證相對能量誤差不超過 的充分停止條件。未通過這條充分條件並不代表實際誤差一定超標:保守的譜界可能使區間很寬。若 ,唯一解為零,(3) 的相對誤差分母為零,應改用絕對誤差界。
考慮兩種偏差的可實施證書
電腦可能儲存近似殘差 ,以及方程 的近似解 。在 Krylov 法的遞推更新中,儲存的殘差可能偏離 。重新計算可以減少偏差,卻不能自動消除浮點誤差。因此,我們明確假設已提供有效界,而非把儲存值當成精確殘差:
此處 是所表示數據與迭代向量的數學殘差。兩個偏差界須由其他方法提供,例如經驗證的誤差分析或驗證算術;浮點輸出本身不自動成為有效界。設
定理 1.6.3
(包含偏差的絕對誤差證書)
在 (1)、(4) 下,若 (5) 中的量精確計算或向外取界,則
特別是,若上界不大於指定的絕對容差,便證明誤差符合容差。
證明
(預處理範數中的兩次三角不等式)
範數的反三角不等式給出
由 ,對角化可得 。又 ,因此 。代入 (2) 即得結論。此結果包括 ,不要求 為正。實際計算時,對 、 和常數取外界亦須考慮捨入;普通浮點計算的顯示值不能直接當作證明。
內層求解偏差與殘差偏差作用不同:前者量度 解得多準,後者比較儲存殘差與 。只有其中一項細小,不能取代另一項的界。若要相對誤差證書,可同樣獨立地為分母 求一個嚴格正的下界;不要除以可能為零的下界。
例題 1.6.4
(明確計算兩項偏差)
設 、、,以及 。廣義特徵值為 和 ,可取 、、。真實殘差為 。假設計算儲存了 和 ,則
故 ,由 (6) 可知能量誤差介乎 與 。已知精確解 ,因此 ,確在區間內。實際求解時通常不能用真實殘差和精確誤差作這種比較,須另外取得有效的偏差界。
例題 1.6.5
(共軛梯度迭代值的相對界)
沿用 、、 及 ,但改用精確算術,故 、。此時 ,,所以比值為 。不等式 (3) 給出
由於 ,實際值為 。若要用充分準則證明相對誤差不超過 ,比值須降至 。
例題 1.6.6
(精確預處理消除差距)
在邊界情況 中,條件 (1) 以 成立,(2) 變成恆等式 。對 及 ,殘差 給出 ,正好等於 。此界是精確的,但計算 需要解一次與 相關的方程,而那正是原問題。
常見錯誤
(估計的特徵值不是有效的界)
(2) 的上界需要一個真正是 的譜下界的常數 。由少數 Lanczos 步或粗略模型得到的估計可能把它高估。在第一個例子中,真值是 ;若改用 ,會得到 ,小於實際誤差 ,所得證書便是錯的。
反例模式
殘差小,誤差卻可以大
取 、、。此時 ,且 ,但 。矩陣在第二特徵方向壓小了誤差所產生的殘差。這不違反 (2):相關的譜下界很小,而且必須指明範數及尺度。
練習與解答
快速檢查
(精細度:設 、,其中 。甚麼誤差使 (2) 的各邊取等號?)
試考慮沿單一特徵向量的誤差。
解答 · 答案
若 位於 的特徵空間,則 ,而 ,誤差上界取等號。位於 特徵空間的誤差則使下界取等號。所以只用這兩個端點界時,兩個常數都不能改進。
快速檢查
(容差:設 、、。(6) 是否證明能量誤差不超過 ?)
計算 (6) 的上端點。
解答 · 答案
上界為 ,所以可以,前提是所有列出的界都有效,而且所顯示的算術已安全地計算。
快速檢查
(遺漏偏差:設 、、、、。內層求解精確,是否足以證明誤差為零?)
比較儲存的殘差與 。
解答 · 答案
不足以。內層偏差為零,但 ,所以殘差偏差 。實際誤差為一,而 (6) 正確地給出區間 ;忽略 會產生錯誤的零誤差證書。
快速檢查
(下界:為甚麼上界證書很小,並不表示 (6) 的下界為正?)
考慮 的情況。
解答 · 答案
若 ,證書的下端點為零。這時已有資訊既與精確解相容,也與非零誤差相容;它並未說明實際誤差是否為零。
這些界針對固定的 SPD 系統,並假設已給定確定性的有效包圍界。它們不會自動提供譜界或驗證浮點計算,也不分析可變或不定預處理矩陣,更不保證線性系統對原微分方程的離散化誤差。