Number Representations & States

"how numbers are stored in computers""how numbers are stored in computers"

If subtraction uses a guard digit, and if are the sides of a triangle (), then the relative error in computing the area of the triangle as is at most , provided .

Summary

This proof shows that a specific formula involving the sides of a triangle can be calculated in floating-point arithmetic with very little error, as long as a certain technical condition is met (using a guard digit during subtraction) and the rounding error, denoted by , is less than 0.005. Virtually all real-world floating point arithmetic systems provide a much lower value than 0.005 for .

The formula being calculated includes several additions, subtractions, and multiplications of the triangle's side lengths , , and . Each of these operations can introduce small rounding errors in floating-point arithmetic, so the proof carefully examines each step and uses earlier theorems to show that the individual errors from each operation are small and well-controlled. In particular, it points out that because of the triangle inequality, some potentially problematic subtractions turn out to be either exact or harmless.

When all the small errors from the additions, subtractions, and multiplications are combined, the total relative error in the final result is shown to be less than . This means that despite each step potentially introducing a small amount of error, the final result stays very close to what you would get with perfect precision. This shows that the entire formula is numerically stable, and will yield accurately rounded results as long as is sufficiently small.

Proof

Let's examine the factors one by one. From Theorem 10, , where is the relative error, and . Then the value of the first factor is

This means there is an such that

The next term involves the potentially catastrophic subtraction of and , because may have rounding error. Because , and are the sides of a triangle, , and combining this with the ordering gives . Therefore, satisfies the conditions of Theorem 11, so is exact, and is a harmless subtraction which can be estimated from Theorem 9 to be

The third term is the sum of two exact positive quantities, so

Finally, the last term is

using both Theorem 9 and Theorem 10. If multiplication is assumed to be exactly rounded, so that with , then combining the terms above gives

Where the relative error is

An upper bound for is , which expands out to . Some writers simply ignore the term, but it is easy to account for it. Writing , where is a polynomial in with positive coefficients, and therefore an increasing function of . Since , for all , and hence .

To get a lower bound on , note that , so when , . Combining these two bounds yields , so the relative error is at most .