使用牛顿迭代法实现开*方

前言

牛顿迭代法（Newton's method）又称为牛顿-拉夫逊方法（Newton-Raphson method），它是牛顿在17世纪提出的一种在实数域和复数域上*似求解方程的方法。多数方程不存在求根公式，因此求精确根非常困难，甚至不可能，从而寻找方程的*似根就显得特别重要。方法使用函数f(x)的泰勒级数的前面几项来寻找方程f(x) = 0的根。牛顿迭代法是求方程根的重要方法之一，其最大优点是在方程f(x) = 0的单根附*具有*方收敛，而且该法还可以用来求方程的重根、复根。另外该方法广泛用于计算机编程中。

原理

比如求*方根： $x^2=78$ ，可以转为求 $x^2-78=0$ 这个方程的根
已知曲线方程 $f(x)$ ，我们在 $x_n$ 点做切线，求 $x_{n+1}$ ：

容易得出， $x_n$ 点的切线方程为： $f(x_n)+f'(x_n)(x-x_n)$ 。
要求 $x_{n+1}$ ，即相当于求 $f(x_n)+f'(x_n)(x-x_n)=0$ 的解，即 $f(x_n)+f'(x_n)(x_{n+1}-x_n)=0\implies$ ： $x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}$ 。
将f(x)=x²-c,f^`(x)=2x代入方程得到x=x-(x²-c)/2x=(x+c/x)/2

实现

public class Client {

  public static void main(String[] args) {
    System.out.println(Math.sqrt(10));
    System.out.println(sqrt(10));
    System.out.println(Math.sqrt(-10));
    System.out.println(sqrt(-10));
    System.out.println(Math.sqrt(0.000));
    System.out.println(sqrt(0));
    System.out.println(Math.sqrt(0.5));
    System.out.println(sqrt(0.5));
  }

  private static double sqrt(double n) {
    if (Double.isNaN(n) || n < 0) {
      return Double.NaN;
    }
    if (n == 0) {
      return n;
    }
    double k = 1.0;
    while (Math.abs(k * k - n) > 1e-5) {  //精度自己控制
      k = (k + n / k) / 2;
    }
    return k;
  }

}

得到的结果和java内置的sqrt方法结果一致。

参考

数学笔记9——牛顿迭代法
 如何通俗易懂地讲解牛顿迭代法求开方？数值分析？
sqrt函数分析