Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

What are the options for a Newton Iteration that starts jumping between two values and never converges?

I am projecting 3D points on the spherical UV surface and approaching the poles the issue arise. Is the issue releated to the projection problem (U, V tangents get smaller) or to the Newton-Raphson implementation?

Thanks.

share|improve this question
    
If you'd just post what your function looks like (and also possibly a graph), you might get more helpful answers. –  J. M. Jul 21 '11 at 14:26

2 Answers 2

up vote 2 down vote accepted

When you are applying Newton's method to an equation $f(z)=0$ or to a system of equations $f_i({\bf x})=0$ $\ (1\leq i\leq n)$ defined in some region $\Omega\subset{\mathbb R}^n$ you have to be aware the that the geometric situation defined by these equations might be complicated to begin with. Now Newton's method $z_n\to z_{n+1}$ defines a discrete dynamic system on $\Omega$ with various basins of attraction of individual solutions, basins of attraction of periodic orbits and worse things. In addition these basins are intertwined in a fractal way, see, e.g. Peitgen/Saupe: The science of fractal images, pp. 207ff., for a picture of the basins for Newton's method applied to the equation $z^3-1=0$.

These things are usually not dealt with in numerical practice. One just starts with an approximation to a solution that was arrived at by heuristic or other means, and after a few runs of the algorithm it becomes obvious whether one has convergence or not.

share|improve this answer
1  
Are you trying to tell me that I need good starting point, right? In fact, walking toward poles (and using the last good approximation as start for the next) is easy and not the opposite... –  Alberto Jul 21 '11 at 12:10
1  
@devdept: Newton-Raphson always requires a good seed if you're to obtain usable results from it. –  J. M. Jul 21 '11 at 14:24

I would indeed suspect numerically unstable reciprocals of tiny derivatives as you get close to the pole, in case you are iterating in the $UV$ space and solutions are close to poles. You could try iterating in a rotated $U'V'$ space so that derivatives would behave better.

Can you perhaps describe your problem more thoroughly, i.e. what is the function of which root you are finding?

share|improve this answer
    
I am walking on a Nurbs surface (en.wikipedia.org/wiki/…). Do you mean trying to rotate the sphere to move away poles from my path? It isn't always possible (you may need to walk from pole to pole) and it's even harder to decide how and how much rotate the sphere. –  Alberto Jul 22 '11 at 6:34
    
Since the surface can be perhaps quite "wild" (?), you could consider methods which limit how far they follow the gradient -- e.g. Powell's method (can also be used with analytically-computed gradients), or conjugate gradients. I am not an expert here, though. There are good implementations of those methods in minpack, and e.g. eigen has a templated implementation in c++, if that is your language. –  eudoxos Jul 22 '11 at 9:06

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.