牛顿迭代法(牛顿 |
您所在的位置:网站首页 › 迭代函数的参数要求是 › 牛顿迭代法(牛顿 |
起源[编辑]
牛顿法最初由艾萨克·牛顿在《流数法》(Method of Fluxions,1671年完成,在牛顿死后的1736年公开发表)。约瑟夫·拉弗森也曾于1690年在Analysis Aequationum中提出此方法。 方法说明[编辑]![]() ![]() 首先,选择一个接近函数 ![]() 我们将新求得的点的 ![]() 已经证明,如果
利用迭代算法解决问题,需要做好以下三个方面的工作: 一、确定迭代变量 在可以用迭代算法解决的问题中,至少存在一个可直接或间接地不断由旧值递推出新值的变量,这个变量就是迭代变量。 二、建立迭代关系式 所谓迭代关系式,指如何从变量的前一个值推出其下一个值的公式(或关系)。迭代关系式的建立是解决迭代问题的关键,通常可以使用递推或倒推的方法来完成。 三、对迭代过程进行控制 在什么时候结束迭代过程?这是编写迭代程序必须考虑的问题。不能让迭代过程无休止地执行下去。迭代过程的控制通常可分为两种情况:一种是所需的迭代次数是个确定的值,可以计算出来;另一种是所需的迭代次数无法确定。对于前一种情况,可以构建一个固定次数的循环来实现对迭代过程的控制;对于后一种情况,需要进一步分析得出可用来结束迭代过程的条件。 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 |