Errors
Computers make mathematical errors. Here’s why.
Twin problems that confuse the computer
Look at this pair of problems.
Problem 1: solve the equation x²-4x+4 = 0.
Problem 2: solve the equation x²-4x+3.9999999 = 0.
Those two problems resemble each other. The only difference is that where the second problem says 3.9999999, the first problem says 4. But the correct solutions to the problems are quite different from each other:
The correct solution to problem 1 is "x = 2".
The correct solution to problem 2 is "x = 1.9996838 or x = 2.0003162".
Unfortunately, problem 1 looks so similar to problem 2 that the computer can hardly tell the difference.
Some computers treat 3.9999999 as if it were 4. If you ask such a computer to solve problem 2, it will solve problem 1 instead, and its answer to problem 2 will therefore be wrong.Here’s another pair of problems.
Problem 3: solve the equation (x-1)*(x-2)*(x-3)*(x-4)*...*(x-20) = 0.
Problem 4: solve the equation (x-1)*(x-2)*(x-3)*(x-4)*...*(x-20) -2-23*x19 = 0.
Those two problems resemble each other. In fact, if you "expand the polynomial", you’ll see that problem 3 can be rewritten like this:
x20 - 210x19 + ... = 0.
Problem 4 can be rewritten like this:
x20 - (210+2-23)x19 + ... = 0.
So problem 4 differs from problem 3 just by saying 210+2-23 instead of 210. Since 2-23 is a tiny number (approximately .0000001), some computers can’t tell the difference between 210 and 210+2-23, can’t distinguish problem 4 from problem 3, and say the same answer to problem 4 as to problem 3. But the correct solutions to the two problems are different:
The correct solution to problem 3 is "x=1 or x=2 or x=3 or x=4 or ... or x=20".
The correct solution to problem 4 is "x=1.000 or x=2.000 or x=3.000 or x=4.000 or x=5.000 or x=6.000 or x=7.000 or x=8.007 or x=8.917 or x=10.095
±.644i or x=11.794±1.652i or x=13.992±1.519i or x=16.731±2.813i or x=19.502± 1.940i or x=20.847". (i denotes the square root of -1.)Here’s one more case.
Problem 5: solve the simultaneous equations "913x+659y=254 and 780x+563y=217".
Problem 6: solve the simultaneous equations "913x+659y=254 and 780x+563y=216.999".
Although the problems are almost identical (so that some computers can’t distinguish them from each other), the correct solutions are quite different:
The correct solution to problem 5 is "x=1 and y=-1".
The correct solution to problem 6 is "x=.341 and y=-.087".
That last case of "confusing twins" leads to this fascinating paradox.… Suppose you tell your friendly computer to "guess" an x and y to solve problem 5:
913x + 659y = 254
780x + 563y = 217
If the computer guesses "x=.999 and y=-1.001", it finds:
913x + 659y = 252.428
780x + 563y = 215.757
But if the computer guesses "x=.341 and y=-.087" instead, it finds:
913x + 659y = 254
780x + 563y = 216.999, which is about 217
The computer therefore deduces that its second guess is almost perfect and much better than its first guess. But — here’s the paradox — the second guess is not better than the first guess; the first guess is better, because the correct solution is "x=1 and y=-1", which is closer to the first guess.
Reduce round-off error
By the laws of mathematics, 5+.14+.14+.14 should be the same as .14+.14+.14+5. But a calculator that holds just two significant digits gives different answers:
5+.14+.14+.14
.14+.14+.14+55.0 .14
+.14 +.14
5.1 .28
+.14 +.14
5.2 .42
+.14 +5.0
5.3 5.4
Since the correct answer is 5.42, the calculation on the right is more accurate. The general rule is:
when adding a list of numbers, you’ll get more accuracy if you begin with the numbers closest to 0. The rule is valid even on a top-quality computer, although the computer’s inaccuracies are not so obvious.By the laws of mathematics,
(31/5 - 31/7)*70 is 4:
1 7
3 = 3
5 35
1 5
-3 = 3
7 35
x
2
* 70 = 4
35
But if we try that calculation on our two-digit calculator, we get a totally different answer:
1
3 = 3+.2 = 3.2
5
1
-3 = 3+.14 = 3.1
7
x
.1 * 70 = 7.0
The general warning is:
when you subtract two numbers that are almost equal (like 31/5 and 31/7), few of the digits in your answer will be correct. The warning is valid even on a top-quality computer, although the computer’s inaccuracies are not so obvious.Estimates
The computer can estimate an answer.
Connecting the dots
Suppose you’re given the value of y when x is 1, 2, 3, 4, and 5:
Suppose you’d like to make an "intelligent guess" as to the value of y when x is 1.5, 3.01, 100, -400, and other values. Guessing y for an in-between x (such as 1.5 and 3.01) is called
interpolation; guessing y for a very large x or a very small x (such as 100 and -400) is called extrapolation.One way to guess is to connect the points with line segments:
That’s called
piecewise linear estimation.You get a much smoother picture by using a
cubic spline:
P1 and P6 are parts of straight lines. P2, P3, P4, and P5 are parts of four different cubics (third-degree polynomials), chosen so that, at the point where Pi meets Pi+1, Pi has the same
derivative and second derivative as Pi+1. (The term "derivative" is defined by calculus.)Least-square line
Suppose you’re given these
approximate values of y:
To estimate y for other values of x, you could use piecewise linear estimation or a cubic spline. But notice the points lie almost on a straight line:
The points aren’t exactly on that line; the errors in the y values are e1, e2, e3, e4, and e5. The line’s
squared error is e1² + e2² + e3² + e4² + e5². This line has a larger squared error:
The line having the smallest squared error is called the
least-square line, and is considered to be the line that best approximates the data.Solve equations
The computer can solve equations.
Single equations
Suppose you want to solve a tough equation, such as 2x+x3=20. Rewrite it to make the right side be 0:
2x+x3-20=0
Let f(x) denote the left side of the equation:
f(x) is 2x+x3-20
So the equation you want to solve is f(x)=0. Here’s a way to solve it — called the
secant method.…Let x1 and x2 be your favorite numbers. Graph f(x1) and f(x2):
Let x3 be where the line connecting those points hits the x axis:
Graph f(x3); it’s probably close to 0:
Connect the x2 point to the x3 point, to find x4:
Connect the x3 point to the x4 point, to find x5:
Probably you’ll get closer and closer to the point where f(x) is 0.
A different method, called
Muller’s method, uses parabolas instead of straight lines.…Let x1, x2, and x3 be your three favorite numbers. A common choice is -.5, .5, and 0. Graph f(x1), f(x2), and f(x3):
Draw the parabola that passes through those points:
The parabola hits the x axis at two points (although the points might be what mathematicians call "imaginary"). Let x4 be at one of those points. For best results, choose the point that’s closer to the origin:
Graph f(x4):
Draw a parabola through the x2, x3, and x4 points, to find x5:
Probably you’ll get closer to the place where f(x) is 0.
Usually, Muller’s method moves toward the solution more rapidly than the secant method. It can even find complex, "non-real" solutions, since the x value where the parabola hits the x axis might be of the form a+bi, where i denotes the square root of -1. (If you’re interested in just solutions that are real, pretend b is 0.)
Using either the secant method or Muller’s, suppose you finally find a solution of the equation 2x+x3-20=0. Let s1 denote that solution. To hunt for additional solutions, try solving this equation:
2x+x3-20
= 0
x-s1
If you find a solution of that new equation, call it s2, and solve this equation:
2x+x3-20
x= 0
(x-s1)(x-s2)
If that produces a solution s3, solve
2x+x3-20
x= 0
(x-s1)(x-s2)(x-s3)
to find s4. The solutions s1, s2, s3, s4, etc., are all solutions of the original equation.
The round-off error will be less if |s1| < |s2| < |s3| < |s4| < .... So when you hunt for solutions, begin by trying to find the solutions closest to zero. That’s why, when Muller’s parabola hits the x axis in two points, you should pick the point that’s closer to zero. And that’s why a common choice for x1, x2, and x3 is numbers near zero.
Simultaneous equations
Try to solve these simultaneous linear equations:
8x + y - z = 8
2x + y + 9z = 12
x - 7y + 2z = -4
An obvious way is
Gauss-Jordan elimination. Eliminate the first coefficient:1 1 1
x + y - z = 1 (I multiplied by )
8 8 8
2x + y + 9z = 12
x - 7y + 2z = -4
Eliminate everything below it:
1 1
x + y - z = 1
8 8
3 37
y + z = 10 (I subtracted twice the first row)
4 4
57 17
- y + z = -5 (I subtracted the first row)
8 8
Eliminate the first coefficient in the second row:
1 1
x + y - z = 1
8 8
37 40 4
y + z = (I multipled by )
3 3 3
57 17
- y + z = -5
8 8
Eliminate everything above and below it:
5 2 1
x - z= - (I subtracted times the second row)
3 3 8
37 40
y + z =
3 3
57
90z = 90 (I added times the second row)
8
Eliminate the first coefficient in the third row:
5 2
x - z= -
3 3
37 40
y + z =
3 3
1
z = 1 (I multiplied by )
90
Eliminate everything above it:
5
x = 1 (I added times the third row)
3
37
y = 1 (I subtracted times the third row)
3
z = 1
That’s the solution. (It’s depressing that so much computation was needed, to get such a simple solution!)
In that example, I pivoted on the first coefficient of the first equation, then the first coefficient of the second equation, and finally the first coefficient of the third equation. To reduce the computer’s round-off error, it’s better at each stage to pivot on the coefficient that has the largest absolute value, relative to the coefficients in its row. For example, at this stage —
1 1
x + y - z = 1
8 8
3 37
y + z = 10 (I subtracted twice the first row)
4 4
57 17
- y + z = -5 (I subtracted the first row)
8 8
it would have been better to pivot on -57/8 than on 3/4, since 57/8 divided by 17/8 is bigger than 3/4 divided by 37/4.
Now let’s go back to the original equations —
8x + y - z = 8
2x + y + 9z = 12
x - 7y + 2z = -4
and solve them by a different method, called
Gauss-Seidel iteration. In each equation, find the variable whose coefficient has the largest absolute value, and put that variable on one side:1 1
x = - y + z + 1
8 8
2 1 4
z = - x - y +
9 9 3
1 2 4
y = x + z +
7 7 7
Begin by guessing that x, y, and z are all 0, then improve the guesses by using those equations. Here are the calculations, to three decimal places:
x = 0
y = 0
z = 0
1 1
x = - y + z + 1 = 1.000
8 8
1 2 4
y = x + z + = .714
7 7 7
2 1 4
z = - x - y + = 1.032
9 9 3
1 1
x = - y + z + 1 = 1.041
8 8
1 2 4
y = x + z + = 1.014
7 7 7
2 1 4
z = - x - y + = .990
9 9 3
1 1
x = - y + z + 1 = .997
8 8
1 2 4
y = x + z + = .996
7 7 7
2 1 4
z = - x - y + = 1.002
9 9 3
1 1
x = - y + z + 1 = 1.001
8 8
1 2 4
y = x + z + = 1.000
7 7 7
2 1 4
z = - x - y + = 1.000
9 9 3
1 1
x = - y + z + 1 = 1.000
8 8
1 2 4
y = x + z + = 1.000
7 7 7
2 1 4
z = - x - y + = 1.000
9 9 3
In the example, x and y and z gradually approach the correct solutions.
Is Gauss-Seidel iteration better or worse than Gauss-Jordan elimination?
A disadvantage of Gauss-Seidel iteration is: it doesn’t guarantee you’ll approach the correct solution. If you follow the advice about pivoting on the coefficient that has the largest relative absolute value, you stand a better chance of approaching the correct solution, but there’s no guarantee.
On the other hand, if Gauss-Seidel iteration does approach a solution, the solution will have less round-off error than with Gauss-Jordan elimination.