Gaussian elimination revisited

Suppose we have a hypothetical computer that represents numbers using only three decimal digits. We will consider the linear system

1. Show that this system has the unique solution

2. If we represent this solution inside our computer that only holds 3 decimal digits, what do we find for the solution? This is the best that we can hope to find using our computer.

3. Let's imagine that we use our computer to f…

We will consider the matrix and begin performing Gaussian elimination without using partial pivoting.

1. Perform two row replacement operations to find the row equivalent matrix Find elementary matrices $E_1$ and $E_2$ that perform these two operations so that $E_2E_1 A = A'$.

2. Perform a third row replacement to find the upper triangular matrix Find the elementary matrix $E_3$ such that $E_3E_2E_1A = U$.

3. We can write $A=E_1^{-1}E_2^{-1}E_3^{-1} U$. Find the inverse matr…

In this section, we saw that errors made in computer arithmetic can produce approximate solutions that are far from the exact solutions. Here is another example in which this can happen. Consider the matrix

1. Find the exact solution to the equation $A\xvec = \twovec{2}{2}$.

2. Suppose that this linear system arises in the midst of a larger computation except that, due to some error in the computation of the right hand side of…

In this section, we found the $LU$ factorization of the matrix in one of the activities, without using partial pivoting. Apply a sequence of row operations, now using partial pivoting, to find an upper triangular matrix $U$ that is row equivalent to $A$.

In the following exercises, use the given $LU$ factorizations to solve the equations $A\xvec = \bvec$.

1. Solve the equation

2. Solve the equation

Use Sage to solve the following equation by finding an $LU$ factorization: .

Here is another problem with approximate computer arithmetic that we will encounter in the next section. Consider the matrix

1. Notice that this is a positive stochastic matrix. What do we know about the eigenvalues of this matrix?

2. Use Sage to define the matrix $A$ using decimals such as 0.2 and the $3\times3$ identity matrix $I$. Ask Sage to compute $B = A-I$ and find the reduced row echelon form of $B$.

3. Why is the computat…

In practice, one rarely finds the inverse of a matrix $A$. It requires considerable effort to compute, and we can solve any equation of the form $A\xvec = \bvec$ using an $LU$ factorization, which means that the inverse isn't necessary. In any case, the best way to compute an inverse is using an $LU$ factorization, as this exercise demonstrates.

1. Suppose that $PA = LU$. Explain why $A^{-1} = U^{-1}L^{-1}P$.

   Since $L$ and $U$ are triangular, finding their in…

Consider the matrix

1. Find the $LU$ factorization of $A$.

2. What conditions on $a$, $b$, $c$, and $d$ guarantee that $A$ is invertible?

In the $LU$ factorization of a matrix, the diagonal entries of $L$ are all $1$ while the diagonal entries of $U$ are not necessarily $1$. This exercise will explore that observation by considering the matrix .

1. Perform Gaussian elimination without partial pivoting to find $U$, an upper triangular matrix that is row equivalent to $A$.

2. The diagonal entries of $U$ are called pivots. Explain why $\det A$ equals the product of t…

Please provide a justification to your responses to these questions.

1. In this section, our hypothetical computer could only store numbers using 3 decimal places. Most computers can store numbers using 15 or more decimal places. Why do we still need to be concerned about the accuracy of our computations when solving systems of linear equations?

2. Finding the $LU$ factorization of a matrix $A$ is roughly the…

Consider the matrix

1. Find the $LU$ factorization of $A$.

2. Use the factorization to find a basis for $\nul(A)$.

3. We have seen that $\nul(A) = \nul(U)$. Is it true that $\col(A) = \col(L)$?