0
$\begingroup$

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.

  • 0
    If you'd just post what your function looks like (and also possibly a graph), you might get more helpful answers.2011-07-21

2 Answers 2

2

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.

  • 1
    @devdept: Newton-Raphson **always** requires a good seed if you're to obtain usable results from it.2011-07-21
1

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?

  • 0
    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](http://en.wikipedia.org/wiki/Powell%27s_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](http://eigen.tuxfamily.org/) has a templated implementation in `c++`, if that is your language.2011-07-22