Home / Courses / Numerical Methods / Linear Systems

Numerical Methods · Module 4 of 10

Systems of Linear Equations

Linear systems appear everywhere a problem is discretised: trusses, circuits, finite elements. Gauss elimination reduces the system to a triangle you can back-substitute, and LU decomposition reuses that work for many right-hand sides.

01

Readiness check

This module solves linear systems. Tick only what you can do closed-notes.

  • Write a system of equations in matrix form Ax = b.
  • Add a multiple of one equation to another.
  • Solve a triangular system by substitution.
  • Multiply two small matrices.
  • Recall that a zero pivot blocks elimination.
0 or 1 weak itemsContinue with this module.
2 weak itemsRefresh matrices and systems in Mathematics, Module 8.
3 or more weak itemsReview iteration habits in Module 3.
02

The core idea

Gauss elimination turns Ax = b into an upper-triangular system by row operations, then back substitution solves it from the bottom up. LU decomposition stores that elimination so many right-hand sides can be solved cheaply.

A x = beliminate → U x = b′, back-substituteA = L U, solve L y = b then U x = y

A system of linear equations is written Ax = b, with the coefficients in the matrix A, the unknowns in x, and the right-hand sides in b. Gauss elimination is the direct method: using elementary row operations, it eliminates the unknowns below each pivot to leave an upper-triangular system, which back substitution then solves from the last equation upward. If a pivot is zero or small, partial pivoting swaps in the largest available coefficient to keep the arithmetic stable. LU decomposition factors A into a lower-triangular L and an upper-triangular U that record the same elimination; once factored, any new right-hand side is solved by a forward substitution Ly = b followed by a back substitution Ux = y, far cheaper than repeating the full elimination. This reuse is why LU underlies the solvers in structural and thermal analysis.

The skill works when: you eliminate to a triangle, pivot when needed, and back-substitute carefully.
The skill breaks down when: a small pivot is kept without pivoting, or back substitution runs in the wrong direction.
The concept. Elimination reduces the full matrix to a triangle that back substitution solves. Factoring A into L and U stores that work, so new right-hand sides cost only two substitutions.
03

The skills, taught in order

Five skills build from the matrix form to Gauss elimination, pivoting, and LU decomposition.

4.1 The matrix form

A linear system is collected as Ax = b. Writing it this way separates the structure (A) from the loading (b) and exposes the system to matrix methods. Most discretised engineering problems arrive in exactly this form.

4.2 Gauss elimination

Forward elimination subtracts multiples of each pivot row from the rows below to zero out the coefficients beneath the pivot, reducing A to upper-triangular form U. The same operations are applied to b. The work scales as the cube of the system size.

4.3 Back substitution

With an upper-triangular system, the last equation gives the last unknown directly; substituting upward gives each remaining unknown in turn. Back substitution is the cheap second half of the solve.

StepProducesCost
Forward eliminationupper-triangular Uorder n3
Back substitutionthe solution xorder n2
LU then substitutex for a new border n2

The factorisation costs the same as one elimination, but each later right-hand side then costs only the cheap substitution.

4.4 Partial pivoting

A zero pivot stops elimination, and a small one amplifies roundoff. Partial pivoting swaps the current row with the one below having the largest pivot magnitude, keeping the multipliers below one and the arithmetic stable. It is almost always used in practice.

4.5 LU decomposition

LU decomposition writes A = LU, with L holding the elimination multipliers and U the resulting triangle. Solving Ax = b becomes Ly = b (forward) then Ux = y (back). The factorisation is done once; every new right-hand side reuses it, the key economy for repeated solves.

Engineering connection: a finite-element stiffness matrix is factored once, then solved against many load cases, exactly the LU economy.

04

Worked example 1: Gauss elimination of a 3 by 3 system

Solve the system x + y + z = 6, 2x − y + z = 3, x + 2y − z = 2 by Gauss elimination and back substitution.

Figure 1. Forward elimination clears the first column, then the second, leaving a triangular system. Back substitution recovers z, then y, then x.
  1. ProblemSolve the 3 by 3 system in Figure 1 for x, y, z.
  2. Given / findx + y + z = 6; 2x − y + z = 3; x + 2y − z = 2. Find x, y, z.
  3. AssumptionsThe system is nonsingular; pivots are nonzero, so no row swaps are needed.
  4. ModelEliminate below the first pivot, then the second, to reach a triangle, then back-substitute.
  5. EquationsR2 ← R2 − 2R1, R3 ← R3 − R1then eliminate column 2, back-substitute
  6. SolveAfter R2 − 2R1: −3y − z = −9. After R3 − R1: y − 2z = −4. Eliminate y: R3 + (1/3)R2 gives −2z − z/3 = −4 − 3, so −(7/3)z = −7, z = 3. Then −3y − 3 = −9 gives y = 2, and x + 2 + 3 = 6 gives x = 1.
  7. CheckSubstitute into all three: 1 + 2 + 3 = 6 ✓; 2 − 2 + 3 = 3 ✓; 1 + 4 − 3 = 2 ✓.
  8. ConclusionElimination plus back substitution gives the exact solution (1, 2, 3). The method is direct: a fixed amount of work, no iteration.
Result. x = 1, y = 2, z = 3.
05

Worked example 2: LU decomposition and solve

Factor A = [[3, 1], [1, 2]] into L and U, then use the factorisation to solve Ax = b for b = [9, 8].

Figure 2. The single elimination multiplier 1/3 fills L, and the resulting triangle is U. Forward then back substitution against b = [9, 8] gives the solution.
  1. ProblemFactor A and solve Ax = b for b = [9, 8], as in Figure 2.
  2. Given / findA = [[3, 1], [1, 2]], b = [9, 8]. Find L, U, and x.
  3. AssumptionsThe pivot 3 is nonzero, so no pivoting is needed.
  4. ModelThe multiplier ℓ21 = a21/a11 fills L; U is the eliminated matrix; solve Ly = b then Ux = y.
  5. Equationsℓ21 = 1/3, u22 = 2 − (1/3)(1) = 5/3L y = b, U x = y
  6. SolveL = [[1, 0], [1/3, 1]], U = [[3, 1], [0, 5/3]]. Forward: y1 = 9, y2 = 8 − (1/3)(9) = 5. Back: x2 = 5/(5/3) = 3, x1 = (9 − 1·3)/3 = 2.
  7. CheckLU = [[3, 1], [1, 2]] reproduces A, and Ax = [3·2 + 3, 2 + 6] = [9, 8] = b.
  8. ConclusionThe factorisation solves the system, and a different b would reuse the same L and U, needing only the two cheap substitutions.
Result. L = [[1, 0], [1/3, 1]], U = [[3, 1], [0, 5/3]]; x = 2, y = 3.
06

Misconceptions and diagnostics

MistakeSymptomDiagnostic questionCorrection
Small pivot keptRoundoff swamps the solution"Is the pivot the largest available?"Use partial pivoting to bring up the biggest coefficient.
Back substitution directionUnknowns solved top-down"Did I start from the last equation?"Back-substitute from the bottom row upward.
Refactoring for each bRepeated full eliminations"Did I reuse L and U?"Factor once, then substitute for each new b.
Singular matrix unnoticedA zero pivot with no swap available"Does a unique solution exist?"A zero column means the system is singular.
07

Practice ladder

Level 1 · Direct skill

Solve 2x + y = 5, x − y = 1 by elimination.

Show answer

Add the two equations to eliminate y: 3x = 6, so x = 2. Then x − y = 1 gives y = 1. Check: 2(2) + 1 = 5 ✓.

Level 2 · Mixed concept

For A = [[4, 3], [2, 3]], find the elimination multiplier and U.

Show answer

ℓ21 = 2/4 = 0.5. U = [[4, 3], [0, 3 − 0.5·3]] = [[4, 3], [0, 1.5]].

Level 3 · Independent problem

Using the L and U from Worked Example 2, solve Ax = b for a new b = [6, 7].

Show answer

Forward: y1 = 6, y2 = 7 − (1/3)(6) = 5. Back: x2 = 5/(5/3) = 3, x1 = (6 − 3)/3 = 1. So x = 1, y = 3.

Transfer task | Real engineering

A structure must be analysed under twenty load cases with the same stiffness matrix. Explain why LU decomposition is the right tool and what it saves.

What good work looks like

The matrix is factored once at order n3 cost, then each of the twenty loads is solved with cheap order-n2 substitutions, instead of twenty full eliminations, a large saving that grows with system size.

08

Working with AI, and proving it yourself

Use AI as an examiner, not a solver

"Check that my LU product reproduces the original matrix."
"Give me three systems; I will reduce each to triangular form."
"Solve this system for me." Performing the elimination is the skill.
"Do I need pivoting?" Judging the pivot sizes yourself is the point.

Portfolio task

Solve a real linear system by Gauss elimination, verify the solution by substitution, then factor the matrix as LU and reuse it for a second right-hand side.

Must include: an elimination, a verified solution, and an LU reuse for a new b.
09

Retrieval and spaced review

Closed notes. Answer out loud, then reveal.

1. What does forward elimination produce?

An upper-triangular system U from the coefficient matrix A.

2. In what order does back substitution solve?

From the last equation upward, last unknown first.

3. Why use partial pivoting?

To avoid zero or small pivots that block elimination or amplify roundoff.

4. What does LU decomposition store?

The elimination: L holds the multipliers, U the resulting triangle.

5. How is a new right-hand side solved with LU?

Forward-substitute Ly = b, then back-substitute Ux = y.

TodayFinish this quiz and Levels 1 and 2 of the ladder.
+1 dayRe-solve the 3 by 3 system from a blank page.
+3 daysFactor and solve three new systems.
+7 daysSolve large systems iteratively, Module 5.
+30 daysReuse LU when solving a stiffness matrix against many loads.
10

Textbook mapping

This module follows Chapra and Canale, Numerical Methods for Engineers, 7th edition. Use these references to read further.

Topic in this moduleWhere to read more
Gauss elimination and back substitutionChapra & Canale, Chapter 9
Partial pivotingChapra & Canale, Chapter 9
LU decompositionChapra & Canale, Chapter 10

Chapter numbers refer to the 7th edition. The elimination methods are standard, so any recent edition will align closely.