LU Factorisation, Pivoting and the Cost of a Solve · seed 1 · A4, ink-friendly. The answer key prints on its own page for grown-ups.

Factor once, solve many times

Mathematics · Linear Algebra · ages 20-21
Name ______________________   Date ____________

  1. Forward substitution: L has ones on the diagonal and two below the diagonal. The right hand side is three then eleven. The first unknown is three, and twice it plus the second unknown is eleven. What is the second unknown?

    Answer: ______________

  2. A equal [[2, 1], [4, 3]] factors without pivoting as L times U. What is U?

    • [[1, 0], [2, 1]]
    • [[2, 1], [0, 1]]
    • [[2, 0], [4, 3]]
    • [[1, 2], [0, 1]]

  3. A with rows [2, 1] and [4, 3] factors without pivoting as L times U. What is U?

    • Rows [2, 1] and [0, 1]
    • Rows [1, 0] and [2, 1]
    • Rows [2, 0] and [4, 3]

  4. Partial pivoting is only needed when a pivot is exactly zero.

    Circle one:   True   False

  5. The leading cost of LU factorisation is n cubed over three operations. For n equal thirty, what is that cost?

    Answer: ______________

  6. Why pivot even when no pivot is exactly zero?

    • Pivoting speeds up the arithmetic
    • Tiny pivots inflate rounding error through large multipliers
    • Pivoting changes the solution vector

  7. With A equal L times U, which order solves A times x equal b?

    • Forward substitution on L, then back substitution on U
    • Back substitution on U, then forward substitution on L
    • Forward substitution on both factors
    • Invert A directly and multiply

  8. Once A is factored, each extra right hand side costs only order n squared operations. True or false?

    Circle one:   True   False

  9. Once A is factored, each extra right hand side costs only order n squared operations.

    Circle one:   True   False

  10. A equal [[0, 1], [1, 0]]. What happens if you eliminate without pivoting?

    • It factors cleanly with L equal the identity
    • U comes out singular
    • The first pivot is zero so elimination breaks at step one
    • The product L times U gives the identity matrix
LightMySky · lightmysky.comW1-mt_5Gg2v3Oxrr-s1

Answer key

For grown-ups. Fold this page away before handing over the rest.

Factor once, solve many times W1-mt_5Gg2v3Oxrr-s1

  1. 5 · Twice three is six, and eleven minus six is five.
  2. [[2, 1], [0, 1]] · Eliminate with multiplier 2: the second row becomes [0, 1], which is the bottom row of U.
  3. Rows [2, 1] and [0, 1] · Multiplier 2 clears the lower left, leaving bottom row [0, 1].
  4. False · Tiny pivots also inflate rounding through large multipliers.
  5. 9000 · Thirty cubed is 27000, divided by three is 9000.
  6. Tiny pivots inflate rounding error through large multipliers · Small pivots make huge multipliers that amplify rounding.
  7. Forward substitution on L, then back substitution on U · Set y equal U times x: first crack L times y equal b going forward, then U times x equal y going backward.
  8. True · True. Two triangular solves at n squared each beat a fresh factorisation.
  9. True · Two triangular solves cost about n squared, not n cubed.
  10. The first pivot is zero so elimination breaks at step one · The top left entry is zero, so the first multiplier needs division by zero.
Worksheet · LightMySky