為甚麼結合兩種方法?
二分法每步計算一次函數值,且異號區間的收縮速度可預先確定。割線利用兩點函數值預測曲線與橫軸的交點;曲線接近直線時,這個預測可能更準確。但外推得到的割線迭代點可能離開目標區域,即使交點位於區間內部,也不一定有效縮短區間。我們把割線交點當作候選點,只有它能保證區間有足夠進展時才接受。保障規則提供證明;割線只是爭取加速的機會,並不保證更快。
明確的算法
設 f : [ a 0 , b 0 ] → R f:[a_0,b_0]\to\mathbb R f : [ a 0 , b 0 ] → R 連續,a 0 < b 0 a_0<b_0 a 0 < b 0 ,且 f ( a 0 ) f ( b 0 ) < 0 f(a_0)f(b_0)<0 f ( a 0 ) f ( b 0 ) < 0 。定理先採用精確算術。第 n n n 步開始時記 L n = b n − a n L_n=b_n-a_n L n = b n − a n ,端點函數值異號。經過 ( a n , f ( a n ) ) (a_n,f(a_n)) ( a n , f ( a n )) 與 ( b n , f ( b n ) ) (b_n,f(b_n)) ( b n , f ( b n )) 的割線與橫軸交於
s n = a n f ( b n ) − b n f ( a n ) f ( b n ) − f ( a n ) = a n − f ( a n ) ( b n − a n ) f ( b n ) − f ( a n ) . s_n=\frac{a_nf(b_n)-b_nf(a_n)}{f(b_n)-f(a_n)}
=a_n-\frac{f(a_n)(b_n-a_n)}{f(b_n)-f(a_n)}. s n = f ( b n ) − f ( a n ) a n f ( b n ) − b n f ( a n ) = a n − f ( b n ) − f ( a n ) f ( a n ) ( b n − a n ) .
異號使分母非零,並保證 s n s_n s n 嚴格處於區間內部;但它可能離端點任意近。固定 0 < θ ≤ 1 / 2 0<\theta\le1/2 0 < θ ≤ 1/2 。若 s n s_n s n 在中央區間 [ a n + θ L n , b n − θ L n ] [a_n+\theta L_n,b_n-\theta L_n] [ a n + θ L n , b n − θ L n ] 內,令 x n = s n x_n=s_n x n = s n ;否則令 x n = ( a n + b n ) / 2 x_n=(a_n+b_n)/2 x n = ( a n + b n ) /2 。計算 f ( x n ) f(x_n) f ( x n ) :若等於零,精確返回 x n x_n x n ;否則保留端點值異號的子區間,並在下步重用 f ( x n ) f(x_n) f ( x n ) 。
給定絕對容差 ε > 0 \varepsilon>0 ε > 0 ,可在提出下一點之前 檢查 L n / 2 ≤ ε L_n/2\le\varepsilon L n /2 ≤ ε ;成立時返回中點及區間。實作時應在要求嚴格異號之前先檢查端點是否為根。只有返回精確零點(包括端點零點)或滿足寬度準則,算法才給出保證;其他退出均無認證。
在上述假設下,除非遇到精確零點,每個保留區間都是包含至少一個零點的異號區間,且
L n ≤ ( 1 − θ ) n L 0 . L_n\le(1-\theta)^n L_0. L n ≤ ( 1 − θ ) n L 0 . 寬度準則返回的中點距最終區間中每一個根至多 ε \varepsilon ε 。對於任何滿足 ( 1 − θ ) N L 0 ≤ 2 ε (1-\theta)^N L_0\le2\varepsilon ( 1 − θ ) N L 0 ≤ 2 ε 的非負整數 N N N ,算法至多經過 N N N 步便終止:要麼遇到精確零點,要麼滿足寬度保證。保證只涉及最終區間內根的存在和位置精度,並不證明唯一性或給出所有根的數目。
證明與實作選擇
介值定理確保初始區間內存在零點。每一步選定的 x n x_n x n 都嚴格位於區間內部;若其函數值非零,恰有一個端點與之異號,故保留區間仍有異號端點。連續性確保該區間仍含零點。
接受的點必在中央區間:若割線點被拒絕,改取的中點也在中央區間,因為 θ ≤ 1 / 2 \theta\le1/2 θ ≤ 1/2 。因此兩種可能的新區間長度均至多為 ( 1 − θ ) L n (1-\theta)L_n ( 1 − θ ) L n 。歸納得到上述界。由於 1 − θ < 1 1-\theta<1 1 − θ < 1 ,有限的 N N N 一定能滿足寬度準則。最終區間內每一點距中點不超過半個區間寬度,從而得到誤差結論。若沒有容差並且未遇到精確零點,把迭代無限繼續下去,則嵌套閉區間收斂到同一點,連續性保證它是零點;證明不需要單調性或可微性。
證明透視
不變量承擔兩項不同任務 論證依靠兩個假設,而每個假設都只在一個可以指明的位置用到。連續性只透過介值定理使用,並對每個保留區間重新應用:符號檢驗選出端點仍然異號的那一段,連續性再把這個符號模式化為零點。限制 θ ≤ 1 / 2 \theta\le1/2 θ ≤ 1/2 只用來說明備用的中點本身通過中央檢驗;若 θ > 1 / 2 \theta\gt1/2 θ > 1/2 ,中央區間便是空集。
關鍵一步是:接受檢驗使長度界與割線落在何處無關。無論採用哪一點,它到兩個端點的距離都至少是 θ L n \theta L_n θ L n ,所以任一保留段的長度至多為 ( 1 − θ ) L n (1-\theta)L_n ( 1 − θ ) L n 。終止於是成為幾何數列的性質;誤差結論只用到中點與區間內每一點的距離不超過半個寬度。證明不需要割線公式、可微性或根是單根。不變量的兩半不能互相取代:收縮的區間未必含零點,異號區間也未必收縮到一點,下文的試位法例子正說明後者。
定理中的保證附屬於一個特定的返回點。
若寬度準則在至少一步之後才成立,最後計算的點 x n x_n x n 是最終區間的一個端點,因為保留段總以 x n x_n x n 為一端。區間內的根與它的距離可達整個寬度 L ≤ 2 ε L\le2\varepsilon L ≤ 2 ε 。因此以容差 ε \varepsilon ε 報告 x n x_n x n ,會把精度高估至多一倍;有保證的距離界屬於中點。
精確算術下的簡明過程為:
solve(f, a, b, epsilon, theta):
require a < b, epsilon > 0, 0 < theta <= 1/2
evaluate fa=f(a), fb=f(b)
if fa=0 return exact a; if fb=0 return exact b
require fa and fb to have opposite signs
while (b-a)/2 > epsilon:
s = a - fa*(b-a)/(fb-fa)
if a+theta*(b-a) <= s <= b-theta*(b-a): x=s
else: x=(a+b)/2
evaluate fx=f(x)
if fx=0 return exact x
if fx and fa have opposite signs: b=x; fb=fx
else: a=x; fa=fx
return midpoint (a+b)/2 and bracket [a,b]
精確算術及嚴格異號假設使最後的 else 合理。實際程序應比較符號而非相乘,避免乘積上溢或下溢。檢測非有限值、求值失敗及捨入後候選點或中點與端點重合;無法繼續時,應返回失敗或明確標為沒有認證的結果。浮點零可能來自下溢,不一定是數學上的精確零點。證明要求可靠符號與算術;經驗證的浮點保證還需要控制求值誤差和捨入誤差。達到最大迭代次數並不等於通過寬度準則。
檢驗 fa*fb < 0 看似等價於異號,但在 IEEE 雙精度中,10 − 200 10^{-200} 1 0 − 200 與 − 10 − 200 -10^{-200} − 1 0 − 200 的乘積 − 10 − 400 -10^{-400} − 1 0 − 400 會下溢為 − 0 -0 − 0 。與 0 0 0 比較時便報告沒有異號,有效的區間因而被拒絕。反方向而言,兩個接近 10 200 10^{200} 1 0 200 的值相乘會上溢。應直接比較兩個值的符號。
逐步算例
設 f ( x ) = x 2 − 2 f(x)=x^2-2 f ( x ) = x 2 − 2 ,初始區間 [ 1 , 2 ] [1,2] [ 1 , 2 ] ,θ = 1 / 4 \theta=1/4 θ = 1/4 。端點值為 − 1 -1 − 1 和 2 2 2 ,因此 s 0 = 4 / 3 s_0=4/3 s 0 = 4/3 ,落在 [ 5 / 4 , 7 / 4 ] [5/4,7/4] [ 5/4 , 7/4 ] 內。因 f ( 4 / 3 ) = − 2 / 9 f(4/3)=-2/9 f ( 4/3 ) = − 2/9 ,保留 [ 4 / 3 , 2 ] [4/3,2] [ 4/3 , 2 ] 。下一次割線提議是 7 / 5 7/5 7/5 ,而中央區間為 [ 3 / 2 , 11 / 6 ] [3/2,11/6] [ 3/2 , 11/6 ] ;7 / 5 7/5 7/5 太靠近左端。於是改取中點 5 / 3 5/3 5/3 ,此時 f ( 5 / 3 ) = 7 / 9 f(5/3)=7/9 f ( 5/3 ) = 7/9 ,保留 [ 4 / 3 , 5 / 3 ] [4/3,5/3] [ 4/3 , 5/3 ] 。該區間中點 3 / 2 3/2 3/2 與區間內根的絕對距離至多為 1 / 6 1/6 1/6 。精確根是 2 \sqrt2 2 ,但建立這個界不需要知道它。
兩步後的最壞情況長度界是 ( 3 / 4 ) 2 = 9 / 16 (3/4)^2=9/16 ( 3/4 ) 2 = 9/16 ,實際長度為 1 / 3 1/3 1/3 。這個保守保證適用於所有滿足連續與異號假設的函數。
令 f ( x ) = 3 x − 1 f(x)=3x-1 f ( x ) = 3 x − 1 ,區間 [ 0 , 4 ] [0,4] [ 0 , 4 ] ,θ = 1 / 4 \theta=1/4 θ = 1/4 ,ε = 1 / 10 \varepsilon=1/10 ε = 1/10 。對仿射函數,割線就是圖像本身,所以每次提議都等於根 1 / 3 1/3 1/3 。端點值為 − 1 -1 − 1 和 11 11 11 ,得 s 0 = 0 + 4 / 12 = 1 / 3 s_0=0+4/12=1/3 s 0 = 0 + 4/12 = 1/3 ;但中央區間是 [ 1 , 3 ] [1,3] [ 1 , 3 ] ,提議被拒絕。中點 2 2 2 有 f ( 2 ) = 5 > 0 f(2)=5\gt0 f ( 2 ) = 5 > 0 ,保留 [ 0 , 2 ] [0,2] [ 0 , 2 ] 。下一提議仍是 1 / 3 1/3 1/3 ,不在 [ 1 / 2 , 3 / 2 ] [1/2,3/2] [ 1/2 , 3/2 ] 內;中點 1 1 1 有 f ( 1 ) = 2 > 0 f(1)=2\gt0 f ( 1 ) = 2 > 0 ,留下 [ 0 , 1 ] [0,1] [ 0 , 1 ] 。此時中央區間為 [ 1 / 4 , 3 / 4 ] [1/4,3/4] [ 1/4 , 3/4 ] ,提議 1 / 3 1/3 1/3 被接受,且 f ( 1 / 3 ) = 0 f(1/3)=0 f ( 1/3 ) = 0 ,算法返回精確零點。半寬 2 , 1 , 1 / 2 2,1,1/2 2 , 1 , 1/2 都大於 ε \varepsilon ε ,所以循環從未因寬度而停止。這個邊界情況顯示保障規則的代價:即使提議完美,只要太靠近端點便會被忽略,並以二分步驟補償。
令 f ( x ) = x 3 − x f(x)=x^3-x f ( x ) = x 3 − x ,區間 [ − 2 , 3 / 2 ] [-2,3/2] [ − 2 , 3/2 ] ,θ = 1 / 4 \theta=1/4 θ = 1/4 。區間含三個根 − 1 -1 − 1 、0 0 0 、1 1 1 。因 f ( − 2 ) = − 6 f(-2)=-6 f ( − 2 ) = − 6 、f ( 3 / 2 ) = 15 / 8 f(3/2)=15/8 f ( 3/2 ) = 15/8 ,
s 0 = − 2 − ( − 6 ) ( 7 / 2 ) 15 / 8 + 6 = − 2 + 8 3 = 2 3 , s_0=-2-\frac{(-6)(7/2)}{15/8+6}=-2+\frac83=\frac23, s 0 = − 2 − 15/8 + 6 ( − 6 ) ( 7/2 ) = − 2 + 3 8 = 3 2 , 它在中央區間 [ − 9 / 8 , 5 / 8 ] [-9/8,5/8] [ − 9/8 , 5/8 ] 之外。中點 − 1 / 4 -1/4 − 1/4 有 f ( − 1 / 4 ) = 15 / 64 > 0 f(-1/4)=15/64\gt0 f ( − 1/4 ) = 15/64 > 0 ,與 f ( − 2 ) f(-2) f ( − 2 ) 異號,故保留 [ − 2 , − 1 / 4 ] [-2,-1/4] [ − 2 , − 1/4 ] 。下一提議為
s 1 = − 2 − ( − 6 ) ( 7 / 4 ) 15 / 64 + 6 = − 2 + 32 19 = − 6 19 , s_1=-2-\frac{(-6)(7/4)}{15/64+6}=-2+\frac{32}{19}=-\frac{6}{19}, s 1 = − 2 − 15/64 + 6 ( − 6 ) ( 7/4 ) = − 2 + 19 32 = − 19 6 , 不在 [ − 25 / 16 , − 11 / 16 ] [-25/16,-11/16] [ − 25/16 , − 11/16 ] 內;中點 − 9 / 8 -9/8 − 9/8 有 f ( − 9 / 8 ) = − 153 / 512 < 0 f(-9/8)=-153/512\lt0 f ( − 9/8 ) = − 153/512 < 0 ,故保留 [ − 9 / 8 , − 1 / 4 ] [-9/8,-1/4] [ − 9/8 , − 1/4 ] 。區間內只剩根 − 1 -1 − 1 。定理只保證最終區間內有一個根,而這次計算已捨棄 0 0 0 和 1 1 1 :方法認證的是一個根,不是全部根。
保障規則防止甚麼?
反例模式
試位法的異號區間可能停滯 取 f ( x ) = x 2 − 1 f(x)=x^2-1 f ( x ) = x 2 − 1 和初始區間 [ 0 , 2 ] [0,2] [ 0 , 2 ] 。普通試位法始終用割線零點替換一個端點,沒有中央檢驗。其右端點始終為 2 2 2 ,左端點滿足
a n + 1 = 2 a n + 1 a n + 2 , a 0 = 0. a_{n+1}=\frac{2a_n+1}{a_n+2},\qquad a_0=0. a n + 1 = a n + 2 2 a n + 1 , a 0 = 0. 事實上,若 0 ≤ a n < 1 0\le a_n<1 0 ≤ a n < 1 ,則 a n < a n + 1 < 1 a_n<a_{n+1}<1 a n < a n + 1 < 1 且 f ( a n + 1 ) < 0 f(a_{n+1})<0 f ( a n + 1 ) < 0 。又 1 − a n + 1 = ( 1 − a n ) / ( a n + 2 ) ≤ ( 1 − a n ) / 2 1-a_{n+1}=(1-a_n)/(a_n+2)\le(1-a_n)/2 1 − a n + 1 = ( 1 − a n ) / ( a n + 2 ) ≤ ( 1 − a n ) /2 ,故 a n → 1 a_n\to1 a n → 1 。割線提議趨於根,但區間長度趨於 1 1 1 而非 0 0 0 。因此僅保留異號並不能將中點誤差控制到任意小。對任意固定 θ \theta θ ,中央檢驗會拒絕距離任一端點小於 θ L n \theta L_n θ L n 的提議;無論軌跡如何,收縮定理都排除此類停滯。
局部割線行為及其局限
無約束割線法使用最近兩個迭代點,它們不一定是區間端點。若 x n ≠ x n − 1 x_n\ne x_{n-1} x n = x n − 1 且 f ( x n ) ≠ f ( x n − 1 ) f(x_n)\ne f(x_{n-1}) f ( x n ) = f ( x n − 1 ) ,則
x n + 1 = x n − f ( x n ) x n − x n − 1 f ( x n ) − f ( x n − 1 ) . x_{n+1}=x_n-f(x_n)\frac{x_n-x_{n-1}}{f(x_n)-f(x_{n-1})}. x n + 1 = x n − f ( x n ) f ( x n ) − f ( x n − 1 ) x n − x n − 1 .
設 f f f 在單根 r r r (即 f ( r ) = 0 f(r)=0 f ( r ) = 0 且 f ′ ( r ) ≠ 0 f'(r)\ne0 f ′ ( r ) = 0 )附近屬於 C 2 C^2 C 2 ,相異迭代點收斂到 r r r 而沒有恰好等於它。將通過 x n − 1 , x n x_{n-1},x_n x n − 1 , x n 的直線插值餘項在 r r r 處求值,並對割線斜率使用中值定理,可知充分大的 n n n 滿足
∣ x n + 1 − r ∣ ≤ C ∣ x n − r ∣ ∣ x n − 1 − r ∣ . |x_{n+1}-r|\le C|x_n-r|\,|x_{n-1}-r|. ∣ x n + 1 − r ∣ ≤ C ∣ x n − r ∣ ∣ x n − 1 − r ∣.
這裏二階導數有界,割線斜率在根附近有正的絕對值下界。因此除以 ∣ x n − r ∣ |x_n-r| ∣ x n − r ∣ 可知相鄰誤差之比趨於零。這是有條件的局部結論:它假設迭代有定義且收斂;它不證明全局收斂,也不能自動賦予上述帶保障算法同樣的速率,因為後者可能使用二分步。分母為零時無約束公式無定義,例如 f ( x ) = x 2 − 1 f(x)=x^2-1 f ( x ) = x 2 − 1 的起始點 − 2 -2 − 2 和 2 2 2 的函數值相同。
概念視角 結構
區分三個對象 最近的割線點是一個近似值。連續函數的異號區間是存在性證明。區間半寬始終給出位置誤差界;只有區間足夠窄時才能滿足指定容差。單憑小殘差或相鄰提議相近,都不能證明寬度結論。
練習與解答
快速檢查
(若 L 0 = 1 L_0=1 L 0 = 1 、θ = 1 / 4 \theta=1/4 θ = 1/4 、ε = 1 / 10 \varepsilon=1/10 ε = 1/10 ,定理保證寬度準則成立的最小非負整數 N N N 是多少?)
解答 · 答案 需要 ( 3 / 4 ) N ≤ 1 / 5 (3/4)^N\le1/5 ( 3/4 ) N ≤ 1/5 。N = 5 N=5 N = 5 時 243 / 1024 > 1 / 5 243/1024\gt1/5 243/1024 > 1/5 ;N = 6 N=6 N = 6 時 729 / 4096 < 1 / 5 729/4096\lt1/5 729/4096 < 1/5 。所以最壞情況估計下 N = 6 N=6 N = 6 足夠;具體計算可能提前停止。
快速檢查
(對 f ( x ) = x 2 − 2 f(x)=x^2-2 f ( x ) = x 2 − 2 、區間 [ 1 , 2 ] [1,2] [ 1 , 2 ] 和 θ = 1 / 4 \theta=1/4 θ = 1/4 ,驗證算例前兩次提議及保留區間。為何拒絕第二次提議?)
解答 · 答案 第一個割線零點 4 / 3 4/3 4/3 落在 [ 5 / 4 , 7 / 4 ] [5/4,7/4] [ 5/4 , 7/4 ] 內而被接受;f ( 4 / 3 ) = − 2 / 9 f(4/3)=-2/9 f ( 4/3 ) = − 2/9 ,故保留 [ 4 / 3 , 2 ] [4/3,2] [ 4/3 , 2 ] 。下一提議為 s = 4 / 3 + ( 2 / 9 ) ( 2 / 3 ) / ( 20 / 9 ) = 7 / 5 s=4/3+(2/9)(2/3)/(20/9)=7/5 s = 4/3 + ( 2/9 ) ( 2/3 ) / ( 20/9 ) = 7/5 ,小於中央區間 [ 4 / 3 + 1 / 6 , 2 − 1 / 6 ] = [ 3 / 2 , 11 / 6 ] [4/3+1/6,2-1/6]=[3/2,11/6] [ 4/3 + 1/6 , 2 − 1/6 ] = [ 3/2 , 11/6 ] 的左端,即太靠近左端點。改取 5 / 3 5/3 5/3 的函數值為正,故保留 [ 4 / 3 , 5 / 3 ] [4/3,5/3] [ 4/3 , 5/3 ] 。
快速檢查
(f ( x ) = 1 / x f(x)=1/x f ( x ) = 1/ x 在 [ − 1 , 1 ] [-1,1] [ − 1 , 1 ] 上滿足定理嗎?f ( x ) = ( x − 1 ) 2 f(x)=(x-1)^2 f ( x ) = ( x − 1 ) 2 在 [ 0 , 2 ] [0,2] [ 0 , 2 ] 上滿足嚴格異號假設嗎?)
解答 · 答案 兩者都不滿足。第一函數在零處無定義、不連續,雖然端點值異號,該區間內卻沒有零點。第二函數連續並有根 1 1 1 ,但兩個端點值均為正;嚴格異號是根存在的充分條件,不是必要條件。
快速檢查
(精確算術下,若區間為 [ 2 , 2.02 ] [2,2.02] [ 2 , 2.02 ] ,給出中點的有效誤差界。若 ∣ f ( 2.01 ) ∣ |f(2.01)| ∣ f ( 2.01 ) ∣ 也很小,僅憑這一事實能認證更好的界嗎?)
解答 · 答案 中點為 2.01 2.01 2.01 ,區間內任何根與它相距至多 0.01 0.01 0.01 。殘差帶有 f f f 的單位;沒有定量斜率下界等額外資訊,就不能由殘差推出更小的位置誤差界。例如縮放函數可使殘差任意小,卻不改變根的位置。