Convergence rate of iterated nonlinear equations? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T13:57:30Z http://mathoverflow.net/feeds/question/120602 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/120602/convergence-rate-of-iterated-nonlinear-equations Convergence rate of iterated nonlinear equations? astar 2013-02-02T16:46:13Z 2013-02-04T23:51:22Z <p>For $i=1, \dots, n$ ($n$ could be large) we have variables $x_i$ and $y_i$ relating to probability bounds s.t. $x_i, y_i \geq 0, x_i+y_i \leq 1 \; \forall i$. Each $i$ has a constant $\theta_i$, and some of the pairs $(i,j)$ have a nonzero constant $w_{ij}$ (weight of interaction, positive or negative) in which case say $j \in N(i)$.</p> <p>Let $W_i=\sum_{j \in N(i): w_{ij}>0} w_{ij}$ (sum of positive edges), $V_i=-\sum_{j \in N(i): w_{ij}&lt;0} w_{ij}$ (minus sum of negative edges), $\alpha_{ij} =\exp (|W_{ij}|) -1$.</p> <p>We initialize all $x_i, y_i =0$ then iteratively update as shown below via intermediate variables ${L_i,U_i}$. All iterations are monotonically nondecreasing, $x_i, y_i$ are bounded above hence converge, empirically typically rapidly. </p> <blockquote> <p>Can we prove something on the rate of convergence? (any pointers appreciated)</p> </blockquote> <p>The problem may be easier if we restrict all $w_{ij}>0$, which would still be very helpful, in which case $V_i=0$ and just rewriting the pseudocode below, each iteration sets e.g. new $x_i \leftarrow \left(1 + \frac{\exp(-\theta_i)}{\prod_{j \in N(i)} \left(1 + \frac{\alpha_ij x_j}{1+\alpha_{ij}(1-y_i)(1-x_j)} \right) } \right)^{-1}$.</p> <pre><code>REPEAT until convergence { FOR each i { Li, Ui=1 // Initialize this pass FOR each j \in N(i) { IF w_{ij}&gt;0 { Li *= 1+ \frac{\alpha_{ij} x_j} {1+\alpha_{ij} (1-y_i) (1-x_j)} Ui *= 1+ \frac{\alpha_{ij} y_j} {1+\alpha_{ij} (1-x_i) (1-y_j)} } ELSE { Li *= 1+ \frac{\alpha_{ij} y_j} {1+\alpha_{ij} (1-y_i) (1-y_j)} Ui *= 1+ \frac{\alpha_{ij} x_j} {1+\alpha_{ij} (1-x_i) (1-x_j)} } } x_i = 1 / (1+exp(-\theta_i + V_i)/Li) y_i = 1 / (1+exp(\theta_i + W_i)/Ui) } </code></pre>