同一個方程,兩種數值困難
代數恆等式在精確運算中成立,電腦卻必須使用有限精度。設儲存的實係數就是精確輸入,a=0,且 D=b2−4ac>0,所以 ax2+bx+c=0 有兩個不同實根。先假設 c=0;零常數項將在後面單獨處理。求根時要區分兩件事:公式中的近數相減,以及根對係數變化的敏感性。改變公式可以改善前者,卻無法消除後者。
記 s=D,約定 b≥0 時 sgn(b)=1,否則為 −1。構造
q=−21(b+sgn(b)s),xL=aq,xS=qc.
這裏 L 指絕對值不小於另一根,而非數值上較大的帶符號根。在上述假設下 q=0。括號內兩項同號或其中一項為零,因此這一步不會相減兩個幾乎相等的正數。
上述 xL,xS 恰好是兩個根,並且 ∣xL∣≥∣xS∣。
第一個式子是二次公式的一個選項,因此給出一根。兩根之積為 c/a,所以另一根是 (c/a)/(q/a)=c/q;這裏無需計算兩個近數之差。∣q∣=(∣b∣+s)/2,另一根的絕對值為 ∣∣b∣−s∣/(2∣a∣)。因為 ∣b∣+s≥∣∣b∣−s∣,次序成立。若 b=0,約定選出兩個絕對值相等、符號相反的根之一。
例題 8.2.3
(binary64 算術中的消去)
在 IEEE binary64 算術(最近捨入)中取 a=1、b=108、c=1。精確根為 −5⋅107±25⋅1014−1,故小根為 −1.00000000000000010…×10−8。所儲存的判別式 1016−4 是精確的,算得的平方根為 99999999.99999999。在 108 附近,相鄰的 binary64 數相距 2−26≈1.49×10−8,所以直接公式的分子 −b+s 只能是 2−26 的小倍數;此處它等於 −2−26。除以 2 得 −7.45×10−9,相對誤差約為 25%。穩定公式則得 q=−21(108+s)=−108,並返回 c/q=−10−8,約有十六位正確數字;大根 q/a=−108 的精度相同。
例題 8.2.4
(b=0 時兩根絕對值相等)
對 x2−4=0,有 b=0、D=16、s=4。約定 sgn(0)=1,故 q=−21(0+4)=−2,xL=q/a=−2,xS=c/q=−4/(−2)=2。兩根都得到,而且 ∣xL∣=∣xS∣:標記 L 只保證絕對值不小於另一根,所以在這個邊界情形,它僅記錄符號約定選出了哪一根。
若寫成 q=−21(b−sgn(b)s),或總是取 −b+s,那麼當 ∣b∣ 接近 s,即 ∣4ac∣ 遠小於 b2 時,就重新引入了這個恆等式原本要避免的相減。s 的符號必須與 b 的符號一致。
捨入界需要甚麼假設?
設計算採用最近捨入,單位捨入誤差為 u;有關運算均滿足 fl(z)=z(1+δ)、∣δ∣≤u,並且沒有溢出或使此模型失效的下溢。再假設所算非負平方根 s 有獨立證明的相對誤差界
s=s(1+η),∣η∣≤ρ<1.
這一假設同時包括判別式計算和開方的誤差;僅有正確捨入的開方指令並不能保證它。先以一次捨入加法和一次捨入乘以 −1/2 得到 q,再計算 xL=fl(q/a) 及 xS=fl(c/q)。設
e=(1+ρ)(1+u)2−1.
若 e<1,兩個計算根均非零,而且
xLxL−1≤(1+e)(1+u)−1,xSxS−1≤1−ee+u.
b 與 sgn(b)s 同號或 b=0。將 s 換成 s 時,和的絕對變化至多 ρs,原來和的絕對值為 ∣b∣+s≥s,因此相對變化至多 ρ,即未捨入的和等於精確和乘以 1+θ,其中 ∣θ∣≤ρ。再計入兩次捨入,可寫成 q=q(1+ξ),其中 ∣ξ∣≤e:乘積上界為 (1+ρ)(1+u)2,向下偏離 1 的幅度不超過這一上偏差。故 1+ξ≥1−e>0。
第一次除法滿足 xL/xL=(1+ξ)(1+δ),同樣估計乘積得到第一界。第二次除法則滿足 xS/xS=(1+δ)/(1+ξ),因此
1+ξ1+δ−1=∣1+ξ∣∣δ−ξ∣≤1−eu+e.這裏把除法視為單獨捨入;若運算溢出、下溢使模型失效,或編譯器改變運算次序,就不能直接照搬此證明。
證明透視
符號約定在哪裏發揮作用
整個證明建基於一個結構事實:唯一的加法 b+sgn(b)s 把兩個同號的數相加。正因如此,平方根的絕對擾動 ρs 才會變成和的至多 ρ 的相對擾動,因為和的絕對值至少是 s。若符號相反,同一絕對擾動要除以可以任意小的 ∣∣b∣−s∣,便得不到任何相對界。此後一切都是乘法:1+θ、1+δ1、1+δ2 三個因子給出 q,每個根再多一個因子。小根是除以 q 得到的,所以它的誤差因子以倒數出現,這就是分母出現 1−e、並且需要 e<1 的原因。關於 s 的假設只用了一次,而且此處並未證明;定理的可靠程度取決於這個外部誤差界。
十進制計算例子
假設機器保留三位有效數字,每次運算都捨入到最近值,指數範圍足夠大。取 a=1、b=−104、c=1,精確根是 (104±108−4)/2。在此算術中,108−4 捨入為 108,開方後為 104。直接公式的小根分子 104−104 因而為零。新公式給出 q=104,小根算為 10−4。實際小根約為 0.000100000001,故新式保留了三位有效數字;直接式卻給零。大根約為 9999.9999,在此格式中也捨入為 104。這只是一個算術例子,不是對所有問題的精確性保證。
穩定公式修補的是直接公式本身造成的精度損失。根對係數的敏感性則是問題本身的性質,任何重排運算都不能消除。
反例模式
穩定公式不能補回缺失的判別式資訊
令 a=c=1、b=−2,方程有重根 1。只將 b 改為 −2−ϵ,判別式變為 4ϵ+ϵ2>0,根為 1+ϵ/2±ϵ+ϵ2/4。係數變化量為 ϵ 階,根的分離卻為 ϵ 階。反之,令 b=−2+ϵ 且 0<ϵ<4,判別式為負。重根附近,連實根的數目也對數據敏感。前面的相對誤差定理明確要求 D>0 和有效的 s 誤差界;判別式被捨入成零或改變符號時不可使用。
下面的互動圖把每步運算捨入到 t 位有效數字,並排執行教科書公式與利用兩根之積的公式;降低 t,即可看到 −b+s 的消去,以及重根附近 D 的符號如何丟失。
直接計算 b2−4ac 本身也可能相減近數。將全部係數乘以同一非零常數不改變根,有時能減少溢出或下溢,但不能僅憑縮放認證判別式的符號或消除病態。需要嚴格保證時,必須用適當的精確運算、更高精度或區間運算等控制誤差。若 c=0,直接返回 0 與 −b/a;若 b 也為零,則零是重根。D=0 時重根為 −b/(2a),但要判斷 D 精確為零需有數據依據。D<0 時需要複數算術,本節不討論。
概念視角分析
判別式控制根的條件數
對單根 r,把係數擾動 δa,δb,δc 後,它在一階近似下移動
δr=−2ar+bδar2+δbr+δc,∣2ar+b∣=D.若每個係數的相對變化都不超過 ϵ,則在一階近似下根的相對變化至多為 ϵ(∣a∣r2+∣b∣∣r∣+∣c∣)/(∣r∣D)。因子 1/D 屬於問題本身,而非任何公式;當 D→0 時線性估計完全失效,得到反例中的平方根行為。
在重根附近,b2 與 4ac 幾乎相等,所以算得的 D 可能被捨入成零,甚至符號錯誤。只憑浮點計算的 D 來判斷是兩個實根、重根還是複根並不可靠;作此判斷需要 D 的誤差界。
練習與解答
快速檢查
(對 x2+108x+1=0,哪個直接公式分子有消去問題?給出小根的替代表達式。)
解答 · 答案
−108+1016−4 相減兩個近數。取 q=−(108+1016−4)/2,小根為 1/q。
快速檢查
(假設 u=10−4、ρ=10−3。用 0.001201 作為 e 的上界,求小根相對誤差界。)
展開 e=(1+ρ)(1+u)2−1,再用定理的第二個界。
解答 · 答案
展開得 e=1.001(1.0001)2−1=0.00120021001<0.001201。定理給出 (e+u)/(1−e)<0.001303。這依賴獨立的平方根誤差界和所述捨入模型。
快速檢查
(求 x2−2x+(1−10−8)=0 的精確根,說明為何係數相對誤差小,根的相對誤差未必同樣小。)
解答 · 答案
判別式為 4⋅10−8,根為 1±10−4。將常數改為 1,其相對變化約 10−8,兩根卻合併到 1,每根移動 10−4。這是接近重根時的敏感性。
快速檢查
(對 2x2+3x=0,為何實作中不應無條件套用 c/q?)
解答 · 答案
單獨處理得 0 和 −3/2。雖然此例 q=0,當 b=c=0 時 q=0,c/q 無定義。統一處理 c=0 可涵蓋兩種情況並避免不必要的異常除法。