\documentclass[11pt]{article}


\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amssymb}
\input epsf
\usepackage [usenames,dvipsnames]{color}
\newcommand{\R}{\mathbb R}
\newcommand{\C}{\mathbb C}
\newcommand{\F}{\mathbb F}
\newcommand{\pa}{\partial}
\renewcommand{\P}{\mathcal P}
\newcommand{\cL}{\mathcal L}
\renewcommand{\O}{\Omega}
\newcommand{\norm}[1]{\left\lVert#1\right\rVert}
\def\ds{\displaystyle}
\def\ul{\underline}
\def\mb{\mathbf}
\usepackage{graphicx}
\usepackage{tikz}
\oddsidemargin=-0.0cm
\evensidemargin=-0.0cm
\topmargin=-0.0cm
\textwidth=7in
\textheight=9in
\newtheorem{theorem}{Theorem}
\newtheorem{cor}{Corollary}
\newtheorem{lemma}{Lemma}
\newtheorem{definition}{Definition}
\def\ds{\displaystyle}
\def\ul{\underline}
\def\mb{\mathbf}


\DeclareMathAlphabet{\mathpzc}{OT1}{pzc}{m}{it}



\oddsidemargin=-0.0cm
\evensidemargin=-0.0cm
\topmargin=-0.0cm
\textwidth=7in
\textheight=9in

\title{Sample Problems}
\pagestyle{myheadings}
\author{Math 464}
\date{}

\begin{document}
\maketitle
\markboth{Sample Problems}{Sample Problems}



%\section{Header File}

The midterm (on Wednesday, October 26) will be closed book and will
cover the material through \S 4.3.3  One
notebook-size page of notes will be allowed on 
the test. You should give any numerical answers in the form of a
rational number or a simple expression involving radicals. Calculators
or electronic devices 
will not be allowed. 
\bigskip

\begin{enumerate}

\item In using Newton's method to find a root of an equation $\ds
  f(x)=0$, with initial guess $\ds x_0=3$, we compute $f(x_0)=1$, and
  find that $\ds x_1=5$. What is $\ds f'(x_0)$?

\item Let $\ds a $ be a given number and suppose that $\ds
  0 < \epsilon <1$ is also a given number,  Show that the equation $\ds
  a=x-\epsilon \sin x$ has a unique solution and it can be found by fixed
  point iteration of an appropriate function with any starting value.

\item Consider the system of equations
\begin{align*}
2x+y&=3,\\
x+2y&=1.
\end{align*}
\begin{enumerate}
\item Compute two steps of the Jacobi method and two steps of the
  Gauss-Seidel method, beginning with initial guess $x=1, y=0$ for this system.
\item Compute the 1-norm and $\infty$-norm of the iteration matrices.
\item  Which method do you think converges fastest?
\end{enumerate}

\item The reciprocal of a number $R$ can be computed by the following 
iteration (no divisions!):
\[
 x_{n+1}=x_n(2-x_nR).
\]
  This is Newton's method applied to find the zero
of a certain function $f$.  What is $f$?

\bigskip

\item  Each of the following iterations may converge.  If the iteration
  does converge it will be to a root of a polynomial $p(x)$.  In all three
  cases the convergence will be to some root of the same polynomial.  

\begin{equation}
x_{k+1}=x_k^2-2x_k+2
\end{equation}
\begin{equation}
x_{k+1}=x_k-\frac{x_k^2 -3x_k+2}{2x_k-3}
\end{equation}
\begin{equation}
x_{k+1}=-x_k^2+4x_k-2
\end{equation}
\begin{itemize}
\item[a)]  What is $p(x)$?  What are its roots?
\item[b)]  One of the iterations will converge to either of the two roots
  of $p(x)$ if the initial guess is sufficiently close.  Each of the others
  will converge to one root, but can't possibly converge to the other
  unless the initial guess is exactly equal to the root.  Which is which?
  Give a justification for your answer.
\end{itemize}

\bigskip

\item 
\begin{itemize}
\item[a)]  Find the $A=LU$ factorization of 
\begin{equation*}
\begin{bmatrix} 1&\frac{1}{2}&\frac{1}{3}\\ \frac{1}{2}&\frac{1}{3}&\frac{1}{4}\\ \frac{1}{3}&\frac{1}{4}&\frac{1}{5}\end{bmatrix}
\end{equation*}
by using Gaussian elimination.  $L$ should have $1$'s on the
main diagonal.
\item[b)]  Use part a) to solve:
\begin{equation*}
Ax=\begin{bmatrix}1\\0\\1\end{bmatrix}
\end{equation*}
\end{itemize}

\bigskip

\item Find the best least squares straight line fit $\ds y=ax+b$ to the data
$\ds (0,1), (1, -1), (2, 4)$.  

\item  Let
$
A=\begin{bmatrix}1&2\\2&2\\2&3\end{bmatrix}\   
b=\begin{bmatrix} 5\\0\\-4\end{bmatrix}
$.  Find the least squares 
solution to the 
problem $Ax=b$ using the normal equations.

\bigskip

\item Compute four steps of Newton's method to solve $x^3-2x +2=0$
  with $x_0=0$. Explain what is happening.

\bigskip

\item  
\begin{itemize}
\item[a)]  Let $A$ be row diagonally dominant.  Prove that
  $A^{-1}$ exists.
\item[b)]  Let 
\begin{equation*}
A=\begin{bmatrix}3&1\\1&2\end{bmatrix},\ 
b=\begin{bmatrix}1\\1\end{bmatrix},\ 
x^{(0)}=\begin{bmatrix}0\\0\end{bmatrix}
\end{equation*}
Compute two steps, $x^{(1)}, x^{(2)}$ of the Jacobi method for solving
$Ax=b$.  Give an error estimate for $\Vert x^{(2)}-x_t\Vert$ in terms of
$\Vert x^{(1)}- x^{(0)}\Vert$, where $x_t$ is the true solution.
\end{itemize}

\bigskip

\item  Let
\begin{equation*}
A=\begin{bmatrix}3&1\\2&1\end{bmatrix}
\end{equation*}
\begin{itemize}
\item[a)]  Compute $\kappa_{\infty}(A)$.
\item[b)]  Let 
\begin{equation*}
b=\begin{bmatrix}4\\3\end{bmatrix}
\end{equation*}
and suppose that 
\begin{equation*}
x_c=\begin{bmatrix}.9\\1.1\end{bmatrix}
\end{equation*}
is a computed solution of $Ax=b$.  Give upper and lower estimates on
${\displaystyle \frac{\Vert x_c-x_t\Vert} {\Vert x_t\Vert}}$, using
$\kappa_{\infty}(A)$, where $x_t$ is the true solution.
\end{itemize}

\bigskip

\item  Consider the fixed point iteration
\begin{equation*}
x_{n+1}=\frac{1}{3+x_n}, x_0=0
\end{equation*}

\begin{itemize}
\item[a)]  Prove that 
\begin{equation*}
\vert x_{n+1}-x_n\vert < \frac{1}{ 9}\vert x_n-x_{n-1}\vert
\end{equation*}
\item[b)]  Prove that $x_n$ converges to a limit, $s$.
\item[c)]  Prove that $x_n-s$ alternates in sign.
\item[d)]  Find $s$.
\end{itemize}

\end{enumerate}

%\bibliographystyle{amsplain}
%\bibliography{header}

\end{document}
