Re: Convergence Tests - Numerical Algorithms

[Laurent Hoeltgen]

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