LU decomposition: A = LU keeps a record of elimination
Slide 5 wrote elimination as E₃₂E₃₁E₂₁A = U, and slide 6 showed how such products work. Now we run it backwards. Keep every multiplier ℓ from elimination in a lower triangular matrix L: 1s on the diagonal, the multipliers below it, zeros above. Then L times U gives A back: A = LU. Think of meal prep. Chop the week's vegetables on Sunday, and every dinner is quick. Factoring A = LU is the Sunday work, and each new right side b is a quick dinner: two easy triangle solves.
Lesson 2 · slide 7A = LU- A = LU: L is lower triangular with 1s on its diagonal, U is upper triangular.
- The multipliers ℓᵢⱼ go straight into L, in the positions where they were used.
- To solve Ax = b: first solve Lc = b, then Ux = c. Both are fast triangular solves.
- Factor once, then reuse L and U for every new right-hand side b.
Solving with L and U
Why two solves? Replace A by LU: (LU)x = b, and the brackets can move (slide 6): L(Ux) = b. Call Ux = c. Solve Lc = b for c, then Ux = c for x.
This is slide 3's c: b after elimination. Solving Lc = b top-down (forward substitution) just redoes those subtractions on b. Row 2 of L reads ℓ₂₁c₁ + c₂ = b₂, so with b = 5−29 from slide 3, c₂ = b₂ − ℓ₂₁c₁ = −2 − 2·5 = −12, as on slide 3. The example “Solve Lc = b by forward substitution” below finishes c₃.
Where L comes from
Slide 5 wrote elimination as E₃₂E₃₁E₂₁A = U. To get A back, undo the steps in reverse order, on both sides. To undo E₃₂, multiply both sides on the left by E₃₂⁻¹. Since E₃₂⁻¹E₃₂ = I, E₃₂ cancels. Then the same for E₃₁, then E₂₁:
Shoes come off before socks: the last step done is the first undone. So E₃₂⁻¹ sits next to U.
Each inverse is the identity with +ℓ where E had −ℓ (slide 5). In this order the multipliers don't mix: no new entries appear, and each multiplier just sits in its own spot, as the product below shows. So L needs no extra arithmetic: it is the record of the multipliers.
The example from slides 3 to 5
You can watch both triangles grow at the same time. Start with L = I and U = A. Each elimination step changes one row of U, and its multiplier drops into the same spot of L.
Why it saves time
For n unknowns, factoring takes about n³/3 multiplications, and both triangular solves together about n². With n = 1000: roughly 330 million operations to factor, then about a million per new b.
So when only the right side changes, as in a simulation stepping through time, factor once and reuse L and U. In the lab, lu(A) returns both factors so you can check your work.
A bigger example: 4 × 4
Each row of A only touches its neighbours, so L and U stay just as thin. Matrices like this come up in simulations with thousands of unknowns, and the thin L and U make every new solve very fast.
Next: The recap puts the whole lesson on one page.
Examples
Example 1 · Factor, then solve
A = 1238, b = 519.
Show solutionHide solution
Example 2 · A 3 by 3 factorization
A = 111122123 (from slide 3's example “A full 3 by 3 solve”).
Show solutionHide solution
Each multiplier was 1, so L has 1s everywhere below the diagonal.
Example 3 · A fractional multiplier
A = 4363.
Show solutionHide solution
Example 4
Solve Lc = b by forward substitution: L = 100210−1−11, b = 5−29.
Show solutionHide solution
c₁ = 5. Then 2·5 + c₂ = −2, so c₂ = −12. Then −5 + 12 + c₃ = 9, so c₃ = 2. c = 5−122, the same c as on slide 3.
Example 5
Why does A = 0111 have no LU factorization? How is it fixed?
Show solutionHide solution
The first pivot is 0, so no multiplier can be formed. Swap the rows first. Lesson 3 writes this swap as a matrix P: P is I with its rows swapped, and it does the row exchange first. Here PA = 1101 is already upper triangular, so PA = LU with L = I.
Questions and comments
Stuck on something, or found a mistake? Ask here and I'll answer. You sign in with GitHub.