Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. It only takes a minute to sign up.
Sign up to join this community
I need to find the zero of a function $f(\lambda)$ which is of the form $\sum \frac{c_i^2}{(1+\lambda d_i)^2} -1 $. I tried using Newton's method, and it works sometimes, but it is higly dependent of the initial choice, and the chances of divergence are very high, since the function is "almost" flat.
What would be the best method to find the zero of such a function?
For now, I replaced Newton with secant method, and it seems to work better.
Off the top of my head, there are a number of things that may be going wrong. You might want to verify the following
Are the function values or derivatives you are computing numerically stable? Is the rounding error in their evaluation smooth? You can verify this visually by plotting an extremely small interval around a known root such that the function values are $\pm \varepsilon_\mathsf{mach}$. If your function or derivative changes sign near the root, Newton's method won't work.
What termination criteria are you using? If you're looking for a root $f(\lambda)=0$ with $\lambda \in [a,b]$, do you stop when $|b-a|<\tau$ or when $|f(\lambda)|<\tau$ where $\tau$ is your tolerance? In either case, what is your rationale for your choice of $\tau$ and how does it fit with the error/interval you observe in the previous point?
Newton's method is a good hammer, but there are many functions that will look a lot like your thumb. The Secant method is a good choice for functions that are almost linear in the search interval, but will perform poorly as soon as you depart from that assumption. A good alternative is the so-called Illinois algorithm. A major advantage of interval methods is that they don't rely on the function or any of its derivatives being numerically smooth as you can run them until $fl(f(\lambda))=0$ or until the search interval $[a,b]$ is numerically zero, i.e. $fl(a)=fl(b)$.
Can you bound your zero? If you can come up with a good heuristic for the approximate location of the zero and then compute bounds for it over an interval that is not too large, the performance of many methods is improved. Here's some Matlab code I use to perform basic root bracketing for monotonic functions.
In terms of interval methods, @Pedro's suggestion to use the Illinois algorithm is a good simple possibility. If you want a big hammer, there is of course Brent's method, which is more complex to implement. It's the basis of Matlab's fzero.
Using a line search or trust region method along with Newton's method typically does the trick of finding the zero reliably. Check any advanced numerical methods or optimization book.
