A while ago I wrote about using Boltzmann sampling to generate random instances of algebraic data types, and mentioned that I have some code I inherited for doing the core computations. There is one part of the code that I still don’t understand, having to do with a variant of Newton’s method for finding a fixed point of a mutually recursive system of equations. It seems to work, but I don’t like using code I don’t understand—for example, I’d like to be sure I understand the conditions under which it does work, to be sure I am not misusing it. I’m posting this in the hopes that someone reading this may have an idea.
Let be a vector function, defined elementwise in terms of functions :
where is a vector in . We want to find the fixed point such that .
Now let and let be the identity matrix. Then for each define
Somehow, magically (under appropriate conditions on , I presume), the sequence of converge to the fixed point . But I don’t understand where this is coming from, especially the equation for . Most generalizations of Newton’s method that I can find seem to involve multiplying by the inverse of the Jacobian matrix. So what’s going on here? Any ideas/pointers to the literature/etc?