In computing, a roundoff error,[1] also called rounding error,[2] is the difference between the result produced by a given algorithm using exact arithmetic and the result produced by the same algorithm using finite-precision, rounded arithmetic.[3] Rounding errors are due to inexactness in the representation of real numbers and the arithmetic operations done with them. This is a form of quantization error.[4] When using approximation equations or algorithms, especially when using finitely many digits to represent real numbers (which in theory have infinitely many digits), one of the goals of numerical analysis is to estimate computation errors.[5] Computation errors, also called numerical errors, include both truncation errors and roundoff errors.

When a sequence of calculations with an input involving any roundoff error are made, errors may accumulate, sometimes dominating the calculation. In ill-conditioned problems, significant error may accumulate.[6]

In short, there are two major facets of roundoff errors involved in numerical calculations:[7]

  1. The ability of computers to represent both magnitude and precision of numbers is inherently limited.
  2. Certain numerical manipulations are highly sensitive to roundoff errors. This can result from both mathematical considerations as well as from the way in which computers perform arithmetic operations.

Representation error

The error introduced by attempting to represent a number using a finite string of digits is a form of roundoff error called representation error.[8] Here are some examples of representation error in decimal representations:

Notation Representation Approximation Error
1/7 0.142 857 0.142 857 0.000 000 142 857
ln 2 0.693 147 180 559 945 309 41... 0.693 147 0.000 000 180 559 945 309 41...
log10 2 0.301 029 995 663 981 195 21... 0.3010 0.000 029 995 663 981 195 21...
32 1.259 921 049 894 873 164 76... 1.25992 0.000 001 049 894 873 164 76...
2 1.414 213 562 373 095 048 80... 1.41421 0.000 003 562 373 095 048 80...
e 2.718 281 828 459 045 235 36... 2.718 281 828 459 045 0.000 000 000 000 000 235 36...
π 3.141 592 653 589 793 238 46... 3.141 592 653 589 793 0.000 000 000 000 000 238 46...

Increasing the number of digits allowed in a representation reduces the magnitude of possible roundoff errors, but any representation limited to finitely many digits will still cause some degree of roundoff error for uncountably many real numbers. Additional digits used for intermediary steps of a calculation are known as guard digits.[9]

Rounding multiple times can cause error to accumulate.[10] For example, if 9.945309 is rounded to two decimal places (9.95), then rounded again to one decimal place (10.0), the total error is 0.054691. Rounding 9.945309 to one decimal place (9.9) in a single step introduces less error (0.045309). This can occur, for example, when software performs arithmetic in x86 80-bit floating-point and then rounds the result to IEEE 754 binary64 floating-point.

Floating-point number system

Compared with the fixed-point number system, the floating-point number system is more efficient in representing real numbers so it is widely used in modern computers. While the real numbers are infinite and continuous, a floating-point number system is finite and discrete. Thus, representation error, which leads to roundoff error, occurs under the floating-point number system.

Notation of floating-point number system

A floating-point number system is characterized by integers:

Any has the following form:

where is an integer such that for , and is an integer such that .

Normalized floating-number system

IEEE standard

In the IEEE standard the base is binary, i.e. , and normalization is used. The IEEE standard stores the sign, exponent, and significand in separate fields of a floating point word, each of which has a fixed width (number of bits). The two most commonly used levels of precision for floating-point numbers are single precision and double precision.

Precision Sign (bits) Exponent (bits) Trailing Significand field (bits)
Single 1 8 23
Double 1 11 52

Machine epsilon

Machine epsilon can be used to measure the level of roundoff error in the floating-point number system. Here are two different definitions.[3]

Roundoff error under different rounding rules

There are two common rounding rules, round-by-chop and round-to-nearest. The IEEE standard uses round-to-nearest.

x Round-by-chop Roundoff Error Round-to-nearest Roundoff Error
1.649 1.6 0.049 1.6 0.049
1.650 1.6 0.050 1.6 0.050
1.651 1.6 0.051 1.7 -0.049
1.699 1.6 0.099 1.7 -0.001
1.749 1.7 0.049 1.7 0.049
1.750 1.7 0.050 1.8 -0.050

Calculating roundoff error in IEEE standard

Suppose the usage of round-to-nearest and IEEE double precision.

Since the 53-rd bit to the right of the binary point is a 1 and is followed by other nonzero bits, the round-to-nearest rule requires rounding up, that is, add 1 bit to the 52-nd bit. Thus, the normalized floating-point representation in IEEE standard of 9.4 is

This representation is derived by discarding the infinite tail

from the right tail and then added in the rounding step.

Then .
Thus, the roundoff error is .

Measuring roundoff error by using machine epsilon

The machine epsilon can be used to measure the level of roundoff error when using the two rounding rules above. Below are the formulas and corresponding proof.[3] The first definition of machine epsilon is used here.

Theorem

  1. Round-by-chop:
  2. Round-to-nearest:

Proof

Let where , and let be the floating-point representation of . Since round-by-chop is being used, it is

In order to determine the maximum of this quantity, there is a need to find the maximum of the numerator and the minimum of the denominator. Since (normalized system), the minimum value of the denominator is . The numerator is bounded above by . Thus, . Therefore, for round-by-chop. The proof for round-to-nearest is similar.

Roundoff error caused by floating-point arithmetic

Even if some numbers can be represented exactly by floating-point numbers and such numbers are called machine numbers, performing floating-point arithmetic may lead to roundoff error in the final result.

Addition

Machine addition consists of lining up the decimal points of the two numbers to be added, adding them, and then storing the result again as a floating-point number. The addition itself can be done in higher precision but the result must be rounded back to the specified precision, which may lead to roundoff error.[3]

This example shows that roundoff error can be introduced when adding a large number and a small number. The shifting of the decimal points in the significands to make the exponents match causes the loss of some of the less significant digits. The loss of precision may be described as absorption.[11]

Note that the addition of two floating-point numbers can produce roundoff error when their sum is an order of magnitude greater than that of the larger of the two.

This kind of error can occur alongside an absorption error in a single operation.

Multiplication

In general, the product of two p-digit significands contains up to 2p digits, so the result might not fit in the significand.[3] Thus roundoff error will be involved in the result.

Division

In general, the quotient of 2p-digit significands may contain more than p-digits.Thus roundoff error will be involved in the result.

Subtraction

Absorption also applies to subtraction.

The subtracting of two nearly equal numbers is called subtractive cancellation.[3] When the leading digits are cancelled, the result may be too small to be represented exactly and it will just be represented as .

Even with a somewhat larger , the result is still significantly unreliable in typical cases. There is not much faith in the accuracy of the value because the most uncertainty in any floating-point number is the digits on the far right.

This is closely related to the phenomenon of catastrophic cancellation, in which the two numbers are known to be approximations.

Accumulation of roundoff error

Errors can be magnified or accumulated when a sequence of calculations is applied on an initial input with roundoff error due to inexact representation.

Unstable algorithms

An algorithm or numerical process is called stable if small changes in the input only produce small changes in the output, and unstable if large changes in the output are produced.[12] For example, the computation of using the "obvious" method is unstable near due to the large error introduced in subtracting two similar quantities, whereas the equivalent expression is stable.[12]

Ill-conditioned problems

Even if a stable algorithm is used, the solution to a problem may still be inaccurate due to the accumulation of roundoff error when the problem itself is ill-conditioned.

The condition number of a problem is the ratio of the relative change in the solution to the relative change in the input.[3] A problem is well-conditioned if small relative changes in input result in small relative changes in the solution. Otherwise, the problem is ill-conditioned.[3] In other words, a problem is ill-conditioned if its conditions number is "much larger" than 1.

The condition number is introduced as a measure of the roundoff errors that can result when solving ill-conditioned problems.[7]

See also

References

  1. ^ Butt, Rizwan (2009), Introduction to Numerical Analysis Using MATLAB, Jones & Bartlett Learning, pp. 11–18, ISBN 978-0-76377376-2
  2. ^ Ueberhuber, Christoph W. (1997), Numerical Computation 1: Methods, Software, and Analysis, Springer, pp. 139–146, ISBN 978-3-54062058-7
  3. ^ a b c d e f g h i j Forrester, Dick (2018). Math/Comp241 Numerical Methods (lecture notes). Dickinson College.
  4. ^ Aksoy, Pelin; DeNardis, Laura (2007), Information Technology in Theory, Cengage Learning, p. 134, ISBN 978-1-42390140-2
  5. ^ Ralston, Anthony; Rabinowitz, Philip (2012), A First Course in Numerical Analysis, Dover Books on Mathematics (2nd ed.), Courier Dover Publications, pp. 2–4, ISBN 978-0-48614029-2
  6. ^ Chapman, Stephen (2012), MATLAB Programming with Applications for Engineers, Cengage Learning, p. 454, ISBN 978-1-28540279-6
  7. ^ a b Chapra, Steven (2012). Applied Numerical Methods with MATLAB for Engineers and Scientists (3rd ed.). McGraw-Hill. ISBN 9780073401102.
  8. ^ Laplante, Philip A. (2000). Dictionary of Computer Science, Engineering and Technology. CRC Press. p. 420. ISBN 978-0-84932691-2.
  9. ^ Higham, Nicholas John (2002). Accuracy and Stability of Numerical Algorithms (2 ed.). Society for Industrial and Applied Mathematics (SIAM). pp. 43–44. ISBN 978-0-89871521-7.
  10. ^ Volkov, E. A. (1990). Numerical Methods. Taylor & Francis. p. 24. ISBN 978-1-56032011-1.
  11. ^ Biran, Adrian B.; Breiner, Moshe (2010). "5". What Every Engineer Should Know About MATLAB and Simulink. Boca Raton, Florida: CRC Press. pp. 193–194. ISBN 978-1-4398-1023-1.
  12. ^ a b Collins, Charles (2005). "Condition and Stability" (PDF). Department of Mathematics in University of Tennessee. Retrieved 2018-10-28.

Further reading