- (a)
- Try solving the system of equations \begin{equation} \label{eq:diagdom1} \begin{array}{ccccc} 5x& -&2y&=&10\\ x & +&3y&= &36 \end{array} \end{equation} from various starting points . Does the iterative method “converge” to the actual solution of this system?
- (b)
- Now try solving the same system of equations, but changing which equation is the red line and which equation is the blue line. In other words, try \begin{equation} \label{eq:diagdom2} \begin{array}{ccccc} x & +&3y&= &36 \\ 5x& -&2y&=&10 \end{array} \end{equation} from various starting points . Now what happens when we try the iterative method?
- (c)
- Try other systems of equations and see how the iterative method works.
Iterative Methods for Solving Linear Systems
The approaches to solving linear systems we have studied up to this point are often called direct methods, to set them apart from iterative methods, which we study in this section. When we solve linear systems using iterative methods, we repeat the same procedure (called an iteration) many times (usually using a computer), and we look for the outputs to “converge to” the actual solution. Let’s begin with an exploration to illustrate this idea.
In the following GeoGebra interactive, the red line is the graph of , and the blue line
is the graph of . Point , referred to as our “initial guess,” may be dragged anywhere
on the plane before starting the iterative procedure. Use the navigation bar on the
bottom to proceed through several iterations. One iteration will consist of sliding
horizontally from the current point until we hit the red line, followed by sliding
vertically until we hit the blue line. These two steps are then repeated from the new
point on the blue line.
Iterative methods have become more important as computers have become more ubiquitous. When we execute an iterative method, we are implementing the same sequence of steps repeatedly, and this is something computers do very well.
In this section we will explore two different iterative methods for solving a system of linear equations. Exploration exp:gauss-seidel2x2 was a geometric representation of the Gauss-Seidel method for a system of two equations with two unknowns. We will show how this may be implemented numerically to approximate the solution to a system of equations. However, we first explore a related method known as Jacobi’s method.
Jacobi’s method
As you saw in the Exploration above, iterative methods do not give an exact answer, but an approximate answer. More iterations give a more accurate answer.
To use Jacobi’s method for solving a linear system of equations in variables, we isolate the first variable in the first equation, we isolate the second variable in the second equation, and in general, we isolate the th variable in the th equation.
Let’s return to the system of equations from Exploration exp:gauss-seidel2x2. To use Jacobi’s method to approximate the solution to the system, we solve for a different variable in each of the two equations. This gives us two formulas, one for each unknown. We begin with our initial guess , and use these formulas to compute the next iteration . Taking the vector , and we again apply these formulas to compute the next iteration to arrive at .
\begin{equation*} \begin{array}{ccccc} 5x& -&2y&=&10\\ x & +&3y&= &36 \end{array} \rightsquigarrow \text{isolating one variable in each equation}\rightsquigarrow \begin{array}{ccc} x& =&\dfrac{10+2y}{5}\\ y& =&\dfrac{36-x}{3} \end{array} \end{equation*}
Let’s begin with the initial guess . Applying the pair of formulas gives For the next iteration, we apply these same formulas to the and values of . We get We use this to perform another iteration, giving us We observe that at each iteration our approximate solution gets closer to the actual solution to the system, .
The Gauss-Seidel method
To implement the Gauss-Seidel method for solving a linear system of equations in variables, we use the same set of formulas as we use in Jacobi’s method. The difference is that we implement the formulas sequentially rather than simultaneously.
To demonstrate, we return to the same system of equations examined above.
\begin{equation*} \begin{array}{ccccc} 5x& -&2y&=&10\\ x & +&3y&= &36 \end{array} \rightsquigarrow \text{isolating variables as before}\rightsquigarrow x=\dfrac{10+2y}{5}, y=\dfrac{36-x}{3} \end{equation*}
Once again we start with the initial guess . We apply the first formula and get However, we will compute using this new value rather than using . We get So after our first iteration we have . We repeat this procedure to perform another iteration. We get followed by so we have .
We observe that in this example the second iteration of the Gauss-Seidel method is closer to the actual solution of than the third iteration of Jacobi’s method. The Gauss-Seidel method is more efficient than Jacobi’s method because it makes use of a better approximation of one coordinate to find another.
The Jacobi and Gauss-Seidel methods are easily implemented on a computer. Below
is a link to a spreadsheet which can be used to solve a linear system of 2 equations in
2 unknowns using each of these methods.
To use the spreadsheet, SAVE A COPY of the sheet. Then you will be able to change the yellow boxes to input a system of equations as well as the initial values. The video below the link to the spreadsheet gives additional information.
_
Both techniques described above can be used to solve linear systems with more variables.
Use direct methods to solve the linear system. Then try using Jacobi’s Method and
the Gauss-Seidel method.
We perform Gauss-Jordan elimination by applying elementary row operations as
described in Gaussian Elimination and Rank. \begin{equation*} \left [\begin{array}{ccc|c} 5&1&2&1\\2&5&1&1\\2&1&5&1 \end{array}\right ] \rightsquigarrow \text{ becomes (after a number of steps) } \rightsquigarrow \left [\begin{array}{ccc|c} 1&0&0&1/8\\0&1&0&1/8\\0&0&1&1/8 \end{array}\right ] \end{equation*}
This shows that the three planes in share a common intersection point at ,
which is easily verified by looking at the original equations, and can also
be seen in the GeoGebra graph below (RIGHT-CLICK AND DRAG TO
ROTATE).
Now we solve the same linear system using our iterative methods. In order to use Jacobi’s method or the Gauss-Seidel method, we solve for in the first equation, we solve for in the second equation, and we solve for in the third equation. We get three formulas. \begin{equation*} \begin{array}{ccccccc} 5x & +&y&+&2z&= &1 \\ 2x& +&5y&+&z&=&1\\ 2x& +&y&+&5z&=&1 \end{array} \rightsquigarrow \text{isolating these variables}\rightsquigarrow \begin{array}{c} x=\frac{1-y-2z}{5},\\ \\ y=\frac{1-2x-z}{5},\\ \\ z=\frac{1-2x-y}{5} \end{array} \end{equation*}
Below is a link to a spreadsheet which can be used to solve a linear system of 3 equations in 3 unknowns using the Jacobi method and the Gauss-Seidel method.
To use the spreadsheet, SAVE A COPY of the sheet. Then you will be able to change the yellow boxes to input a system of equations as well as the initial values.
Notice how much more efficient the Gauss-Seidel method is than Jacobi’s method. Both methods converge toward the exact solution we computed earlier using Gauss-Jordan elimination ( in decimal form). Starting with an initial guess of , when we use the Gauss-Seidel method, each coordinate gets to within 0.001 of the corresponding value of the exact solution. Using Jacobi’s method, 15 iterations are necessary to achieve the same level of accuracy with the same initial guess. This is not surprising, since the Gauss-Seidel Method uses new values as we find them, rather than waiting until the subsequent iteration, as is done with the Jacobi Method.
Convergence of Iterative Methods
We observed in Exploration exp:gauss-seidel2x2 that the Gauss-Seidel method converged for the linear system eq:diagdom1. However, when we switched the order of the equations, writing the same linear system using eq:diagdom2, the method failed to converge.
If you experiment with the spreadsheets and the GeoGebra interactive, you can find other systems of equations for which these iterative methods fail to converge to the solution. At this point you may be wondering why we are studying iterative methods when we cannot be certain that they will converge to the solution!
There are many situations where iterative methods are, in fact, the best methods we have for performing computations. We will see a nice example of this later when we study The Power Method and the Dominant Eigenvalue.
Also, it turns out that sometimes we can be certain that an iterative method will converge to the solution. To do so, we examine the coefficient matrix of a linear system . To be clear, when we write a linear system as a single augmented matrix, the coefficient matrix is the part of an augmented matrix to the left of the vertical line.
We need the following definition, which will also be useful when we study Gershgorin’s Theorem.
Let be the matrix which is the coefficient matrix of the linear system .
Let
denote the sum of the absolute values of the non-diagonal entries in row . We say
that is strictly diagonally dominant if
for all values of from to .
For each of the linear systems examined above, determine whether or not the
coefficient matrix is strictly diagonally dominant.
- (a)
- In Example ex:3x3iterative we considered the linear system The associated coefficient matrix is We see that is strictly diagonally dominant, for proceeding row by row, we note that \begin{align*} 5 &> 1 + 2 \\ 5 &> 2 + 1 \\ 5 &> 2 + 1 . \end{align*}
- (b)
- In Exploration exp:gauss-seidel2x2 we considered the linear system The associated coefficient matrix is We see that is strictly diagonally dominant, for proceeding row by row, we note that \begin{align*} 5 &> |-2| \\ 3 &> 1 \\ . \end{align*}
- (c)
- Later in the same Exploration exp:gauss-seidel2x2, we switched the order of the equations, giving us the linear system The associated coefficient matrix is We see that is NOT strictly diagonally dominant, for proceeding row by row, we note that \begin{align*} 1 &< 3 \\ 5 &> |-2| . \end{align*}
.
Now that we have explained the definition of strict diagonal dominance, we state (but do not prove) the following convergence theorem.
Let be the matrix which is the coefficient matrix of the linear system ,
and suppose is strictly diagonally dominant. Then both the Jacobi method
and the Gauss-Seidel method will converge to the solution to the linear
system.
The proof of this theorem at this point in the course would take us too far astray. Instead, we refer the interested reader to this 1995 paper by Roberto Bagnara.
Note that the converse of this theorem is false. Sometimes these iterative methods converge even though the coefficient matrices are not strictly diagonally dominant. Practice Problem prob:systems-iterative gives two examples where both methods converge to the solution even though the coefficient matrices are not strictly diagonally dominant. We say that strict diagonal dominance is sufficient to guarantee convergence, but it is not a necessary condition for convergence.
Practice Problems
Problems prob:systems-iterative-1-prob:systems-iterative-2
For each of the following, use Jacobi’s method and the Gauss-Seidel method with an initial guess of to find an approximate solution where each coordinate is within 0.1 of the exact solution. You can make a copy of the spreadsheets above and modify them to help. Note that the order of the equations may affect convergence.
Problems prob:systems-iterative-3x3-1-prob:systems-iterative-3x3-2
For each of the following, use Jacobi’s method and the Gauss-Seidel method with an initial guess of to find an approximate solution where each coordinate is within 0.1 of the exact solution. You can make a copy of the spreadsheets above and modify them to help. Note that the order of the equations may affect convergence.
\begin{equation*} \begin{array}{ccccccc} 3x& -&2y&+&z&=&-5\\ x& +&3y&-&z&=&12\\ x& +&y&+&2z&=&0 \end{array} \end{equation*}
\begin{equation*} \begin{array}{ccccccc} 8x& +&3y&+&3z&=&7\\ 4x& +&9y&+&3z&=&7\\ 2x& +&6y&+&9z&=&9 \end{array} \end{equation*}
The lines, and intersect at . Use Jacobi’s method and the Gauss-Seidel method
with an initial guess of to find an approximate solution where each coordinate is
within 0.1 of the exact solution. Write the coefficient matrix so it is strictly
diagonally dominant in order to ensure convergence.
What happens if the Gauss-Seidel method is to find the solution to a system of 2
equations in 2 unknowns when the slopes of the two lines are and ?
Practice Problem Source
Problem prb:2.1 comes from the end of Chapter 1 of Ken Kuttler’s A First Course in Linear Algebra. (CC-BY)
Ken Kuttler, A First Course in Linear Algebra, Lyryx 2017, Open Edition, p. 42.
2024-09-26 20:28:07