LU factorization

GUIDING QUESTION: How can I compute a solution to a linear system?

Motivation

In many, many applications, we'll need to solve the linear systems $$\color{var(--emphColor)}{A}x=b_1, \,\, \color{var(--emphColor)}{A}x=b_2, \,\, \ldots, \,\, \color{var(--emphColor)}{A}x=b_N,$$ for many different load vectors $b_j$.

We could use Gaussian Elimination to solve each system, but that seems wasteful:
although we'd be transforming a different load vector every time, we'd be performing the same operations on $A$!

A better way forward

What if we run Gaussian Elimination once on $A$, keeping track of the elementary row operations used.

Then, using this record, we may transform each load vector accordingly.

GE + bookkeeping = LU

The LU factorization results from recording the elementary row operations used in Gaussian Elimination.

An LU factorization of an $n\times n$ matrix $A$ is a pair of lower and upper triangular matrices $L$ and $U$ such that $$A=LU.$$

In general, the LU factorization of a matrix $A$ is not unique unless we specify the diagonal entries of either $L$ or $U$.
Setting $l_{ii}=1$ reulsts in the popular “Doolittle” factorization and requiring $u_{ii}=1$ results in the “Crout” factorization.
See warm-up exercise 12 on HW2.

How do we get $L$?

The goal of Gaussian Elimination is to obtain an upper triangular system, so the resulting matrix is probably related to the $U$ we seek in an LU factorization.

How does the lower triangular matrix $L$ come out of the elimination procedure?

Let's take a closer look

Consider the array $L$ created during our Gaussian Elimination routine.