Gaussian Elimination

Example m-file: Show steps in Gauss elimination and back substitution. No pivoting. (http://siber.cankaya.edu.tr/ozdogan/NumericalComputations/mfiles/chapter2/GEshow.m GEshow.m)

\includegraphics[scale=1.5]{figures/2-2}

  1. The augmented coefficient matrix is

    \begin{displaymath}
\left[
\begin{array}{rrrrr}
0 & 2 & 0 & 1 &0 \\
2 & 2 & 3...
...& -3 & 0 & 1 &-7 \\
6 & 1 &-6 &-5 &6 \\
\end{array} \right]
\end{displaymath}

  2. We cannot permit a zero in the $a_{11}$ position because that element is the pivot in reducing the first column.
  3. We could interchange the first row with any of the other rows to avoid a zero divisor, but interchanging the first and fourth rows is our best choice. This gives


    \begin{displaymath}
\left[
\begin{array}{rrrrr}
6 & 1 &-6 &-5 &6 \\
2 & 2 & 3...
...& -3 & 0 & 1 &-7 \\
0 & 2 & 0 & 1 &0 \\
\end{array} \right]
\end{displaymath}


    \begin{displaymath}
\left[
\begin{array}{rrrrr}
6 & 1 &-6 &-5 &6 \\
0 &1.6667...
... & 4 &4.3333&-11 \\
0 & 2 & 0 & 1 &0 \\
\end{array} \right]
\end{displaymath}

4
We again interchange before reducing the second column, not because we have a zero divisor, but because we want to preserve accuracy. Interchanging the second and third rows puts the element of largest magnitude on the diagonal.

\begin{displaymath}
\left[
\begin{array}{rrrrr}
6 & 1 &-6 &-5 &6 \\
0 &-3.666...
...67& 5 &3.6667&-4 \\
0 & 2 & 0 & 1 &0 \\
\end{array} \right]
\end{displaymath}

5
Now we reduce in the second column

\begin{displaymath}
\left[
\begin{array}{rrrrr}
6 & 1 &-6 &-5 &6 \\
0 &-3.666...
...1\\
0 & 0 & 2.1818 & 3.3636 &-5.9999 \\
\end{array} \right]
\end{displaymath}

6
No interchange is indicated in the third column. Reducing, we get

\begin{displaymath}
\left[
\begin{array}{rrrrr}
6 & 1 &-6 &-5 &6 \\
0 &-3.666...
...9.0001\\
0 & 0 & 0 & 1.5600 &-3.1199 \\
\end{array} \right]
\end{displaymath}

7
Back-substitution gives

\begin{displaymath}
x_1=-0.50000,
x_2=1.0000,
x_3=0.33325,
x_4=-1.9999.
\end{displaymath}

Example m-file: LU factorization without pivoting. (http://siber.cankaya.edu.tr/ozdogan/NumericalComputations/mfiles/chapter2/luNopiv.m luNopiv.m)
Example m-file: LU factorization with partial pivoting. (http://siber.cankaya.edu.tr/ozdogan/NumericalComputations/mfiles/chapter2/luPiv.m luPiv.m)

\includegraphics[scale=1.5]{figures/2-4}

Cem Ozdogan 2010-11-03