Back to the on-screen lesson ·
Turning a square system into a triangular one and unwinding it, what the work costs as the system grows, and the division that decides whether the method finishes.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to carry out an elimination step and back substitution, state how the work grows with the size of the system, and say exactly which coefficient values make the method break down and why.
You can solve a small system by row reduction and you know what it means for a matrix to be singular. What is new here is counting the work, and watching what the arithmetic does to an answer that the algebra says exists.
The pivot is the diagonal entry a column is eliminated with; the multiplier is the entry below it divided by it. The system is upper triangular when everything below the diagonal is zero, and back substitution solves it from the last equation upwards. The augmented matrix carries the right-hand side as one more column.
Turn a square system into a triangular one, then unwind it. For each column in turn, take the pivot, form the multiplier $m_{ij} = \dfrac{a_{ij}}{a_{jj}}$ for every row below, and subtract $m_{ij}$ times the pivot row from row $i$ — the right-hand side included, because it is a column like any other. When the matrix is upper triangular, back substitution reads the unknowns off from the bottom: the last equation has one unknown, the next has one new one, and so on. Two things matter beyond the algebra you already know. The cost: each pivot touches a block one smaller than the last, and summing the squares gives about $\tfrac23 n^{3}$ operations — so doubling the size multiplies the work by eight, while back substitution costs only about $n^{2}$ and is free by comparison. And the breakdown: the method divides by each pivot, so a zero pivot stops it. That is the algebra reporting a singular system. A pivot that is merely small stops nothing and is the more dangerous case, because the run completes and the answer is dominated by whatever rounding error reached that division.
Another way: steps
Another way: example
$2x + y = 5$, $4x - y = 4$. Multiplier $\tfrac42 = 2$; the second row becomes $(0, -3)$ with right-hand side $4 - 10 = -6$, so $y = 2$, and then $2x = 5 - 2$ gives $x = \tfrac32$. Substituting into both originals checks it.
It is tempting to treat the right-hand side as something outside the matrix that is dealt with at the end. It is not: every row operation applies to it at the same moment it applies to the coefficients, and forgetting this is the commonest arithmetic error in the whole method. Keeping the augmented matrix as a single array, rather than a matrix and a vector, is what makes the omission impossible.
The first pivot updates an $(n-1) \times n$ block: about $n^{2}$ operations.
One pass over the block.
The next updates an $(n-2) \times (n-1)$ block, and so on.
A shrinking square each time.
$\sum_{k=1}^{n} k^{2} \approx \tfrac{n^{3}}{3}$, so the total is cubic.
Doubling $n$ costs eight times as much.
$0x + y = 1$, $x + y = 2$ has the perfectly good solution $(1, 1)$.
The matrix is invertible.
But the first pivot is $0$, and the method divides by it.
Elimination stops.
Swapping the two rows fixes it entirely. So a zero pivot means this row order fails, not that the system does.
Which is why row swaps are part of the method.
The multiplier is $\tfrac63 = 2$.
The second row becomes $(0, 1 - 4) = (0, -3)$ with right-hand side $8 - 14 = -6$.
So $y = 2$, and then $3x = 7 - 4$ gives $x = 1$.
The system is $x + 2y = 5$ and $2x + 0y = -2$. Eliminate $x$ from the second equation, and give the row that results.
| Coefficient of x | Coefficient of y | Right-hand side | |
|---|---|---|---|
| First row | 1 | 2 | 5 |
| Second row, before | 2 | 0 | -2 |
| Second row, after |
Gaussian elimination is run on a dense $126 \times 126$ system. How does the amount of arithmetic grow as the size of the system grows?
Solve $2x + 2y = -4$ and $4x - 5y = -17$, and give the solution as the row $(x, y)$.
This task has no paper form; do it on a device.
Put the five steps of solving an $7 \times 7$ system by elimination into order.
Number the steps in order (write the number in the box):
In the system $3x + 3y = e$ and $3x + dy = f$, the coefficient $d$ is left free. For which values of $d$ does the elimination produce a usable second equation? Give the set.
This task has no paper form; do it on a device.
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
After one elimination step the system $4x + 3y = 2$, $8x + 4y = 8$ has second equation $-2y = 4$. What is $y$?
Answer:
You can eliminate, back substitute and state the cost of the method. Say in your own words why doubling the size of a system multiplies the work by about eight.
8. Your turn: eliminate in $3x + 2y = 7$, $6x + y = 8$, step 3