Skip to content

Solutions of Equations in One Variable

本章致力于求解

\[ f(x)=0 \]

其中 \(x\) 是一元标量。

The Bisection Method

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

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

\[ |p_n-p|\leqslant\frac{b-a}{2^n}, \quad n\geqslant 1 \]

分析其优缺点：

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

Fixed-Point Iteration

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

\[ f(x)=0\iff g(x):=f(x)+x=x \]

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

Fixed Point

给定函数 \(g\)，当 \(p\) 满足

\[ p=g(p) \]

则称 \(p\) 为 \(g\) 的不动点 (Fixed Point) 。

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

\[ 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) \]

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

Fixed-Point Theorem

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

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

那么 \(\forall\: p_0\in [a, b]\)，数列 \(\{p_n\}\) 收敛到 \([a, b]\) 上唯一的不动点 \(p\)。

Proof

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

\[ |p_n - p| = |g(p_{n-1})-g(p)| = |g'(\xi)||p_{n-1}-p| \leqslant k|p_{n-1}-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\in (0, 1)\)，所以 \(\lim\limits_{n\to\infty}k^n=0\)，于是 \(\lim\limits_{n\to\infty}|p_n-p|=0\)，即得 \(\lim\limits_{n\to\infty}p_n=p\)。

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

Existence and Uniqueness of Fixed Point

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

  2. 设 \(g\) 在 \([a, b]\) 上有两个不动点 \(p_1\) 和 \(p_2\)，那么 \(g(p_1)=p_1\) 和 \(g(p_2)=p_2\)，于是

    \[ |p_1-p_2|=|g(p_1)-g(p_2)|=|g'(\xi)|\cdot|p_1-p_2|\leqslant k|p_1-p_2| \]

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

在不动点定理的假设下，可以得到用 \(p_n\) 近似 \(p\) 的误差估计：

Error Estimate for Fixed-Point Iteration

用 \(p_n\) 近似 \(p\) 的绝对误差满足

\[ |p_n-p|\leqslant\frac{k^n}{1-k}|p_1-p_0| \]

以及

\[ |p_n-p|\leqslant k^n\max \{p_0-a, b-p_0\} \]

Newton's Method

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

\[ 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\approx p_0-\frac{f(p_0)}{f'(p_0)} \]

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

\[ g(x)=x-\frac{f(x)}{f'(x)} \]

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

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

Convergence

Convergence of Newton's Method

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

Proof

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

\[ g(x) = x-\frac{f(x)}{f'(x)} \]

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

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

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

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

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

Improvement

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

\[ 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 慢

具体而言，迭代公式为

\[ p_n=p_{n-1}-\frac{f(p_{n-1})(p_{n-1}-p_{n-2})}{f(p_{n-1})-f(p_{n-2})} \]

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

\[ 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=0\)，求解的 \(x\) 刚好就是迭代公式中的 \(p_n\)。

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

Error Analysis for Iterative Methods

Rate of Convergence

考虑收敛到 \(p\) 的数列 \(\{p_n\}\)，如果存在常数 \(\alpha>0, \lambda>0\) 使得

\[ \lim_{n\to\infty}\frac{|p_{n+1}-p|}{|p_n-p|^\alpha}=\lambda \]

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

特别地，

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

Calculation of Order of Convergence

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

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

那么不动点迭代生成的 \(\{p_n\}\) 以 \(\alpha\) 阶收敛到 \(p\)。

Proof
\[ \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} \]

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

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

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

Zero of Multiplicity \(m\)

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

\[ f(x)=(x-p)^mq(x) \]

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

\[ \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)=\dfrac{f(x)}{f'(x)}\) 替换 \(f(x)\)，这样 \(f\) 的重根 (simple root) 就成为了 \(\mu\) 的单根。

Accelerating Convergence

Aitken's \(\Delta^2\) Method

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

\[ (p_0, g(p_0)) = (p_0, p_1), \quad (p_1, g(p_1)) = (p_1, p_2) \]

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

\[ 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=\hat{p}\)，解得

\[ \hat{p} = p_0 - \frac{(p_1-p_0)^2}{p_2-2p_1+p_0} \]

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

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

并认为 \(\{\hat{p}_n\}\) 比 \(\{p_n\}\) 更快收敛到 \(p\)。

Forward Difference

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

\[ \Delta p_n = p_{n+1}-p_n \]

其高次幂可以递归定义为

\[ \Delta^k p_n = \Delta(\Delta^{k-1}p_n),\quad k\geqslant 2 \]

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

\[ \hat{p}_n = p_n - \frac{(\Delta p_n)^2}{\Delta^2 p_n} \]

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

Acceleration of Aitken's \(\Delta^2\) Method

设 \(\{p_n\}\) 线性收敛到 \(p\)，并满足

\[ \lim_{n\to\infty}\frac{p_{n+1}-p}{p_n-p}<1 \]

则有

\[ \lim_{n\to\infty}\frac{\hat{p}_n - p}{p_n - p}=0 \]

留作习题证明略

Steffensen's Method

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

简单地说，就是

\[ \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

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

留作习题证明略

Comments