Linear Algebra and Its Applications, Exercise 1.5.10

Exercise 1.5.10. (a) Both Lc = b and Ux = c take approximately n^2/2 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

b = Lc \Rightarrow \begin{bmatrix} 1&&& \\ l_{21}&1&& \\ \vdots&\vdots&\ddots& \\ l_{n1}&l_{n2}&\cdots&1 \end{bmatrix} \begin{bmatrix} c_1 \\ c_2 \\ \vdots \\ c_n \end{bmatrix} = \begin{bmatrix} b_1 \\ b_2 \\ \vdots \\ b_n \end{bmatrix}

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

The total number of operations is then

1 + 2 + 3 + \cdots + n = n(n+1)/2 \approx n^2/2

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

Ux = c \Rightarrow \begin{bmatrix} u_{11}&u_{12}&\cdots&u_{1n} \\ &u_{22}&\cdots&u_{2n} \\ &&\ddots&\vdots \\ &&&u_{nn} \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \\ \vdots \\ x_n \end{bmatrix} = \begin{bmatrix} c_1 \\ c_2 \\ \vdots \\ c_n \end{bmatrix}

Here solving for x_n takes one step, solving for x_{n-1} two steps, and so on until solving for x_1 takes n steps. Again the total number of steps is n(n+1)/2 \approx n^2/2.

(b) As discussed on p. 15, doing elimination on an arbitrary n by n matrix takes approximately n^3/3 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 n^2/2 steps, and can then use Ux = c to solve for x, also in approximately n^2/2 steps, for a total of n^2 steps in all.

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

n^3/3 + 10n^2 = 60^3/3 + 10 \cdot 60^2= (60 \cdot 60^2)/3 + 10 \cdot 60^2
= 20 \cdot 60^2 + 10 \cdot 60^2 = 30 \cdot 60^2 = 30 \cdot 3,600 = 108,000

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.

This entry was posted in linear algebra. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s