Gaussian elimination

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

Motivation

Consider the following linear system. \begin{align*} 2u + v + w & = 5,\\ -8v -2w & = -12,\\ 1w & = 2. \end{align*}

We can readily solve it using substiution!
  1. The last equation implies $w=2$.
  2. With $\color{var(--emphColor)}{w}$ in hand, the second equation gives $v= (-12+2\color{var(--emphColor)}{w})/8=1$.
  3. Knowing $\color{var(--emphColor)}{w}$ and $\color{var(--emphColor)}{v}$ we substitute into the first equation to obtain $u=(5-\color{var(--emphColor)}{v}- \color{var(--emphColor)}{w})/2=1$.

Triangular systems

\begin{equation} \begin{array}{rl} 2u + v + w =& 5\\ -8v -2w =& -12\\ 1w =& 2 \end{array} \color{var(--emphColor)}{\leftrightarrow} \begin{bmatrix} 2 & 1 & 1 \\ & -8 & -2 \\ & & 1 \end{bmatrix} \begin{bmatrix} u \\ v \\ w \end{bmatrix} = \begin{bmatrix} 5 \\ -12 \\ 2 \end{bmatrix} \end{equation}

When the coefficient matrix describing your system is triangular, we may readily solve the system!
As is common practice, we will typically omit writing $0$'s in our matrices. “Missing” entries should be interpreted as zero.

Triangular systems

An $n\times n$ matrix $U$ is said to be upper triangular if $u_{ij} = 0$ whenever $i > j$.
Similarly, an $n \times n$ matrix $L$ is said to be lower triangular if $l_{ij} = 0$ whenever $i < j$.
An upper (lower) triangular matrix can only have nonzero entries below (above) the main diagonal.

Triangular matrices

An upper and lower triangular $U$ and $L$ look like:

Triangular systems

Our motivating example suggests we may solve systems with a triangular coefficient matrix row by row.

Backward substitution

If $U$ is upper triangular and $Ux = b$, we may:

  • (Row $n$) Use the last row to obtain $x_n$: $$u_{nn}x_n = b_n \implies x_n = b_n / u_{nn}.$$
  • (Row $n-1$) With $\color{var(--emphColor)}{x_n}$ in hand, use the $(n-1)$th row to solve for $x_{n-1}$: \begin{align} u_{n-1,n-1} x_{n-1} + u_{n-1,n} \color{var(--emphColor)}{x_n} &= b_{n-1} \implies \\ x_{n-1} &= (b_{n-1} - u _{n-1,n} \color{var(--emphColor)}{x_n}) / u_{n-1, n-1} \end{align}

Backward substitution

  • (Row $n-2$) Knowing $\color{var(--emphColor)}{x_{n}}$ and $\color{var(--emphColor)}{x_{n-1}}$, we use the $(n-2)$th row to compute $x_{n-2}$: \begin{align} u_{n-2,n-2} x_{n-2} + u_{n-2,n-1} \color{var(--emphColor)}{x_{n-1}} +u_{n-2,n}\color{var(--emphColor)}{x_{n}} &= b_{n-2} \implies \\ x_{n-2} = (b_{n-2} - u_{n-2,n-1} \color{var(--emphColor)}{x_{n-1}} &- u_{n-2,n} \color{var(--emphColor)}{x_{n}}) / u_{n-2,n-2} \end{align}
    • $\vdots$
  • (Row $n-i$) Knowing $\color{var(--emphColor)}{x_{n}}, \color{var(--emphColor)}{x_{n-1}}, \ldots, \color{var(--emphColor)}{x_{n-i+1}}$, we use the $(n-i)$th row to compute $x_{n-i}$: \begin{align} u_{n-i,n-i} x_{n-i} + \sum_{k=n-i+1}^{n} u_{n-i,k} \color{var(--emphColor)}{x_{k}} &= b_{n-i} \implies \\ x_{n-i} = (b_{n-i} - \sum_{k=n-i+1}^{n} u_{n-i,k} \color{var(--emphColor)}{x_{k}}) / u_{n-i,n-i} \end{align}