机器学习|二分法迭代求零点

01

—

二分法求解

对于区间 [a，b] 上单调连续，且 f（a）· f（b）< 0 的函数 y = f（x），通过不断地把函数 f（x）的零点所在的区间一分为二，使区间的两个端点逐步逼近零点（1个解），进而得到零点近似值的方法叫二分法。

02

—

二分求解思路

这种方法的局限性：如上，二分求解，给定的初始区间 [a,b]，必须要满足 f（a）· f（b）< 0 ，并且这种方法只能找到一个单根。

二分求解最重要是的找出缩小区间的条件。

二分区间[a,b]， 得到区间的中间点：mid = a + (b-a)/2.0；

如果 f（mid）· f（b）< 0 ，则可以缩小区间，a = mid；

如果 f（a）· f（mid）< 0 ，则可以缩小区间，b = mid；

如果 f(mid) < threshold，则认为 mid 就是方程的根；

03

—

python代码

""" bisection to find solve to f(x) when x in (a,b) and f(a)*f(b)<0 """ def biSection(a,b,threshold,f): iter=0 while a<b: mid = a + abs(b-a)/2.0 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 = biSection(5, 50,1e-10, lambda x: x*x-11*x+10 ) print("solve= "+str(s))

下面是迭代求解的过程，经过38次迭代，最终得到解。

1 a= 5, b= 27.5 2 a= 5, b= 16.25 3 a= 5, b= 10.625 4 a= 7.8125, b= 10.625 5 a= 9.21875, b= 10.625 6 a= 9.921875, b= 10.625 7 a= 9.921875, b= 10.2734375 8 a= 9.921875, b= 10.09765625 9 a= 9.921875, b= 10.009765625 10 a= 9.9658203125, b= 10.009765625 11 a= 9.98779296875, b= 10.009765625 12 a= 9.998779296875, b= 10.009765625 13 a= 9.998779296875, b= 10.0042724609375 14 a= 9.998779296875, b= 10.00152587890625 15 a= 9.998779296875, b= 10.000152587890625 16 a= 9.999465942382812, b= 10.000152587890625 17 a= 9.999809265136719, b= 10.000152587890625 18 a= 9.999980926513672, b= 10.000152587890625 19 a= 9.999980926513672, b= 10.000066757202148 20 a= 9.999980926513672, b= 10.00002384185791 21 a= 9.999980926513672, b= 10.000002384185791 22 a= 9.999991655349731, b= 10.000002384185791 23 a= 9.999997019767761, b= 10.000002384185791 24 a= 9.999999701976776, b= 10.000002384185791 25 a= 9.999999701976776, b= 10.000001043081284 26 a= 9.999999701976776, b= 10.00000037252903 27 a= 9.999999701976776, b= 10.000000037252903 28 a= 9.99999986961484, b= 10.000000037252903 29 a= 9.999999953433871, b= 10.000000037252903 30 a= 9.999999995343387, b= 10.000000037252903 31 a= 9.999999995343387, b= 10.000000016298145 32 a= 9.999999995343387, b= 10.000000005820766 33 a= 9.999999995343387, b= 10.000000000582077 34 a= 9.999999997962732, b= 10.000000000582077 35 a= 9.999999999272404, b= 10.000000000582077 36 a= 9.99999999992724, b= 10.000000000582077 37 a= 9.99999999992724, b= 10.000000000254659 38 a= 9.99999999992724, b= 10.00000000009095

得到方程在区间(5,50)的解： 10.000000000009095