⼆分法求⽅程的根_快速求解⽅程的根——⼆分法与⽜顿迭代
法
今天是周四⾼等数学专题的第7篇⽂章。
之前的⽂章和⼤家聊了许多数学上的理论，今天和⼤家聊点有⽤的东西。
我们都知道，⼯业上的很多问题经过抽象和建模之后，本质还是数学问题。⽽说到数学问题就离不开⽅程，在数学上我们可以⽤各种推算、公式，但是有没有想过在计算机领域我们如何解⼀个⽐较复杂的⽅程？
如果之前没有想过，那你可能得想⼀想，因为以后很有可能会在⾯试题当中遇到。
⼆分法
我们要介绍的第⼀个⽅法是⼆分法。
说到⼆分法⼤家应该都不陌⽣，⽼实说我第⼀次在⾼数课本上看到⼆分法这三个字的时候，其实是蛮震惊的。后来当我⼜在统计等数学书上看到许多其他算法之后，才慢慢习以为常。在我转⾏做算法的
这⼏年当中，我越来越意识到，数学的重要性。虽然这并不意味着你⼀定要成为数学⾼⼿，但如果你还没毕业的话，⾄少数学课好好听讲还是很有必要的。
我们说回⼆分法，如果学过⼆分法，会觉得这是⼀个⾮常简单的算法，但如果你们做过LeetCode第四题，⼜会发现纯⼆分法的题也可以这么难。如果只是单纯地讲解⼆分法的原理，我们是很难完完全全将这个算法吃透的。为了达到这点，我思考了很久，最终决定仿照看⼭是不是⼭的禅宗理论，将⼆分法也分成三个层次。
⾸先是第⼀个层次，即我们每次将⼀个东西分成两半。
这个应该是我们最初也是最直观的观念，⽐如最经典的⾦币问题。说是我们有若⼲个个硬币，其中有⼀个是⾦币，⾦币的重量更重，其他的硬币重量相等。我们只有⼀个天平，怎么样⽤最少的次数出⾦币。
在这个问题当中，我们需要不停地将硬币分成两个部分，⽤天平锁定其中的⼀个。通过不断重复上述操作，快速到答案。
在第⼆个层次当中，⼆分法不再是简单地将物体⼀分为⼆，⽽是⼀个折半查的函数。这也是本⽂重点要介绍的解⽅程的⽅法。
如果有函数 f(x) ，它在区间[a, b]上递增或者递减，并且 f(a)*f(b) < 0。那么我们知道函数必然有⼀个等于0的解，⽽且这个解我们可以⽤⼆分法来求近似解。
在上图当中，f(x)递增，并且f(a) < 0, f(b) > 0。我们继续获取了a和b的中点 x0。根据上图，我们⼜得到 f(x0) > 0，所以我们可以把 x0看成是新的b。于是我们继续寻a和 x0 的中点，重复上述过程，由于我们最⼤的误差就是区间的长度，所以当我们区间的长度缩减到⾜够⼩，那么就说明我们已经到了⼀个⾜够近似的解。
在⼆分法当中，我们没进⾏⼀次⼆分迭代，区间的长度就会缩减⼀半，这是⼀个指数级的缩减。所以即使⼀开始的区间很⼤，经过⼆分迭代也可以迅速缩减，得到⼀个⾮常精准的结果，并且和泰勒级数⼀样，除了能得到⼀个⾜够精确的值之外，还能得到误差的范围。
我们再深⼊⼀些思考，会发现有些条件我们还可以再松动松动。⽐如我们真的需要函数是严格递增或者递减吗？⽐如我们来看下⾯这张图：
在(b2, b1)区间内，函数并不是严格递减的，⽽是先递减再递增的。但是这并不会影响结果的正确性，因为在这个问题当中，⼆分法并不是通过判断 f(x0) 和a处函数值的⼤⼩来缩⼩区间的，⽽是通过f(x0)的正负性。也就是说，只需要满⾜ f(a)*f(b) < 0，并且函数连续且等于0的点只有⼀个，就可以使⽤⼆分来进⾏查。
深⼊思考，就进⼊了⼆分法的第三个层次，即放下递增的限制，回到折半这个原始的概念上来。
⼆分法的本质就是查空间折半，⾄于函数递增或者是数组当中元素递增都只是表象，只是我们进⾏折半的条件。换句话说如果我们能到其他的条件来折半搜索空间，那么我们⼀样可以得到⼆分的效果，并不⽤拘泥于是否有序。
也就是说我们绕了⼀圈，最后⼜回到了将“物体”⼀分为⼆这个最基本的概念上来。只是我们经过这么⼀波折腾，表⾯上看和最初的理解⼀
样，但其实早已天差地别了。
没想到算法领域也能玩⼀把禅宗，看⼭是⼭，看⼭不是⼭，最后回到看⼭还是⼭。
c语言牛顿迭代法求根
⽜顿迭代法
看完了⼆分法，我们再来看另⼀个快速求根的⽅法，和⼆分法⼀样，它也是迭代逼近的⽅法，但是逼近的速度更快。这个⽅法最早是⽜顿提
出的，因此也被称为⽜顿迭代法，我想⽜顿这个名字写出来，⼤家应该都能get到它的分量。
⽜顿迭代法的名头看起来很唬⼈，但是原理真的不难，说⽩了只有⼀句话，就是通过切线去逼近，⽐如我们来看下图：
在上图当中，我们要求 f(x)=0 的根，我们先到了⼀个 xn点，我们在 xn 处进⾏求导取得了它的切线。显然只要这个切线的斜率不为0，
那么我们⼀定可以获得它和x轴的交点。我们将这个交点作为下⼀个取值，也就是 xn+1的点。我们重复上述过程进⾏迭代，很快就可以得
到⼀个⾜够接近的解。
对于点 xn 处的切线⽽⾔，它的斜率是 f'(xn)，截距b就是 f(xn)。它的切线⽅程很好得到，就是：
我们利⽤这个⽅程，可以求到它和x轴的交点，也就是xn+1的值：
解下这个⽅程，可以得到：
上⾯这个式⼦就是⽜顿迭代法的迭代公式，这是⼀个⾮常⽜的⽅法，⽐⼆分法要厉害得多，因为它的收敛速度更快，并且计算也并不复杂。
我们来看下它的威⼒，我们来看知乎鍵⼭⼩鞠[1]⼤神回答⾥的⼀个例⼦：
我们利⽤ f(x) = sin(x) 来求 π 的值，我们都知道在 [π/2, π] 区间内， sin(π) = 0，所以我们求 f(x) = 0 的解就可以间接求出π的值。
在这个问题下，迭代公式为：
我们以 x0 = 3 为迭代起始点，进⾏迭代，得到的结果如下：
x0=3.0(1位)x1=(4位)x2=(11位)x3=(34位)x4=3.141592653589793238462643383279502
可以看到，短短经过五次迭代，我们计算得到的圆周率已经超过了300位，每次迭代我们的精度都会提升三倍以上，这是⾮常令⼈震惊的。
⽆法收敛的情况
但令⼈遗憾的是并不是所有⽅程使⽤⽜顿迭代法都可以有这么好的效果，对于⼀些⽅程，甚⾄可能会出现越⾛越偏的情况。我们再举个例
⼦，⽐如⽅程:
如果我们画出它的迭代过程，是这样的：
我们观察⼀下上⾯的迭代公式也可以看得出来，我们把 -1/f'(xn) 看成是系数，我们对 f(x) 求导算下这个系数，可以得到它的系数是
3*x^{2/3}，观察⼀下就能发现随着x的增⼤，这个系数也是在增⼤的。也就是说，随着我们的迭代，这个值会变得越来越⼤，也就意味着我们的振幅越来越⼤，也就离收敛越来越远。
虽然少数情况下⽜顿迭代法不能收敛，但是⼤多数情况下它效果都⾮常好。⼆分法固定每次缩短⼀半的区间，⽽⽜顿迭代法的迭代效率往往更⾼，⼀般情况下使⽤⽜顿迭代法可以获得更快的收敛速度。和⼆分法相⽐，⽜顿迭代法的公式也并不难写，并且它在机器学习当中也有应⽤，学会它真的⾮常划算！
今天关于⼆分和⽜顿迭代法的⽂章就到这⾥，如果觉得有所收获，请顺⼿点个关注或者转发吧，你们的举⼿之劳对我来说很重要。
参考资料
[1]
知乎: "www.zhihu/question/20690553"

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。