I had a problem in the form

$$ \left( \begin{array} xx_1 \\ x_2 \\ ... \\ x_n \end{array} \right) = \left( \begin{array} FF_1(x_2,...,x_n) \\ F_2(x_1,x_3...,x_n) \\ ... \\ F_n(x_2,...,x_{n-1}) \end{array} \right)$$

and I tried to solve this problem using fixed-point iteration as:

$$ \left( \begin{array} xx_1^{k+1} \\ x_2^{k+1} \\ ... \\ x_n^{k+1} \end{array} \right) = \left( \begin{array} FF_1(x_2^{k},...,x_n^{k}) \\ F_2(x_1^{k},x_3^{k}...,x_n^{k}) \\ ... \\ F_n(x_2^{k},...,x_{n-1}^{k}) \end{array} \right)$$

The problem is that it didn't converge. So I evaluated the Jacobian and its norm was >1, this explains why the procedure does not converged. I tried to do the fixed-point iterations in a Gauss-Seidel style, re-using pre-calculated values. Fortunately, the algorithm converges.

$$ \left( \begin{array} xx_1^{k+1} \\ x_2^{k+1} \\ ... \\ x_n^{k+1} \end{array} \right) = \left( \begin{array} FF_1(x_2^{k},...,x_n^{k}) \\ F_2(x_1^{k+1},x_3^{k}...,x_n^{k}) \\ ... \\ F_n(x_2^{k+1},...,x_{n-1}^{k+1}) \end{array} \right)$$

The problem is that I don't know the reason why this method converges, how do I find a condition for the convergence? I tried to evaluate the Jacobian of the system but the norm was >1, so (unless errors in the evaluation) this algorithm should not converge. To evaluate the jacobian I calculated the derivatives of functions $F$ by considering that (k+1) terms are in reality functions. For instance:

$$ J_{2,1} = \frac{\delta F_2(x_1^{k+1},x_3^{k}...,x_n^{k})}{\delta x_1^{k}} = \frac{\delta F_2(F_1(x_2^{k},...,x_n^{k}),x_3^{k}...,x_n^{k})}{\delta x_1^{k}} $$

and so on for all the terms. What happens is that the first row of the Jacobian is the same of previous matrix, but the other terms change. Finally the norm is still >1 so the method appear non-convergent. Something should be wrong in my evaluation, the implemented algorithm converges.


The procedure described in this question is correct, the reason for such non convergent behavior was that the fixed point was far from the position at which the norm does not provide convergence. Indeed, even if chosen as starting point, the method may initially diverge. This cause the method to go far from the initial point but closer to the solution and/or to a point in which the Jacobian is compatible with convergence condition.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.