4
$\begingroup$

So as the title would suggest I'm currently reading about Newton's method for finding roots. I'm having trouble understanding the reasoning for a function without a root.

It reads as following:

"Consider the function $f(x) =1+x^2$. Clearly f has no real roots though it does have complexroots $x\pm i$.The Newton method formula for f is:

$x_{n+1} = x_{n} - \frac{1+x^2}{2x_{n}}=\frac{x^2-1}{2x_{n}}$"

What is happening here?

Many thanks to whomever might expand this a little for me!

$\endgroup$
6
  • 7
    $\begingroup$ What is your question? Obviously for a polynomial with real coefficients the Newton method with real starting value cannot converge to a complex root. Try a complex starting value. $\endgroup$
    – gammatester
    Jan 13, 2018 at 22:22
  • $\begingroup$ right, but how did the author arrive at $ x_{n+1} = x_{n} - \frac{1+x^2}{2x_{n}}=\frac{x^2-1}{2x_{n}}$ specifically the last two step where he goes from $ x_{n} - \frac{1+x^2}{2x_{n}}$ to $\frac{x^2-1}{2x_{n}}$ ? $\endgroup$
    – Aliasa Zarowny Pseudonymia
    Jan 13, 2018 at 22:30
  • $\begingroup$ That's just algebra (put $x_n$ over a denominator of $2x_n$ and combine like terms). $\endgroup$
    – Ian
    Jan 13, 2018 at 22:32
  • $\begingroup$ $x$ should be $x_n$. ($x_n - f(x_n)/f'(x_n)$, and $f(x) = 1+x^2$) $\endgroup$
    – Atbey
    Jan 13, 2018 at 22:33
  • $\begingroup$ $$x_{n+1}=x_n - \frac{f(x)}{f'(x_n)} = x_n - \frac{x_n^2+1}{2x_n} = \frac{2x_n^2-x_n^2 -1}{2x_ n}=\frac{x_n^2 - 1}{2x_n}$$ $\endgroup$
    – gammatester
    Jan 13, 2018 at 22:34

4 Answers 4

Reset to default
6
$\begingroup$

You have to choose complex starting values, otherwise the method cannot converge to complex roots.

With the correct iteration formula $$x_{n+1}=x_n - \frac{f(x)}{f'(x_n)} = x_n - \frac{x_n^2+1}{2x_n} = \frac{2x_n^2-x_n^2 -1}{2x_ n}=\frac{x_n^2 - 1}{2x_n}$$ and a complex starting value you get e.g.

  1.0              + 1.0 i
  0.2500000000     + 0.7500000000 i
 -0.07500000000    + 0.9750000000 i
  0.001715686274   + 0.9973039215 i
 -0.46418462831e-5 + 1.000002160 i
 -0.1002647834e-19 + 1.000000000 i
  0.0              + 1.000000000 i

and for the other root

  3.0              - 1.0 i
  1.350000000      - 0.5500000000 i
  0.3573529412     - 0.4044117647 i
 -0.4348049736     - 0.8964750065 i
  0.001593678319   - 0.8997608310 i
 -0.0001874328610  - 1.005581902 i
 -0.1037539915e-5  - 1.000015475 i
 -0.1605575154e-10 - 1.000000000 i
  0.0              - 1.000000000 i
$\endgroup$
3
  • $\begingroup$ Which regions converge for each root? $\endgroup$
    – marty cohen
    Jan 13, 2018 at 22:58
  • 1
    $\begingroup$ @marty-cohen: I guess (without proof) that the regions are $\Im x_0 > 0$ and $\Im x_0 < 0,$ but the regions can be quite complicated, see en.wikipedia.org/wiki/Newton_fractal $\endgroup$
    – gammatester
    Jan 13, 2018 at 23:10
  • $\begingroup$ That is correct, although I don't have a reference handy. Newton for this function on the real line goes bananas! $\endgroup$
    – max_zorn
    Jan 13, 2018 at 23:20
2
$\begingroup$

Newton's Method works only if the sequence of iterates converges. This is not always the case.

For example if you choose $f(x)=\sqrt[3] x$ and try Newton's Method to find the root $x=0$

We get $$ x_{n+1}=x_n - \frac{f(x_n)}{f'(x_n)} = x_n - \frac{x_n^{1/3}}{(1/3) x_n^{-2/3}}=-2x_n $$ The sequence of iterates starting at $x=1$ is $$1,-2,4,-8,...$$ which does not converge to $x=0$

$\endgroup$
1
$\begingroup$

In some cases, the Newton's Method does not work. For example, if you encounter a stationary point in the process (division by zero).

Your example is another one in which Newton's Method does not work, because starting with a real number you only go through real numbers in the process. BUT you could start with a complex number, and (with a bit of luck) you will converge to the correct complex root.

$\endgroup$
1
$\begingroup$

There's a typo in your displayed equation. The $x$ in the numerator should be $x_n$. Then one just writes

$$x_{n+1} = x_n -\frac{1+x_n^2}{2x_n} = x_n\frac{2x_n}{2x_n} - \frac{1+x_n^2}{2x_n} =\frac{2x_n^2-x_n^2-1}{2x_n}. $$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .