jiyang1971的个人博客分享 http://blog.sciencenet.cn/u/jiyang1971

博文

计算方法之灵根孕育源流出 精选

已有 4557 次阅读 2018-11-7 14:27 |个人分类:大众物理学|系统分类:科普集锦

 


 

万缕千丝终不改,任他随聚随分。韶华休笑本无根:好风凭借力,送我上青云。

 

很多计算问题都可以归结为求某个方程的根,也就是满足方程$f(x)=0$$x$值。

最基本的方程是单变量的方程。线性方程和二次方程都很简单,三次方程和四次方程也有公式可用(虽然谁也不用),除此而外,就没有那么容易了。比如说,非线性方程$x=\tan x$有很多解,除了最简单的$x=0$以外,其他解都不是很显然的。

简单谈谈非线性方程的几种求根方法。

 

首先,需要判断$f(x)=0$是否有根,但是并没有一般性的方法。代数基本定理告诉我们,$x$$n$次多项式必然有$n$个复数解,然而,这些解并不一定是实数解(物理学通常关心的都是实数),只有实系数的奇数次多项式可以保证有一个实数解。对于一般性的非线性方程,更没有什么可说的了——只能是看运气,当然要认真地观察和思考,还有试探。

对于连续的实函数,如果存在$x_1$和$x_2$使得$f(x)$的数值具有不同的符号,即$f(x_1)f(x_2)<0$,就肯定存在一个解$x_1<x<x_2$,使得,$f(x)=0$。在区间$((k-\frac{1}{2})\pi,(k+\frac{1}{2})\pi)$(其中,$k$是整数)考察方程$x=\tan x$,因为,$\tan x$$x\rightarrow (k+\frac{1}{2})\pi$时趋于正无穷大,在$x\rightarrow (k-\frac{1}{2})\pi$时趋于负无穷大,所以,$f(x)=\tan x -x$肯定有解。

 

然后,猜一个解出来。令$x=(k+\frac{1}{2})\pi-\delta$,带入方程$x=\tan x$,可以得到

$(k+\frac{1}{2})\pi-\delta=\cos \delta/\sin \delta\approx \frac{1-\delta ^2/3}{\delta}$

这就是一个简单的一元二次方程,使用求根公式,再泰勒展开,就可以得到约等于0的解是

 $\delta\approx \frac{1}{(k+\frac{1}{2})\pi}+\frac{2}{27(k+\frac{1}{2})^3\pi ^3}$

所以,近似解就是

$x_0=(k+\frac{1}{2})\pi-\delta \approx (k+\frac{1}{2})\pi - \frac{1}{(k+\frac{1}{2})\pi}-\frac{2}{27(k+\frac{1}{2})^3\pi ^3}$

 

 然后,有好几种方法可以给出更精确的根。

二分法。在$x_0$附近,找出两个值$x_1$$x_2$,使得$f(x)=\tan x -x$在这两点的值具有不同的符号,即$f(x_1)f(x_2)<0$。取$x_1$$x_2$的中点$x_3=(x_1+x_2)/2$,计算那里的函数值$f(x_3)$,它必然与$f(x_1)$$f(x_2)$的一个具有相反的符号(除非你走了大运,碰上了$f(x_3)=0$),就算是$x_1$好了。那么,你就可以用$x_1$$x_3$重复这个两分过程,直到给出一个你满意的解为止。

 

迭代法。把方程$f(x)=0$写成$x=g(x)$的形式,把$x$的一个猜测值$x_i$带入右边,就可以得到一个新的猜测值$x_{i+1}$。我们把$x_0=(k+\frac{1}{2})\pi-\frac{1}{(k+\frac{1}{2})\pi}$带入。为了娱乐起见,我们只采用了一级近似值,并选择$k=10$。经过一些变换,可以得到迭代方程为

$x=10.5\pi - \frac{1}{\tan x}$

初始值是$x_0=1/10.5\pi \approx 0.0303$。不幸的是,用不了几次就会发现,迭代的结果变来变去,根本就不收敛。这是因为迭代方程右边的函数的导数太大了。这种现象其实很常见,必须选择适当的迭代函数(这需要技巧,或者说熟能生巧)。令$x=\arctan y$,则迭代方程变为

$ y = \frac{1}{10.5\pi-\arctan y}$

初始值是$y_0 =\tan x_0 \approx 0.0303$。迭代几次就可以得到$y= 0.030343131$,所以,$x=10.5\pi - 0.03033823$

 

牛顿法。对于$f(x)=0$,在近似解$x_i$附近,有泰勒展开

$f(x)=f(x_i)+f'(x_i)(x-x_i)+\frac{1}{2}f"(\zeta)(x-x_i)^2$

所以,原方程$f(x)=0$就可以近似为线性方程

$f(x_i)+f'(x_i)(x-x_i)=0$

这就得到了迭代公式

$x_{i+1}=x_i-\frac{f(x_i)}{f'(x_i)}$

对于我们感兴趣的方程$f(x)=10.5\pi - \frac{1}{\tan x}-x=0$,初始值是$x_0=0.0303$,导数是$f'(x)=1/\sin ^2 x -1$。迭代两三次就可以得到,$x=0.030333823$。这个结果与上面的迭代法相同。带回原方程$x=\tan x$,可以发现,两端的差别差别大约是$5\times 10^{-8}$,而两端的数值大约是33,也就是说,相对误差是$10^{-9}$

 

弦割法。牛顿法需要计算导数,有些麻烦,可以用差分来替代导数,这就是弦割法。先在近似解附近找到函数曲线上的两个点$(x_1,f(x_1))$和$(x_2,f(x_2))$,把这两个点连接起来,得到一条直线,该直线与$x$轴的交点就是$x_3$。然后用$(x_2,f(x_2))$$(x_3,f(x_3))$找到$x_4$,如此继续下去。具体计算从略。

 

在这些算法的基础上,还有很多改进的算法,就不介绍了。

需要指出的是,只有二分法能够保证找到根,其他几种方法只有在距离根足够近的地方才行。但是二分法的效率非常低,三次迭代才能提高一位的精度($2^3=8\approx 10$)。牛顿法的精度最高,但是其收敛性强烈地依赖于初值。

其实,这些算法的误差分析才是计算方法的主要内容,我们这里介绍的仅仅是算法的具体步骤而已。

 



http://blog.sciencenet.cn/blog-1319915-1145027.html

上一篇:几本图文并茂的书
下一篇:计算方法之渊停岳峙

12 李颖业 王安良 张江敏 李毅伟 沈律 武夷山 张小元 黄永义 郭景涛 宁利中 赵克勤 黄裕权

该博文允许注册用户评论 请点击登录 评论 (1 个评论)

数据加载中...

Archiver|手机版|科学网 ( 京ICP备14006957 )

GMT+8, 2018-12-17 00:24

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部