MathLabs

应用与计算数学

方程的近似解法

像二分法和牛顿法这样的数值方法,能让计算机逐步计算出方程的根。

直观直觉:在根附近放大观察

假设你要寻找方程 f(x)=0f(x)=0 的一个根 rr,但没有任何代数公式能精确给出 rr。数值方法会构造一个猜测序列 x0,x1,x2,…x_0, x_1, x_2,\dots,它在每一步都越来越接近 rr,这很像不断放大 ff 的图像、朝着它与横轴相交的那一点靠近,从而读出越来越多正确的小数位。下面三种方法的区别仅在于它们把当前猜测 xnx_n 变成更好的下一个猜测 xn+1x_{n+1} 的方式有多巧妙。

曲线上过两个邻近点的割线随着步长缩小到0而逐渐旋转成切线,展示了牛顿法背后的几何思想。
把割线的步长 hh 拖向0,观察它逐渐贴合到 x0x_0 处斜率为 f′(x0)f'(x_0) 的切线上:这正是牛顿法用来走向下一个猜测值 x1=x0−f(x0)f′(x0)x_1 = x_0 - \dfrac{f(x_0)}{f'(x_0)} 所沿着的切线,而不是更粗糙的割线斜率 f(x0+h)−f(x0)h\dfrac{f(x_0+h)-f(x_0)}{h}。

大学定义:三种求根方法

定义: 二分法

若连续函数 ff 在区间 [a,b][a,b] 上满足 f(a)f(b)<0f(a)f(b)<0,介值定理保证其内部存在一个根。二分法在每一步都将该区间对半分:计算中点 c=a+b2c=\dfrac{a+b}{2},求出 f(c)f(c),然后保留仍存在变号的那一半,并重复此过程。

∣xn−r∣≤b−a2n+1|x_n - r| \le \dfrac{b-a}{2^{n+1}}

这里 ∣xn−r∣≤b−a2n+1|x_n - r| \le \dfrac{b-a}{2^{n+1}} 给出了第 nn 个中点 xnx_n 与真实根 rr 之间距离的上界:由于区间宽度 L=b−aL=b-a 在每一步都减半,最坏情况下的误差也随之减半,因此仅经过 n=4n=4 步,不确定性就缩小到 L/32L/32。这种有保证、可预测的收缩速度正是二分法的全部魅力所在——它虽然慢,但从不会不收敛。

定义: 牛顿法

牛顿法用 xnx_n 附近曲线的切线 y=f(xn)+f′(xn)(x−xn)y=f(x_n)+f'(x_n)(x-x_n) 来代替曲线,并把该切线与横轴的交点作为下一个猜测值 xn+1x_{n+1},从而得到迭代公式 xn+1=xn−f(xn)f′(xn)x_{n+1} = x_n - \dfrac{f(x_n)}{f'(x_n)}。它在每一步都需要导数 f′f',但一旦有效,收敛速度会比二分法快得多。

xn+1=xn−f(xn)f′(xn)x_{n+1} = x_n - \dfrac{f(x_n)}{f'(x_n)}

第三种视角把两者统一起来:把方程改写成关于某个函数 gg 的不动点问题 x=g(x)x=g(x),使得 ff 的根成为 gg 的不动点,然后从任意 x0x_0 出发迭代 xn+1=g(xn)x_{n+1} = g(x_n)。二分法与牛顿法都是这一思想在 gg 取不同选择时的特例。

三种求根方法比较
方法迭代公式收敛阶所需条件
二分法c=a+b2c=\dfrac{a+b}{2}线性(11)ff 连续,f(a)f(b)<0f(a)f(b)<0
牛顿法xn+1=xn−f(xn)f′(xn)x_{n+1} = x_n - \dfrac{f(x_n)}{f'(x_n)}二次(22)ff 二次可微,f′(r)≠0f'(r) \ne 0,x0x_0 接近 rr
不动点迭代xn+1=g(xn)x_{n+1} = g(x_n)一般为线性(11)在 rr 附近 ∣g′(x)∣≤L<1|g'(x)| \le L < 1

大学关键定理

定理: 二分法的收敛性与误差界

设 ff 在 [a,b][a,b] 上连续且满足 f(a)f(b)<0f(a)f(b)<0。则二分法生成的中点 xn=an+bn2x_n=\dfrac{a_n+b_n}{2} 满足 xn→rx_n \to r,其中 rr 是 [a,b][a,b] 内的某个根,并且第 nn 步后的误差满足 ∣xn−r∣≤b−a2n+1|x_n - r| \le \dfrac{b-a}{2^{n+1}}。

为什么成立?

每一步都把根困在一个不断收缩的“箱子”里,而一个始终包含根、并收缩为一点的箱子,必然收缩到根本身。

证明

第一步(不变量)。设 a0=aa_0=a、b0=bb_0=b。在第 nn 步,我们维持不变量 f(an)f(bn)<0f(a_n)f(b_n)<0,即根被困在 [an,bn][a_n,b_n] 内某处。由假设,该不变量最初成立。给定 [an,bn][a_n,b_n],计算中点 xn=an+bn2x_n=\dfrac{a_n+b_n}{2} 并求出 f(xn)f(x_n):若其符号与 f(an)f(a_n) 相反,则令 an+1=an, bn+1=xna_{n+1}=a_n,\ b_{n+1}=x_n,否则令 an+1=xn, bn+1=bna_{n+1}=x_n,\ b_{n+1}=b_n(若恰好 f(xn)=0f(x_n)=0,则 xnx_n 就是根,过程终止)。无论哪种情况都再次有 f(an+1)f(bn+1)<0f(a_{n+1})f(b_{n+1})<0,因此该不变量由归纳法得以保持。

第二步(宽度收缩)。按构造,每个新区间恰好是前一个区间的一半,故对一切 n≥0n \ge 0 都有 bn−an=b−a2nb_n-a_n = \dfrac{b-a}{2^n}。由于根 rr 在每一步都位于 [an,bn][a_n,b_n] 内(由第一步),而中点 xnx_n 也位于 [an,bn][a_n,b_n] 内,二者都在宽度为 b−a2n\dfrac{b-a}{2^n} 的同一区间内,故已有 ∣xn−r∣≤b−a2n|x_n - r| \le \dfrac{b-a}{2^n} 成立;稍微精细一点地计数(从中点量到某个端点)即得所述的界 ∣xn−r∣≤b−a2n+1|x_n - r| \le \dfrac{b-a}{2^{n+1}}。

第三步(收敛)。由于当 n→∞n\to\infty 时 b−a2n+1→0\dfrac{b-a}{2^{n+1}} \to 0,第二步中的夹逼即迫使 xn→rx_n \to r。这一部分甚至不需要 ff 除初始变号条件之外的连续性——连续性只用于保证一开始 [a,b][a,b] 内部确实存在一个根,这正是在第0步应用的介值定理。

定理: 牛顿法的二次收敛性

设 ff 在根 rr 附近二次连续可微,且 f′(r)≠0f'(r) \ne 0。则存在 rr 的一个邻域,使得若牛顿迭代从该邻域内部出发,迭代序列收敛于 rr,并且对某常数 C=max⁡∣f′′∣2min⁡∣f′∣C=\dfrac{\max|f''|}{2\min|f'|}(最大值与最小值均在该邻域上取)满足 ∣xn+1−r∣≤C ∣xn−r∣2|x_{n+1}-r| \le C\,|x_n-r|^2。

为什么成立?

切线对光滑曲线的逼近非常好,以至于它产生的误差与已走过距离的平方成正比,因此每多正确一位小数,到下一步正确位数大约翻倍。

证明

第一步(围绕当前猜测值作泰勒展开)。由于 ff 二次可微,带拉格朗日余项的泰勒定理给出对某个 ξn\xi_n between xnx_n and rr 有 f(r)=f(xn)+f′(xn)(r−xn)+12f′′(ξn)(r−xn)2f(r) = f(x_n) + f'(x_n)(r-x_n) + \tfrac12 f''(\xi_n)(r-x_n)^2。这是精确等式而非近似,因为余项承载了全部二阶误差。

第二步(代入根的条件)。由于 f(r)=0f(r)=0,左边为零,剩下 0=f(xn)+f′(xn)(r−xn)+12f′′(ξn)(r−xn)20 = f(x_n) + f'(x_n)(r-x_n) + \tfrac12 f''(\xi_n)(r-x_n)^2。两边同除以 f′(xn)f'(x_n)(在 rr 附近非零,因为 f′(r)≠0f'(r) \ne 0 且 f′f' 连续),分离出 r−xnr - x_n:0=f(xn)f′(xn)+(r−xn)+f′′(ξn)2f′(xn)(r−xn)20 = \dfrac{f(x_n)}{f'(x_n)} + (r-x_n) + \dfrac{f''(\xi_n)}{2f'(x_n)}(r-x_n)^2。

第三步(识别出牛顿步)。整理得 r−(xn−f(xn)f′(xn))=−f′′(ξn)2f′(xn)(r−xn)2r - \left(x_n - \dfrac{f(x_n)}{f'(x_n)}\right) = -\dfrac{f''(\xi_n)}{2f'(x_n)}(r-x_n)^2。左边括号内恰是牛顿更新 xn+1x_{n+1},故用 en=xn−re_n = x_n - r 可写成 r−xn+1=−f′′(ξn)2f′(xn) en2r - x_{n+1} = -\dfrac{f''(\xi_n)}{2f'(x_n)}\,e_n^2,即 en+1=−f′′(ξn)2f′(xn) en2e_{n+1} = -\dfrac{f''(\xi_n)}{2f'(x_n)}\,e_n^2。

第四步(界定常数)。取绝对值,并用该邻域上的极值 max⁡∣f′′∣\max|f''| 和 1/min⁡∣f′∣1/\min|f'| 分别界定 ∣f′′(ξn)∣|f''(\xi_n)| 与 1/∣f′(xn)∣1/|f'(x_n)|,即得 C=max⁡∣f′′∣2min⁡∣f′∣C=\dfrac{\max|f''|}{2\min|f'|} 下的 ∣xn+1−r∣≤C ∣xn−r∣2|x_{n+1}-r| \le C\,|x_n-r|^2。一旦 C ∣x0−r∣<1C\,|x_0-r| < 1,该递推关系就迫使 ∣xn−r∣|x_n - r| 收缩到 00,从而证明收敛性,而 ∣xn+1−r∣≤C ∣xn−r∣2|x_{n+1}-r| \le C\,|x_n-r|^2 中的平方正是二次收敛速度的体现。

定理: 不动点迭代的收敛性

设 g:[a,b]→[a,b]g:[a,b]\to[a,b] 连续可微,且对一切 x∈[a,b]x\in[a,b] 都有 ∣g′(x)∣≤L<1|g'(x)| \le L < 1。则 gg 在 [a,b][a,b] 内有唯一不动点 rr,且对任意起点 x0∈[a,b]x_0 \in [a,b],迭代 xn+1=g(xn)x_{n+1}=g(x_n) 收敛于 rr,并满足 ∣xn−r∣≤Ln∣x0−r∣|x_n - r| \le L^n |x_0 - r|。

为什么成立?

斜率的绝对值小于一意味着每次施加 g 都会使各点彼此更靠近,因此无论从哪里出发,反复的压缩都必然使整个区间坍缩到同一个点。

证明

第一步(用介值定理证明存在性)。设 h(x)=g(x)−xh(x)=g(x)-x。由 g(a)∈[a,b]g(a)\in[a,b] 得 g(a)≥ag(a)\ge a,即 h(a)≥0h(a)\ge0;同理由 g(b)≤bg(b)\le b 得 h(b)≤0h(b)\le0。由于 hh 连续,介值定理给出某个 rr 使得 h(r)=0h(r)=0,即 g(r)=rg(r)=r:不动点存在。

第二步(用中值定理证明唯一性)。设 r1,r2∈[a,b]r_1,r_2\in[a,b] 都是不动点且 r1≠r2r_1\ne r_2。中值定理给出二者之间某个 cc 使 g(r1)−g(r2)=g′(c)(r1−r2)g(r_1)-g(r_2) = g'(c)(r_1-r_2);由 g(r1)=r1g(r_1)=r_1 与 g(r2)=r2g(r_2)=r_2,这可写成 r1−r2=g′(c)(r1−r2)r_1-r_2 = g'(c)(r_1-r_2),故 ∣r1−r2∣=∣g′(c)∣ ∣r1−r2∣≤L ∣r1−r2∣|r_1-r_2| = |g'(c)|\,|r_1-r_2| \le L\,|r_1-r_2|。由于 L<1L<1 且 ∣r1−r2∣>0|r_1-r_2|>0,这产生矛盾,故 r1=r2r_1=r_2。

第三步(每一步都收缩)。对任意 xn∈[a,b]x_n\in[a,b],对 g(xn)−g(r)g(x_n)-g(r) 应用中值定理:存在 xnx_n 与 rr 之间的某个 cnc_n 使 g(xn)−g(r)=g′(cn)(xn−r)g(x_n)-g(r) = g'(c_n)(x_n-r)。由 g(r)=rg(r)=r 与 xn+1=g(xn)x_{n+1}=g(x_n),左边即为 xn+1−rx_{n+1}-r,故 ∣xn+1−r∣=∣g′(cn)∣ ∣xn−r∣≤L ∣xn−r∣|x_{n+1}-r| = |g'(c_n)|\,|x_n-r| \le L\,|x_n-r|。

第四步(反复施加收缩)。从 n=0n=0 开始反复应用第三步,得 ∣x1−r∣≤L∣x0−r∣|x_1-r|\le L|x_0-r|,再得 ∣x2−r∣≤L∣x1−r∣≤L2∣x0−r∣|x_2-r|\le L|x_1-r|\le L^2|x_0-r|,归纳可得对一切 nn 都有 ∣xn−r∣≤Ln∣x0−r∣|x_n - r| \le L^n |x_0 - r|。由于 0≤L<10\le L<1,当 n→∞n\to\infty 时右边趋于 00,从而证明 xn→rx_n\to r。

大学实际应用与典型例题

求根是无数没有封闭形式解的计算背后隐藏的引擎。工程师用牛顿法求解结构与电路设计中的非线性方程组;金融领域用它从债券价格反推未知利率,或从期权价格反推隐含波动率;计算机图形学用它求光线与隐式曲面的交点;而每一台科学计算器在内部都通过运行牛顿法的几步来计算 2\sqrt{2} 或立方根。由于二分法万无一失,它是求根库中在牛顿法有发散风险时使用的后备方案。

例题: 对没有代数求根公式的三次方程使用二分法

某力学系统的平衡位置满足 x3−x−2=0x^3-x-2=0。利用区间 [1,2][1,2](其中 f(1)=−2<0f(1)=-2<0,f(2)=4>0f(2)=4>0),执行两次二分步骤,求出所得中点 x2x_2。

解答

第一步:计算第一个中点。x0=1+22=1.5x_0 = \dfrac{1+2}{2} = 1.5,且 f(1.5)=1.53−1.5−2=−0.125<0f(1.5) = 1.5^3 - 1.5 - 2 = -0.125 < 0,故根位于 [1.5,2][1.5, 2] 内,因为 ff 在此处变号(f(1.5)<0f(1.5)<0, f(2)>0f(2)>0)。

第二步:计算第二个中点。x1=1.5+22=1.75x_1 = \dfrac{1.5+2}{2} = 1.75,且 f(1.75)=1.753−1.75−2=1.609375>0f(1.75) = 1.75^3 - 1.75 - 2 = 1.609375 > 0,故根位于 [1.5,1.75][1.5, 1.75]。

第三步:计算 x2x_2。x2=1.5+1.752=1.625x_2 = \dfrac{1.5+1.75}{2} = 1.625。

第四步:解释。仅经过两步,搜索区间就从宽度 11 缩小到 0.250.25,而 x2=1.625x_2=1.625 与真实根 r≈1.5214r\approx1.5214 的距离已不超过 0.1250.125,这与二分法定理给出的误差界 ∣x2−r∣≤2−123=0.125|x_2-r|\le \dfrac{2-1}{2^{3}}=0.125 一致。

例题: 用牛顿法手算平方根

在计算器出现之前,工程师是这样计算平方根的:为求 5\sqrt{5},从 x0=2x_0=2 出发,对 f(x)=x2−5f(x)=x^2-5 应用牛顿法,计算 x1x_1 和 x2x_2。

解答

第一步:建立迭代式。这里 f(x)=x2−5f(x)=x^2-5,f′(x)=2xf'(x)=2x,故牛顿更新式为 xn+1=xn−xn2−52xnx_{n+1}=x_n-\dfrac{x_n^2-5}{2x_n}。

第二步:计算 x1x_1。当 x0=2x_0=2 时:x1=2−22−52⋅2=2−−14=2.25x_1 = 2 - \dfrac{2^2-5}{2\cdot2} = 2 - \dfrac{-1}{4} = 2.25。

第三步:计算 x2x_2。当 x1=2.25x_1=2.25 时:x2=2.25−2.252−52⋅2.25=2.25−0.06254.5≈2.236111x_2 = 2.25 - \dfrac{2.25^2-5}{2\cdot2.25} = 2.25 - \dfrac{0.0625}{4.5} \approx 2.236111。

第四步:解释。真实值为 5≈2.236068\sqrt{5}\approx2.236068,因此仅经过两步,x2x_2 就已精确到小数点后四位——从 x1x_1 到 x2x_2 正确位数大约翻了一倍,这正是上面证明的二次收敛的标志。

从 [a,b]=[0,1][a,b]=[0,1] 开始二分法,执行 n=5n=5 次迭代,∣x5−r∣|x_5 - r| 的保证误差界是多少?

以下哪个公式正确给出了牛顿法的一步?

某债券交易员从猜测值 y0y_0 出发,用牛顿法求解非线性定价方程 P(y)=0P(y)=0 得到收益率 yy。以下哪种情况最可能导致迭代不收敛?

为使 [a,b][a,b] 上的不动点迭代 xn+1=g(xn)x_{n+1} = g(x_n) 从任意 x0∈[a,b]x_0 \in [a,b] 出发都保证收敛到不动点,需要满足哪个条件?