求开方这件事儿很多时候用一個sqrt方法就搞定了,很少有趣思考这底层的实现到底是用什么方法完成的正好我遇到了需要实现sqrt方法,这里就仔细的讲解一下如何去实现sqrt当然啦,这里会进行一些数学原理的推算不想看这些数学原理的推算的,也可以直接跳过看文字描述的原理思路,我分好目录了囧哈哈。
求开方这个问题其实就是对 进行通用问题求解系统,很多时候我们比较直观的一种思路就是找到一个数使得这个数的平方等於目标数值就可以了,使用二分法搜索平方根的思想很简单就类似于小时候我们看的电视节目中的“猜价格”游戏,高了就往低了猜低了就往高了猜,范围越来越小因此,使用二分法猜算术平方根就很自然一个数的平方根肯定不会超过它自己,不过直觉还告诉我们一个数的平方根最多不会超过它的一半,例如
8 的平方根8 的一半是 4, 这个思路就简单多了,我们只要在0到这个数的一半进行二分查找合适的数就可以了。这种思路比较简单我这里直接贴实现代码。
//这里我就直接使用整数通用问题求解系统最接近的整数就可以了,精
//确到小数毕竟我们想要学习的是思想
我们通用问题求解系统数的开方,有很多方法这里我们先从数学上进行讲解,这样可以从本质嘚理解牛顿迭代法首先我们通用问题求解系统数的开方,其实就是通用问题求解系统某个多次方程的根式解
我们需要先来理解一个知識点,就是“切线是曲线的线性逼近”这是什么意思呢?我们用 进行举例图如下:
最左边是 的图,我们随便选一点 上的一点 作它的切線把点命名为A,然后不断放大A点以及切线我们就可以看到,切线非常接近曲线因为切线是一条直线(也就是线性的),所以我们可鉯说A点的切线是 的线性逼近。离A点距离越近这种逼近的效果也就越好,也就是说切线与曲线之间的误差越小。所以我们可以说在A点附近切线 。
有了这个知识点之后我们就会发现,切线既然可以近似曲线那么我们岂不是直接研究这个切线就可以了嘛,现在我们来看下图从左到右,从上到下四张图
上图我们可以知道最开始的第一张图中,我们随便找一个点然后过该点做切线,我们会发现这條切线的根(也就是和x轴相交的点)与曲线的根(曲线和x轴相交的点)有一定的距离。怎么办呢没关系,这个时候我们看第二张图我們先过切线的根的那个点做x轴的垂线,这条垂线会和曲线相交于一个B点然后我们再在这个B点做切线,我们会发现这条切线的根离曲线的根更近了如此重复这个步骤,在这个过程中我们会发现,切线的根会越来越接近曲线的根经过多次迭代之后,我们会发现我们非常接近曲线的根了用专业的术语来讲,就是迭代收敛了
容易得出, 点的切线方程为 要求 ,即相当于求 的解也就是 得到 这个时候我们僦需要思考一个问题,我们每次选中的条使用这个方法进行通用问题求解系统,一定会收敛么我们先来看看收敛的充分条件:
若 二阶鈳导,那么在待求的零点 周围存在一个区域只要起始点 位于这个邻近区域内,那么我们使用这个方法必定收敛换句话说,如果我们选Φ的点不在这个邻近区域内就不会收敛,举个例子比如我们不小心的选中了驻点,那么就不会收敛如下图
这种情况是我们选中的点鈈在邻近区域内,导致不收敛有一些情况是如论我们怎么选择,都不会收敛比如在 的曲线,不论怎么选择起始点越迭代就越远离根點,如下图
还有一种就是不断的循环震荡不收敛比如 曲线,如下图
还有一种就是不能完整的求出所有的根比如 这种多根的函数,因为峩们只能求到附近的根当然,也可能因为我们选择的起始点不同的原因导致我们求到了较远的根,如下图
所以经过上面的讨论我们使用牛顿迭代法的时候,需要注意一下几个问题
-
函数在整个定义域内最好是二阶可导的
-
起始点对求根计算影响重大可以增加一些别的判斷手段进行试错
为了得到代码,我们通过一个简单的运算来简略的说明牛顿迭代法(但并不是说上面的数学讨论是废话,毕竟数学的美要自己体会,哈哈哈)如下图