8: Gauss-Seidel Method
- Page ID
- 104156
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\( \newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\)
( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\id}{\mathrm{id}}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\kernel}{\mathrm{null}\,}\)
\( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\)
\( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\)
\( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\AA}{\unicode[.8,0]{x212B}}\)
\( \newcommand{\vectorA}[1]{\vec{#1}} % arrow\)
\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow\)
\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vectorC}[1]{\textbf{#1}} \)
\( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)
\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)
\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\(\newcommand{\avec}{\mathbf a}\) \(\newcommand{\bvec}{\mathbf b}\) \(\newcommand{\cvec}{\mathbf c}\) \(\newcommand{\dvec}{\mathbf d}\) \(\newcommand{\dtil}{\widetilde{\mathbf d}}\) \(\newcommand{\evec}{\mathbf e}\) \(\newcommand{\fvec}{\mathbf f}\) \(\newcommand{\nvec}{\mathbf n}\) \(\newcommand{\pvec}{\mathbf p}\) \(\newcommand{\qvec}{\mathbf q}\) \(\newcommand{\svec}{\mathbf s}\) \(\newcommand{\tvec}{\mathbf t}\) \(\newcommand{\uvec}{\mathbf u}\) \(\newcommand{\vvec}{\mathbf v}\) \(\newcommand{\wvec}{\mathbf w}\) \(\newcommand{\xvec}{\mathbf x}\) \(\newcommand{\yvec}{\mathbf y}\) \(\newcommand{\zvec}{\mathbf z}\) \(\newcommand{\rvec}{\mathbf r}\) \(\newcommand{\mvec}{\mathbf m}\) \(\newcommand{\zerovec}{\mathbf 0}\) \(\newcommand{\onevec}{\mathbf 1}\) \(\newcommand{\real}{\mathbb R}\) \(\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}\) \(\newcommand{\laspan}[1]{\text{Span}\{#1\}}\) \(\newcommand{\bcal}{\cal B}\) \(\newcommand{\ccal}{\cal C}\) \(\newcommand{\scal}{\cal S}\) \(\newcommand{\wcal}{\cal W}\) \(\newcommand{\ecal}{\cal E}\) \(\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}\) \(\newcommand{\gray}[1]{\color{gray}{#1}}\) \(\newcommand{\lgray}[1]{\color{lightgray}{#1}}\) \(\newcommand{\rank}{\operatorname{rank}}\) \(\newcommand{\row}{\text{Row}}\) \(\newcommand{\col}{\text{Col}}\) \(\renewcommand{\row}{\text{Row}}\) \(\newcommand{\nul}{\text{Nul}}\) \(\newcommand{\var}{\text{Var}}\) \(\newcommand{\corr}{\text{corr}}\) \(\newcommand{\len}[1]{\left|#1\right|}\) \(\newcommand{\bbar}{\overline{\bvec}}\) \(\newcommand{\bhat}{\widehat{\bvec}}\) \(\newcommand{\bperp}{\bvec^\perp}\) \(\newcommand{\xhat}{\widehat{\xvec}}\) \(\newcommand{\vhat}{\widehat{\vvec}}\) \(\newcommand{\uhat}{\widehat{\uvec}}\) \(\newcommand{\what}{\widehat{\wvec}}\) \(\newcommand{\Sighat}{\widehat{\Sigma}}\) \(\newcommand{\lt}{<}\) \(\newcommand{\gt}{>}\) \(\newcommand{\amp}{&}\) \(\definecolor{fillinmathshade}{gray}{0.9}\)After reading this chapter, you should be able to:
- solve a set of equations using the Gauss-Seidel method,
- recognize the advantages and pitfalls of the Gauss-Seidel method, and
- determine under what conditions the Gauss-Seidel method always converges.
Why do we need another method to solve a set of simultaneous linear equations?
In certain cases, such as when a system of equations is large, iterative methods of solving equations are more advantageous. Elimination methods, such as Gaussian elimination, are prone to large round-off errors for a large set of equations. Iterative methods, such as the Gauss-Seidel method, give the user control of the round-off error. Also, if the physics of the problem are well known, initial guesses needed in iterative methods can be made more judiciously leading to faster convergence.
What is the algorithm for the Gauss-Seidel method? Given a general set of \(n\) equations and \(n\) unknowns, we have
\[a_{11}x_{1} + a_{12}x_{2} + a_{13}x_{3} + ... + a_{1n}x_{n} = c_{1} \nonumber \]
\[a_{21}x_{1} + a_{22}x_{2} + a_{23}x_{3} + ... + a_{2n}x_{n} = c_{2} \nonumber \]
\[\vdots \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \vdots \nonumber \]
\[a_{n1}x_{1} + a_{n2}x_{2} + a_{n3}x_{3} + ... + a_{nn}x_{n} = c_{n} \nonumber \]
If the diagonal elements are non-zero, each equation is rewritten for the corresponding unknown, that is, the first equation is rewritten with \(x_{1}\) on the left hand side, the second equation is rewritten with \(x_{2}\) on the left hand side and so on as follows
\[x_{1} = \frac{c_{1} - a_{12}x_{2} - a_{13}x_{3}\ldots\ldots - a_{1n}x_{n}}{a_{11}} \nonumber \]
\[x_{2} = \frac{c_{2} - a_{21}x_{1} - a_{23}x_{3}\ldots\ldots - a_{2n}x_{n}}{a_{22}} \nonumber \]
\[\vdots \nonumber \]
\[\vdots \nonumber \]
\[x_{n - 1} = \frac{c_{n - 1} - a_{n - 1,1}x_{1} - a_{n - 1,2}x_{2}\ldots\ldots - a_{n - 1,n - 2}x_{n - 2} - a_{n - 1,n}x_{n}}{a_{n - 1,n - 1}} \nonumber \]
\[x_{n} = \frac{c_{n} - a_{n1}x_{1} - a_{n2}x_{2} - \ldots\ldots - a_{n,n - 1}x_{n - 1}}{a_{nn}} \nonumber \]
These equations can be rewritten in a summation form as
\[x_{1} = \frac{c_{1} - \sum_{\begin{matrix} j = 1 \\ j \neq 1 \\ \end{matrix}}^{n}{a_{1j}x_{j}}}{a_{11}} \nonumber \]
\[x_{2} = \frac{c_{2} - \sum_{\begin{matrix} j = 1 \\ j \neq 2 \\ \end{matrix}}^{n}a_{2j}x_{j}}{a_{22}} \nonumber \]
\[\vdots \nonumber \]
\[x_{n - 1} = \frac{c_{n - 1} - \sum_{\begin{matrix} j = 1 \\ j \neq n - 1 \\ \end{matrix}}^{n}{a_{n - 1,j}x_{j}}}{a_{n - 1,n - 1}} \nonumber \]
\[x_{n} = \frac{c_{n} - \sum_{\begin{matrix} j = 1 \\ j \neq n \\ \end{matrix}}^{n}{a_{nj}x_{j}}}{a_{nn}} \nonumber \]
Hence for any row \(i\),
\[x_{i} = \frac{c_{i} - \sum_{\begin{matrix} j = 1 \\ j \neq i \\ \end{matrix}}^{n}{a_{ij}x_{j}}}{a_{ii}},i = 1,2,\ldots,n. \nonumber \]
Now to find \(x_{i}\)’s, one assumes an initial guess for the \(x_{i}\)’s and then uses the rewritten equations to calculate the new estimates. Remember, one always uses the most recent estimates to calculate the next estimates, \(x_{i}\). At the end of each iteration, one calculates the absolute relative approximate error for each \(x_{i}\) as
\[\left| \in_{a} \right|_{i} = \left| \frac{x_{i}^{\text{new}} - x_{i}^{\text{old}}}{x_{i}^{\text{new}}} \right| \times 100 \nonumber \]
where \(x_{i}^{\text{new}}\)is the recently obtained value of \(x_{i}\), and \(x_{i}^{\text{old}}\) is the previous value of \(x_{i}\).
When the absolute relative approximate error for each \(x_{i}\) is less than the pre-specified tolerance, the iterations are stopped.
The upward velocity of a rocket is given at three different times in the following table
| Time, \(t (s)\) | Velocity, \(v (m/s)\) |
|---|---|
| 5 | 106.8 |
| 8 | 177.2 |
| 12 | 279.2 |
The velocity data is approximated by a polynomial as
\[v\left( t \right) = a_{1}t^{2} + a_{2}t + a_{3},5 \leq t \leq 12 \nonumber \]
Find the values of \(a_{1},\ a_{2},and \ a_{3}\) using the Gauss-Seidel method. Assume an initial guess of the solution as
\[\begin{bmatrix} a_{1} \\ a_{2} \\ a_{3} \\ \end{bmatrix} = \begin{bmatrix} 1 \\ 2 \\ 5 \\ \end{bmatrix} \nonumber \]
and conduct two iterations.
Solution
The polynomial is going through three data points \(\left( t_{1},v_{1} \right),\left( t_{2},v_{2} \right),and\left( t_{3},v_{3} \right)\) where from the above table
\[t_{1} = 5,v_{1} = 106.8 \nonumber \]
\[t_{2} = 8,v_{2} = 177.2 \nonumber \]
\[t_{3} = 12,v_{3} = 279.2 \nonumber \]
Requiring that \(v\left( t \right) = a_{1}t^{2} + a_{2}t + a_{3}\)passes through the three data points gives
\[v\left( t_{1} \right) = v_{1} = a_{1}t_{1}^{2} + a_{2}t_{1} + a_{3} \nonumber \]
\[v\left( t_{2} \right) = v_{2} = a_{1}t_{2}^{2} + a_{2}t_{2} + a_{3} \nonumber \]
\[v\left( t_{3} \right) = v_{3} = a_{1}t_{3}^{2} + a_{2}t_{3} + a_{3} \nonumber \]
Substituting the data \(\left( t_{1},v_{1} \right),\left( t_{2},v_{2} \right),and\left( t_{3},v_{3} \right)\) gives
\[a_{1}\left( 5^{2} \right) + a_{2}\left( 5 \right) + a_{3} = 106.8 \nonumber \]
\[a_{1}\left( 8^{2} \right) + a_{2}\left( 8 \right) + a_{3} = 177.2 \nonumber \]
\[a_{1}\left( 12^{2} \right) + a_{2}\left( 12 \right) + a_{3} = 279.2 \nonumber \]
or
\[25a_{1} + 5a_{2} + a_{3} = 106.8 \nonumber \]
\[64a_{1} + 8a_{2} + a_{3} = 177.2 \nonumber \]
\[144a_{1} + 12a_{2} + a_{3} = 279.2 \nonumber \]
The coefficients \(a_{1},a_{2},anda_{3}\) for the above expression are given by
\[\begin{bmatrix} 25 & 5 & 1 \\ 64 & 8 & 1 \\ 144 & 12 & 1 \\ \end{bmatrix}\begin{bmatrix} a_{1} \\ a_{2} \\ a_{3} \\ \end{bmatrix} = \begin{bmatrix} 106.8 \\ 177.2 \\ 279.2 \\ \end{bmatrix} \nonumber \]
Rewriting the equations gives
\[a_{1} = \frac{106.8 - 5a_{2} - a_{3}}{25} \nonumber \]
\[a_{2} = \frac{177.2 - 64a_{1} - a_{3}}{8} \nonumber \]
\[a_{3} = \frac{279.2 - 144a_{1} - 12a_{2}}{1} \nonumber \]
Iteration #1
Given the initial guess of the solution vector as
\[\begin{bmatrix} a_{1} \\ a_{2} \\ a_{3} \\ \end{bmatrix} = \begin{bmatrix} 1 \\ 2 \\ 5 \\ \end{bmatrix} \nonumber \]
we get
\[\begin{split} a_{1} &= \frac{106.8 - 5(2) - (5)}{25}\\ &= 3.6720 \end{split} \nonumber \]
\[\begin{split} a_{2} &= \frac{177.2 - 64\left( 3.6720 \right) - \left( 5 \right)}{8}\\ &= - 7.8150 \end{split} \nonumber \]
\[\begin{split} a_{3} &= \frac{279.2 - 144\left( 3.6720 \right) - 12\left( - 7.8510 \right)}{1}\\ &= - 155.36 \end{split} \nonumber \]
The absolute relative approximate error for each \(x_{i}\) then is
\[\begin{split} \left| \in_{a} \right|_{1} &= \left| \frac{3.6720 - 1}{3.6720} \right| \times 100\\ &= 72.76\% \end{split} \nonumber \]
\[\begin{split} \left| \in_{a} \right|_{2} &= \left| \frac{- 7.8510 - 2}{- 7.8510} \right| \times 100\\ &= 125.47\% \end{split} \nonumber \]
\[\begin{split} \left| \in_{a} \right|_{3} &= \left| \frac{- 155.36 - 5}{- 155.36} \right| \times 100\\ &= 103.22\% \end{split} \nonumber \]
At the end of the first iteration, the estimate of the solution vector is
\[\begin{bmatrix} a_{1} \\ a_{2} \\ a_{3} \\ \end{bmatrix} = \begin{bmatrix} 3.6720 \\ - 7.8510 \\ - 155.36 \\ \end{bmatrix} \nonumber \]
and the maximum absolute relative approximate error is \(125.47%\).
Iteration #2
The estimate of the solution vector at the end of Iteration #1 is
\[\begin{bmatrix} a_{1} \\ a_{2} \\ a_{3} \\ \end{bmatrix} = \begin{bmatrix} 3.6720 \\ - 7.8510 \\ - 155.36 \\ \end{bmatrix} \nonumber \]
Now we get
\[\begin{split} a_{1} &= \frac{106.8 - 5\left( - 7.8510 \right) - ( - 155.36)}{25}\\ &= 12.056 \end{split} \nonumber \]
\[\begin{split} a_{2} &= \frac{177.2 - 64\left( 12.056 \right) - ( - 155.36)}{8}\\ &= - 54.882 \end{split} \nonumber \]
\[\begin{split} a_{3} &= \frac{279.2 - 144\left( 12.056 \right) - 12\left( - 54.882 \right)}{1}\\ &= - 798.34 \end{split} \nonumber \]
The absolute relative approximate error for each \(x_{i}\) then is
\[\begin{split} \left| \in_{a} \right|_{1} &= \left| \frac{12.056 - 3.6720}{12.056} \right| \times 100\\ &= 69.543\% \end{split} \nonumber \]
\[\begin{split} \left| \in_{a} \right|_{2} &= \left| \frac{- 54.882 - \left( - 7.8510 \right)}{- 54.882} \right| \times 100\\ &= 85.695\% \end{split} \nonumber \]
\[\begin{split} \left| \in_{a} \right|_{3} &= \left| \frac{- 798.34 - \left( - 155.36 \right)}{- 798.34} \right| \times 100\\ &= 80.540\% \end{split} \nonumber \]
At the end of the second iteration the estimate of the solution vector is
\[\begin{bmatrix} a_{1} \\ a_{2} \\ a_{3} \\ \end{bmatrix} = \begin{bmatrix} 12.056 \\ - 54.882 \\ - 798.54 \\ \end{bmatrix} \nonumber \]
and the maximum absolute relative approximate error is \(85.695\%\).
Conducting more iterations gives the following values for the solution vector and the corresponding absolute relative approximate errors.
| Iteration | \(a_{1}\) | \(\left| \in_{a} \right|_{1} \%\) | \(a_{2}\) | \(\left| \in_{a} \right|_{2} \%\) | \(a_{3}\) | \(\left| \in_{a} \right|_{3} \%\) |
|---|---|---|---|---|---|---|
| 1 | 3.672 | 72.767 | –7.8510 | 125.47 | –155.36 | 103.22 |
| 2 | 12.056 | 69.543 | –54.882 | 85.695 | –798.34 | 80.54 |
| 3 | 47.182 | 74.447 | –255.51 | 78.521 | –3448.9 | 76.852 |
| 4 | 193.33 | 75.595 | –1093.4 | 76.632 | –14440 | 76.116 |
| 5 | 800.53 | 75.85 | –4577.2 | 76.112 | –60072 | 75.963 |
| 6 | 3322.6 | 75.906 | –19049 | 75.972 | –249580 | 75.931 |
As seen in the above table, the solution estimates are not converging to the true solution of
\[a_{1} = 0.29048 \nonumber \]
\[a_{2} = 19.690 \nonumber \]
\[a_{3} = 1.0857 \nonumber \]
The above system of equations does not seem to converge. Why?
Well, a pitfall of most iterative methods is that they may or may not converge. However, the solution to a certain class of system of simultaneous equations does always converge using the Gauss-Seidel method. This class of system of equations is where the coefficient matrix \(\lbrack A\rbrack\) in \(\lbrack A\rbrack\lbrack X\rbrack = \lbrack C\rbrack\) is diagonally dominant, that is
\[\left| a_{ii} \right| \geq \sum_{\begin{matrix} j = 1 \\ j \neq i \\ \end{matrix}}^{n}\left| a_{ij} \right|\ \text{for all }i \nonumber \]
\[\left| a_{ii} \right| > \sum_{\begin{matrix} j = 1 \\ j \neq i \\ \end{matrix}}^{n}\left| a_{ij} \right|\text{for at least one }i \nonumber \]
If a system of equations has a coefficient matrix that is not diagonally dominant, it may or may not converge. Fortunately, many physical systems that result in simultaneous linear equations have a diagonally dominant coefficient matrix, which then assures convergence for iterative methods such as the Gauss-Seidel method of solving simultaneous linear equations.
Find the solution to the following system of equations using the Gauss-Seidel method.
\[12x_{1} + 3x_{2} - 5x_{3} = 1 \nonumber \]
\[x_{1} + 5x_{2} + 3x_{3} = 28 \nonumber \]
\[3x_{1} + 7x_{2} + 13x_{3} = 76 \nonumber \]
Use
\[\begin{bmatrix} x_{1} \\ x_{2} \\ x_{3} \\ \end{bmatrix} = \begin{bmatrix} 1 \\ 0 \\ 1 \\ \end{bmatrix} \nonumber \]
as the initial guess and conduct two iterations.
Solution1
The coefficient matrix
\[\left\lbrack A \right\rbrack = \begin{bmatrix} 12 & 3 & - 5 \\ 1 & 5 & 3 \\ 3 & 7 & 13 \\ \end{bmatrix} \nonumber \]
is diagonally dominant as
\[\left| a_{11} \right| = \left| 12 \right| = 12 \geq \left| a_{12} \right| + \left| a_{13} \right| = \left| 3 \right| + \left| - 5 \right| = 8 \nonumber \]
\[\left| a_{22} \right| = \left| 5 \right| = 5 \geq \left| a_{21} \right| + \left| a_{23} \right| = \left| 1 \right| + \left| 3 \right| = 4 \nonumber \]
\[\left| a_{33} \right| = \left| 13 \right| = 13 \geq \left| a_{31} \right| + \left| a_{32} \right| = \left| 3 \right| + \left| 7 \right| = 10 \nonumber \]
and the inequality is strictly greater than for at least one row. Hence, the solution should converge using the Gauss-Seidel method.
Rewriting the equations, we get
\[x_{1} = \frac{1 - 3x_{2} + 5x_{3}}{12} \nonumber \]
\[x_{2} = \frac{28 - x_{1} - 3x_{3}}{5} \nonumber \]
\[x_{3} = \frac{76 - 3x_{1} - 7x_{2}}{13} \nonumber \]
Assuming an initial guess of
\[\begin{bmatrix} x_{1} \\ x_{2} \\ x_{3} \\ \end{bmatrix} = \begin{bmatrix} 1 \\ 0 \\ 1 \\ \end{bmatrix} \nonumber \]
Iteration #1
\[\begin{split} x_{1} &= \frac{1 - 3\left( 0 \right) + 5\left( 1 \right)}{12}\\ & = 0.50000 \end{split} \nonumber \]
\[\begin{split} x_{2} &= \frac{28 - \left( 0.50000 \right) - 3\left( 1 \right)}{5}\\ &= 4.9000 \end{split} \nonumber \]
\[\begin{split} x_{3} &= \frac{76 - 3\left( 0.50000 \right) - 7\left( 4.9000 \right)}{13}\\ &= 3.0923 \end{split} \nonumber \]
The absolute relative approximate error at the end of the first iteration is
\[\begin{split} \left| \in_{a} \right|_{1} &= \left| \frac{0.50000 - 1}{0.50000} \right| \times 100\\ &= 100.00\% \end{split} \nonumber \]
\[\begin{split} \left| \in_{a} \right|_{2} &= \left| \frac{4.9000 - 0}{4.9000} \right| \times 100\\ &= 100.00\% \end{split} \nonumber \]
\[\begin{split} \left| \in_{a} \right|_{3} &= \left| \frac{3.0923 - 1}{3.0923} \right| \times 100\\ &= 67.662\% \end{split} \nonumber \]
The maximum absolute relative approximate error is \(100.00\%\)
Iteration #2
\[\begin{split} x_{1} &= \frac{1 - 3\left( 4.9000 \right) + 5\left( 3.0923 \right)}{12}\\ &= 0.14679 \end{split} \nonumber \]
\[\begin{split} x_{2} &= \frac{28 - \left( 0.14679 \right) - 3\left( 3.0923 \right)}{5}\\ &= 3.7153 \end{split} \nonumber \]
\[\begin{split} x_{3} &= \frac{76 - 3\left( 0.14679 \right) - 7\left( 3.7153 \right)}{13}\\ &= 3.8118 \end{split} \nonumber \]
At the end of second iteration, the absolute relative approximate error is
\[\begin{split} \left| \in_{a} \right|_{1} &= \left| \frac{0.14679 - 0.50000}{0.14679} \right| \times 100\\ &= 240.61\% \end{split} \nonumber \]
\[\begin{split} \left| \in_{a} \right|_{2} &= \left| \frac{3.7153 - 4.9000}{3.7153} \right| \times 100\\ &= 31.889\% \end{split} \nonumber \]
\[\begin{split} \left| \in_{a} \right|_{3} &= \left| \frac{3.8118 - 3.0923}{3.8118} \right| \times 100\\ &= 18.874\% \end{split} \nonumber \]
The maximum absolute relative approximate error is \(240.61\%\). This is greater than the value of \(100.00\%\) we obtained in the first iteration. Is the solution diverging? No, as you conduct more iterations, the solution converges as follows.
| Iteration | \(a_{1}\) | \(\left| \in_{a} \right|_{1} \%\) | \(a_{2}\) | \(\left| \in_{a} \right|_{2} \%\) | \(a_{3}\) | \(\left| \in_{a} \right|_{3} \%\) |
|---|---|---|---|---|---|---|
| 1 | 0.5 | 100 | 4.9 | 100 | 3.0923 | 67.662 |
| 2 | 0.14679 | 240.61 | 3.7153 | 31.889 | 3.8118 | 18.874 |
| 3 | 0.74275 | 80.236 | 3.1644 | 17.408 | 3.9708 | 4.0064 |
| 4 | 0.94675 | 21.546 | 3.0281 | 4.4996 | 3.9971 | 0.65772 |
| 5 | 0.99177 | 4.5391 | 3.0034 | 0.82499 | 4.0001 | 0.074383 |
| 6 | 0.99919 | 0.74307 | 3.0001 | 0.10856 | 4.0001 | 0.00101 |
This is close to the exact solution vector of
\[\begin{bmatrix} x_{1} \\ x_{2} \\ x_{3} \\ \end{bmatrix} = \begin{bmatrix} 1 \\ 3 \\ 4 \\ \end{bmatrix} \nonumber \]
Given the system of equations
\[3x_{1} + 7x_{2} + 13x_{3} = 76 \nonumber \]
\[x_{1} + 5x_{2} + 3x_{3} = 28 \nonumber \]
\[12x_{1} + 3x_{2} - 5x_{3} = 1 \nonumber \]
find the solution using the Gauss-Seidel method. Use
\[\begin{bmatrix} x_{1} \\ x_{2} \\ x_{3} \\ \end{bmatrix} = \begin{bmatrix} 1 \\ 0 \\ 1 \\ \end{bmatrix} \nonumber \]
as the initial guess.
Solution1
Rewriting the equations, we get
\[x_{1} = \frac{76 - 7x_{2} - 13x_{3}}{3} \nonumber \]
\[x_{2} = \frac{28 - x_{1} - 3x_{3}}{5} \nonumber \]
\[x_{3} = \frac{1 - 12x_{1} - 3x_{2}}{- 5} \nonumber \]
Assuming an initial guess of
\[\begin{bmatrix} x_{1} \\ x_{2} \\ x_{3} \\ \end{bmatrix} = \begin{bmatrix} 1 \\ 0 \\ 1 \\ \end{bmatrix} \nonumber \]
the next six iterative values are given in the table below.
| Iteration | \(a_{1}\) | \(\left| \in_{a} \right|_{1} \%\) | \(a_{2}\) | \(\left| \in_{a} \right|_{2} \%\) | \(a_{3}\) | \(\left| \in_{a} \right|_{3} \%\) |
|---|---|---|---|---|---|---|
| 1 | 21 | 95.238 | 0.8 | 100 | 50.68 | 98.027 |
| 2 | –196.15 | 110.71 | 14.421 | 94.453 | –462.30 | 110.96 |
| 3 | 1995 | 109.83 | –116.02 | 112.43 | 4718.1 | 109.8 |
| 4 | –20149 | 109.9 | 1204.6 | 109.63 | –47636 | 109.9 |
| 5 | 2.0364 \(\times 10^5\) | 109.89 | –12140 | 109.92 | 4.8144 \(\times 10^5\) | 109.89 |
| 6 | –2.0579 \(\times 10^6\) | 109.89 | 1.2272 \(\times 10^5\) | 109.89 | –4.8653 \(\times 10^6\) | 109.89 |
You can see that this solution is not converging and the coefficient matrix is not diagonally dominant. The coefficient matrix
\[\left\lbrack A \right\rbrack = \begin{bmatrix} 3 & 7 & 13 \\ 1 & 5 & 3 \\ 12 & 3 & - 5 \\ \end{bmatrix} \nonumber \]
is not diagonally dominant as
\[\left| a_{11} \right| = \left| 3 \right| = 3 \leq \left| a_{12} \right| + \left| a_{13} \right| = \left| 7 \right| + \left| 13 \right| = 20 \nonumber \]
Hence, the Gauss-Seidel method may or may not converge.
However, it is the same set of equations as the previous example and that converged. The only difference is that we exchanged first and the third equation with each other and that made the coefficient matrix not diagonally dominant.
Therefore, it is possible that a system of equations can be made diagonally dominant if one exchanges the equations with each other. However, it is not possible for all cases. For example, the following set of equations
\[x_{1} + x_{2} + x_{3} = 3 \nonumber \]
\[2x_{1} + 3x_{2} + 4x_{3} = 9 \nonumber \]
\[x_{1} + 7x_{2} + x_{3} = 9 \nonumber \]
cannot be rewritten to make the coefficient matrix diagonally dominant.
Gauss-Seidel Method Quiz
A square matrix \(\left\lbrack A \right\rbrack_{n \times n}\) is diagonally dominant if
(A) \(\displaystyle \left| a_{ii} \right| \geq \sum_{\begin{matrix} j = 1 \\ i \neq j \\ \end{matrix}}^{n}\left| a_{ij} \right|\), \(i = 1,2,...,n\)
(B) \(\displaystyle \left| a_{ii} \right| \geq \sum_{\begin{matrix} j = 1 \\ i \neq j \\ \end{matrix}}^{n}\left| a_{ij} \right|,\) \(i = 1,2,...,n\) and \(\left| a_{ii} \right| > \sum_{\begin{matrix} j = 1 \\ i \neq j \\ \end{matrix}}^{n}\left| a_{ij} \right|,\) for any \(i = 1,2,...,n\)
(C) \(\displaystyle \left| a_{ii} \right| \geq \sum_{j = 1}^{n}\left| a_{ij} \right|,\) \(i = 1,2,...,n\) and \(\left| a_{ii} \right| > \sum_{j = 1}^{n}\left| a_{ij} \right|,\) for any \(i = 1,2,...,n\)
(D) \(\displaystyle \left| a_{ii} \right| \geq \sum_{j = 1}^{n}\left| a_{ij} \right|,\) \(i = 1,2,...,n\)
Using \(\lbrack x_{1},x_{2},x_{3}\rbrack = \lbrack 1,3,5\rbrack\) as the initial guess, the values of \(\lbrack x_{1},x_{2},x_{3}\rbrack\) after three iterations in the Gauss-Seidel method for
\[\begin{bmatrix} 12 & 7 & 3 \\ 1 & 5 & 1 \\ 2 & 7 & - 11 \\ \end{bmatrix}\begin{bmatrix} x_{1} \\ x_{2} \\ x_{3} \\ \end{bmatrix} = \begin{bmatrix} 2 \\ - 5 \\ 6 \\ \end{bmatrix} \nonumber \]
are
(A) \([-2.8333 -1.4333 -1.9727]\)
(B) \([1.4959 -0.90464 -0.84914]\)
(C) \([0.90666 -1.0115 -1.0243]\)
(D) \([1.2148 -0.72060 -0.82451]\)
To ensure that the following system of equations,
\[\begin{matrix} 2x_{1} + & 7x_{2} - & 11x_{3} = & 6 \\ x_{1} + & 2x_{2} + & x_{3} = & - 5 \\ 7x_{1} + & 5x_{2} + & 2x_{3} = & 17 \\ \end{matrix} \nonumber \]
converges using the Gauss-Seidel method, one can rewrite the above equations as follows:
(A) \(\begin{bmatrix} 2 & 7 & - 11 \\ 1 & 2 & 1 \\ 7 & 5 & 2 \\ \end{bmatrix}\ \begin{bmatrix} x_{1} \\ x_{2} \\ x_{3} \\ \end{bmatrix} = \begin{bmatrix} 6 \\ -5 \\ 17 \\ \end{bmatrix}\)
(B) \(\begin{bmatrix} 7 & 5 & 2 \\ 1 & 2 & 1 \\ 2 & 7 & - 11 \\ \end{bmatrix}\ \begin{bmatrix} x_{1} \\ x_{2} \\ x_{3} \\ \end{bmatrix} = \begin{bmatrix} 17 \\ -5 \\ 6 \\ \end{bmatrix}\)
(C) \(\begin{bmatrix} 7 & 5 & 2 \\ 1 & 2 & 1 \\ 2 & 7 & - 11 \\ \end{bmatrix}\ \begin{bmatrix} x_{1} \\ x_{2} \\ x_{3} \\ \end{bmatrix} = \begin{bmatrix} 6 \\ -5 \\ 17 \\ \end{bmatrix}\)
(D) The equations cannot be rewritten in a form to ensure convergence.
For \(\begin{bmatrix} 12 & 7 & 3 \\ 1 & 5 & 1 \\ 2 & 7 & - 11 \\ \end{bmatrix}\ \begin{bmatrix} x_{1} \\ x_{2} \\ x_{3} \\ \end{bmatrix} = \begin{bmatrix} 22 \\ 7 \\ - 2 \\ \end{bmatrix}\)and using \(\begin{bmatrix} x_{1} & x_{2} & x_{3} \\ \end{bmatrix} = \begin{bmatrix} 1 & 2 & 1 \\ \end{bmatrix}\) as the initial guess, the values of \(\begin{bmatrix} x_{1} & x_{2} & x_{3} \\ \end{bmatrix}\) are found at the end of each iteration as
| Iteration # | \(x_{1}\) | \(x_{2}\) | \(x_{3}\) |
|---|---|---|---|
| 1 | 0.41667 | 1.1167 | 0.96818 |
| 2 | 0.93990 | 1.0184 | 1.0008 |
| 3 | 0.98908 | 1.0020 | 0.99931 |
| 4 | 0.99899 | 1.0003 | 1.0000 |
At what first iteration number would you trust at least 1 significant digit in your solution?
(A) \(1\)
(B) \(2\)
(C) \(3\)
(D) \(4\)
The algorithm for the Gauss-Seidel method to solve \(\left\lbrack A \right\rbrack\left\lbrack X \right\rbrack = \left\lbrack C \right\rbrack\) is given as follows when using \(n\max\) iterations. The initial value of \(\left\lbrack X \right\rbrack\) is stored in \(\left\lbrack X \right\rbrack\).
|
(A) Sub Seidel\((n,a,x,{rhs},nmax)\) For \(k = 1\) To \({nmax}\) For \(i = 1\) To \(n\) For \(j = 1\) To \(n\) If (\(i < > j\)) Then Sum = Sum + \(a(i,j)*x(j)\) endif Next \(j\) \(x(i) = ( {rhs}(i) - \text{Sum})/a(i,i)\) Next \(i\) Next \(j\) End Sub |
(B) Sub Seidel\((n,a,x,{rhs},nmax)\) For \(k = 1\) To \({nmax}\) For \(i = 1\) To \(n\) Sum = 0 For \(j = 1\) To \(n\) If (\(i < > j\)) Then Sum = Sum + \(a(i,j)*x(j)\) endif Next \(j\) \(x(i) = ( {rhs}(i) - \text{Sum})/a(i,i)\) Next \(i\) Next \(k\) End Sub |
|
(C) Sub Seidel\((n,a,x,{rhs},nmax)\) For \(k = 1\)To \({nmax}\) For \(i = 1\)To \(n\) Sum = 0 For \(j = 1\)To \(n\) Sum = Sum + \(a(i,j)*x(j)\) Next \(j\) \(x(i) = ( {rhs}(i) - \text{Sum})/a(i,i)\) Next \(i\) Next \(k\) End Sub |
(D) Sub Seidel\((n,a,x,{rhs},nmax)\) For \(k = 1\)To{nmax}$ For \(i = 1\) To \(n\) Sum = 0 For \(j = 1\) To \(n\) If (\(i < > j\)) Then Sum = Sum + \(a(i,j)*x(j)\) endif Next \(j\) \(x(i) = ( {rhs}(i) - \text{Sum})/a(i,i)\) Next \(i\) Next \(k\) End Sub |
Thermistors measure temperature, have a nonlinear output and are valued for a limited range. So when a thermistor is manufactured, the manufacturer supplies a resistance vs. temperature curve. An accurate representation of the curve is generally given by
\[\frac{1}{T} = a_{0} + a_{1}ln(R) + a_{2}\left\{ \ln\left( R \right) \right\}^{2} + a_{3}\left\{ \ln\left( R \right) \right\}^{3} \nonumber \]
where \(T\) is temperature in Kelvin, \(R\) is resistance in ohms, and \(a_{0},a_{1},a_{2},a_{3}\) are constants of the calibration curve. Given the following for a thermistor
| \(R\) | \(T\) |
|---|---|
| ohm | \({^\circ}C\) |
|
1101.0 911.3 636.0 451.1 |
25.113 30.131 40.120 50.128 |
the value of temperature in \({^\circ}C\) for a measured resistance of \(900\) ohms most nearly is
(A) \(30.002\)
(B) \(30.473\)
(C) \(31.272\)
(D) \(31.445\)
Gauss-Seidel Method Exercise
In a system of equation \([A] [X] = [C]\), if \([A]\) is diagonally dominant, then GaussSeidal-Seidel method
- always converges
- may or may not converge
- always diverges
- Answer
-
A
In a system of equations \([A] [X] = [C]\), if \([A]\) is not diagonally dominant, then Gauss-Seidel method
- Always converges
- May or may not converge
- Always diverges.
- Answer
-
B
In a system of equations \([A] [X] = [C]\), if \([A]\) is not diagonally dominant, the system of equations can always be rewritten to make it diagonally dominant.
- True
- False
- Answer
-
B
Solve the following system of equations using Gauss-Seidel method
\[\begin{matrix} 12x_{1} + 7x_{2} + 3x_{3} = 2 \\ x_{1} + 5x_{2} + x_{3} = - 5 \\ 2x_{1} + 7x_{2} - 11x_{3} = 6 \\ \end{matrix} \nonumber \]
Conduct 3 iterations, calculate the maximum absolute relative approximate error at the end of each iteration and choose \(\begin{bmatrix} x_{1} & x_{2} & x_{3} \\ \end{bmatrix} = \begin{bmatrix} 1 & 3 & 5 \\ \end{bmatrix}\) as your initial guess.
- Answer
-
\(\begin{bmatrix} x_{1} & x_{2} & x_{3} \\ \end{bmatrix} = \begin{bmatrix} 0.90666 & -1.0115 & -1.0243 \\ \end{bmatrix}\) \({\begin{bmatrix} \left| \in_{a} \right|_{1} & \left| \in_{a} \right|_{2} & \left| \in_{a} \right|_{3} \\ \end{bmatrix} = \begin{bmatrix} 65.001\% & 10.564\% & 17.099\% \\ \end{bmatrix} }\) \({\begin{bmatrix} \left| \in_{a} \right|_{1} & \left| \in_{a} \right|_{2} & \left| \in_{a} \right|_{3} \\ \end{bmatrix} = \begin{bmatrix} 65.001\% & 10.564\% & 17.099\% \\ \end{bmatrix} }\)
Solve the following system of equations using Gauss-Seidel method
\(12x_{1} + 7x_{2} + 3x_{3} = 2\)
\(x_{1} + 5x_{2} + x_{3} = - 5\)
\(2x_{1} + 7x_{2} - 11x_{3} = 6\)
Conduct 3 iterations, calculate the maximum absolute relative approximate error at the end of each iteration, and choose \(\begin{bmatrix} x_{1} & x_{2} & x_{3} \\ \end{bmatrix} = \begin{bmatrix} 1 & 3 & 5 \\ \end{bmatrix}\) as your initial guess.
- Answer
-
\(\begin{bmatrix} x_{1} & x_{2} & x_{3} \\ \end{bmatrix} = \begin{bmatrix} 0.90666 & - 1.0115 & - 1.0243 \\ \end{bmatrix}\)
Solve the following system of equations using Gauss-Seidel Method
\(x_{1} + 5x_{2} + x_{3} = 5\)
\(12x_{1} + 7x_{2} + 3x_{3} = 2\)
\(2x_{1} + 7x_{2} - 11x_{3} = 6\)
Conduct 3 iterations, calculate the maximum absolute relative approximate error at the end of each iteration, and choose \(\begin{bmatrix} x_{1} & x_{2} & x_{3} \\ \end{bmatrix} = \begin{bmatrix} 1 & 3 & 5 \\ \end{bmatrix}\) as your initial guess.
- Answer
-
\(\begin{bmatrix} x_{1} & x_{2} & x_{3} \\ \end{bmatrix} = \begin{bmatrix} -1163.7 & 1947.6 & 1027.2 \\ \end{bmatrix}\)
\(\begin{bmatrix} \left| \in_{a} \right|_{1} & \left| \in_{a} \right|_{2} & \left| \in_{a} \right|_{3} \\ \end{bmatrix} = \begin{bmatrix} 89.156\% & 89.139\% & 89.183\% \\ \end{bmatrix}\)