Content deleted Content added
Erel Segal (talk | contribs) |
Erel Segal (talk | contribs) |
||
Line 28:
An '''error bound''' is an upper limit on the relative or absolute size of an approximation error.<ref>{{Cite web |title=Approximation and Error Bounds |url=http://www.math.wpi.edu/Course_Materials/MA1021B98/approx/node1.html#:~:text=Thus%20we%20introduce%20the%20term,bound%20the%20better%20the%20approximation. |access-date=2023-06-11 |website=www.math.wpi.edu}}</ref>
===Generalizations===▼
{{Expand section|date=April 2023}}▼
These definitions can be extended to the case when <math>v</math> and <math>v_{\text{approx}}</math> are [[Euclidean vector|''n''-dimensional vectors]], by replacing the absolute value with an [[norm (mathematics)|''n''-norm]].<ref name="GOLUB_MAT_COMP2.2.3">{{cite book|last=Golub|first=Gene|author-link=Gene H. Golub|author2=Charles F. Van Loan|title=Matrix Computations – Third Edition|publisher=The Johns Hopkins University Press|year=1996|___location=Baltimore|pages=53|isbn=0-8018-5413-X}}▼
</ref>▼
==Examples==
Line 41 ⟶ 36:
There are two features of relative error that should be kept in mind. First, relative error is undefined when the true value is zero as it appears in the denominator (see below). Second, relative error only makes sense when measured on a [[Level of measurement#Ratio scale|ratio scale]], (i.e. a scale which has a true meaningful zero), otherwise it is sensitive to the measurement units. For example, when an absolute error in a [[temperature]] measurement given in [[Celsius scale]] is 1 °C, and the true value is 2 °C, the relative error is 0.5. But if the exact same approximation is made with the [[Kelvin scale]], a 1 K absolute error with the same true value of 275.15 K = 2 °C gives a relative error of 3.63{{e|-3}}.
== Comparison ==
Statements about ''relative errors'' are sensitive to addition of constants, but not to multiplication by constants. For ''absolute errors'', the opposite is true: are sensitive to multiplication by constants, but not to addition of constants.<ref name=":02">{{Cite Geometric Algorithms and Combinatorial Optimization}}</ref>{{Rp|page=34}}
== Polynomial-time approximation of real numbers ==
We say that a real value ''v'' is '''polynomially computable with absolute error''' from an input if, for every rational number ''ε''>0, it is possible to compute a rational number ''v''<sub>approx</sub> that approximates ''v'' with absolute error ''ε'', in time polynomial in the size of the input and the encoding size of ''ε'' (which is O(log(1/''ε'')). Analogously, ''v'' is '''polynomially computable with relative error''' if, for every rational number ''η''>0, it is possible to compute a rational number ''v''<sub>approx</sub> that approximates ''v'' with relative error ''η'', in time polynomial in the size of the input and the encoding size of ''η''.
If ''v'' is polynomially computable with relative error (by some algorithm called REL), then it is also polynomially computable with absolute error. ''Proof''. Let ''ε''>0 be the desired absolute error. First, use REL with relative error ''η=''1/2; find a rational number ''r''<sub>1</sub> such that |''v''-''r''<sub>1</sub>| ≤ |''v''|/2, and hence ''|v|'' ≤ 2 |''r''<sub>1</sub>|. If ''r''<sub>1</sub>=0, then ''v''=0 and we are done. Since REL is polynomial, the encoding length of ''r''<sub>1</sub> is polynomial in the input. Now, run REL again with relative error ''η=ε/''(2 ''|r''<sub>1</sub>|). This yields a rational number ''r''<sub>2</sub> that satisfies |''v''-''r''<sub>2</sub>| ≤ ''ε|v''| / (2''r''<sub>1</sub>) ≤ ''ε'', so it has absolute error ''ε'' as wished.<ref name=":02" />{{Rp|page=34}}
The reverse implication is usually not true. But, if we assume that some positive lower bound on |v| can be computed in polynomial time, e.g. |''v''| > ''b'' > 0, and ''v'' is polynomially computable with absolute error (by some algorithm called ABS), then it is also polynomially computable with relative error, since we can simply call ABS with absolute error ''ε = η b.''
An algorithm that, for every rational number ''η''>0, computes a rational number ''v''<sub>approx</sub> that approximates ''v'' with relative error ''η'', in time polynomial in the size of the input and 1/''η'' (rather than log(1/''η'')), is called an [[FPTAS]].
==Instruments==
In most indicating instruments, the accuracy is guaranteed to a certain percentage of full-scale reading. The limits of these deviations from the specified values are known as limiting errors or guarantee errors.<ref>Helfrick, Albert D. (2005) ''Modern Electronic Instrumentation and Measurement Techniques''. p. 16. {{ISBN|81-297-0731-4}}</ref>
▲{{Expand section|date=April 2023}}
▲
▲</ref>
==See also==
| |||