6. 非线性方程

liblaf11/8/22About 2 min

6.1 对分法

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

给定函数 $f (x)$ 和求解区间 $[a, b]$ , 以及精度要求 $ξ > 0$
令 $a_{1} = a$ , $b_{1} = b$
计算 $f (a_{1})$ 和 $f (b_{1})$ , 如果 $\abs f (a_{1}) < ξ$ , 则返回数值解 $x = a 1$ 并停止计算; 如果 $\abs f (b_{1}) < ξ$ , 则返回数值解 $x = b_{1}$ 并停止计算; 如果 $f (a 1) f (b 1) > 0$ , 则输出算法失败信息并停止计算
for $k = 1, 2, \dots,$ do
计算 $x_{k} = \frac{a_{k} + b_{k}}{2}$ 和 $f (x_{k})$
如果 $\abs f (x_{k}) < ξ$ 或者 $\abs b_{k} - a_{k} < ξ$ , 则返回数值解 $x_{k}$ 并停止计算;
如果 $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$ ;
end for

关于对分法的几点注记

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

对任意 $x \in [a, b]$ , 都有 $φ (x) \in [a, b]$ ,
存在常数 $L$ , 满足 $0 < L < 1$ , 使得对任意 $x, y \in [a, b]$ 都有 $\abs φ (x) - φ (y) ⩽ 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 收敛阶