3.3.3 Practice set: linear systems

Linear systems and elimination

Linear systems and Gaussian elimination (lesson 3.3.1)

0 of 8 correct

1.
The system $x_1 - 2x_2 = 3$ , $4x_1 + x_2 = 3$ is $A\mathbf{x} = \mathbf{b}$ . What is $a_{21}$ , the entry in row 2, column 1?
2.
Find $x_2$ in $x_1\begin{pmatrix} 1 \\ 1 \end{pmatrix} + x_2\begin{pmatrix} 2 \\ -1 \end{pmatrix} = \begin{pmatrix} 7 \\ 1 \end{pmatrix}$
3.
To clear the $-3$ below the pivot 6 in column 1, you subtract $m$ times the pivot row. What is $m$ ?
4.
Row 1 of $[A \mid \mathbf{b}]$ is $(1, 2 \mid 5)$ and row 2 is $(3, 4 \mid 11)$ . After $R_2 - 3R_1$ , what is the right-hand side of row 2?
5.
Finish that system: row 2 is now $(0, -2 \mid -4)$ . What is $x_1$ ?
6.
Solve $x_1 + x_2 + x_3 = 2$ , $2x_1 + 3x_2 + x_3 = 1$ , $x_1 - x_2 + 2x_3 = 6$ . What is $x_3$ ?
7.
Elimination leaves the rows $(1, 1, 2)$ , $(0, 0, 5)$ and $(0, 4, 1)$ . Row 2 must swap with which row? Give its number
8.
Partial pivoting on $\begin{pmatrix} 2 & 1 & 0 \\ -5 & 3 & 1 \\ 4 & 0 & 2 \end{pmatrix}$ : which row is swapped up for the first pivot? Give its number

How to type answers

Powers with ^: x^7, 2^(1/3), a^-2.
Multiply with * or by writing side by side: 3x^2, 2(x+1).
ln(x) is the natural log, log(x, 2) is log base 2, e is Euler's number, sqrt(x) is a square root.
sin(x), cos(x) and tan(x) take radians; write pi for π and sin(x)^2 for sin²x.
Your first answer to each question is saved: it counts towards your score and brings the question back for review.
Exact answers like ln(20)/ln(3) are best. Decimals need about 4 significant figures.

Rank and solution sets

Rank and the shape of the solution set (lesson 3.3.2)

0 of 9 correct

1.
How many solutions has $2x_1 - x_2 = 1$ , $-4x_1 + 2x_2 = 3$ ?
2.
What is the rank of $\begin{pmatrix} 1 & -1 & 2 \\ 2 & -2 & 4 \\ 0 & 1 & 1 \end{pmatrix}$ ?
3.
For that matrix, how many free variables has a consistent system $A\mathbf{x} = \mathbf{b}$ ?
4.
The solutions of $x_1 + 2x_2 - x_3 = 4$ , $x_3 = 1$ have $x_2$ free. With $x_2 = 2$ , what is $x_1$ ?
5.
For which $c$ does $x_1 + x_2 = 1$ , $2x_1 + 2x_2 = c$ have solutions?
6.
A tall system: $x_1 + x_2 = 4$ , $x_1 - x_2 = 2$ , $2x_1 + x_2 = c$ . For which $c$ is it consistent?
7.
A consistent system of 3 equations in 5 unknowns has rank 3. How many free variables does it have?
8.
What is the rank of $\begin{pmatrix} 2 & 4 \\ 3 & 6 \end{pmatrix}$ , whose two rows are both nonzero?
9.
$x_1 + x_2 = 2$ and $x_1 + 1.0001x_2 = 2.0001$ give $(1, 1)$ . Change 2.0001 to 2.0002. What is $x_2$ now?

How to type answers

Powers with ^: x^7, 2^(1/3), a^-2.
Multiply with * or by writing side by side: 3x^2, 2(x+1).
ln(x) is the natural log, log(x, 2) is log base 2, e is Euler's number, sqrt(x) is a square root.
sin(x), cos(x) and tan(x) take radians; write pi for π and sin(x)^2 for sin²x.
Your first answer to each question is saved: it counts towards your score and brings the question back for review.
Exact answers like ln(20)/ln(3) are best. Decimals need about 4 significant figures.

Coding exercise

Exercise

Gaussian elimination with partial pivoting

Write gauss_solve(A, b, tol=1e-12) that returns the solution of $A\mathbf{x} = \mathbf{b}$ as a NumPy array, by the method of lesson 3.3.1. Do not call np.linalg.solve; the tests compare your answer with it.

Turn A and b into decimal arrays first (np.asarray(…, dtype=float)), and work on a new augmented matrix, so the caller's arrays are left unchanged.
For each column, swap up the row whose entry is largest in size, at or below the diagonal. If that entry is at most tol times the largest entry of A in size, raise ValueError: the column has no pivot (lesson 3.3.2).
Clear the column below the pivot, then back-substitute from the bottom row.
If A is not square, with one row per entry of b, raise ValueError.

The tests use the examples of lessons 3.3.1 and 3.3.2. They include a zero pivot, a zero in the top-left corner, the tiny pivot $10^{-20}$ , a singular matrix and a tall one. They also try a random 6 × 6 system.

See the tests

import numpy as np


def test_three_by_three():
    """Integer arrays work: the 3 × 3 system of lesson 3.3.1 gives (2, −1, 3)"""
    A = np.array([[1, 2, 1], [2, 5, 3], [3, 4, 4]])
    b = np.array([3, 8, 14])
    expect_close(gauss_solve(A, b), [2, -1, 3], what="gauss_solve on the 3 × 3 example")


def test_zero_pivot():
    """A 0 in the second pivot place needs a row swap: the answer is (3, −1, 2)"""
    A = [[1, 2, 1], [2, 4, 3], [1, 3, 2]]
    expect_close(gauss_solve(A, [3, 8, 4]), [3, -1, 2], what="gauss_solve with a zero pivot")


def test_zero_corner():
    """A 0 in the top-left corner: x₂ = 2 and x₁ + x₂ = 3 give (1, 2)"""
    expect_close(gauss_solve([[0, 1], [1, 1]], [2, 3]), [1, 2], what="gauss_solve([[0, 1], [1, 1]], [2, 3])")


def test_tiny_pivot():
    """A tiny pivot needs partial pivoting: 10⁻²⁰x₁ + x₂ = 1 and x₁ + x₂ = 2 give (1, 1)"""
    x = gauss_solve([[1e-20, 1], [1, 1]], [1, 2])
    expect_close(x, [1, 1], what="gauss_solve with the pivot 1e-20 (swap up the largest entry in size)", rel=1e-12)


def test_one_by_one():
    """A 1 × 1 system, 4x = 2, gives 0.5"""
    expect_close(gauss_solve([[4]], [2]), [0.5], what="gauss_solve([[4]], [2])")


def test_random_system():
    """A random 6 × 6 system agrees with np.linalg.solve"""
    rng = np.random.default_rng(33)
    A = rng.normal(size=(6, 6))
    b = rng.normal(size=6)
    expect_close(gauss_solve(A, b), np.linalg.solve(A, b), what="gauss_solve on a random 6 × 6 system", rel=1e-9)


def test_inputs_unchanged():
    """The A and b passed in are left as they were"""
    A = np.array([[2.0, 1.0], [6.0, 5.0]])
    b = np.array([4.0, 18.0])
    x = gauss_solve(A, b)
    expect_close(x, [0.5, 3], what="gauss_solve on 2x₁ + x₂ = 4, 6x₁ + 5x₂ = 18")
    expect_close(A, [[2, 1], [6, 5]], what="A after the call")
    expect_close(b, [4, 18], what="b after the call")


def test_singular():
    """A singular matrix (rank 2, from lesson 3.3.2) raises ValueError"""
    try:
        gauss_solve([[1, 2, 1], [2, 4, 3], [3, 6, 4]], [4, 9, 13])
    except ValueError:
        return
    raise AssertionError("expected ValueError: column 2 has no pivot, so there is no single solution")


def test_not_square():
    """A 3 × 2 matrix raises ValueError"""
    try:
        gauss_solve([[1, 1], [1, -1], [1, 2]], [3, 1, 4])
    except ValueError:
        return
    raise AssertionError("expected ValueError for a matrix that is not square")

Linear systems and elimination

Rank and solution sets

Coding exercise

Free further reading