91Ó°ÊÓ

Determine which of the following matrices are (i) symmetric, (ii) singular, (iii) strictly diagonally dominant, (iv) positive definite. a. \(\left[\begin{array}{rr}-2 & 1 \\ 1 & -3\end{array}\right]\) b. \(\left[\begin{array}{lll}2 & 1 & 0 \\ 0 & 3 & 2 \\ 1 & 2 & 4\end{array}\right]\) c. \(\left[\begin{array}{rrr}2 & -1 & 0 \\ -1 & 4 & 2 \\ 0 & 2 & 2\end{array}\right]\) d. \(\left[\begin{array}{rrrr}2 & 3 & 1 & 2 \\ -2 & 4 & -1 & 5 \\ 3 & 7 & 1.5 & 1 \\ 6 & -9 & 3 & 7\end{array}\right]\)

Consider the following matrices. Find the permutation matrix \(P\) so that \(P A\) can be factored into the product \(L U\), where \(L\) is lower triangular with 1 s on its diagonal and \(U\) is upper triangular for these matrices. a. \(\quad A=\left[\begin{array}{rrr}1 & 2 & -1 \\ 2 & 4 & 0 \\ 0 & 1 & -1\end{array}\right]\) b. \(\quad A=\left[\begin{array}{rrr}0 & 1 & 1 \\ 1 & -2 & -1 \\ 1 & -1 & 1\end{array}\right]\) c. \(\quad A=\left[\begin{array}{rrrr}1 & 1 & -1 & 0 \\ 1 & 1 & 4 & 3 \\ 2 & -1 & 2 & 4 \\ 2 & -1 & 2 & 3\end{array}\right]\) d. \(\quad A=\left[\begin{array}{rrrr}0 & 1 & 1 & 2 \\ 0 & 1 & 1 & -1 \\ 1 & 2 & -1 & 3 \\ 1 & 1 & 2 & 0\end{array}\right]\)

Use Gaussian elimination and three-digit chopping arithmetic to solve the following linear systems, and compare the approximations to the actual solution. a. \(\quad \begin{aligned} 0.03 x_{1}+58.9 x_{2} &=59.2 \\ 5.31 x_{1}-6.10 x_{2} &=47.0 . \end{aligned}\) Actual solution \([10,1]\). b. $$ \begin{aligned} 3.03 x_{1}-12.1 x_{2}+14 x_{3} &=-119 \\ -3.03 x_{1}+12.1 x_{2}-7 x_{3} &=120 \\ 6.11 x_{1}-14.2 x_{2}+21 x_{3} &=-139 \end{aligned} $$ Actual solution \(\left[0,10, \frac{1}{7}\right]\). c. \(1.19 x_{1}+2.11 x_{2}-100 x_{3}+x_{4}=1.12\), $$ 14.2 x_{1}-0.122 x_{2}+12.2 x_{3}-x_{4}=3.44 $$ $$ \begin{aligned} 100 x_{2}-99.9 x_{3}+x_{4} &=2.15 \\ 15.3 x_{1}+0.110 x_{2}-13.1 x_{3}-x_{4} &=4.16 \end{aligned} $$ Actual solution \([0.176,0.0126,-0.0206,-1.18]\) d. $$ \begin{aligned} &\pi x_{1}-e x_{2}+\sqrt{2} x_{3}-\sqrt{3} x_{4}=\sqrt{11} \\ &\pi^{2} x_{1}+e x_{2}-e^{2} x_{3}+\frac{3}{7} x_{4}=0 \\ &\sqrt{5} x_{1}-\sqrt{6} x_{2}+x_{3}-\sqrt{2} x_{4}=\pi \\ &\pi^{3} x_{1}+e^{2} x_{2}-\sqrt{7} x_{3}+\frac{1}{9} x_{4}=\sqrt{2} \end{aligned} $$ Actual solution \([0.788,-3.12,0.167,4.55]\)

Let \(A\) be a \(3 \times 3\) matrix. Show that if \(\tilde{A}\) is the matrix obtained from \(A\) using any of the operations $$ \left(E_{1}\right) \leftrightarrow\left(E_{2}\right), \quad\left(E_{1}\right) \leftrightarrow\left(E_{3}\right), \quad \text { or } \quad\left(E_{2}\right) \leftrightarrow\left(E_{3}\right) $$ then \(\operatorname{det} \tilde{A}=-\operatorname{det} A\)

Use Crout factorization for tridiagonal systems to solve the following linear systems. a. \(\begin{aligned} x_{1}-x_{2} &=0 \\\\-2 x_{1}+4 x_{2}-2 x_{3} &=-1 \\\\-x_{2}+2 x_{3} &=1.5 \end{aligned}\) b. \(\begin{aligned} 3 x_{1}+x_{2} &=-1 \\ 2 x_{1}+4 x_{2}+x_{3} &=7 \\ 2 x_{2}+5 x_{3} &=9 \end{aligned}\) c. \(\begin{aligned} 2 x_{1}-x_{2} &=3 \\\\-x_{1}+2 x_{2}-x_{3} &=-3 \\\\-x_{2}+2 x_{3} &=1 \end{aligned}\) d. \(\begin{aligned} 0.5 x_{1}+0.25 x_{2} &=0.35, \\ 0.35 x_{1}+0.8 x_{2}+0.4 x_{3} &=0.77 \\ 0.25 x_{2}+\quad x_{3}+0.5 x_{4} &=-0.5, \\ x_{3}-2 x_{4} &=-2.25 . \end{aligned}\)

Prove that \(A B\) is nonsingular if and only if both \(A\) and \(B\) are nonsingular.

a. Show that the \(L U\) Factorization Algorithm requires $$ \frac{1}{3} n^{3}-\frac{1}{3} n \text { multiplications/divisions and } \frac{1}{3} n^{3}-\frac{1}{2} n^{2}+\frac{1}{6} n \text { additions/subtractions. } $$ b. Show that solving \(L \mathbf{y}=\mathbf{b}\), where \(L\) is a lower- triangular matrix with \(l_{i i}=1\) for all \(i\), requires \(\frac{1}{2} n^{2}-\frac{1}{2} n\) multiplications/divisions and \(\frac{1}{2} n^{2}-\frac{1}{2} n\) additions/subtractions. c. Show that solving \(A \mathbf{x}=\mathbf{b}\) by first factoring \(A\) into \(A=L U\) and then solving \(L \mathbf{y}=\mathbf{b}\) and \(U \mathbf{x}=\mathbf{y}\) requires the same number of operations as the Gaussian Elimination Algorithm 6.1. d. Count the number of operations required to solve \(m\) linear systems \(A \mathbf{x}^{(k)}=\mathbf{b}^{(k)}\) for \(k=1, \ldots, m\) by first factoring \(A\) and then using the method of part (c) \(m\) times.

a. Show that the product of two \(n \times n\) lower triangular matrices is lower triangular. b. Show that the product of two \(n \times n\) upper triangular matrices is upper triangular. c. Show that the inverse of a nonsingular \(n \times n\) lower triangular matrix is lower triangular.

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?

Use Crout factorization for tridiagonal systems to solve the following linear systems. a. \(\begin{aligned} 2 x_{1}+x_{2} &=3 \\ x_{1}+2 x_{2}+x_{3} &=-2 \\ 2 x_{2}+3 x_{3} &=0 \end{aligned}\) b. \(\begin{aligned} 2 x_{1}-x_{2} &=5 \\\\-x_{1}+3 x_{2}+x_{3} &=4 \\ x_{2}+4 x_{3} &=0 \end{aligned}\) c. \(\begin{aligned} 2 x_{1}-x_{2} &=3, \\ x_{1}+2 x_{2}-x_{3} &=4 \\ x_{2}-2 x_{3}+x_{4} &=0, \\ x_{3}+2 x_{4} &=6 . \end{aligned}\) d. \(\begin{aligned} 2 x_{1}-x_{2} &=1, \\ x_{1}+2 x_{2}-x_{3} &=2, \\ 2 x_{2}+4 x_{3}-x_{4} &=-1 \\ 2 x_{4}-x_{5} &=-2 \\ x_{4}+2 x_{5} &=-1 \end{aligned}\)