非线性方程的数值解

二分法

求解 $f(x)=0$，首先取一段区间 $[a,b]$，若 $f(a)f(b)\le0$，说明 $[a,b]$ 区间上存在零点。通过不断地把函数零点所在的区间一分为二，使区间的两个端点逐步逼近零点，进而得到零点近似值。

假设 $a_0=a$，$b_0=b$，第 $k$ 步迭代的零点区间为 $[a_k,b_k]$，近似解为 $x_k=\frac{a_k+b_k}{2}$，精确解为 $x^\ast\in[a_k,b_k]$。则 $|x_k-x^\ast|=\left|\frac{a_k+b_k}{2}-x^\ast\right|\le\frac{b_k-a_k}{2}=\frac{b_{k-1}-a_{k-1}}{2^2}=\cdots=\frac{b_0-a_0}{2^{k+1}}=\frac{b-a}{2^{k+1}}$，对于给定的精度 $\varepsilon$，可估计二分法所需的步数 $\frac{b-a}{2^{k+1}}\le\varepsilon$，即 $k\ge\log_2\frac{b-a}{\varepsilon}-1$，取 $k=\left\lceil\log_2\frac{b-a}{\varepsilon}\right\rceil-1$。

这里并不打算花费过多笔墨介绍二分法，二分法原理简单，其用途不仅仅于求解非线性方程；二分法在算法竞赛中也有广泛的应用，许多具有单调性的讨论都可用二分法解决。

试值法

由于二分法收敛速度相对较慢，因此试值法对他进行了改进。

若在区间 $[a,b]$ 上有 $f(a)f(b)<0$，则考虑经过 $(a,f(a))$ 和 $(b,f(b))$ 的割线与 $x$ 轴的交点 $(c,0)$ 为更好的近似值。割线方程为 $y-f(b)=\frac{f(b)-f(a)}{b-a}(x-b)$，令 $y=0$ 得 $c=b-\frac{f(b)(b-a)}{f(b)-f(a)}$。

若 $f(a)f(c)<0$，则在 $[a,c]$ 内有一个零点；若 $f(b)f(c)<0$，则 $[c,b]$ 内有一个零点。

不动点迭代

对于非线性方程 $f(x)=0$，将其等价变换为 $x=g(x)$，$g$ 的不动点 $x^\ast$ 就是 $f(x)=0$ 的解。从一个初始值 $x_0$ 出发，令 $x_{k+1}=g(x_k)$，不断迭代；若 $\{x_k\}$ 收敛，即存在 $x^\ast$ 使得 $\lim\limits_{k\to\infty}x_k=x^\ast$；根据迭代数列的产生方式， $\lim\limits_{k\to\infty}x_{k+1}=\lim\limits_{k\to\infty}g(x_k)$，可知 $x^\ast=g(x^\ast)$，$x^\ast$ 就是 $g$ 的不动点。

不动点存在性

设 $g\in C[a,b]$。如果对于所有 $x\in[a,b]$，映射 $y=g(x)$ 的范围满足 $y\in[a,b]$，则函数 $g$ 在 $[a,b]$ 内有一个不动点；此外，设 $g'(x)$ 定义在 $(a,b)$ 内，且对于所有 $x\in(a,b)$，存在常数 $0\le K<1$，使得 $|g'(x)|\le K<1$，则函数 $g$ 在 $[a,b]$ 内有唯一的不动点。

证明 取 $f(x)=g(x)-x$，故 $f(a)=g(a)-a\ge0$，$f(b)=g(b)-b\le0$，所以 $[a,b]$ 上存在 $f$ 的零点，即 $[a,b]$ 上存在 $g$ 的不动点。假设在 $[a,b]$ 上有两个不动点 $P_1,P_2$，根据中值定理，存在 $\xi\in(a,b)$，$g'(\xi)=\frac{g(P_1)-g(P_2)}{P_1-P_2}=1$，这与 $|g'(x)|<1$ 矛盾，故存在唯一不动点。

收敛阶

不动点迭代中，若迭代数列收敛，且对于真实值 $x^\ast$ 有 $g(x^\ast)\neq 0$。则 $e_{k+1}=x_{k+1}-x^\ast=g(x_k)-g(x^\ast)$，由中值定理，存在 $\xi\in(\min(x_k,x^\ast),\max(x_k,x^\ast))$ 使得$g'(\xi)=\frac{g(x_k)-g(x^\ast)}{x_k-x^\ast}$，故 $e_{k+1}=g'(\xi)\cdot e_k$。于是 $\lim\limits_{k\to\infty}|\frac{e_{k+1}}{e_k}|=g'(x^\ast)\neq 0$，不动点迭代是线性收敛的。