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.
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.
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 .
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, .
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.
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.
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.
ccess GeoGebra interactives through the online version of this text at
https://ximera.osu.edu/oerlinalg.
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.
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.
ccess spreadsheet link through the online version of this text at
https://ximera.osu.edu/oerlinalg.
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.
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.
.
Now that we have explained the definition of strict diagonal dominance, we state (but do not prove) the following convergence theorem.
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.
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.