Linear Algebra - Week 2#

Dive into the fundamentals of linear algebra for machine learning and data science. This week you’ll learn to solve equations using the elimination and substitution methods.

[1]:

import numpy as np

Solving a system of equations#

We can solve this system by elimination or substitution.

\(\begin{cases} 5a + b = 17 \\ 4a - 3b = 6 \end{cases}\)

Elimination method#

  1. \(\begin{cases} a + 0.2b = 3.4 \\ a - 0.75b = 1.5 \end{cases}\)

  2. \(\begin{cases} a + 0.2b = 3.4 \\ a - 0.75b = 1.5 \end{cases}\)

Eliminate \(a\)

  1. \(\begin{cases} a + 0.2b = 3.4 \\ 0 - 0.95b = -1.9 \end{cases}\)

  2. \(\begin{cases} a + 0.2b = 3.4 \\ b = 2. \end{cases}\)

  3. \(\begin{cases} a = 3. \\ b = 2. \end{cases}\)

Substitution method#

  1. \(\begin{cases} a + 0.2b = 3.4 \\ a - 0.75b = 1.5 \end{cases}\)

  2. \(\begin{cases} a = 3.4 - 0.2b \\ a = 1.5 + 0.75b \end{cases}\)

Substitute \(a\)

  1. \(\begin{cases} a = 3.4 - 0.2b \\ 3.4 - 0.2b - 1.5 - 0.75b = 0 \end{cases}\)

  2. \(\begin{cases} a = 3.4 - 0.2b \\ 1.9 - 0.95b = 0 \end{cases}\)

  3. \(\begin{cases} a = 3.4 - 0.2b \\ b = 2. \end{cases}\)

  4. \(\begin{cases} a = 3. \\ b = 2. \end{cases}\)

Let’s check the solution.

[2]:

a = 3.0
b = 2.0

assert 5.0 * a + b == 17.0
assert 4.0 * a - 3.0 * b == 6.0
assert np.allclose(
    np.linalg.solve(np.array([[5.0, 1.0], [4.0, -3.0]]), np.array([17.0, 6.0])),
    np.array([a, b]),
)

Let’s build an elimination algorithm using this system as an example.

\(\begin{cases} a + b + 2c = 12 \\ 3a - 3b - c = 2 \\ 2a - b + 6c = 24 \end{cases}\)

[3]:

a = np.array([[1, 1, 2], [3, -3, -1], [2, -1, 6]], dtype="float32")
b = np.array([12, 2, 24], dtype="float32")


def solve_by_elimination(a: np.array, b: np.array) -> np.array:
    c = np.hstack((a, b.reshape(-1, 1)))
    for i in range(c.shape[0] - 1):
        # normalize row i
        c[i:, :] /= c[i:, i].reshape(-1, 1)
        # remove row i from row i+1, i+2, etc...
        c = np.vstack((c[: i + 1, :], c[i + 1 :,] - c[i, :]))
    for i in range(c.shape[0] - 1, -1, -1):
        # bring solved (if any) to RHS
        c[i, -1] -= np.sum(c[i, (i + 1) : -1])
        c[i, (i + 1) : -1] = 0
        # divide whole row by coefficient of variable
        c[i, :] /= c[i, i]
        # replace solution across the system
        c[:i, i] *= c[i, -1]
    return c[:, -1]


solve_by_elimination(a, b)

[3]:

array([3.757576 , 2.0606058, 3.0909092], dtype=float32)

Let’s check the solution.

[4]:

assert np.allclose(solve_by_elimination(a, b), np.linalg.solve(a, b))

Let’s try it with another one.

[5]:

a = np.array(
    [[2, -1, 1, 1], [1, 2, -1, -1], [-1, 2, 2, 2], [1, -1, 2, 1]], dtype="float32"
)
b = np.array([6, 3, 14, 8], dtype="float32")
assert np.allclose(solve_by_elimination(a, b), np.linalg.solve(a, b))