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}*x^{19} = 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:

x^{20} - 210x^{19} + ... = 0.

Problem 4 can be rewritten like this:

x^{20} - (210+2^{-23})x^{19} + ... = 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+5__

5.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,

(3^{1}/_{5} - 3^{1}/_{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 3^{1}/_{5} and 3^{1}/_{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:

P_{1} and P_{6} are parts of straight lines. P_{2}, P_{3}, P_{4}, and P_{5} are parts of four different cubics (third-degree polynomials), chosen so that, at the point where P_{i} meets P_{i+1}, P_{i} has the same derivative and second derivative as P_{i+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 e_{1}, e_{2}, e_{3}, e_{4}, and e_{5}. The line’s squared error is e_{1}² + e_{2}² + e_{3}² + e_{4}² + e_{5}². 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 2^{x}+x^{3}=20. Rewrite it to make the right side be 0:

2^{x}+x^{3}-20=0

Let f(x) denote the left side of the equation:

f(x) is 2^{x}+x^{3}-20

So the equation you want to solve is f(x)=0. Here’s a way to solve it — called the secant method.…

Let x_{1} and x_{2} be your favorite numbers. Graph f(x_{1}) and f(x_{2}):

Let x_{3} be where the line connecting those points hits the x axis:

Graph f(x_{3}); it’s probably close to 0:

Connect the x_{2} point to the x_{3} point, to find x_{4}:

Connect the x_{3} point to the x_{4} point, to find x_{5}:

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 x_{1}, x_{2}, and x_{3} be your three favorite numbers. A common choice is -.5, .5, and 0. Graph f(x_{1}), f(x_{2}), and f(x_{3}):

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 x_{4} be at one of those points. For best results, choose the point that’s closer to the origin:

Graph f(x_{4}):

Draw a parabola through the x_{2}, x_{3}, and x_{4} points, to find x_{5}:

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 2^{x}+x^{3}-20=0. Let s_{1} denote that solution. To hunt for additional solutions, try solving this equation:

2^{x}+x^{3}-20

= 0

x-s_{1}

If you find a solution of that new equation, call it s_{2}, and solve this equation:

2^{x}+x^{3}-20 x

= 0

(x-s_{1})(x-s_{2})

If that produces a solution s_{3}, solve

2^{x}+x^{3}-20 x

= 0

(x-s_{1})(x-s_{2})(x-s_{3})

to find s_{4}. The solutions s_{1}, s_{2}, s_{3}, s_{4}, etc., are all solutions of the original equation.

The round-off error will be less if |s_{1}| < |s_{2}| < |s_{3}| < |s_{4}| < .... 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 x_{1}, x_{2}, and x_{3} 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.