pc 移动的网站开发,营销型网站建设电话,哪个网站的ppt模板最好,wordpress 软件下载今天是周四高等数学专题的第7篇文章。之前的文章和大家聊了许多数学上的理论#xff0c;今天和大家聊点有用的东西。我们都知道#xff0c;工业上的很多问题经过抽象和建模之后#xff0c;本质还是数学问题。而说到数学问题就离不开方程#xff0c;在数学上我们可以用各种推…今天是周四高等数学专题的第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的点只有一个就可以使用二分来进行查找。深入思考就进入了二分法的第三个层次即放下递增的限制回到折半这个原始的概念上来。二分法的本质就是查找空间折半至于函数递增或者是数组当中元素递增都只是表象只是我们进行折半的条件。换句话说如果我们能找到其他的条件来折半搜索空间那么我们一样可以得到二分的效果并不用拘泥于是否有序。也就是说我们绕了一圈最后又回到了将“物体”一分为二这个最基本的概念上来。只是我们经过这么一波折腾表面上看和最初的理解一样但其实早已天差地别了。没想到算法领域也能玩一把禅宗看山是山看山不是山最后回到看山还是山。牛顿迭代法看完了二分法我们再来看另一个快速求根的方法和二分法一样它也是迭代逼近的方法但是逼近的速度更快。这个方法最早是牛顿提出的因此也被称为牛顿迭代法我想牛顿这个名字写出来大家应该都能get到它的分量。牛顿迭代法的名头看起来很唬人但是原理真的不难说白了只有一句话就是通过切线去逼近比如我们来看下图在上图当中我们要求 f(x)0 的根我们先找到了一个 xn点我们在 xn 处进行求导取得了它的切线。显然只要这个切线的斜率不为0那么我们一定可以获得它和x轴的交点。我们将这个交点作为下一个取值也就是 xn1的点。我们重复上述过程进行迭代很快就可以得到一个足够接近的解。对于点 xn 处的切线而言它的斜率是 f(xn)截距b就是 f(xn)。它的切线方程很好得到就是我们利用这个方程可以求到它和x轴的交点也就是xn1的值解下这个方程可以得到上面这个式子就是牛顿迭代法的迭代公式这是一个非常牛的方法比二分法要厉害得多因为它的收敛速度更快并且计算也并不复杂。我们来看下它的威力我们来看知乎鍵山小鞠[1]大神回答里的一个例子我们利用 f(x) sin(x) 来求 π 的值我们都知道在 [π/2, π] 区间内 sin(π) 0所以我们求 f(x) 0 的解就可以间接求出π的值。在这个问题下迭代公式为我们以 x0 3 为迭代起始点进行迭代得到的结果如下x03.0(1位)x13.1411...(4位)x23.14159265357...(11位)x33.1415926535897932384626433832795020...(34位)x43.14159265358979323846264338327950288419716939937510582097494459230781640628620899862803482534211706786...(102位)x53.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679821480865132823066470938446095505822317253594081284811174502841027019385211055596446229489549303819644288109756659334461284756482337867831652712019091456485669234603486104543266482133936072602491412734...(301位)可以看到短短经过五次迭代我们计算得到的圆周率已经超过了300位每次迭代我们的精度都会提升三倍以上这是非常令人震惊的。无法收敛的情况但令人遗憾的是并不是所有方程使用牛顿迭代法都可以有这么好的效果对于一些方程甚至可能会出现越走越偏的情况。我们再举个例子比如方程:如果我们画出它的迭代过程是这样的我们观察一下上面的迭代公式也可以看得出来我们把 -1/f(xn) 看成是系数我们对 f(x) 求导算下这个系数可以得到它的系数是3*x^{2/3}观察一下就能发现随着x的增大这个系数也是在增大的。也就是说随着我们的迭代这个值会变得越来越大也就意味着我们的振幅越来越大也就离收敛越来越远。虽然少数情况下牛顿迭代法不能收敛但是大多数情况下它效果都非常好。二分法固定每次缩短一半的区间而牛顿迭代法的迭代效率往往更高一般情况下使用牛顿迭代法可以获得更快的收敛速度。和二分法相比牛顿迭代法的公式也并不难写并且它在机器学习当中也有应用学会它真的非常划算今天关于二分和牛顿迭代法的文章就到这里如果觉得有所收获请顺手点个关注或者转发吧你们的举手之劳对我来说很重要。参考资料[1]知乎: https://www.zhihu.com/question/20690553
