牛顿迭代法

牛顿迭代法的介绍

牛顿迭代法（Newton’s method）又称为牛顿-拉弗森方法（Newton-Raphson method），是一种在实数域和复数域上近似求解方程的方法。多数方程不存在求根公式，因此求其精确根非常困难，甚至不可能，因此，寻找方程的近似根就显得特别重要。

牛顿迭代公式的推导方法一

牛顿法使用函数$f(x)$的泰勒展开式的前面几项来寻找方程$f(x)=0$的根。对于一个函数$f(x)$，它的泰勒展开式如下：

$f(x)=f(x_0)+f^′(x_0)(x−x_0)+\frac{1}{2}f^{′′}(x_0)(x−x_0)^2+\dots+\frac{1}{n!}f^n(x_0)(x−x_0)^n,$

我们使用其前两项来近似表示这个函数，即用$\theta(x)$代替$f(x)$：

$\theta(x)=f(x_0)+f^′(x_0)(x-x_0),$

令$\theta(x)=0$，则$x=x_0-\frac{f(x_0)}{f^′(x_0)}$，所以，牛顿法的迭代公式就是：

$x_{n+1}=x_n-\frac{f(x_n)}{f^′(x_n)}.$

牛顿迭代公式的推导方法二

• 有同学可能要说了，这个泰勒展开式我记不住咋办？有没有别的方法呢？
• 别慌，当然有 ————

设$r$是函数$f(x)=0$的根，我们不知道它是多少，现在需要用牛顿法近似求解$r$。

1、我们首先取一个$r$的初始近似值$x_0$，过点$(x_0, f(x_0))$作函数$f(x)$的切线$L_1$，设

$L_1:y=kx+b,$

其中斜率$k$就是函数$f(x)$在$x_0$点处的导数，即：

$k=f^′(x_0),$

将点$(x_0, f(x_0))$代入$L_1$可得：

$b=f(x_0)-f^′(x_0)x_0,$

因此切线$L_1$：

$y=f(x_0)+f^′(x_0)(x-x_0),$

2、接着我们可以求出$L_1$与$x$轴的交点的横坐标$x_1$，令$y=0$即可得：

$x_1=x_0-\frac{f(x_0)}{f^′(x_0)},$

我们称$x_1$为$r$的一次近似值。
3、同理，我们过点$(x_1, f(x_1))$作函数$f(x)$的切线$L_2$，并求该切线与$x$轴的交点的横坐标：

$x_2=x_1-\frac{f(x_1)}{f^′(x_1)},$

称$x_2$为$r$的二次近似值。
4、重复以上过程，可得到$r$的n+1次近似值，也就是牛顿迭代公式：

$x_{n+1}=x_n-\frac{f(x_n)}{f^′(x_n)}.$

牛顿迭代公式的形象理解

• ①、随机选一个初始值$x_1$，进行一次迭代，寻找到$x_2$
  
• ②、$x_2 \Rightarrow x_3$
  
• ③、$x_3 \Rightarrow x_4$
  
• ④、$x_4 \Rightarrow x_5$
  
• ⑤、不断迭代，直到收敛，此时$x_n$即为方程$f(x)=0$的根

牛顿迭代法的应用

x的平方根

题目来源：Leetcode
题目链接：Leetcode-69
题目描述：

实现 int sqrt(int x) 函数。
计算并返回 x 的平方根，其中 x 是非负整数。
由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

示例 1:

输入: 4
输出: 2

示例 2:

输入: 8
输出: 2

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

解题思路

为了避免与$f(x)$中的$x$混淆，我们将题目中x的平方根记为m的平方根

• 明确目标：m的平方根是我们所要求的东西，因此若将这个问题套用到牛顿迭代法上，就是要找到一个函数$f(x)$，使得这个函数的根为$\sqrt{m}$
• 寻找目标函数：考虑函数$f(x)=x^2-m$，其满足$f(\sqrt{m})=\sqrt{m}^2-m=0$，可以作为我们的目标函数。
• 推导迭代公式：将函数 $f(x)=x^2-m$ 和其导数 $f^′(x)=2x$ 代入牛顿迭代公式$x_{n+1}=x_n-\frac{f(x_n)}{f^′(x_n)}$中即可得到：

$x_{n+1}=\frac{1}{2}(x_n+\frac{m}{x_n}).$

• 开始迭代：选定初始值$x_0$，可以为任意数字，不同的初始值只会影响收敛的快慢，最终都会收敛于方程$f(x)=0$的根。此处默认设$x_0=m$，不断迭代，直到收敛。

python

class Solution(object):
    def mySqrt(self, m):
        """
        :type m: int
        :rtype: int
        """
        if(m <= 1):
            return m
        
        sqrt = m
        while(sqrt > m / sqrt):
            sqrt = (sqrt + m / sqrt) // 2
        
        return sqrt