System Solving

Gaussian Elimination

The general method for solving square systems of linear equations.

Solving Triangular Systems

Before tackling general systems, we first look at systems that are already in a "nice" form: Triangular Matrices.

Lower Triangular ($L$)

All non-zero elements are on or below the diagonal.

\[ L = \begin{bmatrix} l_{11} & 0 & \dots \\ l_{21} & l_{22} & 0 \\ \vdots & & \ddots \end{bmatrix} \]

Method: Forward Substitution

Upper Triangular ($U$)

All non-zero elements are on or above the diagonal.

\[ U = \begin{bmatrix} u_{11} & u_{12} & \dots \\ 0 & u_{22} & \dots \\ 0 & 0 & \ddots \end{bmatrix} \]

Method: Backward Substitution

Algorithm: Backward Substitution

x(n) = b(n) / A(n,n)
for i = n-1 down to 1
    s = b(i)
    for j = i+1 to n
        s = s - A(i,j) * x(j)
    end
    x(i) = s / A(i,i)
end

Cost: $\mathcal{O}(n^2)$ FLOPS (Cheap!)

Gaussian Elimination

Our goal is to transform an arbitrary square system $Ax=b$ into an equivalent upper triangular system $Ux=c$, which we can then solve easily.

Hand Calculation Example

Original System

$x_1 + 3x_2 = 5$
$2x_1 + 4x_2 = 6$

➜

Elimination ($R_2 \leftarrow R_2 - 2R_1$)

$x_1 + 3x_2 = 5$
$0 - 2x_2 = -4$

Solve $x_2 = 2$, then substitute back to get $x_1 = -1$.

The "Cartoon" View

Visualizing how zeros propagate through the matrix.

[ x x x ]
[ x x x ]
[ x x x ]

Start

→

[ x x x ]
[ 0 x x ]
[ 0 x x ]

Col 1 Eliminated

→

[ x x x ]
[ 0 x x ]
[ 0 0 x ]

Col 2 Eliminated

The Algorithm & Cost

Forward Elimination Code

for k = 1 to n-1 % Pivot row
    for i = k+1 to n % Target row
        xmult = A(i,k) / A(k,k)
        A(i,k) = xmult % Store multiplier
        for j = k+1 to n % Columns
            A(i,j) = A(i,j) - xmult * A(k,j)
        end
        b(i) = b(i) - xmult * b(k)
    end
end

Computational Cost

Forward Elimination ~ 2/3 n³

Back Substitution ~ n²

Total Cost: $\mathcal{O}(n^3)$

Doubling $n$ increases cost by factor of 8.

Elementary Elimination Matrices

We can represent the row operations as matrix multiplications. To eliminate entries below the $k$-th diagonal, we use matrix $M_k$.

\[ M_k = I - m_k e_k^T = \begin{bmatrix} 1 & & & \\ & 1 & & \\ & -m_{k+1} & 1 & \\ & \vdots & & \ddots \end{bmatrix} \]

Where $m_i = a_i / a_k$ are the multipliers.

The Inverse: $L_k$

The inverse of an elimination matrix is incredibly simple. Just flip the sign of the multipliers!

$L_k = M_k^{-1} = I + m_k e_k^T$

LU Factorization

We transform $A$ to upper triangular $U$ by applying a sequence of matrices: \[ (M_{n-1} \dots M_2 M_1) A = U \]

Inverting the $M$'s moves them to the other side: \[ A = (M_1^{-1} M_2^{-1} \dots M_{n-1}^{-1}) U \]

The product of the inverses is a lower triangular matrix $L$. Thus:

$A = L U$

This factors matrix $A$ into a Lower triangular matrix $L$ and an Upper triangular matrix $U$.

Why "Naive"?

The algorithm described is called "Naive" because it assumes we can always divide by the pivot $A(k,k)$.

Zero Pivot

A = [ 0 2 3 ]
[ 4 5 6 ]
[ 7 8 9 ]

Division by zero error immediately!

Small Pivot

A = [ 1e-10 2 3 ]
[ 4 5 6 ]
[ 7 8 9 ]

Leads to massive roundoff error (Loss of Significance).

🧠 Final Challenge +20 XP

What is the structure of the matrix $M_k$ used to eliminate elements in the $k$-th column?

Gaussian Elimination

Solving Triangular Systems

Lower Triangular ($L$)

Upper Triangular ($U$)

Algorithm: Backward Substitution

Gaussian Elimination

Hand Calculation Example

The "Cartoon" View

The Algorithm & Cost

Forward Elimination Code

Computational Cost

Elementary Elimination Matrices

The Inverse: $L_k$

LU Factorization

Why "Naive"?

Zero Pivot

Small Pivot

🧠 Final Challenge +20 XP

Interactive Playground

MATLAB / Octave (Online)

Python (Client-Side)