CSL361 Problem set 6: Error analysis of $LU$ and some extensions

1. Assume that $A$ is an $n \times n$ matrix of floating point numbers. If no zero pivot is encountered during the execution of $LU$ decomposition (without pivoting), then show that the computed triangular matrices $\hat{L}$ and $\hat{U}$ satisfy
   $$\begin{array}{l} \hat{L}\hat{U} = A + H \\ \vert H\vert \leq 3(n-1)\mu (\vert A\vert + \vert\hat{L}\vert\vert\hat{U}\vert) + O(\mu^2) \end{array}$$

2. Suppose the $\hat{L}$ and $\hat{U}$ computed as above are used in backward and forward substitutions to obtain computed solutions $\hat{y}$ and $\hat{x}$ to $\hat{L}y = b$ and $\hat{U}x = \hat{y}$ respectively. Show that then $(A + E)\hat{x} = b$ with
   $$\vert E\vert \leq n \mu (3\vert A\vert + 5 \vert\hat{L}\vert\vert\hat{U}\vert) + + O(\mu^2)$$

3. Gauss-Jordan elimination is a variation of standard Gaussian elimination in which the matrix is reduced to a diagonal form than merely to a traingular form. The elimination matrix used for a given column vector $a$ is of the form
   $$\left[ \begin{array}{ccccccc} 1 & \ldots & 0 & -m_1 & 0 & \ldots ... ...egin{array}{c} 0 \\ \vdots \\ 0 \\ a_k \\ 0 \\ \vdots \\ 0 \end{array}\right]$$
   where $m_i = a_1/a_k, i=1:n$. Under what situations will Gauss-Jordan elimination be useful? What is its work-load? What are the disadvantages? What can you say about its numerical stability?
4. Show that if all the leading principal submatrices of $A \in \mathbb{R}^{n \times n}$ are nonsingular, then there exists unique lower-triangular matrices $L$ and $M$ and a unique diagonal matrix $D$ such that $A = L D M^t$. How can the factorization be computed?
5. Show that if $A = L D M^t$ and $A$ is symmetric, then $L = M$.
6. A matrix $A$ is positive definite if $x^t Ax > 0$ for all non-zero $x \in \mathbb{R}^n$. Show that if $A$ is positive definite then it is non-singular.
7. Show that if $A \in \mathbb{R}^{n \times n}$ is positive definite and $X \in \mathbb{R}^{n \times k}$ has rank $k$, then $B = X^t AX \in \mathbb{R}^{k \times k}$ is also positive definite.
8. Show that if $A$ is positive definite then all its principal matrices are also positive definite. In particular, show that all diagonal entries are positive.
9. Show that for a positive definite $A$ the factorization $A = L D M^t$ exists and all elements of $D$ are positive.
10. Cholesky factorization: Show that if $A \in \mathbb{R}^{n \times n}$ is symmetric and positive definite, then there exists a unique lower-triangular matrix $L \in \mathbb{R}^{n \times n}$ with positive diagonal entries such that $A = LL^t$. Give an algorithm for Cholesky factorization.
11. Show that if $A$ is a symmetric matrix and $P$ is a permutation matrix, then the update $PAP^t$ preserves symmetry. Use the above to give an algorithm for Cholesky factorization with pivoting.
12. Given $A \in \mathbb{R}^{m \times n}$ with the property that $rank(A) =n$ and $b \in \mathbb{R}^m$, show that the following algorithm computes the least square solution $min \vert\vert Ax -b \vert\vert _2$.
    $$\begin{array}{l} \mbox{Compute the lower triangular portion of } ... ...rization} C = LL^t \\ \mbox{Solve } Ly = d \mbox{ and } L^t x = y \end{array}$$
    Show that the least square solution is unique. What is the total work-load? Is there any advantage over standard Gaussian elimination?
13. Let $A \in \mathbb{R}^{m \times n}$ with $m \geq n$ and $b \in \mathbb{R}^m$ be given and suppose that an orthogonal matrix $Q \in \mathbb{R}^{m \times m}$ has been computed such that
    $$Q^t A = R = \left[ \begin{array}{c} R_1 \\ 0 \end{array} \right] \begin{array}{c} n \\ m-n \end{array}$$
    is upper-triangular. If
    $$Q^t b = \left[ \begin{array}{c} c \\ d \end{array} \right] \begin{array}{c} n \\ m-n \end{array}$$
    show that,
    $$\vert\vert Ax - b\vert\vert^2_2 = \vert\vert Q^t Ax - Q^t b\vert\vert^2_2 = \vert\vert R_1x - c\vert\vert^2_2 + \vert\vert d\vert\vert^2_2$$
    for any $x \in \mathbb{R}^n$. Also, if $rank(A) = rank(R_1) = n$ then the least square solution is defined by $R_1 x = c$ with a residual error of $\vert\vert d\vert\vert^2_2$. What is the total-work-load if the $QR$ factorization is computed using Modified Gram-Schmidt? How does it compare with Cholesky?