Let

Factor A into a product LU, where L is lower triangular with 1’s along the diagonal and U is upper triangular.

Let A be the matrix in Exercise 1. Use the LU factorization of A to solve $A\mathbf{x}=\mathbf{b}$ for each of the following choices of b:

1. ${(4,3,-13)}^T$

2. ${(3,1,-10)}^T$

3. ${(7,23,0)}^T$

Let A and B be $n\times n$ matrices and let $\mathbf{x}\in {ℝ}^n$.

1. How many scalar additions and multiplications are necessary to compute the product Ax?

2. How many scalar additions and multiplications are necessary to compute the product AB?

3. How many scalar additions and multiplications are necessary to compute (AB)x? To compute A(Bx)?

Let $A\in {ℝ}^{m\times n},B\in {ℝ}^{n\times r}$, and $\mathbf{\text{x}},\mathbf{\text{y}}\in {\mathbb{\text{R}}}^n$. Suppose that the product $A{\mathbf{\text{xy}}}^{T}B$ is computed in the following ways:

1. $\left(A\left({\mathbf{\text{xy}}}^T\right)\right)B$

2. $\left(A\mathbf{x}\right)\left({\mathbf{y}}^{T}B\right)$

3. $\left(\left(A\mathbf{x}\right){\mathbf{y}}^T\right)B$

1. How many scalar additions and multiplications are necessary for each of these computations?

2. Compare the number of scalar additions and multiplications for each of the three methods when $m=5,n=4$, and $r=3$. Which method is most efficient in this case?

Let $E_{ki}$ be the elementary matrix formed by subtracting $\alpha$ times the ith row of the identity matrix from the kth row.

1. Show that $E_{ki}=I-\alpha {\mathbf{\text{e}}}_k{\mathbf{\text{e}}}_i^T$.

2. Let $E_{ji}=I-\beta {\mathbf{\text{e}}}_j{\mathbf{\text{e}}}_i^T$. Show that $E_{ji}{E}_{ki}=I-(\alpha {\mathbf{\text{e}}}_k+\beta {\mathbf{\text{e}}}_j){\mathbf{\text{e}}}_i^T$.

3. Show that $E_{ki}^{-1}=I+\alpha {\mathbf{\text{e}}}_k{\mathbf{\text{e}}}_i^T$.

Let A be an $n\times n$ matrix with triangular factorization LU. Show that

If A is a symmetric $n\times n$ matrix with triangular factorization LU, then A can be factored further into a product ${\mathit{\text{LDL}}}^T$ (where D is diagonal). Devise an algorithm, similar to Algorithm 7.2.2, for solving ${\mathit{\text{LDL}}}^T\mathbf{x}=\mathbf{b}$.

Write an algorithm for solving the tridiagonal system

by Gaussian elimination with the diagonal elements as pivots. How many additions/subtractions and multiplications/divisions are necessary?

Let $A=LU$, where L is lower triangular with 1’s on the diagonal and U is upper triangular.

1. How many scalar additions and multiplications are necessary to solve $L\mathbf{y}={\mathbf{e}}_j$ by forward substitution?

2. How many additions/subtractions and multiplications/divisions are necessary to solve $A\mathbf{x}={\mathbf{e}}_j$? The solution ${\mathbf{\text{x}}}_j$ of $A\mathbf{x}={\mathbf{e}}_j$ will be the jth column of $A^{-1}$.

3. Given the factorization $A=LU$, how many additional multiplications/divisions and additions/ subtractions are needed to compute $A^{-1}$?

Suppose that $A^{-1}$ and the LU factorization of A have already been determined. How many scalar additions and multiplications are necessary to compute $A^{-1}\mathbf{b}$? Compare this number with the number of operations required to solve LUx = b using Algorithm 7.2.2. Suppose that we have a number of systems to solve with the same coefficient matrix A. Is it worthwhile to compute $A^{-1}$? Explain.

Let A be a $3\times 3$ matrix and assume that A can be transformed into a lower triangular matrix L by using only column operations of type III; that is,

where $E_1,E_2,E_3$ are elementary matrices of type III. Let

Show that U is upper triangular with 1’s on the diagonal and $A=LU$. (This exercise illustrates a column version of Gaussian elimination.)