牛顿迭代法(牛顿 |
您所在的位置:网站首页 › 牛顿的英语全名是什么呢 › 牛顿迭代法(牛顿 |
起源[编辑]
牛顿法最初由艾萨克·牛顿在《流数法》(Method of Fluxions,1671年完成,在牛顿死后的1736年公开发表)。约瑟夫·拉弗森也曾于1690年在Analysis Aequationum中提出此方法。 方法说明[编辑] 蓝线表示方程 f而红线表示切线. 可以看出 x n+1比 x n更靠近 f所要求的根 x.首先,选择一个接近函数零点的,计算相应的和切线斜率(这里表示函数的导数)。然后我们计算穿过点并且斜率为的直线和轴的交点的坐标,也就是求如下方程的解: 我们将新求得的点的坐标命名为,通常会比更接近方程的解。因此我们现在可以利用开始下一轮迭代。迭代公式可化简为如下所示: 已经证明,如果是连续的,并且待求的零点是孤立的,那么在零点周围存在一个区域,只要初始值位于这个邻近区域内,那么牛顿法必定收敛。 并且,如果不为0, 那么牛顿法将具有平方收敛的性能. 粗略的说,这意味着每迭代一次,牛顿法结果的有效数字将增加一倍。
利用迭代算法解决问题,需要做好以下三个方面的工作: 一、确定迭代变量 在可以用迭代算法解决的问题中,至少存在一个可直接或间接地不断由旧值递推出新值的变量,这个变量就是迭代变量。 二、建立迭代关系式 所谓迭代关系式,指如何从变量的前一个值推出其下一个值的公式(或关系)。迭代关系式的建立是解决迭代问题的关键,通常可以使用递推或倒推的方法来完成。 三、对迭代过程进行控制 在什么时候结束迭代过程?这是编写迭代程序必须考虑的问题。不能让迭代过程无休止地执行下去。迭代过程的控制通常可分为两种情况:一种是所需的迭代次数是个确定的值,可以计算出来;另一种是所需的迭代次数无法确定。对于前一种情况,可以构建一个固定次数的循环来实现对迭代过程的控制;对于后一种情况,需要进一步分析得出可用来结束迭代过程的条件。 3示例编辑 欧几里德算法 最经典的迭代算法是 欧几里德算法,用于计算两个整数a,b的最大公约数。其计算原理依赖于下面的定理: 定理:gcd(a,b) = gcd(b,a mod b) 证明:a可以表示成a = kb + r,则r = a mod b。假设d是a,b的一个公约数,则有 a%d==0,b%d==0,而r = a - kb,因此r%d==0 ,因此d是(b,a mod b)的公约数 同理,假设d 是(b,a mod b)的公约数,则 b%d==0,r%d==0 ,但是a = kb +r ,因此d也是(a,b)的公约数。 因此(a,b)和(b,a mod b)的公约数是一样的,其最大公约数也必然相等,得证。 欧几里德算法就是根据这个原理来做的,欧几里德算法又叫辗转相除法,它是一个反复迭代执行,直到余数等于0停止的步骤,这实际上是一个循环结构。其算法用C语言描述为: int Gcd_2(int a,int b)/*欧几里德算法求a,b的最大公约数*/ { if (a2时)。 在n>2时,fib(n)总可以由fib(n-1)和fib(n-2)得到,由旧值递推出新值,这是一个典型的迭代关系,所以我们可以考虑迭代算法。 int Fib(int n) //斐波那契(Fibonacci)数列 { if (n < 1)/*预防错误*/ return 0; if (n == 1 || n == 2)/*特殊值,无需迭代*/ return 1; int f1 = 1,f2 = 1,fn;/*迭代变量*/ int i; for(i=3; ic>>d; x=diedai(a,b,c,d,x); cout |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |