牛顿迭代法求平方根

发表于 2018 年 1 月 31 日

牛顿法可以求一些非线性方程的近似解. 而对于求平方根,  可以将 $y = \sqrt{x}$ 化成方程 $x^2 - a = 0$ 中求 $x$ 的值, $x$ 即为 $a$ 的开根号, 根据牛顿法定义, 可以写出以下程序

 1double mysqrt(const double input, double approximation = 1, unsigned int iterations = 8)
 2{
 3	if (input < 0 || approximation <= 0)
 4	{
 5		throw std::runtime_error("Input and approximation should bigger than zero.");
 6	}
 7
 8	double y;
 9	double k;
10	for (unsigned int i = 0; i < iterations; ++i)
11	{	
12		y = approximation * approximation - input;
13		k = 2 * approximation;
14		approximation = -y / k + approximation;	
15		//approximation = -(approximation * approximation - input) / (2 * approximation) + approximation;
16	}
17        return approximation;
18}

画成图差不多这样, 是一个不断迭代, 精度越来越高的过程.
实际运行的结果, 在迭了8代的情况, 已经差不多已经到double类型的极限了.