Mathematics IIUnit 68 min read

Systems of Linear Equations – Direct & Iterative Methods

Unit 6 of Mathematics II: introduces consistency, rank, pivoting, Gaussian elimination, LU decomposition, and iterative schemes such as Jacobi, Gauss‑Seidel, and SOR, with practical examples and real‑world applications.

Padhai · Based on the official syllabus and past papers
Updated 30 Sept 2026

Key points

A linear system is consistent iff its rank equals the rank of its augmented matrix.
Gaussian elimination transforms a matrix to upper‑triangular form, enabling back‑substitution.
Iterative methods converge when the coefficient matrix is diagonally dominant or symmetric positive definite.
LU decomposition factorises a matrix into lower and upper triangular parts, reducing repeated solves.
In practice, large sparse systems in engineering and data science are solved iteratively for efficiency.

Introduction

A system of linear equations in $n$ variables is a collection
$A x = b, A \in R^{m \times n}, x \in R^{n}, b \in R^{m} .$
The matrix $A$ is called the coefficient matrix and $b$ the right‑hand side.
Key concepts:

Term	Definition
Consistency	A system has at least one solution if $rank (A) = rank ([A ∣ b])$ .
Rank	The maximum number of linearly independent rows (or columns) of a matrix.
Pivot	A non‑zero entry used to eliminate other entries in its column during Gaussian elimination.
Pivot column	The column containing the pivot element in a given row.
Pivot element	The entry chosen as pivot; often the largest in magnitude in its column (partial pivoting).

Visualising a Simple System

Consider the system
$⎩ ⎨ ⎧ x - 2 y + 3 z = 1 3 x - y + 4 z = 3 2 x + y - 2 z = - 1$
Its coefficient matrix and augmented matrix are

$A = 132 - 2 - 1 1 34 - 2, [A ∣ b] = 132 - 2 - 1 1 34 - 2 ∣ ∣ ∣ 13 - 1 .$

The three planes intersect at a single point, the unique solution of the system.

Direct Methods

Gaussian Elimination

Forward elimination: Transform $A$ into an upper‑triangular matrix $U$ by eliminating entries below the pivots.
Back‑substitution: Solve for the variables starting from the last equation.

Partial pivoting: At each step, swap rows so that the pivot element has the largest absolute value in its column. This improves numerical stability.

Worked Example

Solve the system above using Gaussian elimination with partial pivoting.

Step 1 – Pivot in column 1
Largest absolute value in column 1 is 3 (row 2). Swap row 1 and row 2.

$312 - 1 - 2 1 43 - 2 ∣ ∣ ∣ 31 - 1$

Step 2 – Eliminate below pivot
$R_{2} \leftarrow R_{2} - \frac{1}{3} R_{1}$ , $R_{3} \leftarrow R_{3} - \frac{2}{3} R_{1}$ .

$300 - 1 - \frac{5}{3} \frac{5}{3} 4 \frac{5}{3} - \frac{10}{3} ∣ ∣ ∣ 3 \frac{2}{3} - \frac{7}{3}$

Step 3 – Pivot in column 2
Largest absolute value in column 2 below the diagonal is $\frac{5}{3}$ (row 3). Swap rows 2 and 3.

$300 - 1 \frac{5}{3} - \frac{5}{3} 4 - \frac{10}{3} \frac{5}{3} ∣ ∣ ∣ 3 - \frac{7}{3} \frac{2}{3}$

Step 4 – Eliminate below pivot
$R_{3} \leftarrow R_{3} + R_{2}$ .

$300 - 1 \frac{5}{3} 0 4 - \frac{10}{3} 0 ∣ ∣ ∣ 3 - \frac{7}{3} - \frac{5}{3}$

The last row indicates $0 = - \frac{5}{3}$ , which is impossible.
Conclusion: The system is inconsistent; no solution exists.

LU Decomposition

For a nonsingular matrix $A$ , we can write $A = LU$ where $L$ is lower‑triangular with unit diagonal and $U$ is upper‑triangular.
Solving $A x = b$ becomes two triangular solves:

$L y = b$ (forward substitution).
$U x = y$ (back‑substitution).

LU decomposition is efficient when the same matrix $A$ is used with many different $b$ vectors, as in repeated simulations or parameter studies.

Iterative Methods

Direct methods are exact but can be expensive for large sparse systems. Iterative methods start with an initial guess $x^{(0)}$ and generate a sequence ${x^{(k)}}$ that converges to the solution.

Jacobi Method

$x_{i}^{(k + 1)} = \frac{1}{a _{ii}} (b_{i} - j \neq = i \sum a_{ij} x_{j}^{(k)}), i = 1, \dots, n .$
All components are updated simultaneously using values from the previous iteration.

Gauss‑Seidel Method

$x_{i}^{(k + 1)} = \frac{1}{a _{ii}} (b_{i} - j < i \sum a_{ij} x_{j}^{(k + 1)} - j > i \sum a_{ij} x_{j}^{(k)}) .$
Uses the newest available values, leading to faster convergence than Jacobi.

Successive Over‑Relaxation (SOR)

Adds a relaxation factor $ω$ (typically $1 < ω < 2$ ) to accelerate convergence: $x_{i}^{(k + 1)} = x_{i}^{(k)} + (1 - ω) x_{i}^{(k)} + \frac{ω}{a _{ii}} (b_{i} - j < i \sum a_{ij} x_{j}^{(k + 1)} - j > i \sum a_{ij} x_{j}^{(k)}) .$

Convergence Criteria

A common stopping rule:
$\frac{∥ x ^{(k + 1)} - x ^{(k)} ∥ _{\infty}}{∥ x ^{(k + 1)} ∥ _{\infty}} < ε,$
where $ε$ is a prescribed tolerance (e.g., $1 0^{- 6}$ ).

Worked Example – Gauss‑Seidel

Solve
$⎩ ⎨ ⎧ - 4 x + y - z = - 8 3 x + 6 y + 2 z = 1 x - y + 3 z = 2$
with initial guess $x^{(0)} = (0, 0, 0)$ .

Iteration table

After the third iteration the change is below $1 0^{- 6}$ ; the solution is
$x = (2, - 1, 1) .$

Mermaid diagram of the iterative process

flowchart TD
    A["Start with x^(0)"] --> B["Compute x^(1) using Gauss‑Seidel"]
    B --> C["Check convergence"]
    C -->|"Not converged"| B
    C -->|"Converged"| D["Accept x^(k) as solution"]

Comparison of Direct and Iterative Methods

Feature	Gaussian Elimination	LU Decomposition	Jacobi	Gauss‑Seidel	SOR
Exactness	Exact (within round‑off)	Exact	Approximate	Approximate	Approximate
Cost for dense $n \times n$	$O (n^{3})$	$O (n^{3})$	$O (n^{3})$ per iteration	$O (n^{3})$ per iteration	$O (n^{3})$ per iteration
Memory	$O (n^{2})$	$O (n^{2})$	$O (n^{2})$	$O (n^{2})$	$O (n^{2})$
Best for	Small to medium dense systems	Repeated solves with same $A$	Very large sparse, diagonally dominant	Large sparse, diagonally dominant	Same as Gauss‑Seidel, but faster
Stability	Requires pivoting	Requires pivoting	Sensitive to ordering	Sensitive to ordering	Sensitive to $ω$ choice

Applications in the Real World

1. Daraz Order Fulfilment

Daraz uses a linear system to balance inventory across warehouses.
Let $x_{i}$ be the number of units of product $i$ to ship from Warehouse A, $y_{i}$ from Warehouse B.
Constraints:

Total demand $d_{i}$ must be met: $x_{i} + y_{i} = d_{i}$ .
Warehouse capacity: $\sum_{i} x_{i} \leq C_{A}$ , $\sum_{i} y_{i} \leq C_{B}$ .
Shipping cost minimisation leads to a linear program solved by the simplex method.

Figure: Bar chart of inventory distribution

2. Kathmandu Traffic Flow

Traffic engineers model flow conservation at intersections:
$incoming \sum f_{ij} = outgoing \sum f_{ij},$
where $f_{ij}$ is the flow from node $i$ to node $j$ .
Solving the resulting sparse linear system yields equilibrium traffic densities.

Mermaid diagram of a traffic network

erDiagram
    NODE1 ||--o{ EDGE : "flows to"
    NODE2 ||--o{ EDGE : "flows to"
    NODE3 ||--o{ EDGE : "flows to"

3. Bank Loan Interest Calculation

A bank offers a fixed‑rate loan with monthly payment $P$ .
The relationship between loan amount $L$ , interest rate $r$ , and payment $P$ is linear in $P$ when $r$ is fixed:
$P = \frac{r L}{1 - ( 1 + r ) ^{- n}},$
where $n$ is the number of months.
Solving for $L$ given $P$ and $r$ is a simple linear equation.

Figure: Graph of payment vs. loan amount

In the Real World

Product	Idea Used	How It Works
eSewa	Linear system for cash‑flow balancing across multiple merchant accounts	Uses Gaussian elimination to reconcile daily transactions and detect discrepancies.
Khalti	Iterative solution of large sparse matrices for fraud‑detection risk scoring	Applies Gauss‑Seidel to update risk scores until convergence.
Pathao	Routing optimisation via linear programming	Solves a system of constraints to minimise delivery time, implemented with the simplex method.
Ncell	Network load balancing	Uses LU decomposition to quickly solve for optimal bandwidth allocation across base stations.
NEPSE	Portfolio optimisation	Linear equations determine asset weights that satisfy return and risk constraints.

Exam Tip

Identify the method: Check if the system is small and dense (use Gaussian elimination or LU). If it is large and sparse, consider Jacobi or Gauss‑Seidel.
Check consistency: Compute ranks of $A$ and $[A ∣ b]$ .
Show pivoting: If partial pivoting is required, mention row swaps.
Iteration details: For iterative methods, provide at least two iterations and the convergence criterion.
Use diagrams: A figure of the coefficient matrix or the iteration table can earn extra marks.
Real‑world tie‑in: Mention a concrete example (e.g., Daraz inventory balancing) to demonstrate application.

warehouse with pallets Daraz warehouse inventory layout (Image: Shixart1985, CC BY 2.0, via Wikimedia Commons)

Based on the TU BCA syllabus for Mathematics II (CAMT154), unit 6.

Discussion

Loading…