Re: Convergence Tests - Numerical Algorithms

[Sergei Steshenko]

----- Original Message -----
> From: Laurent Hoeltgen <address@hidden>
> To: address@hidden
> Cc: 
> Sent: Monday, October 1, 2012 5:13 PM
> Subject: Re: Convergence Tests - Numerical Algorithms
> 
> On 30/09/12 00:04, Joza wrote:
>>  This doesn't apply strictly to Octave, but I think it is relevant.
>> 
>>  I have been looking at convergence tests, for example, in computing the 
> root
>>  or the fixed point of a function. Often, a rather crude test is used, such
>>  as
>> 
>>  IF  absolute_value(  x_k  -  x_k-1  )  <=  10^-6  STOP
>> 
>>  where x_k is the kth term in the series. But this is dangerously naive, for
>>  if say x_k = 10^12, then the next number around x_k is
>>  machine_epsilon*absolute_value( x_k ) = 10^-4, so the test can never be
>>  true.
>> 
>>  I understand this quite well. Yet I've come two tests which are used as 
> the
>>  best for general numerical algorithms, and I cannot understand them:
>> 
>>  BETTER:
>>  IF  absolute_value(  x_k  -  x_k-1  )  <=
>>  4.0*machine_epsilon*absolute_value(x_k)
>> 
>>  BEST:
>>  IF  absolute_value(  x_k  -  x_k-1  )  <= E_tol
>>  4.0*machine_epsilon*absolute_value(x_k)
>> 
>>  where E_tol is a tolerance value. Why the factor of 4? Why the E_tol, and
>>  what is it? And why is the last one the best?
>> 
>>  I hope someone can explain this, and these tests mystify me!
>> 
>>  Thanks,
>>  Joza
>> 
>> 
>> 
>>  --
>>  View this message in context: 
> http://octave.1599824.n4.nabble.com/Convergence-Tests-Numerical-Algorithms-tp4644779.html
>>  Sent from the Octave - General mailing list archive at Nabble.com.
>>  _______________________________________________
>>  Help-octave mailing list
>>  address@hidden
>>  https://mailman.cae.wisc.edu/listinfo/help-octave
>> 
> 
> Hi,
> 
> Just out of pure interest (I'm currently working on a number of 
> iterative algorithms). Do you have any references where they present 
> some theory (or general guidelines) for chosing stopping criteria for 
> fix point iterations?
> 
> Regards,
> Laurent
> 
> _______________________________________________
> Help-octave mailing list
> address@hidden
> https://mailman.cae.wisc.edu/listinfo/help-octave


First of all, all such tests are moot and dangerous, i.e. one has to be 
completely aware of what he/she and the mathematical problem are doing.


A trivial example is the following sum:

1 + 1/2 + 1/3 + 1/4 ... + 1/N
.

IIRC, this sum grows with log(N) speed, i.e. is _infinite_ for infinite N.

However, each new step adds smaller and smaller contribution, so any test 
comparing abs(x(k) and x(k-1)) and tolerance will prematurely stop iterations 
yielding in this case conceptually wrong finite result.


Anyway, I often use the following:

if(abs(x(k)) < threshold && (abs(x(k) - abs(x(k+1))) < abs_tolerance) || 
(abs(x(k) >= threshold) && abs((x(k) - x(k+1)) / x(k)) < rel_tolerance))
  # end iterations
endif

- the above is not logically optimized, but is meant to better illustrate the 
idea - I hope you'll get the idea yourselves.


Regards,
  Sergei.
















>