Numerical Methods Qualification Exam Problems and Solutions (University of Maryland)/August 2008

Problem 1

Let $A\in {ℝ}^{m\times n},b\in {ℝ}^m,$ and $p\in {ℝ}^n$, with $m>n$, and let $\delta$ be a scalar. Show how the constrained least squares problem, $\text{minimize }\Vert b-Ax{\Vert }_2\text{ subject to }{p}^{T}x=\delta$ can be reduced to solving a related unconstrained least squares problem. The algorithm should start by finding a Householder transformation $H$ such that $Hp=\Vert p{\Vert }_2{e}_1$ and setting $y=Hx$

Solution 1

Since Householder Matrices are orthogonal and hermitian (i.e. symmetric if the matrix is real), we have

$y=Hx\Rightarrow x=H^{T}y=Hy$

Then the constraint can be written

$\begin{array}{cc}{p}^{T}x& =\delta \\ p^T(H^{T}y)& =\delta \\ (Hp{)}^{T}y& =\delta \\ (\Vert p{\Vert }_2{e}_1{)}^{T}y& =\delta \\ \Vert p{\Vert }_2{e}_1^{T}y& =\delta \\ y_1& =\frac{\delta }{\Vert p{\Vert }_2}\end{array}$

Hence, the first entry of the column vector $y$, $y_1$(a scalar), represents our constraint.

Now we want to show that we can write $\Vert Ax-b{\Vert }_2$ as a related unconstrained problem. Substituting for $x$ in $Ax$ we get,

$Ax=AHy$

Let $AH=B=\left[\begin{array}{cc}{B}_1& \hat{B}\end{array}\right]$ where $B_1$ is the first column of $B$ and $\hat{B}$ are the remaining columns.

Since,

$y=\left[\begin{array}{c}{y}_1\\ \hat{y}\end{array}\right]$

block matrix multiplication yields,

$\begin{array}{cc}AHy& =By\\ & =\left[\begin{array}{cc}{B}_1& \hat{B}\end{array}\right]\left[\begin{array}{c}{y}_1\\ \hat{y}\end{array}\right]\\ & =y_1{B}_1+\hat{B}\hat{y}\end{array}$

So $\underset{y}{\min }\Vert b-AHy{\Vert }_2=\underset{\hat{y}}{\min }\Vert b-y_1{B}_1-\hat{B}\hat{y}{\Vert }_2$ , which is unconstrained.

Problem 2

Prove or disprove the following interpolants exist for all values of $y_1,y_2,y_3$ and all distinct values of $x_1,x_2,x_3$.

Problem 2a

$a.y_i=c_1+c_2{x}_i+c_3{x}_i^2$

Solution 2a

Substituting into this equation the pairs $x_i,y_i,i=1,2,3,$ gives rise to the following matrix equation:

$\left[\begin{array}{c}{y}_1\\ y_2\\ y_3\end{array}\right]=\underset{A}{\underbrace{\left[\begin{array}{ccc}1& x_1& x_1^2\\ 1& x_2& x_2^2\\ 1& x_3& x_3^2\end{array}\right]}}\left[\begin{array}{c}{c}_1\\ c_2\\ c_3\end{array}\right]$

Where A is the Vandermonde matrix, which is know to be non-singular. This proves existence and uniqueness of the coefficients $c_1,c_2,c_3$.

Problem 2b

$b.y_i=c_1+c_2{x}_i^2+c_3{x}_i^4$

Solution 2b

Now, substituting the pairs $x_i,y_i,i=1,2,3,$ gives:

$\left[\begin{array}{c}{y}_1\\ y_2\\ y_3\end{array}\right]=\left[\begin{array}{ccc}1& x_1^2& x_1^4\\ 1& x_2^2& x_2^4\\ 1& x_3^2& x_3^4\end{array}\right]\left[\begin{array}{c}{c}_1\\ c_2\\ c_3\end{array}\right]$

Consider the unique set of points $x_1=1,x_2=-1,x_3=0.$

The system reduces to

$\left[\begin{array}{c}{y}_1\\ y_2\\ y_3\end{array}\right]=\underset{A}{\underbrace{\left[\begin{array}{ccc}1& 1& 1\\ 1& 1& 1\\ 1& 0& 0\end{array}\right]}}\left[\begin{array}{c}{c}_1\\ c_2\\ c_3\end{array}\right]$

Here, the matrix $A$ is clearly singular.

More generally, the determinant of the matrix $A$ is given by

$\left|\begin{array}{ccc}1& x_1^2& x_1^4\\ 1& x_2^2& x_2^4\\ 1& x_3^2& x_3^4\end{array}\right|=(x_2^2-x_1^2)(x_3^2-x_1^2)(x_3^2-x_2^2)=0$ if $x_j=-x_i$ for any $i\ne j$

Problem 3

Consider the linear system of equations $Ax=b$ where $A$ is a symmetric positive definite matrix of order $n$. The conjugate gradient method (CG) for solving this system is Choose $x_0$, compute $r_0=b-A{x}_0$ Set $p_0=r_0$ for $k=0$ until convergence ${\alpha }_k=(r_k,r_k)/(p_k,A{p}_k)$ $x_{k+1}=x_k+{\alpha }_k{p}_k$ $r_{k+1}=r_k-{\alpha }_{k}A{p}_k$ <Test for Convergence> ${\beta }_k=(r_{k+1},r_{k+1})/(r_k,r_k)$ $p_{k+1}=r_{k+1}+{\beta }_k{p}_k$ end where $(v,w)=\sum _{i=1}^n{v}_i{w}_i$ is the Euclidean inner product. Let $Q$ be some other symmetric positive-definite matrix of order $n$. We know that the forms $⟨v,w{⟩}_A\equiv (Av,w)⟨v,w{⟩}_Q\equiv (Qv,w)$ are inner products on $R^n$. In addition, a matrix $M$ is symmetric with respect to the $Q$ inner product $⟨,{⟩}_Q$ if $⟨Mv,w{⟩}_Q=⟨v,Mw{⟩}_Q$ for all $v,w$ in $R^n$, and $M$ is positive definite with respect to $⟨,{⟩}_Q$ if $⟨Mv,v{⟩}_Q>0$ for all nonzero $v$

Problem 3a

Show that $Q^{-1}A$ is symmetric and positive-definite with respect to the $Q$-inner product.

Solution 3a

$\begin{array}{cc}⟨Q^{-1}Av,w{⟩}_Q& =(Q{Q}^{-1}Av,w)\\ & =(Av,w)\\ ⟨v,Q^{-1}Aw{⟩}_Q& =(Qv,Q^{-1}Aw)\\ & =(Q^{-T}Qv,Aw)\\ & =(Q^{-1}Qv,Aw)\\ & =(v,Aw)\\ & =(A^{T}v,w)\\ & =(Av,w)\\ \\ ⟨Q^{-1}Av,v{⟩}_Q& =(Q{Q}^{-1}Av,v)\\ & =(Av,v)\\ & >0\\ \end{array}$

Problem 3b

In light of this fact, CG can be used to solve the system $Q^{-1}Ax=Q^{-1}b$ in an appropriate manner. Specify this algorithm and identify any extra costs required that would not be present with $Q=I$.

Solution 3b

Choose $x_0$
$r_0=b-A{x}_0$
${\tilde{r}}_0$ :  solve $Q{\tilde{r}}_0=r_0$
$p_0={\tilde{r}}_0$
for $k=0,1,2,...$ until convergence
 ${\alpha }_k=(r_k,{\tilde{r}}_k)/(p_k,A{p}_k)$
 $x_{k+1}=x_k+{\alpha }_k{p}_k$
 $r_{k+1}=r_k-{\alpha }_{k}A{p}_k$
 <Test for Convergence>
 ${\tilde{r}}_{k+1}$ :  solve $Q{\tilde{r}}_{k+1}=r_{k+1}$
 ${\beta }_k=(r_{k+1},{\tilde{r}}_{k+1})/(r_k,{\tilde{r}}_k)$
 $p_{k+1}={\tilde{r}}_{k+1}+{\beta }_k{p}_k$
end

One additional cost is computing $Q^{-1}$.

Another one-time cost is multiplying $Q^{-1}A$ which has cost $n^3$ and $Q^{-1}b$ which has cost $n^2$.

Problem 3c

Use any facts you know about the conjugate gradient method to identify properties of $Q$ that would be desirable for computing the solution $x$ efficiently.

Solution 3c

We want $Q^{-1}A$ to have eigenvalues whose values are close together. This accelerates convergence. Furthermore, if there are only $k$ distinct eigenvalues, the algorithm will terminate in $k$ steps.