2
$\begingroup$

I need to solve following system of nonlinear equations.

Here are some characteristics of this system:
It consists of n equation and n variables.
Every equation is in similar form -> sum of products = constant.
The lenght of every product is the same (it will be denoted as k).
The number of elements in sum might be different in each equation.
In every product in equation $i$ one of elements is $x_{i}$ - this is very important.
This system is "symmetrical", it means that if $x_{i} \cdot x_{j} \cdot ...$ is one of elements of equation i, then it is also in equaton j.
$b_{i} > 0$ - where $b_{i}$ is intercept in equation i.

I'll write an example of such equation for k=3 and n=6:
$x_{1} \cdot x_{3} \cdot x_{6} + x_{1} \cdot x_{2} \cdot x_{4} = b_{1}$
$x_{2} \cdot x_{1} \cdot x_{4} + x_{2} \cdot x_{5} \cdot x_{6} = b_{2}$
$x_{3} \cdot x_{1} \cdot x_{6} + x_{3} \cdot x_{4} \cdot x_{6} = b_{3}$
$x_{4} \cdot x_{1} \cdot x_{2} + x_{4} \cdot x_{3} \cdot x_{6} = b_{4}$
$x_{5} \cdot x_{2} \cdot x_{6} = b_{5}$
$x_{6} \cdot x_{1} \cdot x_{3} + x_{6} \cdot x_{2} \cdot x_{5} + x_{6} \cdot x_{3} \cdot x_{4} = b_{6}$

It is very easy to transform this equation to following form:
$x_{i} = b_{i} / something$ , $x_{i}$ is only on left-hand side of ith equation.

If we have all equation in such form then the fixed point is solution of it.
I've experimentally checked that algorithm analogic to Gauss-Seidel is covergent (i've checked ~100 random examples, and in every case it was convergent).
By analogic to Gauss-Seidel algorithm I mean:
1) Choose any initial solution $[x_{1}^{0} , ... , x_{n}^{0}]$
2.1) Calculate value of $x_{1}^{i+1}$ using $[x_{2}^{i} , ... , x_{n}^{i}]$
2.2) Calculate value of $x_{2}^{i+1}$ using $[x_{1}^{i+1} , ... , x_{n}^{i}]$
...
2.n) Calculate value of $x_{n}^{i+1}$ using $[x_{1}^{i+1} , ... , x_{n-1}^{i+1}]$
3) If solution is good enough stop, otherwise go to 2.1

I've tried Banach fixed point theorem, but is hard to say anything about spectral radius. Does anyone have a clue how to prove convergence of this algorithm?

  • 0
    [This](http://dx.doi.org/10.1137/0703043) and [this](http://dx.doi.org/10.1137/0704017) may have something you can use.2010-12-20
  • 0
    If you just need to solve the system you can try resultants I suppose.2010-12-20
  • 0
    @J.M.: Unfortunately I dont have free access to articles right now, I will be able to download them after christmas, so I cant tell now if they are useful, but thanks anyway. @jerr18: Could You elaborate how resultants can help me in solving this system.2010-12-20
  • 0
    Gröbner is useful here if *exact* solutions are what you need; since you seem to be happy with approximations, your Gauss-Seidel scheme is far simpler than what jerr18 is suggesting.2010-12-20
  • 0
    @J.M: I'm happy with this approximation, but I'd have been even happier if I knew why and when it works. Simple simulations showed that it should be convergent in many cases (in random cases it was always convergent, but it doesn't prove anything).2010-12-21
  • 0
    I suggested those particular papers since as I recall (I'm far away from my copies of those papers) there is a proof of convergence (via Kantorovich I think) for a Gauss-Seidel type iteration for simultaneous nonlinear equations.2010-12-21

1 Answers 1