理解使用二分法找到解決方案的迭代次數

Question

我被要求使用Bisection方法找到方程的根，並且Python 3中只有for循環。This線程顯示如何使用該方法，但不能與range()中的數字解釋。

作爲一個例子，我有功能

F（X）= X - 2 * X - 3

和我想找到它的負根，從區間[-4,1]。

我設法用for循環編寫函數，但我不明白我應該使用哪個範圍，或者如何設計它。

這是我的代碼，解決該問題：

... 
a = -4 
b = 1 
c = (a + b)/2 

for i in range(1000): 
    if f(c) == 0: 
     break 
    if f(a) * f(c) < 0: 
     b = c 
    elif f(a) * f(c) > 0: 
     a = c 
    c = (a + b)/2 

return c, f(c), i 

C = -1（中發現的負根）中，f（C）= 0確認程序工作，且i = 52指示經過二十二分之一秒的「嘗試」後，找到了正確的答案。

我在range()中放了一個非常大的數字來確保我找到了根，但爲什麼它只需要52次迭代？

另外，如果我的間隔更改爲[-2,1]，則需要53次嘗試。 這是爲什麼？

Answer 1

如果print([a, b])在循環中，你可以看到的範圍內演變：

[-4, 1] 
[-1.5, 1] 
[-1.5, -0.25] 
[-1.5, -0.875] 
[-1.1875, -0.875] 
[-1.03125, -0.875] 
... 
... 
... 
[-1.0000000000000284, -0.9999999999999929] 
[-1.0000000000000107, -0.9999999999999929] 
[-1.0000000000000018, -0.9999999999999929] 
[-1.0000000000000018, -0.9999999999999973] 
[-1.0000000000000018, -0.9999999999999996] 
[-1.0000000000000007, -0.9999999999999996] 

的-1.0000000000000007和-0.9999999999999996計算的平均值正好是-1。爲什麼？因爲你已經達到了浮點數可以表示的極限。這裏所涉及的確切值：

>>> '%.60f' % -1.0000000000000007 
'-1.000000000000000666133814775093924254179000854492187500000000' 

>>> '%.60f' % -0.9999999999999996 
'-0.999999999999999555910790149937383830547332763671875000000000' 

>>> '%.60f' % (-1.0000000000000007 + -0.9999999999999996) 
'-2.000000000000000000000000000000000000000000000000000000000000' 

>>> '%.60f' % ((-1.0000000000000007 + -0.9999999999999996)/2) 
'-1.000000000000000000000000000000000000000000000000000000000000' 

花車店52 bits of fraction，領先1位後，意味着52位。這意味着你失去了小於你的價值的大約1/2 。經過52個步驟後，您的初始尺寸爲5的尺寸約爲5/2 。這就是你的價值-1的1/2 。因此，在那裏，由於不精確性，你很可能會偶然發現-1。

它可能需要兩個或更多三個步驟，因爲5/2 仍然大於1/2 。你在那裏很幸運。與你的其他初始範圍[-2, 1]你只是沒有幸運。在你達到-1之前，你的範圍縮小到[-1.0000000000000002, -0.9999999999999999]。

如果您從[-4000000, 1]開始，那麼您需要72步。它多20步，因爲初始範圍是百萬倍大，約爲2 。

另一種情況：如果您使用功能x**2 - 1000000和初始範圍[999.3, 1000.3]，則需要41個步驟。爲什麼？最終值（即根）爲1000，初始範圍爲1，即1/1000，因此大約爲1/2 。所以要到1/2 你只需要大約42個二等分。

Answer 2

每次迭代時，都將搜索間隔減半。在每次迭代中，檢查f（c）（中點處的函數值）是否爲0，在計算機浮點表示的準確度範圍內。

如果要選擇區間[-101，99]，只需要1次迭代就可以得到解決方案，就像當你點擊c = -1時一樣。程序將停止，只要它足夠接近評估出現的實際根目錄0.000000

您以寬度範圍5開始。什麼是5除以2，52次？實現中的浮點數的準確度是多少？我敢打賭，你接近兩個花車之間的最小差距。

如果你真的想看到這個動作，加上內環路一條簡單的直線，右頂部：

print a, b, c, f(c) 

這將顯示您找到根的進展。

print聲明是追蹤程序的一種低技術含量的有效方法。

COMMENT響應

好一點：我沒有叫出來的特殊情況夠硬。

你完成了52次迭代，因爲這是程序在適當的值「絆倒」所花費的時間。當你改變了53次迭代並以更小的範圍進行時......簡單的方法就是說你第一次有點幸運。正如我指出的那樣，如果你從以-1爲中點的東西開始，比如[-101，99]，那麼儘管間隔要大得多，你只需要完成一次迭代。