Revisions to Convergence of iterative algorithm.

added 444 characters in body; added 2 characters in body

Source Link

edited Feb 7, 2010 at 10:15

65
1
6

For quite a long time I'm trying to prove convergence of an iterative algorithm in case of a particular 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 (it just need to be divided once).
$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:

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}]$
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?

Edited 7.02.2009 11:09
I've found another restriction. If we denote by $m$ number of all products (in this example it would be 12, becuase in 1st,2nd,3th,4th we have 2 products, in 5th we have 1, and in 6th we have 3). Then following equation is true:
$m = k \cdot \sum_{i=1}^{n}{b_{i}}$ Which also implies thah $\sum_{i=1}^{n}{b_{i}}$ is a natural number (from the symmetry), but it doesn't imply that any of $b_{i}$ is natural.

For quite a long time I'm trying to prove convergence of an iterative algorithm in case of a particular 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 (it just need to be divided once).
$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:

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}]$
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?

For quite a long time I'm trying to prove convergence of an iterative algorithm in case of a particular 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 (it just need to be divided once).
$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:

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}]$
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?

Edited 7.02.2009 11:09
I've found another restriction. If we denote by $m$ number of all products (in this example it would be 12, becuase in 1st,2nd,3th,4th we have 2 products, in 5th we have 1, and in 6th we have 3). Then following equation is true:
$m = k \cdot \sum_{i=1}^{n}{b_{i}}$ Which also implies thah $\sum_{i=1}^{n}{b_{i}}$ is a natural number (from the symmetry), but it doesn't imply that any of $b_{i}$ is natural.