Numerical Analysis - August 2022

Problem 1

(10 points) If $A\in {ℝ}^{n\times n}$ is symmetric and positive definite, show that

$$\left|a_{i,j}\right|\le \frac{1}{2}(a_{i,i}+a_{j,j})$$

holds for all $1\le i,j\le n$.

Problem 2

(10 points) Let $A\in {ℂ}^{m\times n}$ with $m\ge n$. Show that $A^{*}A$ is nonsingular if and only if $A$ has full rank.

Problem 3

(10 points) Let $A\in {ℂ}^{m\times m}$, and let $a_j$ be its jth column. Prove the following inequality:

$$|det\left(A\right)|\le \prod _{j=1}^m\parallel a_j{\parallel }_2.$$

Problem 4

Let

$$T=\left(\begin{array}{ccc}\hfill 4& \hfill 1& \hfill 0\\ \hfill 1& \hfill 2& \hfill -1\\ \hfill 0& \hfill -1& \hfill 3\end{array}\right).$$

1. (5 points) Use Gerschgorin’s disk theorem to show that T is positive semidefinite.
2. (5 points) Without computing the eigenvalues, explain why these eigenvalues are real.

Problem 5

Let

$$B=\left(\begin{array}{ccc}\hfill 3& \hfill -6& \hfill 41/5\\ \hfill 0& \hfill 1& \hfill 1\\ \hfill 4& \hfill -8& \hfill 63/5\end{array}\right).$$

1. (10 points) Find the QR decomposition of B using the Gram-Schmidt orthogonalization process.
2. (10 points) Write down the unitary Householder reflector matrix that you should multiply against B in order to zero out all but the first entry of its first column.

Problem 6

Consider the following linear system,

$$Ax=F,\left(1\right)$$

where

$$A=\left[\begin{array}{cccccc}\hfill 2& \hfill -1& \hfill 0& \hfill \cdots & \hfill \cdots & \hfill 0\\ \hfill -1& \hfill 2& \hfill -1& \hfill 0& \hfill \cdots & \hfill 0\\ \hfill 0& \hfill -1& \hfill 2& \hfill -1& \hfill \ddots & \hfill ⋮\\ \hfill ⋮& \hfill \ddots & \hfill \ddots & \hfill \ddots & \hfill \ddots & \hfill ⋮\\ \hfill ⋮& \hfill \cdots & \hfill 0& \hfill -1& \hfill 2& \hfill -1\\ \hfill \cdots & \hfill \cdots & \hfill \cdots & \hfill 0& \hfill -1& \hfill 2\end{array}\right].$$

1. (10 points) Prove that the n × n tridiagonal matrix A is symmetric, positive definite (SPD).
2. (10 points) Let B be a tridiagonal SPD matrix in the form of the matrix A. Prove that the Cholesky factor L of B has nonzero entries only along the main diagonal and the sub-diagonal lines, where $B=L{L}^t$. Give the formula for L.
3. (10 points) Design an $O\left(n\right)$ algorithm to solve the linear system $Ax=F$.

Problem 7

(10 points) Let $x_j\in {ℝ}^m$ be the j-th column of $X\in {ℝ}^{m\times n}$ be given. Let $y\in {ℝ}^m$ and $\lambda >0$ also be given. Given a vector $w\in {ℝ}^n$, define the following function

$$J\left(w\right)=\parallel Xw-y{\parallel }_2^2+\lambda \parallel w{\parallel }_1,$$

where $\parallel \cdot {\parallel }_2$ and $\parallel \cdot {\parallel }_1$ denote the 2- and 1-norm in ${ℝ}^n$, respectively. Letting the i-th component $w_i$ of $w$ vary and the other components of $w$ be fixed, consider the following one-variable minimization problem reduced from $J\left(w\right)$:

$$\begin{array}{cc}\hfill \underset{w_i}{min}f\left(w_i\right)& \equiv \underset{w_i}{min}\parallel \sum _{j=1}^n{w}_j{x}_j-y{\parallel }_2^2+\lambda \left|w_i\right|+\lambda \sum _{j\ne i}\left|w_j\right|\hfill \\ \hfill & =\underset{w_i}{min}\parallel w_i{x}_i+r{\parallel }_2^2+\lambda \left|w_i\right|+C\hfill \\ \hfill & =\underset{w_i}{min}\sum _{j=1}^m{(w_i{x}_{ji}+r_j)}^2+\lambda \left|w_i\right|+C,\left(2\right)\hfill \end{array}$$

where $r\equiv {\sum }_{j\ne i}{w}_j{x}_j-y$ is in ${ℝ}^m$ with $r={\left(r_k\right)}_{m\times 1}$, and $C=\lambda {\sum }_{j\ne i}\left|w_j\right|$. Show that the optimal solution $w_i^{*}$ for the minimization problem (2) is given by

$$w_i^{*}=\{\begin{array}{cc}0\hfill & \mathrm{\text{if}}\left|a\right|\le \lambda ,\hfill \\ \frac{-\lambda +a}{b}\hfill & \mathrm{\text{if}}\frac{-\lambda +a}{b}>0,\hfill \\ \frac{\lambda +a}{b}\hfill & \mathrm{\text{if}}\frac{\lambda +a}{b}<0,\hfill \end{array}$$

where $a=-{\sum }_{j=1}^{m}2x_{ji}{r}_j$ and $b={\sum }_{j=1}^{m}2x_{ji}^2$.