hw2_Math428_Sp2018.tex

\documentclass [12pt]{article}
\setlength{\topmargin}{-0.5cm} \setlength{\oddsidemargin}{0.0cm}
\setlength{\evensidemargin}{0.0cm} \setlength{\textwidth}{6in}
\setlength{\textheight}{9in}

\usepackage{latexsym,fleqn}
\usepackage{graphicx}

\begin{document}

\def\e{\mathop{\rm e}\nolimits}
\noindent
\begin{center}
{ \bf  {Math/Phys/Engr 428, Math 529/Phys 528 \\
Numerical Methods - Spring 2018 }}\\[7pt]
\underline{\bf Homework 2}\\

%Assigned: Friday, January 20, 2012\\
Due: {\bf Monday, February 12, 2017}

\end{center}


{\bf Taylor Polynomials}

\begin{enumerate}

\item Consider the function $f(x)=\cos(\pi x/2)$.

\begin{enumerate}

\item Expand $f(x)$ in a Taylor series about the point $x_0=0$.

\item Find an expression for the remainder.

\item Estimate the number of terms that would be required to guarantee
%six-significant-digit
accuracy for $f(x)$ within $10^{-5}$  for all $x$ in the interval
$[-1, 1]$.

\item Plot $f(x)$ and its 1st, 3rd, 5th and 7th degree Taylor polynomials
over $[-2, 2]$. (Use the Matlab command {\em subplot}
to generate a number of plots on the same page).

\end{enumerate}

%\end{enumerate}

{\bf Root Finding Methods}

%\setcounter

%\begin{enumerate}

\item Which of the following iterations $x_{n+1}=g(x_{n})$ will
converge to the indicated fixed point $\alpha$ (provided $x_0$ is
sufficiently close to $\alpha$)? If it does converge, give the
order of convergence; for linear convergence, give the rate of
linear convergence (i.e., the asymptotic constant).  In the case
that $g^{\prime}(\alpha)=0$, try expanding $g(x)$ in a Taylor
polynomial about $x=\alpha$ to determine the order of convergence. (See Section 2.3 (pg. 90-91) for more details on convergence of fixed point iteration schemes.)

\begin{enumerate}

\item
 ${\displaystyle x_{n+1}=-16+6x_n+\frac{12}{x_n}}$, \hskip 20pt $\alpha=2$

\item
 ${\displaystyle x_{n+1}=\frac{2}{3}x_n+\frac{1}{x_n^2}}$, \hskip 20pt  $\alpha=3^{1/3}$

\item
 ${\displaystyle x_{n+1}=\frac{12}{1+x_n}}$, \hskip 20pt $\alpha=3$

\end{enumerate}


\item
Let $\alpha$ be a fixed point of $g(x)$. Consider the fixed-point iteration $x_{n+1}
=g(x_n)$ and suppose that $\max |g'(x)|=k<1$. Prove the following error estimate
$$|\alpha-x_{n+1}|\le {k\over {1-k}}|x_{n+1}-x_n|.$$

\vskip 5pt
\noindent
(hint: by MVT,  $|\alpha-x_{n+1}| = |g'(\xi)||\alpha-x_{n}| \le k|\alpha-x_{n}|$)

\item The function $f(x)=27x^4+162x^3-180x^2+62x-7$ has a zero at $x=1/3$. Perform ten iterations of Newton's method on this function, starting from $p_0=0$. What is the apparent order of convergence of the sequence of approximations? What is the multiplicity of the zero at $x=1/3$? Would the sequence generated by the bisection method converge faster?

\item Newton's method approximates the zero of $f(x)=x^3+2x^2-3x-1$ on the interval $(-3,-2)$ to within $9.436\times 10^{-11}$ in $3$ iterations and $6$ function evaluations. How many iterations and how many function evaluations are needed by the secant method to approximate this zero to a similar accuracy? Take $p_0=-2$ and $p_1=-3$.


\item \textbf{(Gaussian Elimination)} 

Let $A$ be the $2 \times 2$ matrix $A =\pmatrix{ a& b \cr c
& d }~.~$ Use Gaussian elimination to obtain $A^{-1}$ by solving the
two systems $Ax_1=e_1$ and $Ax_2=e_2$, where $e_1$ and $e_2$ are
the columns of the $2\times2$ identity matrix. Note that you can
perform both at the same time by considering the augmented system
$[A | I]$. Show that $A^{-1}$ exists if and only if $\det(A) \neq
0$.

\item \textbf{($LU$ Decomposition)}

Find the $LU$ decomposition of $A$ and use it to solve $Ax=b$.
$$
A=\pmatrix{ 4& 1& 0& 0\cr
            1& 4& 1& 0\cr
            0& 1& 4& 1\cr
            0& 0& 1& 4}~,~
b=\pmatrix{2\cr
           -3\cr
           3\cr
           -2}.
$$


\item \textbf{(Back and Forward Substitution: Matlab Program)}

Write two programs, one that performs back substitution on an upper triangular matrix and another that performs forward substitution on a lower triangular matrix (you may assume that the diagonal entries are all 1). Both files should begin:
\begin{verbatim}
function [x] = forwardsub(L, b)
n=length(b); 
(your code here)
\end{verbatim}
In the above, $L{\bf x} = {\bf b}$ and $A$ is lower triangular. Test your code on
the following systems:
$$
\left[\begin{array}{ccc}
                        1&0&0\\
                        2&1&0\\
                        3&4&1 \end{array}
                        \right] {\bf x} = \left[\begin{array}{c}
                        -1\\
                        0\\
                        1 \end{array}
                        \right] \;\mbox{and}\;                         
                        \left[\begin{array}{ccc}
                        1&2&-1\\
                        0&3&-1\\
                        0&0&2 \end{array}
                        \right] {\bf y} = \left[\begin{array}{c}
                        -1\\
                        0\\
                        1 \end{array}
                        \right]
$$
Remember, in Matlab you can solve matrix equations as follows (assuming you have defined the matrix $A$ and the rhs vector ${\bf b}$):
\begin{verbatim}
>> A\b
\end{verbatim}
Print and hand-in the text file containing your program.

\item  \textbf{(Special Matrices)}

Consider the problem $Ax=b$ where $A$ is a tridiagonal matrix.
What is the operation count for the forward elimination and the back
substitution steps of Gaussian elimination in this case?
Count add/sub and mult/div operations separately, then give the
overall order of the total operations needed. (Use $O(n^p)$ notation).

%\newpage



\bigskip

{\bf Suggested / Additional problems for Math 529/Phys 528 students:}


\item
Let
$
E_1=\pmatrix{ 1       &  0 &  0 \cr
             -m_{2,1} &  1 &  0 \cr
             -m_{3,1} &  0 &  1 }~,~~
E_2=\pmatrix{ 1       &  0       &  0 \cr
              0       &  1       &  0 \cr
              0       & -m_{3,2} &  1 }~,~~
P_1=\pmatrix{ 0       &  1 &  0 \cr
              1       &  0 &  0 \cr
              0       &  0 &  1 }~.
$

\bigskip
(a) Show that
$$
E_1^{-1}=\pmatrix{ 1       &  0 &  0 \cr
                   m_{2,1} &  1 &  0 \cr
                   m_{3,1} &  0 &  1 }~.
$$

\bigskip
(b) Show that
$$
E_1^{-1}E_2^{-1}=\pmatrix
            { 1       &  0       &  0 \cr
              m_{2,1} &  1       &  0 \cr
              m_{3,1} &  m_{3,2} &  1 }~.
$$

\smallskip
(c) Show that $P_1^{-1}$=$P_1$.



\item{{(\bf Accelerating convergence of Newton's method) }(Please read Section 2.6 on Accelerating Convergence, in particular, on Restoring Quadratic Convergence to Newton's method (pages 120--122)})

The function $f(x)=27x^4+162x^3-180x^2+62x-7$ has a zero of multiplicity 3 at $x=1/3$. Apply both techniques for restoring quadratic convergence to Newton's method, discussed on pages 120--122, to this problem. Use $p_0=0$, and verify that both resulting frequencies converge quadratically.

\item{{\bf Elementary Matrices, from Trefethen--Bau 1997}}

Let $B$ be a $4 \times 4$ matrix to which we apply the following
operations.
\begin{itemize}
\item   Double column 1, \item   halve row 3, \item   add row 3 to
row 1, \item   interchange columns 1 and 4, \item   subtract row 2
from each of the other rows, \item   replace column 4 by column 3,
\item   delete column 1 (so that the column dimension is reduced
by 1).
\end{itemize}

\begin{enumerate}

\item   Write the result as a product of eight matrices, including
$B$. 

\item   Write it again as a product ABC (same B) of three matrices. 

\noindent \hspace*{-20pt}\underline{Note:} You may find useful
using a handout {\it on elementary matrices} posted on the course
web site:

\begin{verbatim}
http://www.webpages.uidaho.edu/~barannyk/Teaching/elem_matr.pdf
\end{verbatim}

\end{enumerate}
\end{enumerate}

\end{document}


\item  Let $f(x)=\cos(x+2)$. Compute $f'(0)$ using the difference
quotients given below and step-size $h=2^{-n}$, $n=1,\ldots,5$.

\begin{tabular}{ll}
\mbox{a)} & $D_+f=\biggl(f(x+h)-f(x)\biggr)/h$ \\[10pt]
\mbox{b)} & $D_0f=\biggl(f(x+h)-f(x-h)\biggr)/2h$
\end{tabular}

For each difference formula, make a table which contains the
following information.

\begin{tabular}{ll}
\mbox{column 1:} & $h$ \\[5pt]
\mbox{column 2:} & $Df$ \\[5pt]
\mbox{column 3:} & $f'(0)-Df$ \\[5pt]
\mbox{column 4:} & $(f'(0)-Df)/h$ \\[5pt]
\mbox{column 5:} & $(f'(0)-Df)/h^2$ \\[5pt]
\mbox{column 6:} & $(f'(0)-Df)/h^3$
\end{tabular}

\noindent Discuss your results (\underline{Hint}: order of
convergence).

\item  Show that $D_+D_-f=f''(x)+O(h^2)$, where

\[
D_+=\frac{f(x+h)-f(x)}{h}, \qquad  D_-=\frac{f(x)-f(x-h)}{h}
\] \[
D_+D_-f=\displaystyle \frac{f(x-h)-2f(x)+f(x+h)}{h^2}
\]

\underline{Hint:} Expand $f(x \pm h)$ for sufficiently small $h$
to at least fourth order using Taylor polynomials.