I thought I blogged this long ago, but then again I thought I learned this long ago, and rediscovered this morning that I needed to recreate it: how to solve A x^2 + B x + C = 0.
We use a trick called "completing the square" to solve the equation above for X
A x^2 + B x + C = 0
x^2 + B/A x + C/A = 0
x^2 + 2B/2A x = - C/A
x^2 + 2 (B/2A) x + (B/2A)^2 = (B/2A)^2 - C/A
(x + B/2A)^2 = ( B^2 - 4AC ) / 4A^2
x + B/2A = ± ( B^2 - 4AC ) ^ .5 / 2A
x = - B ± ( B^2 - 4AC ) ^.5 /2A
Multiplying both sides by:
1 = [ -B ∓ (B^2 - 4AC) ^.5 ] / [ -B ∓ (B^2 - 4AC) ^.5]
x = 2C / [ -B ∓ (B^2 - 4AC) ^.5 ]
So we actually have two ways of writing x. Why would we need more than one? In a world of exact numbers, we can get by without. But when there are limits to the precision of our numbers, choosing the wrong operation can be catastrophic.
Consider a problem of the form:
x^2 - b x + 1 = 0 (note the minus sign).
The exact solution is
x = [ b ± Q ] / 2.
Q = sqrt( b^2 - 4 )
What happens when we use subtraction here? Let's try an example, using 16 digits of precision:
b = 10000.00000000000
b^2 = 100000000.0000000
b^2 - 4 = 99999996.00000000
Q = 9999.999799999998b+Q = 19999.99979999999
b-Q = 00000.00020000001
Contrast the last two operations. When we added, we lost a little bit of information off the far right side, but we still have 16 useful digits. When we subtracted, the first 8 digits cancelled; and that precision is lost.
What effect does this loss of precision have on our solution?
2/(b+Q) = 0.000100000001
(b-Q)/2 = 0.000100000005
And when we turn around and plug these values back into the original equation, to get a sense for how big the error is
e( 2/(b+Q) ) = +0.000000000000000200000001
e( (b-Q)/2 ) = -0.000000039999998999999975
The precision being lost is essentially that to which b and Q agree. We can use a Taylor expansion to approximate Q
Q = b - 2/b + O(b^2)
So when b is of order 10^n, b-Q is of order 10^-n; losing 2n digits of precision. The wrong approach gives you x = 10^-7, which has an error 10^-14. The right approach gives you x = 10^-7 + 10^-21, and the error is of order 10^-28.
October 17, 2005 1:15 PM
| TrackBack