Numerical Analysis - August 2025

Problem 1

(10 points) Let $A,B\in {ℂ}^{m\times m}$ be arbitrary matrices. Show that

$$\parallel AB{\parallel }_F\le \parallel A{\parallel }_2\parallel B{\parallel }_F,$$

where $\parallel \cdot {\parallel }_2$ and $\parallel \cdot {\parallel }_F$ denote the 2-norm and Frobenius norm, respectively.

Problem 2

(10 points) Let $A\in {ℝ}^{n\times n}$ be a symmetrical positive definite matrix. Show that the following holds:

$$\parallel x{\parallel }_2^2\le \parallel A^{-1}{\parallel }_2\parallel x{\parallel }_A^2$$

where $x\in {ℝ}^n$ is arbitrary, and $\parallel x{\parallel }_A^2=⟨Ax,x⟩$; here $⟨\cdot ,\cdot ⟩$ is the Euclidean inner product.

Problem 3

(15 points) Show that if $A\in {ℝ}^{m\times m}$ is symmetric and positive definite, then solving the linear system $Ax=b$ amounts to computing

$$x=\sum _{i=1}^m\frac{c_i}{{\lambda }_i}{v}_i,$$

where ${\lambda }_i$ are the eigenvalues of $A$ and $v_i$ are the corresponding eigenvectors, and $c_i$ are some constants determined by $b$ and $v_i$.

Problem 4

(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 5

Suppose $X\in {ℝ}^{p\times n}$, $Y\in {ℝ}^{p\times n}$, $rank\left(X\right)=r_x$, and $rank\left(Y\right)=r_y$. Let $X^{T}Y=0$. Show that the following inequalities hold:

1. (5 points) $r_x+r_y\le n$;

2. (5 points) ${\sigma }_k(X+Y)\ge max({\sigma }_k\left(X\right),{\sigma }_k\left(Y\right))$ for $k\ge 1$, where ${\sigma }_k\left(X\right)$ indicates the k-th singular value of $X$.

Problem 6

Consider the following linear system,

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

where

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

1. (5 points) Prove that the $n\times n$ tridiagonal matrix $A$ is symmetric, positive definite (SPD).

2. (5 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. (5 points) Design an $O\left(n\right)$ algorithm to solve the linear system $Ax=F$.

Problem 7

Let $A\in {ℝ}^{m\times n}$, $rank\left(A\right)=r$, and $b\in {ℝ}^m$, and consider the system $Ax=b$ with unknown $x\in {ℝ}^n$. Making no assumption about the relative sizes of $n$ and $m$, we formulate the following least-squares problem:

of all the $x\in {ℝ}^n$ that minimizes $\parallel b-Ax{\parallel }_2$, find the one for which $\parallel x{\parallel }_2$ is minimized.

1. (5 points) Show that the set $\Gamma$ of all minimizers of the least-squares function is a closed convex set:

$$\Gamma =\{x\in {ℝ}^n:\parallel Ax-b{\parallel }_2=\underset{v\in {ℝ}^n}{min}\parallel Av-b{\parallel }_2\}.$$

2. (5 points) Show that the minimum-norm element in $\Gamma$ is unique.

3. (5 points) Show that the minimum norm solution is $x=A^{+}b=V{\Sigma }^{+}{U}^{*}b$, where $A=U\Sigma V^{*}$, and ${\Sigma }^{+}$ is the pseudo-inverse of $\Sigma$.

Problem 8

(15 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.\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^{*}$ 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$.