\documentclass[12pt]{article}
\usepackage{fullpage,amsmath,amsfonts}

\newcommand{\x}{\boldsymbol{x}}
\newcommand{\y}{\boldsymbol{y}}
\newcommand{\f}{\boldsymbol{f}}
\renewcommand{\v}{\boldsymbol{v}}
\newcommand{\w}{\boldsymbol{w}}
\renewcommand{\r}{\boldsymbol{r}}
\renewcommand{\a}{\boldsymbol{a}}
\renewcommand{\b}{\boldsymbol{b}}
\renewcommand{\c}{\boldsymbol{c}}
\renewcommand{\k}{\boldsymbol{k}}
\newcommand{\z}{\boldsymbol{z}}
\newcommand{\e}{\mathrm{e}}
\renewcommand{\i}{\mathrm{i}}
\renewcommand{\d}{\mathrm{d}}
\renewcommand{\Re}{\operatorname{Re}}
\renewcommand{\Im}{\operatorname{Im}}
\newcommand{\Range}{\operatorname{Range}}
\newcommand{\Ker}{\operatorname{Ker}}
\newcommand{\Span}{\operatorname{Span}}
\renewcommand{\dim}{\operatorname{dim}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\C}{\mathbb{C}}

\def\nl{\vphantom\vdots\\}

\begin{document}

\title{Numerical Methods II}
\author{Problem Set 3}
\date{due in class, March 3, 2004}
\maketitle


\begin{enumerate}

\item (From SM, p.\ 103.)
Consider a matrix of the form
\[
  A = 
  \begin{pmatrix}
    b_1 & c_1 & & & \cdots & 0 \nl
    a_2 & b_2 & c_2 & & & \vdots \nl
      & a_3 & b_3 & c_3 \nl
      & & \ddots & \ddots & \ddots \nl
    \vdots & & & a_{n-1} & b_{n-1} & c_{n-1} \nl
    0 & \cdots & & & a_n & b_n \nl
  \end{pmatrix} \,.
\]
\begin{enumerate}
\item Show that if
\[
  |b_j| \geq |a_j| + |c_j| \tag{*}
\]
for $j = 1,\dots,n$ (with the convention that $a_1=c_n=0$), and
\[
  |c_j| > 0  \tag{**}
\]
for $j = 1,\dots,n-1$, then the $LU$ factorization of $A$ can be
computed without pivoting.

\emph{Note:} For simplicity, you may assume that all components of $A$
are nonnegative, though the statement is true with arbitrary signs.

\emph{Hint:} See last semester's final exam problem (3b); solutions
are online now.

\item Show that if (*) is satisfied with strict inequality in at least
  one component, then $A$ is nonsingular.

\item Give an example where (*) holds, but (**) is violated, and
  where $LU$ decomposition without pivoting is not possible.

\item Explain why the result from (b) is important for solving linear
  second order boundary value problems using second order finite
  differences (as, for example, in Project 4 below).

\end{enumerate}

\item (From SM, p.\ 381) The differential equation
\[
  - y'' + r(x) \, y = f(x)
\]
is approximated by
\[
  -\frac{\delta^2 y_j}{h^2}
  + \alpha \, r_{j-1} \, y_{j-1}
  + (1-2\alpha) \, r_j \, y_j
  + \alpha \, r_{j+1} \, y_{j+1}
  = \alpha \, f_{j-1}
  + (1-2\alpha) \, f_j 
  + \alpha \, f_{j+1} \,.
\]

\begin{enumerate}
\item Show that the local truncation error is at least $O(h^2)$ for
  any choice of $\alpha$.
\item Find a particular value for $\alpha$ so that the local truncation
  error is $O(h^4)$.
\end{enumerate}

\item  Consider the equation
\begin{gather*}
  y'' + a^2 \, y = 0 \,. 
\end{gather*}

\begin{enumerate}
\item Show that, when the boundary conditions are homogenous, i.e.\
  $y(0)=y(1)=0$, the equation has multiple solutions for special
  values of $a$.

\item Show that with inhomogenous boundary conditions $y(0) = 0$ and
  $y(1) = 1$, the equation has no solution for those values of $a$.

\end{enumerate}

\item \textbf{Project:} Solve the boundary value problem
\begin{gather*}
  -y'' + \cos^2(x) \, y = x \,, \\
  y(0) = y(10) = 0 \,,
\end{gather*}
using the standard second order finite difference approximation
\[
  -\frac{\delta^2 y_j}{h^2}
  + \cos^2(x_j) \, y_j = x_j \,.
\]
Verify that the method is order $2$ on a log-log error plot.

\item \textbf{Project:} Modify your code from the previous project to
  using the improved method from question (2).  Verify that this
  method is order $4$ on a log-log error plot.

\item \textbf{Project:} Solve the same boundary value problem using
  simple shooting.

\end{enumerate}

\end{document}
