Numerical Analysis - January 2025

Problem 1

(15 points) Let $A\in {ℂ}^{m\times n}$, $m\ge n$, with linearly independent columns:

$$A=[a_1,\cdots ,a_n].$$

What are the eigenvalues and eigenvectors of the projection matrix

$$P=I-A{\left(A^{*}A\right)}^{-1}{A}^{*}?$$

Problem 2

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

(15 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 4

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

(15 points) Let $A\in {ℂ}^{2n\times 2n}$ and $B\in {ℂ}^{n\times n}$, and let $I$ be the $n\times n$ identity matrix. Let

$$A=\left[\begin{array}{cc}\hfill I\hfill & \hfill B\hfill \\ \hfill B^H\hfill & \hfill I\hfill \end{array}\right]$$

with $\parallel B{\parallel }_2<1$, where $B^H$ is the Hermitian conjugate of $B$. Show that

$$\parallel A{\parallel }_2\parallel A^{-1}{\parallel }_2=\frac{1+\parallel B{\parallel }_2}{1-\parallel B{\parallel }_2}.$$

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$.