《算法基础》——2.6 查找零-阿里云开发者社区

开发者社区> 华章计算机> 正文

《算法基础》——2.6 查找零

简介:
+关注继续查看

本节书摘来自华章计算机《算法基础》一书中的第2章,第2.6节,作者:(美)罗德·斯蒂芬斯(Rod Stephens)著,更多章节内容可以访问云栖社区“华章计算机”公众号查看

2.6 查找零

有时候程序需要找出一个方程在哪里与x轴有交点。 换句话说,给定方程为y=f(x),找到x的值,满足f(x)=0,这个值被称为方程的根。
牛顿法,该方法有时被称为牛顿-拉弗森法,是一种解出连续近似方程的根的方法。该方法起始于最初猜测X0为根。当f(X0)是不够接近0时,该算法生成一条与函数相切于点X0的直线。它采用交点的x坐标作为一种新的猜测X1来求方程的根。
该算法然后从新猜测出的X1开始重复此过程,继续沿着函数的切线方向找到根作为新猜测,直到它找到一个值Xk满足F(Xk)足够接近0。
唯一棘手的部分是搞清楚如何沿着切线进行计算。如果使用微积分找到函数的导数f(x),这也可以写作。
下面的公式显示了一种算法如何通过沿着一条切线更新其对根的猜测:
screenshot

注不幸的是,如何找到一个函数的导数不在这本书的范围之内。欲了解更多信息,可以在网上搜索或咨询微积分的书。

screenshot


图2-7显示了该算法图形化的过程。初始猜测的点被标记为1。这点的y值是远不为0的,所以该算法沿切线寻找相交于x轴的新猜测点。算法然后利用新的猜测点计算函数值,以获得在图2-7中标记为2的点。 这点的y坐标也远不为0,所以该算法重复该过程,以寻找下一个猜测,被标记为 3,该算法再一次重复这个过程来找到被标记为4的点,第4点的y坐标足够接近0,所以算法停止。
下面的伪代码显示出该算法:
screenshot

该算法将函数y=f(x),函数的导数screenshot初步推测值以及可接受的最大误差值作为参数。
代码设置变量x等于初始猜测,然后进入For语句循环,最多执行100次。通常情况下,算法很快就找到一个答案。
但在一些情况下,如果函数有正确的曲率,该算法会发散,并且不局限于一个答案,它可以来回跳跃于两种不同的猜测之间。最多100次的循环意味着该程序永远不能停止。
在For循环中,该算法计算f(x)。如果结果不足够接近0时,算法将更新x的值并且重新尝试。
请注意,某些函数有一个以上的根。在这种情况下,需要重复使用FindZero算法用不同的初始猜测找到每一个根。
如图2-8所示的牛顿法示例程序,可以在这本书的网站上找到。这个程序使用了三次牛顿法则来找到函数y=x3/5-x2+x的三个根。圆圈表示搜索到的作为程序猜测的每一个根。

screenshot

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
NOIP-C++大神培养计划 Step1.1.2基础算法——模拟算法2
大家好,我是小笨笨,今天我们继续来讲解模拟算法。 我们直接上例题! 栗1.1.2-1 洛谷P1014 Cantor表https://www.luogu.org/problemnew/show/P1014题目描述现代数学的著名证明之一是Georg Cantor证明了有理数是可枚举的。
987 0
线性查找算法
十大算法之线性查找: 介绍: BFPRT算法解决的问题十分经典,即从某n个元素的序列中选出第k大(第k小)的元素,通过巧妙的分 析,BFPRT可以保证在最坏情况下仍为线性时间复杂度。该算法的思想与快速排序思想相似,当然,为使得算法在最坏情况下,依然能达到o(n)的时间复杂 度,五位算法作者做了精妙的处理。
778 0
二分查找算法
十大算法之二分查找: 二分查找算法是在有序数组中用到的较为频繁的一种算法,在未接触二分查找算法时,最通用的一种做法是,对数组进行遍历,跟每个元素进行比较,其时间为O(n).但二分查找算法则更优,因为其查找时间为O(lgn),譬如数组{1, 2, 3, 4, 5, 6, 7, 8, 9},查找元素6,用二分查找的算法执行的话,其顺序为:     1.第一步查找中间元素,即5,由于56,则6应该在7左边的数组元素中,那么只剩下6,即找到了。
639 0
【阿里云新品发布·周刊】第3期:零算法基础快速训练稳定、高效的AI模型
将你想了解的,新产品、新版本、新技术、新功能、价格调整,评论在下方,下期更新!
9029 0
算法-二分查找极其效率
因为二分查找是一半一半的找,所以每次查找之后都会把查找范围减半; 比如说在一个 1 - 8 的有序数组里面查找 8 也就是查找最坏情况。 在数组当中完成二分查找需要 log2n - 1 次; 也就是时间复杂度是 log2n (就是 log 以 2 为底 n 的对数)
5 0
Java数组排序基础算法,二维数组,排序时间计算,随机数产生
import java.util.Arrays; //包含Arrays import java.util.Random; public class HelloWorld { public static void main(String[] args){ // Scanner s = new Scanner(System.
853 0
查找类算法之二分搜索树 | 算法必看系列十
二分搜索树是为了实现快速查找而生的,也支持快速添加和删除一个数据。如何查找某个元素首先跟根节点去做比较,如果相等的话就返回;如果待查元素要比根节点小,就进行左子树递归查找;如果待查元素要比根节点大,就进行右子树的递归查找;如果查找到最后还没有一个符合的元素,就返回null。
559 0
10059
文章
0
问答
来源圈子
更多
+ 订阅
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载