I'm trying to understand why the Newton Raphson method converges to the root of a given equation? Can someone explain it to me theoretically. Thanks
Asked
Active
Viewed 4,327 times
2
-
Have you read the wikipedia article? http://en.wikipedia.org/wiki/Newton%27s_method They also have a nice gif that explains it! – Ojas Jun 25 '14 at 09:32
2 Answers
1
Newton's method does not always converge.
Let $f$ be a function with $f\left(r\right)=0$. If $f$ is continuously differentiable and its derivative is nonzero at $r$, then there exists a neighborhood of $r$ such that for all starting values $x_0$ in that neighborhood, the sequence $\left\{x_n\right\}$ will converge to $r$.
To convince yourself of this, you can adapt the proof at https://en.wikipedia.org/wiki/Newtons_method#Proof_of_quadratic_convergence_for_Newton.27s_iterative_method to not use the second derivative condition (all that the second derivative condition does is guarantee second order convergence).
As an example, consider the function $f\left(x\right)\equiv x^5-x^2-5$. The proof guarantees that (1) there exists some neighborhood $I$ around the root $r\approx 1.48423$ for which any initial guess $x_0\in I$ will converge to the root $r$. However, (2) Newton's method will not converge unconditionally. Take for example $x_0=0$ as your initial guess. The derivative is zero there (corresponding to a vertical tangent), and hence $x_1$ is undefined.
parsiad
- 25,154
-
This might also be a more gentle read: http://www.math-cs.gordon.edu/courses/mat342/handouts/rate.pdf – parsiad Jun 25 '14 at 09:31
-
-
That polynomial has a single real root. Are you asking if for any initial guess, Newton's method converges to that root? Or are you asking whether or not that is true? – parsiad Jun 25 '14 at 18:30
-
I have answered both of these questions in my edit of my answer above. – parsiad Jun 25 '14 at 18:42
-
2For your example, $f'(0)$ is nicely defined, it is $0$. The issues is that you can't divide by it. – Ross Millikan Jun 25 '14 at 19:26
-
1
There are ways that Newton's method may fail without the derivative being zero. For example, you can get stuck in a loop. Try using Newton's method on $f(x)=\frac{1}{2}x^3-\frac{5}{2}x$ starting with $x_0=1$.
D Wiggles
- 2,818