基本概念

对于一个非线性方程 $f(x)=0$：

• $\exist\alpha$，使得 $f(\alpha)=0$，就称 $\alpha$ 是 $f(x)=0$ 的根或 $f(x)$ 的零点。
• 设 $\exist m\in\mathbb{Z}_+$，使得 $f(x)=(x-\alpha)^mg(x)$，且 $g(\alpha)\neq0$， 则
  • $m=1$，称 $\alpha$ 为 $f(x)=0$ 的单根；
  • $m>1$，称 $\alpha$ 为 $f(x)=0$ 的 $m$ 重根。
    • 如果 $m$ 是 $f(x)= 0$ 的 $m$ 重根，则 $f(\alpha)=f'(\alpha)=f''(\alpha)=\cdots=f^{(m-1)}(\alpha)=0$，且 $f^{(m)}(\alpha)\neq0$。

二分法

理论来源

零点存在性定理。

计算过程

1. 确定起始的有根区间 $[a_0, b_0]$。即 $f(a_0)\cdot f(b_0)<0$。
2. 计算 $x_0=\frac{b_0-a_0}{2}$。然后判定有根区间是 $[a_0, x_0]$ 还是 $[x_0, b_0]$，记新的有根区间为 $[a_1, b_1]$。
3. 重复上面的过程。容易知道 $[a_n, b_n]$ 区间的长度是 $\frac{b-a}{2^n}$。
4. 当 $\frac{b-a}{2^n}$ 小于给定的长度（误差）时，取这个区间的中点 $x_n=\frac{a_n+b_n}{2}$ 为根的近似值。

误差

$|\alpha-x_n|\leqslant\frac{b_n-a_n}{2}=\frac{b-a}{2^{n+1}}$，当 $n\to\infty$ 时，$x_n\to\alpha$。

若要求误差不超过 $\varepsilon$，即 $\frac{b-a}{2^{n+1}}<\varepsilon$，有 $n\geqslant\lfloor\frac{\ln(b-a)-\ln\varepsilon}{\ln 2}\rfloor$（是取下整！），即可以根据误差要求先行确定计算次数。

单点迭代法 / 不动点迭代法

理论来源

将 $f(x)=0$ 改写成 $x=\phi(x)$，以 $x_{n+1}=\phi(x_i)$ 的形式进行迭代。

如果 $\phi(x)$ 连续，且 $\lim\limits_{k\to\infty}x_k=\alpha$，那么 $\alpha$ 为原方程 $f(x)=0$ 的根，称为函数 $\phi(x)$ 的「不动点」。