【Machine Learning】二分法/牛顿迭代求零点

骑猪看日落 2021-10-30 01:08 619阅读 0赞

### 文章目录 ###

*  一、前言
 *  二、何为二分法
 *   *  2.1 具体实现
     *   *  2.1.1 经典算法
         *  2.1.2 求法
 *  三、What is 牛顿迭代法
 *   *  3.1 背景了解
     *  3.2 产生背景
     *  3.3 牛顿迭代公式
     *  3.4 源码实现(python)
 *  四、源码获取

# 一、前言 #

在此博文之前，已经学习了[关于机器学习的基本概念][Link 1]以及涉及到的一些[常用的数学相关知识][Link 2]。而在机器学习中，涉及到最为重要的一个学科就是数学，本篇博文较为简单，重在利用python实现二分法/牛顿迭代求去零点。

# 二、何为二分法 #

来源百度： 对于区间 \[ a ， b \] \[a，b\] \[a，b\]上连续不断且 f ( a ) ⋅ f ( b < 0 ) f(a)·f(b<0) f(a)⋅f(b<0)的函数 y = f ( x ) y=f(x) y=f(x)，通过不断地把函数 f ( x ) f(x) f(x)的零点所在的区间一分为二，使区间的两个端点逐步逼近零点，进而得到零点近似值的方法叫二分法。

## 2.1 具体实现 ##

### 2.1.1 经典算法 ###

算法：当数据量很大适宜采用该方法。采用二分法查找时，数据需是排好序的。  
基本思想：  
假设数据是按升序排序的，对于给定值 k e y key key，从序列的中间位置 k k k开始比较，  
如果当前位置 a r r \[ k \] arr\[k\] arr\[k\]值等于 k e y key key，则查找成功；  
若 k e y key key小于当前位置值 a r r \[ k \] arr\[k\] arr\[k\]，则在数列的前半段中查找 a r r \[ l o w , m i d − 1 \] arr\[low,mid-1\] arr\[low,mid−1\]；  
若 k e y key key大于当前位置值 a r r \[ k \] arr\[k\] arr\[k\]，则在数列的后半段中继续查找 a r r \[ m i d + 1 , h i g h \] arr\[mid+1,high\] arr\[mid\+1,high\]，  
直到找到为止,时间复杂度: O ( l o g ( n ) ) O(log(n)) O(log(n)) 。

### 2.1.2 求法 ###

给定精确度 ξ ξ ξ，用二分法求函数 f ( x ) f(x) f(x)零点近似值的步骤如下:

1.  确定区间 \[ a , b \] \[a,b\] \[a,b\],验证 f ( a ) ⋅ f ( b ) < 0 f(a)·f(b)<0 f(a)⋅f(b)<0,给定精确度 ξ ξ ξ。
2.  求区间 ( a , b ) (a,b) (a,b)的中点 c c c。
3.  计算 f ( m i d ) f(mid) f(mid)。  
    (1) 若 f ( m i d ) = 0 f(mid)=0 f(mid)=0,则 m i d mid mid就是函数的零点;  
    (2) 若 f ( a ) ⋅ f ( m i d ) < 0 f(a)·f(mid)<0 f(a)⋅f(mid)<0,则令 b = m i d b=mid b=mid;  
    (3) 若 f ( m i d ) ⋅ f ( b ) < 0 f(mid)·f(b)<0 f(mid)⋅f(b)<0,则令 a = m i d a=mid a=mid。  
    (4) 判断是否达到精确度 ξ ξ ξ:即若 ∣ a − b ∣ < ξ |a-b|<ξ ∣a−b∣<ξ,则得到零点近似值 a ( 或 b ) a(或b) a(或b),否则重复(2)-(4).

""" author:jjk datetime:2019/5/2 coding:utf-8 project name:Pycharm_workstation Program function: """
    def diSection(a,b,threshold,f):
        iter = 0
        while a < b:
            mid = a + abs(b-a)/2.0 # 求a b的中点
            if abs(f(mid)) < threshold:
                return mid
            if f(mid)*f(b) <0:
                a = mid
            if f(a)*f(mid) <0:
                b= mid
            iter+=1
            print(str(iter)+"a="+str(a)+",b="+str(b))
    
    a = 5
    b = 50
    threshold = 1e-10
    # f(x) = x*x-11*x+10,此方程的解：1,10，因此在（5,50）的解是10
    # 调用函数，用于二分法求解
    s = diSection(5,50,1e-10,lambda x:x*x-11*x+10)
    print("result="+str(s))

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ppYWppa2FuZ19qams_size_16_color_FFFFFF_t_70]

# 三、What is 牛顿迭代法 #

## 3.1 背景了解 ##

百度介绍：牛顿迭代法（Newton’s method）又称为牛顿-拉夫逊（拉弗森）方法（Newton-Raphson method），它是牛顿在17世纪提出的一种在实数域和复数域上近似求解方程的方法。

## 3.2 产生背景 ##

百度介绍：多数方程不存在求根公式，因此求精确根非常困难，甚至不可能，从而寻找方程的近似根就显得特别重要。方法使用函数 f ( x ) f(x) f(x)的泰勒级数的前面几项来寻找方程 f ( x ) = 0 f(x)=0 f(x)=0的根。牛顿迭代法是求方程根的重要方法之一，其最大优点是在方程 f ( x ) = 0 f(x)=0 f(x)=0的单根附近具有平方收敛，而且该法还可以用来求方程的重根、复根，此时线性收敛，但是可通过一些方法变成超线性收敛。另外该方法广泛用于计算机编程中。

## 3.3 牛顿迭代公式 ##

设 r r r是 f ( x ) = 0 f(x)=0 f(x)=0的根，选取 x 0 x\_0 x0作为 r r r 的初始近似值，过点 ( x 0 , f ( x 0 ) ) (x\_0,f(x\_0)) (x0,f(x0))做曲线 y = f ( x ) y=f(x) y=f(x)的切线 L L L ， L : y = f ( x 0 ) + f ′ ( x 0 ) ( x − x 0 ) L : y=f\\left(x\_\{0\}\\right)+f^\{\\prime\}\\left(x\_\{0\}\\right)\\left(x-x\_\{0\}\\right) L:y=f(x0)\+f′(x0)(x−x0)，则 L L L与 x x x轴交点的横坐标 x 1 = x 0 − f ( x 0 ) f ′ ( x 0 ) x\_\{1\}=x\_\{0\}-\\frac\{f\\left(x\_\{0\}\\right)\}\{f^\{\\prime\}\\left(x\_\{0\}\\right)\} x1=x0−f′(x0)f(x0)，称 x 1 x\_\{1\} x1为 r r r的一次近似值。过点 ( x 1 , f ( x 1 ) ) \\left(x\_\{1\}, f\\left(x\_\{1\}\\right)\\right) (x1,f(x1))做曲线 y = f ( x ) y=f(x) y=f(x)的切线，并求该切线与 x x x轴交点的横坐标 x 2 = x 1 − f ( x 1 ) f ′ ( x 1 ) x\_\{2\}=x\_\{1\}-\\frac\{f\\left(x\_\{1\}\\right)\}\{f^\{\\prime\}\\left(x\_\{1\}\\right)\} x2=x1−f′(x1)f(x1)，称 x 2 x\_\{2\} x2为 r r r的二次近似值。重复以上过程，得 r r r的近似值序列，其中 x n + 1 = x n − f ( x n ) f ′ ( x n ) x\_\{n+1\}=x\_\{n\}-\\frac\{f\\left(x\_\{n\}\\right)\}\{f^\{\\prime\}\\left(x\_\{n\}\\right)\} xn\+1=xn−f′(xn)f(xn)， 称为 r r r的 n + 1 n+1 n\+1次近似值，上式称为牛顿迭代公式。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ppYWppa2FuZ19qams_size_16_color_FFFFFF_t_70 1]  
       用牛顿迭代法解非线性方程，是把非线性方程 f ( x ) = 0 f(x)=0 f(x)=0线性化的一种近似方法。把 f ( x ) f(x) f(x)点 x 0 x\_0 x0的某邻域内展开成泰勒级数 f ( x ) = f ( x 0 ) + f ′ ( x 0 ) ( x − x 0 ) + f ′ ′ ( x 0 ) ( x − x 0 ) 2 2 ! + ⋯ + f ( n ) ( x 0 ) ( x − x 0 ) n n ! + R n ( x ) f(x)=f\\left(x\_\{0\}\\right)+f^\{\\prime\}\\left(x\_\{0\}\\right)\\left(x-x\_\{0\}\\right)+\\frac\{f^\{\\prime \\prime\}\\left(x\_\{0\}\\right)\\left(x-x\_\{0\}\\right)^\{2\}\}\{2 !\}+\\dots+\\frac\{f^\{(n)\}\\left(x\_\{0\}\\right)\\left(x-x\_\{0\}\\right)^\{n\}\}\{n !\}+R\_\{n\}(x) f(x)=f(x0)\+f′(x0)(x−x0)\+2!f′′(x0)(x−x0)2\+⋯\+n!f(n)(x0)(x−x0)n\+Rn(x)，取其线性部分（即泰勒展开的前两项），并令其等于0，即 f ( x 0 ) + f ′ ( x 0 ) ( x − x 0 ) = 0 f\\left(x\_\{0\}\\right)+f^\{\\prime\}\\left(x\_\{0\}\\right)\\left(x-x\_\{0\}\\right)=0 f(x0)\+f′(x0)(x−x0)=0，以此作为非线性方程 f ( x ) = 0 f(x)=0 f(x)=0的近似方程，若 f ′ ( x 0 ) ≠ 0 f^\{\\prime\}\\left(x\_\{0\}\\right) \\neq 0 f′(x0)̸=0，则其解为 x 1 = x 0 − f ( x 0 ) f ′ ( x 0 ) x\_\{1\}=x\_\{0\}-\\frac\{f\\left(x\_\{0\}\\right)\}\{f^\{\\prime\}\\left(x\_\{0\}\\right)\} x1=x0−f′(x0)f(x0)， 这样，得到牛顿迭代法的一个迭代关系式：  x n + 1 = x n − f ( x n ) f ′ ( x n ) x\_\{n+1\}=x\_\{n\}-\\frac\{f\\left(x\_\{n\}\\right)\}\{f^\{\\prime\}\\left(x\_\{n\}\\right)\} xn\+1=xn−f′(xn)f(xn) 。

已经证明，如果是连续的，并且待求的零点是孤立的，那么在零点周围存在一个区域，只要初始值位于这个邻近区域内，那么牛顿法必定收敛。 并且，如果不为0, 那么牛顿法将具有平方收敛的性能. 粗略的说，这意味着每迭代一次，牛顿法结果的有效数字将增加一倍。迭代法也称辗转法，是一种不断用变量的旧值递推新值的过程，跟迭代法相对应的是直接法（或者称为一次解法），即一次性解决问题。迭代算法是用计算机解决问题的一种基本方法。它利用计算机运算速度快、适合做重复性操作的特点，让计算机对一组指令（或一定步骤）重复执行，在每次执行这组指令（或这些步骤）时，都从变量的原值推出它的一个新值。

具体可参考：[百度描述][Link 3]

## 3.4 源码实现(python) ##

""" author:jjk datetime:2019/5/2 coding:utf-8 project name:Pycharm_workstation Program function: """
    def newton(x0,niter,threshold,f,fgrad):
        iter = 0 # 记录每次迭代过程标记符
        while niter>0:
            x1 = x0-f(x0)/fgrad(x0) # 获取一次近似值
            if f(x1)<threshold:
                break
            x0 = x1# 循环求解二次近似值
            iter+=1
            print(str(iter)+" x= "+str(x1)) # 打印每次迭代结果
            niter-=1
        return x1
    
    # x0 = 50
    # niter = 100
    # threshold=1e-10
    # f(x) = x*x-11*x+10, 这个方程的解： 1，10
    # f1(x) = 2*x-11 表示一阶导数
    s = newton(50,100,1e-10,lambda x:x*x-11*x+10,lambda x:2*x-11)

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ppYWppa2FuZ19qams_size_16_color_FFFFFF_t_70 2]

# 四、源码获取 #

[https://github.com/jiajikang1993/NLP\_related\_algorithm\_learned/tree/master/Machine%20Learning(ML)][https_github.com_jiajikang1993_NLP_related_algorithm_learned_tree_master_Machine_20Learning_ML]

[Link 1]: https://blog.csdn.net/Jiajikang_jjk/article/details/99705122
[Link 2]: https://blog.csdn.net/Jiajikang_jjk/article/details/99706496
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ppYWppa2FuZ19qams_size_16_color_FFFFFF_t_70]: /images/20211029/935b7a1ccb0a46f39215a4fdc7e29b73.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ppYWppa2FuZ19qams_size_16_color_FFFFFF_t_70 1]: /images/20211029/84e8a29aeb984d14968108195f693740.png
[Link 3]: https://baike.baidu.com/item/%E7%89%9B%E9%A1%BF%E8%BF%AD%E4%BB%A3%E6%B3%95?fromtitle=%E7%89%9B%E9%A1%BF%E6%B3%95&fromid=1384129
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ppYWppa2FuZ19qams_size_16_color_FFFFFF_t_70 2]: /images/20211029/4487d68396434e76bfc1b4d1f101141b.png
[https_github.com_jiajikang1993_NLP_related_algorithm_learned_tree_master_Machine_20Learning_ML]: https://github.com/jiajikang1993/NLP_related_algorithm_learned/tree/master/Machine%20Learning%28ML%29