Suppose m linear systems Ax(p) = b(p) , p = 1, 2, ... , m, are to be solved, each with

Chapter 6, Problem 12

(choose chapter or problem)

Suppose m linear systems Ax(p) = b(p) , p = 1, 2, ... , m, are to be solved, each with the n n coefficient matrix A. a. Show that Gaussian elimination with backward substitution applied to the aug- mented matrix [A : b(1) b(2) b(m) ] requires 1 3 n3 + mn2 1 3 n multiplications/ divisions and 1 3 n3 + mn2 1 2 n2 mn + 1 6 n additions/subtractions. b. Show that the Gauss-Jordan method (see Exercise 12, Section 6.1) applied to the augmented matrix [A : b(1) b(2) b(m) ] requires 1 2 n3 + mn2 1 2 n multiplications/divisions and 1 2 n3 + (m 1)n2 + 1 2 m ! n additions/subtractions. c. For the special case b(p) = 0 . . . 0 1 . . . 0 pth row, for each p = 1, ... , m, with m = n, the solution x(p) is the pth column of A1. Show that Gaussian elimination with backward substitution requires 4 3 n3 1 3 n multiplications/divisions and 4 3 n3 3 2 n2 + 1 6 n additions/subtractions for this application, and that the Gauss-Jordan method requires 3 2 n3 1 2 n multiplications/divisions and 3 2 n3 2n2 + 1 2 n additions/subtractions. d. Construct an algorithm using Gaussian elimination to find A1, but do not per- form multiplications when one of the multipliers is known to be 1, and do not per- form additions/subtractions when one of the elements involved is known to be 0. Show that the required computations are reduced to n3 multiplications/divisions and n3 2n2 + n additions/subtractions. e. Show that solving the linear system Ax = b, when A1 is known, still requires n2 multiplications/divisions and n2 n additions/subtractions. f. Show that solving m linear systems Ax(p) = b(p) , for p = 1, 2, ... , m, by the method x(p) = A1b(p) requires mn2 multiplications and m(n2 n) additions, if A1 is known. g. Let A be an n n matrix. Compare the number of operations required to solve n linear systems involving A by Gaussian elimination with backward substitution and by first inverting A and then multiplying Ax = b by A1, for n = 3, 10, 50, 100. Is it ever advantageous to compute A1 for the purpose of solving linear systems?