Skip to content

Solutions of Equations in One Variable

本章致力于求解

f(x)=0 f(x)=0

其中 xx 是一元标量。

The Bisection Method

二分法（Bisection Method）要求 f∈C[a,b]f\in C[a, b]，且 f(a)f(a) 与 f(b)f(b) 异号。根据连续函数的介值定理，ff 在 [a,b][a, b] 上至少有一个根。

其思想非常简单，不断考虑区间中点 pnp_n，等于 0 则找到根，不等于 0 则用来替换与之同号的区间端点，从而不断缩小区间。数学归纳可以证明，迭代序列 {pn}\{p_n\} 和收敛到的零点 pp 满足

∣pn−p∣⩽b−a2n,n⩾1 |p_n-p|\leqslant\frac{b-a}{2^n}, \quad n\geqslant 1

分析其优缺点：

  • pros
    • 简单，只需要连续的 ff
    • 必然收敛到一个根
  • cons:
    • 收敛较慢
    • 一个好的中间近似解可能被无意丢弃
    • 无法找到重根、复根

Fixed-Point Iteration

使用不动点迭代，首先将原方程求根问题进行转换

f(x)=0  ⟺  g(x):=f(x)+x=x f(x)=0\iff g(x):=f(x)+x=x

于是将求根问题转换为求不动点问题。当然，定义 g(x)g(x) 为 x−f(x)x-f(x) 或者 x+3f(x)x+3f(x) 等等都是可以的。

Fixed Point

给定函数 gg，当 pp 满足

p=g(p) p=g(p)

则称 pp 为 gg 的不动点 (Fixed Point) 。

不动点迭代法即选定一个初始值 p0p_0，随后使用 pn=g(pn−1)p_n=g(p_{n-1}) 进行迭代。如果数列 {pn}\{p_n\} 收敛到 pp，而且 gg 连续，那么就有

p=lim⁡n→∞pn=lim⁡n→∞g(pn−1)=g(lim⁡n→∞pn−1)=g(p) p=\lim_{n\to\infty}p_n=\lim_{n\to\infty}g(p_{n-1})=g(\lim_{n\to\infty}p_{n-1})=g(p)

因此问题的关键成为如何保证 {pn}\{p_n\} 收敛。这里有一个定理：

Fixed-Point Theorem

如果 g∈C[a,b]g\in C[a, b] 满足

  1. g([a,b])∈[a,b]g([a, b])\in [a, b]
  2. ∀ x∈(a,b)\forall\: x\in (a, b), ∃ g′(x)\exists\: g'(x), and ∃ k∈(0,1) s.t. ∣g′(x)∣⩽k\exists\: k\in (0, 1)\text{ s.t. }|g'(x)|\leqslant k

那么 ∀ p0∈[a,b]\forall\: p_0\in [a, b]，数列 {pn}\{p_n\} 收敛到 [a,b][a, b] 上唯一的不动点 pp。

Proof

预设不动点 pp 的存在唯一性。由于 g([a,b])∈[a,b]g([a, b])\in [a, b]，所以从 p0∈[a,b]p_0\in [a, b] 出发，迭代得到 pn=g(pn−1)p_n=g(p_{n-1}) 都落在 [a,b][a, b] 之中。随后，根据 Lagrange 中值定理有

∣pn−p∣=∣g(pn−1)−g(p)∣=∣g′(ξ)∣∣pn−1−p∣⩽k∣pn−1−p∣ |p_n - p| = |g(p_{n-1})-g(p)| = |g'(\xi)||p_{n-1}-p| \leqslant k|p_{n-1}-p|

所以 ∣pn−p∣⩽k∣pn−1−p∣⩽k2∣pn−2−p∣⩽⋯⩽kn∣p0−p∣|p_n-p|\leqslant k|p_{n-1}-p|\leqslant k^2|p_{n-2}-p|\leqslant\cdots\leqslant k^n|p_0-p|。由于 k∈(0,1)k\in (0, 1)，所以 lim⁡n→∞kn=0\lim\limits_{n\to\infty}k^n=0，于是 lim⁡n→∞∣pn−p∣=0\lim\limits_{n\to\infty}|p_n-p|=0，即得 lim⁡n→∞pn=p\lim\limits_{n\to\infty}p_n=p。

注意这里预设了 [a,b][a, b] 上 gg 有唯一的不动点 pp，这是因为定理条件已经满足了不动点存在唯一性的充分条件，在这里给出其相关定理：

Existence and Uniqueness of Fixed Point

  1. （存在性）如果 g∈C[a,b]g\in C[a, b]，且 g([a,b])⊆[a,b]g([a, b])\subseteq [a, b]，那么 gg 在 [a,b][a, b] 上有至少一个不动点
  2. （唯一性）在以上的基础上，∀ x∈(a,b)\forall\: x\in (a, b), ∃ g′(x)\exists\: g'(x), and ∃ k∈(0,1) s.t. ∣g′(x)∣⩽k\exists\: k\in (0, 1)\text{ s.t. }|g'(x)|\leqslant k，那么 gg 在 [a,b][a, b] 有且只有一个不动点
Proof
    1. 如果 g(a)=ag(a)=a 或者 g(b)=bg(b)=b，那么 aa 或者 bb 就是不动点
    2. 如果 g(a)≠ag(a)\neq a 且 g(b)≠bg(b)\neq b，那么必有 g(a)>ag(a)>a 和 g(b)<bg(b)<b。考虑 h(x)=g(x)−xh(x)=g(x)-x，由连续函数的介值定理，∃ c∈(a,b)\exists\: c\in (a, b) 使得 h(c)=g(c)−c=0h(c)=g(c)-c=0。

  2. 设 gg 在 [a,b][a, b] 上有两个不动点 p1p_1 和 p2p_2，那么 g(p1)=p1g(p_1)=p_1 和 g(p2)=p2g(p_2)=p_2，于是

    ∣p1−p2∣=∣g(p1)−g(p2)∣=∣g′(ξ)∣⋅∣p1−p2∣⩽k∣p1−p2∣ |p_1-p_2|=|g(p_1)-g(p_2)|=|g'(\xi)|\cdot|p_1-p_2|\leqslant k|p_1-p_2|

    其中第二个等号使用了 Lagrange 中值定理，有 ξ∈(p1,p2)⊂[a,b]\xi\in (p_1, p_2)\subset [a, b]。由于 k∈(0,1)k\in (0, 1)，所以 ∣p1−p2∣=0|p_1-p_2|=0，即得 p1=p2p_1=p_2。

在不动点定理的假设下，可以得到用 pnp_n 近似 pp 的误差估计：

Error Estimate for Fixed-Point Iteration

用 pnp_n 近似 pp 的绝对误差满足

∣pn−p∣⩽kn1−k∣p1−p0∣ |p_n-p|\leqslant\frac{k^n}{1-k}|p_1-p_0|

以及

∣pn−p∣⩽knmax⁡{p0−a,b−p0} |p_n-p|\leqslant k^n\max \{p_0-a, b-p_0\}

Newton's Method

又称 Newton-Raphson Method，实质是二阶泰勒展开舍去二阶及以上高阶项。

0=f(p)=f(p0)+f′(p0)(p−p0)+f′′(ξ)2(p−p0)2≈f(p0)+f′(p0)(p−p0) 0=f(p)=f(p_0)+f'(p_0)(p-p_0)+\frac{f''(\xi)}{2}(p-p_0)^2\approx f(p_0)+f'(p_0)(p-p_0)

由此有

p≈p0−f(p0)f′(p0) p\approx p_0-\frac{f(p_0)}{f'(p_0)}

将这样计算的 pp 记为 p1p_1，然后根据此式子迭代。由此发现，Newton's Method 也是泛函迭代 pn=g(pn−1)p_n=g(p_{n-1}) 的一种，其迭代函数为

g(x)=x−f(x)f′(x) g(x)=x-\frac{f(x)}{f'(x)}

原始的 Newton's Method 有如下注意点：

  • 有某个 nn 使得 f′(pn−1)=0f'(p_{n-1})=0，此时迭代无法继续
  • 在 pp 附近 f′f' 有界且远离 0，那么 Newton's Method 效率较高
  • 收敛性受初始值选择影响比较大，这在后面的分析中可以看出

Convergence

Convergence of Newton's Method

设 f∈C2[a,b]f\in C^2[a, b]，根 pp 满足 f(p)=0f(p)=0 且 f′(p)≠0f'(p)\neq 0（单根），则 ∃ δ>0\exists\: \delta>0 使得 p0∈(p−δ,p+δ)p_0\in (p-\delta, p+\delta) 时，Newton's Method 产生的序列 {pn}\{p_n\} 收敛到 pp。

Proof

根据泛函迭代格式，Newton's Method 有

g(x)=x−f(x)f′(x) g(x) = x-\frac{f(x)}{f'(x)}

希望应用不动点定理，所以要验证满足其条件。

  1. gg 良定义：f∈C2[a,b]f\in C^2[a, b]，所以 f′∈C[a,b]f'\in C[a, b]，根据极限的保号性，f′(p)≠0f'(p)\neq 0 保证了存在 δ0>0\delta_0>0 使得在 [p−δ0,p+δ0][p-\delta_0, p+\delta_0] 中都有 f′(x)≠0f'(x)\neq 0，所以在 [p−δ0,p+δ0][p-\delta_0, p+\delta_0] 上 gg 是良定义的
  2. g∈C1[p−δ0,p+δ0]g\in C^1[p-\delta_0, p+\delta_0]：g′(x)=f(x)f′′(x)[f′(x)]2g'(x)=\dfrac{f(x)f''(x)}{[f'(x)]^2}，结合 f∈C2[a,b]f\in C^2[a, b] 可得

    包含了 g∈C[p−δ0,p+δ0]g\in C[p-\delta_0, p+\delta_0] 和 x∈[p−δ0,p+δ0]x\in [p-\delta_0, p+\delta_0], ∃ g′(x)\exists\: g'(x) 两层条件

  3. ∃ k∈(0,1)\exists\: k\in (0, 1), ∀ x∈(a,b)\forall\: x\in (a, b) there is ∣g′(x)∣⩽k|g'(x)|\leqslant k：可知 g′(p)=0g'(p)=0，由于 g∈C1[p−δ0,p+δ0]g\in C^1[p-\delta_0, p+\delta_0]，所以 ∃ δ>0\exists\: \delta>0 使得在 [p−δ,p+δ][p-\delta, p+\delta] 上都有 ∣g′(x)∣⩽k|g'(x)|\leqslant k，其中可以任取 k∈(0,1)k\in (0, 1)
  4. g([p−δ,p+δ])⊆[p−δ,p+δ]g([p-\delta, p+\delta])\subseteq [p-\delta, p+\delta]：∀x∈[p−δ,p+δ]\forall x\in [p-\delta, p+\delta]
∣g(x)−p∣=∣g(x)−g(p)∣=∣g′(ξ)∣∣x−p∣⩽k∣x−p∣⩽kδ<δ |g(x)-p|=|g(x)-g(p)|=|g'(\xi)||x-p|\leqslant k|x-p|\leqslant k\delta<\delta

综上，应用不动点定理则得证。

Improvement

优化牛顿法（用于 Lab2）：用 μ(x)=f(x)f′(x)\mu(x)=\dfrac{f(x)}{f'(x)} 替换原来的 f(x)f(x)，即公式变成

pn=pn−1−μ(x)μ′(x)=pn−1−f(pn−1)f′(pn−1)[f′(pn−1)]2−f(pn−1)f′′(pn−1) p_{n}=p_{n-1}-\frac{\mu(x)}{\mu'(x)}=p_{n-1}-\frac{f(p_{n-1})f'(p_{n-1})}{[f'(p_{n-1})]^2-f(p_{n-1})f''(p_{n-1})}

优化牛顿法相比牛顿法

  • pros: 计算重根速度更快（二阶收敛）
  • cons：
    • 需要额外计算二阶导
    • 分母 (denominator) 的两项可能相近导致舍入误差大

分子 (numerator)

割线法 (Secant Method)：使用割线斜率替代严格的导数，避免较难的导数计算，但是收敛速度比 Newton's Method 慢

具体而言，迭代公式为

pn=pn−1−f(pn−1)(pn−1−pn−2)f(pn−1)−f(pn−2) p_n=p_{n-1}-\frac{f(p_{n-1})(p_{n-1}-p_{n-2})}{f(p_{n-1})-f(p_{n-2})}

实际执行中，可以描述为前两个点的直线和 xx 轴的交点作为新的点。这是因为前两个点决定的直线为

y=f(pn−1)+f(pn−1)−f(pn−2)pn−1−pn−2(x−pn−1) y = f(p_{n-1}) + \frac{f(p_{n-1})-f(p_{n-2})}{p_{n-1}-p_{n-2}}(x-p_{n-1})

令 y=0y=0，求解的 xx 刚好就是迭代公式中的 pnp_n。

试位法 (The Method of False Position)：书上还介绍了这种方法，但不是通常推荐的方法。它的思想是像二分一样，保证这次迭代点和上次迭代点中间有根，因此多了符号检查的步骤，计算量通常比割线法更大。

Error Analysis for Iterative Methods

Rate of Convergence

考虑收敛到 pp 的数列 {pn}\{p_n\}，如果存在常数 α>0,λ>0\alpha>0, \lambda>0 使得

lim⁡n→∞∣pn+1−p∣∣pn−p∣α=λ \lim_{n\to\infty}\frac{|p_{n+1}-p|}{|p_n-p|^\alpha}=\lambda

那么称 {pn}\{p_n\} 以 α\alpha 阶收敛到  p\:p (converge to  p\:p of order  α\:\alpha)，且 λ\lambda 称为渐进误差常数 (asymptotic error constant)。

特别地，

  • α=1\alpha=1，则称 {pn}\{p_n\} 线性收敛到  p\:p (linearly convergent)
  • α=2\alpha=2，则称 {pn}\{p_n\} 二次收敛到  p\:p (quadratically convergent)

Calculation of Order of Convergence

设 pp 为 g(x)g(x) 的不动点，若

  • 存在常数 α⩾2\alpha\geqslant 2 使得 g∈Cα[p−δ,p+δ]g\in C^\alpha[p-\delta, p+\delta]
  • g′(p)=g′′(p)=⋯=g(α−1)(p)=0g'(p)=g''(p)=\cdots=g^{(\alpha-1)}(p)=0
  • g(α)(p)≠0g^{(\alpha)}(p)\neq 0

那么不动点迭代生成的 {pn}\{p_n\} 以 α\alpha 阶收敛到 pp。

Proof
pn+1=g(pn)=g(p)+g′(p)(pn−p)+g′′(p)2!(pn−p)2+⋯+g(α)(ξn)α!(pn−p)α=p+g(α)(ξn)α!(pn−p)α=n→∞p+λ(pn−p)α \begin{aligned} p_{n+1}=g(p_n) &=g(p)+g'(p)(p_n-p)+\frac{g''(p)}{2!}(p_n-p)^2+\cdots+\frac{g^{(\alpha)}(\xi_n)}{\alpha!}(p_n-p)^\alpha\\ &=p+\frac{g^{(\alpha)}(\xi_n)}{\alpha!}(p_n-p)^\alpha\\ &\xlongequal{n\to \infty}p+\lambda(p_n-p)^\alpha \end{aligned}

其中 λ=g(α)(p)α!\lambda=\dfrac{g^{(\alpha)}(p)}{\alpha !} 是渐进误差常数，这是因为不动点定理保证了收敛，而 ξn\xi_n 取于 pp 和 pnp_n 之间，所以 ξn→p\xi_n\to p。

通过这个定理，可以导出书上的两个定理

  • g′(p)≠0g'(p)\neq 0，则线性收敛
  • g′(p)=0g'(p)=0，则二次收敛（因此牛顿法对于单根二次收敛）

Zero of Multiplicity mm

对于 f(x)f(x) 的 mm 重零点 (zero of multiplicity  m\:m)  p\:p (m⩾2m\geqslant 2)，x≠px\neq p 时有

f(x)=(x−p)mq(x) f(x)=(x-p)^mq(x)

其中 lim⁡x→pf(p)≠0\lim\limits_{x\to p}f(p)\neq 0。对于 Newton's Method，二次收敛降为线性收敛，因为

g′(x)=1−[(x−p)q(x)mq(x)+(x−p)q′(x)]′=1−mq2(x)+(x−p)2[q′(x)]2−(x−p)2q(x)q′′(x)[mq(x)+(x−p)q′(x)]2g′(p)=1−1m≠0 \begin{aligned} g'(x)&=1-\left[\frac{(x-p)q(x)}{mq(x)+(x-p)q'(x)}\right]'=1-\frac{mq^2(x)+(x-p)^2[q'(x)]^2-(x-p)^2q(x)q''(x)}{[mq(x)+(x-p)q'(x)]^2}\\ g'(p)&=1-\frac{1}{m}\neq 0 \end{aligned}

仍希望二次收敛，则应用上一节提到的优化牛顿法，使用 g(x)=f(x)f′(x)g(x)=\dfrac{f(x)}{f'(x)} 替换 f(x)f(x)，这样 ff 的重根 (simple root) 就成为了 μ\mu 的单根。

Accelerating Convergence

Aitken's Δ2\Delta^2 Method

Aitken's Δ2\Delta^2 Method 是一种加速收敛的方法，其思想是用前两个点连线与 y=xy=x 的交点替代第三个点。迭代的前两个点坐标为

(p0,g(p0))=(p0,p1),(p1,g(p1))=(p1,p2) (p_0, g(p_0)) = (p_0, p_1), \quad (p_1, g(p_1)) = (p_1, p_2)

这样就能得到两点连线方程

y=g(p0)+g(p1)−g(p0)p1−p0(x−p0)=p1+p2−p1p1−p0(x−p0) y = g(p_0) + \frac{g(p_1)-g(p_0)}{p_1-p_0}(x-p_0) = p_1 + \frac{p_2-p_1}{p_1-p_0}(x-p_0)

令 y=x=p^y=x=\hat{p}，解得

p^=p0−(p1−p0)2p2−2p1+p0 \hat{p} = p_0 - \frac{(p_1-p_0)^2}{p_2-2p_1+p_0}

Aitken's Δ2\Delta^2 Method 定义数列

p^n=pn−(pn+1−pn)2pn+2−2pn+1+pn \hat{p}_n = p_n - \frac{(p_{n+1}-p_n)^2}{p_{n+2}-2p_{n+1}+p_n}

并认为 {p^n}\{\hat{p}_n\} 比 {pn}\{p_n\} 更快收敛到 pp。

Forward Difference

对数列 {pn}\{p_n\} 定义前向差分 (forward difference) Δpn\Delta p_n：

Δpn=pn+1−pn \Delta p_n = p_{n+1}-p_n

其高次幂可以递归定义为

Δkpn=Δ(Δk−1pn),k⩾2 \Delta^k p_n = \Delta(\Delta^{k-1}p_n),\quad k\geqslant 2

有了前向差分记号，就可以把 Aitken's Δ2\Delta^2 Method 的公式写成

p^n=pn−(Δpn)2Δ2pn \hat{p}_n = p_n - \frac{(\Delta p_n)^2}{\Delta^2 p_n}

根据以下定理可以定量证明 Aitken's Δ2\Delta^2 Method 的加速效果：

Acceleration of Aitken's Δ2\Delta^2 Method

设 {pn}\{p_n\} 线性收敛到 pp，并满足

lim⁡n→∞pn+1−ppn−p<1 \lim_{n\to\infty}\frac{p_{n+1}-p}{p_n-p}<1

则有

lim⁡n→∞p^n−ppn−p=0 \lim_{n\to\infty}\frac{\hat{p}_n - p}{p_n - p}=0

留作习题证明略

Steffensen's Method

与直接应用 Aitken's Δ2\Delta^2 Method 于不动点迭代不同，Steffensen's Method 是将 Aitken's Δ2\Delta^2 Method 修正原始不动点迭代。通过这种修正，可以将线性收敛的不动点迭代加速为二次收敛。

简单地说，就是

p1←g(p0)p2←g(p1)p←p0−(p1−p0)2p2−2p1+p0p0←p \begin{aligned} p_1&\gets g(p_0)\\ p_2&\gets g(p_1)\\ p&\gets p_0 - \frac{(p_1-p_0)^2}{p_2-2p_1+p_0}\\ p_0&\gets p \end{aligned}

持续以上的循环。

Acceleration of Steffensen's Method

设 pp 为 g(x)g(x) 的不动点，满足 g′(p)≠1g'(p)\neq 1。若存在 δ>0\delta>0 使得 g∈C3[p−δ,p+δ]g\in C^3[p-\delta, p+\delta]，则 Steffensen's Method 对 ∀ p0∈[p−δ,p+δ]\forall\: p_0\in [p-\delta, p+\delta] 二次收敛到 pp。

留作习题证明略

Comments