求根與非線性方程

Brent 法(Brent's method)

/ BRENT /

如果你想要一個可靠、單一的單變數求根器——在你不想費神時就拿來用的那個——Brent 法就是標準答案。它是混合法,給你二分法堅不可摧的收斂保證「以及」割線與插值法的快速局部速度,並在兩者之間自動切換,讓你永遠不必抉擇。

Brent 法隨時保有環繞根的夾根區間 [a, b](所以絕不會發散),而每一步它都嘗試一個快速移動:反二次插值(用最近三點配一條橫躺的拋物線,讀出它碰到零的位置);若不成,則用一次割線步。接著它檢查所提的點是否合理——在夾根區間內,且讓區間縮得夠快。若快速步看起來不可靠,或區間沒在縮小,它就退回普通的二分步,雖慢但有保證。這套記帳(出自 Dekker,並由 Richard Brent 於 1973 年精煉)使 Brent 法在表現良好的函數上超線性收斂,最壞情況下也絕不比二分法差。

Brent 法正是科學程式庫中預設求根器背後的東西(它是數值軟體中名為 brentq 或 fzero 的常式的主力),因為它不需導數,只要求一個帶變號的起始夾根區間,且對真實問題產生的各種雜亂函數都很穩健。入場的代價是夾根區間:你必須先提供函數值異號的 a、b,而且和所有夾根法一樣,它找到內部的一個根,不是全部的根。對多維系統,你需要的是牛頓法或擬牛頓法——Brent 是一維專家。

實務上你呼叫類似 brentq(f, a, b):給定 f(x) = x^3 - x - 1 與帶變號的夾根區間 [1, 2],Brent 法在寥寥幾步內回傳 1.324717957...。內部它大多使用快速的反二次步,但在任何快速步會離開夾根區間或無法縮小它的迭代上,悄悄退回二分法。

二分法的安全加上插值法的速度——預設的一維求解器。

Brent 仍需要一個有效的變號夾根區間才能起步,且只找到其中「一個」根。它是一維方法;對非線性「系統」你必須用牛頓法或 Broyden 法,而非 Brent。

又称
Brent-Dekker methodinverse quadratic interpolation root-finderBrent-Dekker 法