Randomized Newton-Raphson (Q922640)

Let g: \(R^ 1\to R^ 1\) be a differentiable function. For the numerical solutions of the equation \(g(x)=0\) a randomized Newton process of the form \(X_{k+1}=x_ k-(g(x_ k)+Z_{1,k})/(g'(x_ k)+Z_{2,k}),\quad k=0,1,...,\) is considered where \(Z_{1,k}\), \(Z_{2,k}\) are mutually independent random variables with controllable densities and hence \(\{X_ k\}\) represents a recursively defined sequence of random variables realizing \(\{x_ k\}\). Conditions are developed under which the process converges in various senses to a root of g. A generalization to functions on \(R^ n\) is based on a stochastic version of the generalized inverse. Several examples are given and empirical results about convergence rates are discussed.