\documentclass[12 pt]{article}
\usepackage{verbatim}
\usepackage{amsfonts}
\usepackage{graphics}
\usepackage{amsmath}
\usepackage{url}
\hoffset=-0.725in
\voffset=-0.825in
\setlength{\textheight}{9.0in}
\setlength{\textwidth}{6.5in}
\renewcommand{\baselinestretch}{1.00}
\pagestyle{empty}

% Definitions
\def\SS{\scriptsize}
\def\TM{\!\!$^{\mbox{\texttt{\SS TM}}}$~}
\def\TMnosp{\!\!\!$^{\mbox{\texttt{\SS TM}}}$}

\begin{document}
\begin{center}
{\bf \hfill Seema Nanda\\}
{\bf Numerical Analysis \hfill Assignment 3 \hfill Feb 7, 2011
 in class}
\end{center}
\hrulefill
\begin{center}
Show all your work clearly. Please follow the instructions for assignments and homework as given in the
course web page. Late homework will not be accepted. You may discuss problems with anyone but the work in the end should be your own. You MUST give credit to whoever helped you in your homework.
\end{center}
\hrulefill

% Homework starts here.



\begin{enumerate}
\item{\bf Root finding}
Write code using Horner's method to find $p(x_0)$ and $p'(x_0)$ for any $x_0$ that is input for the given polynomial below. 
Combine with your existing code for Newton's method to find the roots of the polynomial. Recall that if your first guess is real you get only real roots.
\begin{equation}
 p(z) = z^3 - 2z^2 + z - 2
\end{equation}
\item  {\bf Norms}
\begin{enumerate}
\item In the case of square matrices, a matrix norm subordinate to a vector norm has additional property 
besides the 3 properties for a vector norm, namely:
$ \|AB\| \le \|A\| \|B \|$, for $n \times n$ matrices $A$ and $B$. \\
Define $\|A\| =\sum_{i=1}^n \sum_{j=1}^n |a_{ij}|$. Show that this is a matrix norm (that is a norm on the linear space 
of all $n \times n$ matrices). Show that it is not subordinate to any vector norm. Does it satisfy the above property?
%(Kincaid/Cheney)


\item Not all vector norms will become matrix norms in $R^{n \times n}$. True? Support your answer.

\item For any real number $p \ge 1$ the formula 
$\|x\|_p = (\sum_{i=1}^{n} \|x_i\|^p) ^{\frac{1}{p}}$ 
defines a norm. Prove that for each $x \in R^n$  $lim_{p\to \infty } \|x\|_p = \|x\|_{\infty}$.

\item Which of the norm axioms are satisfied by the spectral radius function $\rho(A)$ and which are not? Justify your answers
 \end{enumerate}

\item{\bf Condition Number}
\begin{enumerate}
Recall $ \kappa(A) = \|A\| \|A^{-1}\|$
 \item {For any square matrix $A \in R^{n \times n}$, prove the following relations\\
$\frac{1}{n} K_2(A) \le K_1(A) \le nK_2(A)$\\
$\frac{1}{n} K_\infty(A) \le K_2(A) \le nK_\infty(A)$\\
$\frac{1}{n^2} K_1(A) \le K_{\infty}(A) \le n^2K_1(A)$\\
% Quarteroni - Numerical Mathematics p 121
This allows us to conclude that if a matrix is ill-conditioned in a certain norm it remains so in another norm, upto a factor depending on $n$. }

\item Show that the condition number $\kappa(A)$ can be expressed as the following formula
%(Kincaid/Cheney)
\begin{equation}
 \kappa(A) = sup_{\{\|x\|=\|y\|\}} \frac{\|Ax\|}{\|Ay\|}
\end{equation}

%\item  In solving the system of equations

\item Give an example of a well-conditioned matrix whose determinant is very  small.

\item What is the condition number of a $2 \times 2$ and a $3 \times 3$ Hilbert matrix? 
Write a matlab program to plot condition number of a Hilbert matrix versus the dimension of the matrix. 
You may use matlab inbuilt functions to do this. (Explore what the function is in matlab to find condition number).
What can you conclude about the conditioning of a Hilbert matrix.

Extra marks: can you come up with (an estimate of) condition number of an $n \times n$ Hilbert matrix?
\end{enumerate}

\item {\bf Iterative methods}
% Kincaid Cheney
\begin{enumerate}
 \item 
Find the explicit form of the iteration matrix $I - Q^{-1}A$ in the Gauss Seidel method when 

A = \[ \left( \begin{array}{ccccccc}
2  & -1 &    &   &   &  &     \\
-1 & 2  & -1 &   &   &  &     \\
   & -1 &  2 & -1&   &  &     \\
   &    &  . &  .& . &  &     \\
   &    &    &  .& . &. &     \\
   &    &    &   & -1& 2& -1  \\
   &    &    &   &   & -1& 2   \end{array} \right)\] 
 

\item Write code for the Gauss-Seidel iteration to find solution for $Ax=b$ where $b = [0.88824  0.74988]^T$ and

A = \[ \left( \begin{array}{cc}
0.96326 & 0.81321   \\
0.81321 & 0.68654    \\
   \end{array} \right)\] 
\end{enumerate}


\end{enumerate}



\end{document}