\documentclass[twoside]{article}

\usepackage{palatino}
\usepackage{camnum}

\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 1999}}

  {\Large \textbf{Numerical Analysis -- Detailed Example
      2\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 LU factorization with pivoting}}
\end{center}

Let
\begin{displaymath}
  A=A_0=\left[
    \begin{array}{rrrr}
      -3 & 2 & 3 & -1\\
      6 & -2 & -6 & 0\\
      -9 & 4 & 10 & 3\\
      12 & -4 & -13 & -5
    \end{array}\right],\qquad \MM{i}=\left[
    \begin{array}{c}
      1\\2\\3\\4
    \end{array}\right].
\end{displaymath}
($\MM{i}$ holds the order of rows.) Hence, assembling in $A_k$ bits of
$L$, $U$ and the `real' $A_k$
\begin{Eqnarray*}
  &&\qquad\mbox{Pivot}=(A_0)_{4,1},\qquad A_0^{\CC{new}}=\left[
    \begin{array}{rrrr}
      12 & -4 & -13 & -5\\
      6 & -2 & -6 & 0\\
      -9 & 4 & 10 & 3\\
      -3 & 2 & 3 & -1
    \end{array}\right],\qquad \MM{i}=\left[
    \begin{array}{c}
      4\\2\\3\\1
    \end{array}\right]\\
  && \MM{\ell}_1=\left[
    \begin{array}{r}
      1\\\frac12 \\ -\frac34 \\ -\frac14
    \end{array}\right],\qquad \MM{u}_1^{\CC{T}}=[
    \begin{array}{rrrr}
      12, & -4, & -13, & -5
    \end{array}], \qquad A_1=\left[
    \begin{array}{r|rrr}
      12 & 4 & -13 & -5\\\hline
      \frac12 & 0 & \frac12 & \frac52\\
      -\frac34 & 1 & \frac14 & -\frac34\\
      -\frac14 & 1 & -\frac14 & -\frac94
    \end{array}\right],\\
  &&\qquad\mbox{Pivot}=(A_1)_{3,2},\qquad A_1^{\CC{new}}=\left[
    \begin{array}{r|rrr}
      12 & -4 & -13 & -5\\\hline
      -\frac34 & 1 & \frac14 & -\frac34\\
      \frac12 & 0 & \frac12 & \frac52\\
      -\frac14 & 1 & -\frac14 & -\frac94
    \end{array}\right],\qquad \MM{i}=\left[
    \begin{array}{c}
      4\\3\\2\\1
    \end{array}\right],\\
  && \MM{\ell}_2=\left[
    \begin{array}{r}
      0\\1\\0\\1
    \end{array}\right],\qquad \MM{u}_2^{\CC{T}}=[
  \begin{array}{rrrr}
    0, & 1, & \frac14, & -\frac34
  \end{array}],\qquad A_2=\left[
    \begin{array}{rr|rr}
      12 & -4 & -13 & -5\\
      -\frac34 & 1 & \frac14 & -\frac34\\\hline
      \frac12 & 0 & \frac12 & \frac52\\
      -\frac14 & 1 & -\frac12 & -\frac32
    \end{array}\right],\\
  &&\qquad\mbox{Pivot}=(A_2)_{3,3},\qquad
  A_2^{\CC{new}}=A_2^{\CC{old}},\qquad \MM{i}=\left[
    \begin{array}{c}
      4\\3\\2\\1
    \end{array}\right],\\
  && \MM{\ell}_3=\left[
    \begin{array}{r}
      0\\0\\1\\-1
    \end{array}\right], \qquad \MM{u}_3^{\CC{T}}=[
  \begin{array}{rrrr}
    0, & 0, & \frac12, & \frac52
  \end{array}],\qquad A_3=\left[
    \begin{array}{rrr|r}
      12 & -4 & -13 & -5\\
      -\frac34 & 1 & \frac14 & -\frac34\\
      \frac12 & 0 & \frac12 & \frac52\\\hline
      -\frac14 & 1 & -1 & 1
    \end{array}\right],\\
  && \MM{\ell}_4=\left[
    \begin{array}{r}
      0\\0\\0\\1
    \end{array}\right], \qquad \MM{u}_3^{\CC{T}}=[
  \begin{array}{rrrr}
    0, & 0, &0, & 1
  \end{array}].
\end{Eqnarray*}
Hence
\begin{displaymath}
  A=PLU=\left[
    \begin{array}{cccc}
      0 & 0 & 0 & 1\\
      0 & 0 & 1 & 0\\
      0 & 1 & 0 & 0\\
      1 & 0 & 0 & 0
    \end{array}\right] \left[
    \begin{array}{rrrr}
      1 & 0 & 0 & 0\\
      -\frac34 & 1 & 0 & 0\\
      \frac12 & 0 & 1 & 0\\
      -\frac14 & 1 & -1 & 1
    \end{array}\right] \left[
    \begin{array}{rrrr}
      12 & -4 & -13 & -5\\
      0 & 1 & \frac14 & -\frac34\\
      0 & 0 & \frac12 & \frac52\\
      0 & 0 & 0 & 1
    \end{array}\right].
\end{displaymath}


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