\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 -- Problem Sets 3 and 4}
\author{Fall Semester 2005}
\date{Due September 30 (Theory), October 7 (Projects)}
\maketitle

\noindent

Background reading: S\"uli and Mayers, Chapter 2; Quarteroni and
Saleri, Chapter 5.  Please submit the theoretical homework directly to
Stanislav Harizanov (e.g.\ clearly addressed to him via the mailbox in
front of Research I, room 40.)


\begin{enumerate}

\item The following root finding method is a modification of the
bisection method.  It is called \emph{regula falsi}.
\begin{equation*}
  x_{k+1} = x_0 - \frac{x_k-x_0}{f(x_k)-f(x_0)} \, f(x_0) \,.
  \tag{*}
\end{equation*}
\begin{enumerate}
\item Show that the \emph{regula falsi} is consistent.

(Recall that a method is consistent if every fixed point $\xi$ of this
iteration solves the equation $f(\xi)=0$.)

\item Give an argument using Taylor expansion that the \emph{regula
falsi} is convergent with order $1$.

\item The \emph{regula falsi} is applied in the following way.  Choose
two starting values $x_0$ and $x_1$ so that $f(x_0)\cdot f(x_1)<0$.
Compute the sequence of $x_k$ via (*).  If $f(x_0)\cdot f(x_{k+1})>0$,
re-initialize by setting $x_0:=x_k$.

Show that if $f$ is continuous, the sequence $x_k$ will always
converge to a root of $f$.

Hint: Notice that $x_{k+1}$ is the zero of the line joining the points
$(x_0,f(x_0))$ and $(x_k,f(x_k))$.  Then note that the sequence of
intervals that bracket the root has monotonic bounds.

\end{enumerate}

\item (From SM.) 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} \,.
\]

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 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 (possibly complex)
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 (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$.

\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}
