比較Python中的根函數（函數）算法

Question

我想比較不同的方法來尋找Python中函數的根（如牛頓的方法或其他簡單的基於計算的方法）。我認爲編寫算法不會有太多麻煩。什麼是進行實際比較的好方法？我讀了一下Big-O。這是否會走？

（任何項目的想法或曲折也不勝感激）

謝謝。

Answer 1

Big O notation非常適合將算法的漸近行爲表達爲算法「增加」的輸入。這可能不是查找算法的一個很好的方法。相反，我認爲將實際誤差降低到某個ε以下所需的迭代次數將是一個更好的衡量標準。另一個衡量標準是使連續迭代之間的差異小於某個εε所需的迭代次數。 （如果你的輸入沒有確切的根值，那麼連續迭代之間的差異可能是一個更好的選擇，你可以使用一個標準，如連續的差異來知道何時在實踐中終止你的根發現者，所以你可以或者應該在這裏使用他們。）

雖然你可以表徵由它們之間的比例不同的算法所需的迭代次數（一種算法可能需要大約10倍以上的迭代，以達到相同的精度另一個）隨着投入的變化，迭代中經常沒有「增長」。當然，如果你的算法需要更多的「更大」輸入迭代，那麼Big O符號就有意義了。

Answer 2

@sarnold的答案是正確的 - 做一個Big-Oh分析是沒有意義的。

求根算法之間的主要區別是：

• 收斂速度（迭代次數），每次迭代
• 計算工作量
• 什麼是需要輸入（即你需要知道的一階導數，您是否需要設置平分的高/低極限等）
• 它可以很好地工作的功能（即對多項式工作正常，但對帶極點的功能失效）
• 它對功能做了什麼假設（即連續一階導數或正在分析等）
• 的方法是如何實現簡單

我想你會發現，每一個方法都有一些很好的素質，一些壞的品質，和一組的情況下，這是最合適的選擇。

Answer 3

Big-O符號旨在描述當n趨於無窮時，alogorithm如何表現極限。在理論研究中這比在實際的實驗中更容易。我會選擇要學習的東西，以便您可以輕鬆地衡量這一點，以及人們關心的問題，例如精確度和計算機資源（時間/內存）消耗。

當你編寫並運行一個計算機程序來比較兩種算法時，你正在進行一個科學實驗，就像測量光速的某個人或者比較吸菸者和非吸菸者死亡率的人一樣同樣的因素適用。

嘗試並選擇一個或多個代表性問題來解決這個問題，或者至少對您很有意思，因爲您的結果可能不會推廣到您沒有實際測試過的場合。如果您從一大組可能出現的問題中隨機抽樣，並發現所有隨機樣本的行爲方式非常相似，或者至少遵循相同的趨勢，則您可以增加結果回覆的範圍。即使理論研究表明應該有一個很好的n log n趨勢，你也可能會有意想不到的結果，因爲理論研究很少說明突然用完了緩存，或者內存不足，或者通常甚至對於整數溢出等問題。

要警惕錯誤來源，儘量減少錯誤，或讓它們適用於所有比較事物。當然，您想要爲您正在測試的所有算法使用完全相同的輸入數據。對每個算法進行多次運行，並檢查變量是如何變化的 - 也許一些運行速度較慢，因爲計算機每次都在做其他事情。請注意，緩存可能會使算法的運行速度更快，特別是如果您立即運行它們。你想要什麼時間取決於你決定你測量的是什麼。如果你有很多的I/O需要記住，現代操作系統和計算機緩存內存中的大量磁盤I/O。每次運行後，我都會關閉計算機並重新啓動計算機，這是我唯一可以確定設備I/O高速緩存刷新的方法。

Answer 4

只需更改出發點，您就可以得到相同問題的截然不同的答案。選擇一個接近根的初始猜測，牛頓的方法會給你一個二次收斂的結果。在問題空間的不同部分選擇另一部分，根搜索器將大大發散。

這對於算法有何說法？是好是壞？

Answer 5

我建議你看看下面的Python根目錄演示。 這是一個簡單的代碼，它們之間有一些不同的方法和比較（就收斂速度而言）。

http://www.math-cs.gordon.edu/courses/mat342/python/findroot.py

Answer 6

何必呢？可以只有一個：

public class BrentsMethodResult 
    { 
     public bool TerminatedSuccessfully; 
     public double Result; 
     public double UpperResult; 
     public double LowerResult; 
    } 

    public static BrentsMethodResult BrentsMethodSolve(Func<double, double> function, double lowerLimit, double upperLimit, double errorTol) 
    { 
     BrentsMethodResult result = new BrentsMethodResult(); 

     double a = lowerLimit; 
     double b = upperLimit; 
     double c = 0; 
     double d = double.MaxValue; 

     double fa = function(a); 
     double fb = function(b); 
     result.LowerResult = fa; 
     result.UpperResult = fb; 

     if (Double.IsNaN(fa) || Double.IsNaN(fb)) 
     { 
      result.TerminatedSuccessfully = false; 
      result.Result = Double.NaN; 
      return result; 
     } 

     double fc = 0; 
     double s = 0; 
     double fs = 0; 

     // if f(a) f(b) >= 0 then error-exit 
     if (fa * fb >= 0) 
     { 
      result.TerminatedSuccessfully = false; 
      if (Math.Abs(fa) < Math.Abs(fb)) 
      { 
       result.Result = a; 
       return result; 
      } 
      else 
      { 
       result.Result = b; 
       return result; 
      } 
     } 

     // if |f(a)| < |f(b)| then swap (a,b) end if 
     if (Math.Abs(fa) < Math.Abs(fb)) 
     { double tmp = a; a = b; b = tmp; tmp = fa; fa = fb; fb = tmp; } 

     c = a; 
     fc = fa; 
     bool mflag = true; 
     int i = 0; 

     while (Math.Abs(fb) > errorTol && Math.Abs(a - b) > errorTol) 
     { 
      //tol1 = 2.0 * double_Accuracy * Math.Abs(b) + 0.5 * errorTol; 

      if ((fa != fc) && (fb != fc)) 
       // Inverse quadratic interpolation 
       s = a * fb * fc/(fa - fb)/(fa - fc) + b * fa * fc/(fb - fa)/(fb - fc) + c * fa * fb/(fc - fa)/(fc - fb); 
      else 
       // Secant Rule 
       s = b - fb * (b - a)/(fb - fa); 

      double tmp2 = (3 * a + b)/4; 
      if ((!(((s > tmp2) && (s < b)) || ((s < tmp2) && (s > b)))) || (mflag && (Math.Abs(s - b) >= (Math.Abs(b - c)/2))) || (!mflag && (Math.Abs(s - b) >= (Math.Abs(c - d)/2)))) 
      { 
       s = (a + b)/2; 
       mflag = true; 
      } 
      else 
      { 
       if ((mflag && (Math.Abs(b - c) < errorTol)) || (!mflag && (Math.Abs(c - d) < errorTol))) 
       { 
        s = (a + b)/2; 
        mflag = true; 
       } 
       else 
        mflag = false; 
      } 
      fs = function(s); 

      if (Double.IsNaN(fs)) 
      { 
       result.TerminatedSuccessfully = false; 
       result.Result = Double.NaN; 
       return result; 
      } 

      d = c; 
      c = b; 
      fc = fb; 
      if (fa * fs < 0) { b = s; fb = fs; } 
      else { a = s; fa = fs; } 

      // if |f(a)| < |f(b)| then swap (a,b) end if 
      if (Math.Abs(fa) < Math.Abs(fb)) 
      { double tmp = a; a = b; b = tmp; tmp = fa; fa = fb; fb = tmp; } 
      i++; 
      if (i > 100) 
      { 
       throw new Exception(String.Format("100 iterations exceeded and error is {0}", fb)); 
      } 
     } 
     result.TerminatedSuccessfully = true; 
     result.Result = b; 
     return result; 
    } 

Answer 7

我剛剛完成了一個項目，比較二等分，牛頓和割線根發現方法。既然這是一個實際案例，我認爲你不需要使用Big-O符號。 Big-O符號更適合漸近觀點。你可以做的是長期對它們進行比較：

速度 - 例如這裏牛頓迭代的速度最快的，如果良好的條件都聚集

數量 - 例如這裏平分採取最迭代

精度 - 如果存在多個根，或者甚至根本不會收斂，它會多頻繁地收斂到正確的根。

輸入 - 需要什麼信息才能開始。例如牛頓爲了收斂需要靠近根的X0，它還需要一個不容易找到的一階導數。

其他 - 舍入誤差

對於可視化的緣故，你可以存儲每個迭代的數組中的值，並繪製出來。使用你已經知道根源的函數。