Je bent je ingevulde velden bij deze pagina aan het verwijderen. Ben je zeker dat je dit wilt doen?
You are erasing your filled-in fields on this page. Are you sure that is what you want?
Nieuwe Versie BeschikbaarNew Version Available
Er is een update van deze pagina. Als je update naar de meest recente versie, verlies je mogelijk je huidige antwoorden voor deze pagina. Hoe wil je verdergaan ?
There is an updated version of this page. If you update to the most recent version, then your current progress on this page will be erased. Regardless, your record of completion will remain. How would you like to proceed?
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 \(ax+by=r\), and the blue line is the graph of \(cx+dy=s\). Point \(A\), 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.
from various starting points \(A\). Now what happens when we try the iterative
method?
3.
Try other \(2 \times 2\) systems of equations and see how the iterative method works.
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 \(n\) equations in \(n\) 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 \(i\)th variable in the \(i\)th
equation.
Let’s return to the system of equations from Exploration . 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 \(\vec {v}_0\), and use these formulas to compute the next iteration \(\vec {v}_1\). Taking the vector \(\vec {v}_1\), and we again apply these
formulas to compute the next iteration to arrive at \(\vec {v}_2\).
\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 \(\vec {v}_0 = \begin{bmatrix} 0\\0 \end{bmatrix}\). Applying the pair of formulas gives
We observe that at each iteration our approximate solution gets closer to the actual solution to the system,
\(x=6, y=10\).
The Gauss-Seidel method
To implement the Gauss-Seidel method for solving a linear system of \(n\) equations in \(n\) variables, we use the same set of \(n\)
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 \(\vec {v}_0 = \begin{bmatrix} 0\\0 \end{bmatrix}\). We apply the first formula and get
\[x= \dfrac {10+2(0)}{5}=2.\]
However, we will compute \(y\) using this new value \(x=2\) rather than using \(x=0\). We get
\[y=\dfrac {36-2}{3} = 34/3 \approx 11.33.\]
So after our first iteration we have \(\vec {v}_1 = \begin{bmatrix} 2\\11.33 \end{bmatrix}\). We repeat this procedure to perform another iteration. We get
\[x= \dfrac {10+2(11.33)}{5}\approx 6.53\]
followed by
\[y=\dfrac {36-6.53}{3} \approx 9.82,\]
so we have \(\vec {v}_2 \approx \begin{bmatrix} 6.53\\9.82 \end{bmatrix}\).
We observe that in this example the second iteration of the Gauss-Seidel method is closer to the actual solution of \(x=6, y=10\) 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.
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 \(\RR ^3\) share a common intersection point at \(\left (\frac {1}{8},\frac {1}{8},\frac {1}{8} \right )\), 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 \(x\) in the first equation, we solve for \(y\) in the second equation, and we solve for \(z\) 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.
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 (\((0.125,0.125.0.125)\) in decimal form). Starting
with an initial guess of \((1,2,3)\), 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 that the Gauss-Seidel method converged for the linear system 1. However, when we switched the
order of the equations, writing the same linear system using 2, 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\(A\) of a linear system \(A \vec {x}= \vec {b}\). To be clear, when we write a linear system as a
single augmented matrix, the coefficient matrix \(A\) 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 \(A=[a_{ij}]\) be the \(n\times n\) matrix which is the coefficient matrix of the linear system \(A \vec {x}= \vec {b}\). Let
\[ r_i(A):= \sum _{j \ne i} |a_{ij}| \]
denote the sum of the absolute values of the non-diagonal entries in row \(i\). We say that \(A\) is strictly diagonally dominant
if
\[|a_{ii}|>r_i(A)\]
for all values of \(i\) from \(i=1\) to \(i=n\).
For each of the linear systems examined above, determine whether or not the coefficient matrix is strictly diagonally
dominant.
We see that \(A\) 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 \(A=[a_{ij}]\) be the \(n\times n\) matrix which is the coefficient matrix of the linear system \(A \vec {x}= \vec {b}\), and suppose \(A\) 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 ?? 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 -
For each of the following, use Jacobi’s method and the Gauss-Seidel method with an initial guess of \(x=0,y=0\) 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}{ccccc} -5x& +&y&=&17\\ x & +&y&= &5 \end{array} \end{equation*}
For each of the following, use Jacobi’s method and the Gauss-Seidel method with an initial guess of \(x=0,y=0, z=0\) 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.
The lines, \(x+3y=1\) and \(4x-y=3.\) intersect at \(x=\frac {10}{13},y=\frac {1}{13}\). Use Jacobi’s method and the Gauss-Seidel method with an initial guess of \(x=0,y=0\) 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 \(m\) and \(-m\)?
Linear Algebra: An Interactive Introduction