GUIDING QUESTION:
How can I improve the LU factorization?
Motivation
Let's study the shortcomings of our
LU factorization algorithm
and think about how we can improve the process.
Use Gaussian Elimination to
compute an LU factorization for
\begin{align}
\begin{bmatrix}
0 & 1\\
1 & 0
\end{bmatrix}.
\end{align}
Our algorithm assumes we'll never encounter zero pivots, so we can't
factor this matrix!
Motivation
In practice, when performing finite-precision arithmetic,
pivots that are
almost zero
may cause the roundoff error to explode.
Let's solve the linear system
\begin{align}
\begin{bmatrix}
0.0001 & 1\\
1 & 1
\end{bmatrix}
\begin{bmatrix}
x\\
y
\end{bmatrix}
=
\begin{bmatrix}
1\\
2
\end{bmatrix}
\end{align}
using Gaussian Elimination.
The factor $l_{21}= \frac {a_{21}} {a_{11}} = 10^4$,
so the second equation becomes
$-9999y = -9998$,
so
\begin{align}
& \,\, y = 0.9998\overline{9998} \text{ and then} \\
&\bbox[4pt, border: 3pt solid var(--emphColor)]{x = 1.0001\overline{0001}}
\end{align}
the equation $-9999 y = - 9998$ becomes
$-0.1 \times 10^5 y=-0.1 \times 10^5$, so
\begin{align}
& \,\, y = 1 \text{ and then} \\
&\bbox[3pt, border: 3pt solid var(--emphColor)]{x = 0,}
\end{align}
which is completely off!
How can we fix this?
Partially, by swapping rows!
Exchanging rows, we have
\begin{align}
x + y & = 2\\
.0001x + y & =1
\end{align}
Exchanging rows, we have
\begin{align}
x + y & = 2\\
.0001x + y & =1
\end{align}
Now $l_{21} = \frac {0.0001}{1} = .0001$ and eliminating the first
column gives
\begin{align}
x + \,\,\,\,\,\,\,\,\,\, y & = 2\\
.9999y & = .9998
\end{align}
Exchanging rows, we have
\begin{align}
x + y & = 2\\
.0001x + y & =1
\end{align}
so we obtain
$\bbox[3pt, border: 3pt solid var(--emphColor)]{x = 1}$.
Motivation
The last example suggests that swapping rows may improve our
LU factorization algorithm.
In general, we must devise a strategy to inform which rows to
swap and when.
Partial pivoting
At the
$k$th elimination step,
set $$M_{\color{var(--emphColor)}{k}} = \max _{\color{var(--emphColor)}{k} \leq i \leq n} |a_{i\color{var(--emphColor)}{k}}|$$
denote the largest entry in $A(k:n, k)$, the $\color{var(--emphColor)}{k}$th column at or below row
$\color{var(--emphColor)}{k}$.
If the maximum appears in row $i_0$ below row $k$,
swap rows $i_0$ and $k$:
$r_{i_0} \gets r_k, \quad r_k \gets r_{i_0}.$
In contrast to the more complicated
full pivoting
,
and
rook pivoting
strategies, which involve
swapping both rows and columns, our
partial pivoting strategy involves only
row swaps.