Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

4.1 对分法、简单迭代与收敛阶

对应教材 4.1.1–4.1.4、定理 4.1–4.5、例 1–2、习题 1–5；对应老师第 7 讲末、第 8 讲、第 9 讲 §一–§二。 主线：先保证“有根、能夹住”，再讨论“迭代收敛”，最后用“收敛阶”比较快慢。

4.1.1 对分法

设 f∈C[a,b]f\in C[a,b]，f(a)f(b)<0f(a)f(b)\lt0，且 (a,b)(a,b) 内只有一个根 ss。对分法：

  1. 令 a0=a,b0=ba_0=a,b_0=b；
  2. 对 k=0,1,…k=0,1,\dots：取 xk=ak+bk2x_k=\frac{a_k+b_k}{2}；
  3. 若 bk−ak≤εb_k-a_k\le\varepsilon 或 ∣f(xk)∣≤η|f(x_k)|\le\eta，停止；
  4. 若 f(ak)f(xk)<0f(a_k)f(x_k)\lt0，令 ak+1=ak,bk+1=xka_{k+1}=a_k,b_{k+1}=x_k；否则令 ak+1=xk,bk+1=bka_{k+1}=x_k,b_{k+1}=b_k。

误差直接由区间长度给出： ∣xk−s∣≤bk−ak2=b−a2k+1. |x_k-s|\le\frac{b_k-a_k}{2}=\frac{b-a}{2^{k+1}}. 要绝对误差不超过 ε\varepsilon，取 k≥log⁡2b−aε−1. k\ge\log_2\frac{b-a}{\varepsilon}-1. 收敛速度与公比 1/21/2 的等比数列同阶（线性收敛）。对分法只要求连续，最稳；但只能求实根，不能求偶重根和复根，且收敛慢。

4.1.2 简单迭代法

把 f(x)=0f(x)=0 改写成等价形式 x=φ(x)x=\varphi(x)，迭代 xk+1=φ(xk). x_{k+1}=\varphi(x_k). 若 s=φ(s)s=\varphi(s)，则 ss 是 φ\varphi 的不动点，也是原方程的根。

定理 4.1（全局压缩）：设 φ∈C[a,b]\varphi\in C[a,b]，在 (a,b)(a,b) 内可导，且

  1. 当 x∈[a,b]x\in[a,b] 时，φ(x)∈[a,b]\varphi(x)\in[a,b]（自映射）；
  2. 存在 L<1L\lt1，使 ∣φ′(x)∣≤L|\varphi&#x27;(x)|\le L 对 x∈(a,b)x\in(a,b) 成立（压缩）。

则 φ\varphi 在 [a,b][a,b] 内有唯一不动点 ss，且对任意 x0∈[a,b]x_0\in[a,b]，迭代收敛到 ss，并有 ∣xk−s∣≤Lk1−L∣x1−x0∣. |x_k-s|\le\frac{L^k}{1-L}|x_1-x_0|.

证明要点：自映射 + 压缩给出唯一不动点（存在性用介值定理，唯一性用压缩）；再由中值定理 ∣xk+1−s∣=∣φ(xk)−φ(s)∣≤L∣xk−s∣, |x_{k+1}-s|=|\varphi(x_k)-\varphi(s)|\le L|x_k-s|, 反复递推即得。■\blacksquare

定理 4.2（局部收敛）：若 φ′(s)\varphi&#x27;(s) 存在且 ∣φ′(s)∣<1|\varphi&#x27;(s)|\lt1，则存在 δ>0\delta\gt0，当 x0∈(s−δ,s+δ)x_0\in(s-\delta,s+\delta) 时迭代收敛到 ss。

证明要点：由 ∣φ′(s)∣<1|\varphi&#x27;(s)|\lt1 和导数的连续性，取 L∈(∣φ′(s)∣,1)L\in(|\varphi&#x27;(s)|,1)，在 ss 的小邻域内 ∣φ′(x)∣≤L|\varphi&#x27;(x)|\le L，再用定理 4.1。■\blacksquare

例 1（教材 4.1.2）：方程 x3−x−1=0x^3-x-1=0 在 [1,2][1,2] 内有唯一根。改写成 x=φ(x)=x+13. x=\varphi(x)=\sqrt[3]{x+1}. 在 [1,2][1,2] 上 φ′(x)=13(x+1)−2/3≤1343<1\varphi&#x27;(x)=\frac{1}{3}(x+1)^{-2/3}\le\frac{1}{3\sqrt[3]{4}}\lt1，且 φ([1,2])⊂[1,2]\varphi([1,2])\subset[1,2]，故收敛。取 x0=1.5x_0=1.5：

kk012345
xkx_k1.51.357211.330861.325881.324941.32476

根约 s≈1.32472s\approx1.32472。收敛是线性的，速度由 φ′(s)≈0.38\varphi&#x27;(s)\approx0.38 决定。

4.1.3 收敛阶

设 xk→sx_k\to s，ek=xk−se_k=x_k-s。若存在 p≥1p\ge1、C>0C\gt0，使 lim⁡k→∞∣ek+1∣∣ek∣p=C, \lim_{k\to\infty}\frac{|e_{k+1}|}{|e_k|^p}=C, 称迭代为 pp 阶收敛；p=1p=1 为线性收敛，p=2p=2 为平方收敛。

定理 4.3（一阶判据）：若 φ\varphi 在 ss 附近充分光滑，φ′(s)≠0\varphi&#x27;(s)\ne0，则简单迭代是线性收敛的，且 lim⁡k→∞ek+1ek=φ′(s). \lim_{k\to\infty}\frac{e_{k+1}}{e_k}=\varphi&#x27;(s).

定理 4.4（高阶判据）：若 φ′(s)=φ′′(s)=⋯=φ(m−1)(s)=0,φ(m)(s)≠0, \varphi&#x27;(s)=\varphi&#x27;&#x27;(s)=\cdots=\varphi^{(m-1)}(s)=0,\qquad \varphi^{(m)}(s)\ne0, 则迭代是 mm 阶收敛的，且 lim⁡k→∞ek+1ekm=φ(m)(s)m!. \lim_{k\to\infty}\frac{e_{k+1}}{e_k^m}=\frac{\varphi^{(m)}(s)}{m!}.

读法：想加速，就让 φ\varphi 在根处的前几阶导数尽量为零。Newton 法正是令 φ′(s)=0\varphi&#x27;(s)=0，所以至少二阶。

4.1.4 Steffensen 加速

对线性收敛的简单迭代，用两次迭代值做 Aitken 外推： xk+1=xk−(φ(xk)−xk)2φ(φ(xk))−2φ(xk)+xk. x_{k+1}=x_k-\frac{(\varphi(x_k)-x_k)^2}{\varphi(\varphi(x_k))-2\varphi(x_k)+x_k}. 这就是 Steffensen 迭代。它把“线性收敛”加速到“平方收敛”，且不需要导数。

定理 4.5：若 φ′(s)≠0\varphi&#x27;(s)\ne0，φ\varphi 在 ss 附近二阶连续可导，则 Steffensen 迭代在 ss 的某邻域内平方收敛。

例 2（教材 4.1.4）：仍取 x3−x−1=0x^3-x-1=0、φ(x)=x+13\varphi(x)=\sqrt[3]{x+1}。Steffensen 从 x0=1.5x_0=1.5 出发：

kkxkx_k∣f(xk)∣|f(x_k)|
01.50000000008.75×10−18.75\times10^{-1}
11.32489918247.73×10−47.73\times10^{-4}
21.32471795758.94×10−108.94\times10^{-10}
31.32471795722.22×10−162.22\times10^{-16}

2 次就到 10−910^{-9}，3 次到机器精度；简单迭代 5 次才到 10−410^{-4}。代价是每步多算两次 φ\varphi。

4.1.5 习题（教材习题 1–5）

4.1 · 对分法（教材习题 1）

用对分法求 x3−3x+1=0x^3-3x+1=0 的最大正根，以及 x+sin⁡x=1x+\sin x=1 的根，绝对误差限 10−310^{-3}。

参考答案

先隔离根：x3−3x+1x^3-3x+1 在 [1,2][1,2] 变号，最大正根约 1.5321.532；x+sin⁡x−1x+\sin x-1 在 [0,1][0,1] 变号，根约 0.5110.511。按 k≥log⁡2((b−a)/10−3)−1k\ge\log_2((b-a)/10^{-3})-1 估步数，约 10 步。

4.2 · 简单迭代（教材习题 2）

用简单迭代求 ex+10x−2=0e^x+10x-2=0、x−tan⁡(x−1)=0x-\tan(x-1)=0、e−x=cos⁡xe^{-x}=\cos x 的根，相对差 ≤10−6\le10^{-6}，并说明收敛理由。

参考答案

分别改写成 x=φ(x)x=\varphi(x)，验证 ∣φ′(s)∣<1|\varphi&#x27;(s)|\lt1 或区间压缩；迭代到 ∣xk−xk−1∣/∣xk∣≤10−6|x_k-x_{k-1}|/|x_k|\le10^{-6}。若 ∣φ′∣≥1|\varphi&#x27;|\ge1，换等价形式或改用 Newton/割线。

4.3 · 收敛阶判断（教材习题 3）

证明教材习题 3 的迭代序列收敛，并判断阶。

参考答案

先证根存在、迭代自映射且压缩；再算 φ′(s)\varphi&#x27;(s)：若 ≠0\ne0 则线性，若 =0=0 且 φ′′(s)≠0\varphi&#x27;&#x27;(s)\ne0 则二阶。按定理 4.3/4.4 下结论。

4.4 · 三阶迭代（教材习题 4）

证明 xk+1=xk(xk2+3a)3xk2+ax_{k+1}=\frac{x_k(x_k^2+3a)}{3x_k^2+a} 收敛到 a\sqrt a，且三阶收敛。

参考答案

这是 a\sqrt a 的 Halley 型迭代；验证 φ(a)=a\varphi(\sqrt a)=\sqrt a，并算 φ′(a)=φ′′(a)=0\varphi&#x27;(\sqrt a)=\varphi&#x27;&#x27;(\sqrt a)=0、φ′′′(a)≠0\varphi&#x27;&#x27;&#x27;(\sqrt a)\ne0，由定理 4.4 得三阶。

4.5 · Steffensen（教材习题 5）

用 Steffensen 迭代求指定方程的根。

参考答案

按 4.1.4 公式，每步算 φ(xk)\varphi(x_k) 与 φ(φ(xk))\varphi(\varphi(x_k))；平方收敛，通常 2–4 步到高精度。注意分母接近零时改用简单迭代或 Newton。

覆盖核对

本节覆盖教材 4.1.1–4.1.4、定理 4.1–4.5、例 1–2、习题 1–5；老师第 7 讲末、第 8 讲、第 9 讲 §一–§二。下一节：4.1.5–4.1.8 Newton 法与割线法。