\documentclass[]{article}
\textwidth 6.4in
\textheight 8.5in
\oddsidemargin -0.3in
\evensidemargin -0.3in
\usepackage{latexsym}
\usepackage{multicol}
%\usepackage{epsfig}
\usepackage{latexsym}
 \usepackage{epsfrag}
\usepackage{multicol}
\usepackage{fancybox}

% \topmargin -.5in

\input{/afs/eos.ncsu.edu/users/z/zhilin/TEX/mystyle}
\def\be{\begin{enumerate}}
\def\ee{\end{enumerate}}
%\newcommand{\vthin}{\vskip 5pt}


\pagestyle{empty}
\begin{document}          
\hfill\vbox{\hbox{MA/CSC 580, \ Homework \#3}
\hbox{\bf Due, October 16, 2018}}

\vskip .2in
\baselineskip 14pt

\be

\item (a): Let $x_e$ be the solution of $Ax=b$ assuming that $det(A)\neq~0$, 
$\bar{x}$ be the solution of $Ax=b + \delta b$, show that
\eqmno
\fr{ \|x_e - \bar{x}\|}{\|x_e\|} \le cond(A) \fr{\|\delta b\|}{\|b\|}.
\enmno
{\bf Hint:} $\|b\| = \| A A^{-1} b\| \le \|A\| \|A^{-1} b\|$.

(b): Given a matrix $A$ that is invertible. Let $E$ is be  such a matrix that $\|A^{-1} E\| < \alf <1$. Show that $A+E$ is invertible and $\dsp \|(A+E)^{-1}\| \le \fr{ \|A^{-1}\| }{1-\alf}$.

\vthin

\item Plot or sketch the set of $\|{\bf x}\|_p=1$ in two-dimensions, $p=1, 2, \infty$. This example helps us to understand geometric meanings of  vector norms. 

\vthin
\item %Problem 2.20 on page 99.

Given an $n$-by-$n$ non-singular matrix $A$, how do you efficiently solve
the following problems using Gaussian elimination with partial column
pivoting?
\be 
\item Solve $A^k x = b$, where $k$ is a positive integer.
\item Computer $\alf=c^T A^{-1} b$, where $c$ and $b$ are two vectors.
%\item Solve the matrix equation $AX=B$, where $B$ is an  $n$-by-$m$ matrix.
\ee
You should (1) describe your algorithm; (2) present a pseudo-code; (3) find
out the required operation counts.

\vthin

\item Often a small determinant is a sign of an ill-conditioned matrix. But this exercise is an exception. Given the following matrix $A$. (a): Find $\|A\|_{\infty}$ and $det(A)$. (b): Using Gaussian elimination to find the $A=LU$ decomposition. (c): Using your result to find $cond_{\infty}(A)$. Do you think this matrix is ill-conditioned? {\bf Hint:} Find the inverse of $U^T$ to get $U^{-1}$.  
\eqmno
A = 
  \left [\begin {array}{ccccc}
1& & & &1\\\noalign{\medskip}-1 &1& &  &1\\
\noalign{\medskip}-1 &-1 &1& &1\\
\noalign{\medskip}\vdots&\ddots&\ddots& & 1 \\
\noalign{\medskip}-1 &-1 & \cdots &-1 &1\end {array}\right ].
\enmno


\vthin
\item Check whether the following matrices are:
\bi
\item Strictly column diagonally dominant.
\item Symmetric positive definite.
\ei
Justify your conclusion. What is the significance of knowing these special
matrices to the Gaussian related algorithms? Answer this question by 
considering issues of accuracy, speed, and the
storage.
\eqmno
\left [\begin {array}{cccc}
-5&2&1&0\\\noalign{\medskip}2&7&-1&-1\\\noalign{\medskip}1&-1&5&1
\\\noalign{\medskip}0&-1&1&4\end {array}\right ], \qquad
\left [\begin {array}{ccc}
2&-1&0\\\noalign{\medskip}-1&2&-1\\\noalign{\medskip}0&-1&2\end {array}\right ]
, \qquad \left [\begin {array}{cc}
\alf & \beta \\\noalign{\medskip} -1 &2 \end
{array}\right ]
\enmno
Find the Cholesky
decomposition $A=L L^T$ or $A=L D L^T$ for the middle matrix. Note that,
you need to determine the range of $\alf$ and $\beta$.


\vthin
\vthin
\item Given a matrix $A$ and a vector $b$
\eqmno
A = \left [\begin {array}{ccc} {\frac{1}{100}}&0&0\\\noalign{\medskip}
0&2&-1\\\noalign{\medskip}0&-1&2\end {array}\right ],
\qquad b=\left [\begin {array}{c} {\frac
{1}{100}}\\\noalign{\medskip}1\\\noalign{\medskip}1\end {array}\right ]
\enmno
\be
\item Find the condition number of $A$ in 2-norm.
\item Given $x_1= \left [\begin {array}{ccc} 1&1&1\end {array}\right ]^T$
 and $x_2= \left [\begin {array}{ccc} 1.1&1&0.9\end {array}\right ]^T$,
 find the residual, and
the norm of the residual, for both $x_1$ and $x_2$ in 2-norm. 
\item Is one of $x_1$ and $x_2$ the exact solution of the system $Ax=b$?
\item If $x_1$ or $x_2$ is not the solution, use the error estimate
discussed in class (relation between the residual and the relative error) 
to give an
estimate error bound for the relative error.
\item Find the actual relative error for $x_1$ and $x_2$ as approximations
to $Ax=b$ and compare with the error bound that you just have got. How much
is the difference?
\ee

\vthin
\vthin
\item (Programming Part) Let $A$ be a symmetric positive definite
matrix.
\be
\item Derive the algorithms for $A=LDL^T$ decomposition, where $L$ is a
unit lower triangular matrix, and $D$ is a diagonal matrix.
\item Write a Matlab code (or other language if you prefer) to do the
factorization and solve the linear system of equations $Ax=b$
using the factorization.
{\bf Hint:} the process is the following:
\eqmno
L y &=& b, \qquad \mbox{$y$ is the unknown,} \\
D z &= &y, \qquad \mbox{$z$ is the unknown,}\\
L^T x &=& z, \qquad \mbox{$x$ is the unknown, which is the solution}.
\enmno

Construct at least one example that you know the exact solution to validate
your code.  %(Talk to the instructor if you need help on this.)
\ee

\ee
\end{document}
