什麼是牛頓 - 拉夫遜方法的時間複雜性？

Question

牛頓 - 拉夫遜方法的時間複雜度是多少？

• Wikipedia: Newton's method

Answer 1

從http://en.citizendium.org/wiki/Newton%27s_method#Computational_complexity：

使用牛頓法如上所述 ，的 時間複雜度計算函數f（x） 與n位精度的根部，條件是 一個良好的初始近似是已知的， 爲O（（\ log n）的F（N）），其中F（n）是計算F（X）/ f的 成本'（x）的\，與 n位精度。

但是，根據您的精度要求，你可以做的更好：

若f（x）的可可變 精度進行評估，該算法可以 提高。因爲 「自我糾正」牛頓 方法的性質，這意味着它是由小的擾動影響 一旦 達到二次 收斂的階段，它僅需要 使用m-數位精度在一個步驟其中 的近似值具有m位數字 的準確性。因此，在第一次迭代 可以使用精密 兩倍高X_0， 第二次迭代的精度用精密 四倍高來執行，等等。如果 精度水平適當地選擇，只 最終迭代需要 F（X）/ F'（x）的\，以全 n位精度進行評價。假設F（n） 超線性增長，實際上 的情況就是這種情況，因此發現根的成本僅爲O（F（n）），其中 常數因子接近於1。

Answer 2

這article給出了一個相關的辦法對如何考慮方法的複雜性。