0
$\begingroup$

I am currently working on Newton Raphson Method.

I am kind of facing a problem how Newton Raphson Method work on more than second order quadratic functions with double roots. I have googled and found some information on it. The information says that Newton Raphson Method is slow on double roots,

Why? How do I know if the function has double roots?

Please let me have your advice. I am sorry if I have placed my question in the wrong places. Thank you.

$\endgroup$
2
$\begingroup$

The usual method is slow for double roots because of the following Taylor series argument. Assume $f$ is twice continuously differentiable and $r$ is a single root, i.e. $f(r)=0$ and $f'(r) \neq 0$. Then

\begin{eqnarray*}\left ( x - \frac{f(x)}{f'(x)} \right ) - r & = & x - r - \left ( x - r + \frac{f''(r)}{2 f'(r)} (x-r)^2 + o((x-r)^2) \right ) \\ & = & \frac{f''(r)}{2 f'(r)} (x-r)^2 + o((x-r)^2) \end{eqnarray*}

What I did here was Taylor expand $\frac{f(x)}{f'(x)}$ to second order about $x=r$, and then substitute in the fact that $f(r)=0$, which cancels a lot of terms. The result means that when $r$ is a single root, the method converges quadratically. Roughly speaking this means that the number of correct digits double at each step, once the error is small enough. On the other hand, if it is a double root (i.e. $f(r)=f'(r)=0$ and $f''(r) \neq 0$), we have a different situation. Here we cannot expand $f(r)/f'(r)$ about $x=r$ because this function is not defined there. Instead we must do the following:

\begin{eqnarray*}\left ( x - \frac{f(x)}{f'(x)} \right ) - r & = & x-r - \frac{1/2 f''(r) (x-r)^2 + o((x-r)^2)}{f''(r)(x-r) + o(x-r)} \\ & = & x-r -\frac{1/2 (x-r) + o(x-r)}{1 + o(1)} \\ & = & x-r - (1/2 (x-r) + o(x-r))(1+o(1)) \\ & = & 1/2 (x-r) + o(x-r) \end{eqnarray*}

This means the method converges linearly with a coefficient of $1/2$. This means the error is approximately halved at each step, once the error is small enough, which basically means that you gain a correct binary digit at each step. This gets even worse for higher order roots: for a root of order $n$ we have a coefficient of $1-\frac{1}{n}$.

There is a modified Newton method which can detect proximity to a non-simple root and modify $f$ in such a way that quadratic convergence is recovered. If you know the order of the root is $n$, then you can use

$$x_{k+1} = x_k - n \frac{f(x_k)}{f'(x_k)}.$$

A similar argument to the first one shows that this converges quadratically. If you don't know the order of the root, there is a method which can estimate it: see http://mathfaculty.fullerton.edu/mathews/n2003/NewtonAccelerateMod.html

Edit: the symbol $o(f(x))$, called "little oh notation", is a standard shorthand. It means an unspecified function $g(x)$ such that $g(x)/f(x) \to 0$ as $x$ tends to something specified by context (usually $0$ or $\infty$, in this case $0$). So for example, calculus tells us that

$$\lim_{h \to 0} \frac{f(x) - h f'(x)}{h} = 0$$

which is the same as

$$f(x) - h f'(x) = o(h)$$

Little oh notation has a weaker counterpart, called "Big oh notation". That is, the symbol $O(f(x))$ means an unspecified function $g(x)$ such that $g(x)/f(x)$ is bounded as $x$ tends to something specified by context.

$\endgroup$
  • $\begingroup$ Thank you for your time work. However, I don't really follow what you are saying. I really want to understand this topic, but it looks like there is no way I can understand it. I am not really deep in maths. $\endgroup$ – user122358 Jul 6 '14 at 15:53
  • $\begingroup$ Other than the $o$ notation, which is really just a convenient shorthand, everything I'm describing is covered in two semesters of calculus. I can explain what $o$ means if you want. $\endgroup$ – Ian Jul 6 '14 at 16:10
  • $\begingroup$ Please do so, I want to understand it. And please tell me if I need to understand Tayler series. $\endgroup$ – user122358 Jul 6 '14 at 16:18
  • $\begingroup$ You do need to understand Taylor series or at least second order Taylor approximations in order to understand the convergence properties of Newton's method. $\endgroup$ – Ian Jul 6 '14 at 16:31
  • $\begingroup$ I will study Taylor series and can I have a reason why I need to know Taylor series before I get to know it? $\endgroup$ – user122358 Jul 6 '14 at 16:51
1
$\begingroup$

The usual fast convergence of Newton-Raphson depends on the function having a nonzero derivative at the root.

If there's a multiple root, then the derivative at the root is 0 and this doesn't hold anymore. In the best case the root is a double root, and the function looks locally like a parabola touching the $x$-axis near the root. Then the error is halved for each iteration of the approximation, rather than squared, and the number of iterations you need is proportional to the number of correct digits you want to find. (For single roots, the number of iterations is proportional to the logarithm of the number of correct digits desired).

$\endgroup$
  • $\begingroup$ I am kind of understanding what you are saying, literally. Can you please make it a little simpler for me to understand. I don't think I am deep in mathematics. $\endgroup$ – user122358 Jul 6 '14 at 15:52

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.