牛顿迭代法

概念理解

牛顿迭代法可以使用函数极限角度无限迭代趋近于某一点理解。

迭代算法解决问题，需要做好3个方面的工作：

确定迭代变量 在可以用迭代算法解决的问题中，至少存在一个可直接或间接地不断由旧值递推出新值的变量，这个变量就是迭代变量。

建立迭代关系式 所谓迭代关系式，指如何从变量的前一个值推出其下一个值的公式(或关系)。迭代关系式的建立是解决迭代问题的关键，通常可以使用递推或倒推的方法来完成。

对迭代过程进行控制 在什么时候结束迭代过程？这是编写迭代程序必须考虑的问题。不能让迭代过程无休止地执行下去。迭代过程的控制通常可分为两种情况：一种是所需的迭代次数是个确定的值，可以计算出来；另一种是所需的迭代次数无法确定。对于前一种情况，可以构建一个固定次数的循环来实现对迭代过程的控制；对于后一种情况，需要进一步分析得出可用来结束迭代过程的条件。

实例：

1. 欧几里德算法 辗转相除法

概念：

算法证明：

整理：

确定迭代变量 a，b

建立迭代关系式 gcd(a,b) = gcd(b,a mod b)， r = (参1)%(参2)

对迭代过程进行控制 条件 r = 0;结果为2参数 即为最大公约数。

2. 斐波那契数列

定义：

还有一个很典型的例子是斐波那契(Fibonacci)数列。斐波那契数列为：0、1、1、2、3、5、8、13、21、…，即 fib⑴=0; fib⑵=1;fib(n)=fib(n-1)+fib(n-2) (当n>2时)。

在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; i<=n; ++i)/*用i的值来限制迭代的次数*/

{

fn = f1 + f2; /*迭代关系式*/

f1 = f2;//f1和f2迭代前进，其中f2在f1的前面

f2 = fn;

}

return fn;

}

当然 斐波那契数列 得算法岂止一种。

参见 斐波那契数列