Questions tagged [error-estimation]
The error-estimation tag has no usage guidance.
38 questions
1
vote
0
answers
19
views
Algorithm for finding relative estimate from absolute estimate
I am trying to find a textbook reference for an algorithm that gives you a relative estimate of a quantity $a$ (i.e. $|a-\overline{a}|\leq \epsilon_{rel} a$) from an algorithm that gives you an ...
- 247
0
votes
2
answers
115
views
How to calculate error bounds for the function behind the following algorithm?
D.E. Knuth, in his infamous The Art of Computer Programming, section 1.2.2, presents the following algorithm to efficiently calculate logarithms based on the method used by Henry Briggs:
Suppose that ...
- 23
8
votes
13
answers
6k
views
Why do we rely on computers in critical fields?
I assume that computers make many mistakes (like errors, bugs, glitches, etc.), which can be observed from the amount of questions asked everyday on different communities (like Stack Overflow) showing ...
- 217
4
votes
1
answer
617
views
Is there some kind of expected error margin for my Monte Carlo algorithm?
My Monte Carlo algorithm starts by placing some circles in the plane with potential overlaps. I then place a large circle somewhere and compute the overlapping area of this larger circle with the ...
- 817
1
vote
1
answer
76
views
Regula falsi with error in x-axis
I want the regula falsi to get x +- .0001 so that f(x) = 0. But all the implemetations I see get x so that f(x) +- .0001 = 0 which doesn't make much sense. (f(x) = x^3).
How do I stop the regula ...
- 47
1
vote
1
answer
184
views
Adaptive step size constrained to a limited number of iterations
I'm solving a differential equation on the form $\ddot x = f( \dot x, x)$ on a microchip within a limited (real world) time frame, hence I want to use an adaptive step size to get as good of a result ...
0
votes
1
answer
533
views
$f(x) = \sqrt{x^{2}+1}-1$ (Loss of Significance)
Let us say that I want to compute $f(x) = \sqrt{x^{2}+1}-1$ for small values of $x$ in a Marc-32 architecture. I can avoid loss of significance by rewriting the function
$$f(x)=\left(\sqrt{x^{2}+1}-1\...
- 124
2
votes
4
answers
131
views
How do compilers assure stability?
Suppose you need a c compiler. It would be preferable to write that compiler in a c-like language, given the complexity of a compiler of that degree. At best, the c compiler would be written in c, but ...
user123355
1
vote
1
answer
51
views
Help comparing relative error for different parenthesizations of addition
I am given two functions:
$ fl(fl(x+y)+z) $ and $ fl(x+fl(y+z)) $ and asked to derive their relative error. Then, given a set of conditions:
a) $ x < y < x $
b) $ x > 0, y < 0, z > 0 $...
- 113
0
votes
0
answers
49
views
minimal distance of a self correcting code
i wonder: how can i find minimal distance of a self correcting code in following situation: if we know that a code can fix every 3 errors(if not more than 3 errors, the word is recovered) and can ...
- 55
2
votes
1
answer
347
views
Numerical issues in solving linear systems
There was an exam in the class. The course is "High Performance Scientific Computing". One of the question in the exam is as follows:
Consider the linear system
$$ \begin{bmatrix} a & b ...
- 143
5
votes
4
answers
938
views
Is order of matrix multiplication affecting numerical accuracy of the result?
I have to multiply three matrices of floats: A (100x8000), B (8000x27) and C (27x1).
Is ...
- 151
1
vote
1
answer
72
views
What does it mean when saying "we want $\Lambda$ to be $\tilde{O}(1)$ as a function of $M$"?
What does it mean when saying "we want $\Lambda$ to be $\tilde{O}(1)$ as a function of $M$"? (it appears on the top of page 12 of this paper)
- 155
4
votes
2
answers
805
views
What does $\tilde{O}_P(N^\alpha)$ mean?
What does $\tilde{O}_P(N^\alpha)$ mean? It appears in an estimation error mention in this paper, in the second paragraph on page 3.
What does big O subscript P mean in a probability context?
- 155
4
votes
2
answers
692
views
Proof that (x-y)(x+y) is more accurate than x²-y²
I was carrying on my reading of What Every Computer Scientist Should Know About Floating-Point Arithmetic but got stuck on the proof of Theorem 2 (page 34).
At some point it says:
\begin{align}
(x \...
- 483
3
votes
1
answer
145
views
Proof that a guard digit bound the error of subtraction
I was reading What Every Computer Scientist Should Know About Floating-Point Arithmetic, which is extremely interesting. But I have some troubles understanding the proof of Theorem 9 (page 33).
First ...
- 483
3
votes
1
answer
63
views
Rigorous error bounds for eigenvalue solvers
I computed the first four eigenvalues of a quite large ($2^{24}\times 2^{24}$) but very sparse matrix. I used pythons in-build function sparse.linalg.eigsh to compute them.
I need a validation that ...
- 131
6
votes
0
answers
365
views
What is the state of the algorithmic art for floating point arithmetic on complex numbers?
Most modern compilers and processors implement the IEEE 754 binary formats for floating point numbers. IEEE 754 guarantees that the addition, subtraction, multiplication, division, and square root ...
- 3,563
1
vote
2
answers
666
views
Addition errors in IEEE754 floating point representation
So in class, we were talking about the idea of floating point precision in IEEE754 format, and how, when some numbers are added, precision is lost. My professor then gave the following example of a ...
- 135
4
votes
0
answers
57
views
Compile-time error control vs. interval arithmetic?
I use interval arithmetic for reliable computing. Now, a procedure coded in a good implementation of interval arithmetic takes perhaps about eight times as much as the same procedure carried out ...
- 241
0
votes
0
answers
53
views
Q-Learning Error Bounds
I have searched a lot for this, but apparently there is no result on calculating any bound on the error $||Q-Q^*||$ when I stop Q-learning after say $N$ iterations ($Q$ is the vector of Q-values at ...
- 175
1
vote
2
answers
355
views
Computing the error bound of floating-point expression
How should I compute the maximum absolute and relative error of the following IEEE-754 floating-point expression?
a.y + (x - a.x) * ((b.y - a.y) / (b.x - a.x))
...
- 187
2
votes
1
answer
778
views
What happens to a file after too many copy-pasting?
Let's say we're talking about a 1 GB video file. It's copy-pasted from hard disk D1 to the hard disk D2, then from D2 to D3, and so on, all using Windows. If we continue this process for like 1 ...
- 71
1
vote
1
answer
114
views
Machine error in computer arithmetic
I'm wondering if if is possible to have a function $f$ such that there exists $x,y$ such that we have $f_t(x) > f_t(y)$ where $f_t$ denotes the true value of $f$ and $f_a(x)<f_a(y)$ where $f_a$ ...
- 121
2
votes
2
answers
2k
views
How to estimate floating-point precision of function?
Let's say I have a function that consists solely of floating-point operations where the last operation rounds the computed value to a predefined number of digits. And I feed this function with a range ...
- 21
1
vote
1
answer
96
views
Which implementation for the Maclaurin Series for the cosine function is better?
First, sorry if this post is off-topic. I consider it too analytic for stack overflow.
In Numerical Analysis subject I must explain which one is better (has less error).
The recursive ...
2
votes
1
answer
1k
views
Avoiding overflows while computing $e^x$ by Taylor series
I'm coding a program to calculate the value of $e^x$ by using the Taylor expansion, that is:
$$ e^x =\sum_{k=0}^\infty \frac{x^k}{k!} $$
...
- 1,493
3
votes
1
answer
1k
views
The stability of log(1+x)
I am trying to understand why the formula
$$ \frac{\log(1+x)}{(1+x)-1} \times x,$$
which simply reduces down to $\log(1+x)$, is considered as more stable to compute than $\log(1+x)$. In my head it ...
- 143
4
votes
2
answers
75
views
Fitting a low-degree polynomial to a function on a finite 1d grid - a combinatorial problem?
I need to fit a low-degree polynomial $p$ (with $\text{deg}(p) \leq k$) to a function $f$ evaluated on the grid $\{0, 1, ... n-1\}$, so as to minimize the $L_\infty$ norm, i.e. minimize $\text{max}_{0 ...
- 1,005
3
votes
2
answers
2k
views
Floating Point Systems - Rounding Error in Taylor series
I have a question about rounding error. I have created a function to approximate exp(x) by summing the terms of its taylor series until the sum stops changing. (That is, 1 + x + x^2/2! ...).
This ...
- 51
3
votes
0
answers
32
views
Numerical Stability of Halley's Recurrence for Integer $n^{\mathrm{th}}$-Root
tl;dr? See last paragraph.
If I use the initial value $2^{\left(\big\lfloor\lfloor\log_2 x \rfloor/n\big\rfloor + 1\right)}$ with Halley's recurrence in the compact form
$ x_{k+1} = \frac{x_k\Big[A\...
- 131
3
votes
2
answers
171
views
How likely is it that a computer miscalculates 1+1? [closed]
Of course, normally a fully-functional computer will calculate 1+1=2. However, the physics governing the behavior of a chip is quantum mechanical. So in principle there is a certain probability that ...
- 131
2
votes
2
answers
81
views
Learning parameters of noise and filter coefficients from data where data and noise both have Gaussian distributions
Assume $X$ and $N$ are two sets of vectors (observations) from a normal distribution, where $X$ represents clean data and $N$ represents noise; and $A$ a projection matrix of a filter. The scenario is ...
- 123
3
votes
0
answers
179
views
Representing Computations on Transcendental Numbers
Consider the set of transcendental numbers that are not compressible to a finite base-2 representation. How can I compute multiples (more generally, any algebraic computation) of one of these numbers,...
- 161
3
votes
2
answers
272
views
Monetary computations theory (manual/textbook)
My problem is due to the fact that I am manipulating a set of amounts that span over some intervals of time (start date/end date) and that are rounded to cents. I have to multiply each of them by some ...
- 133
2
votes
1
answer
89
views
Why is the precision of floating point numbers worse for smaller numbers?
Why is the machine error/epsilon higher between a pair of two lower numbers than a pair of two high numbers? For example, between the two smallest numbers possible in 5 bit mantissa and the two ...
- 21
1
vote
1
answer
95
views
Error estimates of piecewise-linear curve approximations
In order to plot a curve a set of points is usually calculated based on some formula. The function FPLOT in MATLAB also supports plotting with some error tolerance. Its help says the following about ...
8
votes
1
answer
138
views
Is the per-vertex error over a PageRank iteration monotonically decreasing?
It seems to me that taken over the entire graph, the norm of the error vector must be monotonically decreasing, otherwise we couldn't guarantee that PageRank would ever converge.
However, is the same ...
- 265