数值分析—非线性方程的数值解

研究背景

形如$x-tanx=0$、$xlnx+e^{-x^2}+sinx=0$等称为非线性方程，自变量之间并非简单的线性关系，这种问题我们无法通过其结构求解，需要其他的逼近方式，本章将基于该问题介绍两种方法——二分法，迭代法。

二分法

预备知识

零点定理：
若$f(x)\in [a,b]$且$f(a)f(b)<0$，则$f(x)$在$(a,b)$内至少有一个零点，若$f(x)$为单调函数，则$f(x)$有唯一零点。

重根判别方法：
设$f(x)$在$x$有n阶导数，则$x$为$f(x)=0$的m重根的充要条件为：
$f(x)=f^{\prime }(x)=f^{m-1}(x)=0且f^m(x)!=0$。

求实根的二分法

基本思想为：
将有根区间一分为二，等分为两个区间，判断根再哪一个更小的区间，舍去无根的小区间，再把有根的小区间等分，如此重复，直到找到满足精度的近似根。

算法流程：
取终点$x_0=\frac{a+b}{2}$，若$f(x_0)=0,x_0$为所求，否则计算$f(a)f(x_0)$的符号，$>0$取区间$[x_0,b]$，$<0$取$[a,x_0]$，重复上述过程，无穷多次后即为精确解${\lim }_{k\to \infty }{x}_k=x$，但计算中不可能迭代无穷多次，也不可能得知精确解，故一般采用前后两次迭代逼近的程度来衡量，$|x_k-x_{k-1}|\le \frac{b_k-a_k}{2}=\frac{b-a}{2^{k+1}}$，取精度$\frac{b-a}{2^{k+1}}<\epsilon$，迭代步数为$k>\frac{ln(b-a)-ln2\epsilon }{ln2}$

例题：二分法求$f(x)=x^2-x-1=0$的正根，要求误差不超过0.05。
解：
设$f(x)=x^2-x-1,f(1)=-1<0,f(2)=1>0$，故有根区间为$[-1,2]$，该函数在区间内单调，$k>\frac{-ln0.1}{ln2}=\frac{10}{ln2}=3.3$，取步长k=4，求其根表示为：

k	$a_k$	$b_k$	$x_k$	f(x)符号
0	1	2	1.5	-
1	1.5	2	1.75	+
2	1.5	1.75	1.625	+
3	1.5	1.625	1.5625	-
4	1.5625	1.625	1.59375

答：根为1.59375。

该方法实现简单，普及性高，对方程只要求其连续即可，但收敛速度缓慢，下面介绍一种加速收敛的方法—迭代法。

迭代法

基本思想

$f(x)=0<=>x=g(x)$，$g(x)$为迭代函数，$x_{k+1}=g(x_k)$，给定$x_0$可计算$x_1....x_n$，若该数列收敛，则称迭代法$x_{k+1}=g(x_k)$收敛，否则发散。

若$x^{\ast }$满足$x^{\ast }=g(x^{\ast })$则称$x^{\ast }$为$g(x)$的不动点。
若${\lim }_{k\to \infty }{x}_k=x^{\ast }，g(x)$连续，$x^{\ast }={\lim }_{k\to \infty }{x}_{k+1}={\lim }_{k\to \infty }g(x_k)=g({\lim }_{k\to \infty }{x}_k)=g(x^{\ast })$

该过程重点在于：
1，如果构造$g(x)$
2，$g(x)$满足何种条件能保证数列$x_n$收敛
3，收敛速度如何衡量

该方法的几何意义为以直代曲，用切线零点代替曲线零点，不断逼近坐标轴的过程。

迭代格式的适定性与收敛性

定义：如果$x_0\in [a,b]$，若按$x_{k+1}=g(x_k)$生成的序列$x_k\in [a,b]$，则称迭代格式是适定的，适定性是迭代格式能够继续下去的重要条件。

例如：求$x{e}^x-1=0$在$x=0.5$附近的根。
解:$x=e^{-x}$，构造迭代格式$x_{k+1}=e^{-x_k},x_0=0.5$,可继续迭代
$e^x=\frac{1}{x},x=-lnx$，构造$x_{k+1}=-ln{x}_k,x_0=0.5,x_4<0$时终止

定理一：设$g(x)\in [a,b]$，且满足如下条件：
1,任意$x\in [a,b]$，总有$g(x)\in [a,b]$
2,存在$L\in [0,1],使|g(x)-g(y)|\le L|x-y|，x，y为[a,b]内的任意数$
则$g(x)$在$[a,b]$上存在唯一不动点$x^{\ast }$对任意$x\in [a,b]$迭代法适定且收敛，但该条件很不好证明，故多采用定义二。

定理二：若$g(x)\in [a,b]$且满足如下条件：
1，任意$x\in [a,b]，有g(x)\le [a,b]$
2，存在$0\le L\le 1，使对任意x\in [a,b]有|g^{\prime }(x)|\le L$，该定理用导数代替了验证过程。
则$x_{k+1}=g(x_k)\le \frac{L^k}{1-L}|x-x_0|$

注：
1，不等式为停机标准，$|x_{k+1}-x_k|<\epsilon$时，$|x^{\ast }-x^k|\le \frac{\epsilon }{1-L}$
2，先验估计，用于估计达到$\epsilon$精度所需迭代的步数为
$\frac{L^k}{1-L}|x_1-x_0|<\epsilon$，从而$k>\frac{ln(\frac{-(1-L)\epsilon }{(x_1-x_0)})}{lnL}$
3，L越小收敛速度越快。

局部收敛性与收敛阶

定义：$x^{\ast }为g(x)$的不动点，对$\delta >0,称N(x^{\ast },\delta )=[x^{\ast }-\delta ,x^{\ast }+\delta ]$为$x^{\ast }$的一个邻域，若存在一个邻域使对任意$x\in N(x^{\ast },\delta )$按$x_{k+1}=g(x_k)$生成的$x_k\in N(x^{\ast },\delta )$且${\lim }_{x\to \infty }{x}_k=x^{\ast }$，则称迭代格式具有迭代收敛性。
即在邻域内无穷次迭代后能获得精确解。

定理一：设$g(x)在x=g(x)$的根$x^{\ast }$邻域内有连续的一阶导数，且$|g^{\prime }(x^{\ast })|<1$，迭代法具有局部收敛性。
注：实际使用时往往用$|g^{\prime }(x_0)|<1$代替

n阶导数<1收敛，则收敛阶为n。

例题：迭代函数$g(x)=x+c(x^2-3)$，讨论1，写出迭代格式，产生$k$收敛于$\sqrt{3}$，问c应为何值？2，c为何值时收敛速度最快？
解：1，迭代格式$x_{k+1}=g(x_k)=x_k+c(x_k^2-3)，g^{\prime }(x)=1+2cx，|g^{\prime }(\sqrt{3})|=|1+2\sqrt{3}c|<1=>-\frac{\sqrt{3}}{2}<c<0$
2，$g^{\prime }(\sqrt{3})=0,1+2\sqrt{3}c=0,c=-\frac{\sqrt{3}}{6}$收敛最快

Newton迭代法

基本思想：满足一般理论的特殊迭代法，$f(x)=0$先假设$x_k$为$f(x)=0$的近似根，$f^{\prime }(x_k)!=0$，将$f(x)$在$x_k$处作Taylor展开，$f(x)\approx f(x_k)+f^{\prime }(x_k)(x-x_k)+\frac{f^{\prime \prime }(\xi )}{2!}(x-x_k{)}^2$，舍去余项后$f(x)\approx f(x_k)+f^{\prime }(x_k)(x-x_k)$，$f(x_k)+f^{\prime }(x_k)(x-x_k)=0$，故$x=x_k-\frac{f(x_k)}{f^{\prime }(x_k)}$，不动点带入获得迭代函数$g(x)=x-\frac{f(x)}{f^{\prime }(x)}$。

该方法的几何意义是以直代曲，沿曲线方向不断作切线，和x轴的交点作为下一次切线起点，形成一个不断逼近$x^{\ast }$的数列。

例题：Newton迭代法求$f(x)=x^3+2x-6$在1.5附近的根。
解：$f^{\prime }(x)=3x^2+2$，Newton迭代公式$x_{k+1}=x_k-\frac{x_k^3+2x_k-6}{3x_k^2+2}$，取$x_0=1.5$迭代运算，$x_1=1.4571429，x_2=1.4561647$
可以看到Newton迭代法的收敛速度还是比较快的。

Newton迭代法的收敛性与收敛阶

局部收敛性定理：
设$x^{\ast }$为$f(x)=0$的单根，即$f(x^{\ast })=0,f^{\prime }(x^{\ast })!=0$，则Newton迭代格式$x_{k+1}=x_k-\frac{f(x_k)}{f^{\prime }(x_k)}$至少二阶收敛。

非局部收敛性定理：
设$f(x)\in c^2[a,b]$且满足如下条件：
1，$f(a)f(b)<0$
2，$f^{\prime }(x)!=0,任意x\in [a,b]$
3，$x\in [a,b]时，有f^{\prime }(x)不变号$
4，$任意x_0\in [a,b],使f(x_0)f^{\prime \prime }(x_0)>0$
则由Newton迭代格式确定的$x_k$收敛于$f(x)=0$在$[a,b]$有唯一根$x^{\ast }$

简化后的Newton法：
该迭代法主要的计算量来自导数，故简化后采用$x_{k+1}=x-\frac{f(x)}{C}$用常数C代替之，$C=f^{\prime }(x_0)$，该方法使用固定点的导数作为常数来代替后续导数计算，固然简化了计算，但收敛速度也随之下降。

求重根的Newton法

设$x^{\ast }$为$f(x)=0$的重根，$f(x^{\ast })=f^{\prime }(x^{\ast })=...=f^{n+1}(x^{\ast })=0$且$f^n(x^{\ast })!=0$，$f(x)=(x-x^{\ast })A(x)$，显然$A(x^{\ast })!=0$。

Newton迭代法$x_{k+1}=x_k-\frac{f(x_k)}{f^{\prime }(x_k)}，g(x)=x-\frac{f(x)}{f^{\prime }(x)}，g^{\prime }(x^{\ast })<1$收敛，$g^{\prime }(x)=\frac{f(x)f^{\prime \prime }(x)}{[f^{\prime }(x){]}^2}$，故$g^{\prime }(x^{\ast })=\frac{f(x^{\ast })f^{\prime \prime }(x^{\ast })}{[f^{\prime }(x^{\ast }){]}^2}={\lim }_{x\to x^{\ast }\frac{g(x)-g(x^{\ast })}{x-x^{\ast }}}$，最后很复杂，一同操作后得证$g^{\prime }(x^{\ast })=1-\frac{1}{m}$

例题：$x^3-3x^2+4=0$，试用Newton迭代法求$x^{\ast }=2$，并证明收敛性，求收敛阶。
解：$f(x)=x^3-3x^2+4，f^{\prime }(x)=3x^2-6x，x_{k+1}=x_k-\frac{f(x_k)}{f^{\prime }(x_k)}=x_k-\frac{x_k^3-3x_k^2+4}{3x_k^2-6x_k}$，则$g(x)=x-\frac{x^3-3x^2+4}{3x^2-6x}$，若$|g^{\prime }(2)|<1$收敛，$x^{\ast }=2$为$f(x)$的二重根，根据$1-\frac{1}{m}=>|g^{\prime }(2)|=\frac{1}{2}<1$故收敛且线性收敛。

Newton法改进

1，$f(x)=0$的重根$x^{\ast }$的重数m已知，则可得到$x_{k+1}=x_k-m\frac{f(x_k)}{f^{\prime }(x_k)}，g(x)=x-m\frac{f(x)}{f^{\prime }(x)}，g^{\prime }(x^{\ast })=1-m\frac{1}{m}=0$，故至少平方收敛。

2，$f(x)=0$的重根$x^{\ast }$的重数m未知，令$u(x)=\frac{f(x)}{f^{\prime }(x)}$，若$x^{\ast }$为$f(x)$的m重根，$x^{\ast }$为$f^{\prime }(x)$的m-1重根，$x^{\ast }$必为$u(x)$的单根，只需构造$u(x)=0$的单根Newton法，$x_{k+1}=x_k-\frac{u(x_k)}{u^{\prime }(x_k)},u^{\prime }(x)=\frac{[f^{\prime }(x){]}^2-f(x)f^{\prime }(x)}{[f^{\prime }(x){]}^2},x_{k+1}=x_k-\frac{f(x_k)f^{\prime }(x_k)}{[f^{\prime }(x_k){]}^2-f(x_k)f^{\prime \prime }(x_k)}$，至少平方收敛。

例题1：设$f(x)=x^4-6x^2+8x-3$，求$x_1=3,x_2=1$的二阶局部收敛的Newton法。
解：首先判断单根还是重根，$f^{\prime }(x)=4x^3-12x+8,x_1=3,f(-3)=0,f^{\prime }(-3)!=0$，所以$x_1=3$为单根，用二阶收敛的呢我同法，$x_{k+1}=x_k-\frac{x_k^4-6x_k^2+8x_k-3}{4x_k^3-12x_k+8}$。
$x_2=1,f(1)=0,f^{\prime }(1)=0,f^{\prime \prime }(1)=0,f^{\prime \prime \prime }(1)!=0$，所以$x_2=1$为三重根，方法同上，二阶收敛的Newton法$x_{k+1}=x_k-3\frac{x_k^4-6x_k^2+8x_k-3}{4x_k^3-12x_k+8}$。

总结

本章介绍了非线性方程的数值解法，二分法实现简单，但收敛很慢，迭代法主要是Newton迭代法，用泰勒公式近似方程，着重分析其收敛性和收敛阶，该章公式很多很杂，大量篇幅在于分析性质而非单纯计算，到整理完毕整体也没消化完，还需后面补足，大致为：确定适定性，分析收敛性，写出迭代格式，计算收敛阶。

这也是数值分析的最后一章，我们依次介绍了误差分析的方法、线性方程组的数值解法、函数插值的预测法、数值积分的近似计算法和本章非线性方程的数值解法，这些方法我们以后未必能用得到，但通过对这些方法学习，我们如果能体会这种逼近和代替的思想也是很大的收获，现实世界的很多问题我们没法精确求解分析，构造相近的情景再解决也算是曲线救国了。