Approximation error: Difference between revisions

Revision as of 11:20, 27 March 2024

Latest revision as of 21:11, 13 August 2025

(8 intermediate revisions by 7 users not shown)

Line 1:

{{Short description|Mathematical concept}}

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

{{redirect-distinguish|Relative error|Relative change}}

{{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, isvisually represented as the vertical gap between the two curves, and itdemonstrably increases for values of x valuesthat are positioned further from the point of approximation, which in this case is x = 0.]]

The '''approximation error''' in a given data value isrepresents the significant discrepancy betweenthat arises when an exact, true value andis compared against some [[approximation]] toderived for it. This inherent error in approximation can be quantified and expressed in two principal ways: as an '''absolute error''', which denotes (the direct numerical amountmagnitude of thethis discrepancy) irrespective of the true value's scale, or as a '''relative error''', which provides a scaled measure of the error by considering (the absolute error dividedin byproportion to the exact data value), thus offering a context-dependent assessment of the error's significance.

An approximation error can occurmanifest fordue to a varietymultitude of diverse reasons,. Prominent among themthese aare limitations related to computing [[machine precision]], where digital systems cannot represent all real numbers with perfect accuracy, leading to unavoidable truncation or rounding. Another common source is inherent [[measurement error]], stemming from the practical limitations of instruments, environmental factors, or observational processes (e.g.for instance, if the actual length of a piece of paper is precisely 4.53&nbsp;cm, but the measuring ruler only allows you topermits estimatean itestimation to the nearest 0.1&nbsp;cm, sothis youconstraint measurecould itlead asto a recorded measurement of 4.5&nbsp;cm, thereby introducing an error).

In the [[mathematics|mathematical]] field of [[numerical analysis]], the crucial concept of [[numerical stability]] ofassociated with an [[algorithm]] indicatesserves to indicate the extent to which initial errors or perturbations present in the input data of the algorithm willare leadlikely to largepropagate and potentially amplify into substantial errors ofin the final output;. Algorithms that are characterized as numerically stable algorithmsare robust in the sense that they do not yield a significantsignificantly magnified error in their output even when the input is slightly malformed andor contains minor inaccuracies; conversely, numerically unstable algorithms may exhibit dramatic error growth from small input changes, rendering their viceresults versaunreliable.<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>

==Formal definition==

Given some true or exact value ''v'', we sayformally state that an approximation ''v''_approx approximatesestimates or represents ''v'' withwhere the magnitude of the '''absolute error''' is bounded by a positive value ''ε'' (i.e., ''ε''>0), if the following inequality holds: <ref>{{Cite web |last=Weisstein |first=Eric W. |title=Absolute Error |url=https://mathworld.wolfram.com/ |access-date=2023-06-11 |website=mathworld.wolfram.com |language=en}}</ref><ref name=":0">{{Cite web |title=Absolute and Relative Error {{!}} Calculus II |url=https://courses.lumenlearning.com/calculus2/chapter/absolute-and-relative-error/ |access-date=2023-06-11 |website=courses.lumenlearning.com}}</ref>

:<math>|v-v_\text{approx}| \leq \varepsilon</math>

where the vertical bars, | |, unambiguously denote the [[absolute value]] of the difference between the true value ''v'' and its approximation ''v''_approx. This mathematical operation signifies the magnitude of the error, irrespective of whether the approximation is an overestimate or an underestimate.

where the vertical bars denote the [[absolute value]].

WeSimilarly, we saystate that ''v''_approx approximates the value ''v'' withwhere the magnitude of the '''relative error''' is bounded by a positive value ''η'' (i.e., ''η''>0), provided ''v'' is not zero (''v'' ≠ 0), if the subsequent inequality is satisfied:<blockquote><math>|v-v_\text{approx}| \leq \eta\cdot |v|</math>.</blockquote>This definition ensures that ''η'' acts as an upper bound on the ratio of the absolute error to the magnitude of the true value. If ''v'' ≠ 0, then the actual '''relative error''', often also denoted by ''η'' in context (representing the calculated value rather than a bound), is precisely calculated as:

:<math> \eta = \frac{|v-v_\epsilontext{approx}|}{|v|}

= \left| \frac{v-v_\text{approx}}{v} \right|

= \left| 1 - \frac{v_\text{approx}}{v} \right|

</math>.

Note that the first term in the equation above implicitly defines `ε` as `|v-v_approx|` if `η` is `ε/|v|`.

The '''percent error''', (anoften expressiondenoted as ''δ'', is a common and intuitive way of expressing the relative error), iseffectively scaling the relative error value to a percentage for easier interpretation and comparison across different contexts: <ref name=":0" />

:<math>\delta = 100\%\times\eta = 100\%\times\left| \frac{v-v_\text{approx}}{v} \right|.</math>

An '''error bound''' isrigorously defines an established upper limit on either the relative or the absolute sizemagnitude of an approximation error. Such a bound thereby provides a formal guarantee on the maximum possible deviation of the approximation from the true value, which is critical in applications requiring known levels of precision.<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>

==Examples==

{{Diophantine_approximation_graph.svg}}

AsTo anillustrate these concepts with a numerical example, ifconsider an instance where the exact, accepted value is 50, and theits corresponding approximation is determined to be 49.9,. thenIn this particular scenario, the absolute error is precisely 0.1 (calculated as |50 − 49.9|), and the relative error is calculated as the absolute error 0.1/ divided by the true value 50, =which equals 0.002. =This relative error can also be expressed as 0.2%. AsIn a more practical examplesetting, such as when measuring the volume of liquid in a 6&nbsp;mL beaker, if the valueinstrument readreading wasindicates 5&nbsp;mL. Thewhile correctthe readingtrue beingvolume is actually 6&nbsp;mL, this means the percent error infor thatthis particular measurement situation is, when rounded to one decimal place, approximately 16.7% (calculated as |(6&nbsp;mL − 5&nbsp;mL) / 6&nbsp;mL| × 100%).

The utility of relative error isbecomes oftenparticularly usedevident when it is employed to compare approximationsthe quality of approximations for numbers ofthat possess widely differing sizemagnitudes; for example, approximating the number 1,000 with an absolute error of 3 results in a relative error of 0.003 (or 0.3%). This is, inwithin the context of most scientific or engineering applications, muchconsidered worsea significantly less accurate approximation than approximating the much larger number 1,000,000 with an identical absolute error of 3;. inIn the latter case, the relative error is a mere 0.000003 (or 0.0003%). In the first case, the relative error is 0.003, whilewhereas in the second, more favorable scenario, it is a substantially smaller value of only&nbsp; 0.000003. This comparison clearly highlights how relative error provides a more meaningful and contextually appropriate assessment of precision, especially when dealing with values across different orders of magnitude.

There are two crucial features or caveats associated with the interpretation and application of relative error that should always be kept in mind. FirstFirstly, relative error isbecomes mathematically undefined whenwhenever the true value (''v'') is zero, asbecause itthis true value appears in the denominator of its calculation (seeas belowdetailed in the formal definition provided above), and division by zero is an undefined operation. SecondSecondly, the concept of relative error onlyis makesmost sensetruly meaningful and consistently interpretable only when measuredthe measurements under consideration are performed on a [[Level of measurement#Ratio scale|ratio scale]], (i.e. aThis type of scale whichis characterized hasby possessing a true, meaningfulnon-arbitrary zero) point, otherwisewhich itsignifies the complete absence of the quantity being measured. If this condition of a ratio scale is not met (e.g., when using interval scales like Celsius temperature), the calculated relative error can become highly sensitive to the choice of measurement units, potentially leading to misleading interpretations. For example, when an absolute error in a [[temperature]] measurement given in the [[Celsius scale]] is 1&nbsp;°C, and the true value is 2&nbsp;°C, the relative error is 0.5. (or But50%, calculated as |1°C / 2°C|). However, if thethis exact same approximation, representing the same physical temperature difference, is made withusing the [[Kelvin scale]] (which is a ratio scale where 0&nbsp;K represents absolute zero), a 1&nbsp;K absolute error (equivalent in magnitude to a 1&nbsp;°C error) with the same true value of 275.15&nbsp;K =(which is equivalent to 2&nbsp;°C) gives a markedly different relative error of approximately 0.00363, or about 3.63{{e|-3}} (calculated as |1&nbsp;K / 275.15&nbsp;K|). This disparity underscores the importance of the underlying measurement scale.

== Comparison ==

When comparing the behavior and intrinsic characteristics of these two fundamental error types, it is important to recognize their differing sensitivities to common arithmetic operations. Specifically, statements and conclusions made about ''relative errors'' are notably sensitive to the addition of a non-zero constant to the underlying true and approximated values, as such an addition alters the base value against which the error is relativized, thereby changing the ratio. However, relative errors remain unaffected by the multiplication of both the true and approximated values by the same non-zero constant, because this constant would appear in both the numerator (of the absolute error) and the denominator (the true value) of the relative error calculation, and would consequently cancel out, leaving the relative error unchanged. Conversely, for ''absolute errors'', the opposite relationship holds true: absolute errors are directly sensitive to the multiplication of the underlying values by a constant (as this scales the magnitude of the difference itself), but they are largely insensitive to the addition of a constant to these values (since adding the same constant to both the true value and its approximation does not change the difference between them: (''v''+c) − (''v''_approx+c) = ''v'' − ''v''_approx).<ref name=":02">{{Cite Geometric Algorithms and Combinatorial Optimization}}</ref>{{Rp|page=34}}

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 ==

WeIn saythe realm of [[computational complexity theory]], we define that a real value ''v'' is '''polynomially computable with absolute error''' from ana given input if, for everyany specified rational number ''ε'' > 0 representing the desired maximum permissible absolute error, it is algorithmically possible to compute a rational number ''v''_approx such that ''v''_approx approximates ''v'' with an absolute error no greater than ''ε'' (formally, in|''v'' − ''v''_approx| ≤ ''ε''). Crucially, this computation must be achievable within a time duration that is polynomial in terms of the size of the input data and the encoding size of ''ε'' (whichthe islatter typically being of the order O(log(1/''ε'')). bits, reflecting the number of bits needed to represent the precision). Analogously, the value ''v'' is considered '''polynomially computable with relative error''' if, for everyany specified rational number ''η'' > 0 representing the desired maximum permissible relative error, it is possible to compute a rational number ''v''_approx that approximates ''v'' with a relative error no greater than ''η'' (formally, |(''v'' − ''v''_approx)/''v''| ≤ ''η'', assuming ''v'' ≠ 0). This computation, similar to the absolute error case, must likewise be achievable in an amount of time that is polynomial in the size of the input data and the encoding size of ''η''. (which is typically O(log(1/''η'')) bits).

IfIt can be demonstrated that if a value ''v'' is polynomially computable with relative error (byutilizing somean algorithm calledthat we can designate as REL), then it is consequently also polynomially computable with absolute error. ''Proof sketch''.: Let ''ε'' > 0 be the desiredtarget maximum absolute error that we wish to achieve. First,The useprocedure commences by invoking the REL algorithm with a chosen relative error bound of, for example, ''η='' = 1/2;. This initial step aims to find a [[rational number]] approximation ''r''₁ such that the inequality |''v''- − ''r''₁| ≤ |''v''|/2 holds true. From this relationship, andby henceapplying the reverse triangle inequality (|''v''| − |''r''₁| ≤ |''v'' − ''r''₁|), we can deduce that |''v''| ≤ 2 |''r''₁|. If(this holds assuming ''r''₁ ≠ 0; if ''r''₁ = 0, then the relative error condition implies ''v'' must also be 0, in which case the problem of achieving any absolute error ''ε'' > 0 is trivial, as ''v''_approx = 0 works, and we are done). SinceGiven that the REL isalgorithm operates in polynomial time, the encoding length of the computed ''r''₁ iswill necessarily be polynomial inwith respect to the input size. NowSubsequently, runthe REL againalgorithm is invoked a second time, now with a new, typically much smaller, relative error target set to ''η{{'}}'' = ''ε/'' / (2 |''|r''₁|) (this step also assumes ''r''₁ is non-zero, which we can ensure or handle as a special case). This second application of REL yields aanother rational number approximation, ''r''₂, that satisfies the condition |''v''- − ''r''₂| ≤ ''εη{{'}}''|''v''|. Substituting the expression for ''η{{'}}'' gives |''v'' − ''r''₂| ≤ (''ε'' / (2|''r''₁|)) |''v''|. Now, using the previously derived inequality |''v''| ≤ 2|''r''₁|, we can bound the term: |''v'' − ''r''₂| ≤ (''ε'' / (2|''r''₁|)) × (2|''r''₁|) = ''ε''. Thus, sothe itapproximation has''r''₂ successfully approximates ''v'' with the desired absolute error ''ε'', asdemonstrating wishedthat polynomial computability with relative error implies polynomial computability with absolute error.<ref name=":02" />{{Rp|page=34}}

The reverse implication, namely that polynomial computability with absolute error implies polynomial computability with relative error, is usuallygenerally not true without imposing additional conditions or assumptions. ButHowever, a significant special case exists: if weone can assume that some positive lower bound ''b'' on |v|the canmagnitude beof computed in polynomial time,''v'' (i.e.g., |''v''| > ''b'' > 0) can itself be computed in polynomial time, and if ''v'' is also known to be polynomially computable with absolute error (byperhaps somevia an algorithm calleddesignated as ABS), then it is''v'' also becomes polynomially computable with relative error,. sinceThis weis because one can simply callinvoke the ABS algorithm with a carefully chosen target absolute error, specifically ''ε_target'' = ''ηb'', where ''η'' is the desired relative error. The resulting approximation ''v''_approx would satisfy |''v'' − ''v''_approx| ≤ ''ηb''. To see the implication for relative error, we divide by |''v''| (which is non-zero): |(''v'' − ''v''_approx)/''v''| ≤ (''ηb'')/|''v''|. Since we have the condition |''v''| > ''b'', it follows that ''b''/|''v''| < 1. Therefore, the relative error is bounded by ''η'' × (''b''/|''v''|) < ''η'' × 1 = ''η'', which is the desired outcome for polynomial computability with relative error.

An algorithm that, for every given rational number ''η'' > 0, successfully computes a rational number ''v''_approx that approximates ''v'' with a relative error no greater than ''η'', and critically, does so in a time complexity that is polynomial in both the size of the input and in the reciprocal of the relative error, 1/''η'' (rather than being polynomial merely in log(1/''η''), which typically allows for faster computation when ''η'' is extremely small), is calledknown anas a [[Fully Polynomial-Time Approximation Scheme|Fully Polynomial-Time Approximation Scheme (FPTAS)]]. The dependence on 1/''η'' rather than log(1/''η'') is a defining characteristic of FPTAS and distinguishes it from weaker approximation schemes.

==Instruments==

In the context of most indicating measurement instruments, such as analog or digital voltmeters, pressure gauges, and thermometers, the specified accuracy is frequently guaranteed toby their manufacturers as a certain percentage of the instrument's full-scale reading capability, rather than as a percentage of the actual reading. The defined boundaries or limits of these permissible deviations from the true or specified values under operational conditions are knowncommonly referred to as limiting errors or, alternatively, guarantee errors. This method of specifying accuracy implies that the maximum possible absolute error can be larger when measuring values towards the higher end of the instrument's scale, while the relative error with respect to the full-scale value itself remains constant across the range. Consequently, the relative error with respect to the actual measured value can become quite large for readings at the lower end of the instrument's scale.<ref>Helfrick, Albert D. (2005) ''Modern Electronic Instrumentation and Measurement Techniques''. p. 16. {{ISBN|81-297-0731-4}}</ref>

== Generalizations ==

{{Expand section|date=April 2023}}

The fundamental definitions of absolute and relative error, as presented primarily for scalar (one-dimensional) values, can be naturally and rigorously extended to more complex scenarios where the casequantity of wheninterest <math>v</math> and its corresponding approximation <math>v_{\text{approx}}</math> are [[Euclidean vector|''n''-dimensional vectors]], matrices, or, more generally, elements of a [[normed vector space]]. This important generalization is typically achieved by systematically replacing the [[absolute value]] function (which effectively measures magnitude or "size" for scalar numbers) with an appropriate [[norm (mathematics)|vector ''n''-norm]] or [[matrix norm]]. Common examples of such norms include the L₁ norm (sum of absolute component values), the L₂ norm (Euclidean norm, or square root of the sum of squared components), and the L_∞ norm (maximum absolute component value). These norms provide a way to quantify the "distance" or "difference" between the true vector (or matrix) and its approximation in a multi-dimensional space, thereby allowing for analogous definitions of absolute and relative error in these higher-dimensional contexts.<ref name="GOLUB_MAT_COMP2.2.3">{{cite book |last=Golub |first=Gene |title=Matrix Computations – |edition=Third Edition |author2=Charles F. Van Loan |publisher=The Johns Hopkins University Press |year=1996 |isbn=0-8018-5413-X |___location=Baltimore |pages=53 |author-link=Gene H. Golub}}

</ref>