% 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 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}