JOVANA
Explore Library Glossary Getting Started Three Levels Fields How it works Mission
Join the mission
All guides

條件數與消失的位數

第一篇問的是:一個問題到底敏不敏感?這一篇要替那份敏感度標上一個數字——條件數——並揭開它逼出的那筆殘酷帳:條件數接近 1e8,就會在任何演算法跑起來之前,悄悄吃掉你 16 位雙精度數字裡的大約 8 位。

從「它敏感嗎?」到「到底有多敏感?」

在上一篇我們問的是一個是非題:輸入的一點點晃動,會造成輸出的一點點晃動,還是巨大的晃動?這就是問題的條件數這個觀念,而它住在問題本身裡,跟你打算用哪個演算法無關。但「一點點」和「很多」並不是量測。這一整篇的工作,就是把那個形容詞換成一個誠實的數字——條件數——好讓我們能精確地說:輸入誤差在通往輸出的路上,被放大了幾倍。

把問題想成一個黑盒子,吃進一個輸入 x、吐出一個輸出 y = f(x)。你從來無法把精確的 x 交給它;你交的是 x 加上一點點相對誤差(存它時的捨入、量它時的雜訊)。條件數不過就是這個問題的答案:那份相對的輸入誤差,會以幾倍被放大、重新出現在輸出裡?如果 x 上 0.001% 的晃動造成 y 上 0.001% 的晃動,條件數就大約是 1,日子很好過。如果同樣 0.001% 的晃動造成 y 上 100% 的晃動,條件數就大約是 100000,那你就麻煩了。

相對進、相對出:實用的定義

因為誤差最好用與尺度無關的方式來判斷——回想一下基礎那一階談過的相對誤差——我們真正會用的,是相對條件數。用白話說:它是輸出的相對變化除以輸入的相對變化,並在輸入晃動趨近於零的最壞情況下取值。條件數 kappa 的意思是:一個大小為 eps 的相對輸入誤差,可能膨脹成大到 kappa 乘以 eps 的相對輸出誤差。這一個乘法,就是整個誤差放大的機制。

                |relative change in output|
  kappa  =  max  --------------------------    (as the input wobble -> 0)
                |relative change in input |

  relative output error   <=   kappa  x  relative input error

  for a smooth f(x):   kappa(x)  =  |x f'(x)| / |f(x)|
相對條件數是一個最壞情況的放大倍率;對一個光滑的純量函數 f,它有個乾淨的封閉形式 |x f'(x) / f(x)|。

kappa(x) = |x f'(x) / f(x)| 這道小公式,值得你盯著看一會兒。斜率 f'(x) 說的是輸出移動得多快;而 x 和 1/f(x) 這兩個因子,把那道斜率重新換算成相對的尺度。試試 f(x) = sqrt(x):那麼 f'(x) = 1/(2 sqrt(x)),算出來 kappa 在每個地方都剛好是 1/2——平方根的條件數漂亮得很,會把任何相對誤差減半。再試 f(x) = x - 1 在 x = 1 附近:這裡 f(x) 很小,而 x f'(x) 大約是 1,於是 kappa 爆炸。這就是從條件數那一側看到的「兩個幾乎相等的數相減」:問題『對接近 1 的 x 計算 x - 1』本身就是病態的,無論你怎麼寫程式都一樣。

算帳:條件數吃掉你的位數

現在來看把條件數從抽象變成你能感受到的數字的那一部分。雙精度一開始給你大約 16 位正確的有效十進位數字——這是一筆固定的預算,在你的輸入被存進去的那一刻就定了,因為光是存下 x,就已經付出了接近機器 epsilon、約 1e-16 的相對誤差。把這份躲不掉的起始誤差乘上條件數,你就得到任何方法可能交出的最佳相對誤差。取以 10 為底的對數,整幅圖就變成一道乾淨的算術:條件數接近 10^k,就要花掉你大約 k 位數字。

所以一個 kappa 大約是 1 的良態問題,幾乎保住全部 16 位。一個 kappa 大約是 1e8 的問題——這在真實應用裡雖大卻再普通不過——把你 1e-16 的起始誤差乘到約 1e-8,剩下大約 8 位可信的數字。推到 kappa 大約 1e16,數學就很慘了:16 減 16 等於 0,於是連最好的計算都可能交回一個一位正確數字都沒有的答案。這不是你能抓出來的程式臭蟲;這是問題本身,拒絕在雙精度裡被精確地回答。

解 A x = b 的矩陣條件數

同樣的觀念可以放大到下一階的主力問題:解線性系統 A x = b。這裡的輸入是資料(A 與 b),輸出是解 x。A 的矩陣條件數,寫成 kappa(A),回答的正是那個老問題:如果我把 b(或 A)擾動一個微小的相對量,x 的相對誤差可以長大多少?用 2-範數時,它等於最大奇異值對最小奇異值的比,kappa(A) = sigma_max / sigma_min——這個數永遠至少是 1,而且你可以從 A 的幾何形狀把它讀出來。

從幾何上看,kappa(A) 衡量的是 A 把空間拉伸得多不均勻:它是你把 A 作用到一個圓上得到的橢圓,最長軸對最短軸的比。當這個比很大,矩陣就接近奇異——它的列或行幾乎線性相依——而解 x 就坐在刀鋒上,b 上一根頭髮寬度的改變,都能把它滑到老遠。一個經典的麻煩製造者,是擬合高次多項式時出現的范德蒙矩陣:它的條件數隨次數呈指數成長,這正是為什麼天真的高次擬合會亂成一團。

幾乎每個初學者都有的反射動作,是想靠算出 A 的反矩陣來「檢查」一個系統。忍住別這麼做。求反矩陣更貴、更不準,而且不會告訴你任何條件數沒說過的事——更何況你打從一開始就幾乎不會為了解 A x = b 去求反矩陣。條件數才是你想要的那份誠實健康報告;反矩陣是一條昂貴的繞路,還可能把事情弄得更糟。

為什麼再完美的演算法也救不了你

這裡有一句把整階串起來的話,現在先說、接下來三篇再慢慢拆開。你實際拿到的準確度服從一條黃金法則:向前誤差 <= 條件數 × 向後誤差。向前誤差是你的答案錯得多離譜;向後誤差則大致是:你得把輸入動多少手腳,才能讓你算出來的答案,剛好是那個動過手腳的問題的精確解。一個好演算法會把向後誤差壓到接近捨入誤差的等級——那就是叫做向後穩定的黃金標準,也是第四篇的主題。

但盯著這條黃金法則看,殘酷之處就一目了然。就算你的演算法完美無瑕、把向後誤差一路壓到機器 epsilon,向前誤差仍然要被條件數乘上去。如果 kappa 是 1e12,那微小的 1e-16 向後誤差就變成 1e-4 的向前誤差——只剩四位可信的數字,無論你的程式碼多完美。一個穩定的演算法用在病態問題上,給你的是某個鄰近問題的精確解,而那可能離你真正問的那個問題的精確解很遠。這不是演算法的失敗;是問題的失敗。

用一口氣說完這一階的全部身分:準確度 = 條件數 × 穩定性。本篇的主角條件數,是「條件數」這一半——由問題定死,超出任何演算法所能觸及的範圍。第三篇會把向前誤差與向後誤差的分別磨得更利;第四篇會解釋為什麼向後穩定是你能誠實要求一個方法做到的極限;第五篇會把這兩半再乘回去。你現在握著的經驗誤差界——相信大約 16 減 log10(kappa) 位數字——正是那條宏大恆等式落在地上的影子。