Numerical Challenges

Since you have successfully worked so many problems with matrices, you may be wondering why people still need to study them. The methods for dealing with matrices that you have learned work nicely for most small matrices, but difficulties are encountered when the matrices are larger. Can you imagine solving by hand a system of equations in which A was of dimension 10 by 10? That would take a dreadfully long time. However, a computer can solve this system quickly. Does that mean that a computer can solve all systems? What if the system involved a matrix with dimensions of 100,000 by 100,000? The computer could have difficulty with this system. You might be thinking that this is a ridiculous size for a system of equations, but systems this size and larger are needed in most industrial applications. For example, the major airlines need systems of this size to schedule flights and crews. Also, large systems are needed when an oil or water reservoir is simulated to learn about how to best pump the liquid or perform an environmental cleanup.

One problem is that the system might be too large for the computer's memory to hold all the information at one time. This means that new algorithms must be found that require less of the problem to be stored in memory at one time. These new algorithms still need to arrive at the correct solution in a reasonable amount of time.

The amount of work (the number of individual additions, subtractions, multiplications, or divisions) needed to solve a system also depends on the size of the system (among other properties such as the percentage of zeros in the matrix and where the non-zero numbers are in the matrix). Even if the computer can solve this system, will it be able to do it in a reasonable amount of time? In many ways, Gaussian elimination is our method of choice for solving linear systems. Yet, even Gaussian elimination may take days, months, or even years to solve very large linear systems on the world's fastest computers. Researchers are working to find algorithms that will solve systems with less work. They are also working in the field of parallel computing in which the problem is broken down into parts. Parts that do not depend on one another can be sent to separate processing units so that those parts of the problem can be processed at the same time. Computers are already extremely fast, so the room that is left for improvement lies mostly in improving algorithms. There are also many problems that still cannot be solved. These are reasons why researchers are needed in the mathematical sciences.

Roundoff error is probably the biggest detriment to effective computation because it can affect small problems as well as large ones. If you try to turn the fraction into a decimal, you can carry out the approximation as far as you want. However, a computer has only a set number of digits that it can store for each number. Therefore, the fraction has to be rounded at some point. For a single number, this rounding is not too significant, but it becomes important when operations are performed with rounded numbers. Most computers store numbers in a manner similar to scientific notation called normal notation. In normal notation, a number is written as m x 10^a where 0.1 ≤ |m| < 1. (In scientific notation, 1 ≤ |m| < 10). In this equation, m stands for mantissa and a stands for abscissa. The number 1234 is represented as 0.1234 x 10⁴. (Since most computers work in the binary system rather than the decimal system, this is not entirely accurate, but it will suffice to demonstrate roundoff error). The mantissa of this example is 0.1234. The abscissa is 4. For demonstration purposes, let us pretend that our computer stores 4-digit mantissas and 2-digit abscissas (the sign of the number is not included in the 4 digits of the mantissa on our fictional computer).

Let's add 10 + .00001. The exact arithmetic solution is 10.00001. Our computer stores this as 0.1000 x 10² + 0.1000 x 10^-4. When added, this yields 0.1000001 x 10². However, our computer will only store a 4 digit mantissa, so this rounds to 0.1000 x 10² which is the first addend of our problem. This means that our solution does not reflect that we added 0.1000 x 10^-4 at all. Our solution is only off by 0.1000 x 10^-4 which may not be much, but suppose that we want to add the number 0.1000 x 10^-4 ten thousand times to the number 10 rather than just once. The exact solution is 11, but our computer still gives the solution as 10 because each time that we add 0.1000 x 10^-4 to our solution, it doesn't make a difference. The source of this problem is that the two numbers that we are adding are of such different magnitudes. We can correct this problem by summing 0.1000 x 10^-4 ten thousand times before we add the result to 10. This will yield a much closer solution. Roundoff problems can be minimized by paying attention to details like the order of magnitude of the numbers, but they cannot be eliminated.

Subtractive cancellation is another big problem when dealing with computers. When you subtract two numbers that are very close to each other, an error is introduced. Suppose we want to perform this operation on our fictional computer: 0.5555 - 0.5554. Of course, the accurate solution is 0.0001, but that is not necessarily what the computer obtains. The computer represents this as 0.5555 x 10⁰ - 0.5554 x 10⁰. The subtraction yields 0.0001 x 10⁰, but the computer stores this number in normal form, so it should be stored as 0.1 x 10^-3. However, the computer fills all 4 digits of the mantissa. Since there is no accurate information for the other 3 digits of the mantissa, some computers fill the slots with random digits rather than zeros. Therefore, the solution is stored as 0.1ddd x 10^-3, where the d's are random digits. Because of this error, we try to avoid subtracting numbers that are too close to each other.

We can also run into problems when we solve systems of equations. Let's look at the system

When we try to solve this system on our fictional computer, we run into problems.

If you substitute this into the original equation, you can see that we definitely have a wrong solution. However, if we switch the order of the rows, we will get the right solution.

You can check, by substituting into the original equation, that this yields the correct solution. The first time that we worked this problem, we magnified the rounding errors in our data because we divided by .0001, which is the same as multiplying by 10,000. This is what caused our error.

You have seen many ways that errors can be introduced into a solution. Although very little error is introduced in each step, the errors accumulate when calculations are performed with rounded data. At each step, the error could increase. Therefore, an error of only 0.1 x 10^-6 per step could easily make our solution inaccurate if we perform enough steps before arriving at the solution.

<<<