Suppose \(m\) linear systems
$$A \mathbf{x}^{(p)}=\mathbf{b}^{(p)}, \quad p=1,2, \ldots, m$$
are to be solved, each with the \(n \times n\) coefficient matrix \(A\).
a. Show that Gaussian elimination with backward substitution applied to the
aug- mented matrix
$$\left[\begin{array}{ll}
A: & \mathbf{b}^{(1)} \mathbf{b}^{(2)} \cdots \mathbf{b}^{(m)}
\end{array}\right]$$
requires
$$\frac{1}{3} n^{3}+m n^{2}-\frac{1}{3} n \quad \text { multiplications/
divisions }$$
$$\frac{1}{3} n^{3}+m n^{2}-\frac{1}{2} n^{2}-m n+\frac{1}{6} n \quad \text {
additions/subtractions. }$$
b. Show that the Gauss-Jordan method (see Exercise 12 , Section \(6.1\) )
applied to the augmented matrix
$$\left[\begin{array}{ll}
A: & \left.{\mathbf{b}^{(1)} \mathbf{b}^{(2)}} \cdots \mathbf{b}^{(m)}\right]
\end{array}\right.$$
requires
$$\frac{1}{2} n^{3}+m n^{2}-\frac{1}{2} n \quad \text {
multiplications/divisions }$$
and
$$\frac{1}{2} n^{3}+(m-1) n^{2}+\left(\frac{1}{2}-m\right) n \quad \text {
additions/subtractions. }$$
c. For the special case
$$\mathbf{b}^{(p)}=\left[\begin{array}{c}
0 \\
\vdots \\
0 \\
1 \\
\vdots \\
0
\end{array}\right] \leftarrow p \text { th row }$$
for each \(p=1, \ldots, m\), with \(m=n\), the solution \(x^{(p)}\) is the \(p\) th
column of \(A^{-1}\). Show that Gaussian elimination with backward substitution
requires
\(\frac{4}{3} n^{3}-\frac{1}{3} n \quad\) multiplications/divisions
and
$$\frac{4}{3} n^{3}-\frac{3}{2} n^{2}+\frac{1}{6} n \quad \text {
additions/subtractions }$$
for this application, and that the Gauss-Jordan method requires
$$\frac{3}{2} n^{3}-\frac{1}{2} n \quad \text { multiplications/divisions }$$
and
$$\frac{3}{2} n^{3}-2 n^{2}+\frac{1}{2} n \quad \text {
additions/subtractions. }$$
d. Construct an algorithm using Gaussian elimination to find \(A^{-1}\), 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^{3}\) multiplications/divisions and \(n^{3}-2 n^{2}+n\)
additions/subtractions.
e. Show that solving the linear system \(A x=\mathbf{b}\), when \(A^{-1}\) is
known, still requires \(n^{2}\) multiplications/divisions and \(n^{2}-n\)
additions/subtractions.
f. Show that solving \(m\) linear systems \(A x^{(p)}=\mathbf{b}^{(p)}\), for
\(p=1,2, \ldots, m\), by the method \(x^{(p)}=\) \(A^{-1} \mathbf{b}(p)\) requires
\(m n^{2}\) multiplications and \(m\left(n^{2}-n\right)\) additions, if \(A^{-1}\)
is known.
g. Let \(\mathrm{A}\) be an \(n \times 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 \(A x=\mathbf{b}\) by \(A^{-1}\), for \(n=3,10,50,100 .\) Is it ever
advantageous to compute \(A^{-1}\) for the purpose of solving linear systems?
Explanations 
Textbooks 
Flashcards 
91影视 AI 
Notes 
Study Plans 
Study Sets 
Find a degree 
Magazine 
