\documentclass[12pt]{article}
\usepackage{fullpage,amsmath,amsfonts}

\newcommand{\x}{\boldsymbol{x}}
\renewcommand{\v}{\boldsymbol{v}}
\newcommand{\w}{\boldsymbol{w}}
\renewcommand{\a}{\boldsymbol{a}}
\renewcommand{\b}{\boldsymbol{b}}
\renewcommand{\c}{\boldsymbol{c}}
\newcommand{\e}{\boldsymbol{e}}
\renewcommand{\Re}{\operatorname{Re}}
\renewcommand{\Im}{\operatorname{Im}}
\newcommand{\Range}{\operatorname{Range}}
\newcommand{\Ker}{\operatorname{Ker}}
\newcommand{\Span}{\operatorname{Span}}
\renewcommand{\dim}{\operatorname{dim}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\C}{\mathbb{C}}


\begin{document}

\title{Numerical Methods I}
\author{Problem Set 4}
\date{due in class, October 8, 2003}
\maketitle


\begin{enumerate}

\item Let $\rho(A)$ denote the spectral radius of a matrix $A$, i.e.
\begin{equation*}
  \rho(A) = \max_{i=1,\dots,m} |\lambda_i| \,,
\end{equation*}
where $\lambda_1, \dots, \lambda_m$ are the eigenvalues of $A$.
\begin{enumerate}
\item Show that $\rho(A) \leq \|A\|$ for any matrix norm of $A$.
\item Give an example of a nonzero matrix for which $\rho(A)=0$.
\end{enumerate}

\item Consider the Jacobi method for solving the equation $A\x=\b$,
where
\begin{equation*}
  A = 
  \begin{pmatrix}
  1 & \varepsilon \\ \varepsilon & 1
  \end{pmatrix}
\end{equation*}
For which values of $\varepsilon$ does the method converge?

\item \textbf{Project:} Modify your program for the $LU$
decomposition to include pivoting.  I.e., let your program find $P$,
$L$, and $R$ so that for a given nonsingular matrix $A \in \R^{n\times
n}$, $PA=LU$.  Use your program to solve last week's Vandermonde test
problem.  Does pivoting help?

\item \textbf{Project:} Use $LU$ decomposition with and without
pivoting to solve randomly generated linear equations.  Print the
$2$-norm of the residual and the condition number of the matrix for
many test problems.  Describe the effect of pivoting.

\item \textbf{Project:} Write an \textsf{Octave} code to perform a
$QR$ decomposition of an $n\times m$ matrix.  Then compute the least
squares solution to $A\x=\b$ with
\begin{equation*}
  A = 
  \begin{pmatrix}
  0 & 1 & 1 \\ 1 & 0 & 1 \\ 0 & 0 & 1 \\ 0 & 1 & 1
  \end{pmatrix} \,, \qquad
  \b =
  \begin{pmatrix}
  4 \\ 3 \\ 2 \\ 1
  \end{pmatrix}\,.
\end{equation*}

\end{enumerate}
\end{document}
