8. An upper-triangular linear system has the form a11 a12 a13 a14 21 0 0221 023...

 

Transcribed Image Text:

8. An upper-triangular linear system has the form a11 a12 a13 a14 21 0 0221 023 a24 22 b 0 0 0 033 034 00 23 b3 044 ba for example, in the case of a 4 x 4 system. Such systems are easily solved by back substitution (solve the last equation for 4, then the previous equation for x3, etc.) How many multiplication operations does this require? (Count a division the same as a multipli- cation, so computing x4 =b4/044 takes 1 "multiply", for example.) Exactly how many "multiplies" does it take to solve a general n x n upper-triangular system? In particular, how many to solve an upper-triangular system of 1000 equations? 8. An upper-triangular linear system has the form a11 a12 a13 a14 21 0 0221 023 a24 22 b 0 0 0 033 034 00 23 b3 044 ba for example, in the case of a 4 x 4 system. Such systems are easily solved by back substitution (solve the last equation for 4, then the previous equation for x3, etc.) How many multiplication operations does this require? (Count a division the same as a multipli- cation, so computing x4 =b4/044 takes 1 "multiply", for example.) Exactly how many "multiplies" does it take to solve a general n x n upper-triangular system? In particular, how many to solve an upper-triangular system of 1000 equations?