9

Newton's method for solving nonlinear equations is known to converge quadratically when the starting guess is "sufficiently close" to the solution.

What is "sufficiently close"?

Is there literature about the structure of this basin of attraction?

David Ketcheson
  • 16,522
  • 4
  • 54
  • 105
  • The root should be isolated (not multiple). If the Hessian is uniformly definite (concave up or down) in the region, you should be good to go. Of course guaranteeing or testing these conditions empirically is usually impractical. – hardmath Jul 23 '12 at 15:30
  • I saw the question in NA-Digest the other day and thought it intriguing. Apparently I wasn't the only one :-) – Wolfgang Bangerth Jul 25 '12 at 15:15

3 Answers3

8

For a single rational equation in the complex domain, the basin of attraction is fractal, the compelement of a so-called Julia set. http://en.wikipedia.org/wiki/Julia_set . For theory with some nice online figures, see, e.g.,
http://mathlab.mathlab.sunysb.edu/~scott/Papers/Newton/Published.pdf
http://hera.ugr.es/doi/15019160.pdf

Even the ''globalized'' damped Newton method for $x^3-1=0$ has a fractal basin of attraction; see http://www.jstor.org/stable/10.2307/2653002 .

Thus there is little point in specifying in detail what is "sufficiently close" to the solution. If one knows bounds on the second derivatives, there is the Newton--Kantorovich theorem which gives lower bounds on the radius of a ball in which Newton's method converges, but except in 1D, these tend to be quite pessimistic.

Computationally useful bounds can be obtained using interval arithmetic; see, e.g., my paper
Shen Zuhe and A. Neumaier, The Krawczyk operator and Kantorovich's theorem, J. Math. Anal. Appl. 149 (1990), 437-443.
http://www.mat.univie.ac.at/~neum/scan/61.pdf

Arnold Neumaier
  • 11,318
  • 20
  • 47
  • It is only in the complex plane that $x^3 - 1 = 0$ has a fractal basin of attraction. On the real line, any initial guess $x > 0$ will do (once $x > 1$ the convergence will be monontone decreasing and quadratic rate will quickly appear). – hardmath Jul 24 '12 at 14:17
  • 1
    @hardmath: yes, but the complex equation becomes two real equations in 2 variables, for which the same applies. – Arnold Neumaier Jul 24 '12 at 14:25
4

"Sufficiently close" is difficult to characterize considering that it gives rise to a class of fractals. Newton methods with globalization strategies such as line search and trust region extend the basin of attraction. If additional problem structure is available, such as in optimization, the assumptions necessary for convergence can be further weakened.

Jed Brown
  • 25,650
  • 3
  • 72
  • 130
  • Just for curiosity, do you have any example for "If additional problem structure is available, such as in optimization, the assumptions necessary for convergence can be further weakened."? – vanCompute Oct 17 '12 at 10:01
  • @vanCompute See this example for an example related to optimization, where the object functional provides information that is lost in the first order optimality conditions. Another form would be knowledge that a certain continuation (pseudotransient, parameter, grid, etc) always converged, but the residual may have to increase before reaching the solution if one attempts to solve the problem directly. – Jed Brown Oct 17 '12 at 11:25
3

There are some useful results for Newton's method applied to complex polynomials.

Joel Friedman in On the Convergence of Newton's Method (Theorem 2.2) gives an explicit radius for a disk contained in the immediate basin of attraction of each root of a polynomial $f$: $$ r=\frac{\eta}{2d} $$ where $\eta$ is the minimum distance between two roots of $f$ and $d$ is the degree of $f$.

Other explicit bounds are given by Anthony Manning in How to be sure of finding a root of a complex polynomial using Newton's method (Theorem 1.2).

See also How to find all roots of complex polynomials by Newton's method by Hubbard et al.
Invent. Math. 146 (2001), no. 1, 1–33. pdf

lhf
  • 966
  • 1
  • 7
  • 12