help-octave
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Convergence Tests - Numerical Algorithms


From: Laurent Hoeltgen
Subject: Re: Convergence Tests - Numerical Algorithms
Date: Mon, 01 Oct 2012 19:59:07 +0200
User-agent: Mozilla/5.0 (X11; Linux i686; rv:15.0) Gecko/20120912 Thunderbird/15.0.1

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



reply via email to

[Prev in Thread] Current Thread [Next in Thread]