为什么结合两种方法?
二分法每步计算一次函数值,且异号区间的收缩速度可预先确定。割线利用两点函数值预测曲线与横轴的交点;曲线接近直线时,这个预测可能更准确。但外推得到的割线迭代点可能离开目标区域,即使交点位于区间内部,也不一定有效缩短区间。我们把割线交点当作候选点,只有它能保证区间有足够进展时才接受。保障规则提供证明;割线只是争取加速的机会,并不保证更快。
明确的算法
设 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 的单位;没有定量斜率下界等额外信息,就不能由残差推出更小的位置误差界。例如缩放函数可使残差任意小,却不改变根的位置。