4

I'm using a calculator to observe the sluggishness with which Newton's method converges with $f(x) = (x-1)^8$. I let $x_0 = 1.1$. Clearly it's taking forever to get to the root $x=0$. I'm not completely sure why this is. I know it has to deal with the multiplicity of 8.

I'm looking to reconcile this slow convergence with the theory. Thanks for any help :)

Drake
  • 851

3 Answers3

4

Newton's method converges quadratically to the root for any initial approximation provided the root is a simple zero.

For roots that are not simple (higher multiplicity), we do not get quadratic convergence.

We can modify Newton's Method to work with those to:

$$g(x) = x - \dfrac{f(x)f'(x)}{[f'(x)]^2 - [f(x)][f''(x)]}$$

The obvious drawback is the need for the second derivative, but it will converge quadratically if $g$ has the required continuity conditions. This second order term can also cause serious roundoff errors when we have small differences.

Amzoti
  • 56,093
  • Hmmm. What if $f(x_0) = f'(x_0) = f''(x_0) = 0?$ – Will Jagy Sep 28 '13 at 21:44
  • anyway, http://en.wikipedia.org/wiki/Newton%27s_method#Slow_convergence_for_roots_of_multiplicity_.3E_1 – Will Jagy Sep 28 '13 at 21:46
  • In those cases, you might not find the root or this method will show no improvement. – Amzoti Sep 28 '13 at 21:48
  • @WillJagy: For your example, what would happen with Newton's Method of $g(x) = x - f(x)/f'(x)$. In other words, how is that any different? – Amzoti Sep 28 '13 at 22:02
  • Amzoti, I think both methods work slowly in that case. I am unable to think of a really pretty method that works when you have multiple roots but have little ability to correctly assign an "order" to the multiplicity. On those rare occasions when i need a custom rootfinder, I just use bisection. – Will Jagy Sep 28 '13 at 22:18
  • You're wracking up a string of green checkmarks! +1 – amWhy Sep 29 '13 at 00:14
  • Aha! Good idea... ;-) – amWhy Sep 29 '13 at 00:32
2

Why not use $f(x) = x^8$ instead?

Let's look at one iteration of Newton's method: $$x_1 = x_0 - \frac{x_0^8}{8x_0^7} = x_0 - \frac{1}{8}x_0 = \frac{7}{8}x_0.$$

So each iteration just multiplies the previous one by 7/8; repeated application gives a geometric series converging to the root 0.

If you replace the exponent 8 by $n$, then the geometric series has ratio $1-(1/n)$; so the larger $n$ is, the closer the ratio is to 1, and the slower the convergence.

Ted
  • 33,788
0

$\newcommand{\pars}[1]{\left( #1 \right)}$ If we know the multiplicity $m$, we solve ${\rm f}^{1/m}\pars{x} = 0$ instead of ${\rm f}\pars{x} = 0$. Newton-Rapson yields

$$ x_{n + 1} = x_{n} - {{\rm f}^{1/m}\pars{x_{n}} \over \pars{1/m}\,{\rm f}^{\pars{1/m} - 1}\pars{x_{n}}{\rm f}'\pars{x_{n}}} \quad\Longrightarrow\quad \color{#ff0000}{\large x_{n + 1}} \color{#000000}{\large\ =\ } \color{#ff0000}{\large x_{n}- m\,{{\rm f}\pars{x_{n}} \over {\rm f}'\pars{x_{n}}}} $$

Notice the multiplicative factor $m$. It is faster than the original one $ x_{n + 1} = x_{n} - {\rm f}\pars{x_{n}}/{\rm f}'\pars{x_{n}} $.

$$ \begin{array}{rrclcrcl} \mbox{Modified Newton-Rapson}:& x_{n + 1} & = & x_{n} - 8\,{\pars{x_{n} - 1}^{8} \over 8\pars{x_{n} - 1}^{7}} & \Longrightarrow & \color{#ff0000}{\Large x_{n + 1}} & = & \color{#ff0000}{\Large 1} \\ \mbox{Original Newton-Rapson}:& x_{n + 1} & = &x_{n} - {\pars{x_{n} - 1}^{8} \over 8\pars{x_{n} - 1}^{7}} & \Longrightarrow & x_{n + 1} & = & {7x_{n} + 1 \over 8} \end{array} $$

Felix Marin
  • 89,464