牛顿迭达法

多数方程不存在求根公式，因此求精确根非常困难，甚至不可能，从而寻找方程的近似根就显得特别重要，牛顿迭达法就是一种有效的求近似根的方法。

一、问题引入

##实现 int sqrt(int x) 函数。

  计算并返回 x 的平方根，其中 x 是非负整数。

  由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

示例 1:

输入: 4

输出: 2

示例 2:

输入: 8

输出: 2

  说明: 8 的平方根是 2.82842…, 由于返回类型是整数，小数部分将被舍去

---

###此处要求算的是一个数的平方根，所以我们可以很合理的考虑使用牛顿迭达法（也称牛顿法或牛顿-拉夫森法）

###一、牛顿法的基本思想：

  通过迭代来实现，每次运算都让结果比之前好一点。

  哪怕只好一点点，在很多次迭代之后也可以得到一个很好的结果甚至最优或期望的结果。

###二、牛顿法的目的：

  牛顿法就是通过使原方程泰勒展开的一阶近似等于零不断获得更好的结果的求解方程零点的方法。

###三、牛顿迭达法的详解

• 牛顿法是求解方程零点的方法

• 牛顿法利用泰勒展开的一阶近似的零点获得更接近真实零点的点

• 牛顿法通过迭代的方法不断的获得更好的解来求得最好的解


####

具体的图像如下所示：


  图中最右边点为原来猜想的点，然后经过迭达后得到左边的橙色点，这样子逐步逼近到零点。

####  当然对于这个公式还有个问题，为什么是一阶导而不是二阶导或者三阶导呢？

第一是一阶导已经能够满足我们的需求了；

第二就是二阶导三阶导不一定存在，而且就算存在计算也会比较麻烦。

###  好了，现在我们已经熟悉牛顿迭达法的原理了，那么解决上述问题就是轻而易举地事情，具体的代码如下：

class Solution {
      int s;  
      public int mySqrt(int x) {
      s=x;
      if(x==0) return 0;
      return ((int)(sqrts(x)));
      }

public double sqrts(double x){
      double res = (x + s / x) / 2;
      if (res == x) {
          return x;
      } else {
          return sqrts(res);
      }
   } 
}

  根据牛顿迭达法我们知道 ****x−f(x)/(2x)****就是一个比x更准确的的近似值，此处将 f(x)=x^2-a 代入到上述的公式中就得到x−(x^2−a)/(2x)，也就是(x+a/x)/2,(上述的a就是我们要求平方根的2)，循环的结束条件就是我们通过牛顿迭达法得到的值res已经达到稳定了（或者说不再发生变化了）。

参考博客：牛顿法及牛顿法求解优化问题