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 augmented matrix [A : b⁽¹⁾b⁽²⁾ · · · b^(m)]

Requires

1/3 n³ + mn² – 1/3 n multiplications/ divisions And 1/3 n³ + mn² – 1/2 n² − 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⁽¹⁾b⁽²⁾ · · · b^(m)]

Requires

1/2 n³ + mn² – 1/2 n multiplications/divisions And 1/2 n³ + (m − 1)n² + (1/2− m) n additions/subtractions.

c. For the special case

For each p = 1, . . . ,m, with m = n, the solution x(p) is the pth column of A⁻¹. Show that Gaussian elimination with backward substitution requires 4/3 n³ – 1/3 n multiplications/divisions and 4/3 n³ – 3/2 n² + 1/6 n additions/subtractions for this application, and that the Gauss-Jordan method requires 3/2 n³ – 1/2 n multiplications/divisions and 3/2 n³ − 2n² + 1/2 n additions/subtractions.

d. Construct an algorithm using Gaussian elimination to find A⁻¹, 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 n³ multiplications/divisions and n³ − 2n² + n additions/subtractions.

e. Show that solving the linear system Ax = b, when A⁻¹ is known, still requires n² multiplications/divisions and n² − n additions/subtractions.

f. Show that solving m linear systems Ax^(p) = b^(p), for p = 1, 2, . . . ,m, by the method x^(p) = A⁻¹b^(p) requires mn² multiplications and m(n² − n) additions, if A⁻¹ is known.

Transcribed Image Text:

-pth row, 1