Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Let $F : R^k \to R^k$ be a smooth map whose Jacobian $J(F): R^k \to R$ vanishes on a discrete set $S$, so that if $O$ is the complement of $S$, then $f: O \to R^k$, the restriction of $F$, is a local diffeomorphism, and in particular there are only finitely many points $x$ inside the unit ball of $R^k$ such that $f(x) = 0$. What I would like to know is if there any a good algorithm for finding such points $x$. Of course, if $k=1$ this is easy, using the Intermediate Value Theorem; just partition the interval $[-1,1]$ into a reasonably large number $N$ of subintervals of length $2/N$ and test on which subintervals $f$ changes sign, and then use bisection to locate a zero in those subintervals. If $k>1$ I suspect that some sort of application of Marching Cubes may work, but the usual search methods have not turned up anything.

share|improve this question
1  
With a lipschitz bound on $DF$, Newton's method gives an algorithm to approximate $F^{-1}$ effectively. There's a version of this written up in Hubbard's calculus textbook. –  Ryan Budney Aug 22 '13 at 21:27
    
Do you have $F$ as "a formula", or do you only have the ability to evaluate up to some precision on a suitably dense grid in $\mathbb{R}^k$? –  Vidit Nanda Aug 22 '13 at 23:32
    
@Nanda For the application I have in mind, F will be given by a formula. –  Dick Palais Aug 22 '13 at 23:51

1 Answer 1

up vote 3 down vote accepted

With a Lipschitz bound on the derivative, Newton's method gives an algorithm to efficiently approximate $F^{-1}$. Hubbard's calculus textbook has a write-up using this perspective, viewing the result as a consequence of Kantorovich's Theorem. There's a fairly extensive analysis of the absolute error.

share|improve this answer
    
Yes! Newton's Method is clearly the way to go. For $k=1$, the algorithm I wrote in fact did use Newton's Method, (rather than bisection) since it is much faster. But I guess I forgot that Newton's Method works in higher dimensions too. Thanks Ryan. –  Dick Palais Aug 23 '13 at 5:40

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.