使用牛顿迭代法计算平方根

使用牛顿迭代法计算平方根

算法第四版 1.1.6.1提到一个计算方法，代码如下:

public static double sqrt(double c)
{
	if(c < 0) return Double.NaN;
	double err = 1e-15;
	while(Math.abs(t - c/t) > err * t)
		t = (t + c/t) / 2.0;
	return t;
}

公式简单推导

x² = c， f(x) = x² - c , f^'(x) = 2 * x

err是误差的精度

x_k+1 = x_k - f(x_k) / f^'(x_k) = x_k - (x_k² - c) / (2x_k) = 1/2 * (x_k + c / x_k)

结束条件

|t - c / t| <= err * t

<= |1 - c / t ²| <= err,即t²和c的值接近的程度满足误差要求