% FILE antonNM6.tex


\subsection{The Gauss-Seidel and Jacobi Iterative Methods}

These methods are used for very large but very sparse matrices.
We have no worthwhile comments concerning Maple and the material
in Anton on these methods.
We next turn to important items related to $LU$-factorisation,
or more-precisely $PLU$-factorisation.

\subsection{Partial Pivotting}
Roundoff error is the error associated with the storage or arithmetic of
floating-point numbers on computers with a finite precision.
An example is given in the following.

\begin{maple}
# A simpler example than AR6 Section 9.4 Example 3, p458-460
# We set the value of Digits to 5, and try to solve the equations
> eqn1:= 10^(-8)*x+y=1;                                   eqn2:= x+y=2;
                         eqn1 := 1/100000000 x + y = 1

                               eqn2 := x + y = 2

> vars:= {x,y}:            Digits:= 5:            fsolve( {eqn1,eqn2},vars );
                            {y = 1.0000, x = 1.0000}

# If we pivot on the first coefficient of  eqn2,  we get
> eqn:= evalf(eqn1-eqn2/10^8);                      fsolve( {eqn,eqn2},vars );
                           eqn := 1.00000 y = 1.00000

                            {y = 1.0000, x = 1.0000}

# which is the correct answer to five significant figures.
#
# However, if we try to pivot on the first coefficient of  eqn1,  we get
> eqn:= evalf(eqn2-10^8*eqn1);                     fsolve( {eqn1,eqn},vars );
                                         9                9
                     eqn :=  - .100000*10  y = -.100000*10

                              {x = 0, y = 1.0000}

# which is not the correct answer.
# Note that Maple gives the correct answer (in both cases) with the value
> Digits:= 10:
\end{maple}


\subsubsection*{Overwriting Matrices}
Situations often arise in which we do not need to store all the entries of a
matrix. One example is in the $LU$-decomposition of a matrix 
(see page~\pageref{lufac} of these notes). When the matrix
$(L,U)$ is stored, the zeroes in $L$ may be over-written by the entries of $U$.

In order to save space in some circumstances, Maple allows an argument
{\tt sparse} when defining a matrix using the function {\tt array}
(but {\em not} when using the function {\tt matrix}). This causes only those
entries actually assigned to be stored.
  
Another example of this economy of space is given in symmetric matrices.
In this case, only just over half of
the entries need to be stored, and so the Maple command (with $n$ assigned to a
positive integer)
\begin{verbatim}
A:= array(symmetric,1..n,1..n);
\end{verbatim} 
stores the $n(n+1)/2$ entries on or above the diagonal, together with the rule
\quad {\tt A[j,i]:= A[i,j]}.

\subsection*{Ill-conditioned Systems}
We have already seen problems of round-off which can be
dealt with using partial pivotting. However there are some systems of
linear equations where round-off errors cannot be avoided
-- ill-conditioned systems. 
  
The {\it condition number} measures how ill-conditioned a system is.
The Maple command to calculate matrix condition numbers is {\tt cond}.

%For further details on this, see the separate notes on
%Maple and numerical linear algebra.
\vfill
\eject
\endinput
