Expressing the Algorithm

There is a more systematic way of describing the Gaussian elimination process.

Easy-to-solve systems
- A is a lower-triangular matrix $\begin{eqnarraystar} \left[ \begin{array} {ccccc} a_{11} & 0 & 0 & \cdots & 0 ... ...b_1 \ b_2 \ b_3 \ \vdots \ b_n \end{array} \right]. \end{eqnarraystar}$ It can be solved as $\begin{eqnarraystar} x_1 & = & b_1 / a_{11}, \ x_2 & = & (b_2 - a_{21} x_1) / ... ...1} x_1 - a_{n2} x_2 - \cdots - a_{n\,n-1} x_{n-1}) / a_{nn}. \end{eqnarraystar}$ This is called the forward substitution.
- A is an upper-triangular matrix $\begin{eqnarraystar} \left[ \begin{array} {ccccc} a_{11} & a_{12} & a_{13} & \... ...b_1 \ b_2 \ b_3 \ \vdots \ b_n \end{array} \right]. \end{eqnarraystar}$ It can be solved as $\begin{eqnarraystar} x_n & = & b_n / a_{nn}, \ x_{n-1} & = & (b_{n-1} - a_{n-1... ...} x_{n-1} - a_{1,n-2} x_{n-2} \cdots - a_{12} x_2) / a_{11}. \end{eqnarraystar}$ This is called the back substitution
- Constraint: $a_{11}, a_{22}, \ldots, a_{nn} \neq 0$
- # operations for both cases -- $\Theta(n^2)$ .
Strategy
If we can write A = LU, with L lower-triangular and U upper-triangular, then what we need to do is

1.
Solve z in Lz = b, then
2.
Solve x in Ux = z

Next: LU-factorization Up: SOLVING LINEAR SYSTEMS Previous: Gaussian Elimination