Tell me more ×
Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. It's 100% free, no registration required.
up vote 5 down vote favorite
1

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?

share|improve this question
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

2 Answers

up vote 7 down vote accepted

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

share|improve this answer
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
up vote 3 down vote

"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.

share|improve this answer
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.