# Numerical method for equation solving that works on stochastically computed functions

There are many well known numerical methods for solving equations of the type $$f(x) = 0, \quad x \in \mathbb{R}^n,$$ e.g. bisection method, Newton's method, etc.

In my application $f(x)$ is calculated with a stochastic method (the result is an average).

Are there any numerical equation solving methods that handle this situation well? Links to any discussion of similar situations are also appreciated.

The precision to which I can calculate $f(x)$ depends strongly on $x$, and I might easily hit a wall where I can't increase the precision without increasing the computation time significantly. So I can't ignore the fact that the result from $f$ is not precise. This will also impact the precision to which $x$ can be found in practice.

• What do you know about the noise / precision: does each $f(x)$ come with an error bar, or does the time just hit a wall ? (Can't you just set a time limit ?) Also, there are many methods for minimizing noisy functions e.g. $f(x)^2$, easier than root-finding in $\mathbb{R}^n$ . Aug 29, 2013 at 14:22
• @Denis I do have a rough estimate of the precision, but it's quite rough, and it may heavily depend on $x$. I'm working on that aspect too and might post a question eventually ($f$ is an average calculated using MCMC). I specifically need root-finding here, not optimization, but you're right that minimizing $f(x)^2$ is the same as solving $f(x) = 0$ if the method does indeed find the global minimum. Do you have any references saying that this is a good approach here, and also any references for noisy optimization? Wouldn't this approach be detrimental to the precision of the result? Aug 29, 2013 at 14:32
• the picture on Numerical Recipes p. 474 shows why root-finding in even 2d is tough. On noisy optimization, I'll pass; there are many many methods (more than test cases), ask experts here. Aug 29, 2013 at 14:42
• @Denis Well, yes, it tough, but it's what I need. I have the advantage of having a proof that there's either one root or no roots at all. Aug 29, 2013 at 14:45