动机
根是满足 f(r)=0 的数。即使无法方便地写出精确根,我们仍可计算近似值;但有用的近似应伴随误差判断。图像只能提示位置,不能证明零点存在或数字可靠。我们先建立保证存在性的区间,再研究局部可能更快的迭代。
二分法
设 f 在 [a,b] 连续且 f(a)f(b)<0。介值定理保证 (a,b) 至少有一个根。取中点 m=(a+b)/2:若 f(m)=0 便停止;否则保留端点函数值异号的半区间。每一步由连续性和异号性保留至少一个根。初始区间可能有多个根,方法并不找出所有根。
经 n 次二分后,区间长度为 (b−a)/2n;其中心 mn 到该区间内任何根 r 的距离至多为半个区间长度:
∣mn−r∣≤2n+1b−a.
因此只须令右边不超过 ε,便保证绝对误差不超过 ε。上述证明假设算术和符号判断精确;实际舍入可能影响符号,最终中点亦可能与端点相同;稳健的实现必须顾及这一点。
例如 f(x)=x2−2,由 [1,2] 开始。f(1.5)>0,保留 [1,1.5];f(1.25)<0,保留 [1.25,1.5];f(1.375)<0,保留 [1.375,1.5]。最后中点 1.4375 距区间内某根至多 0.0625,全程无须导数。
异号是充分条件而非必要条件:(x−1)2 在 [0,2] 两端皆为正,仍在 1 有根。没有连续性时,异号亦不足够:1/x 在零两侧异号,但在包含零的区间不连续,也没有零点。
牛顿迭代
在 f′(xn)=0 时,牛顿(Newton)迭代用切线 f(xn)+f′(xn)(x−xn) 近似曲线;令切线为零,得到
xn+1=xn−f′(xn)f(xn).
对 f(x)=x2−2,由 x0=1.5 开始,x1=17/12≈1.4166667,x2=577/408≈1.4142157。它们很接近 2,但快速收敛是局部结论,并不适用于所有起点。
若 f 在根 r 附近二次连续可微且 f′(r)=0,则起点充分接近 r 时,迭代有定义、留在该邻域并收敛至 r,且对某常数 C 有 ∣xn+1−r∣≤C∣xn−r∣2。
记 en=xn−r。由于 f′ 连续且 f′(r)=0,存在 ρ>0 与 m>0,使 f 在 J=[r−ρ,r+ρ] 上属于 C2,并且在 J 上 ∣f′(x)∣≥m。令 K=Jmax∣f′′∣、C=K/(2m);若 C=0 取 δ=ρ,否则取 δ=min(ρ,1/(2C))。
设 ∣en∣≤δ。则 xn∈J,故 f′(xn)=0,xn+1 有定义。从 xn 向 r 使用泰勒(Taylor)定理,对两点之间(因而在 J 内)的某个 ξn,
0=f(xn)+f′(xn)(r−xn)+21f′′(ξn)(r−xn)2.除以 f′(xn) 并代入牛顿公式,得
en+1=2f′(xn)f′′(ξn)en2,∣en+1∣≤Cen2≤Cδ∣en∣≤21∣en∣.由归纳法,只要 ∣e0∣≤δ,每个迭代值都有定义、留在 [r−δ,r+δ] 内,且 ∣en∣≤2−n∣e0∣→0。不等式 ∣en+1∣≤Cen2 就是二次界。邻域与常数依赖函数和根,定理并没有提供全局起点规则。
证明透视
邻域是怎样选出来的
每个假设只用一次。二次连续可微给出带点 ξn 的泰勒余项,并由紧致区间上的连续性给出有限的 K。条件 f′(r)=0 只用来在 r 附近保持 ∣f′∣≥m,使分母 f′(xn) 既非零又受控制。两者合起来产生一个常数 C=K/(2m)。
不显然的一步是选取 δ≤1/(2C)。单靠二次恒等式推不出收敛,因为 ∣en∣ 大时 Cen2 可以超过 ∣en∣。但在半径 δ 的邻域内有 Cen2≤21∣en∣,这同时完成两件事:使下一个迭代值留在常数仍然有效的邻域内,并迫使误差按几何级数递减。只有在收敛已知之后,这个界才读作二次收敛。若 f′(r)=0,m 须随邻域缩小,C 没有上界,论证根本无法开始。
起点与根同样重要。对 f(x)=x3−2x+2,牛顿映射把 0 送到 1,又把 1 送回 0;起点不够接近时,迭代可以循环而根本不收敛。
反例模式
二重根处二次界失效
一个诱人的说法是:牛顿法在光滑函数的每个根附近都二次收敛。取 f(x)=(x−1)2,它光滑、根为 1,但 f′(1)=0。对 xn=1,
xn+1=xn−2(xn−1)(xn−1)2=2xn+1,en+1=21en.若对所有足够大的 n 都有 ∣en+1∣≤Cen2,就得 21≤C∣en∣;但 en→0,这不可能。收敛只是线性的。修正后的命题正是上述定理:根必须是单根,f′(r)=0。对这个已知为二重根的 f,修正步 x−2f(x)/f′(x) 一步就落在 1。
停止与保护
步长小可能表示收敛,也可能来自舍入或尺度不佳。残差小必须配合敏感度判断:f(x)=10−12(x−1) 在 x=0 的残差虽为 10−12,根误差却是 1。若 x 与根 r 之间处处有 ∣f′∣≥m>0,中值定理才给出 ∣x−r∣≤∣f(x)∣/m。
在单根附近,步长 ∣xn+1−xn∣ 与误差 ∣xn−r∣ 的主导项相同,所以常被用作停止准则。在重根附近却不是这样。对 f(x)=(x−1)2 及 xn=1.1,步长为 f(xn)/f′(xn)=0.01/0.2=0.05,误差却是 0.1。没有导数界或夹逼区间时,步长小只是迹象,而不是保证。
一个实用策略是保持连续函数的异号区间,只在牛顿步安全地落于区间内时接受,否则二分,再用新点的符号更新区间。具体实现仍须规定接受及停止准则,但保留区间可持续提供存在性证明。
不动点观点
牛顿法可写成 xn+1=g(xn),其中 g(x)=x−f(x)/f′(x),只在分母非零时有定义。更一般地,若 g 在闭区间 I 上可微、把 I 映到自身,且区间上处处有 ∣g′(x)∣≤q<1,则从 I 任何起点的迭代均收敛至其中唯一的不动点。
中值定理给出 ∣g(x)−g(y)∣≤q∣x−y∣;相邻两项的距离因此按几何级数递减,其和有限,故迭代是闭区间内的Cauchy 序列。由连续性,极限是不动点;把同一不等式用于两个不动点便得唯一性。
这些条件充分但非必要。它们证明的是 g 的不动点,仍须核对该点是否解原方程。牛顿映射在单根处有 g′(r)=0,与局部快速收敛一致;但 f′ 为零时映射无定义,不能跨越该点套用定理。
例如 x2=2 可写成 g(x)=(x+2/x)/2。在 I=[1,2] 上,g 映区间到自身,且 ∣g′(x)∣=∣1−2/x2∣/2≤1/2,因此定理保证该区间内任何起点均收敛。这比观察几步似乎有效提供更强的依据。
根的敏感度与重根
设 f(r)=0、f′(r)=0,把方程扰动为 f(x)+η=0,其中常数 η 很小。若新根为 r+Δr,泰勒展开给出 f′(r)Δr+η 约为零,故 Δr≈−η/f′(r)。导数小会放大垂直扰动;这是绝对敏感度陈述。重新缩放函数也会缩放 η,因此必须说明单位和扰动模型。
重根的反应可能更剧烈。f(x)=x2 改成 x2−ε=0(ε>0)有两根 ±ε;改成 x2+ε=0 则没有实根。小垂直扰动可改变根的位置及实根数量。这不违反牛顿法二次收敛定理,因为零点处 f′(0)=0,不符合定理假设。
比较收敛速度
例如,若最终有 ∣en+1∣≤q∣en∣,其中 q<1,误差便线性收敛;若最终有 ∣en+1∣≤C∣en∣2,便二次收敛。二次迭代足够接近根后正确位数可快速增加;线性方法每步大致增加固定数目的位数。这些描述针对渐近误差,并非每步成本。牛顿法需要导数,远离根时可能失败;二分法则保留区间及简单的最坏情况界。
对 x2−2 从 x0=1 开始,牛顿步依次为 3/2、17/12、577/408。代入迭代式并化简,得到精确误差恒等式
xn+1−2=2xn(xn−2)2.这里正的迭代值远离零,因此平方误差解释了快速收敛。起点可能与后续点位于根的不同侧;牛顿序列本身一般不保持夹逼区间。
二分法的收敛证明
保留的闭区间互相嵌套、长度趋零,且每个都由介值定理包含根;端点因而趋向共同极限。连续性证明极限为零点:若极限的函数值严格为正或负,则充分接近的两个端点会有相同符号,与始终异号矛盾。故存在性及区间收缩共同解释收敛;单有区间长度趋零,没有连续性和异号,不能证明极限是根。
后验误差与停止例子
先验界在计算前选定,例如二分法所需步数;后验界利用计算后得到的信息。若保留连续异号区间 [an,bn],其中点与区间内任何根的距离至多 (bn−an)/2,与之前采取了多少安全牛顿步无关。相反,牛顿修正量 ∣f(xn)/f′(xn)∣ 本身一般不是严格误差界,因为它依靠切线近似。
考虑 f(x)=x2−2 及区间 [1,2],假设计算得 x=1.4142。区间上 f′(x)=2x≥2,中值定理给出 ∣x−2∣≤∣x2−2∣/2。此处 x2−2=−0.00003836,故界为 0.00001918。精确误差更小,但推导这个界并不需要知道精确根的小数展开。导数下界须在近似点与根之间成立,只知道近似点的导数并不足够。
停止规则应说明所需绝对或相对容许误差,以及所界定的量。夹逼宽度控制绝对根误差;残差准则在尺度不同时可能方便,但要配合敏感度估计才能保证根的准确度。接近零时,即使用相对准则也需考虑绝对容许误差。此外,应设最大步数或停滞检查,避免不断重复同一浮点值;若未达所需保证,停止时须如实报告,而非称结果准确。
对下面最后一题的 f(x)=x3−1,f′(x)=3x2 在零处为零,因此“处处 f′(x)>0”的较强命题不成立。然而因式分解 y3−x3=(y−x)(y2+xy+x2) 直接证明严格递增。反过来,单有导数非负仍容许函数在某区间为常数;严格递增需要额外论证。
存在、唯一、收敛和迭代值的数值准确度是四个不同的结论,各有自己的假设。
总结
连续异号区间证明根存在,并以宽度控制中点误差;它既不保证唯一,也可能漏掉不变号的根。牛顿切线迭代在单根附近常有二次收敛,但导数及起点假设不可省略。保护式方法可用夹逼区间约束牛顿步,同时保留局部快速收敛的可能。
判断结果时应先确定证据:夹逼区间、配合导数下界的残差,或另有根据的后验估计。f(x) 的大小取决于函数尺度,距根的距离还取决于斜率。因此把 f 乘以非零常数不改变根,却改变原始残差。停止规则须考虑此区别及有限精度停滞。
找到一个根并未解决所有根的问题。二分法在一个区间找到根之后,原区间内外仍可能有其他根;要计算根的数目,需要单调性或其他计算根个数的定理等额外信息。有限个采样点的数值图像无法排除采样点之间未观察到的振荡。
练习
快速检查
(从 [1,2] 二分求 x3−2 的根,至少多少次能保证中点误差不超过 10−3?)
使用误差界 (b−a)/2n+1。
解答 · 答案
要求 2−(n+1)≤10−3。由 210=1024,n=9 足够;此界下 n=8 不足。
快速检查
(对 x2−3 从 x0=2 做一步牛顿法。)
这里 f′(x)=2x。
解答 · 答案
x1=2−(4−3)/4=7/4。
解答 · 答案
函数可如 (x−1)2 在 [0,2] 接触横轴而不变号;穿过横轴两次也可使端点同号。
快速检查
(设 f(x)=x3−1,区间为 [0,2]。证明其中恰有一个实根,然后做两步二分。最终区间中点是否必然是精确根?说明什么信息保证唯一性。)
解答 · 答案
函数连续且端点值异号。它在实数上严格递增,因为 y>x 时 y3−x3=(y−x)(y2+xy+x2)>0;所以根唯一。第一个中点是 1,且 f(1)=0,方法即停止,无须第二步。恰好命中是本例的特殊性质,并非一般保证;没有单调性时,初始异号只保证至少一个根,并不保证恰好一个。