Exercise 6

We began this section by stating that increasing computational power has helped linear algebra assume a greater prominence as a scientific tool. Later, we looked at one computational limitation: once a matrix gets to be too big, it is not reasonable to apply Gaussian elimination to find its reduced row echelon form.

In this exercise, we will see another limitation: computer arithmetic with real numbers is only an approximation because computers represent real numbers with only a finite number of bits. For instance, the number pi

\begin{equation*} \pi = 3.141592653589793238462643383279502884197169399\ldots \end{equation*}

would be approximated inside a computer by, say,

\begin{equation*} \pi\approx 3.141592653589793 \end{equation*}

Most of the time, this is not a problem. However, when we perform millions or even billions of arithmetic operations, the error in these approximations starts to accumulate and can lead to results that are wildly inaccurate. Here are two examples demonstrating this.

  1. Let's first see an example showing that computer arithmetic really is an approximation. First, consider the linear system

    \begin{equation*} \begin{alignedat}{4} x \amp {}+{} \amp \frac12y \amp {}+{} \amp \frac13z \amp {}={} \amp 1 \\ \frac12x \amp {}+{} \amp \frac13y \amp {}+{} \amp \frac14z \amp {}={} \amp 0 \\ \frac13x \amp {}+{} \amp \frac14y \amp {}+{} \amp \frac15z \amp {}={} \amp 0 \\ \end{alignedat} \end{equation*}

    If the coefficients are entered into Sage as fractions, Sage will find the exact reduced row echelon form. Find the exact solution to this linear system.

    Now let's ask Sage to compute with real numbers. We can do this by representing one of the coefficients as a decimal. For instance, the same linear system can be represented as

    \begin{equation*} \begin{alignedat}{4} x \amp {}+{} \amp 0.5y \amp {}+{} \amp \frac13z \amp {}={} \amp 1 \\ \frac12x \amp {}+{} \amp \frac13y \amp {}+{} \amp \frac14z \amp {}={} \amp 0 \\ \frac13x \amp {}+{} \amp \frac14y \amp {}+{} \amp \frac15z \amp {}={} \amp 0 \\ \end{alignedat} \end{equation*}

    Most computers do arithmetic using either 32 or 64 bits. To magnify the problem so that we can see it better, we will ask Sage to do arithmetic using only 10 bits as follows.

    What does Sage give for the solution now? Compare this to the exact solution that you found previously.

  2. Some types of linear systems are particularly sensitive to errors resulting from computers' approximate arithmetic. For instance, suppose we are interested in the linear system

    \begin{equation*} \begin{alignedat}{3} x \amp {}+{} \amp y \amp {}={} \amp 2 \\ x \amp {}+{} 1.001\amp y \amp {}={} \amp 2 \\ \end{alignedat} \end{equation*}

    Find the solution to this linear system.

    Suppose now that the computer has accumulated some error in one of the entries of this system so that it incorrectly stores the system as

    \begin{equation*} \begin{alignedat}{3} x \amp {}+{} \amp y \amp {}={} \amp 2 \\ x \amp {}+{} 1.001\amp y \amp {}={} \amp 2.001 \\ \end{alignedat} \end{equation*}

    Find the solution to this linear system.

    Notice how a small error in one of the entries in the linear system leads to a solution that has a dramatically large error. Fortunately, this is an issue that has been well studied, and there are techniques that mitigate this type of behavior.