\documentclass[12pt]{article} 

\usepackage{amsmath}    
\usepackage{amsfonts}  
\usepackage{amssymb}
\usepackage{graphicx}  
\usepackage{subfig}
\usepackage{tabularx}
\setlength{\parskip}{3pt plus 2pt}
\setlength{\parindent}{20pt}
\setlength{\oddsidemargin}{0.5cm}
\setlength{\evensidemargin}{0.5cm}
\setlength{\marginparsep}{0.75cm}
\setlength{\marginparwidth}{2cm}
\setlength{\marginparpush}{1.0cm}
\setlength{\textwidth}{165mm}
\setlength{\textheight}{9 true in}
\setlength{\topmargin}{-2cm}
\setlength{\footskip}{10pt}

\linespread{1.5}

\begin{document}

\pagestyle{empty}

%\begin{flushright}
%Name: \line(1,0){200}
%\end{flushright}
%\vskip1ex
\begin{center}{
\large{ \bf{ Homework 4: due March 3/14 \\  MTH 365/465 Numerical Linear Algebra, Spring 2018}}
}\end{center}

\textbf{Note: For computational problems, you should attach both your code(s) and output.}


\emph{All students:}

\begin{enumerate}
 
\item From the text (Chapter 7): Exercises 1 (10pts), 8 (6pts), 9 (10 pts), 10(a) - read the assignment carefully (till the end on p.177) (9pts), and 12 (10pts).   
  \vskip1ex
\item (10pts) For an $n \times n $ identity matrix $I$: 
  \begin{enumerate} 
    \item explain why $||I|| = 1$ for every induced matrix norm;
    \item determine $||I||_F$ (Frobenius norm of $I$). 
  \end{enumerate}
\item (15pts) Consider the matrix 
$$ A = \begin{pmatrix} 1.2969 & 0.8648 \\  0.2161 & 0.1441 \end{pmatrix}.$$ 
Using MATLAB, compute the following and discuss the results:
\begin{enumerate}
 \item Find the condition numbers of $A$ in 1-norm, 2-norm and $\inf$-norm; compute the determinant and inverse of $A$.
 \item Let $B$ be the matrix obtained from $A$ by rounding off $a_{11}$ to three decimal places, i.e.,
$ 1.2969 \rightarrow 1.297$. Find the determinant and inverse of $B$.
 Can you explain why $A^{-1}$ and $B^{-1}$ differ?
 \item Set $b_1 = (1.2969, 0.2161)^T$ and do $x = A \backslash b_1$. You will find the solution 
 $x = (1,0)^T$. Repeat the process but with a vector $b_2$ obtained from $b_1$ by rounding off its entries to three decimal places. Explain what happens. Why do the two answers differ by so much?
 \end{enumerate}
Please submit the code containing all the steps and outputs.
\vskip2ex
\item (15pts) Gaussian elimination \emph{with partial pivoting} 
is usually backward stable in practice (i.e., it finds the exact solution to a nearby problem).
However, despite the beneficial effects of pivoting, there are \textbf{extremely rare cases} 
when it is not true. The following example illustrates this. \\ 
Suppose $A$ is the $n \times n$ matrix
$$A = \begin{pmatrix}  1 & 0 & 0 & \ldots & 1 \\ -1 & 1 & 0 & \ldots & 1 \\ -1 & -1 & 1 & \ldots & 1 \\
\vdots & & \ldots & &  \vdots \\ -1 & -1 & -1 & \ldots & 1 \end{pmatrix}. $$ 
For instance, if $n=5$, $$A = \begin{pmatrix}  1 & 0 & 0 & 0 & 1 \\ -1 & 1 & 0 & 0 & 1 \\ -1 & -1 & 1 & 0 & 1 \\
-1 & -1 & -1 & 1 & 1 \\ -1 & -1 & -1 & -1 & 1 \end{pmatrix}. $$
\begin{enumerate}
 \item Write a code in MATLAB to generate a matrix of this form of a given size $n$. 
 \item Generate a square matrix for, say, of size $n=70$ and perturb the last column with a small random perturbation,
 say, $A(:,n) = A(:,n) + 10^{-6}*\text{randn}(n,1)$. Find the condition number of the resulting matrix with respect to any norm.
 Is $A$ well- or ill-conditioned?
 \item The computed solution to a linear system $A\mathbf{x} = \mathbf{b}$ turns out to be far from correct. 
 To see this, set up a problem by typing $x = \text{randn}(n,1)$ and $b = A*x$. 
 Then perform Gaussian elimination with partial pivoting by using either $[L,U,P] = lu(A)$ 
 with $y = L \backslash (P*b)$ and then $x_c = U \backslash y$ or your own code to 
 compute solution $x_c$. Compare the computed solution $x_c$ with $x$ (you can type $\text{norm}(x_c-x)$). 
\end{enumerate} 
 Please submit the code containing all the steps and outputs.   

\end{enumerate}

\vskip2ex
\emph{MTH 465 students:} In addition, do Exercise 10(b,c) (5pts each) from Chapter 7.

\end{document}






-
