第五章非线性方程的求根

对于非线性方程
$f(x)=0$
中的 $f(x)$ 是 $n$ 次多项式 $f(x)=a_0+a_1x+a_2x^2+\cdots+a_nx^n$ 时，称为代数方程；否则称为超越方程，如 $f(x)=xe^x-1=0,f(x)=x\sin x-\frac{1}{2}=0$ 。

对 $n\ge 5$ 的代数方程和超越方程，没有通用的求根公式，一般用数值分析的方法做近似计算。

5.1 二分法

例子
判别方程 $x^3-3x+1=0$ 的实根存在区间，要求区间长度不大于 1，并求出最小正跟的近似值，误差限 $\varepsilon =10^{-3}$ 。

解

由于方程时 3 次代数方程，故其根的个数不超过 3 个。由下表可知根的存在区间为（-2，-1），（0，1），（1，2）。
$\begin{array}{l|c|c|c|c|r}x &-2&-1&0&1&2\\ \hline f(x)&-1&3&1&-1&3\end{array}$

在区间（0，1）内做二分法迭代，求得最小正跟的近似值为 0.347。

二分法的优点是方法和计算简单，对函数的性质要求不高，只需连续即可。缺点是收敛速度慢，不能求偶数重根。实际应用中常用来判别根的存在区间。

5.2 不动点迭代法

不动点与不动点迭代法

设方程 $f(x)=0$ 可以转化为等价的形式 $x=g(x)$ ，从某个初值 $x_0$ 出发，令 $x_{k+1}=g(x_k),k=0,1,2,\cdots$
得到序列 $\{x_k\}$ ，当 $g(x)$ 连续，且序列 $\{x_k\}$ 收敛于 $\alpha$
时，有
$\lim_{k\rightarrow\infty}x_{k+1}=\lim_{k\rightarrow\infty}g(x_k)=g(\lim_{k\rightarrow\infty}x_k)$
即有 $\alpha=g(\alpha)$ ，所以 $\alpha$ 是方程 $f(x)=0$ 的根。

称上述函数 $g(x)$ 为迭代函数，称 $\alpha$ 是它的一个不动点，构造迭代公式的方法称为不动点迭代法。

例子用不动点迭代方法，求方程 $x^3+4x^2-10=0$ 在（1，2）内的近似根。

解设 $f(x)=x^3+4x^2-10$ ， $f(x)$ 在[1,2]上连续，且 $f(1)=-5<0;f(2)=14>0$ ，由零点定理知，方程在（1，2）内至少存在一实根。

采用迭代公式 $x_{k+1}=g(x_k)=x_k-x_k^3-4x_k^2+10$ ，取初始近似值 $x_0=1.5$ ，迭代后计算结果为： $x_4=1.03\times 10^8$ ，不收敛。

采用迭代公式 $x_{k+1}=g(x_k)=x_k-\frac{x_k^3+4x_k^2-10}{3x_k^2+8x_k}$ ，取初始近似值 $x_0=1.5$ ，迭代后计算结果为： $x_3=1.36523001$ ，收敛。

不动点迭代法的收敛性

求解非线性方程根的不动点迭代法常常只具有局部的收敛性，即当初始值 $x_0$ 充分接近于根 $\alpha$ 时，迭代法产生的序列 $\{x_k\}$ 才可能收敛于根 $\alpha$ 。

若存在常数 $L>0$ ，使得 $|g(x_1)-g(x_2)|\le L |x_1-x_2|, \forall x_1,x_2 \in [a,b]$ ，则称函数 $g(x)$ 在 $[a,b]$ 上满足 Lipschitz 条件， L 称为 Lipschitz 常数。

定理
对迭代方程 $x=g(x)$ ，若迭代函数 $g(x)$ 满足
1）当 $x\in [a,b]$ 时，有 $g(x)\in [a,b]$ ；
2） $g(x)$ 在 $[a,b]$ 上满足 Lipschitz 条件，且 $L<1$ 。
则有：
1） $x=g(x)$ 在 $(a,b)$ 内存在唯一的根 $\alpha$ ;

对 $\forall x_0\in [a,b]$ ，迭代公式 $x_{k+1}=g(x_k)$ 均收敛，且 $\lim_{k\rightarrow\infty}x_{k}=\alpha$
$|\alpha-x_k|\le \frac{L^k}{1-L}|x_1-x_0|$
$|\alpha-x_k|\le \frac{L}{1-L}|x_k-x_{k-1}|$

迭代法的收敛速度

收敛速度是衡量迭代方法好坏的重要标志，常用收敛的阶来刻画。

记迭代公式的第 $k$ 次迭代误差为 $\varepsilon _k=\alpha -x_k$ ，并假设迭代公式是收敛的，若存在实数 $p\ge 1$ 使得
$\lim_{k\rightarrow\infty}\frac{|\varepsilon_{k+1}|}{|\varepsilon_k|^p}=C \ne 0$
则称迭代公式是 p 阶收敛的， C 称为渐近误差常数。

若 $p=1,C<1$ ，称迭代公式为线性收敛；若 $p=2$ ，称迭代公式为二阶收敛；若 $1<p<2$ ，或 $p=1,C=0$ ，称迭代公式为超线性收敛。

收敛阶为 p 的意义是迭代结果的误差与迭代前误差的 p 次方是同阶无穷小；高阶方法比低阶方法收敛快很多，同阶方法中渐近误差常数小的收敛较快。

对迭代公式 $x_{k+1}=g(x_k)$ ，若 $g^{(p)}(x)$ 在根 $\alpha$ 的邻域内连续，且
$g'(\alpha)=g''(\alpha)=\cdots=g^{(p-1)})(\alpha)=0$
则迭代公式在根 $\alpha$ 的领域内至少是 p 阶收敛的（p 是正整数）；若还有 $g^{(p)}(\alpha)\ne 0$ ，则迭代公式在根 $\alpha$ 的邻域内是 p 阶收敛的。

5.3 Newton 迭代法

Newton 迭代法的构造思想

将函数 $f(x)$ 在近似值 $x_k$ 处进行一阶泰勒展开，略去高阶无穷小项，故有迭代公式
$x_{k+1}=x_k-\frac{f(x_k)}{f'(x_k)} \quad\quad {f'(x_k)\ne 0}$

Newton 法的几何意义是用点 $(x_k,f(x_k))$ 处的切线与 $x$ 轴交点处的横坐标作为近似值 $x_{k+1}$ 。

Newton 法的收敛速度

Newton 法的迭代函数 $g(x)=x-\frac{f(x)}{f'(x)}$ ，由 $g'(\alpha)=\frac{f(\alpha)f''(\alpha)}{(f'(\alpha))^2}=0\quad\quad (f'(\alpha)\ne 0)$ ，当 $f'(\alpha)\ne0$ 时， Newton 法至少是二阶收敛的。

例子
用 Newton 法求 $x\sin x=0.5$ 在 0.7 附近的根，误差限 $\varepsilon=10^{-7}$ 。

解
$f(x)=x\sin x-0.5, f'(x)=\sin x + x\cos x, x_0=0.7$
$x_{k+1}=x_k-\frac{f(x_k)}{f'(x_k)}=x_k-\frac{x_k\sin x_k-0.5}{\sin x_k+x_k \cos x_k}, k=0,1,2,\cdots$
计算结果如下表：
$\begin{array}{l|c|c|c|c|c} k&0&1&2&3&4\\ x_k&0.7000000&0.7415796&0.7408412&0.7408410&0.7408410 \end{array}$

简化 Newton 法

迭代公式为： $x_{k+1}=x_k-\frac{f(x_k)}{C}$ ，其中 C 为一常数，常取 $C=f'(x_0)$ 。

简化 Newton 法只有线性收敛性。

例子
用简化 Newton 法求 $x\sin x=0.5$ 在 0.7 附近的根，误差限 $\varepsilon=10^{-7}$ 。

解
$f'(x_0) = 1.179607$
$x_{k+1} = x_k-\frac{f(x_k)}{f'(x_0)}=x_k-\frac{x_k\sin x_k-0.5}{1.179607},k=0,1,2,\cdots$
计算结果如下表：
$\begin{array}{l|c|c|c|c|c|c} k&0&1&2&3&4&5&6\\ x_k&0.7000000&0.7415796&0.7408144&0.7408419&0.7408409&0.7408410&0.7408410 \end{array}$

Newton 下山法

迭代公式 $x_{k+1}=x_k-\lambda_k\frac{f(x_k)}{f'(x_k)},k=0,1,2,\cdots$
其中 $0<\lambda_k\le 1$ ，且满足下山条件：
$|f(x_{k+1})|<|f(x_k)|$

称 $\lambda_k$ 为下山因子。下山因子的选取常用逐步搜索法，先取 $\lambda_k=1$ ，判断下山条件是否成立，若不成立则将 $\lambda_k$ 缩小一半，直到下山条件成立为止。

割线法

Newton 迭代法需要求函数的导数，当求导数有困难时，用差商近似代替微商有迭代公式：
$x_{k+1}=x_k-\frac{x_k-x_{k-1}}{f(x_k)-f(x_{x-1})}f(x_k),\quad k=1,2,3,\cdots$

该方法具有超线性收敛性。收敛阶为黄金分割数 0.618。

例子
用割线法求 $x\sin x=0.5$ 在 0.7 附近的根，取 $x_0=0.5,x_1=1$ ，误差限 $\varepsilon=10^{-7}$ 。

解
$x_{k+1}=x_k-\frac{x_k-x_{k-1}}{f(x_k)-f(x_{k-1})}f(x_k),\quad k=1,2,3,\cdots$
计算结果如下表：
$\begin{array}{l|c|c|c|c|c} k&0&1&2&3&4&5\\ x_k&0.5&1.0&0.7162723&0.7389835&0.7408598&0.7408409\\ x_{k+1}&1.0&0.7162723&0.7389835&0.7408598&0.740840&0.7408410 \end{array}$

5.4 Aitken 加速方法与重根迭代法

Aitken 加速方法
重根的迭代

5.5 非线性方程组求根

设有方程组
$\begin{cases} f_1(x_1,x_2,\cdots,x_n)&=0\\ f_2(x_1,x_2,\cdots,x_n)&=0\\ \cdots\cdots\cdots\cdots\\ f_n(x_1,x_2,\cdots,x_n)&=0\\ \end{cases}$
只要其中有一个是非线性函数，就称为是非线性方程组。

不动点迭代法

例子
求解非线性方程组
$\begin{cases} 3x_1-\cos(x_2x_3)-\frac{1}{2}=0\\ x^2_1-81(x_2+0.1)^2+\sin x_3+1.06=0\\ e^{-x_1x_2}+20x_3+\frac{10\pi -3}{3}=0 \end{cases}$

解
迭代公式为：
$\begin{cases} x_1^{(k+1)}=\frac{1}{3}\cos(x_2^{(k)}x_3^{(k)})+\frac{1}{6}\\ x_2^{(k+1)}=\frac{1}{9}\sqrt{(x_1^{(k)})^2+\sin x_3^{(k)}+1.06}-0.1\\ x_3^{(k+1)}=-\frac{1}{20}e^{-x_1^{(k)}x_2^{(k)}}-\frac{10\pi-3}{60} \end{cases}$

取初值 $x^{(0)}=(0.1,0.1,-0.1)^T$ ，迭代求得 $\alpha=(0.5,0.00000002,-0.52359877)^T$

Newton 迭代法

2020-04-25

2020-04-25

第五章非线性方程的求根

5.1 二分法

5.2 不动点迭代法

5.3 Newton 迭代法

5.4 Aitken 加速方法与重根迭代法

5.5 非线性方程组求根

相关阅读更多精彩内容

友情链接更多精彩内容

2020-04-25

第五章 非线性方程的求根

5.1 二分法

5.2 不动点迭代法

5.3 Newton 迭代法

5.4 Aitken 加速方法与重根迭代法

5.5 非线性方程组求根

相关阅读更多精彩内容

友情链接更多精彩内容

第五章非线性方程的求根