兩個看似相同、其實不同的問題
在浮點數那一級,你學到每個數值答案都是近似值,而且光是「存下一個數」這個動作本身就已經四捨五入了——大多數十進位小數,連 0.1 都沒有精確的二進位形式。所以在任何計算開始之前,你的輸入就已經帶著一點點錯誤抵達了。很自然的擔憂是:我的演算法會不會把這些小小的輸入誤差,變成一個很大的錯誤答案?但底下還藏著一個更狡猾、更根本的問題,而這整級的內容,就是要把這兩者分清楚。
問題一是關於你的方法:演算法有沒有自己添加誤差? 這就是穩定性,我們會在後面的篇章談它。問題二則是關於問題本身,在你還沒挑任何演算法之前:假設真實答案被完美地算出來,但輸入稍微抖動了一下,真實答案會移動多少? 這就是條件性。這一級最誠實的核心主張是:這兩者是真正不同的。一個完美的演算法,救不了一個「真實答案本身就對輸入超級敏感」的問題。
關鍵在於,條件性是問題的性質——也就是從輸入到輸出的那個數學映射——而不是任何程式碼的性質。把問題想成一個黑盒子:餵進資料 x,吐出精確答案 f(x)。條件性只問:當 x 被推一下時,f 會怎麼反應。這個黑盒子既不知道、也不在乎你最終會用哪種語言、函式庫或方法。所以你可以、也應該在寫下任何一行演算法之前,就判斷它的條件性。
一幅畫面:平緩的斜坡與刀鋒般的山脊
把輸入想像成地圖上的一個點,把輸出想像成你的海拔高度。一個良態問題就像平緩的草原:朝任何方向走幾公尺,你的海拔幾乎不變——輸入誤差小,輸出誤差就小。而病態問題則像一道刀鋒般的山脊:同樣那一小步橫移,就讓你跌下懸崖。同樣大小的腳步,後果卻天差地別。差別完全在於地形的形狀,那是問題;而不在於你走得多小心,那是演算法。
這裡有個你可以親手驗算的小例子。在 x = 1 附近計算 sin(x) 是良態的:把 x 推動 0.1%,答案幾乎不動,因為 sin 在那裡斜率平緩。現在對比一下「兩個幾乎相等的數相減」,比方說 a - b,其中 a = 1.00001、b = 1.00000。真實的差是 0.00001。如果 a 在它的第六位上有不確定性——相對誤差約十萬分之一,再典型不過——這份不確定性幾乎全部落到答案上,而這個答案一開始才只有五位有效數字。一個在輸入裡看不見的抖動,變成了整個答案。這種放大正是病態運算的標誌,也是災難性抵消的種子。
替敏感度安上一個數字
我們不想揮揮手就說「蠻敏感的」。我們想要一個數字。一個問題的條件數正是那個增益旋鈕:在輸入端餵入大小為 epsilon 的相對抖動,輸出就大約抖動(條件數)乘以 epsilon。條件數為 1 表示問題原封不動地把誤差傳過去——那是平緩的草原。條件數為 10^6 表示它把誤差放大一百萬倍——那是刀鋒山脊。下一篇會專門講這個數字,以及它如何直接換算成「損失的位數」,所以這裡我們只先認識它。
對於一個光滑的純量函數 f,相對條件數有一個乾淨的封閉形式,你只用一個導數就能算出來。下面這兩個小算例把抽象的概念變得具體:開平方在各處都很溫馴,而指數函數的引數越大就越敏感。
relative condition number of y = f(x): kappa = | x * f'(x) / f(x) |
f(x) = sqrt(x): f'(x) = 1/(2 sqrt(x))
kappa = | x * (1/(2 sqrt(x))) / sqrt(x) | = 1/2 (well-conditioned, always)
f(x) = e^x: f'(x) = e^x
kappa = | x * e^x / e^x | = |x| (fine near 0, touchy for large x)注意條件數可能取決於你在哪裡問這個問題。指數函數在 0 附近溫和,在遠處則越來越敏感。所以「這個問題病態嗎?」往往其實是「它在這個輸入上病態嗎?」。條件性是局部的:它描述的是你正站的這個點上,地形的斜率。
當問題是一整個線性系統時
大多數真實的計算問題並不是單一個純量函數,而是更大的東西,例如求解線性系統 A x = b——找出矩陣 A 映射到 b 的那個 x。我們仍想要一個數字,告訴我們 b(或 A)裡的誤差會被放大成 x 裡多少誤差。那個數字就是矩陣條件數,寫作 kappa(A)。它是線性系統版的增益旋鈕,每當你求解、擬合或求逆時,都會再次遇見它。
幾何畫面是最乾淨的切入點。想像 A 拿起由輸入構成的單位球,把它拉伸成一個橢球。如果這橢球漂亮地接近圓球,每個方向都被大致平等地對待,kappa(A) 就接近 1——良態。如果 A 把球在某個方向上壓得幾乎扁平,那個方向就幾乎被摧毀,當你反過來解出 x 時幾乎救不回來;此時 kappa(A) 巨大,系統病態。形式上,kappa(A) 是「最大拉伸與最小拉伸之比」(最大奇異值除以最小奇異值)。它永遠至少為 1:沒有任何矩陣能比完美良態更好。
一個著名的陷阱顯示,病態矩陣可以長得多麼無害。希爾伯特矩陣的元素是 1/(i+j-1),又小又整齊,然而它 10×10 的版本,kappa(A) 約為 1.6 x 10^13。在雙精度下求解希爾伯特系統,尺寸超過約 12 就幾乎毫無希望——不是因為哪個求解器壞了,而是因為最小奇異值幾乎消失殆盡。順帶一提:這正是為什麼你幾乎從不顯式地算出 A^{-1} 來解 A x = b。反矩陣既較昂貴又較不忠實,比不上直接「分解再求解」;條件性問題是屬於問題本身的,但多此一舉去求逆,只會在它之上再招來額外的誤差。
為什麼這會改變你除錯的方式
這裡就是讓條件性變得實用、而非紙上談兵的回報。當一個答案看起來不對時,最先該做的診斷,不是「我迴圈裡的臭蟲在哪」。而是:問題本身病態嗎? 如果是,那麼這個看似錯誤的答案,可能正是問題給出的誠實判決,而換演算法、加檢查、或打磨程式碼都救不了你。病態的解藥從來不是更好的演算法——而是重新表述問題(避開接近抵消、選一個適定性更好的量)或採用更高的精度。
- 把問題辨認成一個從輸入到輸出的映射 f(x),與你之後要跑的任何程式碼分開。
- 估計它的條件數——純量 f 用導數公式,線性系統用 kappa(A)(函式庫會回報它,例如 LAPACK 的 RCOND)。
- 讀出天花板:條件數接近 10^k 時,大約會花掉你 ~16 位雙精度數字裡的 k 位,不管演算法多麼完美。
- 唯有在這道天花板已知之後,你才去問另一個獨立的問題——我的演算法夠穩定、足以達到它嗎?那是本級其餘篇章的主題。
這種分離正是整級的引擎。它被一條主法則所概括,你稍後會完整見到它:向前誤差(你的答案有多錯)至多等於條件數(問題有多難)乘以向後誤差(你的演算法有多好)。條件性是第一個因子——那個你光看問題就能讀出、在任何程式碼存在之前就成立的因子。乾淨的口號(第 5 篇會展開)是準確度 = 條件性 x 穩定性:穩定的演算法在病態問題上依然失敗,而良態問題也可能被一個不穩定的演算法毀掉。兩者你都需要。
一個警告與一個連結
兩個誠實的但書,能避免把條件性吹捧過頭。第一,條件數是一種一階、線性化的度量——它描述的是在你那個輸入點上、在擾動趨於極小的極限下,地形的斜率。對於大擾動,真實行為可能不同,所以把它當成極好的經驗法則,而非精確的保證。第二,相對條件數在真實輸出為零之處沒有定義(你無法除以一個大小為零的答案);在這類點附近,只有絕對誤差的概念才說得通。
條件性也是適定性的數值表親。一個適定問題的解存在、唯一,並且連續地依賴於資料。條件性把最後這個條件磨利成一個數字:它說的是多麼連續。一個適定但嚴重病態的問題,技術上是連續的,實務上卻是一道刀鋒——那種依賴關係陡到有限精度的算術跟不上。許多惡名昭彰的例子就藏在眼皮底下:相減兩個幾乎相等的數、上面那個希爾伯特矩陣、用高次多項式擬合穿過許多點(凡德蒙條件性問題),以及從係數反推多項式的根。