Re: Convergence Tests - Numerical Algorithms

[Laurent Hoeltgen]

On 01/10/12 17:46, Sergei Steshenko wrote:
> ----- 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.

Which clearly demonstrates that a thorough theoretical analysis 
beforehand can't hurt. Trying to solve a problem that hasn't a solution 
is pointless.

Nevertheless, as the examples above in this thread show, there are bad 
and very bad ways to check whether it's time to stop or not.

> 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.

Thanks for the example.

> Regards,
>    Sergei.
>
>
> >

Regards,
Laurent