Approximation error: Difference between revisions

Revision as of 14:52, 8 October 2024

Revision as of 04:19, 5 November 2024

Line 2:

{{redirect-distinguish|Absolute error|Absolute deviation}}

{{broader|Approximation}}

[[File:E^x with linear approximation.png|thumb|'''Graph of <math>f(x) = e^x</math> (blue) with its linear approximation <math>P_1(x) = 1 + x</math> (red) at a = 0. The approximation error is the gap between the curves, and it increases for x values further from 0.'''|290x290px]]

The '''[[Approximation]]approximation error''' errorin refersa todata value is the differencediscrepancy between an exact value and itssome [[approximation]] to it. This discrepancyerror can be quantifiedexpressed inas two ways: asan '''absolute error''', which(the measuresnumerical amount of the numericaldiscrepancy) difference,or andas asa '''relative error''', which expresses (the absolute error individed relation toby the truedata value. By understanding both types of errors, we can better assess the accuracy of our estimates and measurements).

An approximation error can occur for a variety of reasons, among them a computing [[machine precision]] or [[measurement error]] (e.g. the length of a piece of paper is 4.53&nbsp;cm but the ruler only allows you to estimate it to the nearest 0.1&nbsp;cm, so you measure it as 4.5&nbsp;cm).

Approximation errors can occur due to various factors, often stemming from limitations in [[Instrumentation|measurement tools]] or computing precision. For example, if a piece of paper measures exactly 4.53 cm, but your ruler only marks the nearest 0.1 cm, you’d record it as 4.5 cm. Similarly, in [[computing]], limitations in machine precision mean numbers are sometimes rounded, leading to small [[discrepancies]]. These errors, while often minor, can affect the accuracy of calculations, especially when accumulated over multiple steps.

In the [[mathematics|mathematical]] field of [[numerical analysis]], the [[numerical stability]] of an [[algorithm]] indicates the extent to which errors in the input of the algorithm will lead to large errors of the output; numerically stable algorithms do not yield a significant error in output when the input is malformed and vice versa.<ref>{{Cite web |last=Weisstein |first=Eric W. |title=Numerical Stability |url=https://mathworld.wolfram.com/ |access-date=2023-06-11 |website=mathworld.wolfram.com |language=en}}</ref>

Line 31:

==Examples==

{{Diophantine_approximation_graph.svg}}

ForAs an example, if the exact value is 50 and wethe approximateapproximation it asis 49.9, then the absolute error is 0.1. Theand the relative error, calculated asis 0.1/50, equals= 0.002, or= 0.2%. As a practical example, when measuring a 6&nbsp;mL beaker, the value read was 5&nbsp;mL. The correct reading being 6&nbsp;mL, this means the percent error in that particular situation is, rounded, 16.7%.

In a practical scenario, consider measuring liquid in a '''6 mL beaker'''. If the reading shows '''5 mL''', but the correct value is 6 mL, the percent error is '''61​≈16.7%'''. This kind of error shows how even small discrepancies can translate into significant percent errors, especially with smaller measurements!

The relative error is often used to compare approximations of numbers of widely differing size; for example, approximating the number 1,000 with an absolute error of 3 is, in most applications, much worse than approximating the number 1,000,000 with an absolute error of 3; in the first case the relative error is 0.003 while in the second it is only&nbsp;0.000003.

There are two important aspectsfeatures of relative error tothat should be kept in remembermind. First, relative error becomesis undefined when the exacttrue value is zero, as thisit would place zeroappears in the denominator (see below). Second, relative error isonly meaningfulmakes onlysense when the values are measured on a [[Level of measurement#Ratio scale|ratio scale—onescale]], that(i.e. a scale which has a true meaningful zero.), Thisotherwise is because relative errorit is sensitive to the measurement units. For instanceexample, when an absolute error in a [[temperature]] measurement withgiven anin absolute[[Celsius errorscale]] ofis 1&nbsp;°C, and athe true value ofis 2&nbsp;°C, has athe relative error ofis 0.5. However, onBut if the exact same approximation is made with the [[Kelvin scale]], the samea 1 &nbsp;K absolute error with athe same true value of 275.15 &nbsp;K (equivalent to= 2&nbsp;°C) results ingives a much smaller relative error of 03.0036363{{e|-3}}.

== Comparison ==

Line 43 ⟶ 41:

== 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''_approx 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''_approx 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''₁ such that |''v''-''r''₁| ≤ |''v''|/2, and hence ''|v|'' ≤ 2 |''r''₁|. If ''r''₁=0, then ''v''=0 and we are done. Since REL is polynomial, the encoding length of ''r''₁ is polynomial in the input. Now, run REL again with relative error ''η=ε/''(2 ''|r''₁|). This yields a rational number ''r''₂ that satisfies |''v''-''r''₂| ≤ ''ε|v''| / (2''r''₁) ≤ ''ε'', so it has absolute error ''ε'' as wished.<ref name=":02" />{{Rp|page=34}}