Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

So right now I'm working on an algorithm which has to know when to terminate its calculations - namely, it should do it when the number he's acquired in the last step is at least as precise as the user wanted the result to be. Providing I can't just change the number to a stirng and check each character from given till the end or use some functions checking length of the number, how can I do this?

I mean: in $k$-th step we get $x_i=1.548168$. The wanted precision is $p=10^{-4}$. How can I check that there in fact is something present on the 4th place after the dot or farer?

share|improve this question
    
You haven't mentioned what algorithm you're doing. If, say, you're summing an infinite sum, you might want to watch out for the possibility that some of the terms are zero. –  J. M. May 3 '13 at 17:42
    
I'm doing Romberg's integration and want to let the algorithm know that as soon as the last term in a row has acquired the given precision, it can stop further computations. –  Straightfw May 3 '13 at 17:45
    
Should've mentioned that to begin with. In the particular version of Romberg I am accustomed to, the successive extrapolations are implemented as adding successive small corrections to previous estimates. In that case, you just check if the next correction to be added is tinier than your tolerance. –  J. M. May 3 '13 at 17:48

2 Answers 2

First, be sure that your internal precision is larger than the precision the user could ever possibly want.

There is no simple answer. As your algorithm is working, it's producing a sequence of approximations $x_i$ which converge to the optimal result $x$: $\lim_{i\to\infty}x_i=x$. But unless you know something about the algorithm, you never know when you can stop - after producing $i$ numbers you have no guarantee that $x_{i+1}$ doesn't jump off suddenly.

I'd say the only reasonable way is to modify your algorithm so that it doesn't produce a sequence of approximations, but a sequence of intervals $[y_i,z_i]$ such that $[y_{i+1},z_{i+1}]\subseteq [y_i,z_i]$ and $\lim_{i\to\infty} z_i-y_i = 0$. This way, when your interval is small enough you know you've reached the desired precision


To illustrate it, let's suppose you're computing an approximation of a number given as a infinite continued fraction. Then we know that

  • The even convergents (before the $n$th) continually increase, but are always less than $x_n$.
  • The odd convergents (before the $n$th) continually decrease, but are always greater than $x_n$.

So you always know that the limit is between $x_n$ and $x_{n-1}$.


Perhaps post more details about your algorithm.

share|improve this answer
    
Thank you very much and sorry I haven't mentioned it earlier - I'm doing Romberg's integration and want to let the algorithm know that as soon as the last term in a row has acquired the given precision, it can stop further computations. –  Straightfw May 3 '13 at 17:51
    
@Straightfw Looking at the trapezium rule the error is given as $$-\frac{(b-a)^3}{12N^2} f''(\xi)$$ for some $\xi\in [a,b]$. So you need to know a bound on $f''$ on the interval, and then you'll know the margin of error explicitly. If you don't have such a bound, but you know the function is monotone, you can use the rectangle rule, compute the top-left corner approximation and top-right corner one, and you'll know the result is in between (see the image on the Wiki page). –  Petr Pudlák May 3 '13 at 18:08

Typically you just test whether $|x_{i-1}-x_i|<p$.

share|improve this answer
1  
That only works if you know the algorithm is converging fast enough. For example if the $i$-th approximation would be $i^{-0.01}$ then your criterion will stop roughly at $\lceil 1/p\rceil$, which is still very far from 0. –  Petr Pudlák May 3 '13 at 17:43

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.