Solving systems of linear equations

A system of linear equations asks for numbers that satisfy several equations at once:

2x + y − z = 8, −3x − y + 2z = −11, −2x + y + 2z = −3

Rows of numbers

Write each equation as a row of its coefficients and right side: [2, 1, −1, 8]. Three allowed moves never change the solution:

1. Swap two rows.
2. Multiply a row by a non-zero number.
3. Add a multiple of one row to another.

Gaussian elimination

Go column by column. Pick a row with a non-zero entry in that column (the pivot) and use move 3 to make every other entry in the column zero. At the end each row says "this variable = this number".

from fractions import Fraction

rows = [[2, 1, -1, 8],
        [-3, -1, 2, -11],
        [-2, 1, 2, -3]]
rows = [[Fraction(v) for v in row] for row in rows]
n = 3
for col in range(n):
    pivot = next(r for r in range(col, n) if rows[r][col] != 0)
    rows[col], rows[pivot] = rows[pivot], rows[col]
    top = rows[col]
    for r in range(n):
        if r != col:
            factor = rows[r][col] / top[col]
            rows[r] = [a - factor * b for a, b in zip(rows[r], top)]
for r in range(n):
    print("xyz"[r], "=", rows[r][n] / rows[r][r])

The example keeps every number as a Fraction, so there is no rounding: the answer is exactly x = 2, y = 3, z = −1. In the memory panel, watch the rows change after each step.

Three possible outcomes

• One solution: every column finds a pivot.
• No solution: elimination produces a row like 0 = 5. (x + y = 1 and x + y = 2 can't both hold.)
• Infinitely many: a row becomes 0 = 0 and a variable is free to be anything.

Where it is used

Circuit currents, balancing chemical equations, fitting curves to data (least squares) and 3-D graphics all come down to solving linear systems. NumPy's numpy.linalg.solve does this with floats for thousands of unknowns.

Common mistakes

• Dividing by a zero pivot. If the entry is zero, swap in a lower row that has a non-zero entry first.

Mark lesson complete