[Math] formula that can be used to determine the number of iterations needed when using the Secant Method like there is for the bisection method

numerical methods

The formula used to find the number of iterations needed to find a root of a function using the bisection method is this; $$|c_n-c|\le\frac{|b-a|}{2^n}.$$

Is there a formula that can be used to determine the number of iterations needed to find a root of a function using the Secant Method?

Best Answer

No, there is no guarantee of convergence, as there is for bisection. The secant method can:

  • run into overflow (division by zero) if the secant is very close to horizontal
  • diverge to infinity
  • get stuck in infinite look
  • get stuck in nearly-infinite loop, from which it will eventually converge to the root, but it will take very long time.

That's the tradeoff between speed and reliability. Under favorable conditions, the secant method converges faster than bisection: the error $E_n$ after $n$ steps behaves like $E_{n+1} \approx E_n^\varphi$ with $\varphi = (1+\sqrt{5})/2=1.612\dots$. In other words, the number of correct digits in the answer grows like the Fibonacci sequence with the secant method; while for the bisection method it grows linearly. However, the above is asymptotic error analysis in the vicinity of a root (which assumes the function is twice differentiable, with nonzero first derivative at the root). How long the method will take to get to this vicinity is anyone's guess.

Related Question