%  This is a LaTex file.

%  Homework for the undergraduate course "Numerical Analysus I", 
%  Spring semester, , Wei-Cheng Wang.


\documentclass[12pt]{article}

%          The page format, somewhat wider and taller page than in art12.sty.

\topmargin -0.1in \headsep 0in \textheight 8.9in \footskip 0.6in
\oddsidemargin 0in  \evensidemargin 0in  \textwidth 6.5in

\begin{document}

%          The title and header.

\noindent
{\scriptsize Numerical Analysis I, Fall 2017 
(http://www.math.nthu.edu.tw/\~\,wangwc/)} \hfill 

\begin{center}
\large
Homework Assignment for Week 16  
\normalsize
\end{center}
\noindent
% \vspace{.3in}

% \bigskip

%           The questions!


\begin{enumerate}

\item
Derive a system of equation corresponding to the following
boundary value problem
$$
\begin{array}{l}
%u''(x) - \varepsilon u^3(x) = f(x), \quad x \in (0,1) \\
 u''(x) - u(x) = f(x), \quad x \in (0,1) \\
 u(0) = \alpha, \; u(1) = \beta 
% u(0) = 0, \; u(1) = 0 
\end{array}
$$
with uniformly spaced grids $0=x_0 < x_1 < \cdots <x_N=1$,
$x_i - x_{i-1}= h = 1/N$, using second order finite
difference method.
That is, given $\alpha$, $\beta$,
and $f_i$, $i=1,2,\cdots, N-1$,
try to derive a linear system of equations to solve for $u_i$,
$i=1,2,\cdots, N-1$.

% \item 
% Operation count for tridiagonal solver and tridiagnal LU decomposition.
% This is problem 30.

% \item
% Reading instruction for section 7.3 and 7.4:
% 
% Study understand meanings of Jacobi, Gauss-Siedel and SOR methods.
% Learn how to obtain the corresponding $T_j$, $T_g$ and $T_\omega$
% and the relation between convergence of the iterations
% and the spectral properties of the corresponding $T$'s.

% Theorem 7.22 = Stein-Rosenberg both 9th ed and 10th ed
% Theorem 7.25 = Ostrowski-Reich both 9th ed and 10th ed 
%                                (omega=1 case given in 7.3 problem 19, 10th ed)
%                                (0<omega<<2 given in 7.4 problem 14, 10th ed)
% Theorem 7.26 = rho(T_g) = rho(T_g)^2 <1 for SPD.
%                optimal omega for SPD. 

% \item
% old version: 
% Section 7.3: Min: Problems 18, 22, 26(too hard).
%     8th ed old problems 17 = new problem 9  9th ed
%            old problems 18 = new problem 10
%            old problems 22 = new problem 14
%            old problems 26 = new problem 17, too hard (= problem 19 in 10th ed) 
%                              another proof in sup-norm is in the slides
% Section 7.3: Problems           9(a,c), 10(a,c), 14 (see the slides for the Gauss-Seidel part for reference).  %9th ed, page 459

% Section 7.3: Problems 7(a), 8(a), 9(a,c), 10(a,c), 17. % 10ed page 465
% \item
% Reading instruction for section 7.5 and section 8.1:
% Section 7.5: Study the meaning and derivation of condition number.
% Skip the `iterative refinement' part.
% Section 8.1: Study the derivation of linear least square problems,
% p499-503. Skip the remaining part.
\item % Section 7.5: Error bounds and iterative refinement
% Section 7.5: Problems      2(a,c),               9, 10(a,b).
Section 7.5: Problems 1(a,c),       3(a,c),       ,11, 12(a).

\item Read Theorem 7.11 for evaluation of $\|A\|_\infty$.

\item
Section 7.5: 
The Hilbert matrices are well known ill-conditioned matrices.

In addition to the example provided in problem 9,
you can
use the matlab built-in command 'hilb' and 'cond' 
to find the condition
numbers of the Hilbert matrices $H^{(n)}$ in problem 9 directly.
% section 7.5, problem 11 % 9th ed
% section 7.5, problem 9 %10th ed
Do this for $n=6, \cdots, 10, 15, 20$ and observe how 
fast the condition number grows with $n$. 

\item
% Section 8.1: Problems 2, 14. %9th ed, p506
  Section 8.1: Problems 2, 14. %10th ed

\item
Derive the continuous version of least square problem:

Give $n$ and $f(x): [0,1] \mapsto R$, find
$a_0, \cdots a_n$ to minimize the quantity
$$
\int_0^1 \left( f(x)-(a_0 + a_1 x + \cdots a_n x^n) \right)^2 \ dx
$$
Derive the normal equation for the coefficient vector
$(a_0,\cdots a_n)$.

Remark: 
The matrix corresponding to this linear system is ill-conditioned
for large $n$ (why?). The discrete counter part,  problem 14,
is similarly ill-conditioned for large $n$.
The proper way of solving this problem numerically  for large $n$, 
say $n > 5$, can be found in section 8.2.

%% Remark: It is a fact that,
%% similar to its discrete counter part in section 8.1, problem 14,
%% both linear least square problem leads to ill-conditioned matrices
%% for large $n$. %check it with bultin command cond(A).
%% Therefore this approach is not recommended for $n > 5$.
%% For your reference,
%% the proper treatment for $n > 5$ can be found in section 8.2.

\item  
Let $A$ be the matrix from Problem 4, Homework 15.

\begin{enumerate}
\item
% Estimate numbers of multiplications needed for one iteration
Give the operation count (on multiplcation/dividion) for one iteration
of Jacobi, Gauss Seidel and SOR on this $A$, respectively.

\item
It is a fact (the proof is beyond this course) that {\bf for this $A$},
$\rho(T_j) \approx 1 - {\pi^2 \over 2} h^2$, 
$\rho(T_g) \approx 1 - \pi^2 h^2 \approx \rho(T_j)^2$.
Note that both numbers are very close to 1.
Take this fact for granted, 
estimate the number of iterations Jacobi and Gauss-Siedel take to reach
$\|e^{(k)}\| = h^2$, respectively (assuming 
$\|e^{(0)}\| = 1$) where $e^{(k)} = u^{(k)} - u_e$.
Then estimate the total number of multiplications/divisions needed for Jacobi
and Gauss-Siedel, respectively.  
You will need that $\log (1+x) \approx x$ for $|x|<<1$. 

\item
It is another fact (the proof is also beyond this course) that with 
the optimal $\omega = \omega^* \approx 2 - 2 \pi h$,
we will have $\rho(T_{\omega^*}) \approx 1- 2 \pi h$ for SOR (for this $A$).
Take this fact for granted again, 
estimate the number of iterations and total multiplications/divisions
the optimal SOR takes to reach $\|e^{(k)}\| = h^2$ with
$\|e^{(0)}\| = 1$.

\item
The facts that $\rho(T_j) \approx 1 - C_1 h^2$,
$\rho(T_g) \approx 1 - C_2 h^2$
and
$\rho(T_{\omega^*}) \approx 1 - C_3 h$ remain valid in the 3D 
case, with different constants $C_i$.
Repeat the above problems for the 3D case.

Compare these results (operation count) with that of the 
Gauss Elimination/$LU$ decomposition approach.

\end{enumerate}

\item
Derive the Jacobi version of SOR.
Express $T_{\omega, j}$ in terms of $T_{j}$.

% CCCCCCCCCCCCCCCCCCCCCCCCCCCCC

\end{enumerate}
\end{document}