6. 非线性方程

6.1 对分法

6.1.1 对分法基本思想

定理 6.1

设 $f(x)$ 在 $[a, b]$ 内连续, 且 $f(a) f(b) < 0$, 则在 $(a, b)$ 内至少存在一点 $\xi$, 使得 $f(\xi) = 0$.

算法 6.1

1. 给定函数 $f(x)$ 和求解区间 $[a, b]$, 以及精度要求 $\xi > 0$
2. 令 $a_1 = a$, $b_1 = b$
3. 计算 $f(a_1)$ 和 $f(b_1)$, 如果 $\abs{f(a_1)} < \xi$, 则返回数值解 $x = a1$ 并停止计算; 如果 $\abs{f(b_1)} < \xi$, 则返回数值解 $x = b_1$ 并停止计算; 如果 $f(a1) f(b1) > 0$, 则输出算法失败信息并停止计算
4. for $k = 1, 2, \dots,$ do
5. 计算 $x_k = \frac{a_k + b_k}{2}$ 和 $f(x_k)$
6. 如果 $\abs{f(x_k)} < \xi$ 或者 $\abs{b_k - a_k} < \xi$, 则返回数值解 $x_k$ 并停止计算;
7. 如果 $f(a_k) f(x_k) < 0$, 则令 $a_{k + 1} = a_k$, $b_k = x_k$; 否则令 $a_{k + 1} = x_k$, $b_{k + 1} = b$;
8. end for

关于对分法的几点注记

• 适用范围: 只适合求连续函数的 单重实根 或 奇数重实根;
• 优点: 简单易用, 只要满足介值定理的条件, 算法总是收敛的;
• 缺点:
  1. 收敛速度较缓慢;
  2. 不能求复根和偶数重根;
  3. 一次只能求一个根;
• 总结: 一般可先用来计算解的一个粗糙估计, 然后再用其他方法进行加速, 如 Newton 法.

6.2 不动点迭代法

6.2.1 收敛性分析

定理 6.3 不动点的唯一存在性

设 $\varphi(x) \in C[a, b]$ 且满足

1. 对任意 $x \in [a, b]$, 都有 $\varphi(x) \in [a, b]$,

2. 存在常数 $L$, 满足 $0 < L < 1$, 使得对任意 $x, y \in [a, b]$ 都有

   $$\abs{\varphi(x) - \varphi(y)} \leqslant L \abs{x - y},$$

则 $\varphi(x)$ 在 $[a, b]$ 上存在唯一的不动点.

定理 6.4 不动点迭代的全局收敛性

设 $\varphi(x) \in C[a, b]$ 且满足

1. 对任意 $x \in [a, b]$, 都有 $\varphi(x) \in [a, b]$,

2. 存在常数 $L$, 满足 $0 < L < 1$, 使得对任意 $x, y \in [a, b]$ 都有

   $$\abs{\varphi(x) - \varphi(y)} \leqslant L \abs{x - y}$$

则对任意初始值 $x_0 \in [a, b]$, 不动点迭代收敛, 且

$$\abs{x_k - x_*} \leqslant \frac{L}{1 - L} \abs{x_k - x_{k - 1}} \leqslant \frac{L^k}{1 - L} \abs{x_1 - x_0},$$

其中 $x_*$ 是 $\varphi(x)$ 是 $[a, b]$ 内存在唯一的不动点.

推论 6.5

设 $\varphi(x) \in \mathcal{C}^1[a, b]$ 且对任意 $x \in [a, b]$, 都有 $\varphi(x) \in [a, b]$. 如果存在常数 $L$, 使得

$$\abs{\varphi'(x)} \leqslant L < 1 \qc \forall x \in [a, b]$$

则对任意初始值 $x_0 \in [a, b]$, 不动点迭代收敛, 且

$$\abs{x_k - x_*} \leqslant \frac{L}{1 - L} \abs{x_k - x_{k - 1}} \leqslant \frac{L^k}{1 - L} \pqty{x_1 - x_0}.$$

定理 6.6

设 $x_*$ 是 $\varphi(x)$ 的不动点, 若 $\varphi'(x)$ 在 $x_*$ 的某个邻域内连续且

$$\abs{\varphi'(x_*)} < 1,$$

则不动点迭代局部收敛.

6.2.2 收敛阶