\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 3}
\date{due September 29, 2003}
\maketitle

\noindent
Recall that if $\|\x\|_p$ denotes the $p$-norm of a vector
$\x\in\R^n$, then the associated norm for a matrix $A \in \R^{n\times
n}$ is defined
\[
  \| A \|_p = \max_{\x \neq 0} \frac{\|A \x\|_p}{\|\x\|_p} \,.
\]

\begin{enumerate}

\item (From SM.) Suppose that for a matrix $A \in \R^{n\times n}$,
\begin{equation}
  \label{e.2}
  \sum_{i=1}^n |a_{ij}| \leq C 
\end{equation}
for $j=1,\dots,n$.
\begin{enumerate}
\item Show that, for any vector $\x \in \R^n$,
\begin{equation}
  \label{e.1}
  \| A\x \|_1 \leq C \, \|\x\|_1 \,.
\end{equation}
\item Find $C$ subject to \eqref{e.2} and a nonzero vector $\x$ so
that \eqref{e.1} holds with equality.

\item Conclude that
\[
  \| A \|_1 = \max_{j=1,\dots,n} \sum_{i=1}^n |a_{ij}| \,.
\]
\end{enumerate}

\item
\begin{enumerate}
\item Show that, for $A \in \R^{n\times n}$,
\[
  \| A \|_2 = \sqrt{\lambda_{\max}} \,,
\]
where $\lambda_{\max}$ is the largest eigenvalue of $A^TA$.

Hint: Recall that for any $\x \in \R^n$, you can write
$\x^T\x=\|\x\|_2$.  The eigenvalues of the symmetric matrix $A^TA$ are
real and nonnegative (why?), and its eigenvectors can be chosen to
form an orthonormal basis.

\item Conclude that the condition number of an orthogonal matrix is
$1$.
\end{enumerate}

\item (From SM.) Assume that a nonsingular matrix $A \in \R^{n\times
n}$ has an $LU$ factorization.  Show that $A$ can also be factored in
the form $A=LDR$ where $L$ is unit lower triangular, $D$ is diagonal,
and $R$ is unit upper triangular.  Use this result to express the $LU$
factoriztion of $A^T$ in terms of the $LU$ factorization of $A$.

\item The $n \times n$ Vandermonde Matrix is defined as
\[
 V =
 \begin{pmatrix}
   1 & 2 & 4 & 8 & \cdots & 2^{n-1} \\
   1 & 3 & 9 & 27 & \cdots & 3^{n-1} \\
   1 & 4 & 16 & 64 & \cdots & 4^{n-1} \\
   \vdots & \vdots & \vdots & \vdots & & \vdots \\
   1 & n+1 & (n+1)^2 & (n+1)^3 & \cdots & (n+1)^{n-1}
 \end{pmatrix}.
\]
Let $\b\in\R^n$ be the vector containing the sum of each row of
$V$.  Find a formula for the components of $\b$.  What is the
solution of the system of linear equations $V\x=\b$?

\item \textbf{Project:} Write an \textsf{Octave} function
\texttt{vandermonde(n)} that generates the $n\times n$ Vandermonde
Matrix.  Compute its condition number with respect to the $2$-norm for
different values of $n$.  (You may use the built-in \textsf{Octave}
function \texttt{cond}.)

\item \textbf{Project:} Write an \textsf{Octave} function that computes
the $LU$ decomposition of a matrix without pivoting.  Test your code
by solving $V\x=\b$ from Question~4 for several values of $n$.

\end{enumerate}
\end{document}
