Gaussian Elimination

Therefore, adequate methods should be used in linear equation system solutions such as without calculating determinant or inverse matrix.

Two of the most useful methods are Gaussian elimination and L-U decomposition.

Elimination Methods. While it may be satisfactory for hand computations with small systems, it is inadequate for a large system (numbers may getting bigger!).

The method that is called Gaussian elimination avoids this by subtracting $a_{i1}/a_{11}$ times the first equation from the $i^{th}$ equation to make the transformed numbers in the first column equal to zero.

We do similarly for the rest of the columns.

Observe that zeros may be created in the diagonal positions even if they are not present in the original matrix of coefficients.

A useful strategy to avoid (if possible) such zero divisors in the diagonal positions is to rearrange the equations so as to put the coefficient of largest magnitude on the diagonal at each step.

This is called pivoting.

Generalization. Let the system of equations with N unknowns be given as:

$\begin{indisplay} \begin{array}{c} a_{11}x_1+a_{12}x_2+ \ldots +a_{1n}x_n =b_1\... ...s\\ a_{n1}x_1+a_{n2}x_2+ \ldots +a_{nn}x_n =b_n\\ \end{array}\end{indisplay}$

First Stage. Let $a_{11} \ne 0$ (If not, pivoting), then multiply the $1^{st}$ equation by ( $a_{2}/a_{11})$ ) and subtract it from the $2^{nd}$ equation.
Next, again multiply the $1^{st}$ equation by ( $a_{31}/a_{11}$ ) and subtract from the $3^{rd}$ equation.
Repeat this procedure up to the $n^{th}$ equation.

As a result, the variable $x_1$

is eliminated in the other equations and the new system of equations becomes:

$\displaystyle a_{11}x_1+a_{12}x_2+ \ldots +a_{1n}x_n$	$\displaystyle =$	$\displaystyle b_1$
$\displaystyle \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$	$\displaystyle =$	$\displaystyle b_2-\frac{a_{21}}{a_{11}}b_{1}$
$\displaystyle \left( a_{32}-\frac{a_{31}}{a_{11}}a_{13}\right)x_2+ \ldots +\left(a_{3n}-\frac{a_{31}}{a_{11}}a_{1n}\right)x_n$	$\displaystyle =$	$\displaystyle b_3-\frac{a_{31}}{a_{11}}b_{1}$
$\displaystyle \vdots$
$\displaystyle \left( a_{n2}-\frac{a_{n1}}{a_{11}}a_{1n}\right)x_2+ \ldots +\left(a_{nn}-\frac{a_{nn}}{a_{11}}a_{1n}\right)x_n$	$\displaystyle =$	$\displaystyle b_n-\frac{a_{n1}}{a_{11}}b_{1}$

Notice that in this new system of equations at first stage, the coefficient of the $j^{th}$ term in the $i^{th}$ row and the constant $b_i$

are as follows:

$\displaystyle a_{ij}^{(1)}=a_{ij}-\frac{a_{i1}}{a_{11}}a_{1j}$		$\displaystyle (i,j=2,\ldots,n)$
$\displaystyle b_{i}^{(1)}=b_{i}-\frac{a_{i1}}{a_{11}}b_{i}$		$\displaystyle (i=2,\ldots,n)$

Next, let $a_{22}^{(1)} \ne 0$ (If not, pivoting) in this new system of equations, then multiply the $2^{nd}$ equation by ( $a_{32}^{(1)}/a_{22}^{(1)})$ ) and subtract it from the $3^{rd}$ equation.

Repeat this procedure up to equation $n$

times to obtain the upper-triangular form:

$\displaystyle a_{11}x_1+a_{12}x_2+a_{13}x_3+ \ldots +a_{1n}x_n$	$\displaystyle =$	$\displaystyle b_1$
$\displaystyle a_{22}^{(1)}x_2+a_{23}^{(1)}x_3+ \ldots +a_{2n}^{(1)}x_n$	$\displaystyle =$	$\displaystyle b_{2}^{(1)}$
$\displaystyle a_{33}^{(2)}x_3+ \ldots +a_{3n}^{(2)}x_n$	$\displaystyle =$	$\displaystyle b_{3}^{(2)}$
$\displaystyle \vdots$
$\displaystyle a_{nn}^{(n-1)}x_n$	$\displaystyle =$	$\displaystyle b_{n}^{(n-1)}$

As seen, the number of unknowns decreases by one in the $2^{nd}$ and other equations as $1^{st}$ stage, decreases once again in the $3^{rd}$ and other equations as $2^{nd}$ stage and so on. In $(N-1)^{th}$ stage, a single unknown is obtained.

Then, the $j^{th}$ coefficient of the $i^{th}$ equation as $k^{th}$ stage is as follows:

$\displaystyle \boxed{a_{ij}^{(k)}=a_{ij}^{(k-1)}-\frac{a_{ik}^{(k-1)}a_{kj}^{(k-1)}}{a_{kk}^{(k-1)}}}~~~~ (i,j=1,\ldots,n)$

(6.1)

$\displaystyle \boxed{b_{i}^{(k)}=b_{i}^{(k-1)}-\frac{a_{ik}^{(k-1)}b_{k}^{(k-1)}}{a_{kk}^{(k-1)}}}~~~~~~~ (i=1,\ldots,n)$

(6.2)

After reaching to the upper-triangular form, the solution is almost readily obtained.

From the last equation in the upper-triangular form:

$\displaystyle x_n=b_n^{(n-1)}/a_{nn}^{(n-1)}$

All other unknowns are obtained consequently by backward-substitution. The general expression would be:

$\displaystyle {\small\boxed{x_k=\frac{1}{a_{kk}^{(k-1)}}\left[ b_{k}^{(k-1)} - \sum_{j=k+1}^{n} a_{kj}^{(k-1)} x_j\right]}~~(k=n-1,\ldots,1)}$

(6.3)

Repeat the example of the previous section,

$\begin{indisplay} \left[ \begin{array}{rrrr} 4 & -2 & 1 &15 \\ -3 & -1 & 4 &8 \\ 1 & -1 & 3 &13 \\ \end{array} \right], \end{indisplay}$

$\begin{indisplay} \begin{array}{r} \\ R_2-(-3/4)R_1 \rightarrow \\ R_3-(1/4)R_1 \rightarrow \\ \end{array}\end{indisplay}$

$\begin{indisplay} \left[ \begin{array}{rrrr} 4 & -2 & 1 &15 \\ 0 & -2.5 & 4.75 &19.25 \\ 0 & -0.5 & 2.75 & 9.25 \\ \end{array} \right], \end{indisplay}$

$\begin{indisplay} \begin{array}{r} \\ \\ R_3-(-0.5/-2.5)R_2 \rightarrow \\ \end{array}\end{indisplay}$

$\begin{indisplay} \left[ \begin{array}{rrrr} 4 & -2 & 1 &15 \\ 0 & -2.5 & 4.75 & 19.25 \\ 0 & 0 & 1.8 & 5.40 \\ \end{array} \right] \end{indisplay}$

The method we have just illustrated is called Gaussian elimination.

In this example, no pivoting was required to make the largest coefficients be on the diagonal.

Back-substitution, gives us $x_3= 3,~x_2=-2,~x_1=2$

Example py-file:

without pivoting

myGEshow.py

**Figure 6.1:** Steps in Gaussian elimination and back substitution without pivoting.

if we had stored the ratio of coefficients in place of zero (we show these in parentheses), our final form would have been

$\begin{indisplay} \left[ \begin{array}{rrrr} 4 & -2 & 1 &15 \\ (-0.75) & -2.5... ... 19.25 \\ (0.25) & (0.20) & 1.8 & 5.40 \\ \end{array} \right] \end{indisplay}$