Exercise 1.5.10. (a) Both Lc = b and Ux = c take approximately multiplication-substraction steps to solve. Explain why.

(b) Assume A is a 60 by 60 coefficient matrix. How many steps are required to use elimination to solve ten systems involving A?

Answer: (a) L is lower triangular, so we have

The first entry can be found in a single operation, while solving for takes two operations, solving for three operations, and so on until solving for takes n operations.

The total number of operations is then

We have a similar situation with Ux = c, since U is upper triangular:

Here solving for takes one step, solving for two steps, and so on until solving for takes n steps. Again the total number of steps is .

(b) As discussed on p. 15, doing elimination on an arbitrary n by n matrix takes approximately steps for large n. As a result of performing elimination on A we obtain its two factors L and U. Given the particular system Ax = b we can use Lc = b to solve for c in approximately steps, and can then use Ux = c to solve for x, also in approximately steps, for a total of steps in all.

For ten systems with the same 60 by 60 matrix the total number of steps is then approximately

NOTE: This continues a series of posts containing worked out exercises from the (out of print) book Linear Algebra and Its Applications, Third Edition by Gilbert Strang.

If you find these posts useful I encourage you to also check out the more current Linear Algebra and Its Applications, Fourth Edition, Dr Strang’s introductory textbook Introduction to Linear Algebra, Fourth Edition and the accompanying free online course, and Dr Strang’s other books.