\documentclass[twoside]{article}

\usepackage{palatino}
\usepackage{camnum}

\newcommand {\ra}{{\quad \Rightarrow \quad}}
\renewcommand{\arraystretch}{1.5}

\textheight=22.5cm
\textwidth=15cm
\topmargin=-1cm
\oddsidemargin=0.5cm
\evensidemargin=0.5cm
\parindent=0pt
\parskip=6pt

\begin{document}
\begin{center}
  {\large \textbf{Mathematical Tripos Part IB: Easter 2001}}

  {\Large \textbf{Numerical Analysis -- Detailed Example 3a
       \footnote{Corrections and suggestions to these notes should
        be emailed to \texttt{a.shadrin@damtp.cam.ac.uk}. All handouts
        are available on the WWW at the URL 
        \texttt{http://www.damtp.cam.ac.uk/user/na/PartIB/Handouts.html}.}}}

  \vspace{8pt}
  \textbf{\textit{\LARGE Jacobi and Gauss--Seidel methods}}
\end{center}

\begin{center}
\large \sf 
%\begin{tabular}[t]{l}
%Compute two iterations of 
Jacobi and Gauss--Seidel methods for an 
approximate solution of
$
\left(\begin{array}{ccc}
4&2&1\\
2&5&2\\
1&2&6
\end{array}\right)\,
\left(\begin{array}{c} x_1\\x_2\\x_3 \end{array}\right)
= \left(\begin{array}{c} 5\\4\\7 \end{array}\right)
\quad \mbox{
with the starting vector $x^0 = (1,1,1)^T$}
$
%\end{tabular}
\end{center}

\bigskip
1) The Jacobi method: \quad
$
\begin{array}{rcl*{5}{@{}l}}
x_1^{k+1} &=& \frac{1}{4}\,(5     &       &-2 & x_2^k &-  & x_3^k) \\ 
x_2^{k+1} &=& \frac{1}{5}\,(4 - 2 & x_1^k &   &       &-2 & x_3^k) \\ 
x_3^{k+1} &=& \frac{1}{6}\,(7 -   & x_1^k &-2 & x_2^k)&
\end{array}
$

with $x^0 = (1,1,1)^T$, the first two iterations are
$$
\begin{array}{rlll}
x_1^1 &= \frac{1}{4}\,(5 - 2\cdot 1 - 1\cdot 1) &= \frac{1}{2} \\
x_2^1 &= \frac{1}{5}\,(4 - 2\cdot 1 - 2\cdot 1) &= 0 \\
x_3^1 &= \frac{1}{6}\,(7 - 1\cdot 1 - 2\cdot 1) &= \frac{2}{3}
\end{array} \ra
\begin{array}{rlll}
x_1^2 &= \frac{1}{4}\,(5 - 2\cdot0 - 1\cdot\frac{2}{3}) 
      &= \frac{13}{12} \\
x_2^2 &= \frac{1}{5}\,(4 - 2\cdot\frac{1}{2} - 2\cdot\frac{2}{3}) 
      &= \frac{1}{3} \\
x_3^2 &= \frac{1}{6}\,(7 -  1\cdot\frac{1}{2} - 2\cdot0) 
      &= \frac{13}{12}
\end{array}
$$

\bigskip
2) The Gauss--Seidel method: \qquad
$
\begin{array}{rcl@{}r@{}r@{}l@{}r}
x_1^{k+1} &=& \frac{1}{4}\,(5 &              &-2 &x_2^k     & - x_3^k) \\ 
x_2^{k+1} &=& \frac{1}{5}\,(4 & -2 x_1^{k+1} &   &          &- 2x_3^k) \\ 
x_3^{k+1} &=& \frac{1}{6}\,(7 &  - x_1^{k+1} &-2 &x_2^{k+1})&
\end{array}
$

with $x^0 = (1,1,1)^T$, the first two iterations are
$$
\begin{array}{@{}rclr@{}}
x_1^1 &=& \frac{1}{4}\,(5 - 2\cdot 1 - 1\cdot 1) = & \frac{1}{2} \\
x_2^1 &=& \frac{1}{5}\,(4 - 2\cdot\frac{1}{2} - 2\cdot 1) = & \frac{1}{5}  \\
x_3^1 &=& \frac{1}{6}\,(7 - 1\cdot\frac{1}{2} - 2\cdot\frac{1}{5}) 
= & \frac{61}{60}
\end{array} \ra
\begin{array}{rlll}
x_1^2 &= \frac{1}{4}\,(5 - 2\cdot\frac{1}{5} - 1\cdot \frac{61}{60}) 
      &= \frac{43}{48}
      &= 0.8958 \\
x_2^2 &= \frac{1}{5}\,(4 - 2\cdot\frac{43}{48} - 2\cdot\frac{61}{60}) 
      &= \frac{7}{200}
      & = 0.035  \\
x_3^2 &= \frac{1}{6}\,(7 - 1\cdot\frac{43}{48} - 2\cdot\frac{7}{200})
      &= \frac{7241}{7200}
      & = 1.0057
\end{array}
$$

\bigskip
3) The exact solution is $x^* = (1,0,1)^T$.

\bigskip
4) Both methods converge (because $A$ is positive definite and 
diagonally dominant),\\ 
\phantom{4)} the Gauss--Seidel method much faster.

\end{document}


\end{document}
%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: 
