Recently I was introduced to the Newton-Raphson method for finding roots of a polynomial function. I looked up the proof of it and I found this.

I found a variation of the Newton-Raphson method by considering the first $3$ terms of the Taylor series. i.e, in

$$f(\alpha) = f(x) + (\alpha - x)f'(x) + (\alpha-x)^2\frac{f''(x)}{2!} +\;\; ...$$ We consider

$$f(\alpha) \approx f(x) + (\alpha - x)f'(x) + (\alpha-x)^2\frac{f''(x)}{2!}$$

And as $f(\alpha) = 0$, the above equation turns to

$$0 \approx f(x) + (\alpha - x)f'(x) + (\alpha-x)^2\frac{f''(x)}{2!}$$

And then we solve the above equation for $\alpha$ by using the quadratic formula.

So, my question is will this variation have a worse time complexity for finding the roots of a polynomial function than the original Newton-Raphson method?

  • $\begingroup$ What do you mean by time complexity? Do you mean the $\min$ number of flops needed to solve the quadratic given the values of $x,f(x),f'(x),f''(x)$? $\endgroup$ – copper.hat Aug 23 '18 at 14:49
  • $\begingroup$ Without making additional assumptions about the time complexity of evaluating $f$ and its derivatives, along with even more significant assumptions about the function, it won't be possible to say anything about the time complexity of Newton's method. Except for a few fairly special cases, Newton's method doesn't have polynomial iteration count complexity. In practice we usually analyze the asymptotic convergence rate of Newton and Newton-like methods. $\endgroup$ – Brian Borchers Aug 23 '18 at 14:51
  • $\begingroup$ @copper.hat I have updated my question, please take a look at it. $\endgroup$ – Deepam Sarmah Aug 23 '18 at 15:27
  • $\begingroup$ Are you asking about the cost of finding a solution within some tolerance or the cost for a single iteration? $\endgroup$ – copper.hat Aug 23 '18 at 15:33
  • $\begingroup$ @copper.hat I am asking the cost of finding a solution within some tolerance. $\endgroup$ – Deepam Sarmah Aug 24 '18 at 14:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.