Given the parameters , a seed, and , the tolerance limit, Soumava's algorithm is as follows:
- [Iterate] While :
- [Output] Return
The proof is cluttered, we could clean it up.
Let be a sequence defined as follows: Furthermore, let be the subsequence formed by the even terms of : Similarly, let be the subsequence formed by the odd terms of : We claim that
We split the proof into two parts. First we prove that the sequences converge, and then we show that the limits satisfy the equation.
= = , = for all where is the set of all positive integers, and is any positive real number (domain of is ).
Let us take the two sub-sequences and that are the sub-sequences formed by the odd numbered terms and by the even numbered terms, respectively.
Let the sequence formed by the odd numbered terms be and the sequence formed by the even numbered terms be
Now we express in terms of . By definition,
Our first observation is that the two sub-sequences that I have considered are both bounded below by and above by itself.
The lower bound is easy to observe because we know that the exponential function is positive for all real and positive . And our sequence is of the exponential form only. So is indeed a lower bound.
Now we can establish the validity of as an upper bound by the method of contradiction.
Let us assume that the sequence contains a number which is greater than itself, i.e. for some in .
But necessarily implies that is less than and greater than i.e. is greater than , and is greater than . All this holds if is less than . But again = .
Now if we take logarithm to the base on both sides, then on LHS we get something negative as belongs to by assumption and is greater than (domain of is ). But on RHS we have which is positive because is positive as the lower bound of the sequence is 0. Thus a negative number on the LHS is equal to a positive number on the RHS by assumption that for some positive integer .
So we have a direct contradiction if for some positive integer , and therefore this assumption must be false. So the negation of this statement must be true. That is ‘ for all positive integers . So we have established that itself is an upper bound.
Our second aim is to prove that these two sub-sequences are monotonic.
Let us consider the sub-sequence and we take , and in general for all .
We know by order property (law of trichotomy) that given two reals and , either , or , or . Here we observe that is not equal to for any positive integer , because of the relation between two consecutive terms of the sequence derived in above.
So or .
Next we proceed by the principle of mathematical induction to show that for all positive integers . In fact we have already checked the first step for .
Next we assume the validity of the statement to hold true for some , i.e. or (where obviously ).
So we have > and > , which implies > for all positive integers .
So is a strictly decreasing monotone sequence.
Having established that, we also see that > i.e. > implies that
Therefore > implies that < . If we consider the sub-sequence consisting of then we have , i.e. . By a similar inductive argument as above, we can see that
is a strictly increasing monotone sequence.
It is to be noted that the conclusions drawn above are under the heading of Case I.
Under this consideration, we proceed exactly as in Case I and prove that is a strictly increasing monotone sequence.
And on the same lines as in Case I, we have that is a strictly decreasing monotone sequence.
- In both the cases which are mutually exhaustive, we see that and are monotone sequences of the opposite nature, i.e. if one is increasing the other is decreasing.
- Also and are sub-sequences of a sequence which is bounded as a whole with as a lower bound and as an upper bound.
- So and themselves are also bounded with as a lower bound for both and as an upper bound for both.
So from 1, 2 and 3 we see that M and T are both monotonic and bounded.
By the Bolzano-Weierstrauss theorem, any monotonic bounded sequence has a finite limit.
Since the sequences and meet the requirements of the theorem, they are convergent and have a finite limit. Let the limit of as tends to be and the limit of as tends to be .
Now, we set out to prove that the limits indeed satisfy the equation:
Because the sequence converges, as , By construction, Similarly,
1 2 3 4 5 6
The convergence rate is most likely exponential.
This section requires expansion