第一章 非线性方程的解法
1.1非线性方程根的概念
$$f(x)=0$$
若$f(x)$是n次多项式，则称上式为n次多项式方程 ；若$f(x)$是超越函数（包括对数、指数、三角函数），则称上式为超越方程。一般我们只需得到有一定精度要求的根的近似值就可以了。
对上述方程求根分为三个步骤：
- 根的存在性 ：方程是否有根以及根的个数
- 根的隔离 ：把有根区间分为较小的子区间，每个子区间有一个或者没有根。这样可以将有根子区间内的任一点都可以看成是该根的一个近似值。
- 根的精确化 ：对根的某个近似值逐步精确化，使满足精度要求。
1.2非线性方程求根的数值方法
1.2.1二分法
若函数$f(x)$在$[a,b]$上连续，且$f(a)f(b)<0$，根据连续函数根的存在性定理 ，方程$f(x)$在$(a,b)$ 上一定有实根，称该区间为有根区间，设$(a,b)$内只有一个根$\alpha$
计算过程及分析：
取区间$[a,b]$中点$x_0=\frac{a+b}{2}$ ，并计算中点的函数值$f(x_0)$ ，判断若$f(a)f(x_0)>0$ ，新的有根区间为$[a_1, b_1]=[a, x_0]$ ；若$f(a)f(x_0)=0$，则$x_0$即为所求的根；若$f(a)f(x_0)<0$，则新的有根区间为$[a_1, b_1]=[x_0, b]$ 。此过程一直进行下去。
$[a_n, b_n]$的区间长度为$$b_n-a_n=\frac{b_{n-1}-a_{n-1}}{2}=…=\frac{b-a}{2^n}$$
取最后一个区间的中点$x_n$作为方程根的近似值$$x_n=\frac{a_n+b_n}{2}$$
对给定的小数$\epsilon>0$ ，要使误差估计式$$|a-x_n|=\frac{b_n-a_n}{2^{n+1}}<\epsilon$$
得到$$n=[\frac{ln(b-a)-ln\epsilon}{ln2}]$$
二分法的优缺点：
- 优点：计算过程简单；收敛性可保证；对函数的性质要求低，只要求连续
- 缺点：收敛速度慢；不能求偶数重根、复根和虚根；对计算的函数值只利用了符号，是一种浪费
1.2.2迭代法
通过构造一个递推关系式（迭代格式）计算出根的近似值序列，并要求该序列收敛于方程的根。
将方程$f(x)=0$化为等价方程$x=\phi(x_i), i=0,1,2,…$产生序列${x_i}$。如果该序列收敛于$\alpha$，则$\alpha$一定满足上述等价方程，为方程的根。
示例：
$f(x)=xe^x-1=0$ 改写为$x=e^{-x}$ ，构造迭代格式为$x_{i+1}=e^{-x_i}$
- 单点迭代法 ：仅需一个初始值$x_0$
- 多点迭代法：一般形式为$x_{i+1}=\phi_i(x_i,x_{i-1},…,x_{i-n+1}), i=0,1,2,…$
- 非定常迭代 ：迭代函数$\phi_i$ 随迭代次数$i$变化
- 定常迭代：$\phi_i=\phi$不随迭代次数变化
迭代法考虑的主要问题
收敛性
- 全局收敛性 ：设$\alpha$为$f(x)=0$的根，如果$\forall x_0\in[a,b]$，由迭代法产生的序列都收敛于根$\alpha$
- 局部收敛性 ：设方程$x=\phi(x)$有根$\alpha$，如果存在$\alpha$的某个邻域$\bigtriangleup:|x-\alpha|\leq\delta$，对任意初值$x_0\in\bigtriangleup$，迭代过程所产生的序列均收敛于根$\alpha$
收敛速度
设迭代过程产生的序列收敛于方程的根$\alpha$，记$e_k=\alpha-x_k$，若$$\lim_{k\to\infty}\frac{|e_{k+1}|}{|e_k|^p}=C\neq0$$，则称迭代过程是p阶收敛的 。特别的，当$p=1$时，成为线性收敛；当$p>1$时，称为超线性收敛 ；当$p=2$时，称为平方收敛 。$p$越大，收敛越快。
计算效率
效率指数 ：$EI=p^{\frac{1}{\theta}}$ 其中，$p$表示迭代的收敛阶，$\theta$表示每步迭代的计算量。$EI$越大，计算效率越高。
不动点迭代法（单点迭代法）
迭代公式是否收敛，与迭代函数$\phi(x)$的形式有关。例子：
求方程$9x^2-\sin x-1=0$ 在$[0,1]$内的根，可将该方程化为等价方程$x=\frac{1}{3}\sqrt{\sin x+1}$，于是迭代函数为$\phi (x)=\frac{1}{3}\sqrt{\sin x+1}$ ，在区间内任取一个初始值$x_0$，如0.4，迭代可收敛于根$\alpha=0.391846907$ 。然而当原方程写为$x=arcsin(9x^2-1)$ 时，迭代却是发散的。
定理1.1（不动点迭代法的整体收敛性） 设$\phi(x)$在$[a,b]$上具有一阶导数，且
(1)当$x\in[a,b]$ 时，$\phi (x)\in [a,b]$
(2)$\forall x \in [a,b]$ ，有$|\phi’(x)|\leq L<1$
则对任意初值$x_0\in[a,b]$，迭代过程$x_{k+1}=\phi (x_k)$ 收敛于$x=\phi(x)$ 在$[a,b]$上的唯一根
定理1.2（不动点迭代法的整体收敛性） 设$\phi(x)$满足
(1)当$x\in[a,b]$时，$\phi(x)\in[a,b]$
(2)$\forall x_1,x_2\in[a,b]$有：$\phi(x_1)-\phi(x_2)\leq L|x_1-x_2|, L<1$
则对任意初值$x_0\in[a,b]$，迭代过程$x_{k+1}=\phi(x_k)$ 收敛于$x=\phi(x)$ 在$[a,b]$上的唯一根，且有误差估计式
$$\begin{cases}|\alpha-x_k|\leq \frac{L}{1-L}|x_k-x_{k-1}|\|\alpha-x_k|\leq \frac{L}{1-L}|x_1-x_0|\end{cases} $$
例1：求方程$xe^x-1=0$ 在$[\frac{1}{2}, ln2]$中的根
解：改写方程为$x=e^{-x}$，构造迭代格式$x_{i+1}=e^{-x_i}$ ，迭代函数为$\phi(x)=e^{-x}$ 。$\because \phi’(x)=-e^{-x}<0 \therefore \phi(x)$是单调下降函数，得$\phi(x)\in[\frac{1}{2},ln2]$ ，而$|\phi’(x)|=|-e^{-x}|\leq e^{-\frac{1}{2}}<1$ ，根据定理1.1，方程在区间$[\frac{1}{2}, ln2]$上存在唯一的根切迭代收敛。取初值为$x_0=0.5$ ，迭代计算结果为$x_0=0.50000,x_1=0.606531,x_2=0.545239,…,x_23=0.567143$
定理1.3（不动点迭代法的局部收敛性） 若$\phi(x)$在方程$x=\phi(x)$的根$\alpha$的邻域内有一阶连续的导数，且$|\phi’(\alpha)|<1$ ，则迭代过程$x_{k+1}=\phi(x_k)$具有局部收敛性。
定理1.4（不动点迭代法的局部收敛阶） 若$\phi(x)$ 在方程$x=\phi(x)$的根 $\alpha$ 的邻域内有充分阶连续的导数，则迭代过程$x_{k+1}=\phi(x_k)$在$\alpha$邻域是$p$阶收敛的充分必要条件是$$\phi^{(j)}(\alpha)=0, j=1,2,,…,p-1 \ \phi^{(p)}(\alpha)\neq 0$$
例2：能否用迭代法求解方程$x=4-2^x$ ，若不能，将方程改写为能用迭代法求解的形式
解：方程为$x-4+2^x=0$ ，设$f(x)=x-4+2^x$ ,则$f(1)<0, f(2)>0, f’(x)=1+2^xln2>0$，所以方程$f(x)=0$在区间$(1,2)$内有唯一根。题目中$\phi(x)=4-2^x$，当$x\in[1,2]$时，$|\phi’(x)|=|-2^xln2|\geq2ln2>1$，根据定理1.3，不能用来迭代求根。
把原方程改写为$x=ln(4-x)/ln2$ ，此时$\phi(x)=ln(4-x)/ln2$ ，则有当$x\in[1,2]$时，$\phi(x)\in[1,ln3/ln2]\subset[1,2]$ 且$\forall x\in[1,2]$ ,有$|\phi’(x)|=|\frac{-1}{4-x}\cdot\frac{1}{ln2}|\leq\frac{1}{4-2}\cdot\frac{1}{ln2}=\frac{1}{2ln2}<1$ ，由定理1.3知可用迭代公式$x_{k+1}=ln(4-x_k)/ln2$ 来求解
Newton迭代法
设有方程$f(x)=0$，在其根$\alpha$附近任取一点$x_0$作为初始近似根，由迭代公式$$x_{k+1}=x_k-\frac{f(x_k)}{f’(x_k)} (k=0,1,2,…)$$ 逐次逼近方程的根，又称切线法
定理1.5（Newton迭代法的全局收敛性） 设$f(x)$在有根区间$[a,b]$上二阶导数存在，且满足:
(1)$f(a)f(b)<0$ （保证根的存在）
(2)$f’(x)\neq0, x\in[a,b]$ （单调，根唯一）
(3)$f’’(x)$不变号，$x\in[a,b]$ （凹凸性不变）
(4)初值$x_0\in[a,b]$且使$f’’(x_0)f(x_0)>0$ （保证$x\in[a,b]$时，$\phi(x)=x-\frac{f(x)}{f’(x)}\in[a,b]$ ）
则Newton迭代法收敛于$f(x)=0$在$[a,b]$内的唯一根f