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

Problem 1

Let $A\in \mathbb {R} ^{m\times n},b\in \mathbb {R} ^{m},\!\,$ and $p\in \mathbb {R} ^{n}$, with $m>n\!\,$, and let $\delta \!\,$ be a scalar. Show how the constrained least squares problem, ${\mbox{minimize }}\|b-Ax\|_{2}\quad \quad {\mbox{ 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=\|p\|_{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{aligned}p^{T}x&=\delta \\p^{T}(H^{T}y)&=\delta \\(Hp)^{T}y&=\delta \\(\|p\|_{2}e_{1})^{T}y&=\delta \\\|p\|_{2}e_{1}^{T}y&=\delta \\y_{1}&={\frac {\delta }{\|p\|_{2}}}\end{aligned}}$

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 $\|Ax-b\|_{2}\!\,$ as a related unconstrained problem. Substituting for $x\!\,$ in $Ax\!\,$ we get,

$Ax=AHy\!\,$

Let $AH=B={\begin{bmatrix}B_{1}&{\hat {B}}\end{bmatrix}}$ where $B_{1}\!\,$ is the first column of $B\!\,$ and ${\hat {B}}\!\,$ are the remaining columns.

Since,

$y={\begin{bmatrix}y_{1}\\{\hat {y}}\end{bmatrix}}$

block matrix multiplication yields,

${\begin{aligned}AHy&=By\\&={\begin{bmatrix}B_{1}&{\hat {B}}\end{bmatrix}}{\begin{bmatrix}y_{1}\\{\hat {y}}\end{bmatrix}}\\&=y_{1}B_{1}+{\hat {B}}{\hat {y}}\end{aligned}}$

So $\min _{y}\|b-AHy\|_{2}=\min _{\hat {y}}\|b-y_{1}B_{1}-{\hat {B}}{\hat {y}}\|_{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.\qquad 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:

${\begin{bmatrix}y_{1}\\y_{2}\\y_{3}\end{bmatrix}}=\underbrace {\begin{bmatrix}1&x_{1}&x_{1}^{2}\\1&x_{2}&x_{2}^{2}\\1&x_{3}&x_{3}^{2}\end{bmatrix}} _{A}{\begin{bmatrix}c_{1}\\c_{2}\\c_{3}\end{bmatrix}}$

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.\qquad 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:

${\begin{bmatrix}y_{1}\\y_{2}\\y_{3}\end{bmatrix}}={\begin{bmatrix}1&x_{1}^{2}&x_{1}^{4}\\1&x_{2}^{2}&x_{2}^{4}\\1&x_{3}^{2}&x_{3}^{4}\end{bmatrix}}{\begin{bmatrix}c_{1}\\c_{2}\\c_{3}\end{bmatrix}}$

Consider the unique set of points $x_{1}=1,\ x_{2}=-1,\ x_{3}=0.\$

The system reduces to

${\begin{bmatrix}y_{1}\\y_{2}\\y_{3}\end{bmatrix}}=\underbrace {\begin{bmatrix}1&1&1\\1&1&1\\1&0&0\end{bmatrix}} _{A}{\begin{bmatrix}c_{1}\\c_{2}\\c_{3}\end{bmatrix}}$

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\neq 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-Ax_{0}$ Set $\!\,p_{0}=r_{0}$ for $\!\,k=0$ until convergence $\!\,\alpha _{k}=(r_{k},r_{k})/(p_{k},Ap_{k})$ $\!\,x_{k+1}=x_{k}+\alpha _{k}p_{k}$ $\!\,r_{k+1}=r_{k}-\alpha _{k}Ap_{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 $\langle v,w\rangle _{A}\equiv (Av,w)\quad \quad \quad \langle v,w\rangle _{Q}\equiv (Qv,w)$ are inner products on $\!\,R^{n}$. In addition, a matrix $M\,\!$ is symmetric with respect to the $Q\,\!$ inner product $\langle \,,\,\rangle _{Q}\,\!$ if $\langle Mv,w\rangle _{Q}=\langle v,Mw\rangle _{Q}\,\!$ for all $v,w\,\!$ in $R^{n}\,\!$, and $M\,\!$ is positive definite with respect to $\langle \,,\,\rangle _{Q}\,\!$ if $\langle Mv,v\rangle _{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{aligned}\langle Q^{-1}Av,w\rangle _{Q}&=(QQ^{-1}Av,w)\\&=(Av,w)\\\langle v,Q^{-1}Aw\rangle _{Q}&=(Qv,Q^{-1}Aw)\\&=(Q^{-T}Qv,Aw)\\&=(Q^{-1}Qv,Aw)\\&=(v,Aw)\\&=(A^{T}v,w)\\&=(Av,w)\\\\\langle Q^{-1}Av,v\rangle _{Q}&=(QQ^{-1}Av,v)\\&=(Av,v)\\&>0\\\end{aligned}}$

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-Ax_{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},Ap_{k})$
 $\!\,x_{k+1}=x_{k}+\alpha _{k}p_{k}$
 $\!\,r_{k+1}=r_{k}-\alpha _{k}Ap_{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.