Convergence rate of iterated nonlinear equations?

2013-02-02T16:46:13Z

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)$.

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}<0} w_{ij}$ (minus sum of negative edges), $\alpha_{ij} =\exp (|W_{ij}|) -1$.

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.

Can we prove something on the rate of convergence? (any pointers appreciated)

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}$.

REPEAT until convergence {
  FOR each i {
    Li, Ui=1 // Initialize this pass
    FOR each j \in N(i) {
      IF w_{ij}>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)
}

Convergence rate of iterated nonlinear equations? - MathOverflow

Convergence rate of iterated nonlinear equations?