2

The function $f(x) = x^2 +1$ has zeros in the complex plane at $x = +i$ and $x = -i$. Is there a real starting point for complex Newton's method such that the iterates converge to either of these zeros? Is there a complex starting point too?

I know that Newton's method for finding roots is $x_{n+1} = x_n - \frac {f(x)}{f'(x)}$. But I don't know how to find the proper starting point.

Shadi Taghian
  • 277

2 Answers2

4

For a polynomial with real coefficients the Newton iteration starting from real points will always stay on the real axis, as all the arithmetic operations stay in the reals.

For polynomial functions the Newton iteration is contractive towards the area of the roots. There are counter examples of oszillating iterations, but in general the iteration will converge from a majority of complex initial points. It helps to start close to the root location as far away from them the convergence is linear with contraction factor $\approx 1-\frac1{\deg(f)}$.

See also Newton fractals to illustrate the chaotic relation between starting points and the roots the iteration converges to.

If you instead try to solve the equivalent $0=g(z)=e^{iεz}f(z)$ with the Newton step $$ z_+=z-\frac{g(z)}{g'(z)}=z-\frac{f(z)}{f'(z)+iεf(z)} $$ with some small real $ε$, then iterations starting close to a real solution will still converge to that real solution, however real starting points far from a solution might also converge towards complex roots.

Lutz Lehmann
  • 126,666
3

We can use Newton's Method to find the complex roots. There will be no real starting point for which you can find these complex roots.

We can visualize the complex roots using a contour plot as:

enter image description here

From this plot, we see that we have roots at $z = 0~ \pm~ i$.

Lets write the function as $f(z) = z^2 + 1$, to represent that we want complex roots leading to the Newton iteration formula of:

$$z_{n+1} = z_n - \frac {f(z_n)}{f'(z_n)} = z_n - \dfrac{z_n^2+1}{2 z_n}$$

Lets choose $z_0 = 1 + i$, leading to the iterates:

  • $z_0 = 1.0000000000000000+ 1.0000000000000000 i$,
  • $f(z_0) = 1.+2. i$
  • $z_1 = 0.2500000000000000+ 0.7500000000000000 i$,
  • $f(z_1) = 0.5+0.375 i$
  • $z_2 = -0.0750000000000000+ 0.9750000000000000 i$,
  • $f(z_2) = 0.05500000000000016-0.1462499999999999 i$
  • $z_3 = 0.0017156862745098+ 0.9973039215686280 i$,
  • $f(z_3) = 0.005387831603229309+0.003422121299500236 i$
  • $z_4 = -4.6418462654740370 \times 10^{-6}+ 1.0000021604906580 i$,
  • $f(z_4) = -4.32096443714336 \times 10^{-6}-(9.28371258827906 \times 10^{-6}) i$
  • $z_5 = -1.0028683001159460 \times 10^{-11}+ 0.9999999999915610 i$,
  • $f(z_5) = 1.687860962107379 \times 10^{-11}-(2.005736600214965 \times 10^{-11}) i$
  • $z_6 = 8.4637378770367200 \times 10^{-23}+ 1.0000000000000000 i$,
  • $f(z_6) = 2.220446049250313 \times 10^{-16}+(1.692747575407344 \times 10^{-22}) i$
  • $z_7 = -2.3509887016445750 \times 10^{-38}+ 1.0000000000000000 i$,
  • $f(z_7) = 0.-(4.701977403289151 \times 10^{-38}) i$

We see that this converges in seven steps to $z = 0 + i$.

For the second root, you know they come in complex conjugate pairs, so $z = 0 - i$. You can try a starting value of $z_0 = 1 - i$ to see the iterates.

It has been my experience that you get even more bizarre behaviors with complex numbers. In this case, even if we start with $z_0 = 10 + 100 i$, it takes eleven steps to converge on the root.

If you have the tools, you can draw a Relief Plot that shows the number of steps to convergence for a starting value and that is very instructive.

Moo
  • 11,311