\magnification=\magstep1
\centerline{Mathematics 172 -- Numerical Analysis 2}
\centerline{Lab/Problem Set 3, Studying Gaussian Elimination with Maple}
\centerline{February 25, 1999}
\bigskip
\noindent
{\bf The Goals for Today's Session}
\bigskip
Today, we will use Maple to perform the Gaussian
elimination procedure we discussed
last time in class.  The main goal is to get a feeling for how this
procedure can behave when {\it floating-point arithmetic\/} is employed.
\bigskip
\noindent
{\bf The {\tt linalg} Package}
\bigskip
Most of Maple's built-in routines for linear algebra operations are
contained in an external package called {\tt linalg}.  As with the 
functions in other
Maple packages, you will need to load this package before you 
can use them.  This is done by issuing a 
\bigskip
\centerline{\tt with(linalg);}
\bigskip 
command.   Do this now.
This command should generate a list of about 100 different procedure
names.  Take a look at them and see if you can guess what they do.
As always, you can also use the Maple {\it on-line help} to get info about the 
correct format of the commands and exactly what they do.
\bigskip
\noindent
{\bf Entering Matrices}
\bigskip
In Maple, matrices are represented essentially as lists of row 
vectors (or lists of lists).  For instance, to type in a $3 \times 3$
matrix
$$  A = \pmatrix{3&6&9\cr
                 -1&0&2\cr
                 6&7&21\cr}$$
you would use a format like this:
\bigskip
\centerline{\tt A := array([[3,6,9],[-1,0,2],[6,7,21]]);}
\bigskip
Try it and note the nicely formatted output!
\bigskip
\noindent
{\bf Row Operations\/}  
\bigskip
The {\tt linalg\/} functions that perform row operations on a matrix
are called:
\smallskip
\item{1)}  {\tt mulrow} -- multiplies a row of a matrix by 
an expression (the expression can be a constant, or an expression 
involving only constants, of course!).
\item{2)}  {\tt addrow} -- adds a multiple of a row to another row.
\item{3)}  {\tt swaprow} -- interchanges two rows.
\smallskip
Look at the Maple on-line help files for each of these.  There shouldn't
be any surprises; the {\tt addrow} format is slightly tricky to remember
though -- you may want to write down the format of the command so
you will not have to go back and look at it repeatedly!
\bigskip
Experiment with a few operations on your matrix $A$ from above to get
the hang of it.
\bigskip
\noindent
{\bf Bringing Floating-Point Arithmetic into the Picture}
\bigskip
As we have seen before, there is a built-in Maple variable called
{\tt Digits}.  Its default value is 10, but you can set it to a 
smaller or larger value if you like.  To {\it illustrate, and exaggerate\/}
some round-off effects, set 
\bigskip
\centerline{\tt Digits := 4;}
\bigskip
\noindent
(Maple will now act like a 4-digit {\it rounding\/} calculator for the 
arithmetic operations.) 
\bigskip
\noindent
{\bf Lab Problems}
\bigskip
\item{A)}  Enter the augmented matrix for this system of equations:
$$\matrix{-.002x_1 &+ &4x_2 &+ &4x_3 &= 7.998\cr
          -2x_1 &+ &2.906x_2 &- &5.387x_3  &= -4.481\cr
           3x_1 &- &4.031x_2 &- &3.112x_3 &= -4.143\cr}\leqno(1)$$
and perform row operations on it according to the Gaussian Elimination
method.   One suggestion: If you call your original augmented matrix
{\tt augmat}, the the command 
\medskip
\centerline{\tt augmat := addrow(augmat,1,2,-2);}
\medskip
\item{} would add $-2$ times row 1 to row 2, {\it then store the results
back into the variable {\tt augmat}, so you can continue with further
row operations on that matrix.}
What is your computed solution?  Note: The exact solution 
is $(x_1, x_2, x_3) = (1,1,1)$. (Check it if you don't 
believe me!)   What happened??  What happens if you 
repeat the calculation after setting {\tt Digits} back 
to the default value of 10?  Would the ``full''
Gauss-Jordan elimination procedure
be {\it better\/}, or {\it potentially even worse\/} than Gaussian 
Elimination on an example like this using {\tt Digits} $= 4$?  (You 
can experiment a bit, or think about it without calculation.)

\item{B)} (Some Prophylaxis?)
As a counter-measure, most good numerical software uses a {\it selection
scheme\/} of some sort for the pivot element to use when there is a choice.
A good selection scheme will minimize the effects of round-off error
in the computations of the Gaussian Elimination.
The most basic selection scheme is the following:
\bigskip
\itemitem{} ``Maximal Column Pivoting:''  In selecting the pivot element
in each column, do not use the first non-zero column element encountered.
Instead, pick the element in the column (on or below the diagonal) that
is {\it largest in absolute value\/}.  
\bigskip
\item{1)} Redo the Gauss elimination for (1) above 
using maximal column pivoting, still using 4-digit rounding arithmetic.
How do your results compare with the previous results?
\item{2)} {\it Why\/} is maximal column pivoting better?
\bigskip
\item{C)}  For the following system:
$$\matrix{
&1.19 x_1  &+ &2.11 x_2 &- &100 x_3 &+ x_4 = 1.12\cr
&14.2 x_1  &- &0.122 x_2 &- &12.2 x_3 &- x_4 = 3.44\cr
&          &  &100 x_2 &- &99.9x_3 &+ x_4 = 2.15\cr
&15.3 x_1  &+ &0.11 x_2 &- &13.1 x_3 &- x_4 = 4.16\cr}$$
\itemitem{1)}  Solve the system by Gaussian Elimination (without
pivoting) using 3-digit
rounding arithmetic.
\itemitem{2)}  Repeat part 1 using Maximal Column Pivoting and
3-digit rounding arithmetic.
\itemitem{3)}  Now repeat part 1 using 10-digit rounding arithmetic.
with and without pivoting.  
\itemitem{4)}  Discuss your results.
\bigskip
\item{D)}  (For after class on Tuesday, March 2)  Do 2 a,c; 3 a,c; 5c
from section 6.5 of Burden and Faires (page 402-3).

\bigskip
\noindent
{\bf Assignment}
\bigskip
Individual write-ups due Tuesday, March 16 (after Spring Break). 
\bigskip
\noindent
{\bf For Future Reference -- Maple's Linear Equation-Solvers}
\bigskip
In the future, to solve systems of linear equations, we will not 
need to do row-operations explicitly!  Instead, we will use Maple's
built-in commands:
\smallskip
\item{1)}  {\tt gausselim}:  Does Gaussian elimination with 
maximal column pivoting.  
\item{2)} {\tt backsub}:  Does back-substitution on the eliminated
matrix.
\item{3)} {\tt linsolve}: basically, this is a combination of 1 and 2.
\item{4)}  {\tt gaussjord}:  Does Gauss-Jordan reduction with pivoting.

\bye
