Chapter 04.06: Gaussian Elimination Method for Solving Simultaneous Linear Equations
Learning Objectives
After successful completion of this lesson, you should be able to
1) write the algorithm to solve a set of simultaneous linear equations using Naive Gauss elimination method
How is a set of equations solved numerically by Gaussian elimination method?
One of the most popular techniques for solving simultaneous linear equations is the Gaussian elimination method. The approach is designed to solve a general set of \(n\) equations and \(n\) unknowns
\[\begin{split} &a_{11}x_{1} + a_{12}x_{2} + a_{13}x_{3} + \ldots + a_{1n}x_{n} = b_{1}\\ &a_{21}x_{1} + a_{22}x_{2} + a_{23}x_{3} + \ldots + a_{2n}x_{n} = b_{2}\\ &\vdots \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \vdots\\ &a_{n1}x_{1} + a_{n2}x_{2} + a_{n3}x_{3} + \ldots + a_{{nn}}x_{n} = b_{n} \end{split}\]
Gaussian elimination consists of two parts
1) Forward Elimination of Unknowns: In this part, an unknown is eliminated in the second through the last equation. This way, the equations are reduced to one equation and one unknown in each equation.
2) Back Substitution: In this part, starting from the last equation, each of the unknowns is found.
Forward Elimination of Unknowns:
In the first step of the forward elimination part, the first unknown, \(x_{1}\) is eliminated from all rows below the first row. The first equation is selected as the pivot equation to eliminate \(x_{1}\). So, to eliminate \(x_{1}\) in the second equation, one divides the first equation by \(a_{11}\) (hence called the pivot element) and then multiplies it by \(a_{21}\). This operation is the same as multiplying the first equation by \(a_{21}/a_{11}\) to give
\[a_{21}x_{1} + \frac{a_{21}}{a_{11}}a_{12}x_{2} + \ldots + \frac{a_{21}}{a_{11}}a_{1n}x_{n} = \frac{a_{21}}{a_{11}}b_{1}\]
Now, this equation can be subtracted from the second equation to give
\[\left( a_{22} - \frac{a_{21}}{a_{11}}a_{12} \right)x_{2} + \ldots + \left( a_{2n} - \frac{a_{21}}{a_{11}}a_{1n} \right)x_{n} = b_{2} - \frac{a_{21}}{a_{11}}b_{1}\]
or
\[{a^\prime }_{22}x_{2} + \ldots + {a^\prime }_{2n}x_{n} = {b^\prime }_{2}\]
where
\[\begin{split} &{a^\prime }_{22} = a_{22} - \frac{a_{21}}{a_{11}}a_{12}\\ &\vdots\\ &{a^\prime }_{2n} = a_{2n} - \frac{a_{21}}{a_{11}}a_{1n}\end{split}\]
This procedure of eliminating \(x_{1}\), is now repeated for the third equation to the \(n^{{th}}\) equation to reduce the set of equations as
\[\begin{split} &a_{11}x_{1} + a_{12}x_{2} + a_{13}x_{3} + \ldots + a_{1n}x_{n} = b_{1}\\ &{a^\prime }_{22}x_{2} + {a^\prime }_{23}x_{3} + \ldots + {a^\prime }_{2n}x_{n} = {b^\prime }_{2}\\ &{a^\prime }_{32}x_{2} + {a^\prime }_{33}x_{3} + \ldots + {a^\prime }_{3n}x_{n} = {b^\prime }_{3}\\ &\vdots \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \vdots \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \vdots\\ &{a^\prime }_{n2}x_{2} + {a^\prime }_{n3}x_{3} + \ldots + {a^\prime }_{\text{nn}}x_{n} = {b^\prime }_{n} \end{split}\]
This marks the end of the first step of the forward elimination part. Now for the second step of the forward elimination part, we start with the second equation as the pivot equation and \({a^\prime }_{22}\) as the pivot element. So, to eliminate \(x_{2}\) in the third equation, one divides the second equation by \({a^\prime }_{22}\) (the pivot element) and then multiply it by\({a^\prime }_{32}\). This operation is the same as multiplying the second equation by \(\displaystyle {a^\prime }_{32}/{a^\prime }_{22}\) and subtracting it from the third equation. This subtraction makes the coefficient of \(x_{2}\) zero in the third equation. The same procedure is now repeated for the fourth equation till the \(n^{\text{th}}\)equation to give
\[\begin{split} &a_{11}x_{1} + a_{12}x_{2} + a_{13}x_{3} + \ldots + a_{1n}x_{n} = b_{1}\\ &{a^\prime }_{22}x_{2} + {a^\prime }_{23}x_{3} + \ldots + {a^\prime }_{2n}x_{n} = {b^\prime }_{2}\\ &{a^{\prime\prime}}_{33}x_{3} + \ldots + {a^{\prime\prime}}_{3n}x_{n} = {b^{\prime\prime}}_{3}\\ &\vdots \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \vdots\\ &{a^{\prime\prime}}_{n3}x_{3} + \ldots + {a^{\prime\prime}}_{\text{nn}}x_{n} = {b^{\prime\prime}}_{n} \end{split}\]
The next steps of the forward elimination part are conducted by using the third equation as a pivot equation. That is, there will be a total of \(n - 1\) steps in the forward elimination part of the method. At the end of \(n - 1\) steps within the forward elimination part, we get a set of equations that look like
\[\begin{split} &a_{11}x_{1} + a_{12}x_{2} + a_{13}x_{3} + \ldots + a_{1n}x_{n} = b_{1}\\ &\ \ \ \ \ \ \ \ \ \ \ \ \ {a^\prime }_{22}x_{2} + {a^\prime }_{23}x_{3} + \ldots + {a^\prime }_{2n}x_{n} = {b^\prime }_{2}\\ &\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ {a^{\prime\prime}}_{33}x_{3} + \ldots + {a^{\prime\prime}}_{3n}x_{n} = {b^{\prime\prime}}_{3}\\ &\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \vdots \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \vdots\\ &\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ a_{{nn}}^{\left( n - 1 \right)}x_{n} = b_{n}^{\left( n - 1 \right)}\end{split}\]
Back Substitution:
In this part, the equations are solved starting from the last equation as it has only one unknown.
\[x_{n} = \frac{b_{n}^{(n - 1)}}{a_{{nn}}^{(n - 1)}}\]
Then the second last equation, that is the \((n - 1)^{{th}}\) equation, has two unknowns: \(x_{n}\) and \(x_{n - 1}\), but \(x_{n}\) is already known. This recognition reduces the \((n - 1)^{th}\) equation also to one unknown. Back substitution hence can be represented for all equations by the formula
\[x_{i} = \frac{b_{i}^{\left( i - 1 \right)} - \displaystyle\sum_{j = i + 1}^{n}{a_{{ij}}^{\left( i - 1 \right)}x_{j}}}{a_{{ii}}^{\left( i - 1 \right)}}\ \text{for }i = n - 1,\ \ n - 2,\ldots\ ,\ 1\]
and
\[x_{n} = \frac{b_{n}^{(n - 1)}}{a_{{nn}}^{(n - 1)}}\]
Learning Objectives
After successful completion of this lesson, you should be able to:
1) solve a set of simultaneous linear equations using Naïve Gauss elimination.
Applications
In the previous lesson, you learned the theory behind Naive Gauss Elimination. In this lesson, we will apply the theory to solve a set of simultaneous linear equations.
Example 1
The upward velocity of a rocket is given at three different times in Table 1.
Table 1: Velocity vs. time data.
| 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\]
The coefficients \(a_{1},a_{2},\) and \(a_{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}\]
Find the values of \(a_{1},a_{2},\) and \(a_{3}\) using the Naïve Gauss elimination method. Find the velocity at \(t = 6,\ 7.5,\ 9,\ 11\) seconds.
Solution
The augmented matrix is
\[\begin{bmatrix} 25 & 5 & 1 & | & 106.8 \\ 64 & 8 & 1 & | & 177.2 \\ 144 & 12 & 1 & | & 279.2 \\ \end{bmatrix}\]
Forward Elimination of Unknowns
Since there are three equations, there will be two steps of the forward elimination part.
First step
Divide Row \(1\) by \(25\) and then multiply it by \(64\), that is, multiply Row \(1\) by \(64/25 = 2.56\).
\[\left( \begin{matrix} \left\lbrack 25 \right.\ & \ 5 & \ \ \ \ \ \ \ 1\ \ \ \ \ \ \ |\ \ \ \ \ \\ \end{matrix}106.8\rbrack \right) \times 2.56\ \text{gives Row 1 as}\]
\[\begin{matrix} \left\lbrack 64 \right.\ & 12.8 & 2.56 \\ \end{matrix}\ \ \ \ \ |\ \ 273.408\rbrack\]
Subtract the result from Row \(2\)
\[\frac{\begin{matrix} \ \ \ \lbrack\begin{matrix} 64 & \ \ \ \ 8 & \ \ 1 \\ \end{matrix}\ \ \ \ |\ \ & 177.2\rbrack \\- \lbrack\begin{matrix} 64 & 12.8 & 2.56 \\ \end{matrix}\ \ | & 273.408\rbrack \\ \end{matrix}}{\ \ \ \begin{matrix} \begin{matrix} 0 & - 4.8 & - 1.56 \\ \end{matrix} & - 96.208 \\ \end{matrix}}\]
to get the resulting equations as
\[\begin{bmatrix} 25 & 5 & 1 & | & 106.8 \\ 0 & -4.8 & -1.56 & | & -96.208 \\ 144 & 12 & 1 & | & 279.2 \\ \end{bmatrix}\]
Divide Row \(1\) by \(25\) and then multiply it by \(144\), that is, multiply Row \(1\) by \(144/25 = 5.76\).
\[\left( \begin{matrix} \left\lbrack 25 \right.\ & \ \ \ \ 5 & \ \ \ 1 \\ \end{matrix} \ \ \ \ \ \ |\ \ \ \ \ \ \ \ \ 106.8\rbrack \right) \times 5.76\ \text{gives Row 1 as}\]
\[\left\lbrack \begin{matrix} 144 & 28.8 & 5.76 \\ \end{matrix} \ \ \ \ \right|\ \ \ \ \ \ 615.168\rbrack\]
Subtract the result from Row \(3\)
\[\frac{\begin{matrix} \ \ \ \ \lbrack\begin{matrix} 144 & 12 & \ \ 1 \\ \end{matrix}\ \ \ \ \ \ | & 279.2\rbrack \\ - \begin{matrix} \lbrack 144 & 28.8 & 5.76 \\ \end{matrix}\ \ \ | & 615.168\rbrack \\ \end{matrix}}{\ \ \ \ \begin{matrix} \begin{matrix} 0 & - 16.8 & - 4.76 \\ \end{matrix} & - 335.968 \\ \end{matrix}}\]
to get the resulting equations as
\[\begin{bmatrix} 25 & 5 & 1 & | & 106.8 \\ 0 & -4.8 & -1.56 & | & -96.208 \\ 0 & -16.8 & -4.76 & | & -335.968 \\ \end{bmatrix}\]
Second step
We now divide Row \(2\) by \(-4.8\) and then multiply by \(-16.8\), that is, multiply Row \(2\) by \(-16.8/-4.8 = 3.5\).
\[\left( \left\lbrack 0 - 4.8\ \ - 1.56\ \ \ \ \ \ \ \ \ \ \right|\ \ \ - 96.208\rbrack\ \right) \times 3.5\ \text{gives Row 2 as}\]
\[\left\lbrack 0 - 16.8\ - 5.46\ \ \ \ \ \ \ \ \ \ \right| - 336.728\rbrack\]
Subtract the result from Row \(3\)
\[\frac{\begin{matrix} \ \ \ \ \ \ \lbrack\begin{matrix} 0 & -16.8 & -4.76\ \\ \end{matrix} \ \ \ \ | & -335.968\rbrack \\ \ -\ \lbrack \begin{matrix} 0 & -16.8 & -5.46\ \\ \end{matrix}\ \ \ \ \ | & -336.728\rbrack \\ \end{matrix}}{\begin{matrix} \ \ \ \ \ \begin{matrix} 0 & \ \ \ \ \ \ \ 0 & \ \ \ \ \ \ 0.7 \end{matrix} & \ \ \ \ \ \ \ \ \ \ \ 0.76 \ \ \ \end{matrix}}\]
to get the resulting equations as
\[\begin{bmatrix} 25 & 5 & 1 & | & 106.8 \\ 0 & -4.8 & -1.56 & | & -96.208 \\ 0 & 0 & 0.7 & | & 0.76 \\ \end{bmatrix}\]
\[\begin{bmatrix} 25 & 5 & 1 \\ 0 & - 4.8 & - 1.56 \\ 0 & 0 & 0.7 \\ \end{bmatrix}\begin{bmatrix} a_{1} \\ a_{2} \\ a_{3} \\ \end{bmatrix} = \begin{bmatrix} 106.8 \\ - 96.208 \\ 0.76 \\ \end{bmatrix}\]
Back substitution
From the third equation
\[0.7a_{3} = 0.76\]
\[\begin{split} a_{3} &= \frac{0.76}{0.7}\\ &= 1.08571 \end{split}\]
Substituting the value of \(a_{3}\) in the second equation,
\[- 4.8a_{2} - 1.56a_{3} = - 96.208\]
\[\begin{split} a_{2} &= \frac{- 96.208 + 1.56a_{3}}{- 4.8}\\ &= \frac{- 96.208 + 1.56 \times 1.08571}{- 4.8}\\ &= 19.6905\end{split}\]
Substituting the value of \(a_{2}\) and \(a_{3}\) in the first equation,
\[25a_{1} + 5a_{2} + a_{3} = 106.8\]
\[\begin{split} a_{1} &= \frac{106.8 - 5a_{2} - a_{3}}{25}\\ &= \frac{106.8 - 5 \times 19.6905 - 1.08571}{25}\\ &= 0.290472 \end{split}\]
Hence the solution vector is
\[\begin{bmatrix} a_{1} \\ a_{2} \\ a_{3} \\ \end{bmatrix} = \begin{bmatrix} 0.290472 \\ 19.6905 \\ 1.08571 \\ \end{bmatrix}\]
The polynomial that passes through the three data points is then
\[\begin{split} v\left( t \right) &= a_{1}t^{2} + a_{2}t + a_{3}\\ &= 0.290472t^{2} + 19.6905t + 1.08571,\ \ 5 \leq t \leq 12 \end{split}\;\;\;\;\;\;\;\;\;\;\;\; (E1.1)\]
Since we want to find the velocity at \(t = 6,7.5,9\) and \(11\) seconds, we could simply substitute each value of \(t\) in \(v\left( t \right) = 0.290472t^{2} + 19.6905t + 1.08571\) and find the corresponding velocity. For example, at \(t = 6\)
\[\begin{split} v\left( 6 \right) &= 0.290472\left( 6 \right)^{2} + 19.6905\left( 6 \right) + 1.08571\\ &= 129.686\ \ \text{m/s} \end{split}\]
However, we could also find all the needed values of velocity at \(t\) = \(6, 7.5, 9, 11\) seconds using the matrix multiplication form of Equation (E1.1).
\[v\left( t \right) = \left\lbrack 0.290472\ \ 19.6905 \ \ 1.08571 \right\rbrack\begin{bmatrix} t^{2} \\ t \\ 1 \\ \end{bmatrix}\]
So, if we want to find \(v\left( 6 \right),v\left( 7.5 \right),v\left( 9 \right),v\left( 11 \right),\) it is given by
\[\begin{split} \begin{matrix}\left\lbrack v\left( 6 \right)v\left( 7.5 \right)v\left( 9 \right)v\left( 11 \right) \right\rbrack \end{matrix} &= \left\lbrack 0.290472 \ \ 19.6905\ \ 1.08571 \right\rbrack\begin{bmatrix} 6^{2} & 7.5^{2} & 9^{2} & 11^{2} \\ 6 & 7.5 & 9 & 11 \\ 1 & 1 & 1 & 1 \end{bmatrix}\\ &= \left\lbrack 0.290472 \ \ 19.6905 \ \ 1.08571 \right\rbrack\begin{bmatrix} 36 & 56.25 & 81 & 121 \\ 6 & 7.5 & 9 & 11 \\ 1 & 1 & 1 & 1 \end{bmatrix}\\ &= \left\lbrack 129.686 \ \ 165.104\ \ 201.828 \ \ 252.828 \right\rbrack \end{split}\]
\[v(6) = 129.686\ \text{m/s}\]
\[v(7.5) = 165.104\ \text{m/s}\]
\[v(9) = 201.828\ \text{m/s}\]
\[v(11) = 252.828\ \text{m/s}\]
Learning Objectives
After successful completion of this lesson, you should be able to
1) use the forward elimination part of Naive Gauss elimination method to find the determinant of a square matrix,
2) enumerate theorems related to the determinant of matrices,
3) relate the zero and non-zero value of the determinant of a square matrix to the existence or non-existence of the matrix inverse.
Can we use Naive Gauss elimination methods to find the determinant of a square matrix?
One of the more efficient ways to find the determinant of a square matrix is by taking advantage of the following two theorems on a determinant of matrices coupled with Naive Gauss elimination.
Theorem 1:
Let \(\lbrack A\rbrack\) be a \(n \times n\) matrix. Then, if \(\lbrack B\rbrack\) is a \(n \times n\) matrix that results from adding or subtracting a multiple of one row to another row, then \(det(A) = det(B)\) (The same is true for column operations also).
Theorem 2:
Let \(\lbrack A\rbrack\) be a \(n \times n\) matrix that is upper triangular, lower triangular, or diagonal, then
\[\begin{split} \det(A) &= a_{11} \times a_{22} \times ... \times a_{{ii}} \times ... \times a_{{nn}}\\ &= \prod_{i = 1}^{n}a_{{ii}} \end{split}\]
This formula implies that if we apply the forward elimination part of the Naive Gauss elimination method, the determinant of the matrix stays the same according to Theorem 1. Then since at the end of the forward elimination part, the resulting matrix is upper triangular, the determinant will be given by Theorem 2.
Example 1
Find the determinant of
\[\lbrack A\rbrack = \begin{bmatrix} 25 & 5 & 1 \\ 64 & 8 & 1 \\ 144 & 12 & 1 \\ \end{bmatrix}\]
Solution
If we conduct all the steps of the forward elimination part using the Naive Gauss elimination method on \(\lbrack A\rbrack\), it will give us the following upper triangular matrix (refer to the example in the previous lesson of Naive Gauss elimination for the process)
\[\left\lbrack B \right\rbrack = \begin{bmatrix} 25 & 5 & 1 \\ 0 & - 4.8 & - 1.56 \\ 0 & 0 & 0.7 \\ \end{bmatrix}\]
According to Theorem 2
\[\begin{split} \det(B) &= 25 \times ( - 4.8) \times 0.7\\ &= - 84.00 \end{split}\]
and since forward elimination part involve subtracting multiple of one row from another, using the Theorem 1 \[\begin{split} \det(A) &= \det(B)\\ &= - 84.00 \end{split}\]
What if I cannot find the determinant of the matrix using the Naive Gauss elimination method, for example, if I get division by zero problems during the Naive Gauss elimination method?
Well, in that case, you can apply Gaussian elimination with partial pivoting. However, the determinant of the resulting upper triangular matrix may differ by sign. The following theorem applies in addition to the previous two to find the determinant of a square matrix.
Theorem 3:
Let \(\lbrack A\rbrack\) be a \(n \times n\) matrix. Then, if \(\lbrack B\rbrack\) is a matrix that results from switching one row with another row, then \(\det(B) = - \det(A)\).
Example 2
Find the determinant of
\[\lbrack A\rbrack = \begin{bmatrix} 10 & - 7 & 0 \\ - 3 & 2.099 & 6 \\ 5 & - 1 & 5 \\ \end{bmatrix}\]
Solution
The end of the forward elimination part of Gaussian elimination with partial pivoting, we would obtain
\[\lbrack B\rbrack = \begin{bmatrix} 10 & - 7 & 0 \\ 0 & 2.5 & 5 \\ 0 & 0 & 6.002 \\ \end{bmatrix}\]
\[\begin{split} \det\left( B \right) &= 10 \times 2.5 \times 6.002\\ &= 150.05 \end{split}\]
Since rows were switched once during the forward elimination part of Gaussian elimination with partial pivoting,
\[\begin{split} \det\left( A \right) &= - \det(B)\\ &= - 150.05 \end{split}\]
Example 3
Prove
\[\det(A) = \frac{1}{\det\left( A^{- 1} \right)}\]
Solution
\[\lbrack A\rbrack\lbrack A\rbrack^{- 1} = \lbrack I\rbrack\]
\[\det(AA^{- 1}) = det(I)\]
\[\det(A)\det(A^{-1}) = 1\]
\[\det(A) = \frac{1}{\det(A^{-1})}\]
If \({\lbrack A\rbrack}\) is a \({n \times n}\) matrix and \({\det(A) \neq 0}\), what other statements are equivalent to it?
(1) \(\lbrack A\rbrack\) is invertible.
(2) \(\lbrack A\rbrack^{- 1}\) exists.
(3) \(\lbrack A\rbrack\ \lbrack X\rbrack = \lbrack C\rbrack\) has a unique solution.
(4) \(\lbrack A\rbrack\ \lbrack X\rbrack = \lbrack 0\rbrack\) only solution is \(\lbrack X\rbrack = \lbrack{0}\rbrack\).
(5) \(\lbrack A\rbrack\ \lbrack A\rbrack^{- 1} = \lbrack I\rbrack = \lbrack A\rbrack^{- 1}\ \lbrack A\rbrack\).
Learning Objectives
After successful completion of this lesson, you should be able to
1) enumerate the pitfalls of the Naive Gauss elimination method
2) show the pitfalls of the Naive Gauss elimination method through examples
Are there any pitfalls of the Naive Gauss elimination method?
Yes, there are two pitfalls of the Naive Gauss elimination method.
Division by zero: First, it is possible for division by zero to occur during the beginning of any of the \(n - 1\) steps of the forward elimination part.
For example
\[\begin{split} 5x_{2} + 6x_{3} &= 11\\ 4x_{1} + 5x_{2} + 7x_{3} &= 16\\ 9x_{1} + 2x_{2} + 3x_{3} &= 15 \end{split}\]
will result in division by zero in the first step of the forward elimination part as the coefficient of \(x_{1}\) in the first equation is zero, as is evident when we write the equations in matrix form.
\[\begin{bmatrix} 0 & 5 & 6 \\ 4 & 5 & 7 \\ 9 & 2 & 3 \\ \end{bmatrix}\begin{bmatrix} x_{1} \\ x_{2} \\ x_{3} \\ \end{bmatrix} = \begin{bmatrix} 11 \\ 16 \\ 15 \\ \end{bmatrix}\]
But what about the equations below: Is division by zero a problem?
\[\begin{split} 5x_{1} + 6x_{2} + 7x_{3} &= 18\\ 10x_{1} + 12x_{2} + 3x_{3} &= 25\\ 20x_{1} + 17x_{2} + 19x_{3} &= 56 \end{split}\]
Written in matrix form,
\[\begin{bmatrix} 5 & 6 & 7 \\ 10 & 12 & 3 \\ 20 & 17 & 19 \\ \end{bmatrix}\begin{bmatrix} x_{1} \\ x_{2} \\ x_{3} \\ \end{bmatrix} = \begin{bmatrix} 18 \\25 \\ 56 \\ \end{bmatrix}\]
there is no issue of division by zero in the the first step of forward elimination part. The pivot element is the coefficient of \(x_{1}\) in the first equation, that is, \(5\), and that is a non-zero number. However, at the end of the first step of the forward elimination part, we get the equations in the following matrix form
\[\begin{bmatrix} 5 & 6 & 7 \\ 0 & 0 & - 11 \\ 0 & - 7 & - 9 \\ \end{bmatrix}\begin{bmatrix} x_{1} \\ x_{2} \\ x_{3} \\ \end{bmatrix} = \begin{bmatrix} 18 \\ - 11 \\ - 16 \\ \end{bmatrix}\]
Now at the beginning of the \(2^{nd}\) step of the forward elimination part, the coefficient of \(x_{2}\) in Equation 2 would be used as the pivot element. That element is zero and hence would create the division by zero problem.
So it is important to consider that the possibility of division by zero can occur at the beginning of any of the \(n-1\) steps of the forward elimination part in the Naive Gauss elimination method.
Round-off error: Second, the Naive Gauss elimination method is prone to round-off errors. These errors are higher when there are many equations as errors propagate more than when there are a small number of equations. Also, if there is a large variation in the order of the magnitude of the numbers, and subtraction of close numbers takes place, it may also create large errors. See the examples below.
Example 1
Use Naive Gauss elimination to solve
\[\begin{split} 20x_{1} + 15x_{2} + 10x_{3} &= 45\\ - 3x_{1} - 2.249x_{2} + 7x_{3} &= 1.751\\ 5x_{1} + x_{2} + 3x_{3} &= 9 \end{split}\]
Use six significant digits with chopping in your calculations.
Solution
Putting the equations in the matrix form, we get
\[\begin{bmatrix} 20 & 15 & 10 \\ - 3 & - 2.249 & 7 \\ 5 & 1 & 3 \\ \end{bmatrix}\begin{bmatrix} x_{1} \\ x_{2} \\ x_{3} \\ \end{bmatrix} = \begin{bmatrix} 45 \\ 1.751 \\ 9 \\ \end{bmatrix}\]
The augmented matrix is
\[\begin{bmatrix} 20 & 15 & 10 & | & 45 \\ -3 & -2.249 & 7 & | & 1.751 \\ 5 & 1 & 3 & | & 9 \\ \end{bmatrix}\]
Forward Elimination
First step
Divide Row 1 by \(20\) and then multiply it by \(-3\), that is, multiply Row 1 by \(- 3/20 = - 0.15\).
\[( \left\lbrack 20\ \ 15\ \ 10\ \ \ |\ \ \ 45 \right\rbrack \ ) \times - 0.15\ \text{gives Row 1 as}\]
\[\left\lbrack - 3 \ \ - 2.25 \ \ - 1.5 \ \ \ | \ \ \ - 6.75 \right\rbrack\]
Subtract the result from Row 2
\[\frac{\begin{matrix} \ \ \lbrack\begin{matrix} -3 & \ \ \ -2.249 & \ \ \ \ \ 7 \\ \end{matrix}\ \ \ \ \ \ | & 1.751\rbrack \\ - \begin{matrix} \lbrack -3 & \ \ \ \ -2.25 \ \ -1.5 \ \ \\ \end{matrix}\ \ \ | & -6.75\rbrack \\ \end{matrix}}{\ \ \ \ \begin{matrix} \begin{matrix} 0 & \ \ \ \ \ 0.001 & \ \ \ \ 8.5 \\ \end{matrix} & \ \ \ \ \ 8.501 \end{matrix}}\]
to get the resulting equations as
\[\begin{bmatrix} 20 & 15 & 10 & | & 45 \\ 0 & 0.001 & 8.5 & | & 8.501 \\ 5 & 1 & 3 & | & 9 \\ \end{bmatrix}\]
Divide Row 1 by \(20\) and then multiply it by \(5\), that is, multiply Row 1 by \(5/20 = 0.25\)
\[\left\lbrack 20\ \ 15\ \ 10\ \ \ |\ \ \ 45 \right\rbrack \ \times 0.25\ \text{gives Row 1 as}\]
\[\left\lbrack 5 \ \ 3.75\ \ 2.5 \ \ \ | \ \ \ 11.25 \right\rbrack\]
Subtract the result from Row 3
\[\displaystyle \frac{\begin{matrix} \ \ \lbrack\begin{matrix} 5 & \ \ \ \ \ \ 1 & \ \ \ \ \ \ 3 \\ \end{matrix}\ \ \ \ \ \ \ | & 9\rbrack \\ - \begin{matrix} \lbrack 5 & \ \ \ \ 3.75 \ \ \ \ \ 2.5 \ \ \\ \end{matrix}\ \ \ | & 11.25\rbrack \\ \end{matrix}}{\ \ \ \begin{matrix} \begin{matrix} 0 &\ -2.75 \ \ \ \ \ \ 0.5 \\ \end{matrix} & \ -2.25 \end{matrix}}\]
to get the resulting equations as
\[\begin{bmatrix} 20 & 15 & 10 & | & 45 \\ 0 & 0.001 & 8.5 & | & 8.501 \\ 0 & -2.75 & 0.5 & | & -2.25 \\ \end{bmatrix}\]
Second step
Now for the second step of the forward elimination part, we will use Row 2 as the pivot equation and eliminate Row 3: Column 2.
Divide Row 2 by \(0.001\) and then multiply it by \(-2.75\), that is, multiply Row 2 by \(- 2.75/0.001 = - 2750\).
\[\left\lbrack 0\ \ 0.001\ \ 8.5\ \ \ |\ \ \ 8.501 \right\rbrack \ \times -2750\ \text{gives Row 2 as}\]
\[\left\lbrack 0 \ \ -2.75\ \ -23375 \ \ \ | \ \ \ - 23377.75 \right\rbrack\]
Rewriting within 6 significant digits with chopping
\[\left\lbrack 0 \ \ -2.75\ \ -23375 \ \ \ | \ \ \ - 23377.7 \right\rbrack\]
Subtract the result from Row 3
\[\displaystyle \frac{\begin{matrix} \ \ \lbrack\begin{matrix} 0 & \ \ \ \ \ \ -2.75 & \ \ \ \ \ \ 0.5 \\ \end{matrix}\ \ \ \ \ \ \ | & -2.25\rbrack \\ - \begin{matrix} \lbrack 0 & \ \ \ \ -2.75 \ \ \ \ \ -23375 \ \ \\ \end{matrix}\ \ \ | & -23377.7\rbrack \\ \end{matrix}}{\ \ \ \begin{matrix} \begin{matrix} 0\ \ \ \ \ \ &\ 0 \ \ \ \ \ \ \ \ \ \ \ 23375.5 \\ \end{matrix} & \ \ \ \ \ \ 23375.45 \end{matrix}}\] Rewriting within 6 significant digits with chopping
\[\left\lbrack 0 \ \ 0\ \ 23375.5 \ \ \ | \ \ \ 23375.4 \right\rbrack\] to get the resulting equations as
\[\begin{bmatrix} 20 & 15 & 10 & | & 45 \\ 0 & 0.001 & 8.5 & | & 8.501 \\ 0 & 0 & 23375.5 & | & 23375.4 \\ \end{bmatrix}\]
This is the end of the forward elimination part.
Back substitution
We can now solve the above equations by back substitution. From the third equation,
\[23375.5x_{3} = 23375.4\]
\[\begin{split} x_{3} &= \frac{23375.4}{23375.5}\\ &= 0.999995 \end{split}\]
Substituting the value of \(x_{3}\) in the second equation
\[0.001x_{2} + 8.5x_{3} = 8.501\]
\[\begin{split} x_{2} &= \frac{8.501 - 8.5x_{3}}{0.001} \\ &= \frac{8.501 - 8.5 \times 0.999995}{0.001} \\ &= \frac{8.501 - 8.49995}{0.001}\\ &= \frac{0.00105}{0.001}\\ &= 1.05 \end{split}\]
Substituting the value of \(x_{3}\) and \(x_{2}\) in the first equation,
\[20x_{1} + 15x_{2} + 10x_{3} = 45\]
\[\begin{split} x_{1} &= \frac{45 - 15x_{2} - 10x_{3}}{20}\\ &= \frac{45 - 15 \times 1.05 - 10 \times 0.999995}{20}\\ &= \frac{45 - 15.75 - 9.99995}{20} \\ &= \frac{29.25 - 9.99995}{20} \\ &= \frac{19.2500}{20} \\ &= 0.9625 \end{split}\]
This is the end of the back substitution part.
Hence the solution is
\[\begin{split} \lbrack X\rbrack &= \begin{bmatrix} x_{1} \\ x_{2} \\ x_{3} \\ \end{bmatrix}\\ &= \begin{bmatrix} 0.9625 \\ 1.05 \\ 0.999995 \\ \end{bmatrix} \end{split}\]
Compare this with the exact solution of
\[\begin{split} \left\lbrack X \right\rbrack &= \begin{bmatrix} x_{1} \\ x_{2} \\ x_{3} \\ \end{bmatrix}\\ &= \begin{bmatrix} 1 \\ 1 \\ 1 \\ \end{bmatrix} \end{split}\]
Example 2
In Example 1, we used Naive Gauss elimination to solve
\[\begin{split} 20x_{1} + 15x_{2} + 10x_{3} &= 45\\ - 3x_{1} - 2.249x_{2} + 7x_{3} &= 1.751\\ 5x_{1} + x_{2} + 3x_{3} &= 9\end{split}\]
using six significant digits with chopping in your calculations? Repeat the problem, but now use five significant digits with chopping in your calculations.
Solution
Putting the equations in the matrix form, we get
\[\begin{bmatrix} 20 & 15 & 10 \\ - 3 & - 2.249 & 7 \\ 5 & 1 & 3 \\ \end{bmatrix}\begin{bmatrix} x_{1} \\ x_{2} \\ x_{3} \\ \end{bmatrix} = \begin{bmatrix} 45 \\ 1.751 \\ 9 \\ \end{bmatrix}\]
The augmented matrix is
\[\begin{bmatrix} 20 & 15 & 10 & | & 45 \\ -3 & -2.249 & 7 & | & 1.751 \\ 5 & 1 & 3 & | & 9 \\ \end{bmatrix}\]
Forward Elimination of Unknowns
First step
Divide Row 1 by \(20\) and then multiply it by \(-3\), that is, multiply Row 1 by \(- 3/20 = - 0.15\).
\[( \left\lbrack 20\ \ 15\ \ 10\ \ \ |\ \ \ 45 \right\rbrack \ ) \times - 0.15\ \text{gives Row 1 as}\]
\[\left\lbrack - 3 \ \ - 2.25 \ \ - 1.5 \ \ \ | \ \ \ - 6.75 \right\rbrack\]
Subtract the result from Row 2
\[\frac{\begin{matrix} \ \ \lbrack\begin{matrix} -3 & \ \ \ -2.249 & \ \ \ \ \ 7 \\ \end{matrix}\ \ \ \ \ \ | & 1.751\rbrack \\ - \begin{matrix} \lbrack -3 & \ \ \ \ -2.25 \ \ -1.5 \ \ \\ \end{matrix}\ \ \ | & -6.75\rbrack \\ \end{matrix}}{\ \ \ \ \begin{matrix} \begin{matrix} 0 & \ \ \ \ \ 0.001 & \ \ \ \ 8.5 \\ \end{matrix} & \ \ \ \ \ 8.501 \end{matrix}}\] to get the resulting equations as
\[\begin{bmatrix} 20 & 15 & 10 & | & 45 \\ 0 & 0.001 & 8.5 & | & 8.501 \\ 5 & 1 & 3 & | & 9 \\ \end{bmatrix}\]
Divide Row 1 by \(20\) and then multiply it by \(5\), that is, multiply Row 1 by \(5/20 = 0.25\).
\[\left\lbrack 20\ \ 15\ \ 10\ \ \ |\ \ \ 45 \right\rbrack \ \times 0.25\ \text{gives Row 1 as}\]
\[\left\lbrack 5 \ \ 3.75\ \ 2.5 \ \ \ | \ \ \ 11.25 \right\rbrack\]
Subtract the result from Row 3
\[\displaystyle \frac{\begin{matrix} \ \ \lbrack\begin{matrix} 5 & \ \ \ \ \ \ 1 & \ \ \ \ \ \ 3 \\ \end{matrix}\ \ \ \ \ \ \ | & 9\rbrack \\ - \begin{matrix} \lbrack 5 & \ \ \ \ 3.75 \ \ \ \ \ 2.5 \ \ \\ \end{matrix}\ \ \ | & 11.25\rbrack \\ \end{matrix}}{\ \ \ \begin{matrix} \begin{matrix} 0 &\ -2.75 \ \ \ \ \ \ 0.5 \\ \end{matrix} & \ -2.25 \end{matrix}}\]
to get the resulting equations as
\[\begin{bmatrix} 20 & 15 & 10 & | & 45 \\ 0 & 0.001 & 8.5 & | & 8.501 \\ 0 & -2.75 & 0.5 & | & -2.25 \\ \end{bmatrix}\]
Second step
Now for the second step of the forward elimination part, we will use Row 2 as the pivot equation and eliminate Row 3: Column 2.
Divide Row 2 by \(0.001\) and then multiply it by \(-2.75\), that is, multiply Row 2 by \(- 2.75/0.001 = - 2750\).
\[\left\lbrack 0\ \ 0.001\ \ 8.5\ \ \ |\ \ \ 8.501 \right\rbrack \ \times -2750\ \text{gives Row 2 as}\]
\[\left\lbrack 0 \ \ -2.75\ \ -23375 \ \ \ | \ \ \ - 23377.75 \right\rbrack\]
Rewriting within 5 significant digits with chopping
\[\left\lbrack 0 \ \ -2.75\ \ -23375 \ \ \ | \ \ \ - 23377 \right\rbrack\]
Subtract the result from Row 3
\[\frac{\begin{matrix} \ \ \lbrack\begin{matrix} 0 & \ \ \ \ \ \ -2.75 & \ \ \ \ \ \ 0.5 \\ \end{matrix}\ \ \ \ \ \ \ | & -2.25\rbrack \\ - \begin{matrix} \lbrack 0 & \ \ \ \ -2.75 \ \ \ \ \ -23375 \ \ \\ \end{matrix}\ | & -23377\rbrack \\ \end{matrix}}{\begin{matrix} \begin{matrix}\ \ \ 0 &\ \ \ \ \ \ \ \ \ \ 0 \ \ \ \ \ \ \ \ \ \ \ 23375.5 \\ \end{matrix} & \ \ \ \ \ \ \ \ 23374.75 \end{matrix}}\]
Rewriting with 5 significant digits with chopping
\[\left\lbrack 0 \ \ 0\ \ 23375 \ \ \ | \ \ \ 23374 \right\rbrack\]
to get the resulting equations as
\[\begin{bmatrix} 20 & 15 & 10 & | & 45 \\ 0 & 0.001 & 8.5 & | & 8.501 \\ 0 & 0 & 23375 & | & 23374 \\ \end{bmatrix}\]
This marks the end of the forward elimination part.
Back substitution
We can now solve the above equations by back substitution. From the third equation,
\[\begin{split} 23375x_{3} &= 23374\\ x_{3} &= \frac{23374}{23375}\\ &= 0.99995 \end{split}\]
Substituting the value of \(x_{3}\) in the second equation
\[0.001x_{2} + 8.5x_{3} = 8.501\]
\[\begin{split} x_{2} &= \frac{8.501 - 8.5x_{3}}{0.001}\\ &= \frac{8.501 - 8.5 \times 0.99995}{0.001}\\ &= \frac{8.501 - 8.499575}{0.001}\\ &= \frac{8.501 - 8.4995}{0.001}\\ &= \frac{0.0015}{0.001}\\ &= 1.5 \end{split}\]
Substituting the value of \(x_{3}\) and \(x_{2}\) in the first equation,
\[20x_{1} + 15x_{2} + 10x_{3} = 45\]
\[\begin{split} x_{1} &= \frac{45 - 15x_{2} - 10x_{3}}{20}\\ &= \frac{45 - 15 \times 1.5 - 10 \times 0.99995}{20}\\ &= \frac{45 - 22.5 - 9.9995}{20}\\ &= \frac{22.5 - 9.9995}{20}\\ &= \frac{12.5005}{20}\\ &= \frac{12.500}{20}\\ &= 0.625 \end{split}\]
This marks the end of the back substitution part.
Hence the solution is
\[\begin{split} \left\lbrack X \right\rbrack &= \begin{bmatrix} x_{1} \\ x_{2} \\ x_{3} \\ \end{bmatrix}\\ &= \begin{bmatrix} 0.625 \\ 1.5 \\ 0.99995 \\ \end{bmatrix} \end{split}\]
Compare this with the exact solution of
\[\left\lbrack X \right\rbrack = \begin{bmatrix} x_{1} \\ x_{2} \\ x_{3} \\ \end{bmatrix} = \begin{bmatrix} 1 \\ 1 \\ 1 \\ \end{bmatrix}\]
Reducing the number of significant digits carried from 6 to 5 results in a substantial round-off error. In the next lesson, we will discuss how we can alleviate the two pitfalls of the Naive Gauss elimination method.
Learning Objectives
After successful completion of this lesson, you should be able to
1) write the algorithm to solve a set of simultaneous linear equations using Gaussian elimination with Partial Pivoting.
What are some techniques for improving the Naïve Gauss elimination method?
As seen in the examples in the previous lesson, round-off errors were large when five significant digits were used as opposed to six significant digits. One method of decreasing the round-off error would be to use more significant digits, that is, use double or quad precision for representing the numbers. However, this would not avoid possible division by zero errors in the Naïve Gauss elimination method. To avoid division by zero as well as reduce (not eliminate) round-off error, Gaussian elimination with partial pivoting is the method of choice.
How does Gaussian elimination with partial pivoting differ from Naïve Gauss elimination?
The two methods are the same, except at the beginning of each step of the forward elimination part, a row switching is done based on the following criterion. If there are \(n\) equations, then there are \(n - 1\) steps of the forward elimination part. At the beginning of the \(k^{{th}}\) step of the forward elimination part, one finds the maximum of
\[\left| a_{{kk}} \right|,\left| a_{k + 1,k} \right|,\ldots\ldots,\left| a_{{nk}} \right|\]
Then if the maximum of these values is \(\left| a_{{pk}} \right|\) , \(k \leq p \leq n\), then switch rows \(p\) and \(k\).
The other steps of the forward elimination part are the same as the Naïve Gauss elimination method. The back substitution part stays exactly the same as the Naive Gauss elimination method.
Learning Objectives
After successful completion of this lesson, you should be able to:
1) solve a set of simultaneous linear equations using the Gauss elimination method with partial pivoting
Applications
In the previous lessons, you learned why we modify the Naive Gauss elimination method to the Gaussian elimination with partial pivoting. Then we discussed, the theory behind the method. In this lesson, we will apply the theory to solve a set of simultaneous linear equations.
Example 1
In the examples in the previous lesson, we used Naive Gauss elimination to solve
\[\begin{split} 20x_{1} + 15x_{2} + 10x_{3} &= 45\\ - 3x_{1} - 2.249x_{2} + 7x_{3} &= 1.751\\ 5x_{1} + x_{2} + 3x_{3} &= 9 \end{split}\]
using five and six significant digits with chopping in the calculations. When we used five significant digits with chopping, the solution found was
\[\begin{split} \left\lbrack X \right\rbrack &= \begin{bmatrix} x_{1} \\ x_{2} \\ x_{3} \\ \end{bmatrix}\\ &= \begin{bmatrix} 0.625 \\ 1.5 \\ 0.99995 \\ \end{bmatrix} \end{split}\]
This is quite different from the exact solution of
\[\begin{split} \left\lbrack X \right\rbrack &= \begin{bmatrix} x_{1} \\ x_{2} \\ x_{3} \\ \end{bmatrix}\\ &= \begin{bmatrix} 1 \\ 1 \\ 1 \\ \end{bmatrix} \end{split}\]
Redo using Gaussian elimination with partial pivoting. Use five significant digits with chopping in all your calculations.
Solution
The augmented matrix is
\[\begin{bmatrix} 20 & 15 & 10 & | & 45 \\ -3 & -2.249 & 7 & | & 1.751 \\ 5 & 1 & 3 & | & 9 \\ \end{bmatrix}\]
Forward Elimination of Unknowns
Now for the first step of the forward elimination part, the absolute value of the first column elements below Row 1 is
\[\left| 20 \right|,\left| - 3 \right|,\left| 5 \right|\]
or
\[20,\ 3,\ 5\]
So, the largest absolute value is in Row \(1\). So as per Gaussian elimination with partial pivoting, the switch is between Row \(1\) and Row \(1\) to give
\[\begin{bmatrix} 20 & 15 & 10 & | & 45 \\ -3 & -2.249 & 7 & | & 1.751 \\ 5 & 1 & 3 & | & 9 \\ \end{bmatrix}\]
Divide Row \(1\) by \(20\) and then multiply it by \(-3\), that is, multiply Row \(1\) by \(\displaystyle - 3/20 = - 0.15\).
\[( \left\lbrack 20\ \ 15\ \ 10\ \ \ |\ \ \ 45 \right\rbrack \ ) \times - 0.15\ \text{gives Row 1 as}\]
\[\left\lbrack - 3 \ \ - 2.25 \ \ - 1.5 \ \ \ | \ \ \ - 6.75 \right\rbrack\]
Subtract the result from Row \(2\)
\[\frac{\begin{matrix} \ \ \lbrack\begin{matrix} -3 & \ \ \ -2.249 & \ \ \ \ \ 7 \\ \end{matrix}\ \ \ \ \ \ | & 1.751\rbrack \\ - \begin{matrix} \lbrack -3 & \ \ \ \ -2.25 \ \ -1.5 \ \ \\ \end{matrix}\ \ \ | & -6.75\rbrack \\ \end{matrix}}{\ \ \ \ \begin{matrix} \begin{matrix} 0 & \ \ \ \ \ 0.001 & \ \ \ \ 8.5 \\ \end{matrix} & \ \ \ \ \ 8.501 \end{matrix}}\]
to get the resulting equations as
\[\begin{bmatrix} 20 & 15 & 10 & | & 45 \\ 0 & 0.001 & 8.5 & | & 8.501 \\ 5 & 1 & 3 & | & 9 \\ \end{bmatrix}\]
Divide Row \(1\) by \(20\) and then multiply it by \(5\), that is, multiply Row \(1\) by \(5/20 = 0.25\).
\[\left\lbrack 20\ \ 15\ \ 10\ \ \ |\ \ \ 45 \right\rbrack \ \times 0.25\ \text{gives Row 1 as}\]
\[\left\lbrack 5 \ \ 3.75\ \ 2.5 \ \ \ | \ \ \ 11.25 \right\rbrack\]
Subtract the result from Row \(3\)
\[\displaystyle \frac{\begin{matrix} \ \ \lbrack\begin{matrix} 5 & \ \ \ \ \ \ 1 & \ \ \ \ \ \ 3 \\ \end{matrix}\ \ \ \ \ \ \ | & 9\rbrack \\ - \begin{matrix} \lbrack 5 & \ \ \ \ 3.75 \ \ \ \ \ 2.5 \ \ \\ \end{matrix}\ \ \ | & 11.25\rbrack \\ \end{matrix}}{\ \ \ \begin{matrix} \begin{matrix} 0 &\ -2.75 \ \ \ \ \ \ 0.5 \\ \end{matrix} & \ -2.25 \end{matrix}}\]
to get the resulting equations as
\[\begin{bmatrix} 20 & 15 & 10 & | & 45 \\ 0 & 0.001 & 8.5 & | & 8.501 \\ 0 & -2.75 & 0.5 & | & -2.25 \\ \end{bmatrix}\]
This marks the end of the first step of the forward elimination part.
Now for the second step of the forward elimination part, the absolute value of the second column elements below Row 1 is
\[\left| 0.001 \right|,\left| - 2.75 \right|\]
or
\[0.001,\ 2.75\]
So, the largest absolute value is in Row \(3\). So, Row \(2\) is switched with Row \(3\) to give
\[\begin{bmatrix} 20 & 15 & 10 & | & 45 \\ 0 & -2.75 & 0.5 & | & -2.25 \\ 0 & 0.001 & 8.5 & | & 8.501 \\ \end{bmatrix}\]
Divide Row \(2\) by \(-2.75\) and then multiply it by \(0.001\), that is, multiply Row \(2\) by \(0.001/ - 2.75 = - 0.00036363\).
\[\left\lbrack 0 \ \ - 2.75\ \ 0.5 \ \ \ |\ \ \ - 2.25 \right\rbrack \ \times - 0.00036363\ \text{gives Row 2 as}\]
\[\left\lbrack 0 \ \ \ 0.00099998 \ \ \ - 0.00018182 \ \ \ |\ \ \ 0.00081816 \right\rbrack\]
Subtract the result from Row \(3\)
\[\displaystyle \frac{\begin{matrix} \ \ \ \lbrack \begin{matrix} 0 & \ \ \ \ \ \ \ \ \ \ \ 0.001 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 8.5 \\ \end{matrix} \ \ \ \ \ \ \ \ \ \ \ \ \ \ | & 8.501\rbrack \\ - \begin{matrix} \lbrack 0 & \ \ \ \ 0.00099998 \ \ \ \ \ -0.00018182 \ \ \\ \end{matrix}\ \ \ | & 0.00081816\rbrack \\ \end{matrix}}{\ \ \begin{matrix} \ \begin{matrix} 0 &\ \ \ \ \ \ \ \ \ \ \ 0 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 8.50018182 \\ \end{matrix} & \ \ \ \ \ \ \ \ \ 8.50018184 \end{matrix}}\]
Rewriting within \(5\) significant digits with chopping
\[\left\lbrack 0 \ \ \ 0 \ \ \ 8.5001 \ \ \ | \ \ \ 8.5001 \right\rbrack\]
to get the resulting equations as
\[\begin{bmatrix} 20 & 15 & 10 & | & 45 \\ 0 & -2.75 & 0.5 & | & -2.25 \\ 0 & 0 & 8.5001 & | & 8.5001 \\ \end{bmatrix}\]
Back substitution
\[8.5001x_{3} = 8.5001\]
\[\begin{split} x_{3} &= \frac{8.5001}{8.5001}\\ &= 1 \end{split}\]
Substituting the value of \(x_{3}\) in Row \(2\)
\[- 2.75x_{2} + 0.5x_{3} = - 2.25\]
\[\begin{split} x_{2} &= \frac{- 2.25 - 0.5x_{3}}{- 2.75}\\ &= \frac{- 2.25 - 0.5 \times 1}{- 2.75}\\ &= \frac{- 2.25 - 0.5}{- 2.75}\\ &= \frac{- 2.75}{- 2.75}\\ &= 1\end{split}\]
Substituting the value of \(x_{3}\) and \(x_{2}\) in Row 1
\[20x_{1} + 15x_{2} + 10x_{3} = 45\]
\[\begin{split} x_{1} &= \frac{45 - 15x_{2} - 10x_{3}}{20}\\ &= \frac{45 - 15 \times 1 - 10 \times 1}{20}\\ &= \frac{45 - 15 - 10}{20}\\ &= \frac{30 - 10}{20}\\ &= \frac{20}{20}\\ &= 1 \end{split}\]
So, the solution is
\[\begin{split} \left\lbrack X \right\rbrack &= \begin{bmatrix} x_{1} \\ x_{2} \\ x_{3} \\ \end{bmatrix}\\ &= \begin{bmatrix} 1 \\ 1 \\ 1 \\ \end{bmatrix} \end{split}\]
This, in fact, is the exact solution. By coincidence only, in this case, the round-off error is not only reduced but fully removed.
Example 2
The upward velocity of a rocket is given at three different times in Table 1.
Table 1: Velocity vs. time data.
| 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\]
The coefficients \(a_{1},a_{2}\), and \(a_{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}\]
Find the values of \(a_{1},a_{2},\) and \(a_{3}\) using the Gaussian elimination method with partial pivoting showing 6 significant digits. Find the velocity at \(t = 6,\ 7.5,\ 9,\ 11\) seconds.
Solution
The augmented matrix is
\[\begin{bmatrix} 25 & 5 & 1 & | & 106.8 \\ 64 & 8 & 1 & | & 177.2 \\ 144 & 12 & 1 & | & 279.2 \\ \end{bmatrix}\]
Forward Elimination of unknowns
For the first step of the forward elimination part, the absolute value of the first column elements is
\[|25|,\ |64|,\ |144|\]
Or
\[25,\ 64,\ 144\]
So, the largest absolute value is in the Row 3. As per the Gaussian elimination with partial pivoting, we switch Row 3 by Row 1 to give
\[\begin{bmatrix} 144 & 12 & 1 & | & 279.2 \\ 64 & 8 & 1 & | & 177.2 \\ 25 & 5 & 1 & | & 106.8 \\ \end{bmatrix}\]
Divide Row 1 by \(144\) and then multiply it be \(64\), that is, multiply Row 1 by \(64/144 = 0.444444\)
\[(\lbrack 144\ \ \ 12\ \ \ 1\ \ \ |\ \ \ 279.2\rbrack) \times 0.444444\ \text{gives Row 1 as}\]
\[\lbrack 64\ \ \ 5.33333\ \ \ 0.444444\ \ \ |\ \ \ 124.089\rbrack\]
Subtract the result from Row 2
\[\frac{\begin{matrix} \ \ \ \lbrack\begin{matrix} 64 & \ \ \ \ 8 & \ \ \ \ \ \ \ \ \ \ \ 1 \\ \end{matrix}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ |\ \ & 177.2\rbrack \\ - \lbrack\begin{matrix} 64 & 5.33333 & 0.444444 \\ \end{matrix}\ \ \ \ \ | & 124.089\rbrack \\ \end{matrix}}{\begin{matrix} \begin{matrix} \ \ \ \ \ \ 0 & \ \ 2.66667 & 0.555556 \\ \end{matrix} & \ \ \ \ \ \ \ \ 53.1111 \\ \end{matrix}}\]
To get the resulting equation as
\[\begin{bmatrix} 144 & 12 & 1 & | & 279.2 \\ 0 & 2.66667 & 0.555556 & | & 53.1111 \\ 25 & 5 & 1 & | & 106.8 \\ \end{bmatrix}\]
Divide Row 1 by \(144\) and then multiply it by \(25\), that is, multiply Row 1 by \(25/144 = 0.173611\).
\[(\lbrack 144\ \ \ 12\ \ \ 1\ \ \ |\ \ \ 279.2\rbrack) \times 0.173611\ \text{gives Row 1 as}\]
\[\lbrack 25\ \ \ 2.08333\ \ 0.172611\ \ \ |\ \ \ \ 48.4722\rbrack\]
Subtract the result from Row 3
\[\frac{\begin{matrix} {\ \ \ \ }\lbrack\begin{matrix} 25 & 5 & \ \ \ \ \ \ \ \ \ \ \ \ \ 1 \\ \end{matrix}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ | & 106.8\rbrack \\ - \begin{matrix} \lbrack 25 & 2.08333 & 0.173611 \\ \end{matrix}\ \ \ \ \ \ \ \ | & 48.4722\rbrack \\ \end{matrix}}{{\ \ \ \ }\begin{matrix} \begin{matrix} 0 \ \ \ & 2.91667 & 0.826389 \\ \end{matrix} & \ \ \ \ \ \ \ 58.3278 \\ \end{matrix}}\]
to get the resulting equations as
\[\begin{bmatrix} 144 & 12 & 1 & | & 279.2 \\ 0 & 2.66667 & 0.555556 & | & 53.1111 \\ 0 & 2.91667 & 0.826389 & | & 58.3278 \\ \end{bmatrix}\]
This marks the end of the first step of forward elimination part.
Now for the second step of forward elimination part, the absolute value of the second column elements Row 2 and below are
\[|2.66667|,\ |2.91667|\]
Or
\[2.66667,\ 2.91667\]
The largest value is in Row 3. So, Row 2 is switched with Row 3 to give
\[\begin{bmatrix} 144 & 12 & 1 & | & 279.2 \\ 0 & 2.91667 & 0.826389 & | & 58.3278 \\ 0 & 2.66667 & 0.555556 & | & 53.1111 \\ \end{bmatrix}\]
Divide Row 2 by \(2.91667,\) then multiply it by \(2.66667\), that is, multiply Row 2 by \(2.66667/2.91667 = 0.914286\).
\[(\lbrack 0\ \ \ 2.91667\ \ \ 0.826389\ \ \ \ |\ \ \ 58.3278\rbrack)\ \times \ 0.914286\ \text{gives Row 2 as}\]
\[\lbrack 0\ \ \ 2.66667\ \ \ 0.755556\ \ \ \ |\ \ \ \ 53.3283\rbrack\]
Subtract the result from Row 3
\[\frac{\begin{matrix} {\ \ \ \ }\lbrack\begin{matrix} 0\ \ \ \ & {\ \ \ \ }2.66667 & {\ \ \ \ \ \ \ }0.555556 \\ \end{matrix}\ \ \ \ \ \ \ \ \ | & 53.1111\rbrack \\ - \begin{matrix} \lbrack 0\ \ \ \ \ & {\ \ \ }2.66667 & \ \ \ \ \ \ \ 0.755556\ \ \ \ \ \ \ \ \\ \end{matrix}\ \ | & 53.3283\rbrack \\ \end{matrix}}{\ \ \ \ \begin{matrix} \begin{matrix} \ 0\ \ {\ \ \ \ \ \ \ } & 0\ & \ \ \ \ \ \ \ \ \ \ \ \ \ - 0.2\ \\ \end{matrix} & {\ \ \ } \\ \end{matrix}{\ \ \ \ }{\ \ } - 0.217189}\]
To get the resulting equations as
\[\begin{bmatrix} 144 & 12 & 1 & | & 279.2 \\ 0 & 2.91667 & 0.826389 & | & 58.3278 \\ 0 & 0 & - 0.2 & | & - 0.217189 \\ \end{bmatrix}\]
Back Substitution
\[- 0.2a_{3}\ = \ - 0.217189\]
\[\begin{split} a_{3}\ &= \ \frac{- 0.217189}{- 0.2}\\ a_{3}\ &= 1.08595\end{split}\]
Substituting the value of \(a_{3}\) in Row 2
\[2.91667a_{2} + 0.826389a_{3}\ = \ 58.3278\]
\[\begin{split} a_{2}\ &= \frac{58.3278 - 0.826389 \times a_{3}}{2.91667}\\ &= \ \frac{58.3278 - 0.826389 \times 1.08595}{2.91667}\\ &= \frac{57.4304}{2.91667}\\ &= 19.6903 \end{split}\]
Substituting the value of \(a_{3}\) and \(a_{2}\) in Row 1
\[144a_{1} + 12a_{2} + {1a}_{3}\ = \ 279.2\]
\[\begin{split} a_{1} &= \frac{279.2 - 12a_{2} - 1a_{3}}{144}\\ &= \frac{279.2 - 12 \times 19.6903 - 1.08595}{144}\\ &= \frac{41.8305}{144}\\ &= 0.290489 \end{split}\]
Hence, the solution vector is
\[\begin{bmatrix} a_{1} \\ a_{2} \\ a_{3} \\ \end{bmatrix} = \begin{bmatrix} 0.290489 \\ 19.6903 \\ 1.08595 \\ \end{bmatrix}\]
The polynomial that passes through the three data points is then
\[\begin{split} v\left( t \right) &= a_{1}t^{2} + a_{2}t + a_{3}\\ &= 0.290489t^{2} + 19.6903t + 1.08595,\ \ 5 \leq t \leq 12 \end{split}\]
Since we want to find the velocity at \(t = 6,\ 7.5,\ 9\ and\ 11\) seconds, we could simply substitute each value of \(t\) in \(v\left( t \right) = 0.290489t^{2} + 19.6903t + 1.08595\) and find the corresponding velocity. For example, at \(t = 6\)
\[\begin{split} v\left( 6 \right) &= 0.290489{(6)}^{2} + 19.6903(6) + 1.08595\\ &= \ 129.685\ \text{m/s} \end{split}\]
However, we could also find all the needed values of velocity at \(t = 6,\ 7.5,\ 9,\ 11\) seconds using matrix multiplication.
\[v\left( t \right) = \left\lbrack 0.290489\ \ 19.6903\ \ 1.08595 \right\rbrack\begin{bmatrix} t^{2} \\ t \\ 1 \\ \end{bmatrix}\]
So, if we want to find \(v\left( 6 \right),\ v\left( 7.5 \right),\ v\left( 9 \right),\ v\left( 11 \right),\) it is given by
\[\begin{split}\left\lbrack v\left( 6 \right)v\left( 7.5 \right)v\left( 9 \right)v\left( 11 \right) \right\rbrack &= \left\lbrack 0.290489\ \ 19.6903\ \ 1.08595 \right\rbrack\begin{bmatrix} 6^{2} & 7.5^{2} & 9^{2} & 11^{2} \\ 6 & 7.5 & 9 & 11 \\ 1 & 1 & 1 & 1 \\ \end{bmatrix} \\ &= \left\lbrack 0.290489\ \ 19.6903\ \ 1.08595 \right\rbrack\begin{bmatrix} 36 & 56.25 & 81 & 121 \\ 6 & 7.5 & 9 & 11 \\ 1 & 1 & 1 & 1 \\ \end{bmatrix}\\ &= \left\lbrack 129.685\ \ 165.103\ \ 201.828\ \ 252.828 \right\rbrack \end{split}\]
\[v(6) = 129.685\ \text{m/s}\]
\[v(7.5) = 165.103\ \text{m/s}\]
\[v(9) = 201.828\ \text{m/s}\]
\[v(11) = 252.828\ \text{m/s}\]
Multiple Choice Test
(1). The goal of the forward elimination part in the Naive Gauss elimination method is to reduce the coefficient matrix to a (an) _____________ matrix.
(A) diagonal
(B) identity
(C) lower triangular
(D) upper triangular
(2). Division by zero during the forward elimination part in Naive Gaussian elimination of the set of equations \(\left\lbrack A \right\rbrack\left\lbrack X \right\rbrack = \left\lbrack C \right\rbrack\) implies the coefficient matrix \(\left\lbrack A \right\rbrack\)
(A) is invertible
(B) is nonsingular
(C) may be singular or nonsingular
(D) is singular
(3). Using a computer with four significant digits with chopping, the Naive Gauss elimination solution to
\[\begin{matrix} 0.0030x_{1} + 55.23x_{2} = 58.12 \\ 6.239x_{1} - 7.123x_{2} = 47.23 \\ \end{matrix}\] is
(A) \(x_{1} = 26.66;\ x_{2} = 1.051\)
(B) \(x_{1} = 8.769;\ x_{2} = 1.051\)
(C) \(x_{1} = 8.800;\ x_{2} = 1.000\)
(D) \(x_{1} = 8.771;\ x_{2} = 1.052\)
(4). Using a computer with four significant digits with chopping, the Gaussian elimination with partial pivoting method solution to
\[\begin{matrix} 0.0030x_{1} + 55.23x_{2} = 58.12 \\ 6.239x_{1} - 7.123x_{2} = 47.23 \\ \end{matrix}\] is
(A) \(x_{1} = 26.66;\ x_{2} = 1.051\)
(B) \(x_{1} = 8.769;\ x_{2} = 1.051\)
(C) \(x_{1} = 8.800;\ x_{2} = 1.000\)
(D) \(x_{1} = 8.771;\ x_{2} = 1.052\)
(5). At the end of the forward elimination part of the Naive Gauss elimination method on the following equations
\[\begin{bmatrix} {4.2857 \times 1}{0}^{{7}} & {- 9.2307 \times 1}{0}^{{5}} & {0} & {0} \\ {4.2857 \times 1}{0}^{{7}} & {- 5.4619 \times 1}{0}^{{5}} & {- 4.2857 \times 1}{0}^{{7}} & {5.4619 \times 1}{0}^{{5}} \\ {- 6.5} & {- 0.15384} & {6.5} & {0.15384} \\ {0} & {0} & {4.2857 \times 1}{0}^{{7}} & {- 3.6057 \times 1}{0}^{{5}} \\ \end{bmatrix}{{\ \ }}\begin{bmatrix} {c}_{{1}} \\ {c}_{{2}} \\ {c}_{{3}} \\ {c}_{{4}} \\ \end{bmatrix}{=}\begin{bmatrix} {- 7.887 \times 1}{0}^{{3}} \\ {0} \\ {0.007} \\ {0} \\ \end{bmatrix}\]
the resulting equations in matrix form are given by
\[\begin{bmatrix} {4.2857 \times 1}{0}^{{7}} & {- 9.2307 \times 1}{0}^{{5}} & {0} & {0} \\ {0} & {3.7688 \times 1}{0}^{{5}} & {- 4.2857 \times 1}{0}^{{7}} & {5.4619 \times 1}{0}^{{5}} \\ {0} & {0} & {- 26.9140} & {0.579684} \\ {0} & {0} & {0} & {5.62500 \times 1}{0}^{{5}} \\ \end{bmatrix}{{\ \ }}\begin{bmatrix} {c}_{{1}} \\ {c}_{{2}} \\ {c}_{{3}} \\ {c}_{{4}} \\ \end{bmatrix}{=}\begin{bmatrix} {- 7.887 \times 1}{0}^{{3}} \\ {7.887 \times 1}{0}^{{3}} \\ {1.19530 \times 1}{0}^{{- 2}} \\ {1.90336 \times 1}{0}^{{4}} \\ \end{bmatrix}\]
The determinant of the original coefficient matrix is
(A) \({0.00}\)
(B) \({4.2857 \times 1}{0}^{{7}}\)
(C) \({5.486 \times 1}{0}^{{19}}\)
(D) \({- 2.445 \times 1}{0}^{{20}}\)
(6). The following data is given for the velocity of the rocket as a function of time. To find the velocity at \(t = 21s\), you are asked to use a quadratic polynomial, \(v(t) = at^{2} + {bt} + c\), to approximate the velocity profile.
| \(t\) | \((s)\) | \(0\) | \(14\) | \(15\) | \(20\) | \(30\) | \(35\) |
|---|---|---|---|---|---|---|---|
| \(v(t)\) | \((m/s)\) | \(0\) | \(227.04\) | \(362.78\) | \(517.35\) | \(602.97\) | \(901.67\) |
The correct set of equations that will find a, b and c are
(A) \(\begin{bmatrix} {176} & {14} & {1} \\ {225} & {15} & {1} \\ {400} & {20} & {1} \\ \end{bmatrix}\begin{bmatrix} {a} \\ {b} \\ {c} \\ \end{bmatrix}{=}\begin{bmatrix} {227.04} \\ {362.78} \\ {517.35} \\ \end{bmatrix}\)
(B) \(\begin{bmatrix} {225} & {15} & {1} \\ {400} & {20} & {1} \\ {900} & {30} & {1} \\ \end{bmatrix}\begin{bmatrix} {a} \\ {b} \\ {c} \\ \end{bmatrix}{=}\begin{bmatrix} {362.78} \\ {517.35} \\ {602.97} \\ \end{bmatrix}\)
(C) \(\begin{bmatrix} {0} & {0} & {1} \\ {225} & {15} & {1} \\ {400} & {20} & {1} \\ \end{bmatrix}\begin{bmatrix} {a} \\ {b} \\ {c} \\ \end{bmatrix}{=}\begin{bmatrix} {0} \\ {362.78} \\ {517.35} \\ \end{bmatrix}\)
(D) \(\begin{bmatrix} 400 & 20 & 1 \\ 900 & 30 & 1 \\ 1225 & 35 & 1 \\ \end{bmatrix}\begin{bmatrix} a \\ b \\ c \\ \end{bmatrix} = \begin{bmatrix} 517.35 \\ 602.97 \\ 901.67 \\ \end{bmatrix}\)
For complete solution, go to
http://nm.mathforcollege.com/mcquizzes/04sle/quiz_04sle_gaussianelimination_solution.pdf
Problem Set
(1). Use Naive Gauss elimination to solve
\[{4x_{1} + x_{2} - x_{3} = - 2}\] \[{5x_{1} + x_{2} + 2x_{3} = 4}\] \[{6x_{1} + x_{2} + x_{3} = 6}\]
Answer: \(\left[\begin{matrix}x_1\\x_2\\x_3\\\end{matrix}\right]=\left[\begin{matrix}3\\-13\\1\\\end{matrix}\right]\)
(2). Assume that you are using a computer with four significant digits with chopping. Use the Naive Gauss elimination method to solve
\[{4x_{1} + x_{2} - x_{3} = - 2}\] \[{5x_{1} + x_{2} + 2x_{3} = 4}\] \[{6x_{1} + x_{2} + x_{3} = 6}\]
Answer: \(\left[\begin{matrix}x_1\\x_2\\x_3\\\end{matrix}\right]=\left[\begin{matrix}3\mathrm{.000}\\-13.00\\1\mathrm{.000}\\\end{matrix}\right]\)
(3). For
\[[A]= \begin{bmatrix} 10 & - 7 & 0 \\ - 3 & 2.099 & 6 \\ 5 & - 1 & 5 \\ \end{bmatrix}\]
Find the determinant of \([A]\) using the forward elimination part of Naive Gauss elimination method.
Answer: \(-150.05\)
(4). At the end of the forward elimination part using the Naive Gauss elimination method on the coefficient matrix
\[[A]= \begin{bmatrix} 25 & c & 1 \\ 64 & a & 1 \\ 144 & b & 1 \\ \end{bmatrix}\]
\([A]\) reduces to
\[[B]= \begin{bmatrix} 25 & 5 & 1 \\ 0 & - 4.8 & - 1.56 \\ 0 & 0 & 0.7 \\ \end{bmatrix}\]
What is the determinant of \([A]\)?
Answer: \(-84\)
(5). Use Gaussian elimination with partial pivoting method to solve
\[{4x_{1} + x_{2} - x_{3} = - 2}\] \[{5x_{1} + x_{2} + 2x_{3} = 4}\] \[{6x_{1} + x_{2} + x_{3} = 6}\]
Answer: \(\left[\begin{matrix}x_1\\x_2\\x_3\\\end{matrix}\right]=\left[\begin{matrix}3\\-13\\1\\\end{matrix}\right]\)
(6). Assume that you are using a computer with four significant digits with chopping, use Gaussian elimination with partial pivoting method to solve
\[{4x_{1} + x_{2} - x_{3} = - 2}\] \[{5x_{1} + x_{2} + 2x_{3} = 4}\] \[{6x_{1} + x_{2} + x_{3} = 6}\]
Answer: \(\left[\begin{matrix}x_1\\x_2\\x_3\\\end{matrix}\right]=\left[\begin{matrix}2.998\\-12.99\\1.000\\\end{matrix}\right]\)