0%

牛顿迭代法求平方根

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

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

double y;
double k;
for (unsigned int i = 0; i < iterations; ++i)
{
y = approximation * approximation - input;
k = 2 * approximation;
approximation = -y / k + approximation;
//approximation = -(approximation * approximation - input) / (2 * approximation) + approximation;
}
return approximation;
}

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