0
$\begingroup$

Can someone explain to me what is the convergence criteria for newton's method? As I was trying to code my own Square root function: sqrt(double n) iteratively, can I use: absolute(estimation^2 - n) as an indicator of when the iteration should stop?

I understand that convergence is also a great stopping criteria but why can't I use: absolute(estimation^2 - n)

$\endgroup$
  • $\begingroup$ Your criterion is good for some purposes, but it does not tell you the distance between your estimate and the square root. For that, there is the Kantorovich Theorem. $\endgroup$ – Ryan Budney Feb 18 '16 at 22:14
1
$\begingroup$

You can use both $|x_k-n| < \epsilon$ and $|x_{k + 1}-x_k| < \epsilon'$ as stopping criteria. Although you must be aware that there exists some sequence $(x_k)$ where for any $\epsilon > 0$, it exists $k$ such that $|x_{k + 1}-x_k| < \epsilon$ but $(x_k)$ does not converge. But $x\mapsto x^2$ is convex and you can prove Newton's method converge towards the root for convex functions.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.