         %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
         % Information sheet for the Matlab lab - Maths 6111 %
         %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentclass[10pt]{article} 
\input ma_no_html_header

\usepackage{color}
\usepackage{hyperref}
\hypersetup{breaklinks=true,colorlinks=true}
%\input ma_header
\setlength{\parindent}{0pt}
\pagestyle{myheadings}
% \markright{
% \protect {\protect \epsfxsize=0.2 true cm \protect \epsffile {dolph.line.eps}}
% \it Maths 3018/6111 - Numerical methods \hfill}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{document}

\thispagestyle{empty}
\begin{center}
\textbf{\Large Maths 3018/6111 - Numerical Methods \\*[8mm]
Worksheet 1 - Solutions}\\*[.8cm]
\end{center}

\section*{Theory}

\begin{enumerate}
\item Write down the $1$, $2$ and $\infty$ vector norms of
  \begin{equation*}
    {\bf v}_1 =
    \begin{pmatrix}
      1 \\ 3 \\ -1
    \end{pmatrix}, \quad
    {\bf v}_2 =
    \begin{pmatrix}
      1 \\ -2
    \end{pmatrix}, \quad
    {\bf v}_3 =
    \begin{pmatrix}
      1 \\ 6 \\ -3 \\ 1
    \end{pmatrix}.
  \end{equation*}
  %
  \begin{center}
    \rule{0.9\textwidth}{.1pt}
  \end{center}  
  % 
  We know that the 1-norm is the sum of the absolute values, so
  \begin{align*}
    |{\bf v}_1|_1 & = 1 + 3 + 1 = 5, \\
    |{\bf v}_2|_1 & = 1 + 2  = 3, \\
    |{\bf v}_3|_1 & = 1 + 6 + 3 + 1 = 11.
  \end{align*}
  The 2-norm is the square root of the sum of the squares, so
  \begin{align*}
    |{\bf v}_1|_2 & = \sqrt{1^2 + 3^2 + 1^2} = \sqrt{11} \approx 3.3166, \\
    |{\bf v}_2|_2 & = \sqrt{1^2 + 2^2}  = \sqrt{5} \approx 2.2361, \\
    |{\bf v}_3|_2 & = \sqrt{1^2 + 6^2 + 3^2 + 1^2} = \sqrt{47} \approx
    6.8557.
  \end{align*}
  The infinity norm is the maximum absolute value, so
  \begin{align*}
    |{\bf v}_1|_{\infty} & = 3 \\
    |{\bf v}_2|_{\infty} & = 2 \\
    |{\bf v}_3|_{\infty} & = 6.
  \end{align*}
  %
  \begin{center}
    \rule{0.9\textwidth}{.1pt}
  \end{center}  
  % 
\item Find the $1$ and $\infty$ matrix norms of
  \begin{equation*}
    A_1 =
    \begin{pmatrix}
      1 & 2 \\ 3 & 4
    \end{pmatrix}, \quad
    A_2 =
    \begin{pmatrix}
      -3 & 2 \\ 3 & 6
    \end{pmatrix}
  \end{equation*}
  %
  \begin{center}
    \rule{0.9\textwidth}{.1pt}
  \end{center}  
  % 
  The 1-norm of a matrix is the maximum of the 1-norms of the column
  vectors. For $A_1$ the 1-norms are 4 and 6 respectively. For $A_2$
  they are 6 and 8 respectively. So we have
  \begin{align*}
    \|A_1\|_1 & = 6, \\
    \|A_2\|_2 & = 8.
  \end{align*}

  The infinity norm of a matrix is the maximum of the 1-norms of the row
  vectors. For $A_1$ the 1-norms are 3 and 7 respectively. For $A_2$
  they are 5 and 9 respectively. So we have
  \begin{align*}
    \|A_1\|_{\infty} & = 7, \\
    \|A_2\|_{\infty} & = 9.
  \end{align*}
  %
  \begin{center}
    \rule{0.9\textwidth}{.1pt}
  \end{center}  
  % 
\item Find the condition numbers of the above matrices. What does this
  suggest about the numerical behaviour of an algorithm that used such
  a matrix?
  %
  \begin{center}
    \rule{0.9\textwidth}{.1pt}
  \end{center}  
  % 
  The inverse matrices are
  \begin{align*}
    A_1^{-1} & =
      -\frac{1}{2}
    \begin{pmatrix}
      4 & -2 \\ -3 & 1
    \end{pmatrix}, \\
    A_2^{-1} & =
      -\frac{1}{24}
    \begin{pmatrix}
      6 & -2 \\ -3 & -3
    \end{pmatrix}.
  \end{align*}
  It follows that the matrix norms of the inverse matrices are
  \begin{align*}
    \|A_1^{-1}\|_1 & = \frac{7}{2}, & \|A_2^{-1}\|_1 & = \frac{3}{8}, \\
    \|A_1^{-1}\|_{\infty} & = 3, & \|A_2^{-1}\|_{\infty} & = \frac{1}{3}.
  \end{align*}
  Therefore the condition numbers with respect to the 1-norm are
  \begin{align*}
    K(A_1) & = \|A_1\|_1 \|A_1^{-1}\|_1 \\
           & = 21, \\
    K(A_2) & = \|A_2\|_1 \|A_2^{-1}\|_1 \\
           & = 3,
  \end{align*}
  and the condition numbers with respect to the infinity norm are
  \begin{align*}
    K(A_1) & = \|A_1\|_{\infty} \|A_1^{-1}\|_{\infty} \\
           & = 21, \\
    K(A_2) & = \|A_2\|_{\infty} \|A_2^{-1}\|_{\infty} \\
           & = 3.
  \end{align*}
  In this case they are identical.

  This suggests that if the numerical algorithm used the matrix $A_1$
  then the errors intrinsic in the algorithm would increase by a
  factor of order 10, whilst using $A_2$ would increase them by a
  factor order unity. That is, we expect $A_2$ to be better behaved
  than $A_1$ (this is a rather wooly way of putting it).
  %
  \begin{center}
    \rule{0.9\textwidth}{.1pt}
  \end{center}  
  % 
\item Explain the difference between direct and indirect methods for
  solving linear systems. Give an example of when the latter may be
  more useful.
  %
  \begin{center}
    \rule{0.9\textwidth}{.1pt}
  \end{center}  
  % 
  {\it Standard exam question; see, e.g., 07/08}.

  \textit{Direct methods} consist of a finite list of transformations
  of the original matrix of the coefficients that reduce the linear
  systems to one that is easily solved.  \textit{Indirect or iterative
    methods}, consist of algorithms that specify a series of steps,
  possibly infinite, that lead closer and closer to the solution;
  there may not be a guarantee that they ever exactly reach it.  This
  may not seem a very desirable feature until we remember that we
  cannot in any case perfectly represent an exact solution: most
  iterative methods provide us with a highly accurate solution in
  relatively few iterations.

  Large, sparse matrices are ideally solved using iterative methods.
  %
  \begin{center}
    \rule{0.9\textwidth}{.1pt}
  \end{center}  
  % 
\end{enumerate}

\end{document}

