步長小可能帶來錯覺
迭代解線性方程組會產生一連串近似值,並非經過指定次數運算便一定得到精確解。常見的停止準則是檢查相鄰兩個儲存向量是否接近。這很有用,卻可能誤導:即使距離解仍遠,捨入也可能令計算值不再改變。要解讀小步長,我們既需要理想迭代的收斂界,也需要計算單步誤差的界。
令 T(x)=Bx+c 定義於 Rn,採用固定向量範數及其誘導矩陣範數。假設已知 ∥B∥≤q<1。唯一不動點 x∗ 滿足 x∗=Bx∗+c。我們把儲存的 B,c 視為精確數據;這些數據與原本物理或數學問題的差異須另行分析。電腦計算滿足
yk+1=T(yk)+δk,∥δk∥≤εk.εk 必須涵蓋整次更新的誤差,包括所有捨入和任何不精確的內層求解,並可隨 k 改變。以下結果適用於所有滿足這個模型的計算序列,即使誤差彼此相關或經刻意選取亦然;我們沒有假設隨機捨入。
壓縮性還能給我們甚麼?
對任何 k≥1,
∥yk−x∗∥≤qk∥y0−x∗∥+j=0∑k−1qk−1−jεj.令 dk=∥yk−yk−1∥,則利用最近一次的誤差界可得
∥yk−x∗∥≤1−qqdk+εk−1.另一方法是取任何經認證的 ∥T(yk)−yk∥ 上界 ρk,則
∥yk−x∗∥≤1−qρk.
從計算更新式減去不動點方程,再用三角不等式及誘導範數,得到
∥yk+1−x∗∥≤q∥yk−x∗∥+εk.反覆代入便得第一個界。為得到步長判據,插入上一次計算更新式:
yk−x∗=B(yk−1−x∗)+δk−1=B(yk−x∗)−B(yk−yk−1)+δk−1.取範數並把 q∥yk−x∗∥ 移到左邊,即得所述結果。最後,
yk−x∗=B(yk−x∗)−(T(yk)−yk),同樣整理便得缺陷界。每次都必須使用 1−q>0。
證明透視
保留新的誤差項
三個假設在不同位置進入證明。誘導範數對每個 v 給出 ∥Bv∥≤q∥v∥,每次更新用一次。單步誤差界以加法進入,所以較早的誤差 δj 會被之後每一次壓縮削弱;這就是 εj 帶有權重 qk−1−j、而不會被放大的原因。
步長判據中不顯然的一步,是把 yk−1−x∗ 改寫成 (yk−x∗)−(yk−yk−1)。未知誤差於是出現在等式兩邊,右邊的係數至多為 q,而 q<1 使它可以被吸收到左邊,從而產生因子 1/(1−q);若 q≥1,整理時要除以非正數,甚麼也認證不了。缺陷界是同一種吸收,只是以精確更新 T(yk) 代替儲存的 yk−1,所以沒有 ε 項,但 ρk 必須是精確缺陷的上界。證明沒有用到任何符號或概率假設:每一步都是對刻意選取的誤差也成立的範數不等式。
因此,絕對容差 τ>0 的停止測試可只在 (qdk+εk−1)/(1−q) 的認證上界不超過 τ 時接受結果。實際機器運算中,計算 dk、q 及最後的式子也會產生誤差。應使用精確運算、定向捨入或其他嚴格區間包圍取得所需上界;畫面上的捨入小數不會自動成為上界。若要認證相對誤差,還需要 ∥x∗∥ 的正下界;當解為零時,絕對誤差不能獨自給出相對準確度。
若所有 εk≤ε,則
∥yk−x∗∥≤qk∥y0−x∗∥+1−q1−qkε.若 εk→0,則 yk→x∗。
一致情況下,j=0∑k−1qk−1−jε≤εi=0∑k−1qi=ε(1−qk)/(1−q)。趨於零的情況下,固定 η>0,選 J 使所有 j≥J 都有 εj≤η(1−q)。當 k>J,早期項滿足 j<J∑qk−1−jεj≤qk−Jj<J∑εj,它趨向零;尾項滿足 J≤j<k∑qk−1−jεj≤η(1−q)/(1−q)=η。由於 qk∥y0−x∗∥→0,對每個 η>0 都有 klimsup∥yk−x∗∥≤η。
一致界趨向 ε/(1−q),未必趨向零。這是保證值的誤差下限,並非聲稱每個實際序列的極限誤差都非零。
如何取得單步誤差界
對明確的矩陣與向量乘法,一個標準捨入模型可給出上界。本小節額外假設向量範數具單調性:若逐分量有 ∣v∣≤∣w∣,則 ∥v∥≤∥w∥。常見的 ℓ1、ℓ2 和 ℓ∞ 範數均具此性質,任意向量範數則未必如此。假設純量乘法與加法各自以最接近值捨入,沒有溢出或令模型失效的下溢,且 mu<1;其中 u 是單位捨入誤差,m=n+1。令 γm=mu/(1−mu)。By+c 的每個分量先以順序內積計算 n 個乘積,再加上 ci;標準捨入因子乘積估計給出保守的逐分量界
∣δ∣≤γm(∣B∣∣y∣+∣c∣),ε=γm∣B∣∣y∣+∣c∣.
這裏 ∣B∣、∣y∣ 按分量取絕對值;右側本身亦須向上包圍。對無窮範數,取該非負向量各分量的最大值。融合乘加、不同的求和次序、隱式三角更新、次正規數運算或溢出,都需要適合實際運算的界。特別是,不能把這個明確矩陣計數原封不動地套用於從未構造 B 的 Gauss–Seidel 實作。
對 Ax=b,常見形式為 T(x)=x+M−1(b−Ax),其中分裂矩陣 M 非奇異。其精確缺陷是 M−1(b−Ay),一般並非未經預處理的殘差。因此,只有控制 M−1 的作用及其計算誤差後,殘差界才可轉化成壓縮判據。
算例與簡單準則的失效
考慮純量理想映射 T(x)=21x+1,不動點為 x∗=2。假設 y0=0,第一次計算更新得到 y1=1.01,且已知單步誤差滿足 ε0≤0.01。儲存步長 d1=1.01,定理給出
∣y1−2∣≤1/2(1/2)(1.01)+0.01=1.03.實際誤差為 0.99。此界偏保守,但無須知道單步誤差的符號便有效。同一點的精確缺陷是 ∣T(1.01)−1.01∣=0.495,因此得到更精確的界 0.99。
反例模式
零步長不能認證準確度
再考慮同一映射;若從 y=1.9 出發的計算更新仍返回 1.9,步長為零,但誤差為 0.1。此時計算誤差為 −0.05,修正後步長界是 0.05/(1−1/2)=0.1。只有誤差界也夠小,零步長才構成認證。反過來,若認證界大於目標,只表示此論證不能作結,並不能證明實際答案不準確。
令 B=(1/21/41/41/2)、c=(1,1)T,則 q=∥B∥∞=3/4。解 (I−B)x=c 得 x∗=(4,4)T;驗算:每行 2+1+1=4。在 y=x∗,∣B∣∣y∣+∣c∣ 每個分量都是 2+1+1=4。這裏 n=2,所以 m=3。二進制雙精度中 u=2−53≈1.11×10−16,γ3≈3.33×10−16。因此單步誤差界約為 ε=4γ3≈1.33×10−15,保證值的下限為 ε/(1−q)≈5.33×10−15。用於認證之前,這些小數必須向上捨入。
取 q=1/2、∥y0−x∗∥≤2 及 εj=0.01⋅2−j。加權和的每一項為 2−(k−1−j)⋅0.01⋅2−j=0.01⋅21−k,與 j 無關,所以
∥yk−x∗∥≤21−k+0.01k21−k.當 k=10,此界為 (2+0.2)/1024≈2.15×10−3。正如推論所說,界趨向零;但這個邊界情況顯示,誤差恰以壓縮速率遞減時要付出額外的因子 k。
常見錯誤
對 T(x)=x+M−1(b−Ax),缺陷是 M−1(b−Ay)。取純量情況 A=0.1、M=0.2、b=1:則 T(x)=0.5x+5、q=0.5、x∗=10。在 y=9,殘差為 0.1,缺陷卻是 0.5。用殘差會得到錯誤的判據 0.1/0.5=0.2;缺陷給出 0.5/0.5=1,正是實際誤差。
假設 (qdk+εk−1)/(1−q) 的精確值是 0.0030004,容差為 τ=0.003。捨入到四位小數的顯示是 0.0030,看似通過,實際上測試並不成立。只有向上捨入或精確計算的值才可與 τ 比較。
練習與解答
快速檢查
(設 q=1/4、dk=0.006,且經認證的 εk−1=0.0003。步長判據能否確立絕對誤差不大於 0.003?)
解答 · 答案
上界為 (0.25⋅0.006+0.0003)/0.75=0.0024,所以可以。實作時三個輸入界和最後的運算均須認證。
快速檢查
(設 q=0.9,每次單步誤差均不大於 10−6。求一致誤差公式的極限上界。這是否證明迭代不收斂?)
在一致誤差公式中令 k→∞。
解答 · 答案
極限上界為 10−5。這不證明失敗;例如所有 δk=0 時便正常收斂。此界容許極限誤差非零,卻不要求它非零。
快速檢查
(純量映射 T(x)=0.8x+0.2 在某個候選值的精確缺陷是 0.02。求誤差界。若計算出的缺陷為 0.02,其絕對計算誤差最多為 0.001,又能確立甚麼界?)
這裏 q=0.8,所以 1−q=0.2。
解答 · 答案
精確缺陷給出 0.02/0.2=0.1。第二種情況下缺陷的認證上界為 0.021,故 ∣y−x∗∣≤0.105。
快速檢查
(給出一個具有固定非零單步誤差的計算序列,使其漸近達到一致誤差界。)
解答 · 答案
令 T(x)=qx、0<q<1、x∗=0、y0=0 及 δk=ε>0。直接求和得到 yk=ε(1−qk)/(1−q)。其極限等於上述界,故僅靠這些假設不能得到更小的一致保證。