牛顿迭代法：介绍、原理与运用

介绍

牛顿迭代法是一个可以求一个任意函数的零点的工具。它比二分法快得多。

公式是：x=a-f(a)/f‘(a)。其中a是猜测值，x是新的猜测值。不断迭代，f(x)就越来越接近0。

原理

我们将f(x)做泰勒一阶展开：f(x)∼f(a)+(x-a)f‘(a)。

令f(x)=0，
∴f(a)+(x-a)f‘(a) = 0
∴f(a)+xf‘(a)-af‘(a) = 0
∴xf‘(a)=af‘(a)-f(a)
∴x=a-f(a)/f‘(a)

实例：牛顿迭代法求√2的近似值

令f(x)=方程左边，则f(x)∼0↔x∼√2。

f‘(x) = 2x。于是可以得到迭代公式：

代码如下（要求误差小于1e^-6）：

#include <stdio.h>
#include <math.h>

int main(int argc, char const *argv[])
{
	double a = 2.0;
	double expect_error = 0.000001;
	double expect_answer = 1.4142135623731;
	double x;
	double actual_error;
	unsigned iteration_count = 0;

	do {
		if (a == 0.0) a = 0.1; /* 避免除0 */
		x = a/2 + 1/a;
		actual_error = fabs(expect_answer - x);
		a = x;

		++iteration_count;
		printf("%d\t%.9f\t%.9f\n", iteration_count, a, actual_error);
	} while (actual_error >= expect_error);

	printf("%d\n", iteration_count);

	return 0;
}

输出：

1	1.500000000	0.085786438
2	1.416666667	0.002453104
3	1.414215686	0.000002124
4	1.414213562	0.000000000
4

迭代了4次。用二分法呢？

#include <stdio.h>
#include <math.h>

int main(int argc, char const *argv[])
{
	double high = 2.0;
	double low = 1.0;
	double expect_error = 0.000001;
	double expect_answer = 1.4142135623731;
	double x;
	double actual_error;
	unsigned iteration_count = 0;

	do {
		x = (high+low)/2;

		if (x*x-2 > 0)
			high = x;
		else
			low = x;

		actual_error = fabs(expect_answer - x);

		++iteration_count;
		printf("%d\t%.9f\t%.9f\n", iteration_count, x, actual_error);
	} while (actual_error >= expect_error);

	printf("%d\n", iteration_count);

	return 0;
}

输出：

1	1.500000000	0.085786438
2	1.250000000	0.164213562
3	1.375000000	0.039213562
4	1.437500000	0.023286438
5	1.406250000	0.007963562
6	1.421875000	0.007661438
7	1.414062500	0.000151062
8	1.417968750	0.003755188
9	1.416015625	0.001802063
10	1.415039062	0.000825500
11	1.414550781	0.000337219
12	1.414306641	0.000093078
13	1.414184570	0.000028992
14	1.414245605	0.000032043
15	1.414215088	0.000001526
16	1.414199829	0.000013733
17	1.414207458	0.000006104
18	1.414211273	0.000002289
19	1.414213181	0.000000382
19

迭代了19次。

牛顿迭代法：介绍、原理与运用

原文：http://www.cnblogs.com/destro/p/newton-s-method.html